nested set tree: how to change order of one node?

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

nested set tree: how to change order of one node?

Sam Carleton
The tree in question contains categories, subcategories and finally image
galleries.  It is common for the user to want to sort all the subordinates
of one level a different way, at times alphanumeric, other times simply to
their liking.  I have been reading through Joe Celko's Trees and
Hierarchies In Sql for Smarties book to refresh the old brain.  He never
talks about how to do any sorting, which tells me it is none trivial, but I
am sure it has been done.

My thought process is to do this:

   1. create a temp table to hold all the descendants of the parent
   2. copy the  subordinates (and descendants) into the temp table one at a
   time in the new order to get the lft/rgt values correct
   3. Once all the children and descendants are copied into the temp table,
   update the lft/rgt values of the source table to get the new order

Is this a valid approach?  Is there a better one?

Main Question: What is the best way to implement the insert in #2?
Ideally, I would like to do that in one SQL statement, do one insert select
that reorders things based on a where condition.  What is throwing me off
is the issue of the descents of what is being sorted, their order should
NOT be changing.  This would seem like a great place for a stored proc or
in the case of SQLite the WITH clause.  Can the WITH clause do what I am
trying to achieve?  An outer select controls the ordering of the
subordinates being sorted and the inner select does the actual gathering of
the data to insert into the temp table?  If this is possible, what might it
look like?

P.S.  In the book Joe talks about creating a view that shows subordinates,
for starts that can be used to sort alphanumeric:

select ChildOID, ChildName, lft, rgt
from EventNodeSubordinates
where ParentOID = '98f13b01-3936-44b0-84a4-56681320fb7d' and
      ChildOID <> '98f13b01-3936-44b0-84a4-56681320fb7d'
order by ChildName

Pax vobiscum,
Sam Carleton
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: nested set tree: how to change order of one node?

ingo
Sam,

Can't answer your question directly, maybe the closure extension is
something for you. To read a bit about it:
http://charlesleifer.com/blog/querying-tree-structures-in-sqlite-using-python-and-the-transitive-closure-extension/

ingo

On 18-6-2019 14:19, Sam Carleton wrote:
> My thought process is to do this:
>
>    1. create a temp table to hold all the descendants of the parent
>    2. copy the  subordinates (and descendants) into the temp table one at a
>    time in the new order to get the lft/rgt values correct
>    3. Once all the children and descendants are copied into the temp table,
>    update the lft/rgt values of the source table to get the new order
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: nested set tree: how to change order of one node?

Lifepillar-2
In reply to this post by Sam Carleton
On 18 Jun 2019, at 14:19, Sam Carleton <[hidden email]> wrote:
>
> The tree in question contains categories, subcategories and finally image
> galleries.  It is common for the user to want to sort all the subordinates
> of one level a different way, at times alphanumeric, other times simply to
> their liking.  I have been reading through Joe Celko's Trees and
> Hierarchies In Sql for Smarties book to refresh the old brain.  He never
> talks about how to do any sorting, which tells me it is none trivial, but I
> am sure it has been done.

For the usual (lexicographic, numeric, temporal, …) orderings, SQL’s “order by”
is your friend. If you want to maintain a user-defined ordering, you must
store it explicitly in the database.

> My thought process is to do this:
>
>   1. create a temp table to hold all the descendants of the parent
>   2. copy the  subordinates (and descendants) into the temp table one at a
>   time in the new order to get the lft/rgt values correct
>   3. Once all the children and descendants are copied into the temp table,
>   update the lft/rgt values of the source table to get the new order
>
> Is this a valid approach?

It sounds like a terribly inefficient and complicated approach to me.

>  Is there a better one?

I would step back to the design phase of your database if possible.

From your (not too detailed) description, a draft logical model might be like
the one in attachment (hoping that attachments reach the mailing list). It uses
IDEF1X notation, which you may read about online if you are not familiar with it.
Anyway, the model captures the following requirements:

- Each Node is either a Category or a Gallery.
- Each Category is a Node.
- Each Gallery is a Node (a leaf, in fact).
- A Node is a child of zero or one Category.
- A Category is a parent of zero or more Nodes (*).
- A Category may follow one other Category (at the same level).
- A Category may precede one other Category (at the same level).

