Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!cimshop!davidm From: cimshop!davidm@uunet.UU.NET (David S. Masterson) Newsgroups: comp.databases Subject: Re: Traversing Tree Structures Using SQL Message-ID: Date: 17 Mar 91 20:52:44 GMT References: <1024@rm1.UUCP> Sender: davidm@cimshop.UUCP Distribution: comp Organization: Consilium Inc., Mountain View, California Lines: 30 In-reply-to: bapat@rm1.UUCP's message of 14 Mar 91 22:15:46 GMT >>>>> 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!"