bapat@rm1.UUCP (Subodh Bapat) (03/15/91)
I'm wondering if there's anyone out there who might have some tricks in
their bag of SQL queries that allows the traversal of a tree-structured
hierarchy. (This is probably a FAQ but I haven't seen any FAQ list for
this group).
I have a data structure that looks like:
A
/ \
/ \
B C
/ \ \
/ \ \
D E F
which is flattened into the tabular relation TREE as:
TREE
Childnode Parentnode
------------------------------
A NULL
B A
D B
E B
C A
F C
< plenty of other records in this table for
other unrelated trees >
Is it possible to specify a single SQL query which says "Start with A, and
obtain records for all nodes which are descendants of A" ?
My research so far indicates that Oracle is the only RDBMS which supports
the CONNECT BY clause, which allows this to happen fairly easily. However,
the CONNECT BY clause is not supported by most other RDBMS vendors, nor is
it part of ANSI X3H2 SQL. I'm looking for a way to do this using standard
ANSI SQL. I tried a few queries using table aliasing but none of them worked
right.
Oracle also returns the pseudo-column LEVEL for records returned from
CONNECT-BY queries, indicating the depth of the traversed node in the
subtree. It would be nice if one could return a similar indication using a
standard ANSI SQL query.
Looking forward to tips from anyone who might have done this before,
--
Subodh Bapat bapat@rm1.uu.net OR ...uunet!rm1!bapat
Racal-Milgo, Ft Lauderdaledavidm@uunet.UU.NET (David S. Masterson) (03/18/91)
>>>>> On 14 Mar 91 22:15:46 GMT, bapat@rm1.UUCP (Subodh Bapat) said:
Subodh> Is it possible to specify a single SQL query which says "Start with A,
Subodh> and obtain records for all nodes which are descendants of A" ?
Tree-type structures can be generalized into network-type structures with no
loss of meaning. When thought of that way, this type of query becomes the
well-known "parts explosion" problem. The current definition of SQL has no
general solution for this problem (there is a problem specific solution). Dr.
Codd has suggested an extension to the model that he calls a "recursive" join
which would provide a general solution to the problem (given a two column
table like you had, it would return a two column table showing a node and a
possible decendent of that node).
The problem specific solution is to perform an outer join on the table with
itself N times (where N is the maximum number of generations between a node
and its decendent -- in your case, the height of the tree). Obviously, the
output of this, though, is a tuple having N+1 attributes which would still
have to be parsed by the application. Also, outer join is not an operator in
the ANSI SQL standard, so writing an SQL statement for this method tends to be
system specific. By the way, an outer join is the same as the usual (inner)
join with the addition that records are joined with NULL records if no other
solution for the join can be found.
--
====================================================================
David Masterson Consilium, Inc.
(415) 691-6311 640 Clyde Ct.
uunet!cimshop!davidm Mtn. View, CA 94043
====================================================================
"If someone thinks they know what I said, then I didn't say it!"