SQL Рекурсивный CTE Замена записей в каждой рекурсии

Question

У меня есть такая таблица:

ItemID  ItemFormula
100     'ID_3+ID_5'
110     'ID_2+ID_6'
120     'ID_100+ID_110'
130     'ID_120+ID_4'

Это упрощенная версия таблицы формул с почти 1000 записями и до 40 уровнями ссылок (элементы, используемые в других элементах). Задача состоит в том, чтобы разбить формулы на одну ссылку на уровень, где в одном элементе нет других элементов. Например, в приведенной выше таблице для id = 130 у меня должно быть '((ID_3 + ID_5) + (ID_2 + ID_6)) + ID_4'

РЕДАКТИРОВАТЬ: операции не ограничиваются "+", и элементы имеют характер между ними должен быть узнаваемым. Ради простоты я удалил этот символ.

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

Мой вопрос таков: могу ли я сохранять предыдущую рекурсию только каждый раз, когда рекурсия бывает?

Вот мой код CTE

WITH Formula
  AS  (SELECT A.ItemID
             ,'ID_' + CONVERT(VARCHAR(20), A.ItemID) AS ItemText
             ,CONVERT(VARCHAR(MAX), A.ItemFormula) AS ItemFormula 
       FROM (VALUES (100,'ID_3+ID_5'),
                    (110,'ID_2+ID_6'),
                    (120,'ID_100+ID_110'),
                    (130,'ID_120+ID_4')   
                ) A (ItemID,ItemFormula)

  )
    ,REC
  AS
      (
          SELECT A.ItemID
                ,A.ItemText
                ,A.ItemFormula
                ,1 AS LevelID
          FROM Formula A
          UNION ALL
          SELECT A.ItemID
                ,A.ItemText
                ,' '
                 + TRIM (REPLACE (REPLACE (A.ItemFormula, B.ItemText, ' ( ' + B.ItemFormula + ' ) '), '  ', ' '))
                 + ' ' AS ItemFormula
                ,A.LevelID + 1 AS LevelID
          FROM REC A
              CROSS APPLY
          (
              SELECT *
              FROM
              (
                  SELECT *
                        ,ROW_NUMBER () OVER (ORDER BY GETDATE ()) AS RowNum
                  FROM Formula B2
                  WHERE CHARINDEX (B2.ItemText, A.ItemFormula) > 0
              ) B3
              WHERE B3.RowNum = 1
          ) B
      )
    ,FinalQ
  AS
      (
          SELECT A2.ItemID
                ,A2.ItemFormula
                ,A2.LevelID
          FROM
          (
              SELECT A.ItemID
                    ,REPLACE (TRIM (A.ItemFormula), ' ', '') AS ItemFormula
                    ,A.LevelID
                    ,ROW_NUMBER () OVER (PARTITION BY A.ItemID ORDER BY A.LevelID DESC) AS RowNum
              FROM REC A
          ) A2
          WHERE A2.RowNum = 1
      )
SELECT * FROM FinalQ A2 ORDER BY A2.ItemID;

Заранее спасибо.

Answer 1

Это чрезвычайно сложная проблема. Вот идеи:

1. Найдите, какие элементы не нуждаются в вставках. Это те, которые не имеют ссылок ни на какие другие.
2. Построить заказ для вставки предметов. Вставка может go в элемент, предполагая, что элемент уже определен. Для этого можно использовать рекурсивный CTE.
3. Перечислить вставки. Все из (1) получает «1». Остальные в порядке.
4. Обработка вставок в порядке вставки.

Вот мое решение:

