Errata

p.17
Not exactly a typo, but a comment from Laurent Schneider that grouping by the empty set can be explicitly expressed as
group by ()

p.19-21
Missing and symbols.

p.20
Missing symbols and β:

if x ≥ x₀ then else β endif

p.28 and elsewhere
inner view should read as inline view

p.21
Missing symbols and β again:

if x ≥ x₀ then else β endif = 1 _x-x0 + β 1 _x0-x

Also in the following text fragment:

Easy: the above formula for general step function should handle the case where α is an expression, rather than constant.

p.47.

Since the solution differs between various vendors, now it’s a good time to branch out this information

This was copyedited from

The solution differs between various vendors, so that we have to branch our story here.

which is IMO easier to read.

p.82
Missing symbol :

(x+1) = …

(6) = 59.589686421

p.95
Missing symbol in the expression:

(A B) \ (A B)

p.147
Another typesetting issue of missing arrow:

∅ → {A,B,C}

X → Y

p.170 (brought to my attention by Gary Howard)
Typo, the root node should be

[2 -1]
[1 0]

and not

[1 -1]
[1 0]

p.172 (by David Brusowankin)

Consider the child node 1.3.2.5 which matrix encoding is

[107 -19]
[ ]
[62 -11]

and it’s parent 1.3.2

[19 -7]
[ ]
[11 -4]

so the child.a12 = -19 is the negative of the parent.a11 = 19
and the child.a22 = -11 is the negative of the parent.a21 = 11

The queries:

Find all the employees who report directly to Jones.

select child.name
from MatrixTreeNodes parent, MatrixTreeNodes child
where parent.name = ‘Jones’
and child.a12 = parent.a11 and child.a22 = parent.a21

Who is Jones’ manager?

select parent.name
from MatrixTreeNodes parent, MatrixTreeNodes child
where child.name = ‘Jones’
and child.a12 = parent.a11 and child.a22 = parent.a21


p.173
David Brusowankin and Steve Johnston challenged the algebraic step of division removal. Here is the detailed exposition:

We take

descendant.a11/descendant.a21 <=
(node.a11-node.a12)/(node.a21-node.a22)

and multiply both sides by descendant.a21*(node.a21-node.a22) to get

descendant.a11*(node.a21-node.a22) <=
(node.a11-node.a12)*descendant.a21

which is the same as

descendant.a11*node.a21-descendant.a11*node.a22 <=
node.a11*descendant.a21-node.a12*descendant.a21


At this point we have already reached our goal and removed the division. We can try to simplify more but Steve comment makes me suspect that the following steps have an error hidden somewhere.

Given that we already have

descendant.a11*node.a21 >= node.a11*descendant.a21

we deduce

-descendant.a11*node.a22 <= -node.a12*descendant.a21

which turns to

descendant.a11*node.a22 >= node.a12*descendant.a21

p.181
Steve Johnston noticed that the parent and child matrix entries are also confused in the following query:
select max(floor(a11/a12)) as N from MatrixTreeNodes
where a12 = :parent_a11 and a22 = :parent_a21


Then, there is a case when a node has no children, so the query should be amended as follows:
select case when count(1)=0 then 0 else max(floor(a11/a12)) end as N
from MatrixTreeNodes
where a11 = :parent_a12 and a21 = :parent_a22


Finally, we want to insert into position N+1, not N, because N is occupied.

p.193
Missing symbol :

(₁,₂,₃,…,_k)

Figures for chapter 1

Figure 1.1: Cartesian product of the set A = {2,3,4,6,9} by itself. Counting all the elements x that are no greater than y produces the sequence number of y in the set A.

Figure 1.2: Cartesian product of the set A = {2,3,4,6,9} by itself. The predecessor of y is the maximal number in a set of x that are less than y. There is no predecessor for y = 2.

Figure 1.3: Indicator functions 1_A(x) and 1_B(x).

Figure 1.4: 1_A(x)+1_B(x) is not an indicator function, because it is equal to 2 for any x∈A∩B . By inclusion-exclusion principle we have to subtract 1_A(x)1_B(x).

Figure 1.5: Step function f(x)=1_x.

Figure 1.6: Endpoints of the covering interval are constructed from the endpoints of the first and last intervals in a chain of intervals with no gaps.

Figure 1.7: In the chain of intervals fst, int, lst the endpoint int.x is covered by the fst interval. Likewise, the fst.y is covered by the int.

Figure 1.8: The chain starting with the fst interval and ending with lst is not maximal, since the lst.y is covered by some other interval.

Figure 1.9: A chain of intervals beginning with fst1 and ending with lst1 has a gap. Therefore, there is an element lst2, such that lst2.y is not covered by any other interval.

Figure 1.10: Interval Packing. A set of integers 0,1,2,3,5,6,7,9 is packed into the intervals [0,3], [5,7], and [9,9].

Figures for chapter 5

Figure 5.14: Nested sets structure for the tree in fig. 5.2a with set containment reversed. Now, a child set is required to contain its parent.

Figure 5.15: A different view of the reverse nested sets structure for the tree in fig. 5.14. A set is indistinguishable from path to the root.

Advertisement