函數(shù)依賴導致的XML路徑冗余的判定和消除 *

曹路舟

(池州職業(yè)技術學院 信息技術系，安徽 池州 247000)

由于XML(Xtensible Markup Language)在Internet上的應用非常廣泛，因此XML在具體使用過程中為了得到高質量的數(shù)據(jù)，對其模式的設計就顯得特別重要，而其中DTD(Document Type Definition)模式的設計一直倍受廣大XML研究者關注。DTD模式的研究主要包括以下幾個方面的內容：怎樣判定一個DTD模式設計是否良好；如果是一個設計不好的DTD，我們要通過什么樣方法將其轉化成一個滿足要求的好的DTD模式等。如何來判定一個DTD設計是否良好呢？其主要依據(jù)是檢查該DTD有沒有存在著數(shù)據(jù)冗余信息，如果存在著數(shù)據(jù)冗余信息，它就和關系數(shù)據(jù)庫一樣，會引起XML文檔的插入、刪除、更新等操作異常，這勢必影響到XML在不同應用程序之間的數(shù)據(jù)表示和交換上的使用。

本文利用XML層次結構特點，從路徑的角度出發(fā)，提出了由XML函數(shù)依賴引起的XML文檔樹有路徑冗余的幾種可能存在的情形，并相應的給出了消除冗余的方法及其相關的正確性證明，最后通過具體的實例驗證了定理的正確性和有效性。

一、相關定義及符號聲明

定義1(XML路徑)給定DTD D(E,A,P,R,r)和滿足D的XML文檔樹T( V,lab,ele,att,val,root),文檔樹T中的路徑可以定義如下：路徑q=v1.…. vn,其中,v1=root, vk∈ele(vk-1), (k=2,…,n-1)。若lab(vn)∈E，vn∈

ele(vn-1)， P(lab(vn))≠S，則稱該路徑q為元素節(jié)點型路徑；若lab(vn)∈A，vn∈att(vn-1)或lab(vn)∈E，vn∈ele(vn-1)，P(lab(vk))=S，則稱該路徑q為值類型路徑。

XML路徑說明：

(1)令last(q)=vn,表示路徑q中的最后一個節(jié)點，q-last(q)表示路徑q在除去最后一個節(jié)點路徑后的路徑，本文僅考慮最后一個元素不為空的情況；

(2)Paths(T) 表示文檔樹T中所有路徑的集合,即Paths(T)={q|q是T中的路徑}；其中EPaths(T) 、APaths(T) 、VPaths(T)分別表示元素節(jié)點類型路徑的集合、屬性值類型路徑的集合和文本值類型路徑的集合，即EPaths(T)={q|q∈Paths(T)且lab(last(q))∈E}、APaths(T)={q|q∈Paths(T)且lab(last(q))∈A}和VPaths(T)={q|q∈Paths(T)且last(q)∈E，P(lab(last(q)))=S}。

定義2(路徑包含) 兩條路徑r1,r2，(r1,r2∈Paths(D))，如果r1只是r2的一部分，則可表示為r1?Pathsr2；如果r1可能是r2的一部分也可能是完全一樣，則可表示為r1?Pathsr2。

定義3(樹元組) 給定DTD D=(E,A ,P,R,r)和滿足D的XML文檔樹T=(V , lab , ele , att , val , root)，樹元組t被定義成Paths(D)到V∪S∪{⊥}的映射，則t會滿足以下幾種可能情況：⑴若q∈EPaths(D)，則t[q]∈V∪{⊥}，且t[q] ≠⊥；否則t[q]∈S∪{⊥}；⑵若t[q1]=t[q2]且t[q1]∈V，則q1=q2；⑶若t[q1]=⊥且q1是q2的前綴，則t[q2]=⊥；⑷{q∈Paths(D)|t[q] ≠⊥}不是無限的，而是有限的。

上述定義中的S表示為字符串值,⊥表示為空值，樹元組t[q]也可以表示為t.q，同時本文用T[T]={t|t∈T}來表示所有樹元組的集合。

定義4 (節(jié)點值相等)對于一個給定DTD D=(E,A,P,R,r)和滿足了這個給定D的XML 文檔樹T=(V , lab,ele,att,val,root)，r1和r2是V中的節(jié)點，r1與r2是值相等記為r1=vr2，充分必要條件是：(1)lab(r1)=lab(r2)；(2)若r1和r2是A節(jié)點或者S節(jié)點，則val(r1)=val(r2)；(3)若r1和r2是E節(jié)點，則1)?m1∈att(r1)， m2∈att(r2)，滿足m1=vm2，反之同樣成立；2)若ele(r1)=v1,…,vk，ele(r2)=v1’,…,vk’，則所有的i∈[1,k]，都有vi=vvi’。

定義5 (函數(shù)依賴FD) 給定DTD D=(E , A , P , R , r)和D上的函數(shù)依賴FDφ：

(Sh,[Sx1,…,Sxn]→Sy)，對于滿足了D的XML文檔樹T，則稱T滿足函數(shù)依賴φ充分必要條件是對T(T╞D)中任意兩個t1和t2(樹元組)，在Sh約束范圍內，如果有t1[Sxj]=vt2[Sxj]，(j=1,2,…,n)，則一定有t1[Sy]= vt2[Sy]。

函數(shù)依賴FD的說明：

(1)Sh、[Sx1,…,Sxn]和Sy分別表示函數(shù)依賴φ的頭部路徑、左部路徑和右部路徑，其中Sh∈Paths(D)，Sxj∈Paths(D)(j=1,2,…n)，Sh?PathsSxj,而Sy∈Paths(D)或Sy=ε，Sh?PathsSy；

(2)若Sh=φ，叫做絕對函數(shù)依賴，即表示φ在整個D上都是成立的，否則叫做相對函數(shù)依賴；

(3)若Sy=(Sy為空時)，F(xiàn)D本身是無任何意義的，但由于XML是層次結構，如果沒有此說明，就會丟失層次之間的約束關系。

如圖1中存在函數(shù)依賴FDφ:(college.course,[college.course.student.sno] →college.course.student.grade)等。

圖1 一個有路徑冗余的DTD D結構

定義6(鍵)給定T╞D，?t1,t2∈T[T]，路徑S?pathsSy?pathsSk(k=1,2,…,n)，其中l(wèi)ast(Sy)*∈P(last(Sy-last(Sy)))，last(Sk)∈E∪A。若t1[S]=t2[S]且t1[Sk]=vt2[Sk]成立時t1[Sy]=t2[Sy]也成立，則稱在S的約束范圍內，[S1,S2,…,Sn]唯一標識路徑Sy，定義S[S1,S2,…,Sn]為Sy的鍵，如果沒有{S1’,S2’,…,Sm’}?{S1,S2,…,Sn}，S[S1’,S2’,…,Sm’]也是Sy的一個鍵，則定義S[S1,S2,…,Sn]為Sy的主鍵，鍵子樹是指以last(Sy)為根的子樹。

在圖1中，在college.course的約束范圍下，由鍵的定義得知college.course[college.course.student.sno]既是college.course.student的一個鍵，同時也是它的一個主鍵。

定義7(外鍵) 給定D上S[S1,S2,…,Sn]為Sy的一個鍵，在路徑H(S?pathsH)范圍內，有一組路徑H1,H2,…,Hm。若S為根的子樹中，T[H[H1,H2,…,Hm]]?T[S[S1,S2,…,Sn]]，則[H1,H2,…,Hm]是H相對于S[S1,S2,…,Sn]的一個外鍵。

如圖4中，college.course[college.course.student.sno]是college.course.student的鍵，又是college.course相對于college. new.sno的外鍵。

二、XML路徑冗余判定和消除算法

1.路徑冗余

數(shù)據(jù)冗余可以直觀的理解為同一對象數(shù)據(jù)的重復存儲,若某對象數(shù)據(jù)在同一路徑上被重復存儲，則稱為路徑冗余。如圖1的結構中，路徑college.course.student.credit就是路徑冗余。

2. 受鍵子樹以外的其他路徑約束

如圖2(a)結構所示：這是一種在鍵子樹內的路徑被不是該鍵子樹內的其他路徑約束的一種情況。

