數(shù)據(jù)庫復(fù)雜網(wǎng)絡(luò)構(gòu)造算法及特征分析

李春芳 劉連忠 劉振國(guó)

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

②(北京航空航天大學(xué)計(jì)算機(jī)學(xué)院 北京 100191)

③(河北體育學(xué)院網(wǎng)絡(luò)中心 石家莊 050041)

1 引言

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

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

早在 1983年，文獻(xiàn)[13]利用超圖(hyper networks)超網(wǎng)絡(luò)來描述數(shù)據(jù)庫，其節(jié)點(diǎn)是一個(gè)數(shù)據(jù)模式的所有數(shù)據(jù)表的字段集合，一個(gè)數(shù)據(jù)表定義為一個(gè)超邊(hyper edge)，它能連接多于兩個(gè)節(jié)點(diǎn)。由于超圖的可視化信息不便于直觀理解，遠(yuǎn)不如復(fù)雜網(wǎng)絡(luò)描述數(shù)據(jù)庫內(nèi)部關(guān)聯(lián)更直接。

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

2 形式化表示

數(shù)據(jù)庫完整性指數(shù)據(jù)的正確性和相容性，完整性包括域、實(shí)體、參照和用戶定義完整性，其完整性設(shè)計(jì)就是約束設(shè)計(jì)。在大型MIS系統(tǒng)設(shè)計(jì)中，參照完整性是核心，它集中體現(xiàn)了業(yè)務(wù)邏輯，也是軟件設(shè)計(jì)復(fù)雜性的根源之一，本文將數(shù)據(jù)表間的參照完整性建模為復(fù)雜網(wǎng)絡(luò)，以更簡(jiǎn)潔的方式描述其復(fù)雜關(guān)聯(lián)性。完整性約束可以通過數(shù)據(jù)庫管理系統(tǒng)(DataBase Management System, DBMS)或應(yīng)用程序?qū)崿F(xiàn)，通過DBMS實(shí)現(xiàn)的參照完整性即主外鍵關(guān)聯(lián)，而由應(yīng)用軟件實(shí)現(xiàn)的參照完整性本文定義為語義隱性關(guān)聯(lián)，簡(jiǎn)稱語義關(guān)聯(lián)，它隱含表示了數(shù)據(jù)表主外鍵之間的參照關(guān)系。

大量的開發(fā)經(jīng)驗(yàn)表明，外鍵關(guān)聯(lián)和語義關(guān)聯(lián)各有優(yōu)勢(shì)，表1列出了兩種關(guān)聯(lián)的比較，在本文分析的9個(gè)數(shù)據(jù)模式中，4個(gè)采用了外鍵，5個(gè)采用了隱性語義關(guān)聯(lián)。外鍵關(guān)聯(lián)采用數(shù)據(jù)庫集中管理數(shù)據(jù)關(guān)系，在海量數(shù)據(jù)查詢情況下跨表查詢性能比語義關(guān)聯(lián)差。由于DBMS能自動(dòng)維護(hù)數(shù)據(jù)的完整性，因此在故障發(fā)生時(shí)，能夠保證數(shù)據(jù)的一致性，而語義關(guān)聯(lián)可能會(huì)引入不一致數(shù)據(jù)。在開發(fā)階段，由于系統(tǒng)的不完備性，外鍵會(huì)羈絆代碼實(shí)現(xiàn)，而語義關(guān)聯(lián)需要增加代碼來維護(hù)參照引用數(shù)據(jù)的一致性。CASE工具支持外鍵關(guān)聯(lián)和部分語義關(guān)聯(lián)的圖結(jié)構(gòu)分析。

表1 外鍵關(guān)聯(lián)和語義關(guān)聯(lián)比較