(*) This model allows a Category to have both Categories and Galleries as
children. This may be constrained if necessary.

The code at the end of this message, tested in SQLite, creates the
corresponding tables and shows a few transactions to populate and query the
database (in the real world, such transactions would likely be implemented as
user-defined functions, with suitable parameters). In particular, the
recursive query returns the categories at a given level according to the
persisted ordering. Another possibility would be to store the rank directly,
but that would make other operations more involved.

The closure extension suggested in another post may be used with the
proposed model, if desired, but not with your model (AFAICS).

Hope this helps!
Life.

----
create table Node (
  Name text not null,
  Type text not null,

  primary key (Name),
  constraint ValidNodeType check (Type in ('C','G')) -- Category/Gallery
);

create table Category (
  Name text not null,

  primary key (Name),
  foreign key (Name) references Node(Name)
    on update cascade on delete cascade
);

create table Gallery (
  Name text not null,

  primary key (Name),
  foreign key (Name) references Node(Name)
    on update cascade on delete cascade
);

create table NodeCategory (
  Name       text not null,
  ParentName text not null,

  primary key (Name),
  unique (Name, ParentName), -- Required for foreign keys in CustomOrdering
  -- unique (ParentName, Name), -- Might be useful for performance
  foreign key (Name) references Node(Name)
    on update cascade on delete cascade,
  foreign key (ParentName) references Category(Name)
    on update cascade on delete cascade
);

create table CustomOrdering (
  NextName   text not null,
  PrevName   text not null,
  ParentName text not null,

  constraint ValidPair check (NextName <> PrevName),

  primary key (NextName),
  unique (PrevName),
  foreign key (NextName, ParentName)
    references NodeCategory(Name, ParentName)
    on update cascade on delete cascade,
  foreign key (PrevName, ParentName)
    references NodeCategory(Name, ParentName)
    on update cascade on delete cascade,
  foreign key (ParentName) references Category(Name)
    on update cascade on delete cascade
);

-- Sample transactions

-- Insert a top category
begin transaction;
  insert into Node(Name, Type) values ('Top','C');
  insert into Category(Name) values ('Top');
commit;

-- Insert child categories
begin transaction;
  insert into Node(Name, Type) values ('C1','C');
  insert into Category(Name) values ('C1');
  insert into NodeCategory(Name, ParentName) values ('C1', 'Top');
commit;

begin transaction;
  insert into Node(Name, Type) values ('C2','C');
  insert into Category(Name) values ('C2');
  insert into NodeCategory(Name, ParentName) values ('C2', 'Top');
commit;

begin transaction;
  insert into Node(Name, Type) values ('C3','C');
  insert into Category(Name) values ('C3');
  insert into NodeCategory(Name, ParentName) values ('C3', 'Top');
commit;

begin transaction;
  insert into Node(Name, Type) values ('C1.2','C');
  insert into Category(Name) values ('C1.2');
  insert into NodeCategory(Name, ParentName) values ('C1.2', 'C1');
commit;

-- Insert a gallery

begin transaction;
  insert into Node(Name, Type) values ('G1','G');
  insert into Category(Name) values ('G1');
  insert into NodeCategory(Name, ParentName) values ('G1', 'C1.2');
commit;

-- Sort first-level categories as C2 < C1 < C3.
begin transaction;
  insert into CustomOrdering(PreName, NextName, ParentName)
  values ('C2', 'C1', 'Top');
  insert into CustomOrdering(PrevName, NextName, ParentName)
  values ('C1', 'C3', 'Top');
commit;

-- Get the categories under Top in lexicographical order
select Name
  from NodeCategory
 where ParentName = 'Top'
 order by Name;

-- Get the categories under Top in the custom order
with recursive CategoryList(Name, Rank) as (
  -- Get the first category under Top
  select CO.PrevName, 1 as Rank
    from CustomOrdering CO
   where CO.ParentName = 'Top'
     and not exists (select 1 from CustomOrdering
                      where NextName = CO.PrevName)
  union all
  -- Get the subsequent categories
  select CO.NextName, CL.Rank + 1
    from CustomOrdering CO
    join CategoryList CL
      on CL.Name = CO.PrevName
   where CO.ParentName = 'Top'
)
select Name from CategoryList order by Rank;
----


_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users