基于粒計算的XML近似多值依賴的判定算法

金 花，殷麗鳳

（大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116028）

粒計算[1-2]是人工智能領(lǐng)域中的一種新理念和新方法，它覆蓋了所有和粒度相關(guān)的理論、方法、技術(shù)和工具，主要用于對不確定、不精確、不完整信息的處理，對大規(guī)模海量數(shù)據(jù)的挖掘以及對復(fù)雜問題的求解。目前，它在粗糙集理論、概念格、知識工程、數(shù)據(jù)挖掘、人工智能、機器學(xué)習(xí)等領(lǐng)域有潛在的應(yīng)用，已成為信息科學(xué)的研究熱點之一。

XML（eXtensible Markup Language）已經(jīng)成為 Internet上數(shù)據(jù)表示和信息交換的標(biāo)準(zhǔn)，由于不確定數(shù)據(jù)的普遍存在性，研究表示和處理不確定XML數(shù)據(jù)成為一個新的研究領(lǐng)域。不確定數(shù)據(jù)[3]包含不完備數(shù)據(jù)、概率數(shù)據(jù)以及集值數(shù)據(jù)，我們[4]已經(jīng)對不完備XML數(shù)據(jù)規(guī)范化理論進行了研究；很多學(xué)者對概率XML數(shù)據(jù)各種查詢處理技術(shù)[5-7]進行了研究；目前集值XML數(shù)據(jù)研究得還很少。本文對確定XML數(shù)據(jù)進行擴展，允許葉子節(jié)點取值為原子值的集合（稱作集值XML數(shù)據(jù)）。分析集值XML數(shù)據(jù)庫模型，給出相似關(guān)系，研究集值XML數(shù)據(jù)中路徑間的多值依賴。根據(jù)粒計算中的等價粒概念采用位模式描述集值XML數(shù)據(jù)庫，最后給出XML近似多值依賴（記作XAMVD）的判定算法。此理論成果為集值XML數(shù)據(jù)庫的規(guī)范化、路徑約簡和查詢問題等方面的進一步研究奠定了基礎(chǔ)。

1 基本概念

為了研究近似XML多值依賴，首先給出集值XML數(shù)據(jù)庫模型、集值XML數(shù)據(jù)庫、相似冗余等相關(guān)定義。

定義1一個集值XML數(shù)據(jù)庫模型為一棵樹，記為Tm，其中 Tm為六元組，即 Tm=（Vm，Em，lab，ele，N，Dom），其中：

1）Vm表示樹的節(jié)點的集合；Vm=Vms∪Vml∪Vmr， 其中 Vms表示結(jié)構(gòu)信息，即分支節(jié)點；Vml表示數(shù)據(jù)信息，即葉子節(jié)點；Vmr代表根節(jié)點。

2）Em表示樹邊的集合；

3）lab表示元素名字（EN）和屬性名字（AN）的集合；

4）ele表示從節(jié)點Vm到Vm中一系列節(jié)點的部分映射，滿足對?∈Vm，ele（v）=[v1，…，vn]且邊（v，vi）∈Em，其中 i∈[1，n]；

5）N是從樹節(jié)點 Vm到 Lab的映射，若任意 v∈VS，則 N（v）∈EN，若任意 v∈Vl，則 N（v）∈AN；

6）Dom為T中所有葉子節(jié)點的值域；

定義2同態(tài)映射[8]。設(shè)XML模式樹Tm′和Tm之間的映射函數(shù)為 φ：Vm′→Vm，若（Vm′r）=Vmr，則稱映射 φ 為根保持的；若?v′∈Vm′，有 N（v′）=N（φ（v′）），則稱映射 φ 為名字保持的；若φ滿足下面的兩個條件，則稱φ在Tm′和Tm之間是同態(tài)映射。

1）若 Tm′中任意一條邊（v′，w′）∈Am′，則（φ（v′），φ（w′））∈Am；

2）映射φ為根保持和名字保持。

定義3一個集值XML數(shù)據(jù)庫是一個由n棵樹組成的集合，記為 TI={T1，T2，…，Tn}=（V，E，lab，ele，N，Dom，Val），其中Ti=（Vi，Ei，lab，ele，N，Dom，Val），Vele，N，Dom的定義與定義1相同，Val為葉子節(jié)點的取值，且取值可為非原子值。

集值XML數(shù)據(jù)庫對確定的XML數(shù)據(jù)庫進行了擴展，允許葉子節(jié)點的信息值是多個原子值的集合。本文限定TI中任意一棵樹與Tm之間都存在同態(tài)映射，稱TI為Tm的一個實例。T1，T2，…，Tn的信息可以看作是每個對象信息的描述。

