Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Дерево и наследование  [new]
Шыфл
Member

Откуда: Прага
Сообщений: 691
Добрый день.

Есть дерево скидок

CREATE TABLE [dbo].[DiscountsTree](
	[TreeId] [int] NOT NULL,
	[TreeFatherId] [int] NOT NULL,
	[TreeName] [nvarchar](50) NOT NULL,
	[TreeDescription] [nvarchar](255) NULL,
	[TreeLeft] [int] NULL,
	[TreeRight] [int] NULL,
	[TreeTypeId] [int] NOT NULL)


Есть таблица темплейтов скидок

CREATE TABLE [dbo].[DiscountsTemplate](
	[DiscountTemplateId] [int] NOT NULL,
	[TreeId] [int] NOT NULL,
	[SalesDiscount] [decimal](5, 4) NULL)



которая содержит данные о скидках клиентов, которые наследуются вниз по дереву.

Задача которую решил - найти для произвольного узла значение скидки с учётом наследования (если есть прямое значение - то его, если нет - первое not null ближайшего узла вверх)
+ некрасивое решение

declare @treeid int = 848
;with cte as
(
	select 
		1 rn, 
		dt.* 
	from DiscountsTree dt
	where dt.TreeId=@treeid

union all
	select 
		cte.rn+1 rn,
		dt.* 
	from 
		DiscountsTree dt
	inner join cte on dt.TreeId=cte.TreeFatherId 
)
select * from cte 
outer apply  
	(select 
		SalesDiscount,cte.TreeName 
	from cte
	inner join DiscountsTemplate ddt 
		on cte.TreeId=ddt.TreeId 
		and ddt.DiscountTemplateId=-1
where rn in ( 
				select min(rn) 
				from cte 
				left join DiscountsTemplate ddt 
					on cte.TreeId=ddt.TreeId 
					and DiscountTemplateId=-1
				where ddt.SalesDiscount is not null
			)
	) k
where cte.rn=1



Обратная задача - развернуть дерево вниз от корня с учётом наследования, т.е. если нет собственного значения взять значение ближайшего узла вверх для всего дерева.
Ну не хочется ж делать скалярную функцию и дёргать её для каждого элемента, это ж умнее решается наверняка...
1 сен 17, 14:20    [20764675]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 5136
Шыфл,

попробуйте hierarchyid, отвечает требованиям поиска по дереву родителя.
1 сен 17, 14:32    [20764733]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
Шыфл
Member

Откуда: Прага
Сообщений: 691
Владислав Колосов,
Нам кузнец не нужен (с)

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

Таки не придумал ничего лучше скалярной функции - по номеру клиента и нода определить наследуемую скидку. Если она равна собственной скидке нода - удалить без зазрений совести.
Всего по всем клиентам <150к записей Discounts, дерево <1,5к узлов DiscountsTree, несмотря на жуткость решения на первый взгляд, работало <30 сек.

Вопреки ожиданиям менеджмента, удалилось <5% нодов.
1 сен 17, 16:45    [20765218]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
Шыфл
Member

Откуда: Прага
Сообщений: 691
Продолжаем упрощать дерево:

Задача: пройтись по нодам дерева, и если для какого-то узла все "низлежащие" ноды, без исключений, содержат скидку и эта скидка одинакова - удалить низлежащие ноды, а скидку перененести на родителя.

