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

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

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

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

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