XML模式推斷研究綜述

鄭黎曉，王　成

(1．華僑大學(xué)計算機科學(xué)與技術(shù)學(xué)院，福建廈門361021; 2．中國科學(xué)院軟件研究所計算機科學(xué)國家重點實驗室，北京100190)

?

XML模式推斷研究綜述

鄭黎曉1，2，王成1

(1．華僑大學(xué)計算機科學(xué)與技術(shù)學(xué)院，福建廈門361021; 2．中國科學(xué)院軟件研究所計算機科學(xué)國家重點實驗室，北京100190)

摘要:本文對XML(Extensible Markup Language)數(shù)據(jù)的模式推斷問題研究現(xiàn)狀與進展進行了闡述．首先，從正規(guī)樹文法的角度介紹了不同模式語言的理論模型．進而從模式推斷方法、目標模式語言、支持的表達能力、內(nèi)容模型對應(yīng)的正則表達式類型等多個方面對當前研究工作進行了細致的分類歸納和對比．此外，還介紹了模式語言中支持的基本語義完整性約束推斷的研究進展．最后指出了當前研究中的不足，并對未來需要深入研究的方向進行了展望．重在對XML模式推斷的主流方法和前沿進展進行概括、比較和分析，以期對后續(xù)研究有所助益．

關(guān)鍵詞:可擴展標記語言;模式推斷;正規(guī)樹文法;正則表達式

1　引言

由萬維網(wǎng)聯(lián)盟(World Wide Web Consortium，W3C) 在1997年提出的可擴展標記語言(Extensible Markup Language，XML)可以簡單、靈活地描述各種帶結(jié)構(gòu)的數(shù)據(jù)，已經(jīng)成為網(wǎng)絡(luò)環(huán)境中數(shù)據(jù)交換與集成的事實標準，得到越來越廣泛和深入的應(yīng)用．因此，如何有效處理和使用XML數(shù)據(jù)成為近年來一個持續(xù)的研究熱點．在XML數(shù)據(jù)處理中，模式是一個重要的方面．模式定義了XML數(shù)據(jù)的結(jié)構(gòu)、類型和語法規(guī)范，是保證XML數(shù)據(jù)格式正確和內(nèi)容有效的手段．模式在XML數(shù)據(jù)處理和應(yīng)用程序中發(fā)揮著重要的作用，例如:用于XML文檔的有效性驗證和類型檢查以保證應(yīng)用程序的安全性和正確性［1］;利用模式信息進行查詢優(yōu)化從而提高應(yīng)用程序的實現(xiàn)效率［2］;通過模式匹配和模式映射實現(xiàn)數(shù)據(jù)的自動集成和交換［3］等．此外，一些軟件開發(fā)工具如SUN JAXB等也都依賴模式實現(xiàn)XML數(shù)據(jù)綁定功能．

然而在現(xiàn)實中經(jīng)常出現(xiàn)模式缺失或未有效定義的情況．2006年的統(tǒng)計結(jié)果［4，5］顯示互聯(lián)網(wǎng)上可用的XML文檔中近一半沒有模式定義，而存在的模式中大約有2/3不滿足W3C規(guī)范．一項最新(2013)年的調(diào)查報告［6］指出這種情況變得越來越普遍:統(tǒng)計的數(shù)據(jù)中只有1/4的文檔有模式定義，而這些模式中僅有1/3是有效的．因此，如何從已有的XML文檔中自動推斷出符合規(guī)范的高質(zhì)量模式成為一個亟待解決的問題．實際上，早在2005年，W3C標準制定者之一Florescu［7］就強調(diào)“在半結(jié)構(gòu)化數(shù)據(jù)管理中，我們需要從已有的XML文檔中自動抽取高質(zhì)量的模式，并進行增量式維護”．此外，模式推斷在模式演化方面也有重要應(yīng)用．有些文檔即使存在有效的模式，但定義可能過于泛化，即描述的約束信息相對于存在的XML文檔而言過于寬泛．實際上，這種情況在工業(yè)界普遍存在［8］．此時，也需要利用模式推斷算法獲得更精確的描述，以更好地服務(wù)于應(yīng)用．

XML模式推斷問題早在多年前就引起關(guān)注．近年來，隨著XML的廣泛應(yīng)用和模式缺失的普遍性，有越來越多的學(xué)者研究該問題．本文在充分調(diào)研和深入研究的基礎(chǔ)上對XML模式推斷問題的研究進展進行了綜述: (1)介紹常見XML模式語言及其理論模型，并基于此給出模式推斷的形式化定義; (2)以語言的歸納學(xué)習(xí)經(jīng)典理論模型為參照，將現(xiàn)有的推斷方法歸結(jié)為兩大類進行闡述，從目標模式語言、支持的表達能力、內(nèi)容模型對應(yīng)的正則表達式類型等多個維度對不同的推斷方法進行分析和對比．此外，還介紹了模式語言中語義完整性約束推斷的研究現(xiàn)狀．

2　XML模式語言及其理論模型

2.1模式語言簡介

現(xiàn)有的XML模式語言有很多種，其中較為常用的包括W3C推薦標準文檔類型定義(Document Type Definition，DTD)［9］和XML模式定義(XML Schema Definition，XSD)［10］，以及國際標準化組織(International Organization for Standardization，ISO)推薦標準RELAX NG［11］．下面分別對這幾種語言進行介紹，2.2節(jié)將形式化地給出對應(yīng)的理論模型．

DTD是目前使用較為普遍、也是W3C最早推薦的XML模式語言．DTD本質(zhì)上是一種擴展的上下文無關(guān)文法．在這種文法中，產(chǎn)生式的右部不是簡單的字符串而是正則表達式，允許用戶使用正則操作算子(|、* 等)定義元素的出現(xiàn)順序、次數(shù)等．圖1(a)給出一個描述書本信息的DTD例子．由于其簡單易用，使得DTD得到了普遍的應(yīng)用．但在某些場合，DTD有明顯的局限性，例如基本類型較少，引用機制有限，缺少模塊化，描述無序數(shù)據(jù)的繁瑣等．

XSD為彌補DTD的缺陷，W3C于2001年推出了表達能力更強的模式定義語言XSD．與DTD相比，XSD具有以下幾大特點: (1)引入了類型的概念，允許使用相同的元素名定義不同的類型，例如，使用相同的“section”元素名來描述Book和Paper里面不同的章節(jié)類型; (2)允許使用“all”指示器指定子元素可以以任意順序出現(xiàn)，即交互，和通過“minOccur”、“maxOccur”屬性對元素的出現(xiàn)次數(shù)進行精確限定，即計數(shù); (3)提供了類型派生機制，允許在已經(jīng)定義的數(shù)據(jù)類型基礎(chǔ)上，定義新的數(shù)據(jù)類型，可以實現(xiàn)類型復(fù)用和模式定義的緊湊性; (4)提供更豐富的內(nèi)置數(shù)據(jù)類型，如int、date、time等．此外，XML Schema還支持命名空間的機制，實現(xiàn)了模式復(fù)用和避免命名沖突．近年來，XSD由于其更強的表達能力和豐富的定義機制正逐漸取代DTD而被廣泛應(yīng)用．其缺點是定義較為復(fù)雜，可讀性差．例如，圖1(c)中的XSD和圖1(a)中DTD定義相同的信息，但是篇幅明顯要長很多．