Что-то нет идей совсем как это сделать, воображение рисует жуткие вложенные циклы и курсоры ;(
4 окт 17, 12:17    [20841638]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
Руслан Дамирович
Member

Откуда: Резиновая нерезиновая
Сообщений: 425
Шыфл, я бы начал с чего-то такого
WITH
cte AS (
SELECT
  [init] = nn.[node_id],
  nn.[node_id],
  nn.[discount]
FROM
  nodes nn
UNION ALL
SELECT
  cte.[init],
  nn.[node_id],
  nn.[discount]
FROM
  cte
  INNER JOIN nodes nn ON (
      nn.[parent_id] = cte.[node_id] )
)
SELECT
  [init],
  [init_disc] = MAX( CASE WHEN [node_id] = [init] THEN [discount] END ),
  [max_disc] = MAX( CASE WHEN [node_id] != [init] THEN [discount] END ), 
  [avg_disc] = AVG( CASE WHEN [node_id] != [init] THEN [discount] END )
FROM
  cte
GROUP BY
  [init]
4 окт 17, 12:37    [20841736]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
Шыфл
Member

Откуда: Прага
Сообщений: 691
Руслан Дамирович,

Спасибо за идею, пока не знаю, куда её прикрутить, но выглядит наглядно.
+

;WITH
dte as (
select dt.TreeId,dt.TreeFatherId,dt.TreeName,dt.TreeLeft,dt.TreeRight,dt.TreeTypeId, d.SalesDiscount 
  FROM
  DiscountsTree dt
  left join Discount d on dt.TreeId=d.TreeId and d.CustomerId=18551
),
cte AS (
SELECT
  [init] = TreeId,
  TreeId TreeFatherId,
  SalesDiscount,
  dte.TreeLeft
  FROM
  dte
UNION ALL
SELECT
  cte.[init],
  dte.TreeFatherId,
  dte.SalesDiscount,
  cte.TreeLeft
FROM
  cte
  INNER JOIN dte  
	ON dte.TreeId = cte.TreeFatherId
)

SELECT
  [init],treeleft,
  [init_disc]	= MAX( CASE WHEN cte.TreeFatherId = [init] THEN SalesDiscount END ),
  [max_disc]	= MAX( CASE WHEN cte.TreeFatherId != [init] THEN SalesDiscount END ), 
  [avg_disc]	= AVG( CASE WHEN cte.TreeFatherId != [init] THEN SalesDiscount END ),
  [ct_disc]		= SUM(case when cte.SalesDiscount IS null then 0 else 1 end),
  [ct_all]		= SUM(CASE WHEN cte.TreeFatherId = [init] THEN 0 else 1 end)
FROM
	cte
GROUP BY
  [init],TreeLeft
order by TreeLeft



Что-то мне подсказывает, что просто эта задача не решается. Особенно учитывая, что нужно пересчитывать для каждого клиента в отдельности, похоже удобнее написать это на другом языке, нежели T-SQL, потому что без курсоров не обойтить ИМХО, слишком много условий нужно контролировать.
Плюс ко всему данные тоже не высшего качества, иногда исключения в наследовании, не позволяющие схлопнуть ветку - это ошибка которую нужно исправить, а иногда - так надо, и определить что есть что могут только ответственные менеджеры...
4 окт 17, 16:12    [20842746]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
TaPaK
Member

Откуда: Kiev
Сообщений: 3604
Шыфл,

у нас для деревьев есть таблица генерируемая триггером вида ParentId,ChildId которая легко даёт либо всех предков, либо всех подчинённых
4 окт 17, 16:15    [20842761]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
Шыфл
Member

Откуда: Прага
Сообщений: 691
TaPaK,

У нас каждое утро делается полный экспорт дерева по всем релевантным клиентам. И treeLeft-treeRight посчитаны, проблема не в этом. Проблема в том, что смотришь на ветку, там все скидки проставлены, одинаковые, кроме одной, которой нет вообще, и наследовать неоткуда. И что с ней делать, может решить только менеджер этого конкретного клиента, приложение ты этому не научишь.

Поэтому, используя идею Руслана Дамировича делаю список кандидатов на схлопывание и список странных исключений - пока что это максимум автоматизации.
4 окт 17, 16:26    [20842821]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
aleks222
Guest
Шыфл
Продолжаем упрощать дерево:

Задача: пройтись по нодам дерева, и если для какого-то узла все "низлежащие" ноды, без исключений, содержат скидку и эта скидка одинакова - удалить низлежащие ноды, а скидку перененести на родителя.

Что-то нет идей совсем как это сделать, воображение рисует жуткие вложенные циклы и курсоры ;(


Осподе, чему вас учили? Жертвы рекурсии.

Задача: 1) пройтись по нодам дерева, и если для какого-то узла все "низлежащие" ноды, без исключений, содержат скидку и эта скидка одинакова - удалить низлежащие ноды, 2) а скидку перененести на родителя.

эквивалентна

Задача: 1) удалить нод-лист (нод без потомков) дерева, если его вышележащий содержит ту же самую скидку.
2) для предков, у которого есть только нод-листы (ноды без потомков) и эти ноды содержат одинаковую скидку - перенести на предка скидку;

