裴 松，武 彤

（貴州大學 計算機科學與信息學院，貴州 貴陽550025）

互聯(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ù)進行有效地管理十分困難，傳統(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ù)處理能力強，查詢性能好，采用關(guān)系數(shù)據(jù)庫對XML數(shù)據(jù)進行存儲和操作，將半結(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ù)資源，采用擴展哈弗曼前綴編碼技術(shù)轉(zhuǎn)化為在關(guān)系數(shù)據(jù)庫中存儲，并采用前綴匹配策略實現(xiàn)XML數(shù)據(jù)查詢，抽取富有意義的數(shù)據(jù)，為管理部門提供完整的決策支持數(shù)據(jù)，有助于企業(yè)決策者實現(xiàn)其目標。

1 XML與關(guān)系數(shù)據(jù)庫

XML（Extensible Markup Language）用于標記電子文件使其具有結(jié)構(gòu)性的標記語言，可以用來標記數(shù)據(jù)、定義數(shù)據(jù)類型。一個XML文檔是由一個根元素和若干個子元素組成，元素用標記來標識和界定，XML可看作是有層次結(jié)構(gòu)的半結(jié)構(gòu)化數(shù)據(jù)。XML其優(yōu)勢在于可擴展性強，簡單易懂，不同平臺間的信息交換性好，支持國際化。隨著XML技術(shù)越來越被人們認識和了解，其在數(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)系。

（2）模型映射方法維護用來存儲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)系模式相當于一個模板，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ù)進行數(shù)據(jù)管理。

2.2 XML文檔編碼方案

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

圖1 生產(chǎn)線上XML文檔片段

哈弗曼編碼技術(shù)是對二叉樹的結(jié)點進行編碼，即右子樹的根結(jié)點編碼為1，左子樹的根結(jié)點編碼為0，從而確定結(jié)點之間的關(guān)系。但是XML文檔樹并不局限于二叉樹，其分支是隨意的，因此需要對哈弗曼前綴編碼技術(shù)擴展。

擴展的哈弗曼前綴編碼對于元素和屬性所對應(yīng)的內(nèi)容結(jié)點，不對其進行編碼；其中任何結(jié)點編碼都由該節(jié)點父結(jié)點編碼和該結(jié)點順序碼組成，并且采用十進制編碼方式。對XML文檔樹從根結(jié)點以1開始編碼；每個結(jié)點的孩子結(jié)點按順序從1，2，3…8，9開始，依次遞增、依次類推。這種編碼方案不僅能夠保存XML文檔中節(jié)點間包含關(guān)系，如雙親/孩子，祖先/后裔，也保存了結(jié)點之間的位置關(guān)系，如左/右兄弟結(jié)點。對于這種編碼方法，當判斷一個結(jié)點v是否為另一個結(jié)點u的后裔，只需判斷結(jié)點編碼Node（u）是否是Node（v）的前綴字符，因此，這種編碼方式能夠有效地支持文檔位置關(guān)系計算，也能支持包含關(guān)系的計算。

具體算法步驟：

（1）輸入XML文檔生成DOM樹；

（2）對根節(jié)點進行編碼為“1”，根元素入隊列；

（3）判斷隊列是否為空，否則退出循環(huán)；

（4）從隊列中取結(jié)點p，從左到右依次遍歷孩子結(jié)點；

（5）當訪問p的孩子結(jié)點非內(nèi)容結(jié)點進行哈弗曼前綴編碼，并入隊列操作，返回步驟（3）。

圖2 擴展哈弗曼前綴編碼

當執(zhí)行算法完畢，XML文檔樹所有非內(nèi)容結(jié)點編碼完成，圖2是由圖1轉(zhuǎn)換的擴展哈弗曼前綴編碼。

下面說明這種編碼方法的正確性。基本符號說明：

一篇XML文檔可表示為一棵標志樹T=（u，V，∑），其中V是XML結(jié)點的集合，u是樹的根結(jié)點，∑是文檔元素和屬性名稱組成的集合，結(jié)點u的順序碼表示為Sequence（u），結(jié)點u前綴碼表示為Prefix（u），結(jié)點u的編碼表示為Node（u），即Node（u）=Prefix（u）Sequence（u）；

定理 在一棵給定XML文檔樹T=（u，V，∑），T中不存在任何兩個結(jié)點的編碼相同，即數(shù)學表達式：

（?v，u∈V）（v≠u→Node（v）≠Node（u））

證明 對XML樹中的任何結(jié)點v的編碼Node（v）=Prefix（v）Sequence（v），其 中Sequence（v）∈{1，2，3…8，9}，并且{1，2，3…8，9}的元素是一組無前綴的編碼，由于Prefix（v）是結(jié)點v的父結(jié)點編碼，因此，Prefix（v）Sequence（v）是一種正確的編碼方式，可知，在一棵XML文檔樹中不存在兩個編碼相同的結(jié)點。

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樹進行遍歷，給XML文檔結(jié)點（元素和屬性）賦予惟一擴展哈弗曼前綴編碼，所對應(yīng)的內(nèi)容結(jié)點不對其進行編碼。關(guān)系模式設(shè)置兩個基本表，Path表用于存儲文檔本身的結(jié)構(gòu)信息，Node表存儲文檔本身的內(nèi)容信息：

（1）主表Path（Pid，PathInfo，Nodes），保存文檔本身結(jié)構(gòu)路徑信息，如表1所示。

