Гость
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Найти последнего потомка. / 25 сообщений из 35, страница 1 из 2
26.03.2020, 17:02
    #39941453
Earl11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Здравствуйте. Нужно найти конечного потомка. Такая таблица допустим.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
CREATE TABLE table1(sess_id int, bl_sess_id int);
	
INSERT INTO table1
	([sess_id], [bl_sess_id])
VALUES
(78,394),(81,301),(100,379),(159,271),(195,288),
(202,334),(204,301),(215,389),(217,357),(269,301),
(271,502),(280,334),(301,271),(318,195),(323,301),(326,357),(334,204),(343,02),
(346,195),(349,542),(350,0),(357,301),
(365,404),(366,100),(372,404),(373,301),(374,301),(375,0),(379,334),(381,202),
(389,269),(394,357),(399,349),(403,349),
(404,560),(411,487),(426,373),(428,373),(432,487),(442,0),(453,301),
(457,204),(466,349),(470,366),(474,426),(481,301),(487,564),(491,349),(497,301),(502,271);


Пойдём с первого. 78-394-357-301-271-502-271. Нужен, по сути, 502.
Как-нибудь без рекурсии обойтись можно?
...
Рейтинг: 0 / 0
26.03.2020, 17:09
    #39941455
a_voronin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Earl11,

А чем рекурсия плоха?

https://www.sql.ru/forum/1322566/rekursiya-s-dublyami
...
Рейтинг: 0 / 0
26.03.2020, 17:24
    #39941461
Earl11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
a_voronin,
по заданию желательно сделать без неё. Да и не особо понимаю как)
...
Рейтинг: 0 / 0
26.03.2020, 17:32
    #39941464
invm
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Earl11
Как-нибудь без рекурсии обойтись можно?
Можно. Любая рекурсия заменяется циклом.
...
Рейтинг: 0 / 0
26.03.2020, 17:38
    #39941468
a_voronin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Earl11,

Курсоры вам в руки.
...
Рейтинг: 0 / 0
26.03.2020, 18:18
    #39941483
Earl11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Это, например, как реализовать?
...
Рейтинг: 0 / 0
27.03.2020, 13:58
    #39941656
Earl11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Никто не подскажет?
...
Рейтинг: 0 / 0
27.03.2020, 16:59
    #39941725
alexeyvg
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
a_voronin
Курсоры вам в руки.
Не, курсор тут ни к чему не прилепить, тут нужен просто цикл.
Earl11
Никто не подскажет?
Что, как пишутся циклы?

Это же азы программирования.
Возьмите учебник по программированию на T-SQL, и проходите главу за главой, там циклы будут рассмотрены.
Хотя, циклы есть в любом курсе программирования начального уровня.
...
Рейтинг: 0 / 0
27.03.2020, 17:48
    #39941749
Earl11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
alexeyvg, так вопрос в чём: идёт цепочка допустим 78-394-357-301 и выходит такой момент 271-502-271-271-502-271 и дальше всё вокруг двух значений. И каждый раз проверять текущее значение с -2 значением?
...
Рейтинг: 0 / 0
27.03.2020, 22:54
    #39941799
alexeyvg
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Earl11
alexeyvg, так вопрос в чём: идёт цепочка допустим 78-394-357-301 и выходит такой момент 271-502-271-271-502-271 и дальше всё вокруг двух значений. И каждый раз проверять текущее значение с -2 значением?
А для исключения зацикливания придётся цепочку хранить во временной табличке (в каждой итерации цикла добавлять туда найденный элемент)

И условием выхода из цикла должно быть не только отсутствие нового элемента, но и присутствия найденного
элемента в этой временной табличке.
...
Рейтинг: 0 / 0
29.03.2020, 17:55
    #39942048
Earl11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Иного решения нет, как понимаю?
...
Рейтинг: 0 / 0
29.03.2020, 18:05
    #39942051
a_voronin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Earl11,

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

Защита от зацикливания делается аналогично не зависимо от того, какой способ обхода дерева используется.
...
Рейтинг: 0 / 0
29.03.2020, 18:07
    #39942052
mikron
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
У потомка нет потомков.