【定理1】D上S[S1,S2,…,Sn]為Sy的鍵，且有FD φ：Hz[H1,H2,…,Hm→X]，其中Hz?pathsSy?pathsX，last(X)∈P(last(Sy))，last(Hj)?P(last(Sy))，last(Hj)∈P(last(Hz))(j=1…m)，則T(T╞D)中以Hz為根的子樹下X路徑冗余。

證明：由于S[S1,S2,…,Sn]為Sy的鍵，Hz?pathsSy，故文檔樹T(T╞D)在以Hz為根的所有子樹中，很多次的出現(xiàn)了Sy路徑；又由于last(X)∈P(last(Sy))，故出現(xiàn)的每一條Sy路徑都存在著與之相對應的X路徑；同時last(Hj)∈P(last(Hz))，故而在文檔樹T(T╞D)以Hz為根的所有子樹中，Hi(i=1…m)路徑會出現(xiàn)一次，而且是僅出現(xiàn)一次。

所以存在j個不相同的樹元組t1,t2…，tj，在Hz，[H1,H2,…,Hm]上結點一樣,而在Sy上結點卻互異。又φ：Hz[H1,H2,…,Hm→X]，因此這些樹元組在不同的Sy子樹的X路徑上結點值必定一樣。因而在Hz為根的所有子樹中，就存在著j條一樣的路徑X，即T(T╞D)中以Hz為根的子樹下X路徑冗余。

證畢。

如圖1中，依據(jù)定理1，路徑college.course.student.credit在college.course.student鍵子樹中被該鍵子樹以外的路徑college.courses.cno相約束，從而出現(xiàn)了路徑冗余。

如何消除定理1中出現(xiàn)的路徑冗余呢？解決的方法就是將冗余的X路徑移出鍵子樹，以last(X)為根的子樹往上移成last(Hz)的子樹即可。如圖2(b)所示。消除定理1中X路徑冗余的具體算法描述如下：

【算法1】

步驟1：尋找滿足定理1中所描述情況的最大的X子樹。

若存在著路徑X'，函數(shù)依賴φ'：Hz[H1,H2,…,Hm →X']，Sy ?pathsX'?pathsX，則用X'替代X，用φ'替代φ，重復步驟1，直到?jīng)]有路徑X'結束。

步驟2：D=(E,A,P,R,r)變換為D'=(E,A,P',R',r)，根是last(X) 結點的子樹結構整體往上移動，變成last(Hz)結點的子樹。

算法描述結束。

證明：在D上以Hz為根的子樹中，X路徑在last(Sy)子樹中重復出現(xiàn)k次。在D'上，last(X)為根的子樹與last(Sy)子樹語義無關，以Hz為根的子樹中X路徑只出現(xiàn)一次。證畢。

3. 在鍵約束范圍以外受鍵約束

如圖3(a)結構所示:這是一種鍵對鍵子樹內的路徑的約束超過了鍵本身的約束范圍。

【定理2】D上S[S1,S2,…,Sn]為Sy的鍵，且存在FD φ：G[S1,S2,…,Sn→X]，G?pathsS?pathsSy?pathsX，

last(X)∈P(last(Sy))，則在T(T╞D)中以G為根的子樹下X路徑冗余。

定理2適合用反正法證明，具體證明過程如下：

證明：假設在文檔樹T(T╞D)中以G為根的所有子樹下[S1,S2,…,Sn]路徑無重復出現(xiàn)，即在G的約束范圍內，Sy可以被[S1,S2,…,Sn]所唯一標識，根據(jù)前面鍵的相關定義可以得出S是[S1,S2,…,Sn]唯一標識Sy最大的約束范圍，即S?pathsG。這與條件中G?pathsS不相符，因而假設不能夠成立，在T(T╞D)中以G為根的子樹下[S1,S2,…,Sn]的路徑存在著冗余。又由于函數(shù)依賴FD φ：G[S1,S2,…,Sn→X]，所以[S1,S2,…,Sn]路徑冗余必定也會導致T(T╞D)中以G為根的子樹下有X路徑冗余的存在。

證畢。

如圖1中，路徑college.course.student.sdept就是定理2中描述的這種路徑冗余。

