使用邻接表方法，通过添加传递闭包行进行扩充，使标准 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 具有以下属性：

1. DAG 具有有向边，即图中连接顶点（节点）的链接具有方向。方向由箭头表示。
2. 从任意顶点开始，如果我们沿箭头方向遍历顶点，则不可能返回到原始顶点。

具有上述属性的一个值得注意且熟悉的结构是面向对象编程中的继承层次结构。图 1是一个简单的（不完整的）类图，它恰好是一棵树。图中的箭头应读作“是”。树是具有一个重要附加限制的 DAG：从一个顶点到另一个顶点可能只存在一条路径，例如，从到Dog:Animal只存在一条路Dog -> Pet -> Animal。这个限制极大地帮助我们在 SQL 数据库中对树建模。

图 1：动物类层次结构

可以说，在 SQL 数据库中对树结构建模问题的最简单有效的解决方案是一种称为物化路径的方法。该模型依赖于字符串标记来表示从根顶点到每个顶点的完整路径。标记值由其祖先路径的串联组成。例如，如果根顶点的路径Animal是A，那么 的路径Pet是A.P.并且Dog它的路径是A.P.D.。本质上就是从根一直到当前顶点的路径。表 1是该表的摘录，用于说明该方法。

表 1：来自 Animal 表的示例数据

物化路径方法特别有用，因为使用 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中类层次结构的进一步扩展版本。示例：图 3Cat -> Pet中的边可以用元组表示。表 2显示了我们如何使用此模型表示图 3中的 DAG 。(EdgeId, Start Vertex, End Vertex) -> (3, 4, 2)

图 3：修改后的动物类层次结构

表 2：使用邻接列表表示图 3中的边

请注意，该列表示与图 3EdgeId中所示的边编号完全相同的边。然后应修改该表，如表 3所示。Animal

表 3：改良动物表

表 2和表 3中有一些值得注意的观察结果：

1. 边的表示与顶点的表示是分离的，即表中没有Animal关于它与其他动物的关系的任何信息。此外，该Edge表不包含特定于Animal或AnimalType表的列。因此，没有什么可以阻止我们使用同一个Edge表来表示离散和不相关的图，只要我们防止来自不同图的顶点的 ID 冲突。
2. 现在可以按任何顺序构建图形，例如，您可以先创建边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 bySQL Server 2005 具有with语句以及Common Table Expressions。本质上，他们都是对问题采取过程化的方法，简单地递归遍历邻接表，得到递归问题的答案。这种方法的问题在于它们的程序性质。由于它们实际上在后面运行一个过程，因此当使用此类查询时，查询优化器无能为力，例如，在join.

但是，如果我们将所有可能的路径（称为传递闭包）存储在邻接列表中，标准 SQL 以及所有强大的查询优化和可能使用的邻接列表表上的索引都会恢复正常。如果要表示的对象数量相当多，这对于系统来说是至关重要的。包含图 3Edge中图形路径闭合的表格显示在表 4中。

表 4：具有完整路径列表的边表（第二个三列表示推断的关系）

严格来说，Edges 11 到 20 是多余的，因为可以从其他行推断出它们的存在。但是，它们使我们能够使用清单 1中的标准 SQL 查询来获取所有的牲畜。由于我们现在将解决方案作为 DAG 的传递闭包的维护，我们将不得不面对Edge具有完全传递闭包的表的维护的实际问题，这不是微不足道的。

我拥有的解决方案基于递归，Oracle 或 SQL Server 也是如此。但是，我没有将递归推迟到查询时间，而是在插入时进行递归，假设图形实际上被查询的次数多于被修改的次数（这对于我目前遇到的所有情况都是如此）。

向图中插入新边

通常，必须假设两个顶点与一条新边的连接是两个离散图的连接。我们不能假定任何插入顺序Edge。让我们看一下图 4。新边 11, (EdgeId, Start Vertex, End Vertex) -> (11, 1, 2), 实际上是连接两个离散图。图中的虚线箭头表示那些不是直接连接的边。相反，它们是隐含的，可以从现有的直接连接中推断出来，并且在之前的插入过程中已经由模型创建。

图 4：添加一条新边连接两个图
（请注意，此处仅显示两个图的一部分）

为了清楚起见，图 4中的图表未完全显示。图中省略了以下内容：

1. 出边从vertex A和入边到vertex B。这是因为它们不能参与形成这两个 DAG 之间的新路径，因为它们与流向相反。
2. 大多数其他顶点和边是图中隐含边形成的原因，如虚线箭头所示。

添加一条新边以连接两个图会导致创建隐含边：

1. 将所有传入边的起点处的所有顶点连接到新边的起始顶点（vertex A图 4 中）和结束顶点（图 4vertex B中）。
2. 将新边的起始顶点（vertex A图 4 中）连接到所有出边到结束顶点（图 4 中）的终点处的所有vertex B顶点。
3. 将所有进入边的起点处的所有顶点连接到起始顶点（图 4vertex A中），将所有出边的终点处的所有顶点连接到结束顶点（图 4中）。vertex B

在我向您展示执行此操作的代码之前，我们需要修改表Edge以支持删除操作。新Edge表定义如表 5所示。

表 5：边缘表的新定义

清单 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值，但具有不同的EntryEdgeIds，ExitEdgeIds 和不同的Hops。实际上，如果我们想一次构造图并且只允许添加新边，则可以消除这些冗余。但是，通过允许重复的隐含行，我们使我们的模型能够支持删除场景。

从图中删除现有边

如前所述，删除必须由加法操作支持：加法操作应该告诉它创建了哪些隐含边。因此，我们应该创建一个由以下内容组成的清除列表：

1. 所有边的列表，包含在原始添加操作期间创建的所有边。
2. 由递归地依赖于步骤 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：一些顶点和边的样本平均计算

从公式和表格中可以明显看出，随着边与顶点之比的增加，隐含边的数量呈爆炸式增长。这当然是预料之中的。每个顶点的大量边仅仅意味着表中包含更多的隐含路径。

警告的话

请注意，在生成公式和表 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