在SQL数据库上表示有向无环图（DAG）的模型（译文）

　　使用邻接表方法，通过添加传递闭包行进行扩充，使标准 SQL 能够与有向无环图模型一起使用。但是，需要一些额外的磁盘空间和额外的插入时间。 介绍
　　在我担任软件工程师的这些年里，我一遍又一遍地面临着在关系数据库表中对分层数据建模的相同挑战。我记得的第一个模型是我使用 FoxPro 为一家加工食品公司的产品树创建的模型。
　　然而，对这个问题进行更多思考并最终撰写本文的原因是对 SQL Server 数据库的行级授权模式的反复需求。我当然知道 Microsoft White Paper Implementing Row- and Cell-Level Security in Classified Databases Using SQL Server 2005。我只会说 Microsoft 的解决方案太复杂了，因为他们无法对使用该方法的系统做出假设。因此，他们无法使用许多可能的捷径和简化方法。
　　不过，在本文中，我将仅解决在 SQL 数据库中表示有向无环图 (DAG) 的一般问题，这是我作为基于行的安全问题解决方案的一部分而设计的，因为 DAG 的应用比它多得多只是行级授权。我将发布第二篇文章来补充这一篇文章，并将讨论基于行的安全性的细节，以及在 SQL Server 上的有效实现。
　　在详细介绍之前，让我先解释一下 DAG 是什么。以下是 DAG 上维基百科的摘录：
　　＂在计算机科学和数学中，有向无环图，也称为 DAG，是没有有向环的有向图；也就是说，对于任何顶点 v，不存在从 v 开始和结束的非空有向路径。例如，如果边 u?v 表明 v 是 u 的一部分，那么这样的路径将表明 u 是其自身的一部分，这是不可能的。通俗地说，DAG 单向＂流动＂。
　　有关该主题的更多详细信息，请参阅维基百科上的文章。简而言之，DAG 具有以下属性： DAG 具有有向边，即图中连接顶点（节点）的链接具有方向。方向由箭头表示。 从任意顶点开始，如果我们沿箭头方向遍历顶点，则不可能返回 到 原始顶点。
　　具有上述属性的一个值得注意且熟悉的结构是面向对象编程中的继承层次结构。图 1是一个简单的（不完整的）类图，它恰好是一 棵树 。图中的箭头应读作＂是＂。树是具有一个重要附加限制的 DAG：从一个顶点到另一个顶点可能只存在 一条路径 ，例如，从到 Dog :Animal 只存在一条路Dog -> Pet -> Animal 。这个限制极大地帮助我们在 SQL 数据库中对树建模。
　　图 1：动物类层次结构
　　可以说，在 SQL 数据库中对树结构建模问题的最简单有效的解决方案是一种称为 物化路径 的方法。该模型依赖于字符串标记来表示 从根顶点到每个顶点的完整路径 。标记值由其祖先路径的串联组成。例如，如果根顶点的路径 Animal 是A ，那么 的路径Pet 是A.P. 并且Dog 它的路径是A.P.D. 。本质上就是从根一直到当前顶点的路径。表 1是该表的摘录，用于说明该方法。表 1：来自 Animal 表的示例数据
　　ID
　　小路
　　姓名
　　其他专栏
　　1个
　　装甲运兵车
　　我的猫
　　...
　　2个
　　APD
　　我的狗
　　...
　　3个
　　APD
　　我的第二只狗
　　...
　　4个
　　肌萎缩侧索硬化
　　白羊
　　...
　　5个
　　自动液晶显示器
　　棕牛
　　...
　　物化 路径 方法特别有用，因为使用 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：修改后的动物类层次结构
　　请注意，图 2中的类图不再是一棵树。不同的是，现在一些顶点之间存在多条路径。例如，我们可以使用路径 (Dog -> Pet -> Animal) 和(Dog -> Livestock -> Animal) 从Dog 到Animal 。Dog 但是，一旦我们离开顶点，仍然不可能返回Dog 。所以，它还是符合DAG的定义的。在 OOP 行话中，Dog 据说有多个祖先。[该功能称为多重继承 (MI)。这是一种特殊的 MI，通常被称为可怕的钻石。]
　　Materialized Paths 的简单模式不能用于对图 2中的类图建模。这是因为 Path 列只能用于表示图形上的单个路径，因此仅限于树的建模。请记住，树只有一条通往特定顶点的路径。
　　具有多重继承的类层次结构并不是唯一熟悉的 DAG 案例。还有很多其他人。例如，在 Windows 中，NTFS 文件/文件夹结构（不，它真的不是树）和 Active Directory 用户/组层次结构（这就是我决定解决这个问题的原因）可以使用 DAG 建模。 解决方案
　　有许多出版物解决了 SQL 数据库中的树建模问题。但是，我还没有看到针对更一般化的有向无环图情况的完整解决方案和实现，图 2是其中的一个简单示例。所以，我决定自己解决。
　　我对这个问题的解决方案是基于另一个流行的树问题解决方案的修改版本。该解决方案使用所谓的 邻接 表，即除了实际存储对象（此处为顶点）属性的表之外，还使用存储 边（顶点之间的链接）的辅助表。 为了说明该方法，让我们看一下图 3 ，它是图 2中类层次结构的进一步扩展版本。示例：图 3 Cat -> Pet 中的边可以用元组表示。表 2显示了我们如何使用此模型表示图 3中的 DAG 。(EdgeId, Start Vertex, End Vertex) -> (3, 4, 2)
　　图 3：修改后的动物类层次结构表 2：使用邻接列表表示图 3中的边
　　动物类型表
　　边桌
　　ID
　　姓名
　　其他专栏
　　边号
　　开始顶点
　　端点
　　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个
　　请注意，该列表示与图 3 EdgeId 中所示的边编号完全相同的边。然后应修改该表，如表 3所示。Animal 表 3：改良动物表
　　ID
　　动物类型Id
　　姓名
　　其他专栏
　　1个
　　4个
　　我的猫
　　...
　　2个
　　8个
　　我的狗
　　...
　　3个
　　9
　　我的第二只狗
　　...
　　4个
　　6个
　　白羊
　　...
　　5个
　　7
　　棕牛
　　...
　　表 2和表 3中有一些值得注意的观察结果： 边的表示与顶点的表示是分离的，即表中没有 Animal 关于它与其他动物的关系的任何信息。此外，该Edge 表不包含特定于Animal 或AnimalType 表的列。因此，没有什么可以阻止我们使用同一个Edge 表来表示离散和不相关的图，只要我们防止来自不同图的顶点的 ID 冲突。现在可以按任何顺序构建图形，例如，您可以先创建边 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 和也是，但这对 SQL 来说并不明显，并且会导致不正确的结果集。虽然我们可以推断出并且确实是从表中得出的，但是标准 SQL 没有提供任何语法来在查询中从表中提取这些信息，即 SQL 缺乏遍历相关记录的能力。BulldogLivestockDobermanBulldogLivestockEdgeEdge
　　流行的关系数据库，如 Oracle 和 SQL Server（2005 版本）具有解决标准 SQL 上缺乏递归关系支持的结构：Oracle 具有子句， connect by SQL Server 2005 具有with 语句以及Common Table Expressions。本质上，他们都是对问题采取过程化的方法，简单地递归遍历邻接表，得到递归问题的答案。这种方法的问题在于它们的程序性质。由于它们实际上在后面运行一个过程，因此当使用此类查询时，查询优化器无能为力，例如，在join .
　　但是，如果我们将所有可能的路径（称为 传递闭包 ）存储在 邻接列表 中，标准 SQL 以及所有强大的查询优化和可能使用的 邻接列表 表上的索引都会恢复正常。如果要表示的对象数量相当多，这对于系统来说是至关重要的。包含图 3 Edge 中图形路径闭合的表格显示在表 4中。表 4：具有完整路径列表的边表（第二个三列表示推断的关系）
　　边号
　　开始顶点
　　端点
　　边号
　　开始顶点
　　端点
　　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个
　　严格来说， Edge s 11 到 20 是多余的，因为可以从其他行推断出它们的存在。但是，它们使我们能够使用清单 1中的标准 SQL 查询来获取所有的牲畜。由于我们现在将解决方案作为 DAG 的传递闭包的维护，我们将不得不面对Edge 具有完全传递闭包的表的维护的实际问题，这不是微不足道的。
　　我拥有的解决方案基于递归，Oracle 或 SQL Server 也是如此。但是，我没有将递归推迟到查询时间，而是在插入时进行递归，假设图形实际上被查询的次数多于被修改的次数（这对于我目前遇到的所有情况都是如此）。 向图中插入新边
　　通常，必须假设两个顶点与一条新边的连接是两个离散图的连接。我们不能假定任何插入顺序 Edge 。让我们看一下图 4。新边 11, (EdgeId, Start Vertex, End Vertex) -> (11, 1, 2) , 实际上是连接两个离散图。图中的虚线箭头表示那些不是直接连接的边。相反，它们是隐含的，可以从现有的直接连接中推断出来，并且在之前的插入过程中已经由模型创建。
　　图 4：添加一条新边连接两个图
　　（请注意，此处仅显示两个图的一部分）
　　为了清楚起见，图 4中的图表未完全显示。图中省略了以下内容： 出 边从 vertex A 和入边到vertex B 。这是因为它们不能参与形成这两个 DAG 之间的新路径，因为它们与流向相反。大多数其他顶点和边是图中 隐含 边形成的原因，如虚线箭头所示。
　　添加一条新边以连接两个图会导致创建隐含边： 将所有传入 边的起点处的所有顶点连接到新边的起始顶点（ vertex A 图 4 中）和结束顶点（图 4vertex B 中）。将新边的起始顶点（ vertex A 图 4 中）连接到所有出边到结束顶点（图 4 中）的终点处的所有vertex B 顶点。将所有进入边的起点处的所有顶点连接到起始顶点（图 4 vertex A 中），将所有出边的终点处的所有顶点连接到结束顶点（图 4中）。vertex B
　　在我向您展示执行此操作的代码之前，我们需要修改表 Edge 以支持删除操作。新Edge 表定义如表 5所示。表 5：边缘表的新定义
　　列名
　　类型
　　描述
　　Id
　　Int
　　主键，自增
　　EntryEdgeId
　　Int
　　起始顶点的 传入边 的 ID ，这是此 隐含 边的创建原因；直接边包含与 Id 列相同的值
　　DirectEdgeId
　　Int
　　导致创建此 隐含边的直接边 的 ID ；直接边包含与 Id 列相同的值
　　ExitEdgeId
　　Int
　　来自结束顶点的传出边 的 ID ，这是此 隐含 边的创建原因；直接边包含与 Id 列相同的值
　　StartVertex
　　varchar(36)
　　起始顶点的ID（36是 string 表单中UUID的长度，如果你想知道为什么）
　　EndVertex
　　varchar(36)
　　结束顶点的ID
　　Hops
　　Int
　　指示路径需要多少个顶点跳跃；直接边为零
　　Source
　　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 s，ExitEdgeId s 和不同的Hop s。实际上，如果我们想一次构造图并且只允许添加新边，则可以消除这些冗余。但是，通过允许重复的隐含行，我们使我们的模型能够支持删除场景。从图中删除现有边
　　如前所述，删除必须由加法操作支持：加法操作应该告诉它创建了哪些 隐含边。 因此，我们应该创建一个由以下内容组成的清除列表： 所有边的列表，包含在原始添加操作 期间创建的所有边。 由递归地依赖 于步骤 1 和步骤 2 中描述的任何边的所有边组成的所有边的列表。
　　如果在原始添加操作 之后没有添加操作，则第 2 步的列表将为空。但是，在原始加法操作之后可能还有其他加法操作，这可能已经创建了依赖于步骤 1 中描述的任何边的隐含边。步骤 2 中的操作必须是递归的，因为可能有在 第二次添加操作 之后发生的其他添加操作，依此类推。清单 3是为 SQL Server 执行此操作的代码。同样，如果您将此代码移植到其他数据库，请将其发送给我。
　　实际上，加法运算也是递归的。但是，我们的代码没有显示方法中的任何递归调用或循环 AddEdge 。这样做的原因是添加新的直接边会使用已经创建的隐含边创建所有隐含边。因此，add 过程以隐含边的形式有效地记忆了图的遍历。清单 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 完全取决于应用程序的需要。为了说明这一点，让我们看一下图 5，它表示应用程序的角色和参与者。此处的箭头应理解为＂是……的成员＂。
　　图 5：定义为 DAG 的应用程序角色
　　由于我们已经拥有在表中对 DAG 进行建模的工具，因此构建上图相当容易。清单 4中的 SQL Server 代码就是这样做的。 清单 4：为 SQL Server创建图 5中的图形的 SQL 代码
　　数据库  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 ，这也表明必须访问两个中间顶点（ABCTechnicians 和Technicians ）才能从 遍历Jale 到Users 。边表的行数
　　从代码中可以明显看出，至少在理论上，表 AddEdge 中的行数可以非常大，因为我们维护了传递闭包。实际上，表中隐含的行数在很大程度上取决于应用程序。因此图的复杂性。让我们尝试为不存在的平均情况找到一些预期边数的估计值。假设我们有两个离散图，其顶点和边的总数为。平均而言，这两个图表都会有...Edgeve
　　...传入 或 传出 的每个顶点的边。当您查看 的代码时 AddEdge ，您可以看到添加一条新边将总共创建：
　　步骤1：
　　隐含边
　　第2步：
　　隐含边
　　第 3 步：
　　每个直接边的隐含边
　　因此，单次调用将创建的边总数 AddEdge ：
　　每条直接边
　　或者：
　　新连接图的总边数
　　表6列出了上述公式的一些计算示例。 表 6：一些顶点和边的样本平均计算
　　图#
　　v
　　电子
　　A
　　吨
　　吨
　　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(e 2 ) 的数量级，可能会高很多，因为我们假设顶点之间的边以某种方式 均匀分布。 理论上，公平 DAG 的传递闭包集的大小可以 非常大 有了这个模型，远远超过了数百万。给定 DAG 的最大边数本身是图论中的一个研究课题，但我的实际测试表明，存在具有 100 个顶点和 300 条边的 DAG，其传递闭包使用该算法将创建超过 20,000,000 行。
　　幸运的是，这种 任意复杂的 图表很少见。它们存在于无论如何都需要超级计算机的生物分子研究等领域。一般来说，随着 DAG 与 平衡树 的相似度增加，隐含的行数会 大大 减少。此外，我们限制任何隐含链接的 单个实例的存在，以失去删除单个边的能力 为代价，表中的行数将大大减少（从数百万减少到数千）如前所述。因此，即使是复杂的情况——即网络上的变化是有限的——也可以从这个模型中受益。在这种情况下，每次删除后都应该从头开始重新创建整个图，这并没有看起来那么糟糕。 结论
　　使用 邻接表 方法，通过添加 传递闭 包行进行扩充，使标准 SQL 能够与有向无环图 (DAG) 模型一起使用。 为换取 SQL 的表达能力和非常快的 结果而付出的代价是一些额外的磁盘空间和额外的 插入时间 ，我认为为我手头的问题付出代价是相当合理的。 参考
　　以下是您可能会发现对您自己的工作有用的相关工作。如果您知道任何其他工作，请告诉我，以便我添加到此部分。 Guozhu Dong 等人，＂在 SQL 中维护图的传递闭包＂ http://www.comp.nus.edu.sg/~wongls/psZ/dlsw-ijit97-16.ps
　　作者:
　　Kemal Erdogan
　　France
　　This member has not yet provided a Biography. Assume it＂s interesting and varied, and probably something to do with programming.
　　来源:微信公众号:
　　出处:https://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o