數據庫復雜網絡構造算法及特征分析

李春芳 劉連忠 劉振國

①(北京航空航天大學自動化科學與電氣工程學院 北京 100191)

②(北京航空航天大學計算機學院 北京 100191)

③(河北體育學院網絡中心 石家莊 050041)

1 引言

數據庫是各類管理信息系統(Management Information System, MIS)的數據核心。隨著軟件規模擴大，數據庫的規模和關聯復雜性相應增加。軟件網絡是軟件復雜系統的骨架，而數據庫復雜網絡是業務系統內部關聯性的骨架。在頂層設計中，主要是將業務內部的關聯性映射為數據表之間的關聯性，盡管業務系統的功能不可能全部在數據庫設計中實現，但是顯而易見，優化的數據庫關聯設計，能盡可能多地覆蓋業務邏輯，減少系統實現的復雜性和代碼量。由于在數據表的基本字段確定后，非主鍵和非外鍵字段的添加和刪除，不會影響其他的關聯性，因此通過主鍵和外鍵建立數據表之間的復雜網絡，作為對MIS系統宏觀層面的描述是合理的。

從文獻看，復雜網絡的解釋為，從實際復雜系統抽取的網絡結構，具有明顯的“無標度”和“小世界”特性，其網絡特征介于隨機網絡和規則網絡之間，即不是完全隨機，也不完全規則。軟件是一類人工復雜系統，復雜網絡理論引入軟件工程來描述和度量軟件的復雜性，形成了軟件網絡[1]。軟件網絡主要探索了軟件包級[2]、類級[3-6]、方法級[4-6]的網絡構造和統計特征，以及軟件的動態運行環境網絡[7]，從復雜網絡角度探索了軟件的宏觀結構和軟件度量[8,9]以及軟件網絡的應用[10-12]，然而對軟件網絡的分支數據庫復雜網絡的研究較少。何克清等認為軟件網絡沒有被準確定義，泛指從軟件系統中抽取的網絡結構，該結構具有復雜網絡的特征[1]。以數據庫中表作為節點，將外鍵到主鍵形成的參照依賴作為有向邊，MIS系統的數據庫可以建模成一個有向圖，本文發現該結構也具有“小世界”和“無標度”特征，可以認為，數據庫復雜網絡是軟件網絡的一個分支，籠統指從數據庫中抽取的網絡結構，研究數據層關聯形成的網絡統計特性。

早在 1983年，文獻[13]利用超圖(hyper networks)超網絡來描述數據庫，其節點是一個數據模式的所有數據表的字段集合，一個數據表定義為一個超邊(hyper edge)，它能連接多于兩個節點。由于超圖的可視化信息不便于直觀理解，遠不如復雜網絡描述數據庫內部關聯更直接。

盡管一個MIS系統的數據庫網絡可能僅有幾十到上千的節點，但是其關聯復雜性足以讓軟件開發人員難以應對，需要 CASE(Computer Aided Software Engineering)工具輔助描述其復雜性。CASE工具，如 Rational Rose, PowerDesigner,Microsoft Visio, Visual Paradigm等均采用了數據庫關系圖描述數據表間的關聯，但是其抽象粒度不夠，開發人員無法看到數據庫網絡更宏觀的視圖，難以駕馭大型系統的數據庫設計。數據庫關系圖沒有從復雜網絡的角度統計其網絡結構特性，本文從更抽象的復雜網絡的角度研究MIS系統數據模式的關聯，以更加“骨感”的形式來描述和度量數據層的復雜性，使軟件開發人員能掌控數據關聯的概貌。

2 形式化表示

數據庫完整性指數據的正確性和相容性，完整性包括域、實體、參照和用戶定義完整性，其完整性設計就是約束設計。在大型MIS系統設計中，參照完整性是核心，它集中體現了業務邏輯，也是軟件設計復雜性的根源之一，本文將數據表間的參照完整性建模為復雜網絡，以更簡潔的方式描述其復雜關聯性。完整性約束可以通過數據庫管理系統(DataBase Management System, DBMS)或應用程序實現，通過DBMS實現的參照完整性即主外鍵關聯，而由應用軟件實現的參照完整性本文定義為語義隱性關聯，簡稱語義關聯，它隱含表示了數據表主外鍵之間的參照關系。

