powered by simpleCommunicator - 2.0.53     © 2025 Programmizd 02
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
17 сообщений из 17, страница 1 из 1
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964369
Mtgktem
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Вопрос для разминки ума умных людей форума))

Классическое дерево.

За каждым узлом закреплен небольшой набор данных int, например [52,6]
Уровень в таблице присутствует (bal_lev).
Корневого элемента в таблице нет, он имеет id = 1

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

Т.е. в этом примере нужно:
-- из узла 66 вычесть данные узлов 67 и 73,
-- из узла 71 вычесть данные узлов 74 и 72,
-- из узла 70 вычесть данные узла 71,

(версия 2008R2)

-- ИСХОДНОЕ ДЕРЕВО, уровней n (поле уровня имеется):

66, 70, 71,... - это просто id узлов элементов
[52,6], [30,2],... - это просто данные этих узлов

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
--------------+----------+----------+
---|   lev1   |   lev2   |   lev3   |
--------------+----------+----------+
-- |
-- +-66[52,6]
-- |  |
-- |  +---------67[30,2]
-- |  |
-- |  +---------73[20,4]
-- |
-- +-70[15,26]
-- |  |
-- |  +---------71[14,26]
-- |             |
-- |             +---------74[8,10]
-- |             |
-- |             +---------72[2,16]
-- |

============================

-- ЖЕЛАЕМОЕ ДЕРЕВО:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
--------------+----------+----------+
---|   lev1   |   lev2   |   lev3   |
--------------+----------+----------+
-- |
-- +-66[2,0]
-- |  |
-- |  +---------67[30,2]
-- |  |
-- |  +---------73[20,4]
-- |
-- +-70[1,0]
-- |  |
-- |  +---------71[4,0]
-- |             |
-- |             +---------74[8,10]
-- |             |
-- |             +---------72[2,16]
-- |

============================

-- ИСХОДНАЯ ТАБЛИЦА:

DECLARE @Tab_BTree TABLE
(
[bal_id] int, [bal_id_parent] int, [bal_lev] int,
[b_data1] int, [b_data2] int -- (а возможно и data3, data4,..)
)

INSERT INTO @Tab_BTree VALUES (66, 1, 1, 52, 6)
INSERT INTO @Tab_BTree VALUES (67, 66, 2, 30, 2)
INSERT INTO @Tab_BTree VALUES (73, 66, 2, 20, 4)
INSERT INTO @Tab_BTree VALUES (74, 71, 3, 8 , 10)
INSERT INTO @Tab_BTree VALUES (72, 71, 3, 2 , 16)
INSERT INTO @Tab_BTree VALUES (70, 1, 1, 15, 26)
INSERT INTO @Tab_BTree VALUES (71, 70, 2, 14, 26)

SELECT * FROM @Tab_BTree
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
-- ===============================================
-- bal_id   bal_id_parent   bal_lev	b_data1	b_data2
-- 66       1               1           52      6
-- 67       66              2           30      2
-- 73       66              2           20      4
-- 74       71              3           8       10
-- 72       71              3           2       16
-- 70       1               1           15      26
-- 71       70              2           14      26


==================================================


-- ЖЕЛАЕМЫЙ РЕЗУЛЬТАТ

SELECT * FROM @Tab_Result
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
-- ===============================================
-- bal_id   bal_id_parent   bal_lev	b_data1	b_data2
-- 66       1               1           2       0
-- 67       66              2           30      2
-- 73       66              2           20      4
-- 74       71              3           8       10
-- 72       71              3           2       16
-- 70       1               1           1       0
-- 71       70              2           4       0

Если в начальном рекурсивном запросе делать выборку по максимальному уровню,
то есть проблема - не все ветви могут быть заполнены до максимального уровня (в этом примере ветвь 70 до 3-го, но, например, ветвь 66 - до 2-го), а значит могут и не попасть в результат.

Подскажите, как же это можно сделать?
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964373
Mtgktem
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Наверно не совсем корректно сформулирован вопрос,
думаю, что расчет при рекурсии нужно вести не с конца дерева, а с корневых веток.

Ну в любом случае, результат должен быть именно такой, как в результирующей табличке.
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964381
Mtgktem
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Есть идеи?
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964387
Дмитрий Мух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Mtgktem,

ветки, листья, рекурсия... зачем тут это всё?

