Results 1 to 2 of 2
  1. #1
    Join Date
    Oct 2001
    Location
    FRANCE
    Posts
    25

    Unanswered: Ordering sibbling nodes (yet another tree question)

    Hi,

    I need to order sibling nodes in a tree hierarchy

    I've taken exemple on the nice sample from Nigelrivett (displaying tree hierarchy sql server)

    the problem is that this sample doesn't allow to order sibbling nodes.

    I currently use a process outside SQL to do this but I would use a SQL way if possible.

    Is there any easy known solution to fix this?

    I've also looked a little bit at the nested set model (columns from Joe Celko) of trees but it seems that for my use:
    -not a huge table (under 1000 rows)
    -I need ordering sibbling nodes on various criteria
    -I need to update the hierarchy structure easily (moving a complete subtree to another place)
    it's not the best way to go.

    Could anyone tell me wich are the criteria that make either the nested set or the model adjacency model (the one I use) more applicable with my use?

    Thanks in advance for your inputs and sorry if any of my assumptions are false.

    here is the sample code
    Code:
    create table #category (id int, name varchar(100), parentid int)
    insert into #category select 1, 'root', NULL
    insert into #category select 2, 'z category', 1
    insert into #category select 3, 'a category', 1
    insert into #category select 4, 'x productsrange', 2
    insert into #category select 5, 'z productsrange', 2
    insert into #category select 6, 'y productsrange', 2
    insert into #category select 7, 'c productsrange', 3
    insert into #category select 8, 'a productsrange', 3
    insert into #category select 9, 'b productsrange', 3
    insert into #category select 10, 'b category', 1
    
    create table #tree (id int, lineage varchar(1000), sequence varchar(1000), depth int)
    
    insert #tree 
    	select 
    		id, 
    		right('/',10),
    		right('/'+convert(varchar(10),id)+'/',10), 
    		1 
    	from #category 
    	where parentid is null
    
    declare @i int
    select @i = 0
    while @@rowcount > 0
    begin
    	select @i = @i + 1
    	insert #tree 
    	select 
    		#category.id, 
    		lineage+convert(varchar(10),#tree.id)+'/',
    		sequence+right(convert(varchar(10),#category.id)+'/',10), 
    		@i+1
    	from #category, #tree
    	where #tree.depth = @i
    	and #category.parentid = #tree.id
    end
    
    select * from #category
    
    select * from #tree, #category
    where #tree.id = #category.id
    order by lineage
    
    select space((depth-1)*4) + #category.name
    from #tree, #category
    where #tree.id = #category.id
    order by sequence
    
    drop table #category
    drop table #tree
    current result:
    Code:
    root
        b category
        z category
            x productsrange
            z productsrange
            y productsrange
        a category
            c productsrange
            a productsrange
            b productsrange
    expected result (when ordered by category.name):
    Code:
    root
        a category
            a productsrange
            b productsrange
            c productsrange
        b category
        z category
            x productsrange
            y productsrange
            z productsrange

  2. #2
    Join Date
    Oct 2001
    Location
    FRANCE
    Posts
    25
    Since I've posted the same question on microsoft.public.sqlserver.programming newsgroup and got a reply from Joe Celko, so I append it here.

    In fact it seems that there is no SQL way to obtain a specific sibling order in tree structure appart from the oldest ordering. The only way will be to rebuild the tree by inserting the nodes in the right order, wich seems overkill compared doing this process outside

    here is the quote from Joe Celko:
    >> I've also looked a little bit at the nested set model (columns from
    Joe Celko) of trees but it seems that for my use:
    -not a huge table (under 1000 rows) <<

    Fine, not a problem. Just keep the nodes in one table and the tree
    structure in another, even for small trees.

    >> -I need ordering sibbling nodes on various criteria <<

    The nested set model automatically orders the sibling by the lft (or
    rgt) number; there is a clear leftmost (oldest son) and rightmost child
    (youngest son).

    >> -I need to update the hierarchy structure easily (moving a complete
    subtree to another place) <<

    I have a whole book on how to do this kind of thing coming out later
    this year. Her is a cut and paste on that topic:

    03.08.01. Moving a Subtree within a Tree

    Yes, it is possible to move subtrees inside the nested sets model for
    hierarchies. But we need to get some preliminary things out of the way
    first. The nested sets model needs a few auxiliary tables to help it.
    The first is

    CREATE VIEW LftRgt (i)
    AS SELECT lft FROM Tree
    UNION ALL
    SELECT rgt FROM Tree;

    This is all lft and rgt values in a single column. Since we should have
    no duplicates, we use a UNION ALL to construct the VIEW. Yes, LftRgt
    can be written as a derived table inside queries, but there are
    advantages to using a VIEW. Self-joins are much easier to construct.
    Code is easier to read. If more than one user needs this table, it can
    be materialized only once by the SQL engine.

    The next table is a working table to hold subtrees that we extract from
    the original tree. This could be declared as a local temporary table,
    but it would lose the benefit of a PRIMARY KEY declaration.

    CREATE TABLE WorkingTree
    (root CHAR(2) NOT NULL,
    node CHAR(2) NOT NULL,
    lft INTEGER NOT NULL,
    rgt INTEGER NOT NULL,
    PRIMARY KEY (root, node));

    The root column is going to be the value of the root node of the
    extracted subtree. This gives us a fast way to find an entire subtree
    via part of the primary key. While this is not important for the stored
    procedure discussed here, it is useful for other operations that involve
    multiple extracted subtrees.

    Let me move right to the commented code. The input parameters are the
    root node of the subtree being moved and the node which is to become its
    new parent. In this procedure, there is an assumption that new sibling
    are added on the right side of the immediate subordinates, so that
    siblings are ordered by their age.

    CREATE PROCEDURE MoveSubtree
    (IN my_root CHAR(2),
    IN new_parent CHAR(2))
    LANGUAGE SQL
    DETERMINISTIC
    BEGIN ATOMIC
    DECLARE right_most_sibling INTEGER;
    DECLARE subtree_size INTEGER;
    -- Cannot move a subtree under itself
    DECLARE Self_reference CONDITION;
    -- No such subtree root node
    DECLARE No_such_subtree CONDITION;
    -- No such parent node in the tree
    DECLARE No_such_parent_node CONDITION;

    -- clean out and rebuild working tree
    DELETE FROM WorkingTree;

    body_of_proc:
    BEGIN
    IF my_root = new_parent
    OR new_parent
    IN (SELECT T1.node
    FROM Tree AS T1, Tree AS T2
    WHERE T2.node = my_root

    AND T1.lft BETWEEN T2.lft AND T2.rgt)
    THEN SIGNAL Self_reference;
    LEAVE body_of_proc;
    END IF;

    IF NOT EXISTS
    (SELECT *
    FROM Tree
    WHERE node = my_root)
    THEN SIGNAL No_such_subtree;
    LEAVE body_of_proc;
    END IF;

    IF NOT EXISTS
    (SELECT *
    FROM Tree
    WHERE node = new_parent)
    THEN SIGNAL No_such_parent_node;
    LEAVE body_of_proc;
    END IF;

    -- put subtree into working table
    DELETE FROM WorkingTree;

    INSERT INTO WorkingTree (root, node, lft, rgt)
    SELECT my_root,
    T1.node,

    T1.lft - (SELECT MIN(lft)
    FROM Tree
    WHERE node = my_root),
    T1.rgt - (SELECT MIN(lft)
    FROM Tree
    WHERE node = my_root)
    FROM Tree AS T1, Tree AS T2
    WHERE T1.lft BETWEEN T2.lft AND T2.rgt
    AND T2.node = my_root;

    -- remove the subtree from original tree
    DELETE FROM Tree
    WHERE node IN (SELECT node FROM WorkingTree);

    -- get size and location for inserting working tree into new slot
    SET right_most_sibling
    = (SELECT rgt
    FROM Tree
    WHERE node = new_parent);

    SET subtree_size = (SELECT (MAX(rgt) +1) FROM WorkingTree);

    -- make a gap in the tree
    UPDATE Tree
    SET lft = CASE WHEN lft > right_most_sibling
    THEN lft + subtree_size
    ELSE lft END,
    rgt = CASE WHEN rgt >= right_most_sibling
    THEN rgt + subtree_size
    ELSE rgt END
    WHERE rgt >= right_most_sibling;

    -- insert the subtree and renumber its rows
    INSERT INTO Tree (node, lft, rgt)
    SELECT node,
    lft + right_most_sibling,
    rgt + right_most_sibling
    FROM WorkingTree;

    -- close gaps in tree
    UPDATE Tree
    SET lft = (SELECT COUNT(*)
    FROM LftRgt
    WHERE LftRgt.i <= Tree.lft),
    rgt = (SELECT COUNT(*)
    FROM LftRgt
    WHERE LftRgt.i <= Tree.rgt);

    -- clean out working tree table
    DELETE FROM WorkingTree;
    END body_of_proc;

    END; -- of MoveSubtree

    As a minor note, the variables right_most_sibling and subtree_size could
    have been replaced with their scalar subqueries in the UPDATE and INSERT
    INTO statements that follow their assignments. But that would make the
    code much harder to read at the cost of only a slight boost in
    performance.

    I also used this code to show how error handling is done in the SQL/PSM
    Standard language. You can declare errors, then use the SIGNAL command
    to put their names into the diagnostics area when they are detected.
    The LEAVE command voids out the actions of the labeled block of code to
    in which it appears and jumps control to the end of the block.

    This is one of the few times I will show you error handling or even the
    deferring of constraints. Each vendor's procedural language will be
    different and you will have to adjust this code to your product in the
    real world.

    03.08.02. MoveSubtree Second Version

    Another version of the MoveSubtree procedure which does not use the
    working table looks like this.

    CREATE PROCEDURE MoveSubtree
    (IN my_root CHAR(2), IN new_parent CHAR(2))
    LANGUAGE SQL
    DETERMINISTIC
    BEGIN ATOMIC
    DECLARE origin_lft INTEGER;
    DECLARE origin_rgt INTEGER;
    DECLARE new_parent_rgt INTEGER;

    SET origin_lft
    = (SELECT lft, rgt
    FROM Tree
    WHERE node = my_root);

    SET origin_rgt
    = (SELECT lft, rgt
    FROM Tree
    WHERE node = my_root);

    SET new_parent_rgt
    = (SELECT rgt
    FROM Tree
    WHERE node = new_parent);

    UPDATE Tree
    SET lft
    = lft
    + CASE
    WHEN new_parent_rgt < origin_lft
    THEN CASE
    WHEN lft BETWEEN origin_lft AND origin_rgt
    THEN new_parent_rgt - origin_lft
    WHEN lft BETWEEN new_parent_rgt
    AND origin_lft -1
    THEN origin_rgt - origin_lft + 1
    ELSE 0 END
    WHEN new_parent_rgt > origin_rgt
    THEN CASE
    WHEN lft BETWEEN origin_lft
    AND origin_rgt
    THEN new_parent_rgt - origin_rgt -1
    WHEN lft BETWEEN origin_rgt + 1
    AND new_parent_rgt -1
    THEN origin_lft - origin_rgt -1
    ELSE 0 END
    ELSE 0 END,
    rgt
    = rgt
    + CASE
    WHEN new_parent_rgt < origin_lft
    THEN CASE
    WHEN rgt BETWEEN origin_lft
    AND origin_rgt
    THEN new_parent_rgt - origin_lft
    WHEN rgt BETWEEN new_parent_rgt AND origin_lft -1

    THEN origin_rgt - origin_lft + 1
    ELSE 0 END
    WHEN new_parent_rgt > origin_rgt
    THEN CASE
    WHEN rgt BETWEEN origin_lft
    AND origin_rgt
    THEN new_parent_rgt - origin_rgt -1
    WHEN rgt BETWEEN origin_rgt + 1
    AND new_parent_rgt -1
    THEN origin_lft - origin_rgt -1
    ELSE 0 END
    ELSE 0 END;
    END; -- Movesubtree

    This code is due to Alejandro Izaguirre. It does not set a warning if
    the subtree is moved under itself, but leaves the tree unchanged.
    Again, the calculations for origin_lft, origin_rgt, and new_parent_rgt
    could be put into the UPDATE statement as scalar subquery expressions,
    but the code would be more difficulty to read.



    --CELKO--

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •