摘  要： 為從企業(yè)生產(chǎn)線上XML半結(jié)構(gòu)化數(shù)據(jù)中抽取富有意義數(shù)據(jù),，分析了XML半結(jié)構(gòu)化數(shù)據(jù)和關(guān)系數(shù)據(jù)庫中結(jié)構(gòu)化數(shù)據(jù)特點，以及XML半結(jié)構(gòu)化數(shù)據(jù)在關(guān)系數(shù)據(jù)庫中的存儲方法,。針對實際應(yīng)用,，提出采用擴(kuò)展哈弗曼前綴編碼方法，對XML文檔樹進(jìn)行唯一編碼，實現(xiàn)XML文檔與關(guān)系數(shù)據(jù)庫映射,，同時給出最長前綴匹配策略,，支持?jǐn)?shù)據(jù)查詢，以提高查詢效率,。
關(guān)鍵詞： XML,；關(guān)系數(shù)據(jù)庫；哈弗曼前綴編碼,；匹配策略,；模型映射

　互聯(lián)網(wǎng)的迅速發(fā)展，使得網(wǎng)上數(shù)據(jù)不斷增加,，這些數(shù)據(jù)形式不統(tǒng)一,，其數(shù)據(jù)結(jié)構(gòu)的組織方式也各不相同，促使XML半結(jié)構(gòu)化數(shù)據(jù)成為互聯(lián)網(wǎng)上數(shù)據(jù)交換或數(shù)據(jù)瀏覽的中間媒介,，其無模式及自描述的特點適于描述網(wǎng)上數(shù)據(jù),，它的出現(xiàn)推動了互聯(lián)網(wǎng)在電子商務(wù)和企業(yè)生產(chǎn)線等多方面的應(yīng)用。但要想對這種半結(jié)構(gòu)化數(shù)據(jù)進(jìn)行有效地管理十分困難,，傳統(tǒng)的DBMS主要用于管理結(jié)構(gòu)化數(shù)據(jù),，半結(jié)構(gòu)化數(shù)據(jù)與傳統(tǒng)的DBMS管理的數(shù)據(jù)的模式大不相同，如何對半結(jié)構(gòu)化數(shù)據(jù)實施有效的管理成為新的研究領(lǐng)域,。而在理論和實踐上都非常成熟的關(guān)系數(shù)據(jù)庫使用廣泛,，數(shù)據(jù)處理能力強(qiáng)，查詢性能好,，采用關(guān)系數(shù)據(jù)庫對XML數(shù)據(jù)進(jìn)行存儲和操作,，將半結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)為結(jié)構(gòu)化數(shù)據(jù)，通過查詢數(shù)據(jù)庫來提取,、綜合和分析XML數(shù)據(jù),，充分利用成熟的數(shù)據(jù)庫技術(shù)處理XML數(shù)據(jù)已成為重要手段[1-2]。
　互聯(lián)網(wǎng)的發(fā)展也使企業(yè)中大量信息資源以XML半結(jié)構(gòu)化數(shù)據(jù)的形式存在,，半結(jié)構(gòu)化數(shù)據(jù)成為企業(yè)決策人員獲取,、傳播和交換信息的重要途徑。本文基于一個實際的生產(chǎn)項目,，主要對企業(yè)生產(chǎn)線中XML半結(jié)構(gòu)化數(shù)據(jù)資源,，采用擴(kuò)展哈弗曼前綴編碼技術(shù)轉(zhuǎn)化為在關(guān)系數(shù)據(jù)庫中存儲，并采用前綴匹配策略實現(xiàn)XML數(shù)據(jù)查詢,，抽取富有意義的數(shù)據(jù),，為管理部門提供完整的決策支持?jǐn)?shù)據(jù)，有助于企業(yè)決策者實現(xiàn)其目標(biāo),。
1 XML與關(guān)系數(shù)據(jù)庫
　XML（Extensible Markup Language）用于標(biāo)記電子文件使其具有結(jié)構(gòu)性的標(biāo)記語言,，可以用來標(biāo)記數(shù)據(jù),、定義數(shù)據(jù)類型。一個XML文檔是由一個根元素和若干個子元素組成,，元素用標(biāo)記來標(biāo)識和界定,，XML可看作是有層次結(jié)構(gòu)的半結(jié)構(gòu)化數(shù)據(jù)。XML其優(yōu)勢在于可擴(kuò)展性強(qiáng),，簡單易懂,，不同平臺間的信息交換性好，支持國際化,。隨著XML技術(shù)越來越被人們認(rèn)識和了解,，其在數(shù)據(jù)傳輸和數(shù)據(jù)存儲方面的優(yōu)越性也逐漸被人們重視起來。
　關(guān)系數(shù)據(jù)庫是為存儲和管理結(jié)構(gòu)化數(shù)據(jù)設(shè)計的,，采用二維表作為存儲數(shù)據(jù)的模型,，二維表由行和列組成，列用于表示組成數(shù)據(jù)有效信息屬性,，行用于表示一條由各個字段組成的完整數(shù)據(jù)記錄,。表間相關(guān)性通過主鍵—外鍵來關(guān)聯(lián)。
　XML文檔是一種典型的半結(jié)構(gòu)化數(shù)據(jù)[3],，它既能表示關(guān)系,、對象等結(jié)構(gòu)化數(shù)據(jù)，也能表示W(wǎng)eb半結(jié)構(gòu)化數(shù)據(jù),。具有層次結(jié)構(gòu)的半結(jié)構(gòu)化數(shù)據(jù)與扁平的二維表關(guān)系模型之間存在固有的不匹配性,。如果采用關(guān)系數(shù)據(jù)庫來存儲XML數(shù)據(jù)，首先要解決如何把XML文檔模式映射為關(guān)系模式,，即兩個異構(gòu)模式之間的模式映射,。
2 XML數(shù)據(jù)與關(guān)系數(shù)據(jù)庫轉(zhuǎn)換
2.1 XML數(shù)據(jù)與關(guān)系數(shù)據(jù)庫映射方法
　目前，基于關(guān)系的XML存儲的研究受到國內(nèi)外研究者的重視,，總的來說根據(jù)存儲時是否使用XML模式（DTD或XML Schema）可以分為結(jié)構(gòu)映射方法和模型映射方法兩類,。
　（1）結(jié)構(gòu)映射是與XML模式（DTD或XML schema）相關(guān)[4],，即依賴于文檔模式的關(guān)系存儲,。這種存儲映射策略把XML文檔本身看作是數(shù)據(jù)庫中的數(shù)據(jù)區(qū)，DTD或者Schema可以看成是數(shù)據(jù)模式,。依賴于文檔模式的關(guān)系存儲映射就是把DTD或Schema映射為關(guān)系數(shù)據(jù)庫中的Schema,，然后把XML文檔存儲到關(guān)系數(shù)據(jù)庫中。對XML數(shù)據(jù)中結(jié)構(gòu)化的信息建模時,，采用關(guān)系數(shù)據(jù)庫中的主外鍵連接來映射XML樹的父子關(guān)系,。
?。?）模型映射方法維護(hù)用來存儲XML文檔的一個固有的模式[4],，其基本的思想是捕捉XML文檔的樹結(jié)構(gòu),。主要特點是將任何數(shù)據(jù)都放在有固定關(guān)系模式的數(shù)據(jù)庫中，而不考慮XML文檔模式（DTD或XML Schema）,，其本質(zhì)是存儲XML文檔本身的結(jié)構(gòu)信息,。在模型映射方法中，XML文檔被看做由元素和屬性等結(jié)點組成的有向有序的樹或圖,，關(guān)系模式相當(dāng)于一個模板,，XML在關(guān)系數(shù)據(jù)庫中的存儲按數(shù)據(jù)庫提供的模板來組織數(shù)據(jù)。
　由于模型映射方法與XML模式（DTD或XML schema）無關(guān),，而企業(yè)生產(chǎn)線上XML數(shù)據(jù)是一種無模式XML數(shù)據(jù),，更加符合模型映射的特征。本文采用模型映射方法實現(xiàn)映射轉(zhuǎn)換工作,，以便更好地利用關(guān)系數(shù)據(jù)庫成熟技術(shù)進(jìn)行數(shù)據(jù)管理,。
2.2 XML文檔編碼方案

