From: | Tim Uckun <timuckun(at)gmail(dot)com> |
---|---|
To: | Steve Midgley <science(at)misuse(dot)org> |
Cc: | Dmitry Ruban <dmitry(at)ruban(dot)biz>, pgsql-sql(at)lists(dot)postgresql(dot)org |
Subject: | Re: Ordered Hierarchies. |
Date: | 2019-07-19 12:38:13 |
Message-ID: | CAGuHJrOMRhLLY8fXgZBhp1vaUiEL2NTg1R2LbYA+pkWAeNjKtQ@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-sql |
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(at)misuse(dot)org> wrote:
>
>
> On Fri, Jul 19, 2019 at 3:19 AM Tim Uckun <timuckun(at)gmail(dot)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(at)ruban(dot)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(at)gmail(dot)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
>
From | Date | Subject | |
---|---|---|---|
Next Message | Alexandru Lazarev | 2019-07-19 18:15:03 | pg_advisory_lock lock FAILURE / What does those numbers mean (process 240828 waits for ExclusiveLock on advisory lock [1167570,16820923,3422556162,1];)? |
Previous Message | Voillequin, Jean-Marc | 2019-07-19 08:47:05 | RE: Ordered Hierarchies. |