SQLでDAGを表す標準的な方法は、推移閉包テーブルです。
CREATE TABLE Foo (Id int primary key identity, Name nvachar(30))
CREATE TABLE Foo_Foo
(ParentId int not null
,ChildId int not null
,Distance int not null)
したがって、挿入されるすべての親子関係では、親のすべてのFoo_FooエントリをDistance+1で複製する必要があります。
INSERT INTO Foo (Name) VALUES ('Some Name')
DECLARE @somename int = @@IDENTITY
-- DAG: Some Name -> Some other name
INSERT INFO Foo (Name) VALUES ('Some other name')
DECLARE @someother int = @@IDENTITY
INSERT INTO Foo_Foo (ParentId, ChildId, Distance)
VALUES (@somename, @someother, 0)
-- DAG: Some Name -> Some other name -> Some final name
INSERT INTO Foo (Name) Values ('Some final name')
INSERT INTO Foo_Foo (ParentId, ChildId, Distance)
VALUES (@someother, @@IDENTITY, 0)
INSERT INTO Foo_Foo (ParentId, ChildId, Distance)
SELECT ParentId, @@IDENTITY, Distance + 1 FROM Foo_Foo
WHERE ChildId = @someother
-- DAG: Some Name -> Some other name -> Some final name
-- \_____________________/
INSERT INTO Foo_Foo (ParentId, ChildId, Distance)
VALUES (@someother, @@IDENTITY, 0)
問題は、Foo_Fooテーブルが、DAGパスの深さの階乗に一意のパスの数を掛けたもので大きくなることです。DAGのルート頂点Vから距離Dに挿入されたすべてのFooには、少なくとも（VからDへの＃一意のパス）*（D-1）*（D-2）*...Foo_Fooテーブルのエントリが必要です。上記をさらに正規化して、スペースの複雑さ（Vから距離Dにある〜＃頂点）*（D-1）!を取得できますが、それは私が取得できる限り良好です。
これは、任意の長さに成長する可能性のあるDAGを表すには明らかに実行不可能です。再帰クエリはおそらく最良の解決策ですが、どこでも完全にサポートされているわけではありません。ツリーにはいくつかの巧妙な解決策がありますが、DAGの適切な解決策を見つけることができませんでした。非再帰クエリでSQLテーブルを使用する巧妙なDAGソリューションはありますか？