Как рассчитать сумму значений в дереве с помощью SQL

Question

Мне нужно суммировать баллы на каждом уровне, заработанном деревом пользователей. Уровень 1 - это сумма очков пользователей пользователей на 1 уровень ниже пользователя. Уровень 2 - это очки уровня 1 пользователей, которые находятся на 2 уровня ниже пользователя и т. Д.

Расчет происходит один раз в месяц на непроизводственном сервере, не беспокойтесь о производительности.

Как будет выглядеть SQL для этого?

Если ты запутался, не волнуйся, я тоже!

Таблица пользователей:

ID    ParentID    Points
1     0           230
2     1           150
3     0           80
4     1           110
5     4           54
6     4           342

Tree:
0
|---\
1    3
| \
2  4---
    \  \
     5  6

Вывод должен быть:

ID    Points    Level1     Level2
1     230       150+110    150+110+54+342
2     150
3     80
4     110       54+342
5     54
6     342

Синтаксис и функции SQL Server предпочтительно ...

Answer 1

Деревья плохо работают с SQL. Если у вас очень (очень очень) мало обращений к записи, вы можете изменить реализацию дерева, чтобы использовать вложенные наборы, что сделало бы этот запрос невероятно простым.

Пример (если я не ошибаюсь):

SELECT SUM(points) 
FROM users 
where left > x and right < y 

Однако любые изменения в дереве требуют касания огромного количества строк. Возможно, лучше просто выполнить рекурсию в своем клиенте.

Answer 2

Если бы вы использовали СУБД Oracle, это было бы довольно просто, поскольку Oracle поддерживает древовидные запросы с синтаксисом CONNECT BY / STARTS WITH . Для SQL Server, я думаю, вы могли бы найти Общие табличные выражения полезными

Answer 3

Хорошо, это дает вам результаты, которые вы ищете, но нет никаких гарантий, что я ничего не пропустил. Считайте это отправной точкой. Я использовал SQL 2005 для этого, SQL 2000 не поддерживает CTE

WITH Parent (id, GrandParentId, parentId, Points, Level1Points, Level2Points)
AS
(
    -- Find root
    SELECT id,  
            0 AS GrandParentId,
            ParentId,
            Points,
            0 AS Level1Points,
            0 AS Level2Points
    FROM tblPoints ptr
    WHERE ptr.ParentId = 0

    UNION ALL (
    -- Level2 Points
    SELECT pa.GrandParentId AS Id,
            NULL AS GrandParentId,
            NULL AS ParentId,
            0 AS Points, 
            0 AS Level1Points,
            pa.Points  AS Level2Points
    FROM tblPoints pt
            JOIN Parent pa ON pa.GrandParentId = pt.Id 
    UNION  ALL
    -- Level1 Points
    SELECT pt.ParentId AS Id,
            NULL AS GrandParentId,
            NULL AS ParentId,
            0 AS Points, 
            pt.Points AS Level1Points,
            0 AS Level2Points
    FROM tblPoints pt
            JOIN Parent pa ON pa.Id = pt.ParentId AND pa.ParentId IS NOT NULL 
    UNION  ALL
    -- Points
    SELECT pt.id,
            pa.ParentId AS GrandParentId,
            pt.ParentId,
            pt.Points, 
            0 AS Level1Points,
            0 AS Level2Points
    FROM tblPoints pt
            JOIN Parent pa ON pa.Id = pt.ParentId AND pa.ParentId IS NOT NULL )
)
SELECT id, 
    SUM(Points) AS Points,  
    SUM(Level1Points) AS Level1Points,
    CASE WHEN SUM(Level2Points) > 0 THEN  SUM(Level1Points) + SUM(Level2Points) ELSE 0 END AS Level2Points
FROM Parent
GROUP BY id 
ORDER by id

Answer 4

