擴展哈弗曼前綴編碼實現XML數據與關系數據轉換*

裴 松，武 彤

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

互聯網的迅速發展，使得網上數據不斷增加，這些數據形式不統一，其數據結構的組織方式也各不相同，促使XML半結構化數據成為互聯網上數據交換或數據瀏覽的中間媒介，其無模式及自描述的特點適于描述網上數據，它的出現推動了互聯網在電子商務和企業生產線等多方面的應用。但要想對這種半結構化數據進行有效地管理十分困難，傳統的DBMS主要用于管理結構化數據，半結構化數據與傳統的DBMS管理的數據的模式大不相同，如何對半結構化數據實施有效的管理成為新的研究領域。而在理論和實踐上都非常成熟的關系數據庫使用廣泛，數據處理能力強，查詢性能好，采用關系數據庫對XML數據進行存儲和操作，將半結構化數據轉為結構化數據，通過查詢數據庫來提取、綜合和分析XML數據，充分利用成熟的數據庫技術處理XML數據已成為重要手段[1-2]。

互聯網的發展也使企業中大量信息資源以XML半結構化數據的形式存在，半結構化數據成為企業決策人員獲取、傳播和交換信息的重要途徑。本文基于一個實際的生產項目，主要對企業生產線中XML半結構化數據資源，采用擴展哈弗曼前綴編碼技術轉化為在關系數據庫中存儲，并采用前綴匹配策略實現XML數據查詢，抽取富有意義的數據，為管理部門提供完整的決策支持數據，有助于企業決策者實現其目標。

1 XML與關系數據庫

XML（Extensible Markup Language）用于標記電子文件使其具有結構性的標記語言，可以用來標記數據、定義數據類型。一個XML文檔是由一個根元素和若干個子元素組成，元素用標記來標識和界定，XML可看作是有層次結構的半結構化數據。XML其優勢在于可擴展性強，簡單易懂，不同平臺間的信息交換性好，支持國際化。隨著XML技術越來越被人們認識和了解，其在數據傳輸和數據存儲方面的優越性也逐漸被人們重視起來。

關系數據庫是為存儲和管理結構化數據設計的，采用二維表作為存儲數據的模型，二維表由行和列組成，列用于表示組成數據有效信息屬性，行用于表示一條由各個字段組成的完整數據記錄。表間相關性通過主鍵—外鍵來關聯。

XML文檔是一種典型的半結構化數據[3]，它既能表示關系、對象等結構化數據，也能表示Web半結構化數據。具有層次結構的半結構化數據與扁平的二維表關系模型之間存在固有的不匹配性。如果采用關系數據庫來存儲XML數據，首先要解決如何把XML文檔模式映射為關系模式，即兩個異構模式之間的模式映射。

2 XML數據與關系數據庫轉換

2.1 XML數據與關系數據庫映射方法

目前，基于關系的XML存儲的研究受到國內外研究者的重視，總的來說根據存儲時是否使用XML模式（DTD或XML Schema）可以分為結構映射方法和模型映射方法兩類。

（1）結構映射是與XML模式（DTD或XML schema）相關[4]，即依賴于文檔模式的關系存儲。這種存儲映射策略把XML文檔本身看作是數據庫中的數據區，DTD或者Schema可以看成是數據模式。依賴于文檔模式的關系存儲映射就是把DTD或Schema映射為關系數據庫中的Schema，然后把XML文檔存儲到關系數據庫中。對XML數據中結構化的信息建模時，采用關系數據庫中的主外鍵連接來映射XML樹的父子關系。

（2）模型映射方法維護用來存儲XML文檔的一個固有的模式[4]，其基本的思想是捕捉XML文檔的樹結構。主要特點是將任何數據都放在有固定關系模式的數據庫中，而不考慮XML文檔模式（DTD或XML Schema），其本質是存儲XML文檔本身的結構信息。在模型映射方法中，XML文檔被看做由元素和屬性等結點組成的有向有序的樹或圖，關系模式相當于一個模板，XML在關系數據庫中的存儲按數據庫提供的模板來組織數據。

由于模型映射方法與XML模式 （DTD或XML schema）無關，而企業生產線上XML數據是一種無模式XML數據，更加符合模型映射的特征。本文采用模型映射方法實現映射轉換工作，以便更好地利用關系數據庫成熟技術進行數據管理。

2.2 XML文檔編碼方案

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

圖1 生產線上XML文檔片段

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

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

具體算法步驟：

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

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

（3）判斷隊列是否為空，否則退出循環；

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

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

圖2 擴展哈弗曼前綴編碼

當執行算法完畢，XML文檔樹所有非內容結點編碼完成，圖2是由圖1轉換的擴展哈弗曼前綴編碼。

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

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

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

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

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

2.3 XML數據存儲結構

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

（1）主表Path（Pid，PathInfo，Nodes），保存文檔本身結構路徑信息，如表1所示。

Pid路徑編號，每條路徑都有其唯一編號；PathInfo存儲是XML文檔中的路徑標簽，從XML文檔根結點到每一個元素或屬性結點上的所有標簽；Nodes記錄同一條標簽路徑對應的所有結點路徑。

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

Nid是XML文檔中結點編號；Pid對應于Path表Pid字段路徑編號；Node是XML文檔樹中結點編碼；Element保存XML文檔中結點的元素名或屬性；Value保存XML文檔中葉子屬性結點的內容值，如果為非葉子結點的話，則相應的Value值為null。

表1 Path表

表2 Node表

3 查詢過程優化

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

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

針對XML數據查詢有很多種查詢語言，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

在分支謂詞出現的地方將表達式拆分為兩個子查詢Q1（限制分支查詢）：//Fault/FaultType=‘遙控不良’和Q2（主查詢）：//Fault/FaultCause，執行Q1得到限制分支結點{1141}和主結點集{1142，1242}，利用限制分支結點對主結點集作最長公共前綴匹配，得到擁有最長前綴編碼目標結點{1142}，得其內容信息{V707}，對應的SQL查詢：

查詢3：通配符查詢

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

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

三類查詢中，簡單查詢不涉及使用最長前綴匹配策略；而分支查詢、通配符查詢時需進行子查詢分解，再用最長前綴匹配策略進行查詢優化，此時，查詢效率要優于常采用的XRel[7]方法。

隨著互聯網發展，XML正發揮著越來越重要的作用，使用關系數據庫的成熟技術來處理XML文檔成為研究的熱點。由于XML半結構化數據本身特征與關系數據庫中結構化數據具有不匹配性，如何解決XML數據到關系數據庫映射是重點。本文使用擴展哈弗曼前綴編碼的模型映射方法，實現XML數據與關系數據庫的映射，這種方法很好地保存XML文檔中結點間位置關系，采用最長前綴匹配策略，更好地支持數據查詢策略，提高了查詢效率。

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

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

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

[3]潘順，金遠平.半結構化數據到結構化數據的模式抽取[J].計算機工程，2002（5）：55-57.

[4]付靈麗.XML與關系數據庫實現轉換初探[J].河北工業大學成人教育學報，2007（1）：33-36.

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

[6]王燕麗.基于XML的半結構化數據存儲研究[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.