XML函數依賴研究綜述*

劉 嘉，廖湖聲

(北京工業大學計算機學院，北京 100124)

XML函數依賴研究綜述*

劉 嘉，廖湖聲

(北京工業大學計算機學院，北京 100124)

函數依賴作為數據庫規范化的基礎在關系理論中起著重要的作用。近年來，XML得到廣泛應用并已成為互聯網上數據傳輸和交換的標準。由于XML半結構化的特性，使得如何定義XML函數依賴使其具有更強的描述能力，以及如何解決相應的邏輯蘊涵問題成為當今學術界所面臨的挑戰。針對這些問題，系統地描述了目前關于XML函數依賴的研究現狀，特別是把分析的重點放在如何定義函數依賴、判斷其蘊涵關系以及從XML文檔中發現函數依賴等問題上。最后討論了諸如類型化函數依賴關系等一些相關的研究方向。

XML；函數依賴；邏輯蘊涵；依賴發現

1 引言

為了適應在互聯網上交換和分享信息的需要，W3C(World Wide Web Consortium)于1998年推出了半結構化的XML(eXtensible Markup Language)標記語言[1]。XML數據的特點是將內容和樣式分離，使用者只需關心數據本身，至于數據樣式的現實則交給另外的技術來完成。隨著XML的廣泛應用，它已經成為互聯網上數據表示和數據交換的事實標準。由于XML數據具有半結構化的特征，使其數據表示非常靈活，也因此使得XML缺乏語法和語義約束。關于XML語法約束，學術界基于正規樹理論提出了多種XML模式語言，例如DTD、XML Schema、DSD、XDuce、 RELAX Core和TREX等[2]。而關于XML語義約束，特別是XML函數依賴問題，近年來也已成為學術界研究的熱點之一。

在傳統的關系數據庫理論中，函數依賴問題的研究已經取得了一定的成就，以其為核心的規范化理論也得到了廣泛的應用。但是，由于XML半結構化的數據結構與關系數據的線性結構有很大不同，因此這些理論無法直接應用于XML模式語言的規范化。關于XML函數依賴的研究，目前主要集中在解決如何定義、判斷蘊涵關系和從XML文檔中發現函數依賴等問題上。

1.1 XML函數依賴定義的分類

由于XML數據靈活的數據結構，對于XML函數依賴的定義，目前尚無統一和完善的理論。根據定義方式的不同，大致可分為以下三類：

(1) 基于樹元組的定義：這種定義方式主要是對關系模型中元組的概念進行了擴展，使其可以表示XML樹形的數據結構，進而可以類比關系模型解決XML函數依賴問題。

(2) 基于路徑的定義：由于XML是一種基于樹形結構的數據表示模型，因此常常使用諸如XPath這樣的路徑描述語言來導航或定位XML文檔中的數據。基于路徑的XML函數依賴定義方式就是使用某種路徑描述語言來表示函數依賴。

(3) 基于子樹的定義：考慮到XML樹形結構的特征，而路徑表述語言只能描述線性的數據結構，無法充分表示樹的特征，因此提出了基于某種描述子樹結構的方法來表示XML函數依賴的定義。該定義利用同態的技術，進一步增強了XML函數依賴的描述能力。

另外，考慮到上述定義的不同特點，其所能描述XML函數依賴的能力必然也有所不同，因此又可以將XML函數依賴的定義分為基本定義和擴展定義兩種。這兩種定義描述能力的區別在于后者可以描述諸如集合、序列等更豐富的XML數據類型。對于基于樹元組和路徑的函數依賴，有些是屬于基本的定義而有些則屬于擴展的定義。基于子樹的函數依賴都屬于擴展的定義。

1.2 XML函數依賴的蘊涵關系

在關系數據庫中，對于任意一個符合關系模式U的關系實例r，若r滿足函數依賴f，則必滿足函數依賴g，稱f蘊涵g。判斷函數依賴之間是否具有依賴關系是數據庫規范化理論的重要內容之一。找到一組有效且完備的公理推導函數依賴被認為是解決該問題的經典方法。但是，文獻[3]已證明，在一般DTD約束的情況下，基于樹元組的XML函數依賴不存在一組有效且完備的公理。當然，這里僅針對在該文獻所提出的XML函數依賴定義進行了證明，但仍然不失一般性，因為造成不能用公理化方法解決函數依賴問題的原因主要在于DTD包含choice。解決方法：一是尋找非公理化方法，二是尋找適合公理化方法的XML模式和函數依賴定義。

1.3 XML函數依賴的發現

