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

Откуда:
Сообщений: 416
Есть классическое дерево, из которого на лету формируются родственные "пути" от корня до листа дерева. Формируется это все в рекурсии, соответственно порождается много лишних(промежуточных) данных. Вопрос в том, как лучше из этого итогового набора выбрать только конечные результаты, без промежуточных?

Скрипт подготовки данных:
create	table #Tree(ID int not null, ParentID int null)
insert	into #Tree
		values(1, null)
		,(2,1)
		,(3,2)
		,(4,3)
		,(5,2)

Необходимо получить:
5 |2 |1.2.5
4 |3 |1.2.3.4


И скрипт, выдающий правильный результат:
;with CTERec(ID, ParentID, IDPath, IsLast) as(
	select	T.ID
			,T.ParentID
			,IDPath = cast(T.ID as varchar(max))
			,IsLast = 0
	from	#Tree T
	where	T.ParentID is null
	union all
	select	T.ID
			,T.ParentID
			,IDPath = CR.IDPath + '.' + cast(T.ID as varchar(max))
			,IsLast = case when exists(	select	1
										from	#Tree TS
										where	TS.ParentID = T.ID) then 0
					else 1 end
	from	#Tree T
			join CTERec CR on CR.ID = T.ParentID
)
select	* 
from CTERec
where	IsLast = 1


Едиснтвенное решение, которое я нашел, это в Recursion-части CTE заглядывать в следующую итерацию и смотреть, будет ли надйен следующий node. Может у кого ест ьмысли, как решение сделать более лаконичным ?

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

P.S. воспользоваться order by по level + with ties вроде как не получится, т.к. у разных путей могут быть разные уровни.

Версия:
Microsoft SQL Server 2008 (RTM) - 10.0.1600.22 (Intel X86)   Jul  9 2008 14:43:34   Copyright (c) 1988-2008 Microsoft Corporation  Enterprise Edition on Windows NT 6.1 <X86> (Build 7600: ) (VM) 
3 мар 13, 17:26    [14005601]     Ответить | Цитировать Сообщить модератору
 Re: Формирование "Путей" от корня до листа из дерева.  [new]
qwerty112
Guest
Exproment
Необходимо получить:
5 |2 |1.2.5
4 |3 |1.2.3.4

тебе, всего навсего, нужно оставить в выборке, только ноды без чайлдов
3 мар 13, 17:42    [14005626]     Ответить | Цитировать Сообщить модератору
 Re: Формирование "Путей" от корня до листа из дерева.  [new]
qwerty112
Guest
qwerty112
Exproment
Необходимо получить:
5 |2 |1.2.5
4 |3 |1.2.3.4

тебе, всего навсего, нужно оставить в выборке, только ноды без чайлдов

;with CTERec(ID, ParentID, IDPath) as(
	select	T.ID
			,T.ParentID
			,IDPath = cast(T.ID as varchar(max))
	from	#Tree T
	where	T.ParentID is null
	union all
	select	T.ID
			,T.ParentID
			,IDPath = CR.IDPath + '.' + cast(T.ID as varchar(max))
	from	#Tree T
			join CTERec CR on CR.ID = T.ParentID
)
select	a.* 
from CTERec a
left join #Tree b
	on a.ID=b.ParentID
where b.ID is null
3 мар 13, 17:45    [14005629]     Ответить | Цитировать Сообщить модератору
 Re: Формирование "Путей" от корня до листа из дерева.  [new]
Exproment
Member

Откуда:
Сообщений: 416
qwerty112, дааа... эдак затупил так затупил ))) Спасибо :) несколько дней повсеместно думал в направлении групп и hierarchyid :)
3 мар 13, 18:00    [14005641]     Ответить | Цитировать Сообщить модератору
 Re: Формирование "Путей" от корня до листа из дерева.  [new]
Cygapb-007
Member

Откуда:
Сообщений: 1677
а это правильно, что 6 7 8 и 9 не попадают в выборку?
;with 
Tree as(
   select * from (values(1, null),(2,1),(3,2),(4,3),(5,2),(7,6),(8,7),(9,6))t(ID,ParentID)
   ),
CTERec(ID, ParentID, IDPath) as(
   selecе T.ID,T.ParentID,IDPath = cast(T.ID as varchar(max)) 
     from Tree T where	T.ParentID is null
   union all
   select T.ID,T.ParentID,IDPath = CR.IDPath + '.' + cast(T.ID as varchar(max))
      from Tree T
      join CTERec CR on CR.ID = T.ParentID
)
select	* 
from CTERec a
left join Tree b on a.ID=b.ParentID
where b.ID is null
(просто спросил)
3 мар 13, 19:17    [14005791]     Ответить | Цитировать Сообщить модератору
 Re: Формирование "Путей" от корня до листа из дерева.  [new]
Exproment
Member

Откуда:
Сообщений: 416
Cygapb-007, эммм.. а как вы себе представляете дерево, в котором parentid ссылается на несуществующую вершину ? :) Такие попытки должны быть пресечены на уровне процедур или констреинтов )
3 мар 13, 20:15    [14005915]     Ответить | Цитировать Сообщить модератору
 Re: Формирование "Путей" от корня до листа из дерева.  [new]
Cygapb-007
Member

Откуда:
Сообщений: 1677
Exproment
Cygapb-007, эммм.. а как вы себе представляете дерево, в котором parentid ссылается на несуществующую вершину ? :) Такие попытки должны быть пресечены на уровне процедур или констреинтов )
Шматрица
Вот ты её не видишь, а она есть!
4 мар 13, 01:11    [14006585]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить