From: Achilleas Mantzios <achill@matrix.gatewaynet.com>
Organization: Dynacom Tankers Mgmt
To: pgsql-sql@postgresql.org
Subject: Re: Table Design for Hierarchical Data
Date: Wed, 7 Apr 2010 10:28:56 +0200
User-Agent: KMail/1.9.7
References: <n2i5ab13581004061033j4ed25734xd0504cb95a1fc092@mail.gmail.com>
	<201004071000.15529.achill@matrix.gatewaynet.com>
	<4BBC39DC.6050502@bankir.ru>
In-Reply-To: <4BBC39DC.6050502@bankir.ru>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
Message-Id: <201004071128.56216.achill@matrix.gatewaynet.com>

=CE=A3=CF=84=CE=B9=CF=82 Wednesday 07 April 2010 10:53:00 =CE=BF/=CE=B7 sil=
ly sad =CE=AD=CE=B3=CF=81=CE=B1=CF=88=CE=B5:
> On 04/07/10 11:00, Achilleas Mantzios wrote:
>=20
> >   Column  |   Type    |                                 Modifiers
> > ---------+-----------+-------------------------------------------------=
=2D-------------------------
> >   id      | integer   | not null default nextval(('public.paintgentypes=
_id_seq'::text)::regclass)
> >   name    | text      | not null
> >   parents | integer[] |
>=20
> > The parents of any node to the root, i.e. the path of any node to the r=
oot are depicted as
> > parents[0] : immediate parent
> > parents[1] : immediate parent of the above parent
> > .....
> > parents[n] : root of the tree
>=20
> what this schema gives?
>=20
> (1) the parent branch in one select.

1st the number of selects has nothing to do with speed
2nd as you will see below, the number of select is always 1, for any basic =
tree operation.

> what else?
> nothing.
>=20
No, you are wrong.

1) find immediate father
parents[0] (O(1) complexity)
2) find root=20
parents[level(parents)] (O(1) complexity)
3) insert a node under a father
O(1) complexity
4) find all immediate children of a father node: (e.g. 2)
SELECT * from paintgentypes where parents[1] =3D2; (caution: NON indexed se=
lect)
or
SELECT * from paintgentypes where itoar(2) ~ parents and level(parents)=3D(=
level of node 2 )+1;
5) find all children and grandchildren of a father node: (e.g. 2)
SELECT * from paintgentypes where itoar(2) ~ parents and level(parents)<=3D=
(level of node 2 )+2;
6) find whole subtree of a node (e.g. 2)
SELECT * from paintgentypes where itoar(2) ~ parents;

In PostgreSQL, the above model i think is superior to nested trees in every=
 apsect.
This is due to the excellent intarray module.

PS
Excuse me for the typo in the previous mail.
Arrays in postgresql are 1-based.

> compare it to a nested-tree
>=20
>     id      | integer   | NOT NULL
>     name    | text      | not null
>     parent  | integer   |
>     l       | numeric
>     r       | numeric
>=20
> (1) parent branch in one select
> (2) child subtree in one select
> (it makes a sence!)
>=20
>=20
>=20


=2D-=20
Achilleas Mantzios