函數依賴是一種語義約束，需要在定義模式時加以考慮以避免數據冗余的發生。但在實際應用中，數據庫設計者往往不能了解全部的依賴關系，甚至根本未加考慮，以至于在系統運行一段時間后才發現數據之間可能存在依賴關系。這時就需要找到方法將這種依賴關系從數據中挖掘出來，進而開發者可以根據找到的函數依賴用規范化方法對XML模式進行調整優化，并對數據庫中業已存在的數據進行修改，以適應XML模式的變化。

2 基本定義

為了方便描述XML函數依賴，本節給出一些基本術語的定義。在以下的定義中，我們假設E是XML元素節點的標簽集合；A代表屬性節點的標簽集合；text為文本節點的標記。

定義1XML文檔樹被定義為五元組T={V,root,label,value,children}，其中V代表XML文檔樹中所有節點的集合；root∈V代表文檔樹的根節點；label函數表示從V到E∪A∪{text}的映射，用來為XML文檔樹中的每個節點分配相應的標簽。對于任意一個XML文檔樹中的節點n，若n是元素節點，則label(n)∈E；若n是屬性節點，則label(n)∈A，若n是文本節點，則label(n)={text}。value函數用于求屬性節點和文本節點的值，而children函數用于求元素節點的子節點集合。對于XML文檔樹中的任意兩個節點u、v，若u∈children(v)，則稱u是v的孩子節點，v是u的雙親節點。

和關系數據庫中的模式定義相似，XML也需要定義模式來約束XML數據。目前學術界已提出多種XML模式描述語言，例如DTD、XML Schema、DSD、XDuce等。本文從這些模式語言中抽取一個核心子集，定義如下：

定義2XML模式被定義為四元組S={E′,A′,type，R}, 其中E′?E，A′?A分別代表滿足該模式的XML文檔樹中所能出現的元素節點和屬性節點的標簽集合；type函數表示E′中任意元素節點標簽所對應的節點類型，我們可以用正規式τ=ε|tag[τ] |τ,τ|τ|τ|τ*表示該節點類型,tag∈E′∪A′∪{text}；R∈E′并且R不在E′中任何其他元素節點標簽所對應的節點類型正規式出現，換句話說，R代表根元素節點標簽。

對于任一XML模式S，我們稱XML文檔樹T滿足模式S，若T滿足以下三個條件：

(1)label(root)=R。

(2) 對于樹中的任一元素節點e，label(e)∈E′。

(3) 對于樹中的節點e的任一孩子節點n，若n是元素節點或屬性節點，則label(n)在type(label(e))中; 若n是文本節點，則標記text在type(label(e))中。

圖1顯示了一個XML模式和滿足該模式的XML文檔樹的例子。為了方便起見，我們在屬性節點和文本節點前分別加上@和$。

Figure 1 Xml schema and XML document tree圖1 XML模式和XML文檔樹

定義3路徑是形如s1,s2,…,sk的表達式(k>0)，其中si∈E∪A∪{text}(1≤i≤k)。路徑式的路徑實例w定義于XML樹之上，是一個形如〈v1,v2,…,vk〉的節點序列，且滿足條件：對于vi∈V，1

例如，在圖1中，路徑式scores.score.pname.$text的路徑實例有三個，依次包含了scores、score、pname和$text節點。

定義4節點值相等。對于一棵XML文檔樹的兩個節點n1和n2，若label(n1) =label(n2)，并且若n1和n2都是屬性節點或者文本節點，且value(n1)=value(n2)；若n1和n2都是元素節點，并且它們的孩子節點也兩兩值相等，則稱n1和n2的值相等，簡記為n1=vn2。

3 XML函數依賴的定義

在關系模型中，函數依賴的定義是唯一的。設X、Y是關系U的兩個屬性集合，當任何時刻U中的任意兩個元組中的X屬性值相同時，它們的Y屬性值也相同，則稱X函數決定Y，或Y函數依賴于X。而對于XML數據模型來說，由于其樹形的半結構化特征和復雜的模式語言，至今沒有統一的XML函數依賴定義。這些定義根據表達形式可以簡單地分為基于樹元組的定義、基于路徑的定義和基于子樹的定義三種。在下面的描述中，用XFD1,…, XFDk來代表不同文獻中定義的XML函數依賴。

3.1 基于樹元組的XML函數依賴定義

XFD1文獻[3]將關系模型中元組的概念擴展到XML數據模型中。作者首先將XML模式映射到關系模式，設D為XML模式，則paths(D)表示D中的所有路徑集合。例如，圖1a的XML模式的路徑集合為：

scores;

scores.score;

scores.score.@pno;

scores.score.pname;

scores.score.$item;

scores.score.@point;

scores.score.pname.$text。

