在 SQL 数据库上表示有向无环图 (DAG) 的模型
4.97/5 (47投票s)
解决在 SQL 数据库中表示有向无环图 (DAG) 的通用问题。
引言
在我作为软件工程师的这些年里，我一次又一次地面临着在关系型数据库表中建模分层数据的挑战。我记得的第一个是使用 FoxPro 为一家加工食品公司的产品树创建的模型。
然而，促使我更深入地思考这个问题并最终撰写本文的原因，是 SQL Server 数据库对行级授权方案的反复需求。当然，我知道微软的白皮书《使用 SQL Server 2005 在分类数据库中实现行级和单元级安全性》。我只想说，微软的解决方案过于复杂，因为他们无法对方法的应用系统做出假设。因此，许多可能的捷径和简化对他们来说都不可用。
然而，在本文中，我将仅解决在 SQL 数据库中表示有向无环图 (DAG) 的一般问题，这是我为解决基于行的安全问题而设计的解决方案的一部分，因为 DAG 的应用比仅行级授权要广泛得多。我将发布第二篇文章，以补充本文，并将讨论基于行的安全性的具体细节，以及在 SQL Server 上的高效实现。
在我深入细节之前，请允许我解释一下什么是 DAG。这是来自维基百科关于 DAG 的摘录：
“在计算机科学和数学中，有向无环图（Directed Acyclic Graph），也称为 DAG，是无有向环的有向图；也就是说，对于任何顶点 v，不存在从 v 开始并以 v 结束的非空有向路径。DAG 出现在顶点无法形成到自身的路径的模型中；例如，如果边 u?v 表示 v 是 u 的一部分，那么这样的路径将表示 u 是它自身的一部分，这是不可能的。非正式地说，DAG 是“单向流动”的。”
有关该主题的更多详细信息，请参阅维基百科上的文章。简而言之，DAG 具有以下属性：
具有上述属性的一个显著且熟悉的结构是面向对象编程中的继承层次结构。图 1 是一个简单的（且不完整的）类图，恰好是一个树。图中的箭头应读为“is a”。树是 DAG，但有一个重要的额外限制：从一个顶点到另一个顶点可能存在只有一条路径，例如，从Dog到Animal只有一种方式：Dog -> Pet -> Animal。此限制在 SQL 数据库建模方面为我们提供了极大的帮助。
可以说，解决 SQL 数据库中树结构建模问题的最简单且高效的解决方案是称为物化路径的方法。此模型依赖于从根顶点到每个顶点的完整路径的字符串标记。标记值由其祖先路径的串联组成。例如，如果根顶点Animal的路径是A，那么Pet的路径是A.P.，Dog的路径是A.P.D.。本质上，它是从根到当前顶点的路径。表 1 是此类表的摘录，以说明该方法。
表 1：动物表的样本数据
| ID | Path | 名称 | 其他列 |
| 1 | A.P.C. | 我的猫 | ... |
| 2 | A.P.D. | 我的狗 | ... |
| 3 | A.P.D. | 我的第二只狗 | ... |
| 4 | A.L.S. | 白绵羊 | ... |
| 5 | A.L.C. | 棕牛 | ... |
物化路径方法特别有用，因为它非常容易使用标准的 SQL like 运算符构建快速查询。例如，要获取所有狗，我将编写如下查询：
SELECT *
FROM Animal
WHERE Path LIKE 'A.P.D.%'
或者要获取所有牲畜，我可以写：
SELECT *
FROM Animal
WHERE Path LIKE 'A.L.%'
请注意，即使类继承体系稍后扩展，上述查询仍然有效。例如，如果我添加两个Dog类，Doberman和Bulldog，路径分别为A.P.D.D.和A.P.D.B.，则前面的查询仍然会返回所有狗。
问题
不幸的是，树对于建模现实世界来说过于局限。实际上，一个对象可能有多个方面，而不是树结构所暗示的一个方面。例如，仔细查看图 1会发现，在某些国家/地区，狗实际上也是牲畜。此外，有人可能将羊羔作为宠物。图 2显示了一个修改后的（仍然不完整的）类图，它包含了这些事实。（这只是一个例子，请勿争辩！）
请注意，图 2中的类图不再是树。区别在于，现在某些顶点之间存在多条路径。例如，我们可以使用路径(Dog -> Pet -> Animal)和(Dog -> Livestock -> Animal)从Dog到Animal。但是，一旦离开Dog顶点，仍然不可能回到Dog。因此，它仍然符合 DAG 的定义。用 OOP 的术语来说，Dog被认为具有多个祖先。[该功能称为多重继承 (MI)。这是一种特殊的多重继承，通常称为令人头疼的菱形继承。]
简单的物化路径模式不能用于建模图 2中的类图。这是因为路径列只能用于表示图上的单个路径，因此仅限于建模树。请记住，树只有一个到达特定顶点的路径。
具有多重继承的类继承体系并非 DAG 的唯一常见示例。还有许多其他示例。例如，在 Windows 中，NTFS 文件/文件夹结构（不，它实际上不是树）和 Active Directory 用户/组继承体系（这也是我决定解决此问题的原因）可以使用 DAG 进行建模。
解决方案
有许多出版物解决了在 SQL 数据库中建模树的问题。然而，我还没有看到一个针对有向无环图更普遍情况的完整解决方案和实现，其中图 2是一个简单的例子。因此，我决定自己解决它。
我的解决方案基于另一种流行的树问题解决方案的修改版本。该解决方案使用所谓的邻接表，即一个辅助表，除了实际存储对象（此处为顶点）属性的表之外，还存储边（顶点之间的链接）。为了说明该方法，让我们看一下图 3，这是图 2中类继承体系的进一步扩展版本。示例：图 3中的边Cat -> Pet可以由元组(EdgeId, Start Vertex, End Vertex) -> (3, 4, 2)表示。表 2显示了我们如何使用此模型表示图 3中的 DAG。
表 2：使用邻接表表示图 3上的边
| AnimalType 表 | Edge 表 | |||||
| ID | 名称 | 其他列 | EdgeId | 起始顶点 | EndVertex | |
| 1 | 动物 | ... | 1 | 2 | 1 | |
| 2 | 宠物 | ... | 2 | 3 | 1 | |
| 3 | 牲畜 | ... | 3 | 4 | 2 | |
| 4 | 猫 | ... | 4 | 5 | 2 | |
| 5 | 狗 | ... | 5 | 6 | 3 | |
| 6 | 绵羊 | ... | 6 | 7 | 3 | |
| 7 | 牛 | ... | 7 | 6 | 2 | |
| 8 | 杜宾犬 | ... | 8 | 5 | 3 | |
| 9 | 斗牛犬 | ... | 9 | 8 | 5 | |
| 10 | 9 | 5 | ||||
请注意，EdgeId列表示图 3上显示的完全相同的边号。然后应按表 3所示修改Animal表。
表 3：修改后的动物表
| ID | AnimalTypeId | 名称 | 其他列 |
| 1 | 4 | 我的猫 | ... |
| 2 | 8 | 我的狗 | ... |
| 3 | 9 | 我的第二只狗 | ... |
| 4 | 6 | 白绵羊 | ... |
| 5 | 7 | 棕牛 | ... |
- 边的表示与顶点的表示是解耦的，也就是说，
Animal表中不再包含关于其与其他动物关系的信息。此外，Edge表中不包含特定于Animal或AnimalType表的列。因此，只要我们防止来自不同图的顶点 ID 冲突，就没有什么能阻止我们使用同一个Edge表来表示离散且不相关的图。 - 现在可以按任何顺序构造图，例如，您可以先创建边
Cat -> Pet，然后创建Pet -> Animal等，而不会对图的其余部分造成任何干扰。这与物化路径模型不同，在物化路径模型中，图中的任何单一更改都会触发其他行的许多更改。例如，在图构造完成后，在Animal和Pet之间插入另一个顶点。
现在让我们尝试使用新结构获取一些结果。例如，如何从表 2和表 3中显示的表中获取所有牲畜？列表 1中的 SQL 查询可能可以完成这项工作。
列表 1：获取所有牲畜的 SQL 查询
SELECT *
FROM Animal
WHERE AnimalTypeId IN (
SELECT StartVertex
FROM AnimalType
WHERE EndVertex = 3 )
这对于图 2中的类图是有效的。不幸的是，它不适用于图 3，因为并非所有牲畜的后代类都是直接后代。图 3 中的两个子类Doberman和Bulldog也是Livestock，但 SQL 无法识别这一点，导致结果集不正确。虽然我们可以从Edge表中推断出Doberman和Bulldog确实是Livestock，但标准 SQL 没有提供任何语法来在查询中从Edge表中提取此信息，即 SQL 缺乏遍历相关记录的能力。
流行的关系数据库，如 Oracle 和 SQL Server（2005 版本），具有解决标准 SQL 中缺乏递归关系支持的构造：Oracle 有connect by子句，SQL Server 2005 有with语句以及公用表表达式。本质上，它们都采用了过程化的方法来解决问题，只是递归地遍历邻接表以回答递归问题。这种方法的问题在于其过程性。由于它们实际上在后台运行过程，因此在使用此类查询时，例如在join中，查询优化器无法做太多事情。
然而，如果我们存储所有可能的路径（称为传递闭包），那么标准 SQL 就可以恢复正常，并能进行所有强大的查询优化，并且可以利用邻接表上的索引。如果表示的对象数量相当多，这对系统至关重要。表 4显示了包含图 3中图的路径闭包的Edge表。
表 4：带有完整路径列表的边表
（第二组三列指示推断的关系）
| Edge Id | 起始顶点 | EndVertex | Edge Id | 起始顶点 | EndVertex | |
| 1 | 2 | 1 | 11 | 4 | 1 | |
| 2 | 3 | 1 | 12 | 5 | 1 | |
| 3 | 4 | 2 | 13 | 6 | 1 | |
| 4 | 5 | 2 | 14 | 7 | 1 | |
| 5 | 6 | 3 | 15 | 8 | 1 | |
| 6 | 7 | 3 | 16 | 8 | 2 | |
| 7 | 6 | 2 | 17 | 8 | 3 | |
| 8 | 5 | 3 | 18 | 9 | 1 | |
| 9 | 8 | 5 | 19 | 9 | 2 | |
| 10 | 9 | 5 | 20 | 9 | 3 |
严格来说，边 11 到 20 是多余的，因为可以从其他行推断出它们的存在。但是，它们使我们能够使用列表 1中的标准 SQL 查询来获取所有牲畜。由于我们现在将解决方案定为维护 DAG 的传递闭包，因此我们将面临维护具有完整传递闭包的Edge表的实际问题，这并不容易。
我的解决方案基于递归，就像 Oracle 或 SQL Server 一样。然而，我没有在查询时进行递归，而是在插入时进行递归，假设图实际上被查询的次数比修改的次数多（到目前为止，我遇到的所有情况都是如此）。
向图中插入新边
通常，连接两个顶点的新边被假定为连接两个离散的图。我们不能假设Edge的插入顺序。让我们看一下图 4。新边 11，(EdgeId, Start Vertex, End Vertex) -> (11, 1, 2)，实际上连接了两个离散的图。图中的虚线箭头表示那些不是直接连接的边。它们是可以通过现有直接连接推断出来的隐含边，并且在之前的插入过程中已由模型创建。
（请注意，此处仅显示了两个图的一部分）
为了清晰起见，图 4中的图并未完全显示。图中省略了以下内容：
vertex A的出边和vertex B的入边。这是因为它们无法参与在这两个 DAG 之间形成新路径，因为它们与流动方向相反。- 大多数其他顶点和边，这些是图中由虚线表示的隐含边的形成原因。
添加新边以连接两个图会导致创建以下隐含边：
- 将所有作为新边起始顶点（图 4 中的
vertex A）和结束顶点（图 4 中的vertex B）的入边的起始顶点连接起来。 - 将新边的起始顶点（图 4 中的
vertex A）连接到所有作为新边结束顶点（图 4 中的vertex B）的出边的结束顶点。 - 将所有作为起始顶点（图 4 中的
vertex A）的入边的起始顶点，以及所有作为结束顶点（图 4 中的vertex B）的出边的结束顶点连接起来。
在我向您展示完成此操作的代码之前，我们需要修改Edge表以支持删除操作。新的Edge表定义如表 5所示。
表 5：Edge 表的新定义
| 列名 | 类型 | 描述 |
ID | Int | 主键，自动递增 |
EntryEdgeId | Int | 这是指向起始顶点的入边的 ID，它是此隐含边的创建原因；直接边包含与 Id 列相同的值。 |
DirectEdgeId | Int | 这是导致此隐含边创建的直接边的 ID；直接边包含与 Id 列相同的值。 |
ExitEdgeId | Int | 这是指向结束顶点的出边的 ID，它是此隐含边的创建原因；直接边包含与 Id 列相同的值。 |
StartVertex | varchar(36) | 起始顶点 ID（如果您好奇的话，36 是 UUID 在string形式下的长度） |
EndVertex | varchar(36) | 结束顶点 ID |
Hops | Int | 表示需要多少个顶点跳数才能到达路径；对于直接边，此值为零。 |
源 | varchar(150) | 用于指示图创建的上下文的列；如果应用程序中有多个 DAG 需要表示，则很有用。 注意：您需要确保来自不同源的顶点 ID 永远不会冲突；最好是使用 UUID |
列表 2是针对 SQL Server 完成此操作的代码。将其移植到其他数据库应该很简单。如果您这样做，请将其发送给我，以便我将其包含在本文中。
列表 2：用于 SQL Server 插入新边的代码
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE PROC AddEdge
@StartVertexId varchar(36),
@EndVertexId varchar(36),
@Source varchar(150)
AS
BEGIN
SET NOCOUNT ON
IF EXISTS(SELECT Id
FROM Edge
WHERE StartVertex = @StartVertexId
AND EndVertex = @EndVertexId
AND Hops = 0)
BEGIN
RETURN 0 -- DO NOTHING!!!
END
IF @StartVertexId = @EndVertexId
OR EXISTS (SELECT Id
FROM Edge
WHERE StartVertex = @EndVertexId
AND EndVertex = @StartVertexId)
BEGIN
RAISERROR ('Attempt to create a circular relation detected!', 16, 1)
RETURN 0
END
DECLARE @Id int
INSERT INTO Edge (
StartVertex,
EndVertex,
Hops,
Source)
VALUES (
@StartVertexId,
@EndVertexId,
0,
@Source)
SELECT @Id = SCOPE_IDENTITY()
UPDATE Edge
SET EntryEdgeId = @Id
, ExitEdgeId = @Id
, DirectEdgeId = @Id
WHERE Id = @Id
-- step 1: A's incoming edges to B
INSERT INTO Edge (
EntryEdgeId,
DirectEdgeId,
ExitEdgeId,
StartVertex,
EndVertex,
Hops,
Source)
SELECT Id
, @Id
, @Id
, StartVertex
, @EndVertexId
, Hops + 1
, @Source
FROM Edge
WHERE EndVertex = @StartVertexId
-- step 2: A to B's outgoing edges
INSERT INTO Edge (
EntryEdgeId,
DirectEdgeId,
ExitEdgeId,
StartVertex,
EndVertex,
Hops,
Source)
SELECT @Id
, @Id
, Id
, @StartVertexId
, EndVertex
, Hops + 1
, @Source
FROM Edge
WHERE StartVertex = @EndVertexId
-- step 3: A’s incoming edges to end vertex of B's outgoing edges
INSERT INTO Edge (
EntryEdgeId,
DirectEdgeId,
ExitEdgeId,
StartVertex,
EndVertex,
Hops,
Source)
SELECT A.Id
, @Id
, B.Id
, A.StartVertex
, B.EndVertex
, A.Hops + B.Hops + 1
, @Source
FROM Edge A
CROSS JOIN Edge B
WHERE A.EndVertex = @StartVertexId
AND B.StartVertex = @EndVertexId
END
AddEdge过程为每个可能的路径创建一个隐含边，导致出现比实际需要更多的冗余隐含行。因此，可能存在许多行具有相同的Start Vertex和End Vertex值，但具有不同的EntryEdgeId、ExitEdgeId和不同的Hop。实际上，如果我们想构造图一次并只允许添加新边，那么可以消除这些冗余。然而，通过允许重复的隐含行，我们使模型能够支持删除场景。
从图中删除现有边
如前所述，删除必须得到添加操作的支持：添加操作应告知它创建了哪些隐含边。因此，我们应该创建一个清除列表，该列表由以下部分组成：
- 所有边的列表，包括在原始添加操作期间创建的所有边。
- 所有边的列表，包括递归地依赖于第 1 步和第 2 步中所述任何边的边。
如果没有在原始添加操作之后进行其他添加操作，则第 2 步中的列表将为空。但是，可能存在其他添加操作（在原始添加操作之后），这些操作可能已创建依赖于第 1 步所述任何边的隐含边。第 2 步的操作必须是递归的，因为可能存在其他添加操作（在第二次添加操作之后发生）依此类推。列表 3是针对 SQL Server 执行此操作的代码。同样，如果您将此代码移植到其他数据库，请发送给我。
实际上，添加操作也是递归的。然而，我们的代码在AddEdge方法中没有显示任何递归调用或循环。原因在于，添加新的直接边会创建所有隐含边，并使用已创建的隐含边。因此，添加过程有效地以隐含边的形式记忆了图的遍历。
列表 3：从图中删除边的代码，适用于 SQL Server
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE PROC RemoveEdge
@Id int
AS
BEGIN
IF NOT EXISTS( SELECT Id FROM Edge WHERE Id = @Id AND Hops = 0 )
BEGIN
RAISERROR ('Relation does not exists', 16 ,1)
RETURN
END
CREATE TABLE #PurgeList (Id int)
-- step 1: rows that were originally inserted with the first
-- AddEdge call for this direct edge
INSERT INTO #PurgeList
SELECT Id
FROM Edge
WHERE DirectEdgeId = @Id
-- step 2: scan and find all dependent rows that are inserted afterwards
WHILE 1 = 1
BEGIN
INSERT INTO #PurgeList
SELECT Id
FROM Edge
WHERE Hops > 0
AND ( EntryEdgeId IN ( SELECT Id FROM #PurgeList )
OR ExitEdgeId IN ( SELECT Id FROM #PurgeList ) )
AND Id NOT IN (SELECT Id FROM #PurgeList )
IF @@ROWCOUNT = 0 BREAK
END
DELETE Edge
WHERE Id IN ( SELECT Id FROM #PurgeList)
DROP TABLE #PurgeList
END
GO
如何使用 Edge 表
Edge表的使用完全取决于应用程序的需求。为了说明这一点，让我们看一下图 5，它表示应用程序的角色和参与者。这里的箭头应读为“is a member of”。
由于我们已经具备了在表中建模 DAG 的工具，因此构造上述图非常容易。SQL Server 代码列表 4正是这样做的。
列表 4：用于在图 5上创建图的 SQL 代码，适用于 SQL Server
EXEC AddEdge 'HelpDesk', 'Admins', 'AD'
EXEC AddEdge 'Ali', 'Admins', 'AD'
EXEC AddEdge 'Ali', 'Users', 'AD'
EXEC AddEdge 'Burcu', 'Users', 'AD'
EXEC AddEdge 'Can', 'Users', 'AD'
EXEC AddEdge 'Managers', 'Users','AD'
EXEC AddEdge 'Technicians', 'Users', 'AD'
EXEC AddEdge 'Demet', 'HelpDesk', 'AD'
EXEC AddEdge 'Engin', 'HelpDesk', 'AD'
EXEC AddEdge 'Engin', 'Users', 'AD'
EXEC AddEdge 'Fuat', 'Managers', 'AD'
EXEC AddEdge 'G l', 'Managers', 'AD'
EXEC AddEdge 'Hakan', 'Technicians', 'AD'
EXEC AddEdge 'Irmak', 'Technicians', 'AD'
EXEC AddEdge 'ABCTechnicians', 'Technicians', 'AD'
EXEC AddEdge 'Jale', 'ABCTechnicians', 'AD'
这里的好处是，如果我们更改上述语句的顺序，图将以完全相同的结果形成（除了行的 ID，当然）。现在我们可以开始查询我们的Edge表。例如，要获取所有Admins，我们可以编写：
SELECT StartVertex, Hops
FROM Edge
WHERE EndVertex = 'Admins'
这会返回：
StartVertex Hops
--------------- -----------
HelpDesk 0
Ali 0
Demet 1
Engin 1
(4 row(s) affected)
上面的结果显示Demet和Engin是Admins，但间接（Hops值为1表示）。Hops列实际上显示在达到特定路径所需的所需顶点之前必须访问多少个中间顶点，即路径的长度。例如，以下查询显示了Jale的所有成员资格。
SELECT EndVertex, Hops
FROM Edge
WHERE StartVertex = 'Jale'
这会返回：
EndVertex Hops
--------------- -----------
ABCTechnicians 0
Technicians 1
Users 2
(3 row(s) affected)
Jale是Users组的成员。她不是直接成员，因为Hops计数为2，这也表示在从Jale到Users的遍历中有两个中间顶点（ABCTechnicians和Technicians）必须被访问。
Edge 表中的行数
从AddEdge的代码中可以明显看出，Edge表中的行数，至少在理论上，可能会非常大，因为我们维护了传递闭包。实际上，表中的隐含行的数量在很大程度上取决于应用程序。因此，图的复杂性。让我们尝试估计不存在的平均情况的预期边数。假设我们有两个离散图，总共有v个顶点和e条边。平均而言，这两个图将各有...
...每条边的入边或出边。当您查看AddEdge的代码时，可以看到添加一条新边会创建总共：
| 步骤 1 |  | 隐含边 |
| 第二步 | | 隐含边 |
| 步骤 3 |  | 每条直接边的隐含边 |
因此，单次调用AddEdge将创建的总边数：
 | 每条直接边的总边数 |
或
 | 新连接图的总边数 |
表 6列出了一些上述公式的计算示例。
表 6：对某些顶点和边数的样本平均计算
| 图 # | v | e | a | t | T |
| 1 | 10 | 10 | 0.50 | 2.25 | 23 |
| 2 | 50 | 100 | 1.00 | 4.00 | 400 |
| 3 | 100 | 300 | 1.50 | 6.25 | 1,875 |
| 4 | 500 | 1,000 | 1.00 | 4.00 | 4,000 |
| 5 | 1,000 | 5,000 | 2.50 | 12.25 | 61,250 |
从公式和表中都可以看出，随着边与顶点比率的增加，隐含边的数量呈爆炸式增长。这当然是预料之中的。每条边的高顶点数简单地意味着表中要包含的隐含路径要多得多。
一句警告
请注意，为了得出公式和表 6，我们做了许多假设。它们仅用于粗略估计不存在的平均情况下的行数。可以肯定的是，图中预期的行数至少是O(e2)的数量级，甚至可能高得多，因为我们假设边在顶点之间某种程度的均匀分布。理论上，一个公平的 DAG 的传递闭包集的大小使用此模型可能非常大，远超数百万。给定 DAG 的最大边数是图论中的一个研究课题，但我的实际测试表明，存在具有 100 个顶点和 300 条边的 DAG，其传递闭包使用此算法将创建超过 20,000,000 行。
幸运的是，这种任意复杂的图很少见。它们存在于生物分子研究等领域，这些领域反正需要超级计算机。通常，随着 DAG 与平衡树的相似性增加，隐含行的数量会显着减少。此外，我们规定，只要存在任何隐含链接的单个实例，表中的行数就会大大减少（从数百万减少到数千），但代价是失去删除单个边的能力，如前所述。因此，即使是复杂的情况——即网络更改有限——也可以从该模型中受益。在这种情况下，删除后应从头开始重新创建整个图，这并不像看起来那么糟糕。
结论
使用邻接表方法，并增加传递闭包行，使得标准 SQL 可以与有向无环图 (DAG) 模型一起使用。为换取 SQL 的表达能力和非常快速的结果而付出的代价是额外的磁盘空间和额外的插入时间，我认为这对于我目前的问题来说是相当合理的。
参考文献
以下是您在自己的工作中可能会发现有用的相关工作。如果您知道任何其他工作，请告诉我，以便我将其添加到本节。
- Dong Guozhu 等人，“在 SQL 中维护图的传递闭包” http://www.comp.nus.edu.sg/~wongls/psZ/dlsw-ijit97-16.ps
附加许可
如有需要，本文及代码也可根据 GPL 和 LGPL 使用，具体版本取决于上下文。
历史
- 2008 年 1 月 10 日：发布原始版本