基于有向圖的外鍵沖突解決算法設計與實現

王智鐸，江 波，苗 瑞，趙 慧

（1.中國電子科技集團公司第三十二研究所，上海 201808；2.上海交通大學船舶海洋與建筑工程學院，上海 200240）

0 概述

數據庫作為存儲數據的介質，其包含數量龐大的數據表和復雜的數據關聯。為確保數據庫中數據的一致性，需要在數據表間定義一些約束關系，并引入外鍵（foreign key）概念，用于建立和加強兩個表數據之間的鏈接關系，即通過將表中某一字段或多個字段映射到另一個表中，創建兩個表之間的約束關聯。目前，采用外鍵設計的數據庫已在傳統行業中廣泛使用，其優點主要是從數據庫底層實現了數據的完整性和一致性，軟件底層數據庫開發與軟件應用層開發相對透明，上層應用開發人員無需完全了解數據庫設計規約。隨著大數據時代的到來，互聯網的數據容量呈現指數級增長，傳統行業的應用軟件逐漸轉向互聯網應用模式。由于外鍵字段執行寫入操作時，需實現外鍵約束邏輯，對涉及外鍵校驗的數據表加同步鎖。如果寫入操作不按照某種順序執行，則造成外鍵校驗不通過。因此，互聯網行業應用不推薦使用外鍵。例如，數據表A關聯數據表B，在用戶執行寫入操作時，新增表A數據的操作應在新增表B數據的操作之后，刪除表A數據的操作應在刪除表B的操作之前。

為滿足大數據時代用戶新需求，需要將通過客戶端訪問的模式轉向通過瀏覽器訪問的模式。數據表的數據量逐漸擴增且存在極為復雜的多表多字段外鍵依賴關系。在搭建數據庫集群實現數據同步過程中，極易出現因外鍵沖突導致同步業務困難問題。如果重新設計底層數據庫結構，消除已有外鍵依賴的數據表必然大幅增加開發成本。傳統的解決方法是通過遞歸暴力查找外鍵沖突，此方法需反復訪問數據庫來查找外鍵依賴，造成IO操作頻繁，影響了整體業務的性能。

外鍵識別是解決外鍵沖突的開始，通過外鍵字段的數據類型是否為所述外鍵關系中標識可定義外鍵關系［1-3］。文獻［4］提出一種自動檢測外鍵約束關系的算法，將外鍵定義為唯一列的組合和包含依賴項集合的子集。然而，此方法只適用于數據表的單列的外鍵檢測，并不適用于存在多列的外鍵關聯的業務場景。文獻［5］提出一種識別多列外鍵的算法，通過評估外鍵的相關性、列名以及數據的最大值最小值來查找外鍵關系。

隨著人工智能技術的興起，研究人員使用機器學習算法檢測傳統數據庫的外鍵關系［6-8］。文獻［9］介紹一種采用機器學習檢測關系型數據庫外鍵依賴的方法，包括數據表字段名的相似度和字段數據的平均長度等，被數據庫廠商廣泛應用于數據庫外鍵關系檢測。同時，多列外鍵依賴關系機器學習檢測算法受到人們重視。文獻［10］提出一種機器學習算法確定關系型數據庫的數據表中主鍵與外鍵關系的方法，但該方法僅適用于外鍵與主鍵的關系檢測，并未考慮外鍵沖突的情況，以及解決外鍵沖突的方法。文獻［11］提出一種基于外鍵沖突消除的外鍵檢測算法，該方法定義了外鍵依賴關系的圖結構模型，以圖的層級順序消除外鍵沖突，但該方法只適用于網絡表格，其外鍵關系的定義與傳統的關系型數據庫相比存在明顯區別。然而，現有的外鍵沖突解決算法僅提出了理論依據，或僅能解決某些應用場景的實現，而未提出一種通用的算法，來滿足傳統應用軟件兼容互聯網應用模式且不改變數據庫表結構設計等需求。