Решается двумя элементарными update в цикле "пока есть чего update - тать".
4 окт 17, 16:42    [20842876]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
Шыфл
Member

Откуда: Прага
Сообщений: 691
aleks222
Осподе, чему вас учили? Жертвы рекурсии.

Задача: 1) пройтись по нодам дерева, и если для какого-то узла все "низлежащие" ноды, без исключений, содержат скидку и эта скидка одинакова - удалить низлежащие ноды, 2) а скидку перененести на родителя.

эквивалентна

Задача: 1) удалить нод-лист (нод без потомков) дерева, если его вышележащий содержит ту же самую скидку.
2) для предков, у которого есть только нод-листы (ноды без потомков) и эти ноды содержат одинаковую скидку - перенести на предка скидку;

Решается двумя элементарными update в цикле "пока есть чего update - тать".


Гладко было на бумаге, да забыли про овраги...

Наши задачи не эквивалентны. Задачу 1 в формулировке
удалить нод, если его вышележащий содержит ту же самую скидку.

Это я уже решил, уже к третьему посту. Проблема в том, что для листов, у которых есть собственные скидки, прямой родитель может скидки не содержать. И тут мы плавно переходим к задаче 2
для предков, у которого есть только нод-листы (ноды без потомков) и эти ноды содержат одинаковую скидку - перенести на предка скидку
Все изменения должны быть эквивалентны. Если хотя бы у одного потомка скидки нет, нельзя ничего переносить на родителя, ибо тогда она появится там где её не было.

Вскрытие показало, что дерево дырявое донельзя, потому что сортимент меняется со временем и там, где скидки на листьях (продуктах), их редко добавляют вовремя. Только если клиент решил купить новинку и обнаружил отсуствие скидки, тогда он обращается к манагеру, который торгуется с ним о данной конкретной новинке. А если продукт не интересен покупателю, то у него образуется пробел в скидках, который там висит и никому не мешает, кроме, как выяснилось, меня.

Потому как если заполнить 5000 пустых нодов, можно схлопнуть всю таблицу в 3 раза.
4 окт 17, 17:54    [20843158]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
aleks222
Guest
Шыфл
aleks222
Осподе, чему вас учили? Жертвы рекурсии.

Задача: 1) пройтись по нодам дерева, и если для какого-то узла все "низлежащие" ноды, без исключений, содержат скидку и эта скидка одинакова - удалить низлежащие ноды, 2) а скидку перененести на родителя.

эквивалентна

Задача: 1) удалить нод-лист (нод без потомков) дерева, если его вышележащий содержит ту же самую скидку.
2) для предков, у которого есть только нод-листы (ноды без потомков) и эти ноды содержат одинаковую скидку - перенести на предка скидку;

Решается двумя элементарными update в цикле "пока есть чего update - тать".


Гладко было на бумаге, да забыли про овраги...

Наши задачи не эквивалентны. Задачу 1 в формулировке
удалить нод, если его вышележащий содержит ту же самую скидку.

Это я уже решил, уже к третьему посту. Проблема в том, что для листов, у которых есть собственные скидки, прямой родитель может скидки не содержать. И тут мы плавно переходим к задаче 2
для предков, у которого есть только нод-листы (ноды без потомков) и эти ноды содержат одинаковую скидку - перенести на предка скидку
Все изменения должны быть эквивалентны. Если хотя бы у одного потомка скидки нет, нельзя ничего переносить на родителя, ибо тогда она появится там где её не было.

Вскрытие показало, что дерево дырявое донельзя, потому что сортимент меняется со временем и там, где скидки на листьях (продуктах), их редко добавляют вовремя. Только если клиент решил купить новинку и обнаружил отсуствие скидки, тогда он обращается к манагеру, который торгуется с ним о данной конкретной новинке. А если продукт не интересен покупателю, то у него образуется пробел в скидках, который там висит и никому не мешает, кроме, как выяснилось, меня.

Потому как если заполнить 5000 пустых нодов, можно схлопнуть всю таблицу в 3 раза.


