Transitive Closure and Relational Division
Date: 21 Dec 2006 13:34:48 -0800
Message-ID: <1166736888.034364.19040_at_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
|
|
- 3
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!
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 - 22:34:48 CET