此外，研究人員對于異構數據庫的數據遷移［12］與數據同步［13-14］問題也展開了廣泛的研究。由于其數據遷移過程涉及大批量讀寫操作，外鍵沖突問題會造成寫入數據操作困難，因此解決數據庫外鍵沖突是實現異構數據庫同步的重要技術之一。文獻［15］介紹了一種異構數據庫的同步解決方案，提出存在外鍵關聯表的模式轉換同步方案，但該方案僅考慮到外鍵依賴主鍵字段。文獻［16］提出一種異構數據庫多種數據同步技術方案，但該方案中提到的觸發器同步、快照同步、時間戳同步均需要變更數據表結構。文獻［17］介紹一種利用有向圖模型解決分布式控制系統中局部信息一致性問題的方法，該方法將多智能體系統數據建模為有向圖模型，從而得出完全分布式的一致性算法。此外，一些關于外鍵依賴的異常檢測方法也可以應用于解決外鍵沖突問題［18-20］。

本文提出一種外鍵關聯有向圖模型算法，將數據表之間的外鍵關系以有向圖的形式展現，方便分析造成外鍵沖突的原因。根據數據庫提供的SQL語句實現有向圖生成算法，并將有向圖轉化為鄰接矩陣，為解決外鍵沖突提供元數據。在此基礎上，提出以鄰接矩陣作為輸入數據、以拓撲排序算法作為數據處理方法的原子性序列生成算法，解決外鍵沖突問題。

1 數據表與外鍵的有向無環圖表征法

1.1 有向無環圖模型生成

外鍵關系檢測是解決外鍵沖突的必要條件，因此在介紹外鍵沖突解決算法前，本節首先將數據表之間的外鍵依賴關系通過有向圖直觀展現。表1所示為本文中的符號描述。

表1 符號描述Table 1 Symbol description

假定ta為要解決外鍵沖突的表，ta依賴于tb、tc、td、te。圖1給出了該外鍵依賴關系的有向無環圖示例，在后續的論述中，均以此為例。

圖1 外鍵有向圖模型Fig.1 Directed graph model of foreign key

數據表外鍵依賴關系轉化為有向無環圖方法的步驟如下：

步驟1獲取數據庫的數據表集合T=｛ta，tb，tc，td，te｝，令T=V。

步驟2獲取ti.fk與tj.rfk，得到Referenc（eti.fk，tj.rfk）。

步驟3令ei=Reference（ti.fk，tj.rfk），即一條從ti指向tj的有向邊，構建G（V，E）。

步驟4由數據庫的外鍵約定可知，外鍵不存在循環依賴，即不存在環，G=DAG。

1.2 鄰接矩陣生成算法

根據1.1節給出的將數據表之間的外鍵關聯轉換為有向圖模型方法，DAG可以直觀地展現外鍵依賴關系，但是DAG不能直接作為應用程序的輸入數據交給計算機處理。因此，通常會將DAG轉化為鄰接矩陣，以方便數據存儲和外鍵沖突解決處理。本節的主要研究工作集中在如何通過程序執行SQL語句獲取T和Reference數據，以及設計并實現將外鍵依賴關系轉化為鄰接矩陣的方法。以oracle數據庫為例，將DAG轉化為鄰接矩陣的SQL代碼如下：

本文的研究重點在于如何通過SQL語句生成鄰接矩陣，該SQL語句的詳細功能如下：

1）從user_constraints查詢parent和child數據，user_constraints是主鍵、外鍵等約束記錄。查詢結果如表2所示。

表2 笛卡爾積映射表Table 2 Cartesian product mapping table

2）對user_constraints做笛卡爾積自鏈接inner join生成以數據庫所有表作為節點集合T的無向圖，如圖2所示，圖中任意兩節點間均一步可達，tn代表不存在外鍵的冗余節點。

圖2 節點集合T 的無向圖Fig.2 Undirected graph of node set T

3）以constraint_name列等于r_constraint_name列作為自連接映射關聯的過濾條件，篩選滿足該條件的邊；使用where關鍵字作為過濾條件，過濾掉不包含fk、rfk的數據表，即移除圖2中無關的節點和邊，過濾后的結果如圖3所示。

圖3 過濾后的結果Fig.3 Filtered result

