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₁₁ and a₂₁ 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:

19-mod(107,19) = 7

11-mod(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₁₁=107, a₁₂=19, a₂₁=62, and a₂₂=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 n-th 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 component-wise:

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]]