RELAX NG最初由結(jié)構(gòu)化信息標準促進組織(Organization for the Advancement of Structured Information Standards，OASIS)提出，現(xiàn)已成為ISO標準．其初衷是為了結(jié)合DTD的簡潔性和XSD的強表達能力，同時避免它們各自的缺陷．RELAX NG具有兩種定義方式:一種基于XML語法，提供了許多與XSD等同的功能，如子元素的交互(即無序)出現(xiàn)、豐富的內(nèi)置數(shù)據(jù)類型等;一種是緊湊的文本語法，使用元素嵌套的方式進行定義，實現(xiàn)與DTD類似的簡潔性．圖1(b)給出使用緊湊文法定義的一個例子．由于RELAX NG對元素及其內(nèi)容模型的定義沒有規(guī)定嚴格的限制形式，因此其表達能力要強于DTD和XSD(具體見2.3節(jié))．

其它研究人員還提出了其他一些XML模式語言，例如Schematron［12］、XDuce［13］、DSD［14］等．其中，Schematron是一種基于規(guī)則的模式語言．如圖1(d)所示，Schematron使用斷言的方式給出一系列規(guī)則描述XML文檔中某個或某些元素或?qū)傩詰?yīng)該滿足的約束．XML數(shù)據(jù)的傳統(tǒng)模型為有序無秩(ordered unranked)樹．最近，一些學(xué)者研究無序(unordered)樹，提出描述無序XML樹結(jié)構(gòu)的模式語言DMS［15］．DMS采用與DTD類似的定義方式，特點是去除了正則表達式中描述出現(xiàn)順序的連接符“，”，替換為無序連接符“‖”．這些模式語言目前主要用于學(xué)術(shù)研究，實際應(yīng)用還不太廣泛．

2.2理論模型

采用文法、自動機以及邏輯等方式［16，17］都可以對XML的模式語言進行形式化描述．由于XML文檔既可以看成是字，也可以看作是樹，因此描述其模式語言的文法或自動機也有兩大類．從字的角度上，有平衡文法［18］以及可見下推語言(Visibly Pushdown Languages，簡稱VPL)［19］等．其中平衡文法是由括號文法［20］擴展而來，可以允許有多種形式的括號，且文法中產(chǎn)生式的右部允許使用正則表達式; VPL是能被一個帶有棧的下推自動機所接受的語言，在接受過程中根據(jù)輸入的字母決定棧中對應(yīng)的操作．XML文檔中的開始和結(jié)束標記對應(yīng)于平衡文法中多種形式的括號，因此可以使用平衡文法描述XML的模式語言;標記也可以對應(yīng)VPL中的配對符號，因此也可以利用VPL描述XML文檔或進行XML相關(guān)的處理．從樹的角度上，最常見的描述XML模式語言的文法是正規(guī)樹文法，其定義的語言是正規(guī)樹語言，是能被樹自動機所接受的語言［21］．本節(jié)從正規(guī)樹文法的角度進行介紹，詳細內(nèi)容參見文獻［22］．

2．2．1正規(guī)樹文法

一個正規(guī)樹文法(Regular Tree Grammars，簡稱RTG)是個四元組G = (VN，VT，S，P)，其中VN、VT分別是非終極符和終極符的有限集合; S∈VN是開始符號; P是形如N →lr的產(chǎn)生式的有限集合，其中N∈VN，稱為產(chǎn)生式的左部，lr是產(chǎn)生式的右部，l∈VT稱為標號，r是VN上的正則表達式，稱為產(chǎn)生式的內(nèi)容模型(Content Model)．

給定樹t和正規(guī)樹文法G，稱t是G的一個合法實例當且僅當存在一個映射I使得對于t中的任意結(jié)點e，I(e)是G的一個非終極符并且滿足下列條件: (1)若e是根結(jié)點，則I(e)是開始符號; (2)對于結(jié)點e和其子結(jié)點e1，…，em，存在G中的一條產(chǎn)生式X→a r使得I(e)是非終極符X，e的標號是終極符a，I(e1)…I(em)是正則表達式r的句子．由G的所有合法樹構(gòu)成的集合稱為G所定義的正規(guī)樹語言．

對于正規(guī)樹文法G中的兩個非終極符N1和N2，N1≠N2，若存在兩個產(chǎn)生式，其左部分別為N1和N2，右部具有相同的終極符，則稱非終極符N1和N2存在競爭．如果G中不含有存在競爭的非終極符，則稱G是local正規(guī)樹文法;如果G中每條產(chǎn)生式的內(nèi)容模型中的非終極符互不存在競爭，則稱G是single-type正規(guī)樹文法．由以上定義可知，在local正規(guī)樹文法中，非終極符與終極符是一一對應(yīng)的．換言之，由非終極符可以唯一確定相應(yīng)的產(chǎn)生式和內(nèi)容模型．local的和single-type的正規(guī)樹文法都是正規(guī)樹文法的子類．local的正規(guī)樹文法也是single-type的，反之則不然．因此，從表達能力上講，三者之間的關(guān)系為:

2．2．2正則表達式及其子類

正規(guī)樹文法使用正則表達式定義產(chǎn)生式的內(nèi)容模型，因此所描述的樹均是無秩(unranked)的，即樹中每個結(jié)點的子結(jié)點數(shù)目不是固定的．這與XML數(shù)據(jù)的有序無秩樹模型相吻合．本節(jié)介紹與正則表達式及其子類相關(guān)的概念．

令Σ表示符號的集合．Σ上的正則表達式(Regular Expression，簡稱RE)可以遞歸的定義如下:空集?、空字符ε、每個符號a∈Σ是正則表達式;如果E1和E2是正則表達式，則將他們進行連接運算E1，E2(為了方便表示，下文中省去了連接運算符)、選擇運算E1| E2、和星號運算E1*的結(jié)果仍然是正則表達式．L(E)表示正則表達式E所定義的語言．