　XML文檔可以樹模型來描述，文檔中的元素,、屬性和值對應(yīng)樹模型中的結(jié)點,，文檔中元素與元素、元素與值對應(yīng)樹模型中的邊,。對于XML文檔樹編碼方案,，主要分為兩種：基于區(qū)間的編碼和基于路徑編碼?；趨^(qū)間編碼是利用每一個元素在原XML文檔中字典順序位置給每一個結(jié)點賦予唯一編碼,；基于路徑編碼利用XML文檔嵌套關(guān)系，給從XML文檔根節(jié)點開始到達(dá)的每一個路徑元素結(jié)點賦予唯一編碼[5],。以上編碼方案雖各自有其優(yōu)點,，但不能有效地支持XML數(shù)據(jù)查詢，尤其對于部分匹配復(fù)雜查詢,。因此本文采用擴(kuò)展的哈弗曼前綴編碼方案,，在保持XML文檔位置關(guān)系特性同時，優(yōu)化XML數(shù)據(jù)查詢,，提高查詢效率,。圖1為企業(yè)生產(chǎn)線上部分XML文檔片段。

　哈弗曼編碼技術(shù)是對二叉樹的結(jié)點進(jìn)行編碼,，即右子樹的根結(jié)點編碼為1,，左子樹的根結(jié)點編碼為0，從而確定結(jié)點之間的關(guān)系,。但是XML文檔樹并不局限于二叉樹,，其分支是隨意的，因此需要對哈弗曼前綴編碼技術(shù)擴(kuò)展,。
　擴(kuò)展的哈弗曼前綴編碼對于元素和屬性所對應(yīng)的內(nèi)容結(jié)點,，不對其進(jìn)行編碼,；其中任何結(jié)點編碼都由該節(jié)點父結(jié)點編碼和該結(jié)點順序碼組成，并且采用十進(jìn)制編碼方式,。對XML文檔樹從根結(jié)點以1開始編碼,；每個結(jié)點的孩子結(jié)點按順序從1，2,，3…8,，9開始，依次遞增,、依次類推,。這種編碼方案不僅能夠保存XML文檔中節(jié)點間包含關(guān)系，如雙親/孩子,，祖先/后裔,，也保存了結(jié)點之間的位置關(guān)系，如左/右兄弟結(jié)點,。對于這種編碼方法,，當(dāng)判斷一個結(jié)點v是否為另一個結(jié)點u的后裔，只需判斷結(jié)點編碼Node（u）是否是Node（v）的前綴字符,，因此,，這種編碼方式能夠有效地支持文檔位置關(guān)系計算，也能支持包含關(guān)系的計算,。
具體算法步驟：
?。?）輸入XML文檔生成DOM樹；
?。?）對根節(jié)點進(jìn)行編碼為“1”,，根元素入隊列；
?。?）判斷隊列是否為空,，否則退出循環(huán)；
?。?）從隊列中取結(jié)點p,，從左到右依次遍歷孩子結(jié)點；
?。?）當(dāng)訪問p的孩子結(jié)點非內(nèi)容結(jié)點進(jìn)行哈弗曼前綴編碼,，并入隊列操作，返回步驟（3）,。
　當(dāng)執(zhí)行算法完畢,，XML文檔樹所有非內(nèi)容結(jié)點編碼完成，圖2是由圖1轉(zhuǎn)換的擴(kuò)展哈弗曼前綴編碼,。

　
2.3 XML數(shù)據(jù)存儲結(jié)構(gòu)
　XML文檔與關(guān)系數(shù)據(jù)庫映射是基于DOM樹構(gòu)建的數(shù)據(jù)模型,，將整個XML文檔看作一個樹結(jié)構(gòu)DOM樹,，樹中結(jié)點即為XML元素、屬性和文本等,，對DOM樹進(jìn)行遍歷，給XML文檔結(jié)點（元素和屬性）賦予惟一擴(kuò)展哈弗曼前綴編碼,，所對應(yīng)的內(nèi)容結(jié)點不對其進(jìn)行編碼,。關(guān)系模式設(shè)置兩個基本表，Path表用于存儲文檔本身的結(jié)構(gòu)信息,，Node表存儲文檔本身的內(nèi)容信息：
?。?）主表Path（Pid，PathInfo,，Nodes）,，保存文檔本身結(jié)構(gòu)路徑信息，如表1所示,。

　Pid路徑編號,，每條路徑都有其唯一編號；PathInfo存儲是XML文檔中的路徑標(biāo)簽,，從XML文檔根結(jié)點到每一個元素或?qū)傩越Y(jié)點上的所有標(biāo)簽,；Nodes記錄同一條標(biāo)簽路徑對應(yīng)的所有結(jié)點路徑。
?。?）從表Node（Nid,，Pid，Node,，Element,，Value），保存文檔本身內(nèi)容信息,，如表2所示,。
Nid是XML文檔中結(jié)點編號；Pid對應(yīng)于Path表Pid字段路徑編號,；Node是XML文檔樹中結(jié)點編碼,；Element保存XML文檔中結(jié)點的元素名或?qū)傩裕籚alue保存XML文檔中葉子屬性結(jié)點的內(nèi)容值,，如果為非葉子結(jié)點的話,，則相應(yīng)的Value值為null。
3 查詢過程優(yōu)化
　基于關(guān)系存儲的XML查詢最終都要將XML查詢轉(zhuǎn)化為SQL查詢,，由于Path表中記錄數(shù)變化不大,，而Node表保存每個結(jié)點內(nèi)容信息，企業(yè)生產(chǎn)線上XML文檔資源很多,，導(dǎo)致Node表記錄冗長,。為提高查詢效率,，首先在Node表Pid字段上建立索引，并在查詢時使用最長前綴匹配方法,，即首先將復(fù)雜查詢分解為限制分支子查詢和主子查詢,，并分別得到其查詢編碼結(jié)果集，使用限制分支子查詢得到編碼同主子查詢得到編碼集進(jìn)行比較,，僅保留與限制分支子查詢擁有公共前綴編碼最長的結(jié)點,，這樣可以得到符合查詢的目標(biāo)編碼集。
為獲取擁有最長公共前綴編碼集,，在SQL SERVER中定義標(biāo)量值函數(shù)：CheckString（@Sql nvarchar（100）,，@Str nvarchar（2），@Split nvarchar（30））此函數(shù)是獲取擁有最長公共前綴目標(biāo)編碼集的重要函數(shù),，其返回值是以逗號分隔的編碼集字符串,；并定義fn_getArray（@inStr1 nvarchar（100），@inStr2 nvarchar（100））是獲取兩字符串公共前綴標(biāo)量值函數(shù),，其返回值是公共前綴,；定義fn_Split（@Sql nvarchar（100），@Str nvarchar（2））是按照@Str分解字符串,，返回值是分解后的Table類型虛擬表,。
　針對XML數(shù)據(jù)查詢有很多種查詢語言，XML查詢核心是XPath路徑表達(dá)式查詢,，按照查詢過程的復(fù)雜程度,，針對查詢路徑表達(dá)式，可以分為三類[6]：
　查詢1：簡單查詢
　只含有雙親/子女關(guān)系或祖先/后裔關(guān)系的路徑查詢,，如：/productCase/Product/Plate,，就是按照路徑選出相應(yīng)信息，對應(yīng)SQL查詢：
　SELECT B.Nid,，B.Value FROM Path as A,，Node as B
WHERE A.PathInfo like‘/productCase/Product/Plate’and A.Pid=B.Pid
　查詢2：分支查詢
　帶有分支謂詞的路徑查詢，如：//Fault[/FaultType=‘遙控不良’]/FaultCause
在分支謂詞出現(xiàn)的地方將表達(dá)式拆分為兩個子查詢Q1（限制分支查詢）：//Fault/FaultType=‘遙控不良’和Q2（主查詢）：//Fault/FaultCause,，執(zhí)行Q1得到限制分支結(jié)點{1141}和主結(jié)點集{1142,，1242}，利用限制分支結(jié)點對主結(jié)點集作最長公共前綴匹配,，得到擁有最長前綴編碼目標(biāo)結(jié)點{1142},，得其內(nèi)容信息{V707}，對應(yīng)的SQL查詢：
　SELECT A.Short,，B.Value
    FROM（SELECT Short FROM dbo.[fn_Split]（
   （SELECT dbo.[CheckString]（T.nos,，‘，’，S.no）
     FROM（SELECT Path.Nodes as nos FROM Path
