基于元素樹的異質(zhì)數(shù)據(jù)庫間雙向轉換算法研究

包空軍,曹 瑞

(1. 鄭州輕工業(yè)大學工程訓練中心,河南 鄭州 450000;2. 鄭州輕工業(yè)大學計算機與通信工程學院,河南 鄭州 450000)

1 引言

數(shù)據(jù)集成的關鍵是各種類型數(shù)據(jù)庫間的雙向轉換,確保集成后的數(shù)據(jù)為統(tǒng)一的標準化格式[1,2],不會影響系統(tǒng)間信息的交換。傳統(tǒng)的數(shù)據(jù)庫轉換算法,實現(xiàn)過程較為困難,且成本高,無法被廣泛應用[3,4],數(shù)據(jù)庫轉換算法欠缺,直接影響數(shù)據(jù)集成效果。因此,為確保異質(zhì)數(shù)據(jù)集成效果達到最佳[5-7],便需研究較優(yōu)的異質(zhì)數(shù)據(jù)庫轉換算法。賴欣等人分析了異質(zhì)數(shù)據(jù)的結構特點,及異質(zhì)數(shù)據(jù)庫內(nèi)數(shù)據(jù)的表達差異,依據(jù)分析結果設計異質(zhì)數(shù)據(jù)庫間的轉換算法,實驗證明了該算法的可行性[8];劉穩(wěn)等人依據(jù)異質(zhì)數(shù)據(jù)間的差異,塑造異質(zhì)數(shù)據(jù)關聯(lián)轉換的總體框架,完成異質(zhì)數(shù)據(jù)的對接轉換,實驗證明該算法可有效轉換異質(zhì)數(shù)據(jù),同時數(shù)據(jù)轉換的一致性較高[9];這兩種算法均僅適合單向轉換,并不支持異質(zhì)數(shù)據(jù)庫間的雙向轉換,且轉換操作較為繁瑣。為此研究基于元素樹的異質(zhì)數(shù)據(jù)庫間雙向轉換算法,提升異質(zhì)數(shù)據(jù)庫雙向轉換效果,確保雙向轉換過程中數(shù)據(jù)的安全性。

2 異質(zhì)數(shù)據(jù)庫間雙向轉換算法

異質(zhì)數(shù)據(jù)庫指關系數(shù)據(jù)庫與概率可擴展的標記語言(extensible markup language,XML)數(shù)據(jù)庫兩種類型,在這兩種數(shù)據(jù)數(shù)據(jù)庫內(nèi)引入概率數(shù)值描繪數(shù)據(jù)節(jié)點,可更加精準地呈現(xiàn)數(shù)據(jù)庫的結構特性,提升異質(zhì)數(shù)據(jù)庫間雙向轉換效果。

2.1 概率異質(zhì)數(shù)據(jù)模型

2.1.1 概率關系數(shù)據(jù)模型

現(xiàn)實世界內(nèi)的對象由元組T的集合ε1×ε2×…×εn描繪,屬性閾值是εi,那么關系R的集合是G(ε1×ε2×…×εn)。

關系數(shù)據(jù)庫內(nèi)概率屬性代表和概率有關的一般屬性,其閾值εi是εi=[0,1]×εi,因此概率元組pT的集合是ε1×ε2×…×εn。

令pT的屬性i的概率為Pi(pT),投影計算符號是∏,那么其值為∏i(pT),令主鍵是k的概率關系數(shù)據(jù)pR的集合G(ε1×ε2×…×εn),那么pR的鍵值是v的全部pT的集合為:

∏v(pR)={pT∈|∏i(pT)=v}

(1)

pR內(nèi)Di相應的pT公式如下:

εi|pR={v∈εi|(pT∈pR)∏i(pT)=v}

(2)

與關系數(shù)據(jù)庫不同,pR存在兩個約束條件

(3)

依據(jù)可能世界模型的語義得知[10],pT的概率為

(4)

因為pW∈pR,所以式(5)與式(6)成立,公式如下

