Postgresql recursive self join

Question

Моя таблица в postgres выглядит, как показано ниже, в таблице хранится цепочка отношений между идентификаторами, и я хочу получить запрос, который может дать результат типа «vc1» -> «rc7» или «vc3» - > «RC7», я буду запрашивать только идентификаторы в первом столбце ID1

ID1  ID2 
"vc1" "vc2" 
"vc2" "vc3" 
"vc3" "vc4" 
"vc4" "rc7" 

Так что я хочу поставить некоторые «головы» идентификатор здесь, для которого я должен принести хвост (последний в цепочке) ид.

Answer 1

Вот SQL с помощью рекурсивного ОТВ:

with recursive tr(id1, id2, level) as (
     select t.id1, t.id2, 1 as level 
     from t union all 
     select t.id1, tr.id2, tr.level + 1 
     from t join 
      tr 
      on t.id2 = tr.id1 
    ) 
select * 
from (select tr.*, 
      max(level) over (partition by id1) as maxlevel 
     from tr 
    ) tr 
where level = maxlevel; 

Here является SQLFiddle

Answer 2

Это классическое использование простого рекурсивного общего табличного выражения (WITH RECURSIVE), доступны в PostgreSQL 8.4 и более поздних версий ,

Демонстрируется здесь: http://sqlfiddle.com/#!12/78e15/9

Учитывая данные выборки как SQL:

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

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

Вы могли бы написать:

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; 

Что это делает итеративно ходить цепи, добавляя каждую строку Таблица chain как от и до указателей. Когда он встречает строку, для которой ссылка «to» не существует, она добавит ссылку «null» в эту строку. Следующая итерация заметит, что ссылка «to» равна null и создает нулевые строки, что приводит к завершению итерации.

Внешний запрос затем берет строки, которые были определены как конец цепочки, имея несуществующий to_id.

Требуется немного усилий, чтобы получить голову вокруг рекурсивных CTE. Они ключевые вещи, чтобы понять, являются:

• Они начинают с выходом первоначального запроса, который они неоднократно накидной с выходом «рекурсивной части» (запрос после UNION или UNION ALL) до рекурсивной части не добавляет строк. Это останавливает итерацию.

• Они не являются действительно рекурсивными, более итеративными, хотя они хороши для того, что вы можете использовать для рекурсии.

Итак, вы в основном строите стол в петле. Вы не можете удалять строки или изменять их, добавлять только новые, поэтому вам обычно нужен внешний запрос, который фильтрует результаты, чтобы получить нужные строки результатов. Вы часто добавляете дополнительные столбцы, содержащие промежуточные данные, которые вы используете для отслеживания состояния итерации, условий остановки и т. Д.

Это может помочь посмотреть на нефильтрованный результат. Если я заменяю окончательный итоговый запрос с помощью простого SELECT * FROM chain я могу увидеть таблицу, которая была генерируемый:

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

Первая строка является вручную добавлена ​​начальная точка строки, где вы указываете, что вы хотите посмотреть - в этом случай, который был vc2.Каждая последующая строка была добавлена ​​рекурсивным термином ed, который выполняет LEFT OUTER JOIN по предыдущему результату и возвращает новый набор строк, которые соединяют предыдущий to_id (теперь в столбце from_id) со следующим to_id. Если LEFT OUTER JOIN не соответствует, то to_id будет иметь значение null, в результате чего следующий вызов будет возвращать теперь строки и завершать итерацию.

Поскольку этот запрос не пытается добавить только последнюю строку , это на самом деле повторяет справедливую работу каждой итерации. Чтобы избежать этого, вам нужно будет использовать подход, более похожий на Gordon's, но дополнительно фильтровать в предыдущем поле глубины при сканировании входной таблицы, поэтому вы присоединились только к самой последней строке. На практике это обычно не требуется, но это может быть проблемой для очень больших наборов данных или там, где вы не можете создавать соответствующие индексы.

Подробнее можно узнать в the PostgreSQL documentation on CTEs.