Tengo un conjunto de dependencias almacenadas en mi base de datos. Estoy buscando encontrar todos los objetos que dependen del actual, ya sea directa o indirectamente. Dado que los objetos pueden depender de cero o más objetos, es perfectamente razonable que el objeto 1 dependa del objeto 9 dos veces (9 depende de 4 y 5, los cuales dependen de 1). Me gustaría obtener la lista de todos los objetos que dependen del objeto actual sin duplicación.

Esto se vuelve más complejo si hay bucles. Sin bucles, uno podría usar DISTINCT, aunque pasar por largas cadenas más de una vez solo para eliminarlos al final sigue siendo un problema. Con los bucles, sin embargo, es importante que el CTE RECURSIVO no se una con algo que ya ha visto.

Así que lo que tengo hasta ahora se ve así:

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;

(Está en un procedimiento almacenado, así que puedo pasar_objectid)

esafortunadamente, esto simplemente omite un objeto dado cuando lo he visto antes en la cadena actual, lo que estaría bien si se realizara un CTE recursivo primero en profundidad, pero cuando es primero en amplitud, se vuelve problemátic

dealmente, la solución sería en SQL en lugar de PLPGSQL, pero cualquiera de los dos funciona.

Como ejemplo, configuré esto en 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);

Y luego intenté ejecutar esto:

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;

Espero "1, 2, 3" como salida.

Sin embargo, esto de alguna manera continúa para siempre (lo que tampoco entiendo). Si agrego unlevel cheque select dep, 0 as level, ...select dep, level + 1, on ... and level < 3), Veo que 2 y 3 se repiten. Por el contrario, si agrego un cheque visto:

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;

Entonces obtengo 1, 2, 3, 2, 3, y se detiene. Podría usarDISTINCT en la selección externa, pero eso solo funciona razonablemente en estos datos porque no hay bucle. Con un conjunto de datos más grande y más bucles, continuaremos aumentando la producción del CTE solo para que DISTINCT lo reduzca nuevamente. Me gustaría que el CTE simplemente detenga esa rama cuando ya haya visto ese valor particular en otro lugar.

Edita: no se trata simplemente de la detección de ciclos (aunque puede haber ciclos). Se trata de descubrir todo lo que hace referencia este objeto, directa e indirectamente. Entonces, si tenemos 1-> 2-> 3-> 5-> 6-> 7 y 2-> 4-> 5, podemos comenzar en 1, ir a 2, desde allí podemos ir a 3 y 4, ambos de esas ramas irán a 5, pero no necesito ambas ramas para hacerlo: la primera puede ir a 5, y la otra simplemente puede detenerse allí. Luego pasamos a 6 y 7. La mayoría de la detección de ciclos no encontrará ciclos y devolverá 5, 6, 7 todo dos veces. Dado que espero que la mayoría de mis datos de producción tengan 0-3 referencias inmediatas, y que la mayoría de ellos sean del mismo modo, será muy común que haya múltiples ramas de un objeto a otro, y bajar esas ramas no será solo redundante pero una gran pérdida de tiempo y recursos.