0

在 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)

因此，插入的每个父子关系都需要使用 Distance + 1 复制所有父级的 Foo_Foo 条目：

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 至少需要 (# unique paths to D from V) * (D-1) * (D-2) * ... Foo_Foo 表中的条目。我可以进一步规范化上述内容以获得空间复杂度（~# 与 V 距离为 D 的顶点）* (D-1)！，但这已经是我能做到的了。

这对于表示可以任意增长的 DAG 显然是不可行的。递归查询可能是最好的解决方案，但并非在所有地方都得到完全支持。树有一些聪明的解决方案，但我一直无法为 DAG 找到一个好的解决方案。有没有使用带有非递归查询的 SQL 表的聪明的 DAG 解决方案？

4

0 回答 0