Ты банальный пустозвон.
Чего тебе не понятно в упрощенном изложении элементарного алгоритма?
4 окт 17, 19:36    [20843384]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
aleks222
Guest
Для примеру, удаление листьев, имеющих скидку равную скидке родителя.
Без функций, рекурсии и прочего фуфла.
Обрабатывающее все разом.
declare @rc int = 1;

while @rc > 0 begin

    with d as ( select * from dbo.DiscountsTree )
       , t as ( select * from dbo.DiscountsTemplate )
         -- все листья, скидка в которых равна скидке родителя
       , l as ( select * from d 
                  where TreeLeft is null and TreeRight is null
                        and exists( select * from d as p 
                                                  inner join t as pt on pt.TreeId = p.TreeId 
                                                  inner join t as lt on lt.SalesDiscount = pt.SalesDiscount
                                       where pr.TreeId = l.TreeFatherId and lt.TreeId = l.TreeId
                                  )
              )
    delete l;
    set @rc = @@rowcount;

end;
4 окт 17, 19:58    [20843449]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
Руслан Дамирович
Member

Откуда: Резиновая нерезиновая
Сообщений: 425
aleks222
Для примеру, удаление листьев, имеющих скидку равную скидке родителя.
Без функций, рекурсии и прочего фуфла.
Обрабатывающее все разом.

Всем иногда нужен отдых. Тебе тоже надо отдохнуть. Задачу повторю капсом, чтобы воспринималось ЛУЧШЕ.

УБРАТЬ ВСЕ ДОЧЕРНИЕ НОДЫ, ЕСЛИ В ЭТИХ ДОЧЕРНИХ НОДАХ ТОЛЬКО ОДНО ЗНАЧЕНИЕ СКИДКИ. И ПОД ДОЧЕРНИМИ ЗДЕСЬ ПОНИМАЮТСЯ НЕ ПРЯМЫЕ ПОТОМКИ, А ВСЕ ПОТОМКИ (ДО АДАМОВА РЕБРА).

Осознай это, и поймешь, что твое упрощение - ошибочный подход.
5 окт 17, 10:26    [20844405]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
aleks222
Guest
Руслан Дамирович
aleks222
Для примеру, удаление листьев, имеющих скидку равную скидке родителя.
Без функций, рекурсии и прочего фуфла.
Обрабатывающее все разом.

Всем иногда нужен отдых. Тебе тоже надо отдохнуть. Задачу повторю капсом, чтобы воспринималось ЛУЧШЕ.

УБРАТЬ ВСЕ ДОЧЕРНИЕ НОДЫ, ЕСЛИ В ЭТИХ ДОЧЕРНИХ НОДАХ ТОЛЬКО ОДНО ЗНАЧЕНИЕ СКИДКИ. И ПОД ДОЧЕРНИМИ ЗДЕСЬ ПОНИМАЮТСЯ НЕ ПРЯМЫЕ ПОТОМКИ, А ВСЕ ПОТОМКИ (ДО АДАМОВА РЕБРА).

Осознай это, и поймешь, что твое упрощение - ошибочный подход.


Дурачка, никакой капс не исправит.

Зри на цикл while. Нема никакого смысла "удалять фсе разом", если можно порционно.
5 окт 17, 11:46    [20844774]     Ответить | Цитировать Сообщить модератору
 Re: Дерево и наследование  [new]
Дедушка
Member

Откуда: Город трёх революций
Сообщений: 4641
Шыфл
Вообще, изначальная задача была пройтись по всем скидкам и удалить такие, у которых собственное значение равно наследуемому (т.е. они не нужны, их удаление не изменит итоговую скидку).
Шыфл
Задача: пройтись по нодам дерева, и если для какого-то узла все "низлежащие" ноды, без исключений, содержат скидку и эта скидка одинакова - удалить низлежащие ноды, а скидку перененести на родителя.
у меня вот возник вопрос...
вполне допускаю, что ТС не рассказал всего контекста, но сначала мы самоотверженно курочим дерево, а затем начинаем извращаться с наследованием:
Шыфл
найти для произвольного узла значение скидки с учётом наследования (если есть прямое значение - то его, если нет - первое not null ближайшего узла вверх)
почему не оставить на каждом узле его значение и не брать его оттуда сразу без поиска по родителям\ наследникам?
5 окт 17, 12:38    [20845047]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить