Autojunção recursiva do Postgresql

Este é um uso clássico de uma expressão de tabela comum recursiva simples (WITH RECURSIVE ), disponível no PostgreSQL 8.4 e posterior.

Demonstrado aqui:http://sqlfiddle.com/#!12/78e15/9

Dados os dados de exemplo como SQL:

CREATE TABLE Table1
    ("ID1" text, "ID2" text)
;

INSERT INTO Table1
    ("ID1", "ID2")
VALUES
    ('vc1', 'vc2'),
    ('vc2', 'vc3'),
    ('vc3', 'vc4'),
    ('vc4', 'rc7')
;

Você poderia escrever:

WITH RECURSIVE chain(from_id, to_id) AS (
  SELECT NULL, 'vc2'
  UNION
  SELECT c.to_id, t."ID2"
  FROM chain c
  LEFT OUTER JOIN Table1 t ON (t."ID1" = to_id)
  WHERE c.to_id IS NOT NULL
)
SELECT from_id FROM chain WHERE to_id IS NULL;

O que isso faz é percorrer iterativamente a cadeia, adicionando cada linha à chain tabela como ponteiros de e para. Quando encontrar uma linha para a qual a referência 'to' não existe, ela adicionará uma referência 'to' nula para essa linha. A próxima iteração notará que a referência 'to' é nula e produzirá zero linhas, o que faz com que a iteração termine.

A consulta externa então pega as linhas que foram determinadas como o fim da cadeia por ter um to_id inexistente.

É preciso um pouco de esforço para entender CTEs recursivos. Eles são as principais coisas para entender são:

Eles começam com a saída de uma consulta inicial, que eles unem repetidamente com a saída da "parte recursiva" (a consulta após o UNION ou UNION ALL ) até que a parte recursiva não adicione linhas. Isso interrompe a iteração.
Eles não são realmente recursivos, mais iterativos, embora sejam bons para os tipos de coisas para as quais você pode usar a recursão.

Então você está basicamente construindo uma tabela em um loop. Você não pode excluir linhas ou alterá-las, apenas adicionar novas, portanto, geralmente você precisa de uma consulta externa que filtre os resultados para obter as linhas de resultados desejadas. Muitas vezes, você adicionará colunas extras contendo dados intermediários que você usa para rastrear o estado da iteração, controlar as condições de parada etc.

Pode ajudar a olhar para o resultado não filtrado. Se eu substituir a consulta de resumo final por um simples SELECT * FROM chain Eu posso ver a tabela que foi gerada:

 from_id | to_id 
---------+-------
         | vc2
 vc2     | vc3
 vc3     | vc4
 vc4     | rc7
 rc7     | 
(5 rows)

A primeira linha é a linha de ponto de partida adicionada manualmente, onde você especifica o que deseja pesquisar - neste caso, foi vc2 . Cada linha subsequente foi adicionada pelo UNION ed termo recursivo, que faz um LEFT OUTER JOIN no resultado anterior e retorna um novo conjunto de linhas que emparelham o to_id anterior (agora no from_id coluna) para o próximo to_id . Se o LEFT OUTER JOIN não corresponde ao to_id será nulo, fazendo com que a próxima invocação retorne agora linhas e finalize a iteração.

Como esta consulta não tenta adicionar apenas o último row a cada vez, na verdade está repetindo um pouco de trabalho a cada iteração. Para evitar isso, você precisaria usar uma abordagem mais parecida com a de Gordon, mas, adicionalmente, filtrar no campo de profundidade anterior quando você varreu a tabela de entrada, então você uniu apenas a linha mais recente. Na prática, isso geralmente não é necessário, mas pode ser uma preocupação para conjuntos de dados muito grandes ou onde você não pode criar índices apropriados.

Mais pode ser aprendido na documentação do PostgreSQL sobre CTEs.