大量的開發經驗表明，外鍵關聯和語義關聯各有優勢，表1列出了兩種關聯的比較，在本文分析的9個數據模式中，4個采用了外鍵，5個采用了隱性語義關聯。外鍵關聯采用數據庫集中管理數據關系，在海量數據查詢情況下跨表查詢性能比語義關聯差。由于DBMS能自動維護數據的完整性，因此在故障發生時，能夠保證數據的一致性，而語義關聯可能會引入不一致數據。在開發階段，由于系統的不完備性，外鍵會羈絆代碼實現，而語義關聯需要增加代碼來維護參照引用數據的一致性。CASE工具支持外鍵關聯和部分語義關聯的圖結構分析。

表1 外鍵關聯和語義關聯比較

大部分的DBMS系統和逆向工程工具都采用了數據庫關系圖，其節點是數據表結構信息，邊是外鍵到主鍵的關聯依賴，因此在數據庫復雜網絡構造上用數據表作為節點，外鍵關系作為邊是合理的。在已有的數據庫關系圖中，節點信息復雜，然而對復雜性起關鍵作用的是主鍵和外鍵，其他非主鍵和非外鍵字段的添加和刪除對關聯復雜性沒有影響，因此進一步化簡節點是可能的。

數據庫復雜網絡(DataBase Complex Networks,DBCN)G={V,E} 是從數據庫模式中抽取的有向網絡模型，V={v1,v2,…,vn}是節點集，代表數據庫模式中的數據表，E={(vi,vj)|i,j=1,2,…,n} 是有向邊集合，代表一個數據表外鍵(或隱含外鍵)到其它數據表主鍵的依賴。

基于復雜網絡的統計參數[1]，定義如下特征參數：

(1)節點數N：數據表個數；

(2)邊數E；

(3)平均最小路徑長度L；

(4)平均聚類系數C；

(5)平均出度/入度Di/Do；

(6)節點對可達率R：定義為有向網絡上任意不同的兩個節點之間存在的可達路徑總數除以N×(N-1),R是對內部關聯緊密程度的一種度量，網絡內聚度越高，R越大，如果系統內部存在級聯刪除和級聯更新，在數據庫內部傳遞的可能性越大；

(7)網絡連接率S：定義為最大連通圖上的節點數除以總節點數。

在DBCN上，節點的入邊是其它數據表的外鍵(或隱含外鍵)字段到該數據表主鍵的引用，節點的出邊是該數據表的外鍵(或隱性外鍵)到其它數據表主鍵的引用。數據庫主鍵和字段的關系是一對多的關系，主鍵可能是一個字段，或者多個字段，即聯合主鍵，絕大多數是一個字段，在聯合主鍵情況下每個獨立字段都是外鍵，即到其他表主鍵的引用。因此入邊都是對節點主鍵的引用，而出邊是對其他節點主鍵的引用。

由于一個數據表中可能有多于一個字段引用其它表的同一個主鍵字段，因此DBCN是一個可能包含重邊的有向圖，在以下的構造算法中去掉了重邊，只考慮簡單有向圖構造的網絡。

3 構造算法

3.1 基于主外鍵的構造算法

本節研究了基于復雜網絡的數據庫關聯分析技術，實現對Oracle, MySQL, SQLServer數據庫中表的元數據的關聯分析。針對基于數據庫主外鍵的關聯和無外鍵的語義隱性關聯提出了兩種網絡構造算法。

算法1基于主外鍵的構造算法(FK-DBCN)(1)查詢系統表讀取一個數據模式下的所有數據表名稱，作為網絡節點信息；

