使用鄰接表方法，通過添加傳遞閉包行進行擴充，使标準 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中類層次結構的進一步擴充版本。示例：圖 3Cat -> 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個 |
請注意，該清單示與圖 3EdgeId中所示的邊編号完全相同的邊。然後應修改該表，如表 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 bySQL Server 2005 具有with語句以及Common Table Expressions。本質上，他們都是對問題采取過程化的方法，簡單地遞歸周遊鄰接表，得到遞歸問題的答案。這種方法的問題在于它們的程式性質。由于它們實際上在後面運作一個過程，是以當使用此類查詢時，查詢優化器無能為力，例如，在join.
但是，如果我們将所有可能的路徑（稱為傳遞閉包）存儲在鄰接清單中，标準 SQL 以及所有強大的查詢優化和可能使用的鄰接清單表上的索引都會恢複正常。如果要表示的對象數量相當多，這對于系統來說是至關重要的。包含圖 3Edge中圖形路徑閉合的表格顯示在表 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個 |
嚴格來說，Edges 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頂點。
- 将所有進入邊的起點處的所有頂點連接配接到起始頂點（圖 4vertex 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值，但具有不同的EntryEdgeIds，ExitEdgeIds 和不同的Hops。實際上，如果我們想一次構造圖并且隻允許添加新邊，則可以消除這些備援。但是，通過允許重複的隐含行，我們使我們的模型能夠支援删除場景。
從圖中删除現有邊
如前所述，删除必須由加法操作支援：加法操作應該告訴它建立了哪些隐含邊。是以，我們應該建立一個由以下内容組成的清除清單：
- 所有邊的清單，包含在原始添加操作期間建立的所有邊。
- 由遞歸地依賴于步驟 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