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

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

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

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

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

　Pid路徑編號，每條路徑都有其唯一編號；PathInfo存儲是XML文檔中的路徑標簽，從XML文檔根結點到每一個元素或屬性結點上的所有標簽；Nodes記錄同一條標簽路徑對應的所有結點路徑。
?。?）從表Node（Nid，Pid，Node，Element，Value），保存文檔本身內容信息，如表2所示。
Nid是XML文檔中結點編號；Pid對應于Path表Pid字段路徑編號；Node是XML文檔樹中結點編碼；Element保存XML文檔中結點的元素名或屬性；Value保存XML文檔中葉子屬性結點的內容值，如果為非葉子結點的話，則相應的Value值為null。
3 查詢過程優(yōu)化
　基于關系存儲的XML查詢最終都要將XML查詢轉化為SQL查詢，由于Path表中記錄數(shù)變化不大，而Node表保存每個結點內容信息，企業(yè)生產(chǎn)線上XML文檔資源很多，導致Node表記錄冗長。為提高查詢效率，首先在Node表Pid字段上建立索引，并在查詢時使用最長前綴匹配方法，即首先將復雜查詢分解為限制分支子查詢和主子查詢，并分別得到其查詢編碼結果集，使用限制分支子查詢得到編碼同主子查詢得到編碼集進行比較，僅保留與限制分支子查詢擁有公共前綴編碼最長的結點，這樣可以得到符合查詢的目標編碼集。
為獲取擁有最長公共前綴編碼集，在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：簡單查詢
　只含有雙親/子女關系或祖先/后裔關系的路徑查詢，如：/productCase/Product/Plate，就是按照路徑選出相應信息，對應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得到限制分支結點{1141}和主結點集{1142，1242}，利用限制分支結點對主結點集作最長公共前綴匹配，得到擁有最長前綴編碼目標結點{1142}，得其內容信息{V707}，對應的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)的地方將表達式拆分為兩個子查詢，Q1（限制分支查詢）：/ProductCase和Q2（主查詢）：/ProductCase//FaultType，執(zhí)行Q1得到編碼{1}，執(zhí)行Q2得到編碼集{1141，1241}，這兩個編碼都是擁有最長前綴編碼的結點，因此目標結點是{1141，1241}，可得其內容信息{‘遙控不良’，‘分量異常’}對應的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
　三類查詢中，簡單查詢不涉及使用最長前綴匹配策略；而分支查詢、通配符查詢時需進行子查詢分解，再用最長前綴匹配策略進行查詢優(yōu)化，此時，查詢效率要優(yōu)于常采用的XRel[7]方法。
　隨著互聯(lián)網(wǎng)發(fā)展，XML正發(fā)揮著越來越重要的作用，使用關系數(shù)據(jù)庫的成熟技術來處理XML文檔成為研究的熱點。由于XML半結構化數(shù)據(jù)本身特征與關系數(shù)據(jù)庫中結構化數(shù)據(jù)具有不匹配性，如何解決XML數(shù)據(jù)到關系數(shù)據(jù)庫映射是重點。本文使用擴展哈弗曼前綴編碼的模型映射方法，實現(xiàn)XML數(shù)據(jù)與關系數(shù)據(jù)庫的映射，這種方法很好地保存XML文檔中結點間位置關系，采用最長前綴匹配策略，更好地支持數(shù)據(jù)查詢策略，提高了查詢效率。
　本文的研究實驗基于特定的項目所涉及的數(shù)據(jù)，因此難免有一定的局限性，對于推廣應用還需進一步研究。
參考文獻
[1] 孟小峰.XML數(shù)據(jù)管理概念與技術[M].北京：清華大學出版社，2009.
[2] 吳潔.XML應用教程[M].北京：清華大學出版社，2007.
[3] 潘順，金遠平.半結構化數(shù)據(jù)到結構化數(shù)據(jù)的模式抽取[J].計算機工程，2002（5）：55-57.
[4] 付靈麗.XML與關系數(shù)據(jù)庫實現(xiàn)轉換初探[J].河北工業(yè)大學成人教育學報，2007（1）：33-36.
[5] 謝桂芳.XML文檔編碼方案研究[J].科學技術與工程，2009（5）：1294-1297.
[6] 王燕麗.基于XML的半結構化數(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.