(2)查詢系統約束表，讀取數據模式的所有外鍵約束，作為從一個數據表節點(外鍵)到參照表節點(主鍵)的有向邊信息。

用算法 1構造了非開源軟件學校管理系統Yundl的數據庫網絡，其DBMS為SQLServer，它采用了外鍵實現參照完整性約束，顯示度排名前三位的節點是 tbStudentBasis, tbTeacherBasis和tbYearBasis，反映該系統中所有的關系中最重要的是學生、教師在學年中的各種關系，這種直接宏觀的業務邏輯表示對于變更的開發團隊、軟件的二次開發以及更新維護非常重要，可以縮短增量開發時間。

3.2 基于語義關聯的構造算法

由于DBCN內部關聯的復雜性，很多的軟件開發實踐表明，業務的主、外鍵關聯往往通過程序內部映射實現，而不采用DBMS本身的完整性約束，從而避開某些關聯控制的難題。實際上，無論在軟件的設計還是實現上，關聯引起的復雜性無法回避。開源軟件網絡與主機監控系統 Zabbix的數據庫關聯采用了 MySQL數據庫，內部無外鍵約束。從對Zabbix的分析中發現，盡管沒有主外鍵，但是從規范的數據表字段命名規則可以推理語義隱性關聯，進而推理出關聯關系，而CASE工具PowerDesigner也采用這種語義推理。例如：在Zabbix數據庫中有兩個數據表History和Items，其中History有3個非主鍵的字段itemid, clock和value，在Items數據表中僅有一個主鍵itemid，那么可以推出表History到表Items有一個隱性外鍵關聯。根據數據表的字段命名規則推理出外鍵約束，進而構造DBCN的有向邊，這種推理一般近似正確，主要取決于隱性主外鍵的命名規則。根據語義隱性關聯設計了算法2。

算法2基于語義隱性關聯的DBCN構造算法(HFK-DBCN)

(1)查詢一個數據模式的所有數據表名稱，作為網絡節點信息，節點數為n；

(2)查詢每個數據表節點 Nodei(i=1,2,…,n)的非主鍵字段個數fc和名稱FFields[1,2,…,fc]；

(3)查詢每個數據表節點 Nodej(j=1,2,…,n,且j≠i)所有主鍵字段個數pc和名稱 PFields[1,2,…,pc]；

(4)如果 FFields[1,2,…,fc]的某個字段等于PFields[1,2,…,pc]中某個字段，則添加一條從節點i到節點j的邊。

針對語義關聯下，通過算法 2仍不能構造DBCN的情況，提出了HFK-DBCN+算法。以開源課程管理系統 Moodle為例，其中所有表的主鍵均采用id命名，通過HFK-DBCN檢索不到任何邊信息，但是在大量的引用表中采用了“數據表名稱”+“id”方式引用主鍵表中的字段，例如在mdl_user表中主鍵為 id，而在引用表 mdl_course_display等多個數據表中均使用userid隱性關聯。

算法2+擴展的語義隱性關聯的數據庫復雜網絡構造算法(HFK-DBCN+)

(1)查詢一個數據模式的所有數據表名稱，作為網絡節點信息，節點數為n；

(2)查詢每個數據表節點 Nodei(i=1,2,…,n)的非主鍵字段個數fc和名稱FFields[1,2,…,fc]；

(3)查詢每個數據表節點 Nodej(j=1,2,…,n,且j≠i)所有主鍵字段個數pc和名稱PFields[1,2,…,pc],增加其擴展的可能主鍵字段名 PFields[pc+1,…,pc+e]；

(4)如果 FFields[1,2,…,fc]的某個字段等于PFields[1,…,pc+e]中某個字段，則添加從節點i到節點j的一條邊。