路徑集合中的每一條路徑都可以認為是關系模式中的一個屬性。由這些路徑在一棵XML文檔樹中所匹配的一組可達節點就可以組合一個樹元組。例如，圖2即為圖1b中XML文檔樹中的一個樹元組。

Figure 2 Tree tuple圖2 樹元組

基于樹元組的函數依賴XFD1被定義為如下形式：p1, p2,…, pk→q1,…, qm，其中p1, p2, …,pk和q1, …,qm是XML模式D路徑集中的路徑。一棵滿足D的XML文檔樹T，若對于屬于T的任意兩個樹元t1和t2，如果t1(p1, p2,…, pk) =vt2(p1, p2,…, pk)，且t1(p1, p2,…, pk)≠null，都有t1(q1,…, qm)=vt2(q1,…, qm)，則稱T滿足XFD1。例如,對于圖1b的文檔樹，可以定義函數依賴：

scores.score.@pno→scores.score.pname

基于樹元組的函數依賴的缺點在于無法表達與集合相關的依賴關系，原因在于根據文獻[3]中樹元組的定義，其對XML文檔樹的劃分過細。例如，對于圖1b文檔樹包含pname為Peter的score節點來說，根據定義需要劃分為三個樹元組，如圖3所示。

Figure 3 Tree tuples including the pname element valued Peter圖3 包含pname為Peter的樹元組

實際上，對于圖1b的XML文檔樹， scores.score 路徑下的@pname、$item與@point存在著函數依賴關系，但由于樹元組劃分過細，以至于XFD1無法描述這種包括集合的依賴關系，因此XFD1屬于基本的XML函數依賴定義。

XFD2為了增加XFD1的描述能力，文獻[4]首先對XFD1中樹元組的定義進行了擴展。在文獻[3]中，一棵XML文檔樹所包含樹元組的個數完全取決于XML模式路徑集合中擁有最多可達節點的路徑。例如，在圖1b中，scores.score.@point所對應的可達節點最多，共有6個，因此XML文檔樹也就包括6個樹元組。實際上對于這棵文檔樹來說，應該按路徑scores.score劃分樹元組，換句話說，這棵文檔樹有幾個score元素節點就劃分成幾個樹元組，而score下面即使在有像@point這樣的重復節點，也不應繼續進行劃分。按照這種方法，總共得到3個樹元組，這樣才比較符合實際XML數據的語義。根據這種思路，文獻[4]的作者將依據某一路徑劃分的樹元組歸為一類，成為元組類。

基于元組類的XML函數依賴XFD2定義如下：一個XFD2被定義為一個三元組{Cp,LHS,RHS}，通常寫成p1,…,pk→prw.r.t.Cp，其中Cp代表由路徑p所確定的元組類，LHS(Left Hand Set)是相對于p的路徑集合{p1,…,pk}，pr是相對于p的單一路徑。一棵XML文檔樹T滿足XFD2，如果對于任意兩個屬于Cp的樹元組t1和t2滿足以下條件：(1)存在i∈[1,…,k]，t1(pi)=null或者t2(pi)=null，或者(2)如果對于任意i∈[1,…,k]，t1(pi) =vt2(pi)，則有t1(pr)≠null，t2(pr)≠null并且t1(pr) =vt2(pr)。按照XFD2，我們可以為圖1b的XML文檔樹定義函數依賴：

@pno，$item→@pointw.r.t.scores.score

XFD2屬于擴展的XML函數依賴定義。

3.2 基于路徑的XML函數依賴定義

由于基于路徑的XML函數依賴定義種類較多，根據其能否表達集合等復雜數據分兩個小節介紹。

3.2.1 基本的路徑XML函數依賴

XFD3與基于樹元組的XML函數依賴定義不同，文獻[5]首先提出了基于路徑的XML函數依賴。XFD1和XFD2定義的樹元組既能表示元素節點又能表示屬性節點和文本節點。文獻[5]的作者認為元素節點在關系模型中沒有相應的對應物，并且元素節點之間也難于比較，因此在函數依賴中不應予以考慮。由此，提出基于原始路徑的XML函數依賴。所謂的原始路徑是指路徑以根元素標簽R為起始，以屬性節點標簽或text標簽為結束的路徑，也就是說原始路徑不能以元素節點標簽結束。

XFD3被定義為如下的表達形式：P→Q，其中P和Q是兩個原始路徑集。設T為滿足XML模式D的XML文檔，若對于D中任意兩個關于P和Q的路徑實例t1和t2，如果t1(Q)≠vt2(Q)，那么必然存在路徑集X∈P，使得t1(X)≠vt2(X)，稱P→Q。例如：可以用XFD3表示函數依賴：