Код: sql
1.
select distinct sess_id from table1 minus select bl_sess_id from table1;
...
Рейтинг: 0 / 0
29.03.2020, 18:12
    #39942053
a_voronin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Earl11
Иного решения нет, как понимаю?


Код: 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.
47.
48.
49.
50.
51.
52.
IF OBJECT_ID('tempdb..#T') IS NOT NULL 
DROP TABLE #T;

WITH A AS 
(	
	SELECT RN = ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM master..spt_values
), B AS 
(
	SELECT RN = ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) 
	FROM A A1, A A2
)


SELECT PARENT, CHILD
INTO #T 
FROM 
(
	SELECT 
		PARENT, CHILD
	FROM 
	(
		SELECT DISTINCT 
			--RN, RN % 9 + 1 AS PARENT, RN % 11 + 1 AS CHILD -- много вариантов 
			--RN, RN % 7 + 1 AS PARENT, RN % 9 + 1 AS CHILD -- средне вариантов 
			RN % 5 + 1 AS PARENT, RN % 7 + 1 AS CHILD -- мало вариантов 
		FROM B
	) C
	WHERE CHILD <> PARENT
) D
GROUP BY PARENT, CHILD
;

WITH T AS 
(
	SELECT 
		PARENT AS Start, 
		PARENT AS Parent, 
		CHILD AS Child, 
		CHAIN = CAST(CONCAT('-', PARENT, '-', CHILD, '-') AS VARCHAR(1024))
	FROM #T S0
	UNION ALL 
	SELECT 
		S1.Start, 
		S2.PARENT AS Parent, 
		S2.CHILD AS Child, 
		CHAIN = CAST(CONCAT(S1.CHAIN, S2.CHILD, '-') AS VARCHAR(1024)) 
	FROM T S1
	INNER JOIN #T S2 ON S1.Child = S2.PARENT
	WHERE CHARINDEX(CONCAT('-', S2.CHILD, '-'), S1.CHAIN) = 0
)
SELECT TOP 100000 t.* FROM T t
ORDER BY Start, Parent, Child



Вот это защита от зацикливания
Код: sql
1.
2.
3.
	CHAIN = CAST(CONCAT('-', PARENT, '-', CHILD, '-') AS VARCHAR(1024))
	CHAIN = CAST(CONCAT(S1.CHAIN, S2.CHILD, '-') AS VARCHAR(1024)) 
	WHERE CHARINDEX(CONCAT('-', S2.CHILD, '-'), S1.CHAIN) = 0
...
Рейтинг: 0 / 0
29.03.2020, 20:08
    #39942074
alexeyvg
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Earl11
Иного решения нет, как понимаю?
Если нужно использовать только цикл, то решение только такое.

Если рекурсивный CTE, то решение дал a_voronin.
mikron
У потомка нет потомков.

Код: sql
1.
select distinct sess_id from table1 minus select bl_sess_id from table1;

А у него в последнем элементе есть потомок :-)
...
Рейтинг: 0 / 0
29.03.2020, 21:40
    #39942097
Earl11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
a_voronin

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

Простой путь - это какой путь? Пусть рекурсия. Условие как прописать?
Взять Ваш ответ
Код: sql
1.
WHERE CHARINDEX(CONCAT('-', S2.CHILD, '-'), S1.CHAIN) = 0


как будет обнаружен ноль, если цепочка повторяется?..Прошу прощения, но я немного не понимаю.
...
Рейтинг: 0 / 0
29.03.2020, 23:14
    #39942114
alexeyvg
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Earl11
a_voronin

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

Простой путь - это какой путь?
Простой - это CTE. Нативный путь для MSSQL, при решении такой задачи.
Earl11
Пусть рекурсия. Условие как прописать?
Взять Ваш ответ
Код: sql
1.
WHERE CHARINDEX(CONCAT('-', S2.CHILD, '-'), S1.CHAIN) = 0


как будет обнаружен ноль, если цепочка повторяется?..Прошу прощения, но я немного не понимаю.
Вы бы взяли этот запрос, посмотрели, что он выводит, что будет в поле S1.CHAIN, что находится в поле S2.CHILD, и тогда станет понятно, что означает CHARINDEX(CONCAT('-', S2.CHILD, '-'), S1.CHAIN).

