Message-ID: <3CEE8966.857521CF@uic.edu>
Date: Fri, 24 May 2002 13:41:42 -0500
From: Douglas Trainor <trainor@uic.edu>
MIME-Version: 1.0
To: Gregory Brauer <greg@wildbrain.com>
Cc: pgsql-sql@postgresql.org
Subject: Re: Trees in SQL
References: <3CEE818B.9020702@wildbrain.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

If you're a book buyer, the one called "Joe Celko's SQL for Smarties: Advanced SQL Programming"
has a collection of tree/graph tricks.  About 50 pages are devoted to these three sections:

    Adjacency List Model of Trees
    Nested Set Model of Trees in SQL
    Graphs in SQL

Book distributors were trying to sell a preview edition of a book by
David Rozenshtein, et al called "Tree & Graph Processing in SQL" -- but something
fell through and the book apparently didn't come out.

Of course, it's more fun to not read a book and to try and implement a few toy tree/graph
things yourself.

    douglas

Gregory Brauer wrote:

> I hope this isn't an overly broad topic that ends up diverging into graph
> theory, but I have a tree structure of identical items (analogous to a
> filesystem directory tree) that I need to store in Postgres.  The
> "obvious" design is to give the table that will represent these objects
> a field identifying its "parent" that is a relation to the same table.
> However, this seems to make many common SQL queries rather difficult.
>
> What sort of strategies are best for storing tree structures in a
> relational database, and how would one structure SQL queries to find,
> say, "all of the children anywhere under this node", or to represent
> the condition "if this node is a child at any depth under this other
> node"?  Are there good strategies for preventing cycles?
>
> I'd appreciate any insights anyone can give.
>
> Thanks.
>
> Greg Brauer
> greg@wildbrain.com
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/users-lounge/docs/faq.html