大部分的DBMS系統(tǒng)和逆向工程工具都采用了數(shù)據(jù)庫關(guān)系圖，其節(jié)點(diǎn)是數(shù)據(jù)表結(jié)構(gòu)信息，邊是外鍵到主鍵的關(guān)聯(lián)依賴，因此在數(shù)據(jù)庫復(fù)雜網(wǎng)絡(luò)構(gòu)造上用數(shù)據(jù)表作為節(jié)點(diǎn)，外鍵關(guān)系作為邊是合理的。在已有的數(shù)據(jù)庫關(guān)系圖中，節(jié)點(diǎn)信息復(fù)雜，然而對(duì)復(fù)雜性起關(guān)鍵作用的是主鍵和外鍵，其他非主鍵和非外鍵字段的添加和刪除對(duì)關(guān)聯(lián)復(fù)雜性沒有影響，因此進(jìn)一步化簡(jiǎn)節(jié)點(diǎn)是可能的。

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

基于復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)參數(shù)[1]，定義如下特征參數(shù)：

(1)節(jié)點(diǎn)數(shù)N：數(shù)據(jù)表個(gè)數(shù)；

(2)邊數(shù)E；

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

(4)平均聚類系數(shù)C；

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

(6)節(jié)點(diǎn)對(duì)可達(dá)率R：定義為有向網(wǎng)絡(luò)上任意不同的兩個(gè)節(jié)點(diǎn)之間存在的可達(dá)路徑總數(shù)除以N×(N-1),R是對(duì)內(nèi)部關(guān)聯(lián)緊密程度的一種度量，網(wǎng)絡(luò)內(nèi)聚度越高，R越大，如果系統(tǒng)內(nèi)部存在級(jí)聯(lián)刪除和級(jí)聯(lián)更新，在數(shù)據(jù)庫內(nèi)部傳遞的可能性越大；

(7)網(wǎng)絡(luò)連接率S：定義為最大連通圖上的節(jié)點(diǎn)數(shù)除以總節(jié)點(diǎn)數(shù)。

在DBCN上，節(jié)點(diǎn)的入邊是其它數(shù)據(jù)表的外鍵(或隱含外鍵)字段到該數(shù)據(jù)表主鍵的引用，節(jié)點(diǎn)的出邊是該數(shù)據(jù)表的外鍵(或隱性外鍵)到其它數(shù)據(jù)表主鍵的引用。數(shù)據(jù)庫主鍵和字段的關(guān)系是一對(duì)多的關(guān)系，主鍵可能是一個(gè)字段，或者多個(gè)字段，即聯(lián)合主鍵，絕大多數(shù)是一個(gè)字段，在聯(lián)合主鍵情況下每個(gè)獨(dú)立字段都是外鍵，即到其他表主鍵的引用。因此入邊都是對(duì)節(jié)點(diǎn)主鍵的引用，而出邊是對(duì)其他節(jié)點(diǎn)主鍵的引用。

由于一個(gè)數(shù)據(jù)表中可能有多于一個(gè)字段引用其它表的同一個(gè)主鍵字段，因此DBCN是一個(gè)可能包含重邊的有向圖，在以下的構(gòu)造算法中去掉了重邊，只考慮簡(jiǎn)單有向圖構(gòu)造的網(wǎng)絡(luò)。

3 構(gòu)造算法

3.1 基于主外鍵的構(gòu)造算法

本節(jié)研究了基于復(fù)雜網(wǎng)絡(luò)的數(shù)據(jù)庫關(guān)聯(lián)分析技術(shù)，實(shí)現(xiàn)對(duì)Oracle, MySQL, SQLServer數(shù)據(jù)庫中表的元數(shù)據(jù)的關(guān)聯(lián)分析。針對(duì)基于數(shù)據(jù)庫主外鍵的關(guān)聯(lián)和無外鍵的語義隱性關(guān)聯(lián)提出了兩種網(wǎng)絡(luò)構(gòu)造算法。

算法1基于主外鍵的構(gòu)造算法(FK-DBCN)(1)查詢系統(tǒng)表讀取一個(gè)數(shù)據(jù)模式下的所有數(shù)據(jù)表名稱，作為網(wǎng)絡(luò)節(jié)點(diǎn)信息；

(2)查詢系統(tǒng)約束表，讀取數(shù)據(jù)模式的所有外鍵約束，作為從一個(gè)數(shù)據(jù)表節(jié)點(diǎn)(外鍵)到參照表節(jié)點(diǎn)(主鍵)的有向邊信息。