(5)

(?pT∈pR)(?pT′∈pW)∏k(pT)

(6)

因此,pR的可能世界集合pWSpR即概率關系數(shù)據(jù)模型

pWSpR={pW代表pR|pW為可能世界}

(7)

pR為1范式情況下,R∈G(ε1×ε2×…×εn),其中,εi=[0,1]×εi,pR為3范式情況下,pR∈εk×Gεi,i=1,2,…,n。

2.1.2 概率XML數(shù)據(jù)模型

以半結構化信息為出發(fā)點,設置概率數(shù)據(jù)在XML數(shù)據(jù)庫內(nèi)的表示方式,塑造概率XML數(shù)據(jù)模型。

定義1:半結構化信息單元(Semis-structured Information Unit,SIU)共有三種形式,分別是若元素名為q,元素值為w,那么〈q〉w〈/q〉為SIU;若元素名為q,元素值為w,屬性名為f,屬性值為g,那么w〈/q〉也為SIU;若元素名為q,s1,…,sm為SIU,那么〈q〉s1,…,sm〈/q〉也為SIU。

半結構化的信息單元可描繪數(shù)據(jù)樹,因此建立概率XML樹,即概率XML數(shù)據(jù)模型,概率XML樹的定義如下:

定義2:令XML樹X是五元組X=(N,Q,r,lable,value),節(jié)點有限集合為N;X的根為r;邊的集合為Q?N×N;lable:N→name,代表N內(nèi)各節(jié)點所分配的標簽[11];葉子節(jié)點leaf(leaf∈N-{r})分配的數(shù)值是value。

定義3:概率XML樹pT的可能世界模型是二元組(tj,pj),j=1,2,…,m的有限集合,XML樹為tj,正實數(shù)為pj,同時p1+p2+…+pm=1。

定義4:概率XML數(shù)據(jù)模型是PDTD=(Q,A,rule,att,str),有限元素集合為Q={q1,q2,…,qm},pT內(nèi)的元素為qj(1≤j≤m),屬性集合為A={a1,a2,…,al},pT內(nèi)元素屬性為ao(1≤o≤l),規(guī)則集合為rule(Q),pT內(nèi)元素與相應取值的關系為att(〈q1,a11,p11〉,…,〈q1,a1m,p1m〉,〈q2,a21,p21〉,…,〈q2,a2l,p2l〉,…),同時p11+p12+…+p1m=1,p21+p22+…+p2l=1,Q至A冪集內(nèi)的映射為str。

2.2 基于元素樹的數(shù)據(jù)模型雙向轉換算法

利用元素樹E完成異質(zhì)數(shù)據(jù)庫概率關系數(shù)據(jù)模型與概率XML數(shù)據(jù)模型的雙向轉換,先建立E與元素節(jié)點C和各種類型數(shù)據(jù)模型間的映射關系,再以E與映射關系為前提,實現(xiàn)數(shù)據(jù)模型雙向轉換。

2.2.1 元素樹

E是具有數(shù)據(jù)模型內(nèi)各元素間的關系樹,包含E內(nèi)各C相應數(shù)據(jù)模型內(nèi)的各元素[12];各C均具有概率屬性列表h、概率子元素列表h′與其余概率信息h″;h內(nèi)存在該概率元素的全部概率屬性;h′內(nèi)存在該概率元素的全部概率子元素[13],各概率子元素均與各新節(jié)點相應;h″內(nèi)存在父親節(jié)點與元素內(nèi)容等。

E的生成步驟如下:

步驟1:解析pWSpR與PDTD,針對全部不存在其余概率元素內(nèi)容中的概率元素c,以C為根節(jié)點,建立W;

步驟2:塑造一個概率節(jié)點C;

步驟3:按照已解析的pWSpR與PDTD,得到c的hc,在C內(nèi)添加hc;

步驟4:分析c的概率內(nèi)容模式ξ[14],得到C的h″C,按照各概率元素內(nèi)容的概率類型得到C的h′C;