просуммируйте данные с группировкой по bal_id_parent и получите идентификаторы строк для изменения и какие величины должны фигурировать в инструкции UPDATE
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964416
Mtgktem
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Дмитрий Мух, спасибо!

В (нужном мне) простейшем варианте решилось так:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
UPDATE dt
   SET dt.[b_data1]=dt.[b_data1]-sm.[sum_data1], dt.[b_data2]=dt.[b_data2]-sm.[sum_data2]
FROM @Tab_BTree dt 
	join
	(SELECT bt.[bal_id_parent], 
		SUM(bt.[b_data1]) AS [sum_data1], SUM(bt.[b_data2]) AS [sum_data2] FROM @Tab_BTree bt
	  GROUP BY bt.[bal_id_parent]) sm
	ON dt.[bal_id] = sm.[bal_id_parent]
-- SELECT * FROM @Tab_BTree

Для моих целей этого вполне достаточно.
В моем случае - из предка вычитаются потомки, вычет происходит разово .

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

А как такое сделать? Можно с примером? )
В целях повышения, так сказать, собственной эрудиции))
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964424
Дмитрий Мух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Mtgktem,

можно и с примером, но не сегодня :) выходные
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964430
Mtgktem
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
вторая задачка

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
-- ЖЕЛАЕМОЕ ДЕРЕВО:

--------------+----------+----------+
---|   lev1   |   lev2   |   lev3   |
--------------+----------+----------+
-- |
-- +-66[2,0]
-- |  |
-- |  +---------67[30,2]
-- |  |
-- |  +---------73[20,4]
-- |
-- +-70[11,26]
-- |  |
-- |  +---------71[4,0]
-- |             |
-- |             +---------74[8,10]
-- |             |
-- |             +---------72[2,16]
-- |

============================

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
-- ЖЕЛАЕМЫЙ РЕЗУЛЬТАТ

SELECT * FROM @Tab_Result
-- ===============================================
-- bal_id   bal_id_parent   bal_lev	b_data1	b_data2
-- 66       1               1           2       0
-- 67       66              2           30      2
-- 73       66              2           20      4
-- 74       71              3           8       10
-- 72       71              3           2       16
-- 70       1               1           11      0
-- 71       70              2           4       0
(в отличие от предыдущей задачки в узле 70 - другие данные)
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964468
Фотография Ennor Tiegael
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Mtgktem,

Угу, нода 70 не стыкуется между желаемым деревом и желаемым результатом. Я понимаю, как вы можете получить (11,26), но я не понимаю, как можно получить (11,0). Уточняйте на пальцах.
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964491
aleks222
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
DECLARE @Tab_BTree TABLE
(
	[bal_id] int, [bal_id_parent] int, [bal_lev] int,
	[b_data1] int, [b_data2] int -- (а возможно и data3, data4,..)
	, [n_data1] int, [n_data2] int -- (а возможно и data3, data4,..)
)

INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1], [b_data2]) VALUES (66, 1, 1, 52, 6)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1], [b_data2]) VALUES (67, 66, 2, 30, 2)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1], [b_data2]) VALUES (73, 66, 2, 20, 4)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1], [b_data2]) VALUES (74, 71, 3, 8 , 10)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1], [b_data2]) VALUES (72, 71, 3, 2 , 16)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1], [b_data2]) VALUES (70, 1, 1, 15, 26)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1], [b_data2]) VALUES (71, 70, 2, 14, 26)

declare @l int = (select max(bal_lev) from @Tab_BTree );

select * from @Tab_BTree;

while @l > 0 begin

  with t as ( select * from @Tab_BTree )
     , l as ( select * from t where [bal_lev] = @l )
    update l set [n_data1] = l.[b_data1] - isnull( x.[b_data1], 0)
	           , [n_data2] = l.[b_data2] - isnull( x.[b_data2], 0)
	  from l 
	       cross apply ( select [b_data1] = sum([b_data1]), [b_data2] = sum([b_data2]) from t where t.[bal_id_parent] = l.bal_id ) as x

  set @l = @l - 1;

end;

select * from @Tab_BTree;
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964497
aleks222
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
DECLARE @Tab_BTree TABLE
(
	[bal_id] int, [bal_id_parent] int, [bal_lev] int,
	[b_data1] int, [b_data2] int -- (а возможно и data3, data4,..)
)

