Oracle FAQ  Your Portal to the Oracle Knowledge Grid 
Home > Community > Usenet > comp.databases.theory > Transitive Closure and Relational Division
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:
124


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}


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:
elem
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