scores.score.@pno→scores.score.pname.$text

注意scores.score.@pno和scores.score.pname.$text都是原始路徑。

XFD4XFD3定義的主要不足是只能表示一棵XML文檔樹在全局范圍內的函數依賴關系，若該文檔樹只有一部分滿足這個依賴關系，則用XFD3無法表示。為此，文獻[6]又提出局部XML函數依賴的概念。局部XML函數依賴被定義為如下形式：P→wQ，其中w是P和Q這兩個原始路徑集的公共前綴。w的作用是指定這個函數依賴在該XML文檔樹中的作用范圍。相當于XFD3中的函數依賴關系P→Q只在w路徑的范圍下存在。

XFD5文獻[7]提出的XFD5統一了XFD3和XFD4這兩種函數依賴。

XFD5被定義為如下形式：Φ(S, P→Q)，其中S是以R開始的非原始路徑，P和Q代表相對于S的以屬性標簽或text標簽結束的路徑集。當S是根元素標簽R時，Φ是像XFD3那樣的全局函數依賴，否則是像XFD4那樣的局部函數依賴。

XFD3～XFD5存在的共同問題是他們用來表達函數依賴關系的路徑都是以屬性標簽或text標簽結束的，因此這三種定義都不能表達元素節點之間的函數依賴關系。

XFD6為了彌補XFD3的不足，文獻[8,9]提出了路徑閉包的概念，并在此基礎上定義了XML強函數依賴。這里的閉包是指，對于路徑集P來說，如果有路徑p∈P，則p的所有前綴路徑也都屬于P。

XFD6被定義為如下形式：p1,…, pk→q，其中p1,…, pk和q都是閉包路徑集P中的路徑。這里可以認為P在一定程度上起到了XML模式的作用。之所以稱之為強函數依賴，是因為該定義的驗證條件具有強滿足性，它的滿足條件要強于上面介紹的XML函數依賴。換句話說，當p1,…, pk和q的可達節點有空節點存在時，這棵XML文檔樹就不滿足XFD6，但是對于XFD1來說卻是滿足的。

XFD6另外一個不同點在于其XML文檔樹只要求滿足閉包路徑集P而不是XML模式，XML模式是比閉包路徑集更靈活的約束條件，因此有函數依賴在其他XFD定義中是平凡函數依賴，而在XFD6中屬于非平凡依賴。例如，有如下的XML模式：r:= a*，a:= b,c，b:=$text，c:=$text,則對于要求滿足XML模式的XML函數依賴，對于XFD1來說，r.a→r.a.b是平凡函數依賴。因為根據這個XML模式，任何一個標記為a的節點必有一個標記為b的孩子節點。但是，與這個XML模式相對應的閉包路徑集為{r, r.a, r.a.b, r.a.c}，根據這個閉包路徑集，無法知道a節點下面是否一定有b節點，因為b和c之間的關系是未知的。因此，對于XFD6來說，r.a→r.a.b就不是平凡函數依賴。

文獻[10]證明，除去對空節點和平凡函數依賴這兩個問題處理不同之外，XFD6和XFD1有相同的函數依賴描述能力。

XFD7文獻[11]使用XPath表達式來定義XML函數依賴。與普通的路徑式相比，XPath表達式有更豐富的導航能力，它可以包括后裔軸、謂詞[]和通配符*。

XFD7定義如下：Q，[e1,…,ek→ek+1]。Q代表一個XPath表達式，e1,…, ek, ek+1代表元素標簽或者加上一個可選的屬性或文本標簽。對于兩個以可達節點Q為根的子樹，當它們在e1,…, ek上的值相等時，在ek+1也一定相等，則稱這棵XML文檔樹滿足XFD7。例如，圖1b中的XML文檔樹可以定義函數依賴：scores，[score.@pno→scorepname.$text]。

XFD7的優點在于使用XPath定位元素節點，比使用普通路徑表達式具有更靈活的定位能力。XFD7的缺點在于e1,…, ek, ek+1是單一的元素，只能定位可達節點Q的孩子元素節點(至多再加上一個可選的標簽或文本節點)，而不能是其他后裔元素節點，這點在很大程度上限制了XFD7的表達能力。

XFD8文獻[12]給出了另一種定義在DTD上的XML的函數依賴。這種函數依賴的形式如下：P(Q1, Q2,…,Qk→P1,P2,…,Pm)，其中P，Q1, Q2,…,Qk，P1,P2,…,Pm都是在某個DTD上的路徑表示，且P為根路徑表達式。例如：scores.score(@pno→pname.$text)。

3.2.2 擴展的路徑XML函數依賴