INSERT INTO @Tab_BTree VALUES (66, 1, 1, 52, 6)
INSERT INTO @Tab_BTree VALUES (67, 66, 2, 30, 2)
INSERT INTO @Tab_BTree VALUES (73, 66, 2, 20, 4)
INSERT INTO @Tab_BTree VALUES (74, 71, 3, 8 , 10)
INSERT INTO @Tab_BTree VALUES (72, 71, 3, 2 , 16)
INSERT INTO @Tab_BTree VALUES (70, 1, 1, 15, 26)
INSERT INTO @Tab_BTree VALUES (71, 70, 2, 14, 26)

declare @l int = 1, @rc int = 1;

select * from @Tab_BTree;

while @rc > 0 begin

  with t as ( select * from @Tab_BTree )
     , l as ( select * from t where [bal_lev] = @l )
    update l set [b_data1] = l.[b_data1] - isnull( x.[b_data1], 0)
	           , [b_data2] = l.[b_data2] - isnull( x.[b_data2], 0)
	  from l 
	       cross apply ( select [b_data1] = sum([b_data1]), [b_data2] = sum([b_data2]) from t where t.[bal_id_parent] = l.bal_id ) as x
  ;
  set @rc = @@rowcount;

  set @l = @l + 1;

end;

select * from @Tab_BTree;
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964500
aleks222
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
DECLARE @Tab_BTree TABLE
(
	[bal_id] int, [bal_id_parent] int, [bal_lev] int,
	[b_data1] int, [b_data2] int -- (а возможно и data3, data4,..)
)

INSERT INTO @Tab_BTree VALUES (66, 1, 1, 52, 6)
INSERT INTO @Tab_BTree VALUES (67, 66, 2, 30, 2)
INSERT INTO @Tab_BTree VALUES (73, 66, 2, 20, 4)
INSERT INTO @Tab_BTree VALUES (74, 71, 3, 8 , 10)
INSERT INTO @Tab_BTree VALUES (72, 71, 3, 2 , 16)
INSERT INTO @Tab_BTree VALUES (70, 1, 1, 15, 26)
INSERT INTO @Tab_BTree VALUES (71, 70, 2, 14, 26)

declare @l int = 1, @rc int = 1;

  with t as ( select * from @Tab_BTree )
     , l as ( select t.[bal_id], t.[bal_id_parent], t.[bal_lev], [b_data1] = t.[b_data1] - isnull( x.[b_data1], 0), [b_data2] = t.[b_data2] - isnull( x.[b_data2], 0) from t cross apply ( select [b_data1] = sum([b_data1]), [b_data2] = sum([b_data2]) from t as l where l.[bal_id_parent] = t.bal_id ) as x 
	        )
	 select * from l
  ;
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964503
Mtgktem
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Сейчас поясню.

С первой задачей все ок. Она решена.

Сейчас речь идет о второй задачке.
Исходное дерево и табличка к ней все те же.

Поясняю на пальцах про желаемое дерево и желаемую табличку для второй задачки:

с веткой 66 получается все так же, как и в первой.
(но если вдруг будет использована рекурсия от листьев к основанию, начиная со всех узлов уровня 3,
то важно не потерять эту ветку в расчетах, т.к. листья у ветки 66 начинаются с уровня 2)

теперь про ветку 70 (в исходном дереве)
-- из предка 71[14,26] вычитаются данные его потомков 74[8,10] и 72[2,16], получается 71[4,0]
-- из предка 70[15,26] вычитаются расчитанные данные его потомка 71[4,0], получается 70[11,26]

Да, Вы правы, это моя ошибка.
Исправляюсь.
Правильный желаемый результат для узла 70[11,26]

в итоге желаемая табличка должна получиться так:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
SELECT * FROM @Tab_Result
-- ===============================================
-- bal_id   bal_id_parent   bal_lev	b_data1	b_data2
-- 66       1               1           2       0
-- 67       66              2           30      2
-- 73       66              2           20      4
-- 74       71              3           8       10
-- 72       71              3           2       16
-- 70       1               1           11      26
-- 71       70              2           4       0

Вкратце -
в первой задачке одноразовое вычисление,
а в этой задачке дожны учитываться и предыдущие вычтенные данные узла.
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964508
Mtgktem
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Дмитрий Мух, Ennor Tiegael, aleks222

Заранее всех благодарю. Всех читаю, пробую, проверяю. Спасибо!
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964564
Фотография Ennor Tiegael
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Mtgktem,