用算法 1構(gòu)造了非開源軟件學(xué)校管理系統(tǒng)Yundl的數(shù)據(jù)庫網(wǎng)絡(luò)，其DBMS為SQLServer，它采用了外鍵實(shí)現(xiàn)參照完整性約束，顯示度排名前三位的節(jié)點(diǎn)是 tbStudentBasis, tbTeacherBasis和tbYearBasis，反映該系統(tǒng)中所有的關(guān)系中最重要的是學(xué)生、教師在學(xué)年中的各種關(guān)系，這種直接宏觀的業(yè)務(wù)邏輯表示對(duì)于變更的開發(fā)團(tuán)隊(duì)、軟件的二次開發(fā)以及更新維護(hù)非常重要，可以縮短增量開發(fā)時(shí)間。

3.2 基于語義關(guān)聯(lián)的構(gòu)造算法

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

算法2基于語義隱性關(guān)聯(lián)的DBCN構(gòu)造算法(HFK-DBCN)

(1)查詢一個(gè)數(shù)據(jù)模式的所有數(shù)據(jù)表名稱，作為網(wǎng)絡(luò)節(jié)點(diǎn)信息，節(jié)點(diǎn)數(shù)為n；

(2)查詢每個(gè)數(shù)據(jù)表節(jié)點(diǎn) Nodei(i=1,2,…,n)的非主鍵字段個(gè)數(shù)fc和名稱FFields[1,2,…,fc]；

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

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

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

算法2+擴(kuò)展的語義隱性關(guān)聯(lián)的數(shù)據(jù)庫復(fù)雜網(wǎng)絡(luò)構(gòu)造算法(HFK-DBCN+)

(1)查詢一個(gè)數(shù)據(jù)模式的所有數(shù)據(jù)表名稱，作為網(wǎng)絡(luò)節(jié)點(diǎn)信息，節(jié)點(diǎn)數(shù)為n；

(2)查詢每個(gè)數(shù)據(jù)表節(jié)點(diǎn) Nodei(i=1,2,…,n)的非主鍵字段個(gè)數(shù)fc和名稱FFields[1,2,…,fc]；

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

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

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

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

3.3 語義隱性關(guān)聯(lián)下確定性DBCN構(gòu)造的數(shù)據(jù)表字段命名規(guī)范

為準(zhǔn)確構(gòu)造語義隱性關(guān)聯(lián)的DBCN，在數(shù)據(jù)庫設(shè)計(jì)中，需要滿足以下條件：

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

(2)所有對(duì)主鍵引用的外鍵字段，采用與所引用的主鍵同名字段標(biāo)識(shí)。

基于以上規(guī)范，不僅基于算法2能構(gòu)造準(zhǔn)確的DBCN，也支持使用CASE工具的語義推理。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

本節(jié)實(shí)現(xiàn)了一個(gè)數(shù)據(jù)庫復(fù)雜網(wǎng)絡(luò)分析工具(DBCN Tool)，其系統(tǒng)結(jié)構(gòu)如圖1所示，通過JDBC連接各種數(shù)據(jù)庫管理系統(tǒng)，提供用戶名、密碼和連接數(shù)據(jù)源信息，構(gòu)造一個(gè)以 Pajek(Pajek是一個(gè)成熟的社會(huì)網(wǎng)絡(luò)分析工具)格式存儲(chǔ)的DBCN，網(wǎng)絡(luò)結(jié)構(gòu)可以通過Pajek軟件分析，或在DBCN Tool中進(jìn)行可視化分析，其可視化部分采用了網(wǎng)絡(luò)分析的Java API 開發(fā)包JUNG。

圖1 數(shù)據(jù)庫復(fù)雜網(wǎng)絡(luò)分析工具的系統(tǒng)結(jié)構(gòu)

在數(shù)據(jù)庫復(fù)雜網(wǎng)絡(luò)中，由于數(shù)據(jù)表作為節(jié)點(diǎn)，網(wǎng)絡(luò)分析的粒度較大，一般節(jié)點(diǎn)數(shù)在幾十到幾百、甚至上千個(gè)數(shù)量級(jí)，可視化的意義遠(yuǎn)大于參數(shù)分析。與 PowerDesigner提供的圖結(jié)構(gòu)關(guān)系表示不同，DBCN弱化了節(jié)點(diǎn)信息，將數(shù)據(jù)表視為一個(gè)節(jié)點(diǎn)，不考慮其內(nèi)部的字段數(shù)和名稱，凸顯了節(jié)點(diǎn)間的參照引用關(guān)系。

