Рекурсивный sql - найти дедушку и бабушку ребенка

У меня есть таблица, как показано ниже:

Id ParentID 1 99 2 9 3 1 4 2 5 4 6 3

и я хотел бы иметь запрос, который дает мне для каждого ребенка последнего предка.

Я имею в виду, что желаемый результат

id Lastancestor 1 99 2 9 3 99 4 9 5 9 6 99

У меня много данных, поэтому мне нужно что-то быстрое.

Спасибо.


sql sql-server tsql recursive-query ancestor
person Xristos Epitropakis    schedule 09.09.2015    source источник
comment
Вам нужно Рекурсивное общее табличное выражение   -  person Magnus    schedule 09.09.2015
comment
и пример из отличной справки в SO: stackoverflow.com/questions/22909692/   -  person xQbert    schedule 09.09.2015
comment
Есть ли максимальная глубина?   -  person Shnugo    schedule 09.09.2015
comment
99? У вас есть план обращения с божествами или вы просто используете магическое число для их (единственного) родителя? Как насчет NULL? Или ноль? Или, чтобы было сложно, свои собственные Id? Проводили ли вы какие-либо исследования или пытались решить вашу проблему? Идея здесь в том, что люди помогают вам решать проблемы, но SO — это не служба написания кода.   -  person HABO    schedule 10.09.2015
comment
@Xristos Epitropakis Вам нужно будет изменить свои данные (и я понимаю, что вы, вероятно, не можете этого сделать), но тип данных HIERARCHYID в T-SQL предназначен для такого рода вещей. Прочитайте это, если вам интересно msdn.microsoft.com/en-us/ библиотека/bb677213.aspx   -  person Paul Spain    schedule 10.09.2015

Ответы (2)


arrow_upward
2
arrow_downward

Вы можете использовать рекурсивное CTE для этого:

;WITH CTE AS (
  SELECT Id AS origId, ParentID, 0 AS lvl
  FROM mytable

  UNION ALL

  SELECT c.origId AS origId, 
         m.ParentID, lvl = lvl + 1
  FROM CTE AS c
  INNER JOIN mytable AS m ON c.ParentID = m.Id
)
SELECT origId AS id, ParentID AS Lastancestor
FROM (
  SELECT origId, ParentID,
         ROW_NUMBER() OVER (PARTITION BY origId 
                            ORDER BY lvl DESC) AS rn
  FROM CTE) AS t
WHERE t.rn = 1

Здесь элемент привязки CTE — это просто вся таблица. Рекурсия идет вверх по иерархии дерева, распространяя исходный Id (как origId) вниз по цепочке рекурсии. Рекурсия завершается, как только возвращается пустой набор, т. е. как только не найдено больше c.ParentID = m.Id совпадений.

Чтобы получить требуемый результат, то есть Lastancestor на id, все, что нам нужно сделать, это выбрать запись, имеющую наибольшее lvl (т.е. глубину) на id. Это достигается с помощью оконной функции ROW_NUMBER.

Демо здесь

person Giorgos Betsos    schedule 09.09.2015
comment
Очень красивое решение! +1 с моей стороны - person Shnugo; 10.09.2015
comment
Один вопрос: использовали ли вы этот подход в реальной жизни? Я очень ценю это, но, как сказал ОП, данных много, и они должны быть быстрыми. Если CTE заполнен большой таблицей, эта рекурсия приведет к много-много полных просмотров таблицы. Сомневаюсь, что используется индекс... Каков ваш опыт в этом? В любом случае, мне это нравится, и я должен сделать несколько тестов... - person Shnugo; 10.09.2015
comment
@Shnugo Это предпочтительный подход к запросам иерархических структур данных в SQL Server. Единственная другая альтернатива AFAIK — использование курсора, который менее эффективен. Однако я никогда не использовал рекурсивные CTE в реальной жизни. ОП может сообщить нам о том, как он работает с его фактическими данными. - person Giorgos Betsos; 10.09.2015

arrow_upward
0
arrow_downward

Если есть максимальная глубина, вы можете использовать этот подход. Вы можете добавить дополнительные уровни глубины с помощью простого копирования, вставки и адаптации. Я добавил один элемент данных «19,6», чтобы сгенерировать один с тремя предками и один с четырьмя.

Просто вставьте это в пустое окно запроса и выполните. Адаптируйтесь к вашим потребностям...

declare @Test table (Id int, ParentID int)

insert into @Test values
(1,99)
,(2,9)
,(3,1)
,(4,2)
,(5,4)
,(6,3)
,(19,6);


WITH Ancestors1 AS
(
    SELECT Test.*
          ,Ancestor.ParentID AS Anc1ID 
    FROM @Test AS Test
    LEFT JOIN @Test AS Ancestor ON Test.ParentID=Ancestor.Id
)
,Ancestors2 AS
(
    SELECT Ancestors1.*
          , Ancestor.ParentID AS Anc2ID 
    FROM Ancestors1
    LEFT JOIN @Test AS Ancestor ON Ancestors1.Anc1ID=Ancestor.Id
)
,Ancestors3 AS
(
    SELECT Ancestors2.*
          , Ancestor.ParentID AS Anc3ID 
    FROM Ancestors2
    LEFT JOIN @Test AS Ancestor ON Ancestors2.Anc2ID=Ancestor.Id
)
SELECT Id,*
      ,COALESCE(Anc3ID,Anc2ID,Anc1ID,ParentID)  AS LastAncId
FROM Ancestors3
person Shnugo    schedule 09.09.2015