曹路舟

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

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

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

一、相關(guān)定義及符號聲明

定義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é)點(diǎn)型路徑；若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é)點(diǎn)，q-last(q)表示路徑q在除去最后一個節(jié)點(diǎn)路徑后的路徑，本文僅考慮最后一個元素不為空的情況；

(2)Paths(T) 表示文檔樹T中所有路徑的集合,即Paths(T)={q|q是T中的路徑}；其中EPaths(T) 、APaths(T) 、VPaths(T)分別表示元素節(jié)點(diǎn)類型路徑的集合、屬性值類型路徑的集合和文本值類型路徑的集合，即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é)點(diǎn)值相等)對于一個給定DTD D=(E,A,P,R,r)和滿足了這個給定D的XML 文檔樹T=(V , lab,ele,att,val,root)，r1和r2是V中的節(jié)點(diǎn)，r1與r2是值相等記為r1=vr2，充分必要條件是：(1)lab(r1)=lab(r2)；(2)若r1和r2是A節(jié)點(diǎn)或者S節(jié)點(diǎn)，則val(r1)=val(r2)；(3)若r1和r2是E節(jié)點(diǎn)，則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約束范圍內(nèi)，如果有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是層次結(jié)構(gòu)，如果沒有此說明，就會丟失層次之間的約束關(guān)系。

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

圖1 一個有路徑冗余的DTD D結(jié)構(gòu)

定義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的約束范圍內(nèi)，[S1,S2,…,Sn]唯一標(biāo)識路徑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)范圍內(nèi)，有一組路徑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ù)的重復(fù)存儲,若某對象數(shù)據(jù)在同一路徑上被重復(fù)存儲，則稱為路徑冗余。如圖1的結(jié)構(gòu)中，路徑college.course.student.credit就是路徑冗余。

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

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

【定理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路徑都存在著與之相對應(yīng)的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]上結(jié)點(diǎn)一樣,而在Sy上結(jié)點(diǎn)卻互異。又φ：Hz[H1,H2,…,Hm→X]，因此這些樹元組在不同的Sy子樹的X路徑上結(jié)點(diǎn)值必定一樣。因而在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，用φ'替代φ，重復(fù)步驟1，直到?jīng)]有路徑X'結(jié)束。

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

算法描述結(jié)束。

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

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

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

【定理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適合用反正法證明，具體證明過程如下：

證明：假設(shè)在文檔樹T(T╞D)中以G為根的所有子樹下[S1,S2,…,Sn]路徑無重復(fù)出現(xiàn)，即在G的約束范圍內(nèi)，Sy可以被[S1,S2,…,Sn]所唯一標(biāo)識，根據(jù)前面鍵的相關(guān)定義可以得出S是[S1,S2,…,Sn]唯一標(biāo)識Sy最大的約束范圍，即S?pathsG。這與條件中G?pathsS不相符，因而假設(shè)不能夠成立，在T(T╞D)中以G為根的子樹下[S1,S2,…,Sn]的路徑存在著冗余。又由于函數(shù)依賴FD φ：G[S1,S2,…,Sn→X]，所以[S1,S2,…,Sn]路徑冗余必定也會導(dǎo)致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結(jié)點(diǎn)下，成為其子樹，如圖3(b)所示。否則，在last(G)下創(chuàng)建一個新結(jié)點(diǎn)new，根是last(X)結(jié)點(diǎn)的子樹結(jié)構(gòu)往上移動到new結(jié)點(diǎn)下，成為其子樹，而根是last(Si)的子樹結(jié)構(gòu)也整體復(fù)制到新結(jié)點(diǎn)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，用φ'替代φ，重復(fù)步驟1，直到?jīng)]有路徑G'結(jié)束。

步驟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(τ)，新結(jié)點(diǎn)new為last(H)，則跳過步驟3直接進(jìn)入步驟4；

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

…，n)為根的所有子樹的結(jié)構(gòu)都復(fù)制到new結(jié)點(diǎn)下成為new結(jié)點(diǎn)的子樹。

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

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

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

算法描述結(jié)束。

證明：由定理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ù)依賴導(dǎo)致的路徑冗余實(shí)例

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

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

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

四、結(jié)束語

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