1

I'm dealing with a data structure that I haven't encountered before. The table is a tree hierarchy and looks something like this:

CREATE TABLE Tree (
    TreeID INT, -- Primary key id
    TreeLevel INT, -- Level in the tree
    TreeDown INT, -- TreeID of first node at the next lower level
    TreeRight INT -- TreeID of the next node at the same level with 0 being the end
)

I then have a list of items that are linked to various nodes in the hierarchy by the TreeID. E.g.:

CREATE TABLE Items (
    ItemID INT,
    TreeID INT, -- Node in the tree hierarchy
    Value INT
)

I'd like to do a select and group by the top level in the tree so with all the children included. For example:

SELECT Tree.TreeID, SUM(Items.Value) FROM Items
JOIN Tree ON Tree.TreeID = Items.TreeID AND Tree.TreeLevel = 0
GROUP BY Tree.TreeID

Of course, this wouldn't actually work, just giving this as an example. In reality, this would only include the items explicitly assigned to tree nodes that happen to have the level 0, but not their children. How do I include their children?

I'm using SQL Server 2008 if it matters, but an agnostic solution would be great.

2 Answers 2

2

Take a look at this related question. You're going to need to create a recursive-cte and this has a similar problem/solution.

CTE to traverse back up a hierarchy?

1
  • This is similar although the way the tree is setup is different. I'll take a look and see if I can figure it out - haven't used the CTE/recursive syntax before. Aug 18, 2011 at 4:08
0

TreeLevel is unnecessary for the solution so I've left it out.

Sample data

create table Tree 
(
    TreeID    int -- Primary key id
   ,TreeDown  int -- TreeID of first node at the next lower level
   ,TreeRight int -- TreeID of the next node at the same level with 0 being the end
)
;

insert into Tree (TreeID,TreeDown,TreeRight) values (1,2,0);
insert into Tree (TreeID,TreeDown,TreeRight) values (2,4,3);
insert into Tree (TreeID,TreeDown,TreeRight) values (3,7,0);
insert into Tree (TreeID,TreeDown,TreeRight) values (4,0,5);
insert into Tree (TreeID,TreeDown,TreeRight) values (5,0,6);
insert into Tree (TreeID,TreeDown,TreeRight) values (6,0,0);
insert into Tree (TreeID,TreeDown,TreeRight) values (7,8,0);
insert into Tree (TreeID,TreeDown,TreeRight) values (8,0,9);
insert into Tree (TreeID,TreeDown,TreeRight) values (9,0,0);

insert into Tree (TreeID,TreeDown,TreeRight) values (10,11,0);
insert into Tree (TreeID,TreeDown,TreeRight) values (11,0,0);

insert into Tree (TreeID,TreeDown,TreeRight) values (12,13,0);
insert into Tree (TreeID,TreeDown,TreeRight) values (13,0,14);
insert into Tree (TreeID,TreeDown,TreeRight) values (14,15,0);
insert into Tree (TreeID,TreeDown,TreeRight) values (15,16,0);
insert into Tree (TreeID,TreeDown,TreeRight) values (16,0,0);


create table Items 
(
    ItemID  int
   ,TreeID  int -- Node in the tree hierarchy
   ,Val     int
)
;

insert into Items (ItemID,TreeID,Val) values (1001,1,1);
insert into Items (ItemID,TreeID,Val) values (1002,1,1);
insert into Items (ItemID,TreeID,Val) values (1004,6,2);
insert into Items (ItemID,TreeID,Val) values (1005,7,2);
insert into Items (ItemID,TreeID,Val) values (1006,8,0);
insert into Items (ItemID,TreeID,Val) values (1007,9,3);
insert into Items (ItemID,TreeID,Val) values (1008,12,4);
insert into Items (ItemID,TreeID,Val) values (1009,15,3);
insert into Items (ItemID,TreeID,Val) values (1010,15,2);
insert into Items (ItemID,TreeID,Val) values (1011,15,1);

Solution

Oracle / SQL Server / SQLLite

For PostgreSQL / Teradata add the word 'recursive' after the word 'with'

with        cte (root_TreeId,TreeId,TreeDown,TreeRight)
            as
            (
                    select      t.TreeId        as root_TreeId
                               ,t.TreeId
                               ,t.TreeDown
                               ,t.TreeRight

                    from        Tree    t   

                    where       t.TreeId not in (select TreeDown from Tree union select TreeRight from Tree)

                    union all

                    select      c.root_TreeId
                               ,t.TreeID
                               ,t.TreeDown
                               ,t.TreeRight

                    from                    cte     c

                                join        Tree    t

                                on          t.TreeID = c.TreeDown
                                        or  t.TreeID = c.TreeRight
            )

select      c.root_TreeID

           ,count (distinct c.TreeID)   as nodes
           ,count (i.ItemID)            as items
           ,sum   (i.Val)               as sum_item_value

from                    cte     c

            left join   Items   i

            on          i.TreeID    =
                        c.TreeID

group by    c.root_TreeID
;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.