Transitive Closure and Relational Division

From: Vadim Tropashko <vadimtro_invalid_at_yahoo.com>
Date: 21 Dec 2006 13:34:48 -0800
Message-ID: <1166736888.034364.19040@79g2000cws.googlegroups.com>

Some earlier exchange suggested a method of quering hierarchies via set containment query. This is a further development of this topic.

For our purposes we'd focus on the following tree example:

1---2---4
|
|

which is formally defined by adjacency relation S:

head tail
---- ----
1 2
1 3
2 4

There are several reasons why adjacency relation is not the best abstraction to work with.
Transitively and reflectively closed relation T

head tail
---- ----
1 1
1 2
1 3
1 4
2 2
2 4
3 3
4 4

is much more "query friendly". (In my book I explored Dong et.al. method of incrementally
maintaining transitive closure -- it turned out to have nice mathematics culminating in the
formula: deltaT = T deltaS T).

A typical query "find all the ancestors of node 2" is expressed as

pi(head) sigma(tail=2) T

Now, lets turn to the set contaiment query perspective. Our example tree can be represented

via nested sets as

node1={1,2,4}---node2={2,4}---node4={4}
|
|

node3={1,3}

Nested sets can be represented as a relation:

set elem
---- ----
1 1
1 2
1 3
1 4
2 2
2 4
3 3
4 4

No doubt you have noticed already that this relation is identical to transitive closure
relation T!

In a nested sets model we do hierarchical query via relational division. "find all the
ancestors of node 2" is done in 2 steps:

Find all the elements of the set at node 2. This would be pi(elem) sigma(set=2) which evaluates into

elem

2
4

Here is is naturally to ask: "Aren't you selecting and projecting on the wrong columns? It
appears as if you look for all the DESCENDANTS of the node 2!". Hang on to step 2.

2. Divide the relation T(set,elem) by this relation, that is find all the sets that contain

set {2,4}.

Summary.
We have the same relation T, the same query "find all the ancestors of node 2", and two
alternative ways to express it; one is much simpler than the other. In practical terms, this
means that set containment approach is not very promising:-( Received on Thu Dec 21 2006 - 15:34:48 CST