Обнаружение дублирующихся элементов в рекурсивном CTE

Question

У меня есть набор зависимостей, хранящихся в моей базе данных.Я ищу, чтобы найти все объекты, которые зависят от текущего, прямо или косвенно.Поскольку объекты могут зависеть от нуля или более других объектов, совершенно разумно, чтобы объект 1 зависел от объекта 9 дважды (9 зависит от 4 и 5, оба из которых зависят от 1).Я хотел бы получить список всех объектов, которые зависят от текущего объекта без дублирования.

Это становится более сложным, если есть циклы.Без циклов можно использовать DISTINCT, хотя прохождение длинных цепей более одного раза только для их отбраковки в конце все еще является проблемой.Однако с циклами становится важным, чтобы RECURSIVE CTE не объединялся с чем-то, что он уже видел.

Итак, то, что я пока имею, выглядит так:

WITH RECURSIVE __dependents AS (
  SELECT object, array[object.id] AS seen_objects
  FROM immediate_object_dependents(_objectid) object
  UNION ALL
  SELECT object, d.seen_objects || object.id
  FROM __dependents d
  JOIN immediate_object_dependents((d.object).id) object
    ON object.id <> ALL (d.seen_objects)
) SELECT (object).* FROM __dependents;

(Этов хранимой процедуре, поэтому я могу передать _objectid)

К сожалению, это просто опускает данный объект, когда я видел его ранее в текущей цепочке, что было бы хорошо, если бы рекурсивный CTE былделается в глубину, но когда он в ширину, он становится проблематичным.

В идеале, решение должно быть в SQL, а не PLPGSQL, но любой из них работает.

В качестве примера яустановите это в postgres:

create table objectdependencies (
  id int,
  dependson int
);

create index on objectdependencies (dependson);

insert into objectdependencies values (1, 2), (1, 4), (2, 3), (2, 4), (3, 4);

И затем я попытался запустить это:

with recursive rdeps as (
  select dep
  from objectdependencies dep
  where dep.dependson = 4 -- starting point
  union all
  select dep
  from objectdependencies dep
  join rdeps r
    on (r.dep).id = dep.dependson
) select (dep).id from rdeps;

Я ожидаю "1, 2, 3" в качестве вывода.

Однако это как-то продолжается вечно (чего я тоже не понимаю).Если я добавлю проверку level (select dep, 0 as level, ... select dep, level + 1, on ... and level < 3), я вижу, что 2 и 3 повторяются.И наоборот, если я добавлю видимый чек:

with recursive rdeps as (
  select dep, array[id] as seen
  from objectdependencies dep
  where dep.dependson = 4 -- starting point
  union all
  select dep, r.seen || dep.id
  from objectdependencies dep
  join rdeps r
    on (r.dep).id = dep.dependson and dep.id <> ALL (r.seen)
) select (dep).id from rdeps;

, тогда я получу 1, 2, 3, 2, 3, и он остановится.Я мог бы использовать DISTINCT во внешнем выборе, но это только разумно работает с этими данными, потому что нет цикла.С большим набором данных и большим количеством циклов мы продолжим наращивать вывод CTE только для того, чтобы DISTINCT сократил его обратно.Я бы хотел, чтобы CTE просто остановил эту ветвь, когда уже видел это конкретное значение где-то еще.

Редактировать : речь идет не просто об обнаружении циклов (хотя могут быть циклы).Речь идет о раскрытии всего, на что ссылается этот объект, прямо и косвенно.Так что, если у нас есть 1-> 2-> 3-> 5-> 6-> 7 и 2-> 4-> 5, мы можем начать с 1, перейти к 2, оттуда мы можем перейти к 3 и 4, обаиз этих веток перейдет к 5, но мне не нужны обе ветви - первая может перейти к 5, а другая может просто остановиться на этом.Затем мы переходим к 6 и 7. Большинство обнаружений циклов не находят циклов и возвращают 5, 6, 7 все дважды.Учитывая, что я ожидаю, что большинство моих производственных данных будут иметь 0-3 непосредственных ссылок, и большинство из них будут аналогичными, будет очень распространено, когда будет несколько ветвей от одного объекта к другому, и переход по этим ветвям не будеттолько излишняя, но огромная трата времени и ресурсов.

Answer 1

Я знаю, что это не довольно старый вопрос, но я немного удивлен, что никто не предлагал удалить all из union для раннего устранения дубликатов.Это довольно простой способ предотвратить дублирование в результате рекурсивного CTE, но у него есть свои предостережения - такой результат должен включать только реальные поля, то есть не рассчитанные на ходу depth, path или что-либо еще.

Используя пример данных из вопроса с этим запросом (немного переформатированный из оригинала):

with recursive
rdeps as (
  select dep.id, dep.id as dependson
  from objectdependencies as dep
  where dep.dependson = 4 -- starting point
  union
  select self.id, dep.dependson
  from rdeps as self 
  join objectdependencies as dep on dep.dependson = self.id
)
select dependson from rdeps;

Я получаю точно 1, 2 и 3.

Более того, это решение предотвращает бесконечный цикл в случае цикла в зависимостях.Однако он не обнаруживает его, так как он не обнаруживает и не может показать наличие цикла, он просто предотвращает бесконечный цикл.

Answer 2

Вы можете использовать это для поиска повторяющихся значений

WITH cte AS (
SELECT ROW_NUMBER()OVER(PARTITION BY [FieldName] ORDER BY [FieldName])[Rank],* 
FROM TableName)
SELECT * 
FROM  cte 
WHERE cte.[Rank]>1

Answer 3

Вы можете использовать функцию connectby, которая существует в модуле tablefunc.

Сначала вам нужно включить модуль

CREATE EXTENSION tablefunc;

Затем вы можете использовать функцию connectby (на основе примераТаблица, которую вы предоставили в вопросе, будет выглядеть следующим образом):

SELECT distinct id
FROM connectby('objectdependencies', 'id', 'dependson', '4', 0)
AS t(id int, dependson int, level int)
where id != 4;

Это вернет: 1 2 3

Вот объяснение параметров из документации:

connectby(text relname, text keyid_fld, text parent_keyid_fld
          [, text orderby_fld ], text start_with, int max_depth
          [, text branch_delim ])

• relname Имя отношения источника
• keyid_fld Имя поля ключа
• parent_keyid_fld Имя поля родительского ключа
• orderby_fld Имя поля дляупорядочить братьев и сестер по (опционально)
• start_with Значение ключа строки, с которой начинается
• max_depth Максимальная глубина для спуска или ноль для неограниченной глубины
• branch_delim Строка для разделения ключейс выходом в ответвлении (необязательно)

Пожалуйста, обратитесь к документации для получения дополнительной информации.https://www.postgresql.org/docs/9.5/static/tablefunc.html

Answer 4

Слово dep во втором запросе (после union) неоднозначно.Фактически он интерпретируется как столбец rdeps, а не как псевдоним objectdependencies.

with recursive rdeps as (
  select dep
  from objectdependencies dep
  where dep.dependson = 4 -- starting point
  union all
  select dep -- this means r.dep
  from objectdependencies dep
  join rdeps r
    on (r.dep).id = dep.dependson
) select (dep).id from rdeps;

. Именно поэтому запрос создает бесконечный цикл.Вы можете исправить это, изменив псевдоним:

with recursive rdeps as (
  select dep
  from objectdependencies dep
  where dep.dependson = 4 -- starting point
  union all
  select objectdep
  from objectdependencies objectdep
  join rdeps r
    on (r.dep).id = objectdep.dependson
) select (dep).id from rdeps;

 id 
----
  1
  2
  3
  1
  2
  1
(6 rows)    

Или лучше, просто используя столбцы, как задумал добрый Господь:

with recursive rdeps as (
    select id, dependson
    from objectdependencies
    where dependson = 4
union all
    select d.id, d.dependson
    from objectdependencies d
    join rdeps r
    on r.id = d.dependson
) 
select *
from rdeps;

Первый запрос в вопросе - это все, что выможет сделать в простом sql, так как нет связи между различными (paralel) ветвями, генерируемыми рекурсивным запросом.В функциональном подходе вы можете использовать временную таблицу в качестве хранилища, общего для всех филиалов.Функция может выглядеть так:

create or replace function rec_function(int)
returns void language plpgsql as $$
declare
    i int;
begin
    for i in
        select id
        from objectdependencies
        where dependson = $1
    loop
        if not exists(
            select from temp_table 
            where id = i)
        then
            insert into temp_table values(i);
            perform rec_function(i);
        end if;
    end loop;
end $$;

Использование:

create temp table temp_table(id int);

select rec_function(4);

select *
from temp_table;