實(shí)驗(yàn)抽取了9個(gè)中大型MIS系統(tǒng)的DBCN，其數(shù)據(jù)基本信息如表2，其中2個(gè)非開源系統(tǒng)，7個(gè)開源系統(tǒng)；1個(gè)Oracle, 2個(gè)SQLServer, 6個(gè)MySQL數(shù)據(jù)模式。

表2 實(shí)驗(yàn)數(shù)據(jù)基本信息

4.2 網(wǎng)絡(luò)參數(shù)

9個(gè)MIS系統(tǒng)的DBCN統(tǒng)計(jì)參數(shù)如表3所示，其節(jié)點(diǎn)和邊的數(shù)量級(jí)接近，與隨機(jī)網(wǎng)絡(luò)相比可達(dá)節(jié)點(diǎn)之間的平均長(zhǎng)度L較小，1＜L＜3；聚類系數(shù)C較大；平均入度和出度Di/Do較小，0＜Di＜3；可達(dá)節(jié)點(diǎn)對(duì)比例R較小，它反映級(jí)聯(lián)更新和級(jí)聯(lián)刪除的傳播能力；網(wǎng)絡(luò)連通性參數(shù)S較大，反映數(shù)據(jù)表孤立節(jié)點(diǎn)數(shù)較少，大部分?jǐn)?shù)據(jù)表與其他數(shù)據(jù)表有參照引用關(guān)聯(lián)。

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

表3 DBCN統(tǒng)計(jì)參數(shù)

4.3 距離分布和度分布

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

圖3分析了Yundl, EcShop, WebErp和CeoErp中每個(gè)節(jié)點(diǎn)的出入度，對(duì)入度按照降序排序，發(fā)現(xiàn)入度分布離散，出度分布比較均勻，例如在 Yundl中節(jié)點(diǎn)tbStudentBase入度達(dá)到33, EcShop的節(jié)點(diǎn)ecs_group_goods入度為 24, WebErp的節(jié)點(diǎn)stockmaster入度為18, CeoErp中節(jié)點(diǎn)tCustomer的入度為13。

圖2 6種DBCN的節(jié)點(diǎn)距離分布

圖3 4種DBCN的各節(jié)點(diǎn)出入度

圖4(a)所示為4種DBCN的入度和出度的概率分布散點(diǎn)圖，圖4(b)為在雙對(duì)數(shù)坐標(biāo)下近似擬合的直線，發(fā)現(xiàn)DBCN網(wǎng)絡(luò)具有比較明顯的無標(biāo)度特征。以Yundl為例，數(shù)據(jù)表中47%的節(jié)點(diǎn)入度為0，有43%的節(jié)點(diǎn)出度為0，網(wǎng)絡(luò)結(jié)構(gòu)不均勻，少數(shù)節(jié)點(diǎn)有較大的度，大量節(jié)點(diǎn)具有較小的度。

4.4 核網(wǎng)絡(luò)特性

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

圖4 4種DBCN的節(jié)點(diǎn)度分布概率

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

5 結(jié)束語

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

圖5 不同核深度下6種DBCN網(wǎng)絡(luò)參數(shù)比較

[1]何克清, 馬于濤, 劉婧, 等. 軟件網(wǎng)絡(luò)[M]. 北京: 科學(xué)出版社,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]韓言妮, 李德毅, 陳桂生. 軟件多粒度拓?fù)涮匦苑治黾捌鋺?yīng)用[J]. 計(jì)算機(jī)學(xué)報(bào), 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]王紅春. 網(wǎng)絡(luò)化軟件多粒度動(dòng)態(tài)特性分析[D]. [博士論文], 武漢大學(xué), 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]馬于濤, 何克清, 李兵, 等. 網(wǎng)絡(luò)化軟件的復(fù)雜網(wǎng)絡(luò)特性實(shí)證[J]. 軟件學(xué)報(bào), 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.