SQL в целом, как говорили другие, не очень хорошо справляется с такими отношениями. Обычно требуется суррогатная таблица «отношений» (id, parent_id, уникальный ключ на (id, parent_id)), где:

• каждый раз, когда вы добавляете запись в «таблицу», вы:

  INSERT INTO relations (id, parent_id) VALUES ([current_id], [current_id]);

  INSERT INTO relations (id, parent_id) VALUES ([current_id], [current_parent_id]);

  INSERT INTO relations (id, parent_id) SELECT [current_id], parent_id FROM relations WHERE id = [current_parent_id];

• есть логика, чтобы избежать циклов

• убедитесь, что обновления, удаления в «отношениях» обрабатываются с помощью хранимых процедур

Учитывая эту таблицу, вы хотите:

SELECT rel.parent_id, SUM(tbl.points)
FROM table tbl INNER JOIN relations rel ON tbl.id=rel.id
WHERE rel.parent_id <> 0
GROUP BY rel.parent_id;

Answer 5

Если вы работаете с деревьями, хранящимися в реляционной базе данных, я бы посоветовал посмотреть на «вложенный набор» или «измененный обход дерева предзаказа». SQL будет так просто:

SELECT id, 
       SUM(value) AS value 
FROM table 
WHERE left>left\_value\_of\_your\_node 
  AND right<$right\_value\_of\_your\_node;

... и делайте это для каждого интересующего вас узла.

Может быть, это поможет вам: http://www.dbazine.com/oracle/or-articles/tropashko4 или воспользуйтесь Google.

Answer 6

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

(Или вы можете получить MS SQL Server 2008 и получить новые функции иерархии ...;))

Answer 7

Следующая таблица:

Id   ParentId
1   NULL
11    1
12    1
110 11
111 11
112 11
120 12
121 12
122 12
123 12
124 12

И следующая таблица сумм:

Id     Val
110 500
111 50
112 5
120 3000
121 30000
122 300000

Только для идентификаторов листьев (последний уровень) определено значение. Запрос SQL для получения данных выглядит так:

;WITH Data (Id, Val) AS
(
    select t.Id, SUM(v.val) as Val from dbo.TestTable t
    join dbo.Amount v on t.Id = v.Id
    group by t.Id
)

select cd.Id, ISNULL(SUM(cd.Val), 0) as Amount FROM
(
    -- level 3
    select t.Id, d.val from TestTable t
    left join Data d on d.id = t.Id

    UNION

    -- level 2
    select t.parentId as Id, sum(y.Val) from TestTable t
    left join Data y on y.id = t.Id
    where t.parentId is not null
    group by t.parentId

    UNION

    -- level 1
    select t.parentId as Id, sum(y.Val) from TestTable t
    join TestTable c on c.parentId = t.Id
    left join Data y on y.id = c.Id
    where t.parentId is not null
    group by t.parentId
) AS cd
group by id

это приводит к выводу:

Id     Amount
1     333555
11   555
12   333000
110 500
111 50
112 5
120 3000
121 30000
122 300000
123 0
124 0

Надеюсь, это поможет.

Answer 8

Вы можете написать простую рекурсивную функцию для выполнения этой работы. Мой MSSQL немного ржавый, но выглядит это так:

CREATE FUNCTION CALC
(
@node integer,
)
returns 
(
@total integer
)
as
begin
    select @total = (select node_value from yourtable where node_id = @node);

    declare @children table (value integer);
    insert into @children   
    select calc(node_id) from yourtable where parent_id = @node;

    @current = @current + select sum(value) from @children;
    return
end

Answer 9

У вас есть несколько вариантов:

1. Использовать курсор и рекурсивный вызов пользовательской функции (это довольно медленно)
2. Создайте кеш-таблицу, обновите ее на INSERT с помощью триггера (это самое быстрое решение, но может быть проблематично, если у вас много обновлений в основной таблице)
3. Выполнить рекурсивный расчет на стороне клиента (желательно, если у вас не слишком много записей)