Eu tenho um conjunto de dependências armazenadas no meu banco de dados. Eu estou procurando encontrar todos os objetos que dependem do atual, direta ou indiretamente. Como os objetos podem depender de zero ou mais outros objetos, é perfeitamente razoável que o objeto 1 seja dependente do objeto 9 duas vezes (9 depende de 4 e 5, os quais dependem de 1). Eu gostaria de obter a lista de todos os objetos que dependem do objeto atual sem duplicação.

Isso fica mais complexo se houver loops. Sem loops, pode-se usar o DISTINCT, embora passar por longas cadeias mais de uma vez apenas para selecioná-las no final ainda seja um problema. Com os loops, no entanto, torna-se importante que o CTE RECURSIVO não se una a algo que ele já viu.

Então, o que eu tenho até agora se parece com isso:

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á em um procedimento armazenado, para que eu possa passar_objectid)

Infelizmente, isso omite um determinado objeto quando o vi anteriormente na cadeia atual, o que seria bom se uma CTE recursiva estivesse sendo executada em profundidade primeiro, mas quando é ampliada em primeiro lugar, torna-se problemática.

Idealmente, a solução seria no SQL, e não no PLPGSQL, mas qualquer um funciona.

Como exemplo, eu configurei isso no 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);

E então eu tentei executar isso:

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;

Estou esperando "1, 2, 3" como saída.

No entanto, isso de alguma forma continua para sempre (o que eu também não entendo). Se eu adicionar umlevel Verifica (select dep, 0 as level, ...select dep, level + 1, on ... and level < 3), Vejo que 2 e 3 estão se repetindo. Por outro lado, se eu adicionar uma verificação vista:

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;

então eu recebo 1, 2, 3, 2, 3 e ele para. eu poderia usarDISTINCT na seleção externa, mas isso apenas funciona razoavelmente nesses dados porque não há loop. Com um conjunto de dados maior e mais loops, continuaremos aumentando a produção do CTE apenas para que o DISTINCT o reduza novamente. Eu gostaria que o CTE simplesmente parasse esse ramo quando ele já viu esse valor específico em outro lugar.

Editar: não se trata apenas de detecção de ciclo (embora possa haver ciclos). Trata-se de descobrir tudo referenciado por esse objeto, direta e indiretamente. Portanto, se tivermos 1-> 2-> 3-> 5-> 6-> 7 e 2-> 4-> 5, podemos começar com 1, ir para 2, a partir daí podemos ir para 3 e 4, ambos desses galhos vão para 5, mas não preciso dos dois para fazer isso - o primeiro pode ir para 5 e o outro pode simplesmente parar por aí. Em seguida, passamos para 6 e 7. A maior parte da detecção de ciclo não encontra ciclos e retorna 5, 6, 7 duas vezes. Dado que eu espero que a maioria dos meus dados de produção tenha 0-3 referências imediatas e a maioria deles seja igualmente, será muito comum haver várias ramificações de um objeto para outro, e descer essas ramificações não será apenas redundante, mas um enorme desperdício de tempo e recursos.