with ordering as (
      select itemid, itemtext, itemformula, convert(varchar(max), null) as otheritemtext, 1 as lev
      from formula f
      where not exists (select 1
                        from formula f2 join
                             string_split(f.itemformula, '+') s
                             on f2.itemtext = s.value
                        where f2.itemid <> f.itemid
                       )
       union all
       select f.itemid, f.itemtext, f.itemformula, convert(varchar(max), s.value), lev + 1
       from formula f cross apply
            string_split(f.itemformula, '+') s join
            ordering o
            on o.itemtext = s.value
        -- where lev <= 2
     ),
     ordered as (
      select distinct o.*,
             dense_rank() over (order by (case when lev = 1 then -1 else lev end), (case when lev = 1 then '' else otheritemtext end)) as seqnum
      from ordering o
     ),
     cte as (
      select o.itemid, o.itemtext, o.itemformula, convert(varchar(max), o.otheritemtext) as otheritemtext,
             o.itemformula as newformula, o.seqnum, 1 as lev
      from ordered o
      where seqnum = 1
      union all
      select cte.itemid, o.itemtext, o.itemformula, convert(varchar(max), cte.itemtext),
             replace(o.itemformula, o.otheritemtext, concat('(', cte.newformula, ')')),  o.seqnum, cte.lev + 1
      from cte join
           ordered o
           on cte.itemtext = o.otheritemtext and cte.seqnum < o.seqnum
     )
select *
from cte;

И дБ < > скрипка .

Answer 2

Вы можете воспользоваться логическим порядком формул, если таковые имеются (Item_100 не может ссылаться на Item_150), и обрабатывать элементы в порядке убывания. Следующее использует LIKE, и оно не будет работать для формул, которые имеют перекрывающиеся шаблоны (например, ID_10 & ID_100), вы можете исправить это с помощью некоторых манипуляций со строками или сохраняя ItemID фиксированной длины (например, ID_10010 & ID_10100: начать нумерацию элементов с высокой число как 10000)

declare @f table
(
ItemId int,
ItemFormula varchar(1000)
);

insert into @f(ItemId, ItemFormula)
values 
(100, 'ID_3+ID_5'),
(110, 'ID_2+ID_6'),
(120, 'ID_100+ID_110'),
(130, 'ID_120+ID_4'),
(140, '(ID_130+ID_110)/ID_100'),
(150, 'sqrt(ID_140, ID_130)'), 
(160, 'ID_150-ID_120+ID_140');


;with cte
as
(
select f.ItemId, replace(cast(f.ItemFormula as varchar(max)), isnull('ID_' + cast(r.ItemId as varchar(max)), ''), isnull('(' + r.ItemFormula+ ')', '')) as therepl, 1 as lvl
from @f as f
outer apply (
    select *
    from
    (
    select rr.*, row_number() over(order by rr.ItemId desc) as rownum
    from @f as rr
    where f.ItemFormula like '%ID_' + cast(rr.ItemId as varchar(1000)) + '%'
    ) as src
    where rownum = 1
    ) as r
union all
select c.ItemId, replace(c.therepl, 'ID_' + cast(r.ItemId as varchar(max)), '(' + r.ItemFormula+ ')'), c.lvl+1
from cte as c
cross apply (
    select *
    from
    (
    select rr.*, row_number() over(order by rr.ItemId desc) as rownum
    from @f as rr
    where c.therepl like '%ID_' + cast(rr.ItemId as varchar(1000)) + '%'
    ) as src
    where rownum = 1
    ) as r
),
rown
as
(
select *, row_number() over (partition by itemid order by lvl desc) as rownum
from cte
)
select *
from rown
where rownum = 1;

Answer 3

Мой вопрос таков: могу ли я сохранить предыдущую рекурсию только каждый раз, когда происходит рекурсия?

Нет. Рекурсивный CTE будет продолжать добавлять строки к тем, которые были найдены в предыдущих итерациях. У вас нет какого-либо элемента управления, который позволял бы вам удалять строки рекурсивного CTE во время его итераций.

Однако вы можете отфильтровать их после рекурсивный CTE завершен, возможно, на вторичном CTE, который учитывает только последние значимые строки (по какому-то правилу, которое будет определено).

Единственная неопределенно похожая идея - находится в PostgreSQL, где вы можете использовать предложение UNION в дополнение к UNION ALL, чтобы избежать создания более идентичных строк. Но в любом случае это отличается от того, что вам нужно.