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

Откуда:
Сообщений: 34
Имеется древовидная структура следующего вида

declare @tree_table (parent int, child int )
insert into @tree values(a1,a2)
insert into @tree values(a1,a3)
insert into @tree values(a1,a4)
insert into @tree values(a2,a5)
insert into @tree values(a2,a6)
insert into @tree values(a3,a7)
insert into @tree values(a5,a10)
insert into @tree values(a6,a11)
insert into @tree values(a4,a8)
insert into @tree values(a4,a9)
insert into @tree values(a8,a12)
insert into @tree values(a9,a13)
insert into @tree values(a9,a12)
insert into @tree values(a10,a14)
insert into @tree values(a10,a15)
insert into @tree values(a11,a16)
insert into @tree values(a11,a17)
insert into @tree values(a11,a18)
insert into @tree values(a12,a3)
insert into @tree values(a17,a15)
insert into @tree values(a18,a7)
insert into @tree values(a13,a19)
insert into @tree values(a14,a4)
insert into @tree values(a13,a4)

Задача вывести в столбик все уникальные значения для конкретной вершины. Т.е. для a1 - это все вершины
28 фев 19, 15:17    [21821853]     Ответить | Цитировать Сообщить модератору
 Re: Вывести уникальные вершины графа  [new]
Fotoview
Member

Откуда:
Сообщений: 34
продолжение....

а для a17 только a15.

Что-то подобное я нашел в этой теме: https://www.sql.ru/forum/135312/zhutkiy-zapros , но не пойму как скорректировать на уникальные значения.

Буду благодарен за помощь.

К сообщению приложен файл. Размер - 60Kb
28 фев 19, 15:20    [21821856]     Ответить | Цитировать Сообщить модератору
 Re: Вывести уникальные вершины графа  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20202
WITH cte AS ( SELECT child FROM table WHERE parent = @starting_node
              UNION ALL
              SELECT table.child FROM table, cte WHERE table.parent = cte.child )
SELECT child FROM cte

?
28 фев 19, 15:28    [21821871]     Ответить | Цитировать Сообщить модератору
 Re: Вывести уникальные вершины графа  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20202
PS. Возможно, достаточно и UNION DISTINCT.
PPS. Лихо Вы в INT присваиваете непонятно что...
28 фев 19, 15:30    [21821877]     Ответить | Цитировать Сообщить модератору
 Re: Вывести уникальные вершины графа  [new]
court
Member

Откуда:
Сообщений: 1956
Akina
WITH cte AS ( SELECT child FROM table WHERE parent = @starting_node
              UNION ALL
              SELECT table.child FROM table, cte WHERE table.parent = cte.child )
SELECT child FROM cte


?
на "пути" а4-а9-а13-а4 попадёт в бесконечную рекурсию

ТС же наврал про "древовидная структура" :)
(хотя в сабже, про граф, - сказал правду)
28 фев 19, 15:32    [21821882]     Ответить | Цитировать Сообщить модератору
 Re: Вывести уникальные вершины графа  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20202
court
на "пути" а4-а9-а13-а4 попадёт в бесконечную рекурсию
Не знаю, как именно к этому отнесётся MS SQL - а попробовать негде. Но UNION DISTINCT должен устранить эту проблему.
28 фев 19, 15:36    [21821886]     Ответить | Цитировать Сообщить модератору
 Re: Вывести уникальные вершины графа  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20202
Во всяком случае postgresql и mysql с UNION DISTINCT точно дадут верный результат.
28 фев 19, 15:37    [21821887]     Ответить | Цитировать Сообщить модератору
 Re: Вывести уникальные вершины графа  [new]
court
Member

Откуда:
Сообщений: 1956
Это будут уникальные пути
Если убрать "*" и расскоментировать "/* distinct node */" - будут вершины достижимые из заданной

