

Nested Intervals
SQL Tips by Donald Burleson 
Querying descendants has to be done
via nested intervals. Given the matrix the interval boundaries are
calculated as:
Of these two numbers which is
interval is lower bound and which is the upper bound? Let's compare
them. Multiplying both numbers to the product of their denominators
and simplifying the result, the problem is reduced to answering if
Here is the determinant expression,
again, which evaluates to 1. Hence, interval boundaries are ordered
as:
Next, how can we be sure those
intervals are indeed nested? Let's compare an arbitrary node
interval ends with that of its children. The nth child
interval encoding is:
Therefore, the child interval
boundaries are:
Note, that the second endpoint is
the same expression as the first one, with n decremented by
1. Therefore, the following must be checked for any n ≥ 1
Both inequalities reduce to correspondingly. This proves that
the parent node interval indeed contains its child interval.
The second property of nested
intervals  sibling node intervals being disjoint  can be proved in
a similar fashion.
Descendants Query
Now that the nested intervals
structure has been covered, querying the node's descendants can be
looked at. As a first approximation, let's take the descendants
query in terms of nested sets as a template and rewrite it in terms
of nested intervals:
select
descendant.*
from
MatrixTreeNodes descendant, MatrixTreeNodes node
where
descendant.a11/descendant.a21 between node.a11/node.a21
and (node.a11node.a12)/(node.a21node.a22)
and
node.name = ?  predicate uniquely identifying a node
Unfortunately, this query would
produce a wrong result. None of the database vendors support the
rational number datatype. The ratios of integers would be silently
casted into float numbers with accompanying errors due to lack of
precision. All the expressions must be rewritten with divisions
within the means of integer arithmetic:
select
descendant.*
from
MatrixTreeNodes descendant, MatrixTreeNodes node
where
descendant.a11*node.a21 >= descendant.a21*node.a11
and
descendant.a11*node.a22 >= descendant.a21*node.a12
and
node.name = ?  predicate identifying a node uniquely
When the descendant query
performance was explained in the context of nested sets, the index
range scan was emphasized as an efficient way to extract all the
descendant nodes. This idea generalizes to nested intervals,
although interval boundaries must be indexed. Let's enhance the tree
encoding schema design with two functionbased indexes:
table
MatrixTreeNodes (
a11
integer,
a12
integer,
a21
integer,
a22
integer
);
CREATE
INDEX idx_left ON MatrixTreeNodes(a11/a21);
CREATE
INDEX idx_right ON MatrixTreeNodes((a11a12)/(a21a22));
The query must be rewritten in such
a way that the optimizer can leverage these indexes:
select
descendant.*
from
MatrixTreeNodes descendant, MatrixTreeNodes node
where
descendant.a11*node.a21 >= descendant.a21*node.a11
and
descendant.a11*node.a22 >= descendant.a21*node.a12
and
descendant.a11/descendant.a21
between node.a11/node.a21  0.0000001
and
(node.a11node.a12)/(node.a21node.a22) + 0.0000001
and
node.name = ?  predicate uniquely identifying a node
The constant 0.0000001 is
designed to compensate for floating point arithmetic rounding
errors. It essentially is a minimal supported mantissa. Please refer
to your favorite database SQL manual in order to find the exact
value. This way the index range scan would capture all the nodes in
the interval, and possibly, some extra, and the small list of nodes
is filtered with the exact condition.
Ancestor Criteria
Suppose there are two nodes: one
encoded with matrix A, and the other encoded with B.
Node A is an ancestor of B if and only if there is a
directed path from A to B. In matrix terms, there has
to be a sequence of atomic matrices so that after A is
multiplied to it, matrix B is then obtained. By matrix
multiplication associativity law, all those atomic matrices can be
combined into a single matrix X. In other words, node A
is an ancestor of node B if there is matrix X such
that:
A X = B
If matrix A has inverse A1,
then when multiplying both sides to A1 the result
is:
X = A1
B
The formula for the inverse of the 2?2
matrix is where knowledge was leveraged that
the matrices always have a determinant 1. Therefore, given any nodes A and B, matrix X that encodes the path between
them can always be found.
This is absurd, as node B
might not be a descendant of A! Let's examine the phenomenon
more closely. As usual, an example might be handy. Consider the
nodes A=1.7 and B=1.3.2.5 in matrix encoding:
Then, A1B
evaluates to:
This is not a valid matrix encoding,
however. It violates the constraint that the entries in the upper
row are greater than the ones in the lower row.
Here is more detailed explanation
for why this is happening. Since matrix A is decomposed into
a product of (atomic) matrices, why not leverage the law of
inverse of matrix product:
(P
Q) 1 = Q1 P1
In the example:
Hence, A1B expands into the
following product of atomic matrices and their inverses
where collapses into the identity matrix.
This is because both A=.1.7 and B=.1.3.2.5 start with the same
prefix .1. Therefore, the above expression for A1B
simplifies to which cannot be further reduced. It
is the multiplication by an atomic matrix inverse that violates the
constraint.
In order to carry over this idea to
SQL, A1B must be written in a generic form which translates to the descendants
query from the previous section:
select B.*
from
MatrixTreeNodes A, MatrixTreeNodes B
where
B.a21*A.a12  B.a11*A.a22 > B.a11*A.a21 + B.a21*A.a11
and
B.a12*A.a22  B.a22*A.a12 > B.a22*A.a11 + B.a12*A.a21
and A.name
= ?  predicate identifying a node uniquely
Admittedly, this query is slightly
more complicated than the nested intervals version. The real
contribution of this section is introducing inverse matrices, which
will be leveraged later when relocating subtrees.