XFD9上節介紹的XFD3～XFD8都不能表達包含集合依賴關系的XML函數依賴，為解決這個問題，文獻[10]給出了一個支持表示集合依賴關系的函數依賴定義。

該函數依賴的表達形式如下：Q：p1(c1),…, pk(ck)→pk+1(ck+1)，其中Q可以包含_或_*，_可以代表E∪A∪{text}中的任意一個標簽，_*代表_的Kleene閉包。p1,…,pk在Q的基礎上又增加了K，類似于XPath中的反向軸，K表示反向導航的次數。c1,…,ck+1為N、L、S和I中的任意一個，分別表示元素(Node)、列表(List)、集合(Set)和存在(IN，p1,…,pk所可達的節點向量可以匹配pk+1所有可達節點中的一個)。例如：_*.score：@pno→@point(S)。

XFD10文獻[13]給出了另一個支持包含集合的XML函數依賴定義。給定一個XML模式D，在D上的XML函數依賴f具有如下形式：{Sh, [Sx1,…,Sxk]→[Sy1,…,Sym]}，其中Sh∈paths(D)叫做函數依賴f的頭部路徑，它定義了f在XML文檔樹上的作用范圍，Sh的最后一個標簽應為元素標簽，如果Sh不為空且不是R標簽，稱f為全局函數依賴，否則稱為局部函數依賴。[Sx1,…,Sxk]稱為f的左手路徑集。對于集合中的每一條路徑Sxi，要求滿足：(1)Sxi∈paths(D)；(2)Sh是Sxi的前綴路徑；(3)Sxi的可達節點可以是元素、屬性或文本節點。[Sy1,…,Sym]稱為f的右手路徑集，對于右手路徑集中的每一條約束，也要滿足上述的三條約束。與XFD9相比，XFD10不支持豐富的路徑表達式，但可以表示包含集合的XML函數依賴。

3.3 基于子樹的XML函數依賴定義

XFD11文獻[14]提出一種基于更復雜的數據結構“子樹”的定義。我們可以把XML模式轉化為一棵XML模式樹，例如，圖1a中的XML模式可以轉化為如圖4所示的結構。

Figure 4 XML schema tree圖4 XML模式樹

XML模式樹中以任一節點v為根的子樹稱為v-subtree。在XML文檔樹中與v相匹配的子樹稱為pre-image。XFD11被定義為如下形式：v：X→Y，其中v是模式樹中的某一節點，X和Y是以v為頂點的兩棵v-subtree。若對于v的任意兩個pre-images，如果二者在X上的投影相等，那么它們在Y上的投影也相等，則稱該XML文檔樹滿足該函數依賴。由于X和Y都是XML模式樹的子樹，因此也具有表示集合的能力，所以XFD11屬于擴展的XML函數依賴定義。

4 XML函數依賴蘊涵問題

4.1 基于樹元組的XML函數依賴蘊涵問題

文獻[3]首先對基于樹元組的XML函數依賴蘊涵問題作了深入的研究。對于關系數據庫來說，函數依賴的蘊涵問題就是判斷是否滿足某個數據模式的所有實例，如果滿足函數依賴集∑，那么也滿足函數依賴σ。函數依賴的蘊涵問題是關系數據庫中的基礎理論問題，一般的解決方法是試圖找到一個正確且完備的推理規則集，構建該問題的公理化系統，例如Armstrong公理系統[15]。對于XML函數依賴，文獻[3]證明了在一般的XML模式下，無法為XML函數依賴找到一組有效而完備的公理系統。如果對于一個公理系統的推導規則的前件來說最多包含k個函數依賴，則文獻[3]稱該公理系統是k元的。例如，Armstrong公理系統是一個2元公理系統，因為其中的傳遞律{若A→B,B→C，則A→C成立}是2元的，且沒有多于2元的推導規則。對于某種數據模型的函數依賴集，若可以找到一個正確且完備的k元公理系統，那么稱這種數據模型的函數依賴的推導規則是可以被公理化的。換句話說，一個函數依賴公理系統的k值應是不變的，不應隨模式或者其他因素而發生變化，例如無論關系數據庫的模式怎樣定義，Armstrong公理都是成立的。而對于XML數據來說，可以找到一個反例，證明k是隨XML模式變化而變化的。對于一個XML模式S來說，設:

E′={A1,…,Ak,Ak+1,B,r}；

R=r；

type(r)=(A1|…|Ak,|Ak+1),B*;

type(t)=ε,t∈E′-r。

定義在S上的XML函數依賴∑包括下面三個集合：

(1)r.Ai→r.B|i∈[1,…,k+1];

(2)r,r.Ai→r.B|i∈[1,…,k+1];