declare @tree table (parent varchar(5), child varchar(5))
insert into @tree values('a1','a2')
insert into @tree values('a1','a3')
insert into @tree values('a1','a4')
insert into @tree values('a2','a5')
insert into @tree values('a2','a6')
insert into @tree values('a3','a7')
insert into @tree values('a5','a10')
insert into @tree values('a6','a11')
insert into @tree values('a4','a8')
insert into @tree values('a4','a9')
insert into @tree values('a8','a12')
insert into @tree values('a9','a13')
insert into @tree values('a9','a12')
insert into @tree values('a10','a14')
insert into @tree values('a10','a15')
insert into @tree values('a11','a16')
insert into @tree values('a11','a17')
insert into @tree values('a11','a18')
insert into @tree values('a12','a3')
insert into @tree values('a17','a15')
insert into @tree values('a18','a7')
insert into @tree values('a13','a19')
insert into @tree values('a14','a4')
insert into @tree values('a13','a4')

declare @a varchar(5)='a1'

;with cte as (
	select 
		node	=child
		,[path]	=cast('/'+child+'/' as varchar(max))
	from @tree 
	where parent=@a

	union all

	select 
		node	=t.child
		,[path]	=cast(cte.[path]+t.child+'/' as varchar(max))
	from @tree t inner join cte on t.parent=cte.node
	where cte.[path] not like '%/'+t.child+'/%'
)

select 
	* 
	/* distinct node */
from cte  
order by 1


nodepath
a10/a2/a5/a10/
a11/a2/a6/a11/
a12/a4/a8/a12/
a12/a4/a9/a12/
a12/a2/a5/a10/a14/a4/a9/a12/
a12/a2/a5/a10/a14/a4/a8/a12/
a13/a2/a5/a10/a14/a4/a9/a13/
a13/a4/a9/a13/
a14/a2/a5/a10/a14/
a15/a2/a5/a10/a15/
a15/a2/a6/a11/a17/a15/
a16/a2/a6/a11/a16/
a17/a2/a6/a11/a17/
a18/a2/a6/a11/a18/
a19/a4/a9/a13/a19/
a19/a2/a5/a10/a14/a4/a9/a13/a19/
a2/a2/
a3/a3/
a3/a4/a9/a12/a3/
a3/a4/a8/a12/a3/
a3/a2/a5/a10/a14/a4/a8/a12/a3/
a3/a2/a5/a10/a14/a4/a9/a12/a3/
a4/a2/a5/a10/a14/a4/
a4/a4/
a5/a2/a5/
a6/a2/a6/
a7/a2/a5/a10/a14/a4/a9/a12/a3/a7/
a7/a2/a5/a10/a14/a4/a8/a12/a3/a7/
a7/a4/a9/a12/a3/a7/
a7/a4/a8/a12/a3/a7/
a7/a3/a7/
a7/a2/a6/a11/a18/a7/
a8/a4/a8/
a8/a2/a5/a10/a14/a4/a8/
a9/a2/a5/a10/a14/a4/a9/
a9/a4/a9/
28 фев 19, 15:37    [21821889]     Ответить | Цитировать Сообщить модератору
 Re: Вывести уникальные вершины графа  [new]
Fotoview
Member

Откуда:
Сообщений: 34
Akina,

Огромное спасибо.

С int перегнул конечно )
28 фев 19, 16:45    [21821965]     Ответить | Цитировать Сообщить модератору
 Re: Вывести уникальные вершины графа  [new]
Fotoview
Member

Откуда:
Сообщений: 34
court
Akina
WITH cte AS ( SELECT child FROM table WHERE parent = @starting_node
              UNION ALL
              SELECT table.child FROM table, cte WHERE table.parent = cte.child )
SELECT child FROM cte


?
на "пути" а4-а9-а13-а4 попадёт в бесконечную рекурсию

ТС же наврал про "древовидная структура" :)
(хотя в сабже, про граф, - сказал правду)


Пробую по результатам отпишусь.
28 фев 19, 16:46    [21821968]     Ответить | Цитировать Сообщить модератору
 Re: Вывести уникальные вершины графа  [new]
Fotoview
Member

Откуда:
Сообщений: 34
court,

Огромное спасибо!!!!
28 фев 19, 16:48    [21821972]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить