Date: Tue, 3 Sep 2002 15:22:07 +0200
From: Hubert depesz Lubaczewski <depesz@depesz.pl>
To: pgsql-sql@postgresql.org
Subject: tree structures in sql - my point of view (with request of comment
	from joe celko)
Message-ID: <20020903132207.GC24879@depesz.pl>
Reply-To: depesz@depesz.pl
Mime-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature"; boundary="bKyqfOwhbdpXa4YI"
Content-Disposition: inline
User-Agent: Mutt/1.4i

--bKyqfOwhbdpXa4YI
Content-Type: text/plain; charset=iso-8859-2
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

hi
i recently spent some time on tree-structures in sql.
i started with simple id/parent_id approach, used by nearly everyone,
then i stopped at joe celko's nested sets, but i found it not very
usable.
then i found my own (maybe someone wrote it before, but i haven't read
it, so idea is mine) way.
in my way we have two tables:
create table data (id serial, name text);
create table structure (parent_id int8, child_id int8, depth int8);

structure table represents all paths in tree.
for example for this tree:

	      sql
	     /	 \
    postgresql	  oracle-----__
	|	 /    |        \
     linux     sco    linux   windows
		     /	   \
		  glibc1   glibc2

(sorry for used data - it is just template, and personally i don't like
oracle).
so, for this tree we would populate the tables this way:
data:
 id | name
----+------------
  1 | sql
  2 | postgresql
  3 | oracle
  4 | linux
  5 | sco
  6 | linux
  7 | windows
  8 | glibc1
  9 | glibc2

structure:
 parent_id | child_id | depth
-----------+----------+-------
         1 |        1 |     0
         2 |        2 |     0
         3 |        3 |     0
         4 |        4 |     0
         5 |        5 |     0
         6 |        6 |     0
         7 |        7 |     0
         8 |        8 |     0
         9 |        9 |     0
         1 |        2 |     1
         1 |        3 |     1
         1 |        4 |     2
         2 |        4 |     1
         1 |        5 |     1
         1 |        6 |     1
         1 |        7 |     1
         3 |        5 |     2
         3 |        6 |     2
         3 |        7 |     2
         1 |        8 |     3
         1 |        9 |     3
         3 |        8 |     2
         3 |        9 |     2
         6 |        8 |     1
         6 |        9 |     1

(records with depth 0 are technologically not necessary, but they
simplify and speedup some queries).

with this data layout (easily indexable) you can fetch any data with
just one select statement (no recursion needed in any case):
- fetching parent
- fetching childs
- fetching "from id up"
- fetching "from id down"
also when you need to get indirect parents/childs or when you need only
some of the data (from me, up, but not more then to my
grand-grand-grand-father).

i'd like to get some comments on this - how do you see my idea, is it
worth it, do you know any better way to store trees in sql?

best regards

depesz

--=20
hubert depesz lubaczewski                          http://www.depesz.pl/
------------------------------------------------------------------------
M=F3j Bo=BFe, spraw abym milcza=B3, dop=F3ki si=EA nie upewni=EA,  =BFe  na=
prawd=EA  mam
co=B6 do powiedzenia.                                      (c) 1998 depesz


--bKyqfOwhbdpXa4YI
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.7 (GNU/Linux)

iD8DBQE9dLd/KBwKA0prOAkRAs60AKDho0hvw4qOsZGWUSIQ2pl2WpdfnwCdE3aa
6RTM4mzeLbUycdKtfzpsg5c=
=nAu5
-----END PGP SIGNATURE-----

--bKyqfOwhbdpXa4YI--