RE: Ordered Hierarchies. - Mailing list pgsql-sql
| From | Voillequin, Jean-Marc |
|---|---|
| Subject | RE: Ordered Hierarchies. |
| Date | |
| Msg-id | 1EC8157EB499BF459A516ADCF135ADCE3AC4AB9F@LON-WGMSX712.ad.moodys.net Whole thread Raw |
| In response to | Re: Ordered Hierarchies. (Steve Midgley <science@misuse.org>) |
| List | pgsql-sql |
Hello,
Do you really need a rank column? A famous DB as sys_connect_by_path function that can be implemented as follow:
create table links(parent_id integer, id integer);
insert into links values (null,1);
insert into links values (1,11);
insert into links values (1,12);
insert into links values (11,111);
insert into links values (11,112);
insert into links values (null,2);
insert into links values (2,21);
insert into links values (2,22);
insert into links values (null,10);
insert into links values (10,101);
insert into links values (10,102);
with recursive w as (
select a.*,1 as level,to_char(a.id) as sys_connect_by_path,to_char(a.id,'0000') as sys_connect_by_path_for_order
from links a
where a.parent_id is null
union all
select a.*,(level+1) as level,concat(w.sys_connect_by_path,'.',a.id) as sys_connect_by_path,concat(w.sys_connect_by_path_for_order,'.',to_char(a.id,'00000')) as sys_connect_by_path_for_order
from links a
join w
on w.id = a.parent_id
)
select w.sys_connect_by_path,w.parent_id,w.id,w.level,w.sys_connect_by_path_for_order
from w
order by w.sys_connect_by_path_for_order;
Hope it helps.
Regards
From: Steve Midgley [mailto:science@misuse.org]
Sent: Friday, July 19, 2019 10:16 AM
To: Tim Uckun <timuckun@gmail.com>
Cc: Dmitry Ruban <dmitry@ruban.biz>; pgsql-sql@lists.postgresql.org
Subject: Re: Ordered Hierarchies.
CAUTION: This email originated from outside of Moody's. Do not click links or open attachments unless you recognize the sender and know the content is safe.
On Fri, Jul 19, 2019 at 3:19 AM Tim Uckun <timuckun@gmail.com> wrote:
Hi Everybody. I have looked at the solutions proposed. Specifically I looked at recursive CTEs, nested sets, materialized paths, using arrays to represent parentage, and ltree. They all presume an unordered set of children and in my case the order of the children is the most important thing. So far it's looking like I need to probably write some complicated stored procs to do what I want and I will definitely need a "rank" or some other column so can say something like "update table T set rank=rank+1 where parent_id=x" and then "insert into table T values (parent_id, rank, item_desc)" or something like that. In order words if I want to insert this item at 1.2..3 I need to increment all 1.2.X by one and then insert this. I know, race conditions galore!!
On Fri, Jul 19, 2019 at 8:58 AM Dmitry Ruban <dmitry@ruban.biz> wrote:
Hi,
There's an approach to store such hierarchy in relational db, have a look
I think it covers your usecases
Cheers
Sent from phone
On Thu, 18 Jul 2019, 14:46 Tim Uckun, <timuckun@gmail.com> wrote:
Hi all.
I have read articles about handling hierarchies in databases but none of them deal with how to keep order in the hierarchy. For example take a typical outline.
1
1.1
1.1.1
1.1.2
1.2
2
etc.
In this scenario the following actions are common.
1. move the item up. 1.1.2 becomes 1.1.1 and 1.1.1 becomes 1.1.2
2 Move the item down. The opposite of above.
3. Move the item left. 1.1.2 becomes 1.2 and 1.2 becomes 1.3 and on down the 1.X list.
4. Move the item right. 1.2. becomes 1.1.3
5. Arbitrarily move an item into a hierarchy. In this case the item becomes the highest numbered child under the target parent and all it's previous peers get renumbered.
6. Arbitrary insert item into a hierarcy. It becomes the highest numbered child in the target parent.
7. Delete an item. This would renumber all peers in the parent greater it's own rank.
In addition there are all the normal access patterns of course.
Has anybody ever done anything like this or read an article about doing something like this in an efficient way?
I should also add that there are lots of more complicated actions one could take based on attributes of the nodes such as inheriting from the parent nodes some attributes or checking constraints based on parentage etc.
I'm not an expert but I've implemented CTEs for ordered hierarchies in the past (I work in education, so curricula and table of contents problems come up a lot). I think you want to link your hierarchy with opaque keys like guids or table IDs. In my implementations, we generate the labels on middleware (Ruby/ActiveRecord) side, but you could just as easily call your CTE in a stored proc, and generate the appropriate numbering at that time. So your fundamental data table could be something like:
ID | ParentID | Hierarchy_Level
Hierarchy_Level would be the "ident" level you want (1 is top level "1." 2 is second level "1.4", etc)
Then you'd have some middle tier - a stored proc in Postgres if that's appropriate - that calls this table using CTE to roll-up the current hiearchy. As it rolls up it uses basic logic to generating the numbering ("n+1" type approach, resetting n every time the Hierarchy_Level value changes). Using this approach you could number using different schemes easily - roman numeral options, 1.A.i scheme, etc..
Finally, using this approach, when you want to insert a new item between two items, you just lock the table, relink the two items apart and put this one in between. I think the big difference between what I'm proposing and what you mentioned in your last post is that you're trying to number stuff when it goes into the table, and I'm suggesting to number the stuff when it goes out of the table..
I don't know how to write that n+1 final numbering in Postgres/stored proc, but it was trivial in Ruby+ORM. I'm sure others here could weigh in on that. I hope I'm answering the right question in a useful way!
Steve
This email was sent to you by Moody’s Investors Service EMEA Limited
Registered office address:
One Canada Square
Canary Wharf
London, E14 5FA
Registered in England and Wales No: 8922701