定義 4 對于 Ti中的 2個節(jié)點 v′，v″∈Vi，如果存在節(jié)點集合{v1，v2，…，vn}，使得 v1∈ele（v′），v2∈ele（v1），…，vn∈ele（vn-1），v″∈ele（vn）成立，其中，w0=lab（v′），w1=lab（v1），w2=lab（v2），…，wn=lab（vn），wn+1=lab（v″）。

稱w=w0/w1/…/wn+1為一條從w0到wn+1的一條路徑；

稱v′.v1.….vn.v″為通過路徑w的一個路徑節(jié)點集。用函數(shù)last（w）表示通過路徑w的一個路徑節(jié)點集的最后節(jié)點。

若w0為根節(jié)點，wn+1為葉子節(jié)點，則稱w為全路徑。Path（Tm）表示Tm的所有全路徑集合，集值XML數(shù)據(jù)庫模型Tm可以看作Path（Tm）的并集構(gòu)成的樹。

定義5設(shè)Tm為一個集值XML數(shù)據(jù)庫模型，集值XML數(shù)據(jù)庫TI為Tm的一個實例，Path（Tm）表示Tm的所有全路徑集合 。 ?p∈Path（Tm），?Ti，Tj∈TI，若 Val（lasti（p））=Val（lastj（p）），則稱 Ti，Tj子樹存在信息冗余，記作 Ti|Tm≡Tj|Tm，其中l(wèi)asti（p）表示在Ti中通過路徑p的路徑節(jié)點集的最后節(jié)點。若Val（lasti（p））∩Val（lastj（p））≠ψ，則稱 Ti，Tj子樹存在信息相似冗余，記作 Ti|Tm≈Tj|Tm。 其中，i∈[1，n]，j∈[1，n]。

2 XML近似多值依賴

若根據(jù)相似冗余直接定義XML近似多值依賴 （記作XAMVD），會導(dǎo)致XAMVD的定義條件太寬松。為了克服這個缺陷，下面給出相似關(guān)系的定義。

定義 6 相似關(guān)系。 設(shè) Tm、TI、Path（Tm）的定義同定義 5，p ∈Path （Tm），Ti，Tj∈TI，Ti|p ≈Tj|p。 設(shè) α =，α∈[0，1]其中 card（ ）表示路徑信息值的個數(shù)，則稱Ti與Tj在路徑p上具有α級相似關(guān)系，記作 Ti|p≈Tj|p=α。

下面給出XAMVD的定義。定義 7設(shè) Tm、TI、Path （Tm） 的定義同定義 5。 在 Tm上的XAMVD具體表現(xiàn)形式為其中Tm）且 P=且 Q={q1，q2，…，qv}，R=Path（Tm）-（P∪Q）且 R={r1，r2，…，rw}。 如果在 TI中存在兩個子樹 T1，T2滿足 T1|pb≈T2|pb，其中 b∈[1，u]。 則在 TI中必存在子樹 T3（T3可以與T1，T2相同）滿足如下條件：

1）T3|pb≈T1|pb或 T3|pb≈T2|pb。 其中 b∈[1，u]。

由于子樹T1，T2的對稱性，一定存在另一個子樹T4∈TI滿足以下條件：

1）T4|pb≈T2|pb或 T4|pb≈T1|pb。 其中 b[1，u]。

3 XAMVD的判定算法

下面采用粒計算中等價粒的位模式研究XAMVD的判定問題。

定義 8 設(shè) Tm、TI、Path（Tm）的定義同定義 5，p∈Path（Tm），Domp為TI中通過路徑p的所有葉子節(jié)點的值域，稱Domp中語義相同但命名不同的值為一個等價粒，Domp為所有等價粒的并集。|Domp|表示等價粒的個數(shù)，設(shè)|Domp|=M，路徑p的等價粒記為 Domp1，Domp2，···，DompM。

定義 9 設(shè) Tm、TI、Path（Tm）的定義同定義 5，p∈Path（Tm），Ti∈TI={T1，T2， …，Tn}，i∈[1，n]，Ti在 p 上的信息值為 dip={d1，d2，…，df}，其中 dc為原子值，dip為原子值的集合，c∈[1，f]。 Bit為映射函數(shù)，Bit：biti1biti2…biti|Domp|， 其映射值為： 當(dāng) dc∈Dompj時，bitij=1， 當(dāng) dc?Dompj時，bitij=0。 其中 j∈[1，|Domp|]，c∈[1，f]。

