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

金 花，殷麗鳳

（大連交通大學 軟件學院，遼寧 大連 116028）

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

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

1 基本概念

為了研究近似XML多值依賴，首先給出集值XML數據庫模型、集值XML數據庫、相似冗余等相關定義。

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

1）Vm表示樹的節點的集合；Vm=Vms∪Vml∪Vmr， 其中 Vms表示結構信息，即分支節點；Vml表示數據信息，即葉子節點；Vmr代表根節點。

2）Em表示樹邊的集合；

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

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

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

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

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

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

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

定義3一個集值XML數據庫是一個由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為葉子節點的取值，且取值可為非原子值。

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

定義 4 對于 Ti中的 2個節點 v′，v″∈Vi，如果存在節點集合{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的一個路徑節點集。用函數last（w）表示通過路徑w的一個路徑節點集的最后節點。

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

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

2 XML近似多值依賴

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

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

下面給出XAMVD的定義。定義 7設 Tm、TI、Path （Tm） 的定義同定義 5。 在 Tm上的XAMVD具體表現形式為其中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 設 Tm、TI、Path（Tm）的定義同定義 5，p∈Path（Tm），Domp為TI中通過路徑p的所有葉子節點的值域，稱Domp中語義相同但命名不同的值為一個等價粒，Domp為所有等價粒的并集。|Domp|表示等價粒的個數，設|Domp|=M，路徑p的等價粒記為 Domp1，Domp2，···，DompM。

定義 9 設 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為映射函數，Bit：biti1biti2…biti|Domp|， 其映射值為： 當 dc∈Dompj時，bitij=1， 當 dc?Dompj時，bitij=0。 其中 j∈[1，|Domp|]，c∈[1，f]。

設全路徑p對應的值域為Domp被劃分為M個等價粒，即有 Domp={Domp1，Domp2，…，DompM}，又設集值 XML 數據庫的第i棵子樹為Ti，其在全路徑p上的信息值記為：dip={d1，d2，…，df}，其中 dc為原子值，dip為原子值的集合，c∈[1，f]。 下面給出dip轉換為由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轉換為相應 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設TI中子樹的個數為n，全路徑p對應的信息值的個數最大為m（一般情況下m

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

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

設 Tm為集值 XML 數據庫模型，TI={T1，T2，…，Tn}為集值XML 數據庫且是 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設TI中子樹的個數為n，算法2的時間復雜度為O（n2）。

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

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

4 實例分析

根據前述所提出的理論，本節給出實例，進行分析。

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

圖1 集值XML數據庫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。 各個全路徑所對應信息根據語義相同名字不同滿足如下等價關系：

department/course/cname:{[數據庫]}；

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

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

利用算法2判定表 1中p，q，r三者之間的依賴關系，由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成立，根據XAMVD的定義在T上成立。

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

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

5 結束語

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

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

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

2）對集值XML數據的查詢進行研究。

[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].智能系統學報，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]苗守謙，李道國.粗糙集理論、算法與應用[M].北京：清華大學出版社，2008.

[4]殷麗鳳，郝忠孝.不完全信息環境下存在XML強多值依賴的XML文檔的規范化研究[J].計算機研究與發展，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]王建衛，郝忠孝.概率XML文件樹結點概率的查詢算[J].計算機研究與發展，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.