劉 嘉，廖湖聲

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

XML函數(shù)依賴研究綜述*

劉 嘉，廖湖聲

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

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

XML；函數(shù)依賴；邏輯蘊涵；依賴發(fā)現(xiàn)

1 引言

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

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

1.1 XML函數(shù)依賴定義的分類

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

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

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

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

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

1.2 XML函數(shù)依賴的蘊涵關系

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

1.3 XML函數(shù)依賴的發(fā)現(xiàn)

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

2 基本定義

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

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

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

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

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

(1)label(root)=R。

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

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

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

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〉的節(jié)點序列，且滿足條件：對于vi∈V，1

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

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

3 XML函數(shù)依賴的定義

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

3.1 基于樹元組的XML函數(shù)依賴定義

XFD1文獻[3]將關系模型中元組的概念擴展到XML數(shù)據(jù)模型中。作者首先將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文檔樹中所匹配的一組可達節(jié)點就可以組合一個樹元組。例如，圖2即為圖1b中XML文檔樹中的一個樹元組。

Figure 2 Tree tuple圖2 樹元組

基于樹元組的函數(shù)依賴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的文檔樹，可以定義函數(shù)依賴：

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

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

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

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

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

基于元組類的XML函數(shù)依賴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文檔樹定義函數(shù)依賴：

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

XFD2屬于擴展的XML函數(shù)依賴定義。

3.2 基于路徑的XML函數(shù)依賴定義

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

3.2.1 基本的路徑XML函數(shù)依賴

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

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表示函數(shù)依賴：

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

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

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

XFD5文獻[7]提出的XFD5統(tǒng)一了XFD3和XFD4這兩種函數(shù)依賴。

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

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

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

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

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

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

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

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

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

XFD8文獻[12]給出了另一種定義在DTD上的XML的函數(shù)依賴。這種函數(shù)依賴的形式如下：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函數(shù)依賴

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

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

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

3.3 基于子樹的XML函數(shù)依賴定義

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

Figure 4 XML schema tree圖4 XML模式樹

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

4 XML函數(shù)依賴蘊涵問題

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

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

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

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

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

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

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

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

4.2 基于路徑的XML函數(shù)依賴蘊涵問題

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

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

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

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

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

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

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

4.3 基于路徑的XML函數(shù)依賴蘊涵問題

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

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

5 挖掘XML函數(shù)依賴

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

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

Figure 6 Example for discoverXFD圖6 DiscoverXFD示例

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

6 未來研究方向

6.1 基于類型的XML函數(shù)依賴定義

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

6.2 XML多值依賴和包含依賴

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

6.3 XML模式規(guī)范化

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

7 結束語

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

[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上的函數(shù)依賴推理[J].軟件學報,2003,14(9):1564-1570.

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

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

廖湖聲(1954-),男,北京人，教授，博士生導師，研究方向為數(shù)據(jù)庫技術和理論, 編譯技術與程序理論。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數(shù)據(jù)管理。E-mail:jeromeliu2006@sina.com

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