SQL - Выбор родительских / верхних узлов и потомков в иерархии данных / дереве

Question

Я имею дело со структурой данных, с которой я раньше не сталкивался.Таблица представляет собой древовидную иерархию и выглядит примерно так:

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
)

Затем у меня есть список элементов, которые связаны с различными узлами в иерархии посредством TreeID.Например:

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

Я бы хотел сделать выборку и сгруппировать по верхнему уровню в дереве, чтобы все дети были включены.Например:

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

Конечно, на самом деле это не сработает, просто приведя это в качестве примера.В действительности это будет включать только элементы, явно назначенные узлам дерева, которые имеют уровень 0, но не их дочерние элементы.Как мне включить их детей?

Я использую SQL Server 2008, если это имеет значение, но агностическое решение было бы здорово.

Answer 1

Посмотрите на этот связанный вопрос. Вам нужно будет создать recursive-cte, и у этого есть похожая проблема / решение.

CTE, чтобы пересечь иерархию?

Answer 2

TreeLevel не требуется для решения, поэтому я его опущу.

Образцы данных

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);

Решение

Oracle / SQLСервер / SQLLite

Для PostgreSQL / Teradata добавьте слово «рекурсивный» после слова «с помощью»

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
;