步驟5:按照ξ內(nèi)各概率內(nèi)容粒子的類型,構建概率節(jié)點α的h′α。

2.2.2 異質(zhì)數(shù)據(jù)庫間雙向概率映射關系

以E為前提,建立E、pWSpR與PDTD間的概率映射關系,先定義E與pWSpR、PDTD結構間的概率映射規(guī)則,再通過概率映射規(guī)則自動獲取W、pWSpR、PDTD間的概率映射關系。

以pWSpR為例,元素樹和pWSpR間的概率映射規(guī)則定義為:

定義5:E的概率根節(jié)點與pWSpR內(nèi)的一個概率表相應,即概率根表Y。

定義6:若某個概率節(jié)點的h或h′不是空集[15],那么該概率節(jié)點即是概率表節(jié)點Y′,與pWSpR內(nèi)的一個概率表相應。

定義7:一個Y′的各屬性與子節(jié)點均與其所屬表內(nèi)的一個字段相應。

定義8:pWSpR內(nèi)除Y外的其余概率表均需存在一個和其概率父表存在關系的外鍵。

定義9:除Y′與概率節(jié)點ξ外的概率節(jié)點是概率字段節(jié)點,與概率父節(jié)點相應概率表內(nèi)的一個概率字段對應。

定義10:ξ與pWSpR內(nèi)的全部概率對象均不對應。

同理獲取元素樹與PDTD的概率映射規(guī)則,概率映射規(guī)則獲取結束后便可自動建立元素樹、pWSpR、PDTD間的概率映射關系,存儲于概率映射表內(nèi)。

2.2.3 數(shù)據(jù)模型的雙向轉換實現(xiàn)

PDTD到pWSpR的轉換步驟如下:

步驟1:掃描PDTD,掃描方式為由上至下,針對PDTD內(nèi)各簡單概率元素,生成一個相應概率類表的概率屬性列,若引用內(nèi)概率操作符為可選的,那么該列可以存在空值;

步驟2:依據(jù)簡單概率元素類型的反復引用,可獲取存在外鍵的h;

步驟3:依據(jù)PDTD內(nèi)各復雜概率元素類型,可獲取存在主鍵的概率類表;

步驟4:依據(jù)復雜概率元素類型的引用,可獲取指向雙親的外鍵;

步驟5:依據(jù)混合內(nèi)容內(nèi)已解析字符數(shù)據(jù),可獲取外鍵的h;

步驟6:全部被引用的概率屬性轉換操作為:依據(jù)單值概率屬性獲取一列,若概率屬性可選,那么該列可以存在空值;依據(jù)多值概率屬性獲取存在外鍵的h,若一個概率屬性存在缺省值,那么將其當成列缺省值。

pWSpR到PDTD的轉換步驟如下:

步驟1:為各概率表創(chuàng)建在一個概率序列引用μ的概率元素類型φ;

步驟2:為概率表內(nèi)各不為鍵的概率數(shù)據(jù)列建立存在已解析字符數(shù)據(jù)的φ,移至相應概率表φ內(nèi),同時在該概率類型的概率序列內(nèi)設置μ,令空值的列為可選引用;

步驟3:為各概率表內(nèi)的主鍵列建立存在已解析字符數(shù)據(jù)的φ,移至相應概率表φ內(nèi),同時在該φ序列內(nèi)設置引用;

步驟4:若存在外鍵,則存在外鍵的概率表是概率子表,外鍵相應的概率表是概率父表,轉換策略是如果概率父表和概率子表為一對一關系,那么在概率父表μ概率序列內(nèi)設置一個概率子表元素的μ,令其為可選形式。在概率父表元素內(nèi)移入概率子表φ所有概率內(nèi)容,并在概率子表μ概率序列內(nèi)設置一條概率父表元素名的μ,且在概率子表元素內(nèi)移入概率父表所有概率內(nèi)容;如果概率父表和概率子表為一對多的關系,那么在概率父表μ概率序列內(nèi)設置一條概率子表元素名的μ,令其為可選反復操作的形式,并依據(jù)概率父表元素μ概率序列的次序,在概率父表元素內(nèi)移入概率子表φ的所有概率內(nèi)容。