(3)S上的所有平凡函數依賴。

若函數依賴φ不屬于集合∑，那么φ必定是r→r.B,因為在S上已經不可能存在其他非平凡函數依賴了。我們假設在這個XML模式上存在一個k元公理系統，其中的推導規則最多需要k個函數依賴，那么至少存在i∈[1,…,k+1]，使得r.Ai→r.B和r,r.Ai→r.B這兩個函數依賴不屬于某個k元推導規則。例如，圖5的XML文檔樹，它顯然滿足模式S，并且滿足最多為k元的推導規則(這個推導規則不包括r.Ai→r.B和r,r.Ai→r.B)，但是顯然推導不出r→r.B。另一方面，若加上函數依賴r.Ai→r.B和r,r.Ai→r.B，則對于任何滿足S的XML文檔樹，必有r→r.B。至此我們可以得出結論，在模式S上無法得到k元的推導規則，其中k是一個固定值，因為若要推出r→r.B，則必定需要∑中的所有非平凡依賴，而∑中非平凡函數依賴的數量又是不固定的。因此，一般的XML模式下，無法為XML函數依賴找到一組有效而完備的公理系統。

Figure 5 Example for not be axiomatized of normal DTD圖5 關于函數依賴在一般DTD下不能公理化的示例

可見，在關系模型中解決函數依賴蘊涵問題常用的公理化方法在XML模型中不一定有效。為解決該問題，文獻[3]的作者另辟蹊徑，將XML函數依賴蘊涵問題轉化為判斷Horn子句的一致性問題，并證明對于簡單XML模式(不含或可消去“|”)，判斷函數依賴蘊涵問題的時間復雜度是O(‖D‖2),其中‖D‖為XML模式中包含的路徑數量；對于僅含有(a|ε)或(a|b)*的XML模式，算法復雜度是多項式時間。而對于一般的XML模式，這是一個coNP完全問題。

4.2 基于路徑的XML函數依賴蘊涵問題

文獻[6]首先針對局部函數依賴XFD4提出了一個公理系統，該系統共包含三條推導規則，如下所示：

(1)自反律：如果P′?P，則有P→wP′;

(2)增廣律：如果P→wQ，則有(P∪H)→w(Q∪H);

(3)傳遞律：如果P→wQ并且Q→wQ′，則有P→wQ′。

可以看出這些推導規則是對關系模型中Armstrong公理的自然擴展。但是，文獻[6]只證明了該公理系統是可靠的，而沒有證明其是否完備。

文獻[16]針對強XML函數依賴XFD6提出了一個可靠的公理系統，并證明對于一元函數依賴來說，這組公理也是完備的。所謂n元函數依賴是針對LHS集合中路徑的數量來說的，一元函數依賴就是指LHS集合中只有一條路徑的函數依賴。本文基于這組推理規則，提供了一個線性時間的蘊涵判定算法，并證明了其正確性。

此外，文獻[12]也給出了XFD8的公理系統，并分別證明了其正確性和完備性。

4.3 基于路徑的XML函數依賴蘊涵問題

文獻[14]首先給出了一個基于子樹的XML函數依賴XFD11的公理系統，該系統同樣是擴展了關系模型的Armstrong公理。并且本文證明了在某些情況下，對于XFD11，該公理系統也不能保證正確性，所以在一般情況下，該公理系統也是不完備的。文獻[17]對該問題作了補充，證明了該公理系統對某些XFD11來說是正確且完備的。

文獻[18]也借助樹模式的概念定義XML函數依賴，并分別討論了DTD不存在和存在時的邏輯蘊涵問題。由于樹模式的概念可以很好地將嵌套的數據結構解嵌套為關系的表結構，從而成為兩種數據模型間轉換的橋梁。在此基礎上，作者使用關系數據庫中的Chase技術解決了邏輯蘊涵問題。

5 挖掘XML函數依賴

在關系數據庫中，關于如何從關系實例中挖掘或發現未知的函數依賴的問題因其涉及數據庫模式規范化、反向工程和查詢優化等多方面內容，因此也是一項重要的研究課題。目前，在關系數據庫中比較有效的函數依賴發現算法包括Dep-Miner[19]、TANE[20]和FUN[21]。由于XML數據模型半結構化的特點，不能直接應用上述算法。

文獻[4]首先根據樹元組定義的XFD2給出了XML函數依賴發現算法DiscoverXFD。該算法的核心是將XML文檔轉化為嵌套關系數據庫。例如，對于圖1b的XML文檔可以轉化為圖6的嵌套關系。然后，對于每張關系表內的函數依賴，就可以用關系數據的相應算法進行挖掘。而對于不同表之間可能存在的依賴關系，DiscoverXFD算法也進行了相應的處理。

