Consulta recursiva para descobrir o registro que cria dependência circular

A detecção de ciclo é um recurso integrado de CTEs recursivos: _{demonstração em db<>fiddle}

1. CYCLEcláusula informa qual valor indica um loop se ele se repetir
2. Ele é seguido por um booleancampo, preenchido para os registros com loops, depois um campo de matriz que contém todo o caminho/grupo com o ciclo.
3. Como o terceiro campo pathacumula todas as chaves, ele pode crescer rapidamente em conjuntos maiores e mais complexos. Como uma alternativa otimizada, rápida e com uso eficiente de memória, considerepgrouting .

WITH recursive tmp AS (
   SELECT supervisor_id,
          emp_id
   FROM incoming_records
   UNION ALL
   SELECT tmp.supervisor_id,
          t.emp_id
   FROM tmp
       INNER JOIN incoming_records AS t
           ON t.supervisor_id = tmp.emp_id
)CYCLE emp_id SET is_cycle USING path ----- here
SELECT * FROM tmp
WHERE is_cycle;

Se você quiser evitá-los em vez de selecionar apenas esses, mude para WHERE NOT is_cycle;.

A cláusula padrão SQL CYCLEpara detecção de ciclo integrada foi adicionada na v14 .

pgr_connectedComponents()

Em comparação com CTEs recursivos do tipo "faça você mesmo", as funções que vêm na pgroutingextensão são executadas mais rapidamente, usando menos memória, graças a anos de desenvolvimento do Boost C++ .

Em conjuntos de amostra com alguns milhares de linhas, ele roda algumas vezes mais rápido do que todas as alternativas aqui e é o único aplicável acima desse tamanho. Os CTEs recursivos ficam sem memória, vazam para o disco e, em seguida, ficam sem espaço nos milhares inferiores. Aqui está um teste em 7,5 mil linhas em que ele leva 143 ms , enquanto pgroutingtermina em 31 ms .
Se você aumentar o tamanho da amostra acima disso, o db<>fiddle fica sem recursos necessários para manter o exemplo de CTE recursivo ativo.

Em 50k amostras, pgroutingo exemplo abaixo encontra 3899 linhas de grupos com loops em 170 ms :
_{demonstração em db<>fiddle}

with trees as(
    select supervisor_id
         , emp_id
         , every(supervisor_id is not null)over w1 as has_cycle
    from pgr_connectedComponents(
      $x$ select row_number()over() as id
               , coalesce(emp_id,supervisor_id,1e7::int) as source
               , coalesce(supervisor_id,emp_id,1e7::int) as target
               , 1      as cost
               , 1      as reverse_cost
          from incoming_records 
      $x$) as c(seq,subgraph,emp_id)
    join incoming_records using(emp_id)
    window w1 as (partition by subgraph) )
select supervisor_id
     , emp_id
from trees 
where has_cycle;

Note que isso pressupõe que você não pode tornar um funcionário seu próprio supervisor e que cada funcionário pode ter no máximo um supervisor por vez. Neste cenário, é suficiente estabelecer que o supervisor de ponta nula está faltando para determinar que uma árvore contém um loop.

Exibindo o máximo possível até chegar ao loop

Em vez de identificar os loops em uma tarefa separada,
você pode obter um passo a passo à prova de falhas, lembrando-se do caminho para chegar a cada item e parando quando encontrar um funcionário já visto.

A estrutura correta para mantê-lo é a do PostgreSQL array:

WITH recursive tmp
AS (
   -- We're starting from the top, so no need of supervisor_id anymore:
   SELECT emp_id,
          array[emp_id] path                -- ← Here init our path.
   FROM incoming_records
   WHERE supervisor_id IS NULL
   UNION ALL
   SELECT t.emp_id,
          path||t.emp_id                    -- ← Here append the current employee.
   FROM tmp
       INNER JOIN incoming_records AS t
           ON t.supervisor_id = tmp.emp_id
   WHERE t.supervisor_id = tmp.emp_id
   AND NOT t.emp_id = ANY(path)             -- ← Here ensure the new employee is not a supervisor (already in the path) of this one.
) select * from tmp;

(veja-o tocando violino )

Um trabalho de 2 etapas (primeiro identificando os loops e depois calculando a árvore quando não houver mais loops) exigiria, de qualquer forma, o cálculo do caminho durante o CTE recursivo,
mas:

• bloqueie sua ferramenta até que você manualmente deleteum dos culpados
• dificultar seu diagnóstico (se você começar de baixo como tentou, não conseguirá subir até o topo e ver onde na hierarquia seus dois candidatos estariam aproximadamente)

Com exibição de culpado

Você pode até mesmo exibir a entrada em loop durante a marcação em vez de filtrar (… e então na próxima iteração, parar a entrada marcada, é claro):

WITH recursive tmp
AS (
   SELECT emp_id, array[emp_id] path, FALSE looping
   FROM incoming_records
   WHERE supervisor_id IS NULL
   UNION ALL
   SELECT t.emp_id, path||t.emp_id, t.emp_id = ANY(path) -- ← If detecting a loop, SELECT but tag.
   FROM tmp
       INNER JOIN incoming_records AS t
           ON t.supervisor_id = tmp.emp_id
   WHERE t.supervisor_id = tmp.emp_id
   AND NOT looping                                       -- ← If last iteration was tagged, do not look for its subordinates anymore.
) select * from tmp;

Então você pode usá-lo tanto na sua consulta de produção (onde você filtrará com um WHERE NOT loopingpara manter apenas um rt08) quanto no seu diagnóstico manual.

Limites

Duplicatas

Observe que ainda pode haver duplicatas se você tiver duas maneiras de entrar no loop.

Por exemplo, se 8 e 9 estiverem abaixo de 7, e um abaixo do outro,
você obterá 9 como 7 > 9e 7 > 8 > 9(o que não é um loop, pois 9ainda não está no caminho; haverá um loop na próxima iteração, com 7 > 8 > 9 > 8).

Mas isso não é específico para loops, aqui é um problema de gráfico.

Você pode evitar isso escolhendo um DISTINCT ON (emp_id) ORDER BY ARRAY_LENGTH(path, 1) DESC(isso elege o caminho mais curto para o funcionário, mas se dois caminhos levam ao mesmo funcionário (por exemplo, se 3 > 5e 4 > 5), um será eleito arbitrariamente; e os subordinados deste incerto não necessariamente escolherão o mesmo caminho, portanto você pode terminar com 3 > 5para, 5mas 4 > 5 > 6com 6).

Nenhum ponto de entrada

Este de cima para baixo requer que seus elementos de loop tenham múltiplos pais, com pelo menos um acessível a partir de um funcionário não supervisionado.
Um loop puro nunca aparecerá nos resultados. (por exemplo: if 8 > 9e 9 > 8loop juntos com no 7 > 8para conectá-los ao resto do mundo).

Neste caso, você não terá outra escolha a não ser ter um "detector de loop puro" separado, como visto na minha resposta dedicada .

Detectando loops puros

Se você tiver loops puros em circuito fechado (sem nenhuma maneira de chegar a um chefe de hierarquia sem um supervisor),
minha abordagem de exibir o máximo possível não funcionará, porque requer um chefe de hierarquia como ponto de entrada.

Nesse caso, você ainda pode usar matrizes do PostgreSQL para construir o caminho de baixo para cima para cada funcionário e
parar assim que encontrar um funcionário já visto:

WITH recursive tmp
AS (
   SELECT supervisor_id, emp_id, array[]::text[] path -- ← Start with an empty path beyond each employee.
   FROM incoming_records
   UNION ALL
   SELECT t.supervisor_id, t.emp_id, tmp.emp_id||path -- ← Append the employee where we came from to the path.
   FROM tmp
       INNER JOIN incoming_records AS t
           ON tmp.supervisor_id = t.emp_id
   AND NOT tmp.emp_id = ANY(path)                     -- ← Do not continue for entries having appeared in their own path.
) select * from tmp where emp_id = ANY(path);         -- ← And show only those, not the intermediates who succeeded into reaching a head of hierarchy without loop.