消除定理2中的X路徑冗余的方法跟消除定理1的方法不同，它是將原T(T╞D)中的鍵變成其他鍵的外鍵。如果[S1,S2,…,Sn]是S相對于G[H1,H2,…,Hm]的一個外鍵，則將last(X)為根的所有子樹往上移動到G結點下，成為其子樹，如圖3(b)所示。否則，在last(G)下創(chuàng)建一個新結點new，根是last(X)結點的子樹結構往上移動到new結點下，成為其子樹，而根是last(Si)的子樹結構也整體復制到新結點new下，從而使[S1,S2,…,Sn]是S相對于G[G.new.last(S1),G.new.last(S2),…,G.new.last(Sn)]的一個外鍵，如圖3(c)所示。消除定理2中X路徑冗余的具體算法描述如下：

【算法2】

步驟1：尋找滿足定理2條件中的最大范圍的G。

如果存在G',存在函數(shù)依賴FD φ'：G'[S1,S2,…,Sn →X], G'?pathsG，則用G'替代G，用φ'替代φ，重復步驟1，直到?jīng)]有路徑G'結束。

步驟2：如果存在著路徑組{H,H1,H2,…,Hm}，G[H1,H2,…,Hm]是H的鍵，[S1,S2,…,Sn]是S相對于G[H1,H2,…,Hm]的一個外鍵，則D=(E,A,P,R,r)變換成D'=(E',A,P',R',r)，E'=E，?τ∈E，R'(τ)=R(τ)，P'(τ)=P(τ)，新結點new為last(H)，則跳過步驟3直接進入步驟4；

步驟3：D=(E,A,P,R,r)變換成D'=(E',A,P',R',r)，同時在last(G)下創(chuàng)建一個新結點new，而以last(Si)(i=1，

…，n)為根的所有子樹的結構都復制到new結點下成為new結點的子樹。

步驟4：尋找滿足上述情況的最大X子樹。

如果存在路徑X'，F(xiàn)D φ'：G[S1,S2,…,Sn→X']，Sy?pathsX'?pathsX，則用X'替代X，用φ'替代φ，重復步驟4，直到?jīng)]有路徑X'結束。

步驟5：根是last(X)結點的子樹結構往上移動，成為新結點new的子樹，更改D'=(E',A,P',R',r)。

算法描述結束。

證明：由定理2為例證明。若[S1,S2,…,Sn]是S相對于G[H1,H2,…,Hm]的一個外鍵，原D上φ在D'上改為φ'：G[H1,H2,…,Hm→G.new.last(X)]，G.new.last(X)沒有路徑冗余

若[S1,S2,…,Sn]不是S相對于G[H1,H2,…,Hm]的一個外鍵，經(jīng)過步3在D'上，[S1,S2,…,Sn]是S相對于G[G.new.last(S1),G.new.last(S2),…,G.new.last(Sn)]的一個外鍵。同上，以G為根的子樹下，G.new.last(X)路徑冗余就沒有了。證畢。

三、消除函數(shù)依賴導致的路徑冗余實例

依據(jù)定理1和算法1，credit節(jié)點從student節(jié)點下移走，插入到course節(jié)點下；

依據(jù)定理2和算法2，建立new結點，sno和sname,sdept為其子結點。

函數(shù)依賴導致的XML路徑冗余就消除了，如圖4所示。

四、結束語

從文中實例可以得出：產(chǎn)生路徑冗余的原因是由于一棵子樹的根與這棵子樹中其他的數(shù)據(jù)都存在著一定的關聯(lián)，使語義上本來毫無聯(lián)系的數(shù)據(jù)在樹中也形成了層次約束。消除路徑冗余的方法就是理順樹中這種語義約束關系。文章在已有的研究基礎之上，給出了由于函數(shù)依賴而產(chǎn)生的路徑冗余的判定及其消解過程，然而多值依賴同樣也會導致路徑冗余，而且也比函數(shù)依賴導致的路徑冗余要復雜的多，怎樣解決多值依賴導致的路徑冗余，這是以后進一步要研究的內容，同時路徑冗余的研究對XML范式研究和保障XML正確應用有著積極的意義。