From: Achilleas Mantzios <achill@matrix.gatewaynet.com>
To: pgsql-sql@postgresql.org
Subject: Re: Table Design for Hierarchical Data
Date: Wed, 7 Apr 2010 10:28:56 +0200
Message-ID: <201004071128.56216.achill@matrix.gatewaynet.com> (raw)
In-Reply-To: <4BBC39DC.6050502@bankir.ru>
References: <n2i5ab13581004061033j4ed25734xd0504cb95a1fc092@mail.gmail.com>
<201004071000.15529.achill@matrix.gatewaynet.com>
<4BBC39DC.6050502@bankir.ru>
Στις Wednesday 07 April 2010 10:53:00 ο/η silly sad έγραψε:
> On 04/07/10 11:00, Achilleas Mantzios wrote:
>
> > Column | Type | Modifiers
> > ---------+-----------+---------------------------------------------------------------------------
> > id | integer | not null default nextval(('public.paintgentypes_id_seq'::text)::regclass)
> > name | text | not null
> > parents | integer[] |
>
> > The parents of any node to the root, i.e. the path of any node to the root are depicted as
> > parents[0] : immediate parent
> > parents[1] : immediate parent of the above parent
> > .....
> > parents[n] : root of the tree
>
> what this schema gives?
>
> (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.
>
No, you are wrong.
1) find immediate father
parents[0] (O(1) complexity)
2) find root
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] =2; (caution: NON indexed select)
or
SELECT * from paintgentypes where itoar(2) ~ parents and level(parents)=(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)<=(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
>
> id | integer | NOT NULL
> name | text | not null
> parent | integer |
> l | numeric
> r | numeric
>
> (1) parent branch in one select
> (2) child subtree in one select
> (it makes a sence!)
>
>
>
--
Achilleas Mantzios
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 using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: achill@matrix.gatewaynet.com
Subject: Re: Table Design for Hierarchical Data
In-Reply-To: <201004071128.56216.achill@matrix.gatewaynet.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