4）確定存在外鍵依賴的表，將無向圖轉為有向圖。其中，connect by表示將每一行的數據按鏈式的層次關系檢索，prior關鍵字表示指針的指向，放置在連接關系兩列中的某一列，prior所在的一側表示入度，另一側表示出度。

5）用start with關鍵字來標識查找圖型結構的起始節點，需要執行寫入操作的起始節點，即程序的輸入。

經過上述流程，圖2所示的無向圖最終轉化為圖1所示的有向圖。完整的SQL語句的執行結果如表3所示，其中parent和child集合為T。以T=｛ta，tb，tc，td，te｝為行和列建立鄰接矩陣表。首先將鄰接矩陣表的數據均初始化為0，然后在表3查找Reference，如果存在Reference=｛ti，t｝j，則將鄰接矩陣的第i行、第j列的元素更新為1。圖1的鄰接矩陣如表4所示。

表3 約束記錄Table 3 Reference record

表4 鄰接矩陣Table 4 Adjacency matrix

2 外鍵沖突解決算法

根據外鍵有向圖模型，分析寫入操作的執行順序可得出以下結論：執行插入操作需滿足插入節點的出度為0；執行刪除操作需滿足刪除節點的入度為0；更新操作可視為插入新數據，且刪除舊數據。更新前的數據為刪除的舊數據，更新后的數據為插入新數據。

數據之間的外鍵約束關系可模型化為遞歸遍歷的層次關系。在遞歸遍歷的執行過程中，還需要判斷當前訪問節點的入度和出度。為實現上述功能，本文提出一種基于拓撲排序［21-22］的鄰接矩陣遍歷算法，具體步驟如下：

步驟1指定用戶需要執行寫入操作數據表為起始節點。

步驟2從當前節點開始，訪問該節點，并標記該節點為已訪問過的節點，防止遞歸回溯出現重復訪問。

步驟3判斷該節點是否存在未被訪問的子節點，若無，則執行步驟4，若有，則判斷未被訪問的節點入度是否為0。若入度為0，則訪問該子節點，跳轉到步驟2，否則執行步驟5。

步驟4如果該節點為根節點，則訪問完畢，否則執行步驟3。

步驟5標記該節點的入度為1，跳轉到步驟3。

綜上所述，掃描整個圖的過程就是有向無環圖（DAG）的拓撲排序過程［23］，其滿足每個節點出現且僅出現一次。若存在一條從節點A到節點B的路徑，那么在序列中頂點A出現在頂點B之前。如果用戶執行插入操作，則需要滿足入度為0，插入操作的順序即為拓撲排序的正序；如果執行刪除操作，則需要滿足出度為0，刪除操作的順序即為拓撲排序的倒序。

以圖1為例，如果對ta執行插入操作，首先判斷該有向圖中出度為0的點，掃描到td的出度為0，則先將td存入輸出結果隊列，從圖中移除td節點。然后重復該操作，遞歸移除出度為0的節點，直到遍歷完圖中的全部節點為止。如果對ta執行刪除操作，只需要掃描入度為0的節點，其余步驟一致，或逆序遍歷執行插入操作的輸出結果均可。執行插入操作的輸出結果集合INSERT=｛td，tc，te，tb，ta｝，執行刪除操作的輸出結果集合DELETE=｛ta，tb，tc，td，te｝。

3 實驗結果與分析

3.1 實驗環境

實驗硬件環境采用Intel?CoreTMi5-9400 CPU @2.9 GHz、16 GB DDR5內存和2 TB機械硬盤；軟件環境采用Microsoft Windows 10操作系統oracle數據庫、Java Development kit 8開發工具包、NaviCat數據庫可視化工具、jprofiler性能測試工具和IntelliJ IDEA開發工具等。

3.2 評估指標