設(shè)全路徑p對應(yīng)的值域為Domp被劃分為M個等價粒，即有 Domp={Domp1，Domp2，…，DompM}，又設(shè)集值 XML 數(shù)據(jù)庫的第i棵子樹為Ti，其在全路徑p上的信息值記為：dip={d1，d2，…，df}，其中 dc為原子值，dip為原子值的集合，c∈[1，f]。 下面給出dip轉(zhuǎn)換為由M位二進制位串表示的算法。

算法1 Path－Bit－Pattern{求全路徑信息值的位模式}

輸入：全路徑 p，Domp={Domp1，Domp2，…，DompM}，dip={d1，d2，…，df}。

輸出：p 在 Ti中的位模式 Bit（dip），1≤i≤n。

Path－Bit－ Pattern（p，Domp，dip）

begin

1）Bit （dip）=00…0；（初始化 dip轉(zhuǎn)換為相應(yīng) M 位二進制串，即共有M位0串）

2）for each dh∈dipdo（這里：1≤h≤f）

if dh∈Domprthen（這里：1≤r≤M）

置 Bit（dip）中的第 r位 bitir為 1；

3） return（Bit（dip））；

end.

定理1設(shè)TI中子樹的個數(shù)為n，全路徑p對應(yīng)的信息值的個數(shù)最大為m（一般情況下m

證明：算法1的時間復(fù)雜度為O（m），求p在TI中的位模式需要調(diào)用算法n次，所以求得p在TI中的位模式算法時間復(fù)雜度為O（nm）。 證畢。

下面給出利用粒計算的位表示法來檢測兩個全路徑或全路徑集之間是否存在XAMVD的算法。

設(shè) Tm為集值 XML 數(shù)據(jù)庫模型，TI={T1，T2，…，Tn}為集值XML 數(shù)據(jù)庫且是 Tm的一個實例，P、Q?Path （Tm）。 P={p1，p2，…，pu}，P 在 Ti中的位模式 Bit（Pi）為 Bit（p1i）+Bit（p2i）+…+Bit（pui），Q={q1，q2，…，qv}，Q 在 Ti中的位模式 Bit（Qi）為 Bit（q1i）+Bit（q2i）+…+Bit（qvi），R={r1，r2，…，rw}，R 在 Ti中的位模式 Bit（Ri）為 Bit（q1i）+Bit（q2i）+…+Bit（qwi），其中+表示位的連接運算。

算法2 Determine－XAMVD{XAMVD的判定算法}

輸入：全路徑集 P、Q、R。

Determine－XAMVD（P，Q，R）

begin

1）flag1=0；flag2=0；

2）利 用 算 法 1 求 出 {Bit（P1），Bit（P2），… ，Bit（Pn）}，{Bit（Q1），Bit（Q2），…，Bit（Qn）}，{Bit（R1），Bit（R2），…，Bit（Rn）}。

3）for i=1 to n－1 do

for j=i+1 to n do

if（αb＞0）then//{其中 b[1，u]}

flag1=flag1+1；

if （βb≥αb≠0） ∨（χb≥αb≠0） then//滿 足XAMVD定義的條件1）。

定理2設(shè)TI中子樹的個數(shù)為n，算法2的時間復(fù)雜度為O（n2）。

證明：算法2在第2）步求全路徑P、Q的位模式的時間復(fù)雜度為O（mn）；算法2中第3）步的雙重循環(huán)時間復(fù)雜度為O（n2）；算法 2 的時間復(fù)雜度為 O（mn）+O（n2），又因為一般情況下m

采用二進制表示集值XML數(shù)據(jù)庫的多值信息，使得數(shù)據(jù)格式更接近機器的內(nèi)部表示，算法的運算效率與速度得到了提高，同時解決了具有相同語義而命名不同的信息值在普通的集合運算下難以區(qū)分的問題。

4 實例分析

根據(jù)前述所提出的理論，本節(jié)給出實例，進行分析。

例5-1下面給出一個描述學(xué)校課程安排情況的實例，一門課程可以由多個老師講授，一門課程可以對應(yīng)多門教材，也就是說課程與老師之間存在一對多的聯(lián)系，課程與教材之間也存在一對多的聯(lián)系。集值XML數(shù)據(jù)庫T存儲了課程（course）“數(shù)據(jù)庫”的安排情況，課程“數(shù)據(jù)庫”對應(yīng)的教材為{數(shù)據(jù)庫系統(tǒng)教程，DB2}、{數(shù)據(jù)庫原理，SQL Server2000}和{數(shù)據(jù)庫原理，DB2，SQL Server2000}，這門課程由{王一，張三}、{王一，張三，李四}和{趙二，李四}講授。T如圖 1所示。

