

Ancestors Query
SQL Tips by Donald Burleson 
Logically, finding
all the ancestors can be accomplished by swapping the roles of the
two join operands in the descendants query. Once again, such a query
will not be a good performer. In the section on materialized path
encoding the problem was split into two parts: computing all the
node encodings in the chain first, and extracting all the nodes by
those keys from the database, second. Since a close tie between the
materialized path and matrix encoding was introduced earlier, it
would come as no surprise that we can perform the same trick with
matrices.
Let's look into
matrix encodings of parent and child nodes one more time:
The child just
inherited the entries a_{11} and a_{21}
from its parent. Therefore, to calculate the left row entries of the
parent, just take them from the right row of the child matrix. The
right row elements are the remainders of the division of the parent
left row by the right row, and as an added bonus, the sibling order
number n was obtained.
Let's demonstrate
it on the familiar example of child node 1.3.2.5:
The modulo function
calculates the remainders:
19mod(107,19) = 7
11mod(62,11) = 4
Let's double check
the results:
107 = (5+1)*19  7
62 =
(5+1)*11 4
Hence, the parent
encoding:
This process
continues as to find the grandfather:
And to find the
grand grandfather:
which happens to be
the root  a matrix with a22 = 0. Now that we have a list of
ancestor matrices, how are they extracted from database? One
solution would be by building a dynamic query like this:
select *
from MatrixTreeNodes
where a11=19 and a12=7 and a21=11 and a22=4
or a11=7 and a12=2 and a21=4 and a22=1
or a11=2 and a12=1 and a21=1 and a22=0
Though a better
approach would be storing the ancestor encoding in a temporary
Ancestors table, and using the generic query:
select n.*
from MatrixTreeNodes n, Ancestors a
where n.a11=a.a11 and n.a12=a.a12 and n.a21=a.a21 and n.a22=a.a22
Some RDBMS engines
allow programming table functions so that the table of ancestor
encodings can be produced as an output of such a function.
Syntactically, the query would become:
select n.*
from MatrixTreeNodes n, Table(Ancestors(49,9,38,7)) a
where n.a11=a.a11 and n.a12=a.a12 and n.a21=a.a21 and n.a22=a.a22
Given the entries
a_{11}=107, a_{12}=19, a_{21}=62, and
a_{22}=11, the Ancestors table function is supposed
to calculate the chain of ancestor encodings.
Converting Matrix to Path
The previous
section revealed the identity connecting parent and child encoding
and mentioned that a sibling order number n is a remainder of
integer division floor((a11*(n+1)a12)/a12). In our example,
the node 1.3.2.5 is the 5^{th} children of the node 1.3.2:
floor(107/19) = 5
floor(62/11) = 5
Working all the way
to the root, the other numbers in the path can be found.
The path is
generated in the order from the leaf to the root. Perhaps, it would
be more convenient to generate it in the opposite order. The
procedure is essentially the same, but applied to the transposed
matrix.
Inserting Nodes
So far our
attention was on queries. But how is the tree filled with nodes? The
new node location is unambiguously defined by the node's parent and
the node's position among the other children. Normally, given a
parent, a new node is attached as the youngest child. Therefore, the
node's insertion is accomplished in two steps:
1. Query all the immediate children
and find the oldest child
select
max(floor(a11/a12)) as N from MatrixTreeNodes
where a11 = :parent_a12
and a21 = :parent_a22
where
:parent_a12 and :parent_a22 are the host variables of the
parent node encoding.
2.
Insert the node at the nth position:
insert into
MatrixTreeNodes (a11,a12,a21,a22) values
(:parent_a11*(:N+1)  :parent_a12,
:parent_a11,
:parent_a21*(:N+1)  :parent_a22,
:parent_a21);
These two steps can
be combined into a single insert as select statement.
Relocating Tree Branches
This is the section
where matrix algebra really shines. Consider a tree branch located
at the node encoded with matrix A, and suppose it is to be
moved to the new location under node B. How would the
encoding of some node C (which is located in the tree branch
under A) change?
That is quite an
easy task for materialized path encoding. First, find the path from
the node A to C. Then, append it to node B.
This idea transfers to matrices almost literally. The encoding of
node C is a product of its ancestor A and some other
matrix:
A X =
C
Matrix X
corresponds to the path from A to C. This path is
appended to path B; the matrices are multiplied and thus the
resulting encoding obtained is:
B X
The unknown matrix
X is calculated via inverse matrix, so the final answer is:
B A^{1}
C
In order to
translate this into SQL, the answer is expanded componentwise:
And can be coded in
SQL as:
update
MatrixTreeNodes c
set c.a11 = (:b12*:a21:b11*:a22)*c.a11
+(:b11*:a12:b12*:a11)*c.a21
c.a12 = (:b12*:a21:b11*:a22)*c.a12
+(:b11*:a12:b12*:a11)*c.a22
c.a21 = (:b22*:a21:b21*:a22)*c.a11
+(:b21*:a12:b22*:a11)*c.a21
c.a22 = (:b22*:a21:b21*:a22)*c.a12
+(:b21*:a12:b22*:a11)*c.a22
where c.a11*:a21 >= c.a21*:a11  all the descendants of
matrix
and c.a11*:a22 >= c.a21*:a12 
[[:a11,:a12][:a21,:a22]]