在Moodle中，所有數據表名以前綴“mdl_”開始，去掉前綴后，人工分析后增加了4項可能匹配的主鍵字段名，4條規則如下：取出表示數據表的名字，例如表 mdl_course中原僅有一個主鍵“id”，增加了“course”；取出表示數據表的名字，直接加“id”，例如表mdl_user中原僅有一個主鍵“id”，增加了“userid”；取出表示數據表的名字，去掉“s”后加“id”，例如表mdl_external_services中原僅有一個主鍵“id”，增加了“externalserviceid”；取出表示數據表的名字，去掉“ies”直接加“yid”，例如表 mdl_glossary_entries中原僅有一個主鍵“id”，增加了“glossaryentryid”。

需要指出的是，由于字段名命名的隨意性，通過算法2和算法2+構造的DBCN是近似正確的，而在 CASE工具中不支持 HFK-DBCN+類型的數據模式圖結構分析。

3.3 語義隱性關聯下確定性DBCN構造的數據表字段命名規范

為準確構造語義隱性關聯的DBCN，在數據庫設計中，需要滿足以下條件：

(1)主鍵使用表名 TableName，或者表名的子串，并拼接“id”，描述為 subString(TableName).concat(“id”)。

(2)所有對主鍵引用的外鍵字段，采用與所引用的主鍵同名字段標識。

基于以上規范，不僅基于算法2能構造準確的DBCN，也支持使用CASE工具的語義推理。

4 實驗與分析

4.1 實驗數據

本節實現了一個數據庫復雜網絡分析工具(DBCN Tool)，其系統結構如圖1所示，通過JDBC連接各種數據庫管理系統，提供用戶名、密碼和連接數據源信息，構造一個以 Pajek(Pajek是一個成熟的社會網絡分析工具)格式存儲的DBCN，網絡結構可以通過Pajek軟件分析，或在DBCN Tool中進行可視化分析，其可視化部分采用了網絡分析的Java API 開發包JUNG。

圖1 數據庫復雜網絡分析工具的系統結構

在數據庫復雜網絡中，由于數據表作為節點，網絡分析的粒度較大，一般節點數在幾十到幾百、甚至上千個數量級，可視化的意義遠大于參數分析。與 PowerDesigner提供的圖結構關系表示不同，DBCN弱化了節點信息，將數據表視為一個節點，不考慮其內部的字段數和名稱，凸顯了節點間的參照引用關系。

實驗抽取了9個中大型MIS系統的DBCN，其數據基本信息如表2，其中2個非開源系統，7個開源系統；1個Oracle, 2個SQLServer, 6個MySQL數據模式。

表2 實驗數據基本信息

4.2 網絡參數

9個MIS系統的DBCN統計參數如表3所示，其節點和邊的數量級接近，與隨機網絡相比可達節點之間的平均長度L較小，1＜L＜3；聚類系數C較大；平均入度和出度Di/Do較小，0＜Di＜3；可達節點對比例R較小，它反映級聯更新和級聯刪除的傳播能力；網絡連通性參數S較大，反映數據表孤立節點數較少，大部分數據表與其他數據表有參照引用關聯。

作為一個反例，筆者一直猶豫將對開源系統NseerErp的分析寫進來，該系統擁有443個數據表，它采用隱性語義關聯，由于數據表和字段命名的隨意性，通過算法 2和算法 2+都無法獲得其真實的DBCN。鑒于NseerErp在所討論的9個系統中規模最大，DBCN在大型系統的作用非常明顯，討論該系統的數據表和字段命名格式非常必要。由于NseerErp所有數據表的第1個字段名為主鍵且名稱均為“id”，其可能真正的主鍵沒有被定義為主鍵，如crm_order表中主鍵為系統自增量“id”，其后跟一個非主鍵“order_id”，在 crm_order_details,crm_discussion等多個表中也存在“order_id”，因此有理由認為這些“order_id”，參照引用表crm_order中的“order_id”字段。由于crm_order的order_id在數據庫中沒有被定義為主鍵，嘗試根據表名提取關鍵字，構造可能的主鍵，即 crm_id,order_id，而由 crm_order_details構造可能的主鍵也包含crm_id, order_id和details_id，無法確定哪個表中的order_id是主鍵，進一步以最短數據表名確定其中一個為主鍵，按照以上規則進一步篩選，其DBCN參數見表3，可以斷定該網絡具有不確定性，近似真實地反映系統的數據表關系，由于字段命名的不規范，可能存在遺漏和虛假的邊。如果系統采用 3.3節的命名規范，滿足外鍵字段和相關聯的主鍵字段同名，則容易構造確定性的DBCN，為軟件的理解和增量設計提供直觀的關系視圖。