Figure 6 Example for discoverXFD圖6 DiscoverXFD示例

另外，文獻[22]給出了基于子樹的XML函數依賴發現算法，與文獻[4]將XML文檔樹轉化為嵌套關系的方法不同，文獻[22]采用了直接遍歷文檔樹的方法。文獻[23]則改造了在OLDP中廣泛應用的PipeSort算法，并將其應用于XML函數依賴的發現，其主要優點在于與文獻[4]的DiscoverXFD算法相比，計算速度大大提高。

6 未來研究方向

6.1 基于類型的XML函數依賴定義

函數依賴體現了數據項之間一對一或者多對一的關系，而這種關系無論是對結構化的關系模型還是半結構化的XML數據模型，都是基于值對應的關系。在關系模型中，根據第一范式，元組的每個屬性分量都必須具有原子性，也就是說再不可以被分割成更小的部分。而XML模型不滿足第一范式的要求，XML樹中每一元素節點都可以包含其他孩子節點。進一步地，我們可以說每一元素節點都是具有復雜類型的。由于出現這種情況，因此XML模型的函數依賴不僅體現在節點值之間，還可能在節點類型和值之間也會存在這種一對一或多對一的函數關系。怎樣擴展現有定義的描述能力使其可以表達這種類型的依賴，以及如何解決這種依賴的邏輯蘊涵和規范化問題，將是XML語義約束研究的一個新方向。

6.2 XML多值依賴和包含依賴

除了函數依賴以外，其他類型的依賴關系，例如多值依賴和包含依賴等，也對XML模型的規范化起到了重要的作用。在這方面，現有的研究還不是很充分。文獻[24]給出了一個形如p→→q|r的定義，其中p、q和r都是路徑表達式。而對于包含依賴，文獻[25]給出了形如P[p1,…,pn]?Q[q1,…,qn]的定義。這些定義都是對關系模型中相關定義的自然擴展。如何更加靈活地表達XML數據的依賴關系以及這些依賴關系的性質仍然值得研究。

6.3 XML模式規范化

研究數據依賴關系的目的在于規范數據模式的設計，從而在實際應用中盡可能減少數據冗余。模式規范化在關系模型中已有了成熟的理論體系，并在實踐中得到廣泛的應用。隨著XML的發展，XML模式的規范化問題也得到了相關研究者的廣泛關注。已有的工作基本遵循了關系數據庫中范式的設計思想，但普遍缺少對規范化算法及其性質的深入分析，在這方面還有許多內容需要加以研究。

7 結束語

由于XML靈活的數據結構，使得人們在研究其語義約束問題上面臨著更大的挑戰。在眾多的語義約束中，函數依賴因其廣泛性，對于研究者來說尤為重要。本文分析了XML函數依賴相關的問題，特別是如何定義函數依賴以及邏輯蘊涵和依賴挖掘問題，最后介紹了一些新的研究方向。

[1] Bray T, Jean P. Extensible markup language (XML)[J]. World Wide Web Journal,1997,2(4):27-66.

[2] Murata M, Lee D, Mani M, et al. Taxonomy of XML schema languages using formal language theory[J]. ACM Transactions on Internet Technology,2005,5(4):660-704.

[3] Arenas M, Libkin L. A normal form for XML documents[J]. ACM Transactions on Database Systems, 2004 ,29(1):195-232.

[4] Yu Cong, Jagadish H V. Efficient discovery of XML data redundancies[C]∥Proc of the 32nd International Conference on Very Large Data Bases,2006:103-114.

[5] Liu Ji-xue, Vincent M, Liu Cheng-fei. Functional dependencies, from relational to XML[C]∥Proc of the 5th International Andrei Ershov Memorial Conference,2003:531-538.

[6] Liu Ji-xue, Vincent M, Liu Cheng-fei. Local XML functional dependencies[C]∥Proc of the Interntational Workshop on Web Information and Data Management,2003:23-28.

[7] Shahriar M S, Liu Ji-xue. On defining functional dependency for XML[C]∥Proc of 2009 IEEE International Conference on Semantic Computing,2009:595-600.

[8] Vincent M, Liu Ji-xue, Liu Cheng-fei. Strong functional dependencies and their application to normal forms in XML[J]. ACM Transactions on Database Systems,2004,29(3):445-462.

[9] Vincent M,Liu Ji-xue.Functional dependencies for XML[C]∥Proc of the 5th Asian-Pacific Web Conference,2003:22-34.

[10] Wang Jun-hu.A comparative study of functional dependencies for XML[C]∥Proc of the 7th Asia-Pacific Web Conference on Web Technologies Research and Development,2005:308-319.