Pid路徑編號，每條路徑都有其唯一編號；PathInfo存儲是XML文檔中的路徑標簽，從XML文檔根結(jié)點到每一個元素或?qū)傩越Y(jié)點上的所有標簽；Nodes記錄同一條標簽路徑對應(yīng)的所有結(jié)點路徑。

（2）從表Node（Nid，Pid，Node，Element，Value），保 存文檔本身內(nèi)容信息，如表2所示。

Nid是XML文檔中結(jié)點編號；Pid對應(yīng)于Path表Pid字段路徑編號；Node是XML文檔樹中結(jié)點編碼；Element保存XML文檔中結(jié)點的元素名或?qū)傩?；Value保存XML文檔中葉子屬性結(jié)點的內(nèi)容值，如果為非葉子結(jié)點的話，則相應(yīng)的Value值為null。

表1 Path表

表2 Node表

3 查詢過程優(yōu)化

基于關(guān)系存儲的XML查詢最終都要將XML查詢轉(zhuǎn)化為SQL查詢，由于Path表中記錄數(shù)變化不大，而Node表保存每個結(jié)點內(nèi)容信息，企業(yè)生產(chǎn)線上XML文檔資源很多，導致Node表記錄冗長。為提高查詢效率，首先在Node表Pid字段上建立索引，并在查詢時使用最長前綴匹配方法，即首先將復雜查詢分解為限制分支子查詢和主子查詢，并分別得到其查詢編碼結(jié)果集，使用限制分支子查詢得到編碼同主子查詢得到編碼集進行比較，僅保留與限制分支子查詢擁有公共前綴編碼最長的結(jié)點，這樣可以得到符合查詢的目標編碼集。

為獲取擁有最長公共前綴編碼集，在SQL SERVER中定義標量值函數(shù)：CheckString（@Sql nvarchar（100），@Str nvarchar（2），@Split nvarchar（30））此函數(shù)是獲取擁有最長公共前綴目標編碼集的重要函數(shù)，其返回值是以逗號分隔的編碼集字符串；并定義fn_getArray（@inStr1 nvarchar（100），@inStr2 nvarchar（100））是獲取兩字符串公共前綴標量值函數(shù)，其返回值是公共前綴；定義fn_Split（@Sql nvarchar（100），@Str nvarchar（2））是按照@Str分解字符串，返回值是分解后的Table類型虛擬表。

針對XML數(shù)據(jù)查詢有很多種查詢語言，XML查詢核心是XPath路徑表達式查詢，按照查詢過程的復雜程度，針對查詢路徑表達式，可以分為三類[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)的地方將表達式拆分為兩個子查詢Q1（限制分支查詢）：//Fault/FaultType=‘遙控不良’和Q2（主查詢）：//Fault/FaultCause，執(zhí)行Q1得到限制分支結(jié)點{1141}和主結(jié)點集{1142，1242}，利用限制分支結(jié)點對主結(jié)點集作最長公共前綴匹配，得到擁有最長前綴編碼目標結(jié)點{1142}，得其內(nèi)容信息{V707}，對應(yīng)的SQL查詢：

查詢3：通配符查詢

包含通配符的路徑查詢，如：/ProductCase/*/FaultType

在通配符出現(xiàn)的地方將表達式拆分為兩個子查詢，Q1（限制分支查詢）：/ProductCase和Q2（主查詢）：/ProductCase//FaultType，執(zhí)行Q1得到編碼{1}，執(zhí)行Q2得到編碼集{1141，1241}，這兩個編碼都是擁有最長前綴編碼的結(jié)點，因此目標結(jié)點是{1141，1241}，可得其內(nèi)容信息{‘遙控不良’，‘分量異?！瘆對應(yīng)的SQL查詢：

三類查詢中，簡單查詢不涉及使用最長前綴匹配策略；而分支查詢、通配符查詢時需進行子查詢分解，再用最長前綴匹配策略進行查詢優(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ù)庫映射是重點。本文使用擴展哈弗曼前綴編碼的模型映射方法，實現(xiàn)XML數(shù)據(jù)與關(guān)系數(shù)據(jù)庫的映射，這種方法很好地保存XML文檔中結(jié)點間位置關(guān)系，采用最長前綴匹配策略，更好地支持數(shù)據(jù)查詢策略，提高了查詢效率。

本文的研究實驗基于特定的項目所涉及的數(shù)據(jù)，因此難免有一定的局限性，對于推廣應(yīng)用還需進一步研究。

[1]孟小峰.XML數(shù)據(jù)管理概念與技術(shù)[M].北京：清華大學出版社，2009.

[2]吳潔.XML應(yīng)用教程[M].北京：清華大學出版社，2007.

[3]潘順，金遠平.半結(jié)構(gòu)化數(shù)據(jù)到結(jié)構(gòu)化數(shù)據(jù)的模式抽取[J].計算機工程，2002（5）：55-57.

[4]付靈麗.XML與關(guān)系數(shù)據(jù)庫實現(xiàn)轉(zhuǎn)換初探[J].河北工業(yè)大學成人教育學報，2007（1）：33-36.

[5]謝桂芳.XML文檔編碼方案研究[J].科學技術(shù)與工程，2009（5）：1294-1297.

[6]王燕麗.基于XML的半結(jié)構(gòu)化數(shù)據(jù)存儲研究[D].山東：山東科技大學，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.