Earl11
как будет обнаружен ноль
Ещё меня эта фраза смутила.
Вы имеете в виду CHARINDEX(...)=0?
Вы смотрели, что эта за функция CHARINDEX ,и когда она возвращает 0?
...
Рейтинг: 0 / 0
30.03.2020, 04:23
    #39942129
nullin
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
a_voronin, а где же битовые маски?
...
Рейтинг: 0 / 0
30.03.2020, 08:11
    #39942135
a_voronin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
nullin,

А что битовые маски? В реальной задаче, а не этом прототипе -- числа до 1000000 -- вы какого размера маски предлагаете таскать, а если вообще строки произвольные.
...
Рейтинг: 0 / 0
30.03.2020, 13:38
    #39942234
nullin
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
a_voronin, ну если так, то в binary(max) вылазит; если строки произвольные, то ещё нумеровать придётся. Для них максимальный объём ~134кк(256мб если unsigned) - про скорость я конечно говорить не буду, но если связываться с рекурсией в текущей реализации, то это вообще не про бытродействие :)
В запросе ТС не нужно цепь выводить, а только скаляр, поэтому именно здесь применение масок очень оправдано.
...
Рейтинг: 0 / 0
30.03.2020, 14:15
    #39942242
nullin
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Нужно только еще сделать fnMatchBit(), чтобы вместо CHARINDEX(...)=0 было
[бит из binary по адресу байта добавляемого номера] & [бит этого номера] = 0. Вместо concat() где формируется цепочка, соответственно fnSetBit()
...
Рейтинг: 0 / 0
30.03.2020, 14:35
    #39942251
Earl11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
alexeyvg, просто нужен был конечный элемент, а получаю несколько цепочек. Ладно)
Спасибо большое Вам и a_voronin
...
Рейтинг: 0 / 0
30.03.2020, 14:38
    #39942253
alexeyvg
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Earl11
alexeyvg, просто нужен был конечный элемент, а получаю несколько цепочек. Ладно)
Ну да, запрос получает дерево.
Нужно к нему добавить TOP 1, с сортировкой CHAIN DESC
...
Рейтинг: 0 / 0
30.03.2020, 15:35
    #39942278
aleks222
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
Earl11
Здравствуйте. Нужно найти конечного потомка. Такая таблица допустим.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
CREATE TABLE table1(sess_id int, bl_sess_id int);
	
INSERT INTO table1
	([sess_id], [bl_sess_id])
VALUES
(78,394),(81,301),(100,379),(159,271),(195,288),
(202,334),(204,301),(215,389),(217,357),(269,301),
(271,502),(280,334),(301,271),(318,195),(323,301),(326,357),(334,204),(343,02),
(346,195),(349,542),(350,0),(357,301),
(365,404),(366,100),(372,404),(373,301),(374,301),(375,0),(379,334),(381,202),
(389,269),(394,357),(399,349),(403,349),
(404,560),(411,487),(426,373),(428,373),(432,487),(442,0),(453,301),
(457,204),(466,349),(470,366),(474,426),(481,301),(487,564),(491,349),(497,301),(502,271);


Пойдём с первого. 78-394-357-301-271-502-271. Нужен, по сути, 502.
Как-нибудь без рекурсии обойтись можно?


Ну, если отбросить вопрос: "пачиму конечный потомок 502, а не 271?"

То рекурсия не нужна от слова совсем.
"Конечный потомок" = "элемент у которого нет потомков".
Это делается в один тривиальный запрос.
...
Рейтинг: 0 / 0
30.03.2020, 19:19
    #39942335
Earl11
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти последнего потомка.
aleks222

Это делается в один тривиальный запрос.

Какой?)
alexeyvg
Нужно к нему добавить TOP 1, с сортировкой CHAIN DESC

В конечный SELECT? или тот, что в рекурсии?
...
Рейтинг: 0 / 0
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Найти последнего потомка. / 25 сообщений из 35, страница 1 из 2
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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