Поиск кольцевых ссылок в реляционной базе данных рекурсивным SQL запросом

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

Между тем, существует способ однозначного выявления циклов без "наматывания" кругов по графу. Рассмотрим граф, показанный на рисунке ниже:

В базе данных он хранится в виде матрицы смежностей в таблице t:

  CREATE TABLE t (
    a INTEGER,
    b INTEGER
  )

Соответственно, исходные данные:

  INSERT INTO t VALUES (1, 2);
  INSERT INTO t VALUES (2, 3);
  INSERT INTO t VALUES (3, 4);
  INSERT INTO t VALUES (3, 5);
  INSERT INTO t VALUES (3, 6);
  INSERT INTO t VALUES (2, 7);
  INSERT INTO t VALUES (6, 1);

Для поиска кольцевых ссылок напишем запрос:

with recursive tree as
  (
    select distinct
      a as initial, a, b, -1 as prev
    from
      t

    union all
    
    select
      iif(tr.initial <> tt.a, tr.initial, -1) as initial,
      tt.a,
      tt.b,
      tr.a as prev
    from
      t tt JOIN tree tr ON
        tr.b = tt.a and tr.initial > 0

  )
select
  *
from
  tree
where
  initial = -1

Запрос покажет все первые сегменты A - B (и предыдущие, т.е. сегменты непосредственно приведшие к циклу, PREV - A), всех возможных циклов в заданных данных. В нашем случае:

INITIAL A B PREV
-1 1 2 6
-1 2 3 1
-1 2 7 1
-1 3 4 2
-1 3 5 2
-1 3 6 2
-1 6 1 3

При необходимости проверить не входит ли в кольцо конкретный узел, следует прописать его ИД в первом запросе рекурсивного CTE:

with recursive tree as
  (
    select distinct
      a as initial, a, b, -1 as prev
    from
      t
    where 
      a = _some_id_

    union all
    
    select
      iif(tr.initial <> tt.a, tr.initial, -1) as initial,
      tt.a,
      tt.b,
      tr.a as prev
    from
      t tt JOIN tree tr ON
        tr.b = tt.a and tr.initial > 0

  )
select
  *
from
  tree
where
  initial = -1