圖1 集值XML數(shù)據(jù)庫TFig.1 Set-valued XML database T

由圖 1可以看出，T由四棵子樹組成， 即 T={T1，T2，T3，T4}。 T的模式由全路徑 p，q，r的并集組成， 其中 p=department/course/cname，q =department/course/teacher/tna -me，r=department/course/teacher/text/textname。 各個全路徑所對應(yīng)信息根據(jù)語義相同名字不同滿足如下等價關(guān)系：

department/course/cname:{[數(shù)據(jù)庫]}；

department/course/teacher/tname:{[王一]，[張三]，[趙二]，[李四]}；

department/course/teacher/text/textname:{[數(shù)據(jù)庫系統(tǒng)教程]，[DB2]，[數(shù)據(jù)庫原理]，[SQL Server2000]}；在 T 中全路徑所對應(yīng)的數(shù)據(jù)信息的位模式如表1所示。

利用算法2判定表 1中p，q，r三者之間的依賴關(guān)系，由T1|p≈T2|p=1，存在 T3滿足 T3|p≈T2|p=1，T3|q≈T1|q=2/3≤1，T3|r≈T2|r=2/3≤1 成立，存在 T4滿足T4|r≈T1|r=1成立，根據(jù)XAMVD的定義在T上成立。

表1 全路徑信息的位模式表Tab.1 Bit-pattern of full-path information

通過此實例表明信息值采用位表示，在進行XAMVD的判定時，避免了繁雜的字符串比較，提高了算法的效率。

5 結(jié)束語

目前，基于粒計算的方法研究不確定XML多值依賴的判定問題，在國內(nèi)外還處于空白。本文對確定的XML數(shù)據(jù)進行了擴展，允許葉子節(jié)點的信息值是多個原子值的集合。采用粒計算的位模式表示方法研究了XML近似多值依賴的判定問題，根據(jù)本方法可以發(fā)現(xiàn)潛在未知的XAMVD，信息值采用位模式，一方面使得數(shù)據(jù)格式更接近機器的內(nèi)部表示，算法的運算效率與速度得到了提高；另一方面解決了具有相同語義而命名不同的信息值在普通的集合運算下難以區(qū)分的問題。

下一步的研究重點主要集中在以下方面：

1）分析集值XML數(shù)據(jù)庫中存在XAMVD引起的數(shù)據(jù)冗余，提出規(guī)范化算法。

2）對集值XML數(shù)據(jù)的查詢進行研究。

[1]Yao Y Y.Paul P.Granular computing:Basic issues and possible solutions[C]//Proceedings of the 5th Joint Conference on Information Sciences.USA：Elsevier Publishing Company，2000:186-189.

[2]王國胤，張清華，胡軍.粒計算研究綜述[J].智能系統(tǒng)學(xué)報，2007，2（6）:8-26.WANG Guo-yin，ZHANG Qing-hua，HU Jun.An overview of granular computing[J].CAAITransactions on Intelligent Systems，2007，2（6）:8-26.

[3]苗守謙，李道國.粗糙集理論、算法與應(yīng)用[M].北京：清華大學(xué)出版社，2008.

[4]殷麗鳳，郝忠孝.不完全信息環(huán)境下存在XML強多值依賴的XML文檔的規(guī)范化研究[J].計算機研究與發(fā)展，2009，46（7）:1226-1233.YIN Li-feng，HAO Zhong-xiao.Normalization of XML document with strong MVD under incomplete information circumstances[J].Journal of Computer Research and Development，2009，46（7）:1226-1233.

[5]王建衛(wèi)，郝忠孝.概率XML文件樹結(jié)點概率的查詢算[J].計算機研究與發(fā)展，2012，49（4）:785-794.WANG Jian-wei，HAO Zhong-xiao.The query algorithm for probabilistic XML document tree node probability[J].Journal of Computer Research and Development，2012，49 （4）:785-794.

[6]ABITEBOUL S，HUBERT CHAN T-H，KHARLAMOV E.Aggregate queries for discrete and continuous probabilistic XML [C]//The 13th International Conference of Database Theory.Lausanne， Switzerland，2010:50-61.

[7]NING B，LIU C F，YU J X，et al.Matching Top-k answers of twig patterns in probabilistic XML[C]//Database systems for advanced applications， the 15th international conference，Tsukuba， Japan，2010:125-139.

[8]Hartmann S，Link S，Kirchberg M.A subgraph-based approach towards functional dependencies for XML[C]//Seventh World-Multi conference on Systemics，Cybernetics and Informatics， invited Session:Dependencies on the Web，2003:200-205.