對于一個正則表達式E，使用下標來依次標記其中出現(xiàn)的字符，使得每個標記后的字符在表達式中僅出現(xiàn)一次，這樣的表達式稱為E的標記表達式，記作E'．與標號操作相對應(yīng)的是去標號．假設(shè)E是一個帶標號的正則表達式，去掉E中所有的標號后所得到的表達式記為E#．例如，令E = a* a，則E' = a1* a2，(E')#= a * a．利用這些記號，我們可以定義正則表達式的一個特殊子類: one-unambiguous表達式［23］．

—個正則表達式E是one-unambiguous的，當且僅當對于任意兩個句子uxv，uyw∈L(E')，| x| = | y| = 1，若x≠y則x#≠y#．One-unambiguous正則表達式通常也被稱為確定性(deterministic)正則表達式．直觀地講，對于輸入句子中的每一個符號，不需要向前看就能唯一地匹配確定性正則表達式中的一個位置．例如，a* a不是確定性表達式，因為對于句子a而言，在不向前看的前提下不能確定符號‘a(chǎn)’與表達式中的第一個a還是第二個a匹配．而aa*是確定性表達式，對于L(aa* )中每一個句子，它的第一個字符都匹配aa*中的第一個a，其余的字符都匹配第二個a．

在實際應(yīng)用中使用更為廣泛的一類表達式是帶數(shù)字與交互的正則表達式，它們是對標準表達式的擴展，增加了帶數(shù)字出現(xiàn)和帶交互出現(xiàn)的操作符．在XSD中使用的就是這類表達式，其定義如下:標準表達式是帶計數(shù)和交互的表達式;令E1和E2是帶計數(shù)與交互的表達式，則和E1＆E2是帶數(shù)字與交互的表達式(其中，∞表示無窮)．

計數(shù)操作精確限定了字符允許出現(xiàn)的次數(shù)，交互操作則允許字符的交互出現(xiàn)．例如L(a［1，3］) = { a，aa，aaa}，L(a＆b) = { ab，ba}．類似地，可以定義帶計數(shù)與交互的確定性表達式．

2.3與模式語言的對應(yīng)關(guān)系

本節(jié)討論幾種常見XML模式語言對應(yīng)的具體理論模型．

(1)表達能力方面

在DTD中，元素的類型聲明對應(yīng)于正規(guī)樹文法中的一條產(chǎn)生式，元素的內(nèi)容模型對應(yīng)產(chǎn)生式的內(nèi)容模型，元素名稱既充當終極符又充當非終極符的角色．這剛好與local正規(guī)樹文法的定義形式吻合．因此，從表達能力上講，DTD屬于local正規(guī)樹文法．XSD中的主要特性如復(fù)雜類型定義、抽象類型定義、類型派生等均可以轉(zhuǎn)換為正規(guī)樹文法的形式描述．特別地，W3C規(guī)范要求對于每一個元素，根據(jù)其上下文即可確定其類型．換言之，處于同一個內(nèi)容模型中的相同元素名不能夠存在競爭．因此，XSD的表達能力屬于single-type正規(guī)樹文法．RELAX NG對元素的定義形式?jīng)]有限制，表達能力最強．本質(zhì)上，RELAX NG能夠表示任何正規(guī)樹語言．

(2)內(nèi)容模型方面

W3C規(guī)范要求DTD和XSD的元素內(nèi)容模型需要滿足惟一粒子屬性(Unique Particle Attribution，UPA)約束，即表達式應(yīng)該是確定性的．其中，DTD使用標準的確定性表達式，XSD中支持計數(shù)和交互定義機制，使用的是帶計數(shù)和交互的確定性表達式．RELAX NG中沒有確定性的要求，并且只支持交互定義機制，因此內(nèi)容模型是帶交互的表達式．

表1給出上述模式語言對應(yīng)的具體理論模型．其中RE和dRE分別表示標準和確定性正則表達式，#和＆分別表示計數(shù)和交互．

表1　XML模式語言的理論模型

3　XML模式推斷問題定義

XML模式推斷屬于語言的歸納學(xué)習(xí)問題，研究如何從語言的有限信息出發(fā)，通過歸納推斷得到語言的定義．Gold 于1969年給出語言學(xué)習(xí)的經(jīng)典理論模型，即語言的極限識認模型［24］．按照該模型，XML模式推斷問題形式化地定義如下:稱一組XML文檔為一個樣本，模式推斷是一個從樣本集到目標模式語言的映射M，使得: (1)對于每一個樣本D，DL(M，(D) ) ; (2)對于每一個目標模式語言中的模式定義S，存在一個樣本Dc，使得對于任意滿足DcDL (S)的樣本D都有M(D) =S．

直觀上來講，條件(1)強調(diào)推斷是正確的(sound)，條件(2)則強調(diào)推斷是完全的(complete)．顯然，推斷問題與目標模式語言有關(guān)．目前的研究主要集中于DTD 和XSD，而RELAX NG的研究較少．DTD屬于local正規(guī)樹文法，內(nèi)容模型與元素是一一對應(yīng)的，因此本質(zhì)上歸約為確定性正則表達式的學(xué)習(xí); XSD引入了類型的概念，因此推斷包括兩個方面:垂直方向——支持single-type正規(guī)樹文法表達能力的類型識別;水平方向——支持計數(shù)與交互定義機制的內(nèi)容模型推斷．其中后者又歸約為帶交互與計數(shù)的確定性表達式學(xué)習(xí)．

實際上，Gold證明出如果只有正例，任何包含所有有限語言和任一無限語言的語言類均是無法識認的．這也意味著正規(guī)樹文法及其local、single-type子類都是無法學(xué)習(xí)的，甚至連內(nèi)容模型對應(yīng)的正則表達式及其確定性子類也無法學(xué)習(xí)［25］．因此，現(xiàn)有的研究主要從兩個方面入手: (1)只關(guān)注推斷的正確性，對目標語言類和推斷的完全性沒有進行討論，我們稱之為啟發(fā)式的推斷方法; (2)是通過對目標語言加以限制，從而尋找到正確性與完全性兼顧的學(xué)習(xí)算法，我們稱之為基于語言極限識認模型的推斷方法．

表2給出了當前主流XML模式推斷研究的具體分類結(jié)果，從推斷方法、目標模式語言、支持的表達能力、內(nèi)容模型對應(yīng)的正則表達式類型等多個維度進行分析和對比．

4　啟發(fā)式的推斷方法

不管目標模式語言是DTD還是XSD，模式推斷的本質(zhì)是從輸入樣本集中推導(dǎo)正規(guī)樹文法．因此，一般而言，啟發(fā)式的推斷方法主要分為如下幾個步驟: (1)推導(dǎo)初始文法; (2)推導(dǎo)正則表達式; (3)轉(zhuǎn)換為目標模式語言．其中，第(1)步所采取的策略決定了推斷方法所支持的表達能力:是local正規(guī)樹文法還是single-type正規(guī)樹文法等?第(2)步則影響推斷結(jié)果中內(nèi)容模型對應(yīng)的正則表達式類型:是標準表達式還是帶計數(shù)或交互的擴展表達式?第(3)步則涉及到具體的目標模式語言．

4.1推導(dǎo)初始文法

首先，對于XML文檔中的每一個元素e和其子元素e1，…，ek，生成一條產(chǎn)生式e→lab(e) e1，…，ek，其中，lab(e)是元素e的標號．由于對每一個元素都生成了一條產(chǎn)生式，接下來需要對產(chǎn)生式進行聚類以識別出相同的元素類型．大多數(shù)文獻如［26，27］等采用的方式是將產(chǎn)生式左部符號相同的歸為一類．顯然，這種方式將所有標號相同的元素識別為同一類型，得到的是local正規(guī)樹文法(也即DTD)．文獻［28，29］提出除了元素名之外，還利用元素到根的路徑信息進行產(chǎn)生式聚類，即將所有祖先路徑相同且產(chǎn)生式左部符號也相同的產(chǎn)生式歸為一類，從而保證獲得single-type正規(guī)樹文法(即XSD)的表達能力．文獻［28］指出，為了獲得正規(guī)樹文法的表達能力，不能簡單采取祖先路徑的方式聚類．該文獻進一步提出，對于相同標號的元素，可通過計算其子樹之間的結(jié)構(gòu)相似度來歸類．子樹之間的相似度根據(jù)樹上的編輯距離［30］來衡量，產(chǎn)生式聚類利用MNC (Mutual Neighborhood Clustering)等聚類算法［31］實現(xiàn)．

4.2推導(dǎo)正則表達式