[11] Lee M, Ling T, Low W. Designing functional dependencies for XML[C]∥Proc of the 8th International Conference on Extending Database Technology,2002:145-158.

[12] Tan Zi-jing, Pang Yin-ming, Shi Be-le. Reasoning about functional dependency for XML[J].Journal of Software,2003,14(9):1564-1570. (in Chinese)

[13] Lv Teng, Yan Ping, Wan Zhen-xing. Functional dependencies for XML[J].Journal of Chinese Computer Systems,2005,26(5):864-868. (in Chinese)

[14] Hartmann S,Link S.More functional dependencies for XML[C]∥Proc of ADBIS’03,2003:355-369.

[15] Armstrong W W. Dependency structures of data base relationships[C]∥Proc of the International Federation for Information Processing Congress, 1974:580-583.

[16] Vincent M,Liu Ji-xue,Liu Cheng-fei.The implication problem for unary functional dependencies in XML [EB/OL].[2013-06-16].http:∥citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.3716.

[17] Hartmann S, Link S, Trinh T. Efficient reasoning about XFDs with pre-image semantics[C]∥Proc of the 12th International Conference on Database Systems for Adocucced Applications,2007:1070-1074.

[18] Kot L,White W.Characterization of the interaction of XML functional dependencies with DTDs[C]∥Proc of the 11th International Conference on Database Theory,2007:119-133.

[19] Lopes S, Petit J M, Lakhal L. Efficient discovery of functional dependencies and Armstrong relations[C]∥Proc of the 7th International Conference on Extending Database Technology,2000:350-364.

[20] Huhtala Y, Juha K, Porkka P,et al. TANE:An efficient algorithm for discovering functional and approximate dependencies[J]. Computer Journal,1999,42(2):100-111.

[21] No?l N, Rosine C. Functional and embedded dependency inference:A data mining point of view[J]. Information Sys-

tems, 2001, 26(7):477-506.

[22] Trinh T. Using transversals for discovering XML functional dependencies[C]∥ Proc of the 5th International Symposium on Foundations of Information and Knowledge Systems,2008:199-218.

[23] Shi Hang,Amagasa T,Kitagawa H.Fast detection of functional dependencies in XML data[C]∥Proc of XSym’10,2010:113-127.

[24] Vincent M,Liu Ji-xue.Multivalued dependencies and a 4NF for XML[C]∥Proc of LAISE’03,2003:14-29.

[25] Karlinger M, Vincent M, Schrefl M. Inclusion dependencies in XML:Extending relational semantics[C]∥Proc of DEXA’09,2009:23-37.

附中文參考文獻：

[12] 談子敬，龐引明，施伯樂. XML上的函數依賴推理[J].軟件學報,2003,14(9):1564-1570.

[13] 呂騰，閆萍，王真星. XML的函數依賴[J].小型微型計算機系統,2005,26(5):864-868.

LIUJia,born in 1984,PhD candidate,his research interests include software theory，and data management in XML.

廖湖聲(1954-),男,北京人，教授，博士生導師，研究方向為數據庫技術和理論, 編譯技術與程序理論。E-mail:liaohs@bjut.edu.cn

LIAOHu-sheng,born in 1954,professor,PhD supervisor,his research interests include database technology and theory, compiler technology, and software theory.

AsurveyonXMLfunctionaldependencies

LIU Jia，LIAO Hu-sheng

(Department of Computer Science,Beijing University of Technology,Beijing 100124,China)

The concept of functional dependencies plays an important role in database theory since it is the basis of normal forms that are used to produce well-design schema. Due to the complexity of the semi-structured XML model, it is a challenge to define the functional dependencies and study the nature of those dependencies such as their capability of representation, logical implication and corresponding normal forms. The previous works in this area are surveyed and the approaches they deployed are described. Particularly, the paper focus on the comparison of functional dependencies definitions, the problem of logical implication and the discovery of dependencies. At last, some novel problems referring to dependencies such as relationship between value and type in shortly are discussed.

XML;functional dependencies;logical implication；dependencies discovery

2013-07-08;

：2013-10-25

北京市自然科學基金資助項目(4082003)

1007-130X(2014)02-0331-09

TP311.132

：A

10.3969/j.issn.1007-130X.2014.02.023

劉嘉(1984-),男,北京人，博士生，研究方向為軟件理論和XML數據管理。E-mail:jeromeliu2006@sina.com

通信地址：100124 北京市朝陽區平樂園100號北京工業大學計算機學院Address:Department of Computer Science,Beijing University of Technology,100 Pingle Yuan,Chaoyang District,Beijing 100124,P.R.China