Thread: Ordered Hierarchies.

Ordered Hierarchies.

From

Tim Uckun

Date:

18 July 2019, 05:46:12

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

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

Fwd: Ordered Hierarchies.

From

Todd Reed

Date:

18 July 2019, 16:45:17

Essentially you will be doing a parent-child recursive lookup. At a basic level, you table would look have three columns: [ID], [Name],[ParentID]. From there, you will need to perform a recursive lookup. This isn't a PostgreSQL Example, but should give you the theory and idea: https://www.codeproject.com/Articles/818694/SQL-Queries-to-Manage-Hierarchical-or-Parent-child. I assume that if the ParentID is 0 or null, then it is at the root level. If it's not going to be sorted by the name (alpha), you may need to add a 'Sort' column, too.

I've done something similar a menu system, but have always limited the number of recursions. The only thing you have to watch out for is orphans.

On Wed, Jul 17, 2019 at 9:46 PM 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.

Re: Ordered Hierarchies.

From

Tony Shelver

Date:

18 July 2019, 19:25:59

Have a look at recursive CTEs before you go the proposed route. There are plenty of good examples out there. The old SQL Server documentation had some excellent examples with will also apply to PG.

One of the potential issues with recursive queries / CTEs is performance. In one SQL Server-based system we were heavily dependent on recursive views that performed more than adequately. You will need to be careful with design, and also limit the hierarchy depth for optional performance.

This approach is often used in manufacturing bill-of-material structures, for example.

Also, not sure about Postgres, but in SQL Server there used to be a limit to the depth of the recursion, I think 22 levels or something like that.

On Thu, 18 Jul 2019 at 04: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.

Re: Ordered Hierarchies.

From

Dmitry Ruban

Date:

18 July 2019, 23:58:45

Hi,

There's an approach to store such hierarchy in relational db, have a look

https://en.m.wikipedia.org/wiki/Nested_set_model

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.

Re: Ordered Hierarchies.

From

Tim Uckun

Date:

19 July 2019, 05:19:03

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

https://en.m.wikipedia.org/wiki/Nested_set_model

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.

Re: Ordered Hierarchies.

From

Steve Midgley

Date:

19 July 2019, 11:15:55

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

https://en.m.wikipedia.org/wiki/Nested_set_model

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

RE: Ordered Hierarchies.

From

"Voillequin, Jean-Marc"

Date:

19 July 2019, 11:47:05

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

https://en.m.wikipedia.org/wiki/Nested_set_model

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.

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)

Steve

-----------------------------------------

Moody's monitors email communications through its networks for regulatory compliance purposes and to protect its customers, employees and business and where allowed to do so by applicable law. The information contained in this e-mail message, and any attachment thereto, is confidential and may not be disclosed without our express permission. If you are not the intended recipient or an employee or agent responsible for delivering this message to the intended recipient, you are hereby notified that you have received this message in error and that any review, dissemination, distribution or copying of this message, or any attachment thereto, in whole or in part, is strictly prohibited. If you have received this message in error, please immediately notify us by telephone, fax or e-mail and delete the message and all of its attachments. Every effort is made to keep our network free from viruses. You should, however, review this e-mail message, as well as any attachment thereto, for viruses. We take no responsibility and have no liability for any computer virus which may be transferred via this e-mail message.

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

-----------------------------------------

Re: Ordered Hierarchies.

From

Tim Uckun

Date:

19 July 2019, 15:38:13

I am not sure if I am missing something but I don't get how you would you reorder something without a rank column.

Say I have 1.1.2 and 1.1.3 . I want to move 1.1.3 "up" one so it becomes 1.1.2 and 1.1.2 becomes 1.1.3 I guess 1.1.1 could not be moved up similarly 1.1.X where X is the highest numbered child could not be moved down.

In this case the 1.1.2 for example the ID of the record is 2, the parent ID is 1. I want to change the ID of the record to 3 so I can change the ID of the record that 3 to 2 in order to move it up in the ranking.

So again I see this as a three step procedure.

1. Delete 1.1.3 returning * so you have it in a record (can do this in a CTE)

2. increment the ID of all children of 1 where the ID is greater than or equal to 3-1

3. Insert the deleted record again with the new ID.

I suppose if you didn't want to delete the record you could set the id to null or something too.

Lots of index churn though.

On Fri, Jul 19, 2019 at 8:16 PM Steve Midgley <science@misuse.org> wrote:

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

https://en.m.wikipedia.org/wiki/Nested_set_model

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