pg.ddx.io  pgsql-sql@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Josh Berkus <josh@agliodbs.com>
To: sqllist <pgsql-sql@postgresql.org>
Subject: Re: How to represent a tree-structure in a relational database
Date: Wed, 13 Dec 2000 15:05:43 -0800
Message-ID: <3A3800C7.8C14A594@agliodbs.com> (raw)
References: <3A379A5F.97FFAF01@joerdens.de>
	<NEBBJLPJHKIDLJDGCMKAKEIDCBAA.stu@slammedia.com>
	<20001213232514.A31376@rakete.joerdens.de>

Frank, etc:

> > create table Category (
> > CategoryID       int4  not null  primary key,
> > ParentCategoryID int4  not null  REFERENCES Category (CategoryID),
> > CategoryName     varchar(100)
> > );

That was it.  I also gave an example of a UNION query that would display
the whole category tree in ASCII format:

I've done this before for one project.  Here's what you do:

CREATE TABLE sample_heirarchy (
        unique_id       SERIAL CONSTRAINT PRIMARY KEY,
        node_linkup     INT4,
        node_level      INT2,
        label           VARCHAR(30)
        data            whatever
        );

Then you use the unique_id and node_linkup fields to create a heirarchy
of data nodes, with an indefinite number of levels, where the
node_linkup of each lower level equals the id of its parent record.  For
example:

id      linkup  level           label           data
3       0       1               Node1           Node1
4       3       2               Node1.1         Node1.1
6       3       2               Node1.2         Node1.2
7       6       3               Node1.2.1       Node1.2.1
5       0       1               Node2           Node2

etc.

You can then access the whole heirarchy through moderately complex, but
very fast-executing UNION queries.  The one drawback is that you need to
know in advance the maximum number of levels (3 in this example), but
I'm sure someone on this list can find a way around that:

SELECT n1.unique_id, n1.label, n1.data, n1.node_level, n1.unique_id AS
level1,
        0 AS level2, 0 AS level3
FROM sample_heirarchy n1
WHERE n1.node_level = 1
UNION ALL
SELECT n2.unique_id, n2.label, n2.data, n2.node_level, n1.unique_id, 
        n2.unique_id, 0
FROM sample_heirarchy n2, sample_heirarchy n1
WHERE n1.unique_id = n2.node_linkup
        AND n2.node_level = 2
UNION ALL
SELECT n3.unique_id, n3.label, n3.data, n3.node_level, n1.unique_id, 
        n2.unique_id, n3.unique_id
FROM sample_heirarchy n1, sample_heirarchy n2, sample_heirarchy n3
WHERE n1.unique_id = n2.node_linkup AND
        n2.unique_id = n3.node_linkup
        AND n3.node_level = 3
ORDER BY level1, level2, level3

Should produce this output (pardon any parsing errors; I'm not at a
PGSQL terminal right now):

unique_id       label           data    level   level1  level2  level3
3               Node1           Node1     1     3       0       0
4               Node1.1         Node1.1   2     3       4       0
6               Node1.2         Node1.2   2     3       6       0
7               Node1.2.1       Node1.2.1 3     3       6       7
5               Node2           Node2     1     7       0       0
etc.

This sorts them in numerical (id) order, but one could just as easily
substitute the labels or data for the various levels and sort them
alphabetically (although you do need to allow for NULL sort order on
your database, and any label duplicates).

The advantages of this structure are:
1. It allows you to create, assign, and re-assign nodes freely all over
the heirarchy ... just change the level and/or linkup.
2. Aside from the Union query above, the table structure allows for any
number of levels, unlike a set or relationally linked tables.
3. Because the display query is entirely once table linking to itself on
(hopefully) indexed fields, in my expreience it runs very, very fast.
4. My PHP developer has reprogrammed the easily available PHP Tree
Control to uses this table structure (I don't know if he's giving it
out, but he said it wasn't very difficult).

-Josh Berkus

-- 
______AGLIO DATABASE SOLUTIONS___________________________
                                        Josh Berkus
   Complete information technology      josh@agliodbs.com
    and data management solutions       (415) 436-9166
   for law firms, small businesses       fax  436-0137
    and non-profit organizations.       pager 338-4078
                        		San Francisco



view thread (27+ messages)  latest in thread

Message-ID: <3A3800C7.8C14A594@agliodbs.com>
Permalink:  ../3A3800C7.8C14A594@agliodbs.com/
Also on:    postgresql.org/message-id/3A3800C7.8C14A594@agliodbs.com

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-sql@postgresql.org
  Cc: josh@agliodbs.com
  Subject: Re: How to represent a tree-structure in a relational database
  In-Reply-To: <3A3800C7.8C14A594@agliodbs.com>
  References: <3A379A5F.97FFAF01@joerdens.de> <NEBBJLPJHKIDLJDGCMKAKEIDCBAA.stu@slammedia.com> <20001213232514.A31376@rakete.joerdens.de> <3A3800C7.8C14A594@agliodbs.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox