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

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

Это становится более сложным, если есть петли. Без циклов можно использовать DISTINCT, хотя прохождение длинных цепей более одного раза только для их отбраковки в конце все еще является проблемой. Однако с циклами становится важным, чтобы рекурсивный 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 непосредственных ссылок, и большинство из них будут аналогичными, будет очень распространено, когда будет несколько ветвей от одного объекта к другому, и переход по этим ветвям не будет только избыточный, но огромная трата времени и ресурсов.

Ответы на вопрос(4)

Ваш ответ на вопрос