推導(dǎo)正則表達式是整個推斷過程中最重要的一步．常用的是一種稱作“合并前綴樹自動機狀態(tài)”的推導(dǎo)方法:首先對每一個產(chǎn)生式聚類，根據(jù)其右部的符號串構(gòu)造前綴樹自動機(Prefix Tree Automata，簡稱PTA) ;然后按照一定的泛化規(guī)則對自動機進行狀態(tài)合并．假設(shè)符號串集合為STR，則從STR中構(gòu)造前綴樹自動機的方式為:對于STR中的第一個串，構(gòu)造一個接受該串的簡單自動機;對于STR中剩余的每一個串，盡可能多的順著自動機的遷移規(guī)則匹配串中的字符，如果遇到一個字符不能匹配，則在自動機中添加新的路徑來接受剩余的串．圖2給出一個從含有兩條產(chǎn)生式的聚類中構(gòu)造前綴樹自動機的例子．

文獻［32］采用一組較為簡單的規(guī)則對前綴樹自動機的狀態(tài)進行合并，這些規(guī)則都是基于經(jīng)驗的推測，例如: aa?a +，表示若一個字符出現(xiàn)了兩次，則很可能該字符允許出現(xiàn)任意次．類似的規(guī)則還有: a? b? c??a|b |c，a b c d a d b c?(a|b|c|d) +等．對前綴樹自動機不斷作用狀態(tài)合并規(guī)則，一直到?jīng)]有可用的規(guī)則時停止．顯然，合并的過程對自動機所定義的正則語言進行了泛化，并且規(guī)則的不同使用順序等因素也影響了最終推導(dǎo)結(jié)果的不確定性．為了選擇較優(yōu)的結(jié)果，文獻［26］提出使用最小描述長度(Minimum Description Length，MDL)原則［33］從所有可能的候選表達式中進行選擇．MDL原則從表達式的緊湊度(conciseness)和精確度(preciseness)兩方面進行評估，前者指存儲表達式本身所需的位數(shù)，后者指使用該表達式解釋輸入串所需的位數(shù)．顯然，這種方法的優(yōu)點是能夠推導(dǎo)出較優(yōu)的結(jié)果，缺點是受搜索空間影響，效率可能降低．文獻［34］根據(jù)前綴樹自動機中狀態(tài)的等價性來進行合并．稱狀態(tài)s1、s2等價當且僅當所有從s1、s2出發(fā)到達某一終止狀態(tài)的路徑都相同．由于檢查狀態(tài)等價的復(fù)雜度較高，實際應(yīng)用中可以將路徑長度限定為某個k(k≥1)值．同時，該文獻還引入蟻群算法［35］的思想來搜索最優(yōu)解．

表2　XML模式推斷方法分類對比

XSD允許元素以任意順序出現(xiàn)和對元素的出現(xiàn)次數(shù)進行精確限定，因此其內(nèi)容模型是帶交互和計數(shù)的確定性表達式．文獻［28］和文獻［29，36，37］在推導(dǎo)表達式時分別考慮了對“交互”和“計數(shù)”操作的支持．同樣地，推導(dǎo)規(guī)則仍舊是啟發(fā)式的，例如通過統(tǒng)計元素實際出現(xiàn)的最小和最大次數(shù)來確定“計數(shù)”操作中的minOccur和maxOccur．為進一步提高表達式的可讀性和緊湊性，許多文獻還包括了對推導(dǎo)得到的表達式進行結(jié)構(gòu)化簡的步驟．化簡的原則是保持語言的等價性，有時也允許適當泛化．常見的一些化簡規(guī)則包括: a???a?，a? a +?a*，(a，b) |(a，c)?a (b|c)等．一些文獻將化簡與表達式推導(dǎo)融合在一起，邊推導(dǎo)邊化簡．部分文獻如［29］沒有考慮這一步驟．

除了文獻［38］外，上述提及的表達式推導(dǎo)過程均沒有考慮確定性問題，因此推導(dǎo)結(jié)果仍舊是標準表達式．嚴格地講，并不符合W3C規(guī)范中對DTD和XSD的元素內(nèi)容模型需要滿足惟一粒子屬性約束的要求．

4.3轉(zhuǎn)換為目標模式

最后一步是將以樹文法形式描述的推斷結(jié)果轉(zhuǎn)換為目標模式語言．由正規(guī)樹文法翻譯為DTD比較直觀，而轉(zhuǎn)換為XSD則較為復(fù)雜．文獻［39］討論了由推斷結(jié)果轉(zhuǎn)換成XSD語法時遵循的實用規(guī)則，如元素的內(nèi)容模型應(yīng)該直接在該元素定義中給出，還是另外定義一個新的復(fù)雜類型;如何識別類型間的派生(extension、restriction)關(guān)系等?文獻［38］則缺省了該步，由用戶根據(jù)需要自由轉(zhuǎn)換為所需的目標模式．

與DTD中只支持PCDATA數(shù)據(jù)類型不同，XSD中都支持豐富的基本類型和用戶自定義類型．因此，轉(zhuǎn)換為XSD時還需要進行數(shù)據(jù)類型的識別．目前，只有文獻［37，38］提到這一問題，并且只討論了簡單的數(shù)值類型如decimal、int以及字符串string等類型的識別．

4.4其他模式語言的推斷

Schematron使用斷言的方式給出一系列規(guī)則，不僅能夠定義XML文檔的結(jié)構(gòu)約束，還能夠定義較為復(fù)雜的語義完整性約束．文獻［40］研究如何由正規(guī)樹文法生成Schematron規(guī)則，因此解決的仍舊是結(jié)構(gòu)約束方面的推斷，沒有涉及較復(fù)雜的語義約束．文獻［41］對學(xué)術(shù)界最近提出的描述無序XML樹的模式語言DMS的推斷問題進行初步探討．這兩個文獻中的推斷方法沒有參照語言學(xué)習(xí)的理論模型，仍舊屬于啟發(fā)式的推斷．

4.5優(yōu)缺點分析

在啟發(fā)式的推斷方法中，無法對推斷結(jié)果所屬的語言類或文法類進行定義，也無法從理論上保證算法的學(xué)習(xí)能力等性質(zhì)．然而，由于其直觀、靈活、易實現(xiàn)等特點，在當前仍有較廣泛的研究和應(yīng)用．文獻［42］對該類推斷方法進行了深入探討，文獻［43］實現(xiàn)一個啟發(fā)式推斷方法研究的輔助工具集，提供文檔解析、自動機可視化等基本功能．

5　基于語言極限識認模型的推斷方法

內(nèi)容模型推斷本質(zhì)上歸結(jié)為確定性表達式的學(xué)習(xí)．Gold定理已指出:不能在有限時間內(nèi)僅通過正樣例來識認類別不受限制的正則表達式．Bex等人［25］證明出這一結(jié)論同樣適用于確定性表達式．因此，在基于語言極限識認模型的推斷方法中，首先需要尋找可學(xué)習(xí)的受限表達式子類，其次，以受限表達式為目標語言，設(shè)計具有正確性和完全性的學(xué)習(xí)算法．

5.1受限表達式子類

確定性表達式可學(xué)習(xí)子類中最具代表性的兩個分別是單次出現(xiàn)表達式和鏈表達式．一個正則表達式中如果每個字符最多只出現(xiàn)一次，那么稱該表達式為單次出現(xiàn)表達式(Single Occurrence Regular Expression，簡稱SORE)．例如，(((a+(b| c) ?)+) d)+是一個SORE，而a? (ba|c)不是一個SORE．如果一個SORE滿足如下形式: f1·…·fn(n≥0)，其中每個fi是一個形如(a1| …|ak)、(a1|…| ak) ?、(a1|…| ak)+或(a1|…| ak)+?的鏈式因子，其中k≥1，每個aj(1≤j≤k)都是一個終極符，那么稱該正則表達式為鏈表達式(Chain Regular Expression，簡稱CHARE)．例如，(a|b)+? c? (d|e|f)+是一個CHARE，(ab+|c|d) ? (e? |f|g+)+則不是．

根據(jù)定義可知SORE和CHARE屬于確定性正則表達式．文獻［44］中的統(tǒng)計結(jié)果顯示，XML模式中出現(xiàn)的正則表達式絕大部分為SORE，而SORE中90％為CHARE．文獻［45，46］證明出對于這兩類受限表達式，存在滿足Gold極限識認模型的推斷算法，即存在一個既是正確的又是完全的推斷算法．算法分為兩步:首先根據(jù)輸入串構(gòu)造單次出現(xiàn)自動機(Single Occurrence Automata，簡稱SOA)，其次從SOA中推導(dǎo)受限表達式．

5.2構(gòu)造SOA

令Σ表示一個字母表，src和sink是兩個特殊符號，src表示開始狀態(tài)，sink表示接受狀態(tài)．Σ上的單次出現(xiàn)自動機SOA是一個滿足以下兩個條件的有向圖A = (V，E) : (1) { src，sinkV，VΣ∪{ src，sink}，V中的每個結(jié)點都有結(jié)點標記，對應(yīng)于Σ中的一個終極符; (2) src結(jié)點只有出邊，sink結(jié)點只有入邊，每一個結(jié)點v∈V都位于src到sink的路徑上．一個句子w = a1…an(n≥0)被SOA接受，當且僅當在SOA中存在這樣一條路徑: src→v1→…→vn→sink，其中結(jié)點vi的標記為ai(1≤i ≤n)．L(A)表示所有被SOA A = (V，E)接受的句子集合，即被A接受的語言．

SOA的定義和通用的自動機定義有些區(qū)別，SOA中的邊沒有遷移標記，每個結(jié)點(狀態(tài))都對應(yīng)于一個終極符，稱為結(jié)點標記．不難看出SOA是確定性有窮自動機(Deterministic Finite Automaton，簡稱DFA)的子類，且每個SOA都存在一個等價的DFA與之對應(yīng)．如果在DFA中存在一條遷移標記為a∈Σ的邊指向狀態(tài)q，那么相應(yīng)地在SOA中存在一個標記為a的結(jié)點有一條入邊．DFA中的開始狀態(tài)和結(jié)束狀態(tài)分別對應(yīng)于SOA中的src結(jié)點和所有到sink存在遷移邊的結(jié)點．

從句子集S構(gòu)造SOA可采用經(jīng)典的2T-INF算法［47］:如果非終極符a、b在句子集S中是相鄰的，則稱(a，b)為S的一個二元組;對于S的每一個二元組(a，b)，添加一條從頂點a到頂點b的邊，便可構(gòu)造出輸入串對應(yīng)的SOA．例如，句子集合S = { aab，cdd}，由2TINF生成的SOA如圖3所示，其中src和sink分別表示起始點和結(jié)束點．

顯然，對于給定句子集合S和由2T-INF算法生成的SOA A，有SL(A)成立．文獻［46］指出，對于目標表達式E和句子集S，如果E所定義的語言L(E)中的所有二元組(a，b)都在句子集S中出現(xiàn)，則L(E) = L(2T-INF(S) )．

5.3推導(dǎo)受限表達式

文獻［46，48］分別給出由SOA推導(dǎo)受限表達式的兩種不同方法．文獻［46］中的推導(dǎo)是基于一組重寫規(guī)則，例如:若SOA中兩個頂點a和b具有相同的前驅(qū)頂點和相同的后繼頂點，則將其重寫為一個頂點a | b;若頂點a到自身有一條邊，則將a及其反身邊重寫為一個頂點a+．在SOA上不斷地作用重寫規(guī)則，一直到?jīng)]有適用的規(guī)則時停止，最后得到的頂點即是SORE．由SOA推導(dǎo)CHARE則是基于有向無環(huán)圖的拓撲序列．首先計算出SOA中的強連通分量，將其替換為一個頂點:若分量中含有三個頂點a、b、c，則替換為頂點為(a | b| c)+．替換后的SOA是一個有向無環(huán)圖，求出其任一拓撲序列，使用連接算子連接起來即是推導(dǎo)得到的CHARE．文獻［46］證明出對于任一SORE(或CHARE) E，存在一個輸入集S，使得L(E) = L(τ(2T-INF(S) ) )，其中τ表示上述推導(dǎo)算法．因此，這也意味著當輸入信息足夠多時，推斷得到的SORE表達式不再變化，滿足語言極限識認模型中的“完全性”要求．例如，圖3所示的SOA推導(dǎo)得到的SORE和CHARE分別為: (a+b) | (cd+)、a+? c? b? d+?．

語言的歸納學(xué)習(xí)存在泛化問題，比較理想的狀態(tài)是實現(xiàn)最小包含泛化或稱描述性泛化［49］．對于輸入串S和推導(dǎo)得到的SORE(或CHARE)表達式E，如果不存在一個SORE(或CHARE)表達式E'滿足SL(E')L(E)，則稱E是S的SORE(或CHARE) -最小包含泛化．文獻［48］指出文獻［46］中的推導(dǎo)算法雖然滿足語言極限識認模型，但是沒有達到描述性泛化要求，因此不是最優(yōu)的．該文獻提出對SOA中的頂點劃分級數(shù)，結(jié)合頂點所處的級數(shù)和其它相關(guān)信息施加相應(yīng)的表達式算子進行推導(dǎo)，并證明了算法的最小包含泛化特性．在某些情況下，兩種推導(dǎo)算法得到的表達式相同．也就是說文獻［46］的算法在某些情況下也可以實現(xiàn)最小包含泛化，但不是對所有情況都成立．

5.4k-ORE和k-local XSD

文獻［50］將表達式的限制放松為每個字符可以出現(xiàn)k次，稱為k-ORE．對于k-ORE，雖然存在滿足Gold極限識認模型的學(xué)習(xí)算法，但是算法的運行時間為指數(shù)級．為此，該文獻給出另外一種基于隱馬爾科夫模型的學(xué)習(xí)算法，首先利用概率模型構(gòu)造kOA，再轉(zhuǎn)換為k-ORE．對于同一個輸入集和不同的k值，可以先學(xué)習(xí)出若干個k-ORE，然后利用最小描述長度原則選擇最優(yōu)者．

SORE、CHARE、以及k-ORE的學(xué)習(xí)算法均可應(yīng)用于XSD的內(nèi)容模型推斷．除此之外，需要解決的另一個問題是XSD的類型識別．Bex等［51］發(fā)現(xiàn)在大部分XSD中，元素類型由其最近的祖先名稱所決定，據(jù)此提出klocal XSD的概念并給出相應(yīng)推斷算法．顯然，該方法的一個缺點是推斷結(jié)果與k的選擇有關(guān)．實際上，當k =1時即退化為DTD．另一個缺點是會產(chǎn)生大量的類型，導(dǎo)致最終得到的模式定義不夠簡潔．

5.5優(yōu)缺點分析

基于語言極限識認模型的推斷方法的優(yōu)點是推斷結(jié)果所屬的語言類具有清晰明確的界定，推斷算法從理論上可以保證具備良好特性:既滿足正確性又滿足完全性，甚至最小泛化特性．缺點是推斷結(jié)果受到限制，比如內(nèi)容模型必須是SORE或CHARE等，缺乏靈活性．

6　基本的語義完整性約束推斷

除了結(jié)構(gòu)約束外，一般模式語言還提供了基本的語義完整性約束定義機制．例如，W3C推薦在XSD中使用“key”和“keyref”元素定義主鍵和外鍵，許多行業(yè)標準采用這些約束描述數(shù)據(jù)的聯(lián)系與依存規(guī)則．DTD中提供的“ID”和“IDREF”屬性類型起到類似作用，但是定義能力相對較弱．鍵約束是最基本也最常見的完整性約束類型，用于保證實體完整性和引用正確性，在查詢優(yōu)化、數(shù)據(jù)質(zhì)量管理、數(shù)據(jù)交換中保持語義信息等方面發(fā)揮著重要作用．因此，完整的模式推斷不僅需要考慮結(jié)構(gòu)約束，還需要考慮語義方面的約束．相比于結(jié)構(gòu)約束，XML的完整性約束推斷算法研究較少．

(1) DTD中的約束推斷

DTD中提供了ID/IDREF(S)屬性類型用于在整個文檔中標識元素和定義引用，類似于主鍵和外鍵．尋找XML文檔中ID/IDREF(S)屬性的基本步驟是首先計算出元素和屬性之間的映射關(guān)系，然后根據(jù)是否滿足單射來確定元素的ID屬性，最后依據(jù)ID屬性值來尋找IDREF(S)屬性．為了避免產(chǎn)生無意義的屬性，文獻［52］引入了“支持度”和“覆蓋度”的概念來衡量和選擇最優(yōu)者．文獻［53］使用類似方法，不同之處在于將選擇最優(yōu)者歸約為整數(shù)線性規(guī)劃解決．

(2) XSD中的約束推斷

XSD中的“key”和“keyref”元素使用路徑表達式定義主鍵和外鍵約束，允許約束限定在文檔的某個范圍內(nèi)，比DTD中的ID/IDREF(S)的表達能力強．XSD主鍵定義形式化描述為key = (c，(Q，{ P1，P2，…，Pk} ) )，其中c稱為上下文，由元素名和該元素的類型決定; Q 和{ P1，P2，…，Pk}分別稱為目標路徑和鍵路徑集，使用一類受限XPath表達式定義．XSD規(guī)范要求對于每一個鍵路徑表達式Pi和由Q計算得到的作用域中的每一個目標結(jié)點u而言，Pi(u)的計算結(jié)果必須是singleton的，即只能包含一個帶有數(shù)據(jù)值的結(jié)點．XSD規(guī)范要求鍵定義應(yīng)該與模式定義相一致，也即對于任意符合模式的XML文檔，鍵都應(yīng)滿足上述規(guī)范．外鍵約束定義形式與主鍵類似，鍵路徑表達式也需滿足相同的規(guī)范．此外，XSD還限定被引用的主鍵應(yīng)與外鍵在同一上下文范圍內(nèi)．

目前為止只有文獻［54］探討了XSD主鍵約束的推斷算法．該文獻首先采用逐層搜索(levelwise search)［55］方法根據(jù)XML文檔中的信息找出所有合法的且滿足一定支持度的候選主鍵，然后進行一致性檢查去除與模式不一致的，最后利用關(guān)系數(shù)據(jù)上的函數(shù)依賴發(fā)現(xiàn)算法［56～58］驗證最終的主鍵．受搜索空間與一致性檢查等影響，該方法在效率上存在缺陷．實際上，該文獻給出的實驗數(shù)據(jù)顯示，當輸入規(guī)模較大時，幾乎全部的時間消耗在一致性檢查上，而最終得到的一致性主鍵只占整個候選主鍵的很小一部分．該文獻也指出如何解決這一瓶頸是個重要的遺留問題．

(3)其他約束推斷

較早關(guān)于XML鍵的定義由Buneman等［59］給出，定義方式與XSD相同，但是沒有限制與模式定義的一致性．文獻［60～63］針對Buneman等的鍵定義研究自動發(fā)現(xiàn)算法．其中，文獻［60］利用關(guān)系數(shù)據(jù)上的相關(guān)算法實現(xiàn)，文獻［61，62］關(guān)注發(fā)現(xiàn)近似鍵，文獻［63］則研究從XQuery查詢?nèi)罩局袑ふ遥送猓麈I和外鍵分別是函數(shù)依賴和包含依賴的特例．一些學(xué)者研究XML函數(shù)依賴及其發(fā)現(xiàn)算法［64～67］，但是同樣沒有考慮模式問題．

7　結(jié)束語

本文針對XML模式推斷問題的研究現(xiàn)狀進行了較為全面的介紹和討論:首先，從樹文法的角度介紹了不同模式語言的理論模型;其次，將現(xiàn)有的模式推斷方法分為啟發(fā)式的方法和基于語言極限識認模型的方法兩大類，并且從目標模式語言、支持的表達能力、內(nèi)容模型對應(yīng)的正則表達式類型等多個維度進行分析和討論;最后，介紹了模式語言中支持的基本語義完整性約束的推斷研究．

XML模式推斷的重要性與現(xiàn)實必要性引起越來越多的學(xué)者的關(guān)注．然而，XML半結(jié)構(gòu)化的模型、復(fù)雜的模式定義等，給問題的解決增加了難度，尚有許多值得深入探索的問題．在本文的最后，我們提出一些值得進一步研究和探討的方面．

(1)正反例相結(jié)合的推斷．Gold定理指出在只有正例的情況下，即便是表達能力較弱的正則語言也無法學(xué)習(xí)．如果在提供正例的同時還提供反例，則有望克服基于語言極限識認模型的推斷方法在僅有正例時的局限性．但是在實際應(yīng)用中，由于反例信息不容易自動辨識或獲取，因此可能需要進行人為的干預(yù)．

(2)輸入數(shù)據(jù)預(yù)處理．網(wǎng)絡(luò)環(huán)境的復(fù)雜性極易導(dǎo)致噪聲數(shù)據(jù)的存在．例如，一組描述某公司訂單信息的XML文檔中可能不小心摻雜個別關(guān)于其他信息的文檔．噪聲數(shù)據(jù)的模式一般會顯著區(qū)別于其他的情況，如果不進行處理，會導(dǎo)致推斷得到的模式過于一般化．為獲得更加精確和有效的模式，有必要對輸入數(shù)據(jù)進行噪聲消除的預(yù)處理．

(3)對XSD中高級類型定義機制的支持．已有的XSD推斷研究大多利用了DTD的內(nèi)容模型生成方法，因此得到的XSD在定義能力上仍舊局限于DTD．如何有效支持XSD中的繼承、多態(tài)、用戶自定義類型等定義機制需要進一步的研究．

(4)增量式維護．隨著網(wǎng)絡(luò)的廣泛普及和應(yīng)用的深入，網(wǎng)絡(luò)數(shù)據(jù)往往呈現(xiàn)快速增長的趨勢．增量計算是應(yīng)付數(shù)據(jù)動態(tài)變化和降低計算成本的有效手段．因此，有必要研究對推斷的模式進行增量維護的方法，以減少重復(fù)計算，提升處理效率，更好地滿足實際應(yīng)用的需求．

