Oracle FAQ Your Portal to the Oracle Knowledge Grid
 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US

Home -> Community -> Usenet -> comp.databases.theory -> Transitive Closure and Relational Division

# Transitive Closure and Relational Division

Date: 21 Dec 2006 13:34:48 -0800

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

• 3

which is formally defined by adjacency relation S:

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

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

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:

1. 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

Original text of this message

 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US