Ленивый рекурсивный запрос вверх в sql

Question

Я пытаюсь сгенерировать путь из имени родителей элемента. Например, если test имеет для родителя dad , путь будет dad / test ;и если бы папа имел для родителя гран путь test был бы gran / dad / test .

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

WITH    SubItems
AS (
    SELECT  CAST([Name] AS VARCHAR(255)) AS [Path],
        Id,
        ParentId,
        0 AS Depth
    FROM    Items
    WHERE   Id = 1 -- First parent of everyone
    UNION ALL
    SELECT  CAST(CONCAT(parent.[Path], '/', sub.[Name]) AS VARCHAR(255)),
        sub.Id,
        sub.ParentId,
        parent.Depth + 1
    FROM    Items sub
        JOIN SubItems parent ON parent.Id = sub.ParentId
)
SELECT      [Path]
FROM        SubItems
WHERE       Id = 1425 -- SubItem I want the path of

Я также могу пойтивверх, что было бы быстрее, но я не могу создать путь таким образом. Я мог бы попытаться объединить все результаты, упорядоченные по «глубине», но опять-таки это кажется неправильным.

DECLARE @Path;
WITH    ParentItems
AS (
    SELECT  [Name],
        Id,
        ParentId,
        0 AS Depth
    FROM    Items
    WHERE   Id = 1425 -- SubItem I want the path of
    UNION ALL
    SELECT  [Name],
        parent.Id,
        parent.ParentId,
        sub.Depth - 1
    FROM    Items parent
        JOIN  ParentItems sub ON sub.ParentId = parent.Id
)
SELECT      @Path = COALESCE(@Path + '/', '') + [Name]
FROM        ParentItems
ORDER BY    Depth;
SELECT @Path;

Есть ли способ рекурсивно идти вверх? Что-то вроде этогонапример, где ParentPath снова будет равно CONCAT(ParentPath, '/', [Path]):

WITH   ...
SELECT CONCAT(ParentPath, '/', [Name])
FROM   Items

Я знаю, в C # вы можете сделать что-то вроде:

function getPath() {
  return (parent?.getPath() ?? "") + "/" + this.Name;
}

---

Редактировать: Почему я не могу построить путь, идущий вверх, например:

WITH ParentItems AS (
      SELECT i.Name, i.Id, i.ParentId, 0 AS Depth,
             CONVERT(VARCHAR(MAX), i.Name) as path
      FROM Items i
      WHERE i.Id = 1425 -- SubItem I want the path of
      UNION ALL
      SELECT i.Name, i.Id, i.ParentId, pi.Depth - 1,
             CONCAT(pi.Name, '/', i.[Path])
      FROM Items i JOIN
           ParentItems pi
           ON pi.ParentId = parent.Id
     )
SELECT *
FROM ParentItems
ORDER BY Depth;

Принимая пример сверху, где gran является родительским для папа является родительским для test , результат этого запроса будет:

| name | path          |
|------|---------------|
| gran | gran/dad/test |
| dad  | dad/test      |
| test | test          |

Хотя должно быть наоборот:

| name | path          |
|------|---------------|
| gran | gran/         |
| dad  | gran/dad      |
| test | gran/dad/test |

Это из-заспособ, которым запрос передает имя потомка вверх, добавляя его к пути его родителя, а не наоборот.

Answer 1

Для будущих ссылок использование FOR XML PATH(''), кажется, работает.

WITH    ParentItems
AS (
    SELECT  [Name],
        Id,
        ParentId,
        0 AS Depth
    FROM    Items
    WHERE   Id = 1425 -- SubItem I want the path of
    UNION ALL
    SELECT  [Name],
        parent.Id,
        parent.ParentId,
        sub.Depth - 1
    FROM    Items parent
        JOIN  ParentItems sub ON sub.ParentId = parent.Id
)
SELECT (
    SELECT '/' + [Name]
    FROM ParentItems
    ORDER BY Depth
    FOR XML PATH('')
)

Answer 2

Следующий код:

1. Ходит по дереву от ребенка до самого старого предка при сборке пути.
2. Получает путь к самому старому предку и разбивает его на отдельных лиц.
3. Просматривает список лиц от самого старого предка до начального потомка при сборке пути.

NB : этот код не использует String_Split, поскольку это задокументировано следующим образом: «Выходные строки могут быть в любом порядке. Порядок не гарантированно совпадает с порядком подстрок во входной строке». A Используется разделитель строк Джеффа Модена , который гарантирует порядок результатов.

Обратите внимание, что вы можете выбрать результаты любого из промежуточных CTE, чтобы увидеть, как протекает процесс. Просто замените окончательный оператор select одной из альтернатив, представленных в комментариях.

Исповедь: я не пытался сгенерировать любопытный свисающий солидус в первой строке желаемого результата ("gran /")а не более последовательный «гран». Предполагается, что это типографская ошибка в данных выборки.