Я так и подумал. Тогда легко, можно даже без циклов:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
DECLARE @Tab_BTree TABLE
(
[bal_id] int, [bal_id_parent] int, [bal_lev] int,
[b_data1] int, [b_data2] int -- (а возможно и data3, data4,..)
)

INSERT INTO @Tab_BTree
VALUES
	(66, 1, 1, 52, 6),
	(67, 66, 2, 30, 2),
	(73, 66, 2, 20, 4),
	(74, 71, 3, 8 , 10),
	(72, 71, 3, 2 , 16),
	(70, 1, 1, 15, 26),
	(71, 70, 2, 14, 26);

with cte as (
	-- Updateable nodes
	select t.bal_id as [Id],
		t.bal_lev as [NestLevel],
		t.bal_id_parent as [ParentId],
		t.b_data1, t.b_data2,
		t.bal_id as [RootId],
		0 as [RelativeNestLevel]
	from @Tab_BTree t
	where exists (
		select 0 from @Tab_BTree l where l.bal_id_parent = t.bal_id
	)
	union all
	-- Subtrees
	select t.bal_id, t.bal_lev, t.bal_id_parent,
		t.b_data1, t.b_data2,
		c.RootId,
		t.bal_lev - c.NestLevel + c.RelativeNestLevel
	from cte c
		inner join @Tab_BTree t on t.bal_id_parent = c.Id
)
select *
from @Tab_BTree t
	cross apply (
		select sum(c.b_data1 * power(-1, c.RelativeNestLevel)) as [Sum1],
			sum(c.b_data2 * power(-1, c.RelativeNestLevel)) as [Sum2]
		from cte c
		where c.RootId = t.bal_id
	) ca
order by t.bal_id;

Учтите только, что если ваше дерево большое и, эээ, раскидистое, то этот код может проигрывать итеративному. Тогда можно попробовать CTE материализовать во временную таблицу и соотв-но проиндексировать.
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964578
Mtgktem
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Спасибо, отлично подходит.
А как думаете, примерно со скольки узлов/веток/листьев стоит индексировать?
(выявлять путем сравнительных котёнковых экспериментов?)
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964581
Фотография Ennor Tiegael
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Mtgktem,

Все зависит от ваших реалий. Хорошо проиндексированная исходная таблица на мощном сервере даже и на миллионе записей может показать приемлемую производительность (опять-таки, смотря что для вас "приемлемо").

Сначала попробуйте, как есть. Если слишком медленно, то материализуйте CTE с кластерным индексом по RootId (уникальным его правда сделать не получится, ключ тут, похоже, Id + RelativeNestLevel). К тому же, некоторые столбцы в CTE похоже лишние, ParentId например - можно его выкинуть и немного сэкономить. NestLevel используется только для вычисления RelativeNestLevel и далее не нужен - в случае кэширования во времянку его можно не вставлять в таблицу.

Экспериментируйте, в общем.
...
Рейтинг: 0 / 0
Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
    #39964601
fkthat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
DECLARE @Tab_BTree TABLE
(
	[bal_id] int,
  [bal_id_parent] int,
  [bal_lev] int,
	[b_data1] int
)

INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1]) VALUES (66, 1, 1, 52)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1]) VALUES (70, 1, 1, 15)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1]) VALUES (67, 66, 2, 30)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1]) VALUES (73, 66, 2, 20)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1]) VALUES (71, 70, 2, 14)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1]) VALUES (74, 71, 3, 8)
INSERT INTO @Tab_BTree([bal_id], [bal_id_parent], [bal_lev],	[b_data1]) VALUES (72, 71, 3, 2)

;with cte(parent_id, child_id, child_level, child_data) as (
  select bal_id_parent, bal_id, bal_lev, b_data1
      from @Tab_BTree
  union all
  select cte.parent_id, t.bal_id, t.bal_lev, t.b_data1 
    from @Tab_BTree t join cte on cte.child_id = t.bal_id_parent
)
select cte.parent_id, 
t.b_data1 + sum(
   case
      when (cte.child_level - t.bal_lev) % 2 = 1 then -cte.child_data
      else cte.child_data
  end
)
from cte join @Tab_BTree t on cte.parent_id = t.bal_id
group by cte.parent_id, t.b_data1
order by parent_id



Код: sql
1.
2.
3.
4.
5.
id          
----------- -----------
66          2
70          11
71          4
...
Рейтинг: 0 / 0
17 сообщений из 17, страница 1 из 1
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Дерево. Подскажите, как вычесть из веток все их листья и до самого корня?
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]