3 仿真分析

以某銷售公司的關系數(shù)據(jù)庫與XML數(shù)據(jù)庫兩個異質(zhì)數(shù)據(jù)庫為實驗對象,以Matlab仿真軟件為仿真操作環(huán)境,利用本文算法將關系數(shù)據(jù)庫內(nèi)的shangpin表內(nèi)數(shù)據(jù)和XML數(shù)據(jù)庫內(nèi)的goods表展開雙向轉換,源數(shù)據(jù)表內(nèi)容雙向轉換前后保持原樣。

兩個異質(zhì)數(shù)據(jù)庫內(nèi)數(shù)據(jù)為完成雙向轉換會存在較多的數(shù)據(jù)沖突,分別是基本表內(nèi)相應字段名稱沖突、字段類型沖突與相應列字段取值區(qū)間沖突。需要展開雙向轉換的shangpin表與goods表基本數(shù)據(jù)如表1所示。

表1 shangpin表與goods表基本數(shù)據(jù)

利用本文算法雙向轉換表1內(nèi)的兩個異質(zhì)數(shù)據(jù)庫內(nèi)的數(shù)據(jù),雙向轉換結果如表2、表3所示。

表2 shangpin表到goods表的轉換結果

表3 goods表到shangpin表的轉換結果

根據(jù)表2與表3可知,本文算法可有效雙向轉換異質(zhì)數(shù)據(jù)庫間的數(shù)據(jù)內(nèi)容,很好地解決了雙向轉換時包含的沖突問題,可為銷售公司獲取符合要求的業(yè)務數(shù)據(jù)。

測試本文算法展開雙向轉換的查詢性能與寫入性能,測試方法為向網(wǎng)絡發(fā)送8000筆交易,交易類型是查詢與寫入,測試本文算法在不同交易發(fā)送頻率時的數(shù)據(jù)雙向交換的查詢性能與寫入性能,交易發(fā)送頻率代表每秒交易數(shù)(Transactions Per Second,TPS),以吞吐量與平均時延為衡量查詢與寫入性能的指標,測試結果如圖1所示。

圖1 查詢性能與寫入性能測試結果

綜合分析圖1(a)與圖1(b)可知,當TPS為600筆/s時,本文算法進行異質(zhì)數(shù)據(jù)庫雙向轉換時的查詢性能最優(yōu),當TPS為400筆/s時,本文算法進行異質(zhì)數(shù)據(jù)庫雙向轉換時的寫入性能最優(yōu)。

在不同惡意網(wǎng)絡節(jié)點概率時,測試本文算法進行異質(zhì)數(shù)據(jù)庫間雙向轉換過程中的數(shù)據(jù)泄露概率,當數(shù)據(jù)泄露概率超過0.05時,說明數(shù)據(jù)雙向交換的安全性較低,測試結果如圖2所示。

圖2 雙向轉換過程中的數(shù)據(jù)泄露概率

根據(jù)圖2可知,當惡意節(jié)點概率達到16%時,兩種攻擊下的數(shù)據(jù)泄露概率均趨于穩(wěn)定,控制在0.05以內(nèi)。仿真結果證明,本文算法在不同惡意節(jié)點概率并承受不同攻擊情況下,進行異質(zhì)數(shù)據(jù)間雙向轉換的安全性較高。

4 結論

依據(jù)元素樹的數(shù)據(jù)映射方法,設計異質(zhì)數(shù)據(jù)庫間的雙向轉換算法,利用元素樹獲取異質(zhì)數(shù)據(jù)庫間的結構映射關系,以該映射關系為前提,完成雙向轉換,確保雙向轉換過程中的數(shù)據(jù)不會泄露,仿真結果表明本文算法在理論上具有一定的指導意義。