私は、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となります。

• （9：

  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 
  

  Iはアークを得ることがこのクエリの結果：

  Iは、ノードから開始アークのリスト（パス）を取得するために、このクエリを使用します、3）

• （12,9）

このクエリは正常に動作しますが、グラフ上のサイクルがある場合：

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

それが無限ループに行き、私はエラーメッセージを取得：

文が終了します。文の完了前に最大再帰100が使い尽くされました。

私のプロジェクトでは他のテーブルを使用したり作成したりすることはできないので、私は一時的なものですべてを行う必要があります。どのようにして正しいパスを得るためにクエリを修正し、サイクルに陥るのを避けることができますか？

Answer 1

あなたが行くとテストとしてidがすでにある場合は、IDの文字列を構築することができます。

;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

各パス/アークをテンポラリテーブルに格納する必要があります。

各パスでtempテーブルをチェックして、パスが保存されているかどうかを確認してください。