(5)完整性約束推斷．除了結(jié)構(gòu)約束外，一般模式語言還提供了基本的語義完整性約束定義機制．因此，完整的模式推斷不僅需要考慮結(jié)構(gòu)約束，還需要考慮語義方面的約束．(1)現(xiàn)有的研究主要關(guān)注前者而忽略了后者; (2)當前大多數(shù)完整性約束發(fā)現(xiàn)算法與模式完全獨立，而W3C規(guī)范要求某些約束，如XSD鍵等，應(yīng)該與模式定義相一致．因此，如何結(jié)合模式信息推斷符合規(guī)范的復(fù)雜語義約束也是一個重要研究方向．

參考文獻

［1］Tova M，Suciu D，Vianu V．Typechecking for XML transformers［J］．Journal of Computer and System Sciences，2003，66(1) : 66－97．

［2］Bj?rklund H，Martens W，Schwentick T．Optimizing conjunctive queries over trees using schema information［A］．Proceedings of the International Symposium on Mathematical Foundations of Computer Science［C］．Berlin Heidelberg: Springer，2008．132－143．

［3］Halevy A，Rajaraman A，Ordille J．Data integration: the teenage years［A］．Proceedings of the VLDB［C］．New York: ACM Press，2006．9－16．

［4］Barbosa D，Mignet L，Veltri P．Studying the XML web: Gathering statistics from an XML sample［J］．World Wide Web，2006，9(2) : 187－212．

［5］Martens W，Neven F，Schwentick T and Bex G J．Expressiveness and complexity of XML Schema［J］．ACM Transactions on Database Systems，2006，31(3) : 770－813．

［6］Grijzenhout S，Marx M．The quality of the XML web［J］．Web Semantics: Science，Services and Agents on the World Wide Web，March 2013，19: 59－68．

［7］Florescu D．Managing semi-structured data［J］．ACM Queue，2005，3(8) : 18－24．

［8］Hinkelman S．Business integration-－Information conformance statements［R］．Technique Report，IBM Developer Works，2005．

［9］Bray T，Paoli J，et al．Extensible markup language(XML) 1．0(Fifth Edition)［EB/OL］．http: / /www．w3．org/TR/ 2008/REC-xml-20081126/，2008．

［10］Gao S，Sperberg-McQueen C M，Thompson H S．XML schema definition language(XSD) 1．1 part 1: structures ［EB/OL］．http: / /www．w3．org/TR/2012/REC-xmlschema11-1-20120405/，2012．

［11］Clark J，Murata M．RELAX NG specication［EB/OL］．http: / /www．oasis-open．org/-committees/relax-ng/，2001．

［12］Jelliffe R．The schematron——an XML structure validation language using patterns in trees［EB/OL］．http: / / xml．a(chǎn)scc．net/resource/schematron/，2001．

［13］Hosoya H，Pierce B C．XDuce: A statically typed XML processing language［J］．ACM Transactions on Internet Technology(TOIT)，2003，3(2) : 117－148．

［14］Klarlund N，M?ller A，Schwartzbach M I．DSD: A schema language for XML［A］．Proceedings of the Third Workshop on Formal Methods in Software Practice［C］．New York: ACM Press，2000．101－111．

［15］Boneva I，Ciucanu R，Staworko S．Simple schemas for unordered XML［A］．Proceedings of the WebDB［C］．New Tork: ACM Press，2013．13－18．

［16］Berstel J，Boasson L．XML grammars［A］．Proceedings of the International Symposium on Mathematical Foundations of Computer Science［C］．Berlin Heidelberg: Springer，2000．182－191．

［17］Neven F．Automata，logic，and XML［A］．Proceedings of the Conference of the European Association For Computer Science Logic［C］．Berlin Heidelberg: Springer，2002．2 －26．

［18］Berstel Jean，Boasson L．Balanced grammars and their languages［J］．Formal and natural computing，2002，2300 (3) : 3－25．

［19］Alur R，Madhusudan P．Visibly pushdown languages［A］．Proceedings of the STOC［C］．New York: ACM Press，2004．202－211．

［20］McNaughton R．Parenthesis grammars［J］．Journal of the ACM，1967，14(3) : 490－500．

［21］Comon H，Dauchet M，et al．Tree automata techniques and applications［DB/OL］．Available on: http: / /www．grappa．univ－lille3．fr/tata，2012．

［22］Murata M，et al．Taxonomy of XML schema languages using formal language theory［J］．ACM Transactions on Internet Technology，2005，5(4) : 660－704．

［23］Brüggemann-Klein A，Wood D．One-unambiguous regular languages［J］．Information and computation，1998，140 (2) : 229－253．

［24］Gold E M．Language identification in the limit［J］．Information and control，1967，10(5) : 447－474．

［25］Bex G J，Gelade W，Neven F，et al．Learning deterministic regular expressions for the inference of schemas from XML data［A］．Proceedings of the WWW［C］．New York: ACM Press，2008．825－834．

［26］Garofalakis M，Gionis A，Rastogi R，et al．XTRACT: learning document type descriptors from XML document collections［J］．Data Mining And Knowledge Discovery，2003，7(1) : 23－56．

［27］Min J K，Ahn J Y，Chung C W．Efficient extraction of schemas for XML documents［J］．Information Processing Letters，2003，85(1) : 7－12．

［28］Vo?ta O，Mlynková I，et al．Even an ant can create an XSD［A］．Proceedings of the DASFAA［C］．Berlin Heidelberg: Springer，2008．35－50．

［29］寧靜，劉杰，葉丹．一種基于內(nèi)容模型圖XML Schema Definition的提取方法［J］．計算機科學(xué)，2010，37(6) : 179－185．Ning Jing，Liu Jie，Ye Dan．Novel approach for extractingXML schema definition based on content model graph ［J］．Computer Science，2010，37(6) : 179－185．(in Chinese)

［30］Nierman A，Jagadish H V．Evaluating structural similarity in XML documents［A］．Proceedings of the WebDB［C］．New York: ACM Press，2002．61－66．

［31］Jain A K，Dubes R C．Algorithms for Clustering Data ［M］．New York: Prentice-Hall Inc．，1988．55－142．

［32］Moh C H，Lim E P，Ng W K．Re-engineering structures from Web documents［A］．Proceedings of the fifth ACM conference on Digital Libraries［C］．New York: ACM Press，2000．67－76．

［33］Grünwald P．Model selection based on minimum description length［J］．Journal of Mathematical Psychology，2000，44(1) : 133－152．

［34］Sankey J，Wong R K．Structural inference for semistructured data［A］．Proceedings of the CIKM［C］．New York: ACM Press，2001．159－166．

［35］Dorigo M，Birattari M，Stutzle T．Ant colony optimization ［J］．IEEE Computational Intelligence Magazine，2006，1 (4) : 28－39．

［36］Zhang Y，Zhou H，Liu J，et al．Efficient schema extraction from large XML documents［A］．Proceedings of the 5th International Conference on Biomedical Engineering and Informatics［C］．Berlin: IEEE Computer Society Press，2012．1255－1260．

［37］Hegewald J，Naumann F，Weis M．XStruct: efficient schema extraction from multiple and large XML documents ［A］．Proceedings of the ICDE Workshops［C］．Berlin: IEEE Computer Society Press，2006．

［38］Chidlovskii B．Schema extraction from XML: a grammatical inference approach［A］．Proceedings of the KRDB ［C］．Aachen Germany: CEUR-WS．org，2001．

［39］Mlynková I，NeˇcaskyM．Towards inference of more realistic XSDs［A］．Proceedings of the SAC［C］．New York: ACM Press，2009．639－646．