表3 DBCN統計參數

4.3 距離分布和度分布

圖2所示為6種DBCN的節點距離的概率分布，從確定性的主外鍵DBCN實例 CeoErp, Yundl和WebErp可以看出，密度最大的距離都為2，即存在傳遞一次的關聯關系最多，最長的傳遞距離分別是4, 5和5，它表示操作一個數據表在級聯更新和級聯刪除時影響其他數據表的深度。

圖3分析了Yundl, EcShop, WebErp和CeoErp中每個節點的出入度，對入度按照降序排序，發現入度分布離散，出度分布比較均勻，例如在 Yundl中節點tbStudentBase入度達到33, EcShop的節點ecs_group_goods入度為 24, WebErp的節點stockmaster入度為18, CeoErp中節點tCustomer的入度為13。

圖2 6種DBCN的節點距離分布

圖3 4種DBCN的各節點出入度

圖4(a)所示為4種DBCN的入度和出度的概率分布散點圖，圖4(b)為在雙對數坐標下近似擬合的直線，發現DBCN網絡具有比較明顯的無標度特征。以Yundl為例，數據表中47%的節點入度為0，有43%的節點出度為0，網絡結構不均勻，少數節點有較大的度，大量節點具有較小的度。

4.4 核網絡特性

一個圖的k-核指反復去掉度小于或等于k的節點后，所剩余的子圖。一個節點存在于k-核網絡，而在(k+1)-核中被移除，那么節點的核數為k，核數表明節點在核中的深度，也表明在網絡傳遞關系上，節點的復雜程度。Yundl-DBCN是基于主外鍵的DBCN，其網絡結構準確，它是一個 3-核網絡。其中 0-核即網絡全集，節點數較多，不易區分重要節點，難以觀察到網絡核心層。在3-核網絡上，迭代刪除了度為0，度為1和度為2的節點，節點數由初始的206個減少到35個，從網絡上能直觀獲得其骨干和深層的關聯信息。軟件工程過程使用DBCN的核網絡可視化數據層的關聯，能降低分析設計的難度。

圖4 4種DBCN的節點度分布概率

在逐次構造的核網絡上，其參數，即以節點數表示的網絡規模，網絡聚類系數，平均長度和網絡密度的變化隨k-核網絡變化分別如圖 5(a)-5(d)所示，隨著k-核的增大，網絡節點數下降，在最大核網絡上，從確定性的主外鍵DBCN的實例CeoErp,Yundl和WebErp看，網絡規模下降到0.2倍以下，DBCN的核在3或4之間，而帶有不確定性的隱性語義關聯的 DBCN實例 Zabbix, EcShop和NseerErp，從圖上可以推測，構造算法可能引入了實際不存在的關聯，網絡的統計特性異常。聚類系數隨k-核的增大變化不確定。網絡平均長度隨著k-核的增大在減少。網絡密度表示網絡節點間實際存在的邊數和可以存在的邊數比，其隨k-核的增大而增大，表明高核網絡上節點之間邊多，關聯緊密， 反映出用高核網絡分析網絡的骨干和深層關聯是合理的。

5 結束語