-- Sample data.
declare @Samples as Table ( Id Int Identity, Name VarChar(10), ParentName VarChar(10) );
insert into @Samples ( Name, ParentName ) values
  ( 'test', 'dad' ),
  ( 'dad', 'gran' ),
  ( 'gran', null );
select * from @Samples;

-- Starting point.
declare @ChildName as VarChar(10) = 'test';

-- Walk the tree.
with
  Tree as (
    -- Note that paths in this initial tree are built using   Id , not   Name .
    --   This keeps the path length down, ensures rows are uniquely identified, avoids problems with "funny" names, ... .
    -- Start at the target child name.
    select Id, Name, ParentName, 0 as Depth,
      Cast( Id as VarChar(100) ) as Path
      from @Samples
      where Name = @ChildName
    union all
    -- Walk up the tree one level at a time.
    select S.Id, S.Name, S.ParentName, T.Depth + 1,
      Cast( Cast( S.Id as VarChar(100) ) + '/' + T.Path as VarChar(100) )
      from Tree as T inner join
        @Samples as S on S.Name = T.ParentName
    ),
  TreePath as (
    -- Take the path of the oldest ancestor and split it apart.
    select ItemNumber, Cast( Item as Int ) as Item from Tree as T cross apply
      dbo.DelimitedSplit8K( T.Path, '/' ) where T.ParentName is NULL ),
  InvertedTree as (
    -- Start at the first item on path, i.e. the oldest ancestor.
    select S.Name, 1 as Depth,
      Cast( S.Name as VarChar(100) ) as Path
      from TreePath as TP inner join
        @Samples as S on S.Id = TP.Item
      where TP.ItemNumber = 1
    union all
    -- Add chldren on the way down.
    select S.Name, IT.Depth + 1,
      Cast( IT.Path + '/' + S.Name as VarChar(100) )
      from InvertedTree as IT inner join
        TreePath as TP on TP.ItemNumber = IT.Depth + 1 inner join
        @Samples as S on S.Id = TP.Item
      )
  -- To see the intermediate results use one of the following   select   statements:
  --  select * from Tree;
  --  select * from TreePath;
  --  select * from InvertedTree;
  select Name, Path
    from InvertedTree
    order by Depth;

Разветвитель строки Джеффа Модена :

CREATE FUNCTION [dbo].[DelimitedSplit8K]
--===== Define I/O parameters
        (@pString VARCHAR(8000), @pDelimiter VARCHAR(16))
--WARNING!!! DO NOT USE MAX DATA-TYPES HERE!  IT WILL KILL PERFORMANCE!
RETURNS TABLE WITH SCHEMABINDING AS
 RETURN
--===== "Inline" CTE Driven "Tally Table" produces values from 1 up to 10,000...
     -- enough to cover VARCHAR(8000)
  WITH E1(N) AS (
                 SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
                 SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
                 SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1
                ),                          --10E+1 or 10 rows
       E2(N) AS (SELECT 1 FROM E1 a, E1 b), --10E+2 or 100 rows
       E4(N) AS (SELECT 1 FROM E2 a, E2 b), --10E+4 or 10,000 rows max
 cteTally(N) AS (--==== This provides the "base" CTE and limits the number of rows right up front
                     -- for both a performance gain and prevention of accidental "overruns"
                 SELECT TOP (ISNULL(DATALENGTH(@pString),0)) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E4
                ),
cteStart(N1) AS (--==== This returns N+1 (starting position of each "element" just once for each delimiter)
                 SELECT 1 UNION ALL
                 SELECT t.N+ Len( @pDelimiter ) FROM cteTally t WHERE SUBSTRING(@pString,t.N, Len( @pDelimiter ) ) = @pDelimiter
                ),
cteLen(N1,L1) AS(--==== Return start and length (for use in substring)
                 SELECT s.N1,
                        ISNULL(NULLIF(CHARINDEX(@pDelimiter,@pString,s.N1),0)-s.N1 ,8000)
                   FROM cteStart s
                )
--===== Do the actual split. The ISNULL/NULLIF combo handles the length for the final element when no delimiter is found.
 SELECT ItemNumber = ROW_NUMBER() OVER(ORDER BY l.N1),
        Item       = SUBSTRING(@pString, l.N1, l.L1)
   FROM cteLen l
;

Answer 3

Почему вы не можете построить путь, идущий вверх?

WITH ParentItems AS (
      SELECT i.Name, i.Id, i.ParentId, 0 AS Depth,
             CONVERT(VARCHAR(MAX), i.Name) as path
      FROM Items i
      WHERE i.Id = 1425 -- SubItem I want the path of
      UNION ALL
      SELECT i.Name, i.Id, i.ParentId, pi.Depth + 1,
             CONCAT(i.Name, '/', pi.path)
      FROM Items i JOIN
           ParentItems pi
           ON pi.ParentId = parent.Id
     )
SELECT *
FROM ParentItems
ORDER BY Depth DESC;