實驗將CPU利用率和內存消耗作為性能評估依據。CPU利用率是反映系統忙閑程度的指標。CPU利用率穩步上升，且數值不會過高，表明程序運行狀態良好。當CPU利用率在某一時刻開始下降時，表明IO線程開始執行訪問數據庫，占用了CPU線程的工作；內存消耗是反映系統資源占用情況的指標。內存占用越高，表明程序運行過程中資源占用越多。當內存在某一時刻開始減少，表明jvm的垃圾回收線程開始工作，清理程序運行中不需要使用的資源。垃圾回收線程工作需要暫停CPU線程的正常運行。若CPU利用率和內存消耗出現頻繁的抖動現象，則表明CPU線程處于阻塞狀態，應用程序會出現明顯的卡頓，影響用戶體驗。

3.3 結果對比與分析

為驗證算法的準確性與泛化性，本文實驗在不同的數據庫應用場景下，對本文算法和傳統算法進行性能比較。實驗1為某學校的OA系統，實驗采集了該管理系統的20張表，表中的數據主要為文本格式，有5張存在外鍵沖突的數據集；實驗2為某公司的業務數據管理系統集群，實驗采集了該數據庫的20張表，表中的數據主要為文本和圖片格式，有100張存在外鍵沖突的數據集；實驗3為某公司的分布式多媒體文件存儲系統，實驗采集了該數據庫的500張表，表中的數據主要為音頻和視頻格式，有200張存在外鍵沖突的數據集。

從圖4可以看出：本文外鍵沖突解決算法的運行時間約為1 s，CPU占用率在運行期間內逐漸增長，最高值不超過40%，內存占用不超過50 MB，運行期間無垃圾回收，該結果說明應用程序訪問數據庫的開銷可忽略不計；傳統暴力枚舉算法的運行時間約為9 s，CPU占用率的峰值接近50%，內存占用約為70 MB，運行期間觸發一次輕量級垃圾回收，該結果說明暴力枚舉算法訪問數據庫的I/O操作影響了CPU線程的正常工作，出現平緩的抖動。

圖4 OA系統數據集Fig.4 OA system dataset

從圖5可以看出：本文外鍵沖突解決算法的運行時間約為2 s，CPU占用率在運行期間逐漸增長后趨于平穩，最高值不超過40%，內存占用不超過50 MB，程序運行期間無垃圾回收，該結果說明訪問數據庫的I/O操作略影響CPU工作線程；傳統暴力枚舉算法的運行時間約為20 s，CPU占用率出現頻繁的波動，最高值超過50%，內存占用約為125 MB，運行期間多次觸發垃圾回收。該結果說明暴力枚舉算法的CPU工作線程被多次阻塞，出現較為頻繁的抖動，應用程序出現卡頓。

圖5 數據管理系統數據集Fig.5 Database management system dataset

從圖6可以看出：本文外鍵沖突解決算法的運行時間約為8 s，CPU占用率在運行期間出現略微抖動，最高值不超過40%，內存占用不超過100 MB，程序運行期間觸發一次垃圾回收，該結果說明外鍵沖突解決算法訪問數據庫的I/O操作略微阻塞了CPU工作線程；傳統暴力枚舉算法的運行時間約40 s，CPU占用率在運行期間出現極為頻繁的抖動，最高值超過50%，內存占用超過150 MB，運行期間多次觸發垃圾回收，該結果說明暴力枚舉算法的CPU線程頻繁處于阻塞狀態，應用程序出現明顯的卡頓，影響用戶體驗。

圖6 分布式多媒體數據庫數據集Fig.6 Distribute multimedia database dataset

綜上所述，本文提出的基于有向圖的外鍵沖突解決算法在運行時間、CPU占用率和內存消耗上均明顯優于暴力枚舉算法。

4 結束語

本文提出一種解決外鍵約束的有向圖模型生成算法，其中有向圖模型以某一數據表為起點，通過拓撲排序遍歷與該表有外鍵關聯的數據表，從而得出用戶數據表寫入操作執行的順序，保證存在外鍵關聯數據表的寫入操作的原子性。實驗結果證明了基于有向圖的外鍵沖突解決算法比暴力枚舉算法在性能上有著明顯優勢。下一步將對數據庫集群化分布式數據同步模塊的外鍵沖突解決方案進行研究，以優化時間復雜度，提升算法的魯棒性。