Similar Threads
1. Relational schema diagrams
2. Simplifying Relational Division
3. Why relational division is so uncommon?
4. 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


 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!
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:(
5. set builder notation for relational division
6. choice of character for relational division
Let us consider the choice of characters to use for
relational operators. It might be desirable to use
different characters for the relational operators from
the scalar ones, so we avoid using * for join, even
though it is in some sense a product operator.
Set subtraction already has a standard character
in common usage: \
But we also need a character for relational division.
The / character is often used, but that's the same
as numerical division. Bummer.
So, if you had to choose an ascii character for
relational division, which one would you use
and why?
Marshall
7. Aggregation (with GBY) is Relational Division
8. Relational Algebra :Division.
I am searching for a simple example of the
Division as in relational algebra.
(Operations : Union, intersection, difference, cartesian product,
selection, projections, join and DIVISION).
The divisor should have more than one attribute and more than
one tuple. The quotient should also be multiple tuples.
And how to present (express) this division in SQL.
Thanks for your attention.
ben brugman