本文提出了數據庫復雜網絡的概念，其工程意義在于為管理信息系統提供了一種規模度量，為軟件的數據庫設計提供一種新的輔助工具，研究了常用數據庫管理系統的主外鍵關聯和語義隱性關聯形成的復雜網絡構造算法，并分析了網絡的統計特性。在大型的 MIS系統中，或者企業內部的多個 MIS系統關聯形成的數據中心，DBCN的工程意義更加明顯，可以化簡數據層的復雜性。數據庫復雜網絡表示了數據庫關聯圖的統計特性，其節點(數據表)在網絡上的重要性是不同的，少量的節點之間蘊含了大多數的業務邏輯關系。此外，數據庫復雜網絡視圖也為軟件開發文檔的數據庫描述提供了一種新的形式，是一種自說明的文檔，使得在軟件版本變更、增量設計以及開發人員變動情況下，尤其在開源軟件的二次開發中，能快速理解數據庫內部的關聯，從而理解業務邏輯關系，縮短開發時間。鑒于構造基于隱性語義關聯的數據庫復雜網絡具有不確定性，提出了按照外鍵字段名與參照引用主鍵同名的原則來規范命名數據字段，能支持構造準確的網絡結構，輔助于軟件開發人員對系統邏輯的理解。

圖5 不同核深度下6種DBCN網絡參數比較

[1]何克清, 馬于濤, 劉婧, 等. 軟件網絡[M]. 北京: 科學出版社,2008: 5-37.

He Ke-qing, Ma Yu-tao, Liu Jing,et al.. Software Networks[M]. Beijing: Science Press, 2008: 5-37.

[2]LaBelle N and Wallingford E. Inter-package dependency networks in open-source software[OL]. http://arxiv. org/abs/cs/0411096, 2011, 2.

[3]Myers C R. Software systems as complex networks: structure,function, and evolvability of software collaboration graphs[J].Physical Review E, 2003, 68(4): 046116.

[4]Pan Wei-feng, Li Bing, and Ma Yu-tao. Multi-granularity evolution analysis of software using complex network theory[J].Journal of Systems Science and Complexity, 2011,24(6): 1068-1082.

[5]韓言妮, 李德毅, 陳桂生. 軟件多粒度拓撲特性分析及其應用[J]. 計算機學報, 2009, 32(9): 1711-1721.

Han Yan-ni, Li De-yi, and Chen Gui-sheng. Analysis on the topological properties of software network at different levels of granularity and its application[J].Chinese Journal of Computers, 2009, 32(9): 1711-1721.

[6]王紅春. 網絡化軟件多粒度動態特性分析[D]. [博士論文], 武漢大學, 2010.

Wang Hong-chun. Multi-granularity dynamic characteristic analysis of networked software[D]. [Ph.D. dissertation],Wuhan University, 2010.

[7]Cai K Y and Yin B B. Software execution processes as an evolving complex network[J].Information Sciences, 2009,179(12): 1903-1928.

[8]Li Huan and Li Bing. A pair of coupling metrics for software networks[J].Journal of Systems Science and Complexity,2011, 24(1): 51-60.

[9]Ma Y T, He K Q, Li B,et al..A hybrid set of complexity metrics for large-scale object-oriented software systems[J].Journal of Computer Science and Technology, 2010, 25(6):1184-1201.

[10]Ma Yu-tao, Liu Yu-chao, Zhang Hai-su,et al.. A hybrid method for prioritizing software requirements in terms of use cases[J].Journal of Convergence Information Technology,2012, 7(5): 17-27.

[11]Li C F, Liu L Z, and Li X Y. Software networks of java class and application in fault localization[C]. Proceedings of ISDEA, Sanya, China, January 7-8, 2012: 1117-1120.

[12]馬于濤, 何克清, 李兵, 等. 網絡化軟件的復雜網絡特性實證[J]. 軟件學報, 2011, 22(3): 381-407.

Ma Yu-tao, He Ke-qing, Li Bing,et al.. Empirical study on the characteristics of complex networks in networked software[J].Journal of Software, 2011, 22(3): 381-407.

[13]Fagin R. Degree of acyclicity for hypergraphs and relational database schemes[J].Journal of the Association for Computing Maceinery, 1983, 33(3): 514-550.