［40］Kozák M，Stárka J，Mlynková I．Schematron schema inference［A］．Proceedings of the IDEAS［C］．New York: ACM Press，2012．42－50．

［41］Ciucanu R，Staworko S．Learning schemas for unordered XML［A］．Proceedings of the DBPL［C］．New York: ACM Press，2013．31－40．

［42］Mlynková I，NeˇcaskˇcyM．Heuristic methods for inference of XML schemas: lessons learned and open issues［J］．Informatica，2013，24(4) : 577－602．

［43］Klempa M，et al．jInfer: A framework for XML schema inference［J］．The Computer Journal，to appear．doi: 10．1093/comjnl/bxt148．

［44］Bex G J，Neven F，Bussche J．DTDs versus XML Schema: a practical study［A］．Proceedings of the WebDB ［C］．New York: ACM Press，2004．79－84．

［45］Bex G J，et al．Inference of concise DTDs from XML data ［A］．Proceedings of the VLDB［C］．New York: ACM Press，2006．115－126．

［46］Bex G J，Neven F，Schwentick T，et al．Inference of concise regular expressions and DTDs［J］．ACM Transactions on Database Systems，2010，35(2) : 1－47．

［47］Garcia P，Vidal E．Inference of k-testable languages in the strict sense and application to syntactic pattern recognition ［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，1990，12(9) : 920－925．

［48］Freydenberger D，K?tzing T．Fast learning of restricted regular expressions and DTDs［A］．Proceedings of the ICDT［C］．New York: ACM Press，2013．45－56．

［49］Freydenberger D，Reidenbach D．Inferring descriptive generalisations of formal languages［J］．Journal of Computer and System Sciences，2012，79(5) : 622－639．

［50］Bex G J，Gelade W，Neven F，et al．Learning deterministic regular expressions for the inference of schemas from XML data［J］．ACM Transactions on the Web，2010，4 (4) : 14: 1－14: 32．

［51］Bex G J，Neven F，Vansummeren S．Inferring XML schema definitions from XML data［A］．Proceedings of the VLDB［C］．New York: ACM Press，2007．998－1009．

［52］Barbosa D，Mendelzon A．Finding ID attributes in XML documents［J］．Lecture Notes in Computer Science，2003，2824: 180－194．

［53］Vitásek M，Mlynková I．Inference of XML integrity constraints［J］．Advances in Databases and Information Systems，2013，186: 285－296．

［54］Arenas M，Daenen J，Neven F，et al．Discovering XSD keys from XML data［A］．Proceedings of the SIGMOD ［C］．New York: ACM Press，2013．61－72．

［55］MannilaH，Toivonen H．Levelwise search and borders of theories in knowledge discovery［J］．Data mining and knowledge discovery，1997，1(3) : 241－258．

［56］Mannila H，R?ih?K J．Algorithms for inferring functional dependencies from relations［J］．Data＆Knowledge Engineering，1994，12(1) : 83－99．

［57］Mannila H，Raiha K J．Practical algorithms for finding prime attributes and testing normal forms［A］．Proceedings of the PODS［C］．New York: ACM Press，1989．128 －133．

［58］Bitton D，Millman J，Torgersen S．A feasibility and performance study of dependency inference［A］．Proceedings of the ICDE［C］．Berlin: IEEE Computer Society Press，1989．635－641．

［59］Buneman P，Davidson S，F(xiàn)an W，et al．Keys for XML［J］．Computer Networks，2002，39(5) : 473－487．

［60］Fajt S，Mlynkova I，Necasky M．On mining XML integrity constraints［A］．Proceedings of the 6th International Conference on Digital Information Management［C］．Berlin: IEEE Computer Society Press，2011．23－29．

［61］Grahne G，Zhu J．Discovering approximate keys in XML data［A］．Proceedings of the CIKM．［C］．New York: ACM Press，2002．453－460．

［62］Liu Y，Ye F，He S．Mining approximate keys based on reasoning from XML data［A］．Proceedings of the PAKDD Workshops［C］．Berlin Heidelberg: Springer，2013．499－510．

［63］NeˇcaskyM，Mlynková I．Discovering XML keys and foreign keys in queries［A］．Proceedings of the SAC［C］．New York: ACM Press，2009．632－638．

［64］Trinh T．Using transversals for discovering XML functional dependencies［J］．Lecture Notes in Computer Science，2008，4932: 199－218．

［65］Shi H，Amagasa T，Kitagawa H．Fast detection of functional dependencies in XML data［J］．Lecture Notes in Computer Science，2010，6309: 113－127．

［66］Liu J，et al．Discover dependencies from data-a review ［J］．IEEE Transactions on Knowledge and Data Engineering，2012，24(2) : 251－264．

［67］金峰，陶曉鵬，胡運發(fā)．XML函數(shù)約束規(guī)則的自動挖掘［J］．計算機科學(xué)，2003，30(10) : 227－229．Jin Feng，Tao Xiaofeng，Hu Yunfa．Automatica mining of functional constraint rule in XML document［J］．Computer Science，2003，30(10) : 227－229．(in Chinese)

鄭黎曉女，1983年9月生于河南南陽．分別于2006年和2012年于吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院和中國科學(xué)院軟件研究所獲學(xué)士學(xué)位和博士學(xué)位．現(xiàn)為華僑大學(xué)計算機科學(xué)與技術(shù)學(xué)院講師．研究方向:形式語言與自動機，數(shù)據(jù)庫理論，軟件測試等．

E-mail: zhenglx@ hqu．edu．cn

王成男，1984年4月生．分別于2006年和2012年于電子科技大學(xué)和西安交通大學(xué)獲學(xué)士學(xué)位和博士學(xué)位．現(xiàn)為華僑大學(xué)計算機科學(xué)與技術(shù)學(xué)院講師．研究方向:機器學(xué)習(xí)，智能電子商務(wù)數(shù)據(jù)挖掘．

E-mail: wangcheng@ hqu．edu．cn

Schema Inference from XML Data: A Review

ZHENG Li-xiao1，2，WANG Cheng1
(1．College of Computer Science and Technology，Huaqiao University，Xiamen，F(xiàn)ujian 361021，China; 2．The State Key Laboratory of Computer Science，Institute of Software，Chinese Academy of Sciences，Beijing 100190，China)

Abstract:This paper surveys the state of the art of schema inference from XML data．First，the formal models based on regular tree grammar for commonly used XML schema languages are presented．Then，the existing works on XML schema inference are summarized and compared from various aspects such as inference methods，target schema languages，supported expressiveness，regular expression types corresponding to the content models，and so on．In addition，inferences of some basic integrity constraints from XML data are also introduced．Finally，this paper points out the defects of current research and discusses some potential future research directions．This paper aims to offer a detail overview，comparison and analysis of the mainstream methods and recent progress in this field，expecting to be beneficial for subsequent research．

Key words:XML(Extensible Markup Language) ; schema inference; regular tree grammar; regular expression

作者簡介

基金項目:華僑大學(xué)科研啟動基金(No．12BS215) ;國家自然科學(xué)基金(No．51305142，No．61502184) ;福建省自然科學(xué)基金(No．2015J01259)

收稿日期:2014-07-02;修回日期: 2014-08-26;責(zé)任編輯:馬蘭英

DOI:電子學(xué)報URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．030

中圖分類號:TP311

文獻標識碼:A

文章編號:0372-2112 (2016) 02-0461-11