powered by simpleCommunicator - 2.0.53     © 2025 Programmizd 02
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Найти последнего потомка.
25 сообщений из 35, страница 1 из 2
Найти последнего потомка.
    #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
Найти последнего потомка.
    #39941455
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Earl11,

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

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

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

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

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

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

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

Код: sql
1.
select distinct sess_id from table1 minus select bl_sess_id from table1;
...
Рейтинг: 0 / 0
Найти последнего потомка.
    #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
Найти последнего потомка.
    #39942074
Фотография alexeyvg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Earl11
Иного решения нет, как понимаю?
Если нужно использовать только цикл, то решение только такое.

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

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

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

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

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


как будет обнаружен ноль, если цепочка повторяется?..Прошу прощения, но я немного не понимаю.
...
Рейтинг: 0 / 0
Найти последнего потомка.
    #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
Найти последнего потомка.
    #39942129
nullin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
a_voronin, а где же битовые маски?
...
Рейтинг: 0 / 0
Найти последнего потомка.
    #39942135
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
nullin,

А что битовые маски? В реальной задаче, а не этом прототипе -- числа до 1000000 -- вы какого размера маски предлагаете таскать, а если вообще строки произвольные.
...
Рейтинг: 0 / 0
Найти последнего потомка.
    #39942234
nullin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
a_voronin, ну если так, то в binary(max) вылазит; если строки произвольные, то ещё нумеровать придётся. Для них максимальный объём ~134кк(256мб если unsigned) - про скорость я конечно говорить не буду, но если связываться с рекурсией в текущей реализации, то это вообще не про бытродействие :)
В запросе ТС не нужно цепь выводить, а только скаляр, поэтому именно здесь применение масок очень оправдано.
...
Рейтинг: 0 / 0
Найти последнего потомка.
    #39942242
nullin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Нужно только еще сделать fnMatchBit(), чтобы вместо CHARINDEX(...)=0 было
[бит из binary по адресу байта добавляемого номера] & [бит этого номера] = 0. Вместо concat() где формируется цепочка, соответственно fnSetBit()
...
Рейтинг: 0 / 0
Найти последнего потомка.
    #39942251
Earl11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
alexeyvg, просто нужен был конечный элемент, а получаю несколько цепочек. Ладно)
Спасибо большое Вам и a_voronin
...
Рейтинг: 0 / 0
Найти последнего потомка.
    #39942253
Фотография alexeyvg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Earl11
alexeyvg, просто нужен был конечный элемент, а получаю несколько цепочек. Ладно)
Ну да, запрос получает дерево.
Нужно к нему добавить TOP 1, с сортировкой CHAIN DESC
...
Рейтинг: 0 / 0
Найти последнего потомка.
    #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
Найти последнего потомка.
    #39942335
Earl11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
aleks222

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

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

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


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