WHERE Path.PathInfo like‘%/Fault/FaultCause’）as T,，
      （SELECT Path.Nodes as no FROM Path,，Node
WHERE Path.PathInfo like‘%/Fault/FaultType’AND Node.Value=‘遙控不良’
       AND Path.Pid= Node.Pid）as S），‘,，’））as A
Node as B WHERE A.Short=B.Node
　查詢3：通配符查詢
　包含通配符的路徑查詢,，如：/ProductCase/*/FaultType
　在通配符出現(xiàn)的地方將表達(dá)式拆分為兩個子查詢，Q1（限制分支查詢）：/ProductCase和Q2（主查詢）：/ProductCase//FaultType,，執(zhí)行Q1得到編碼{1},，執(zhí)行Q2得到編碼集{1141，1241},，這兩個編碼都是擁有最長前綴編碼的結(jié)點,，因此目標(biāo)結(jié)點是{1141,，1241},，可得其內(nèi)容信息{‘遙控不良’，‘分量異常’}對應(yīng)的SQL查詢：
　SELECT A.Short,，B.Value
　FROM（SELECT Short FROM dbo.[fn_Split]（
?。⊿ELECT dbo.[CheckString]（T.nos，’,，’,，S.no）
　FROM（SELECT Path.Nodes as nos FROM Path
　WHERE Path.PathInfo like‘/ProductCase%/FaultType’）as T，
?。⊿ELECT Path.Nodes as no FROM Path
　WHERE Path.PathInfo like‘/ProductCase’）as S）,，‘，’））as A,，
　Node as B WHERE A.Short=B.Node
　三類查詢中,，簡單查詢不涉及使用最長前綴匹配策略；而分支查詢,、通配符查詢時需進(jìn)行子查詢分解,，再用最長前綴匹配策略進(jìn)行查詢優(yōu)化，此時,，查詢效率要優(yōu)于常采用的XRel[7]方法,。
　隨著互聯(lián)網(wǎng)發(fā)展，XML正發(fā)揮著越來越重要的作用,，使用關(guān)系數(shù)據(jù)庫的成熟技術(shù)來處理XML文檔成為研究的熱點,。由于XML半結(jié)構(gòu)化數(shù)據(jù)本身特征與關(guān)系數(shù)據(jù)庫中結(jié)構(gòu)化數(shù)據(jù)具有不匹配性，如何解決XML數(shù)據(jù)到關(guān)系數(shù)據(jù)庫映射是重點,。本文使用擴(kuò)展哈弗曼前綴編碼的模型映射方法,，實現(xiàn)XML數(shù)據(jù)與關(guān)系數(shù)據(jù)庫的映射，這種方法很好地保存XML文檔中結(jié)點間位置關(guān)系，采用最長前綴匹配策略,，更好地支持?jǐn)?shù)據(jù)查詢策略,，提高了查詢效率。
　本文的研究實驗基于特定的項目所涉及的數(shù)據(jù),，因此難免有一定的局限性,，對于推廣應(yīng)用還需進(jìn)一步研究。
參考文獻(xiàn)
[1] 孟小峰.XML數(shù)據(jù)管理概念與技術(shù)[M].北京：清華大學(xué)出版社,，2009.
[2] 吳潔.XML應(yīng)用教程[M].北京：清華大學(xué)出版社,，2007.
[3] 潘順，金遠(yuǎn)平.半結(jié)構(gòu)化數(shù)據(jù)到結(jié)構(gòu)化數(shù)據(jù)的模式抽取[J].計算機(jī)工程,，2002（5）：55-57.
[4] 付靈麗.XML與關(guān)系數(shù)據(jù)庫實現(xiàn)轉(zhuǎn)換初探[J].河北工業(yè)大學(xué)成人教育學(xué)報,，2007（1）：33-36.
[5] 謝桂芳.XML文檔編碼方案研究[J].科學(xué)技術(shù)與工程，2009（5）：1294-1297.
[6] 王燕麗.基于XML的半結(jié)構(gòu)化數(shù)據(jù)存儲研究[D].山東：山東科技大學(xué),，2008.
[7] YOSHIKAWA M,， SHIMURA T， UEMURA S. Xrel： A Path-Based approach to storage and retrieval of XML documents using relational database[C]. ACM TOIT,，1（1）,，2001.