pg.ddx.io  pgsql-sql@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Stuart Statman <stu@slammedia.com>
To: 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:42:18 -0800
Message-ID: <NEBBJLPJHKIDLJDGCMKAIEIJCBAA.stu@slammedia.com> (raw)
In-Reply-To: <3A3800C7.8C14A594@agliodbs.com>

[Josh Berkus]

> 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

I don't think I'd be comfortable with having the node_level column in the
table structure. First, because you can derive that value using a function,
it's duplicate data. Second, if you decide to take an entire segment of your
hierarchy and move it under another node (by changing the value of
node_linkup/ParentCategoryID), you'll need to recalculate all of those
node_level values. And all the node_level values underneath it.

> 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:

I can think of another way to do this, though it would be a little complex
and would involve temp tables. Select all of your top level nodes into a
temp table. Create a new table with a new column for the new level. Select
the children of the top level nodes into the temp table, followed by those
top level nodes themselves, with a 0 in the new column and a flag indicating
not to expand again. Create a new temp table just like the last but with
another column for the new level, and repeat the above process from the
first temp table to the second, only expanding the latest children, but
copying all records over. Keep doing it until there are no more new
children.

Alternately, if you didn't need each level to have it's own column, but
didn't mind an x.x.x.x kind of notation, you could use one temp table, and
just append '.0' to the end of every copied-over parent node.

Basically, both methods are simulations of recursing the tree, but you get
to do each level all at once using an insert ... select. If you wanted, you
could even use a counter, to identify which level each node appeared in.

Clearly, this could also be done with cursors and recursive

> 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).

We've done a similar thing for Java. It was ridiculously easy to create a
TreeModel wrapped around this data. Almost too easy; it made me feel dirty.

Stuart Statman
Director of Software Development
Slam Media, Inc.

Attachments:

Stuart Statman.vcf (text/x-vcard, 481B) download BEGIN:VCARD VERSION:2.1 N:Statman;Stuart FN:Stuart Statman ORG:Slam Media, Inc. TITLE:Director of Software Development TEL;WORK;VOICE:(206) 391-0187 ADR;WORK;ENCODING=QUOTED-PRINTABLE:;;Slam Media, Inc.=0D=0A800 5th Ave. #101-296;Seattle;WA;98104;United States= of America LABEL;WORK;ENCODING=QUOTED-PRINTABLE:Slam Media, Inc.=0D=0A800 5th Ave. #101-296=0D=0ASeattle, WA 98104=0D=0AUnit= ed States of America EMAIL;PREF;INTERNET:stuart@slammedia.com REV:20000910T063546Z END:VCARD

view thread (27+ messages)  latest in thread

Message-ID: <NEBBJLPJHKIDLJDGCMKAIEIJCBAA.stu@slammedia.com>
Permalink:  ../NEBBJLPJHKIDLJDGCMKAIEIJCBAA.stu@slammedia.com/
Also on:    postgresql.org/message-id/NEBBJLPJHKIDLJDGCMKAIEIJCBAA.stu@slammedia.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: stu@slammedia.com, josh@agliodbs.com
  Subject: Re: How to represent a tree-structure in a relational database
  In-Reply-To: <NEBBJLPJHKIDLJDGCMKAIEIJCBAA.stu@slammedia.com>
  References: <3A3800C7.8C14A594@agliodbs.com> <NEBBJLPJHKIDLJDGCMKAIEIJCBAA.stu@slammedia.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