Received: from nollie.summersault.com (nollie.summersault.com [208.196.32.199]) by postgresql.org (8.11.3/8.11.4) with SMTP id f7GKXCP27455 for ; Thu, 16 Aug 2001 16:33:12 -0400 (EDT) (envelope-from mark@summersault.com) Received: (qmail 66790 invoked from network); 16 Aug 2001 20:36:09 -0000 Received: from hoobella.summersault.com (HELO summersault.com) (208.196.32.195) by nollie.summersault.com with SMTP; 16 Aug 2001 20:36:09 -0000 Message-ID: <3B7C2E52.4F645776@summersault.com> Date: Thu, 16 Aug 2001 15:34:41 -0500 From: Mark Stosberg Reply-To: mark@summersault.com Organization: Summersault X-Mailer: Mozilla 4.78C-CCK-MCD {C-UDP; EBM-APPLE} (Macintosh; U; PPC) X-Accept-Language: en,pdf MIME-Version: 1.0 To: pgsql-sql@postgresql.org Subject: Re: Re: Help!!! Trying to "SELECT" and get a tree structure back. References: <9h8146$2qg9$1@news.tht.net> <7e67a7b3.0106291105.26574b5f@posting.google.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Archive-Number: 200108/218 X-Sequence-Number: 4450 --CELKO-- wrote: > > >> The table causing my headache: > > CREATE TABLE app_components > (id NUMERIC(7) NOT NULL PRIMARY KEY, > name VARCHAR(100) NOT NULL, > description VARCHAR(500) NULL, > parent_id NUMERIC(7) NULL > REFERENCES app_components(id) > ON DELETE CASCADE, > CONSTRAINT appcomp_name_u UNIQUE (name, parent_id)); << I first tried the above approach to model trees in SQL, which also caused me headaches. The recursion needed to find all the ancestors for a given id was slow. So I bought and looked through Joe Celko's book (who recently posted on this topic). I implemented his ideas, and found that they were better than the method above (and faster, as he says), but I still wasn't satisfied. First, I didn't like that the notion wasn't easily parsable for me. Updating and deleting categories felt like hacks, and moving a category seemed like too much work. So I kept looking for new ideas to model trees in SQL. On my third try, I found a solution I was happy with, which I'll call the "sort key" method. I first read about it here: http://philip.greenspun.com/wtr/dead-trees/53013.htm (Search for "Sort keys deserve some discussion") on this page The sort key is a single string that gives you the location of a node in a tree. Used in conjunction with a parent_id, I found that most of the questions I was asking were easy to answer: Who is my parent? Who are all my ancestors? Who are my immediate children? How many descendants do I have? Who are siblings? Furthermore, it's fairly straightforward to manipulate items using this structure, and queries are fast-- most questions can answered with one SQL statement. Finally, the sort_keys are fairly human parsable, which is nice. The trade-off for all these features is that you have a fixed number of immediate children for any parent (based on how many characters are used for each piece of the sort key). I think in my application to categorize data, each parent can only have 62 immediate children. I can live with that. Cascade is a complete (free) Perl/Postgres application using this scheme if you are interested in seeing these ideas in action. It's homepage is here: http://summersault.com/software/cascade/ You'll be able to get a demo and source code from there. Thanks, -mark http://mark.stosberg.com/