Я застрял на циклах, чтобы получить путь SQL-ориентированного графа

Question

У меня есть таблица, в которой я храню пары чисел, чтобы указать дуги ориентированного графа, где каждый узел идентифицируется целочисленным значением:

CREATE TABLE graph (    
n2 INTEGER NOT NULL,    
n1 INTEGER NOT NULL,
PRIMARY KEY (id_area_possesso, id_area_utente)
CONSTRAINT CK CHECK (n1 <> n2)
)

Где n1 указывает на n2 и т. Д .; так, например, когда я вставлю

INSERT INTO graph VALUES (3,4)
INSERT INTO graph VALUES (9,3)
INSERT INTO graph VALUES (12,9)

Я получу этот график: 4-> 3-> 9-> 12.

Я использую этот запрос, чтобы получить список дуг (пути), начиная с узла:

WITH tmp (n2,n1) AS (
SELECT G.n2 , G.n1 
FROM Graph AS G
WHERE n1=3
UNION ALL

SELECT n2 , n1
FROM Graph AS G JOIN tmp ON (G.n1=tmp.N2)  

)

SELECT * FROM tmp 
GO

В результате этого запроса я бы получил дуги:

• (9,3)
• (12,9)

Этот запрос работает нормально, но когда на графике есть циклы:

INSERT INTO graph VALUES (0,1)
INSERT INTO graph VALUES (2,0)
INSERT INTO graph VALUES (1,2)

он идет по бесконечному циклу, и я получаю сообщение об ошибке:

Заявление прекращено. Максимальная рекурсия 100 была исчерпана до завершения оператора.

Я не могу использовать или создавать другие таблицы в моем проекте, поэтому мне придется делать все на временных. Как я могу исправить свой запрос, чтобы получить правильный путь, избегая зацикливания?

Answer 1

Вы можете создать строку с идентификаторами, когда вы идете, и проверить, есть ли идентификатор уже.

;WITH tmp (n2,n1,nx) AS
(
  SELECT G.n2, 
         G.n1,
         cast('/'+cast(G.n1 as varchar(10))+'/' as varchar(max))
  FROM Graph AS G
  WHERE n1=1
  UNION ALL
  SELECT G.n2, 
         G.n1,
         tmp.nx+cast(G.n1 as varchar(10)) +'/'
  FROM Graph AS G 
    JOIN tmp 
      ON (G.n1=tmp.N2) and
         tmp.nx not like '%/'+cast(G.n1 as varchar(10))+'/%' 
)

SELECT * FROM tmp 

Answer 2

вам нужно будет хранить каждый путь / дугу во временной таблице.

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