孫天翔

[摘要]提出基于前綴編碼的模型映射改進(jìn)方法，實(shí)現(xiàn)XML半結(jié)構(gòu)化數(shù)據(jù)到關(guān)系數(shù)據(jù)庫(kù)的映射，從而為將半結(jié)構(gòu)化數(shù)據(jù)管理轉(zhuǎn)化為傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)管理奠定基礎(chǔ)。

[關(guān)鍵詞]半結(jié)構(gòu)化數(shù)據(jù) 關(guān)系數(shù)據(jù)庫(kù) XML 前綴編碼

中圖分類號(hào)：TP3 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671－7597（2009）0120057－01

一、引言

互聯(lián)網(wǎng)上存在著各種形式的數(shù)據(jù)，其數(shù)據(jù)結(jié)構(gòu)的組織方式也各不相同，因此，半結(jié)構(gòu)化數(shù)據(jù)模型應(yīng)運(yùn)而生，其無(wú)模式及自描述的特點(diǎn)適宜于描述網(wǎng)上數(shù)據(jù)。但傳統(tǒng)的數(shù)據(jù)庫(kù)管理系統(tǒng)主要用于管理結(jié)構(gòu)化的數(shù)據(jù)，半結(jié)構(gòu)化數(shù)據(jù)與傳統(tǒng)的數(shù)據(jù)庫(kù)管理系統(tǒng)的模式有很大不同。如何對(duì)半結(jié)構(gòu)化數(shù)據(jù)實(shí)施有效的管理成為新的研究領(lǐng)域。

二、半結(jié)構(gòu)化數(shù)據(jù)的描述

（一）XML半結(jié)構(gòu)數(shù)據(jù)

Internet的發(fā)展使XML成為互聯(lián)網(wǎng)上數(shù)據(jù)交換或數(shù)據(jù)瀏覽的轉(zhuǎn)換媒介，XML數(shù)據(jù)屬于半結(jié)構(gòu)數(shù)據(jù)模型。專用的半結(jié)構(gòu)化數(shù)據(jù)管理系統(tǒng)目前仍處于初步實(shí)驗(yàn)階段。但是可行的方法是將半結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)化為結(jié)構(gòu)化數(shù)據(jù)，采用關(guān)系數(shù)據(jù)庫(kù)對(duì)XML數(shù)據(jù)進(jìn)行存儲(chǔ)和操作。這樣才有可能把Web上海量的半結(jié)構(gòu)化信息結(jié)構(gòu)化，進(jìn)行統(tǒng)一的管理、控制和操作。

（二）半結(jié)構(gòu)化數(shù)據(jù)的描述

目前對(duì)半結(jié)構(gòu)化數(shù)據(jù)的自動(dòng)抽取、數(shù)據(jù)模型、查詢語(yǔ)言等一種常見的描述方法的模型是OEM模型[1]。OEM模型由表示對(duì)象的結(jié)點(diǎn)和帶標(biāo)簽的有向邊構(gòu)成的圖。在OEM模型中所有的實(shí)體均為對(duì)象，每個(gè)對(duì)象用一個(gè)四元組來(lái)表示：(ID,LBL, type, value)。其中LBL是對(duì)象的標(biāo)簽描述，type是對(duì)象類型。OEM模型可以用一個(gè)帶根有向圖G(r,V,E)來(lái)表示，其中r表示根節(jié)點(diǎn)；V表示對(duì)象集；E是有向邊的集合，邊上的標(biāo)簽表示對(duì)象之間的關(guān)系，記作，他表示對(duì)象I通過標(biāo)簽為L(zhǎng)的邊指向另一個(gè)對(duì)象J。每一個(gè)圖都有一個(gè)對(duì)應(yīng)的存儲(chǔ)表示方法，鄰接矩陣和鄰接表是圖的兩種最常用的存儲(chǔ)結(jié)構(gòu)。OEM模型是一個(gè)有向圖，于是就可以采用有向圖的存儲(chǔ)表示方法來(lái)表示OEM模型。

三、XML半結(jié)構(gòu)化數(shù)據(jù)到關(guān)系數(shù)據(jù)庫(kù)的映射

隨著XML技術(shù)的出現(xiàn)和對(duì)XML技術(shù)的深入研究，半結(jié)構(gòu)化數(shù)據(jù)和XML數(shù)據(jù)模型之間的對(duì)應(yīng)關(guān)系越來(lái)越明顯，因而把XML數(shù)據(jù)到關(guān)系數(shù)據(jù)庫(kù)的映射為是至關(guān)重要的一步。

（一）XML文檔編碼

XML文檔可以被描述為樹模型，文檔中的元素、屬性和值對(duì)應(yīng)于樹模型中的結(jié)點(diǎn)，其中屬性用@前綴區(qū)別，文檔中元素與元素、元素與結(jié)點(diǎn)以及元素與值對(duì)應(yīng)于樹模型中的邊。

將XML文檔映射為關(guān)系模式存儲(chǔ)，可以通過對(duì)XML文檔樹的結(jié)點(diǎn)進(jìn)行編碼，通過編碼直接判斷結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。編碼方案主要有以下幾種：位向量編碼、區(qū)間編碼、前綴編碼和哈夫曼編碼等。前綴編碼也稱Dewey編碼[2]。前綴編碼直接將一個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編碼作為該結(jié)點(diǎn)編碼的前綴，這種編碼方案保存了文檔的結(jié)構(gòu)信息。對(duì)于前綴編碼，要判斷一個(gè)結(jié)點(diǎn)v是否是另一個(gè)結(jié)點(diǎn)u的后裔，只需判斷字符串c(u)的前綴是否是c(v)的前綴。前綴編碼的一個(gè)重要性質(zhì)是它們的字典有序：以結(jié)點(diǎn)r為根的子樹中的任意一個(gè)結(jié)點(diǎn)u，它的前綴編碼c(u)大于（小于）它的左兄弟子樹（右兄弟子樹）中所有結(jié)點(diǎn)的前綴編碼。因此，前綴編碼不僅能夠有效的支持包含關(guān)系的計(jì)算，而且能夠有效地支持文檔位置的計(jì)算。本文在采用了Dewey編碼的基礎(chǔ)上，對(duì)XML文檔進(jìn)行關(guān)系模式存儲(chǔ)。對(duì)XML文檔樹從根結(jié)點(diǎn)以0開始編碼，作為第一層次的結(jié)點(diǎn)；第二層次的結(jié)點(diǎn)編碼從00，01，02……開始，依次遞增；同理，第三層次的結(jié)點(diǎn)編碼從000，001，002，003……開始，依次遞增，依次類推。但是有一點(diǎn)需要我們注意，如果XML文檔樹的度不超過10，我們可以從0到9數(shù)字進(jìn)行擴(kuò)充，如果XML文檔樹的度超過10則可以用a,b,c等字母依次排列進(jìn)行編碼。

（二）XML文檔存儲(chǔ)結(jié)構(gòu)

對(duì)XML文檔樹編碼工作完成之后，設(shè)計(jì)若干關(guān)系來(lái)存儲(chǔ)XML文檔樹中的結(jié)點(diǎn)信息、結(jié)點(diǎn)值信息和結(jié)構(gòu)信息。本文使用三個(gè)表來(lái)存儲(chǔ)XML文檔，存儲(chǔ)XML文檔的關(guān)系存儲(chǔ)模式如下所示：

Document (DocID, XMLDoc)

Code_Path (DocID, Code, Pathexp)

Element (DocID, Code, Element, flag, value)

其中，Document表用來(lái)存儲(chǔ)XML文檔信息，DocID為XML文檔的代碼，XMLDoc為XML文檔的保存路徑；在Code_Path表中，Code為各結(jié)點(diǎn)對(duì)應(yīng)的編碼，Pathexp為采用路徑方式表達(dá)的結(jié)點(diǎn)位置；在Element表中，Element為結(jié)點(diǎn)的元素名或者是屬性名，flag為結(jié)點(diǎn)元素的類型，結(jié)點(diǎn)類型分為葉結(jié)點(diǎn)和非葉子結(jié)點(diǎn)，葉子結(jié)點(diǎn)類型分別為integer, decimal, string等，但此處在這個(gè)模式映射方法中，論文用0和1來(lái)區(qū)分，也就是說，如果為葉子結(jié)點(diǎn)則為0，否則為1；value為葉子結(jié)點(diǎn)對(duì)應(yīng)的值，如果為非葉子結(jié)點(diǎn)的話，則該值為空。

（三）XML查詢

基于關(guān)系存儲(chǔ)的XML查詢最終都要將XML查詢轉(zhuǎn)化為SQL查詢，并將SQL查詢得到的平坦表形式的結(jié)果再轉(zhuǎn)化為XML文檔返回給用戶或應(yīng)用。但是XML查詢語(yǔ)言比SQL要復(fù)雜得多，它們一般通過路徑表達(dá)式來(lái)對(duì)XML文檔中的嵌套結(jié)構(gòu)進(jìn)行查詢，而且路徑表達(dá)式中可以包含各種查詢軸和謂詞，謂詞中又可以包含路徑表達(dá)式、操作符和函數(shù)等。轉(zhuǎn)換XML查詢?yōu)镾QL查詢對(duì)于基于關(guān)系的XML數(shù)據(jù)庫(kù)的發(fā)展前途起到?jīng)Q定性的作用。

XPath是一個(gè)XML查詢語(yǔ)言，它用來(lái)描述在一個(gè)XML文檔樹中的查詢導(dǎo)航。

XML查詢的核心是XPath路徑表達(dá)式查詢。XPath是文檔之內(nèi)進(jìn)行信息尋址的一種方法，目的在于自動(dòng)化搜索操作，方便編程用戶訪問信息。XML查詢按照復(fù)雜程度分為3類[3]：

簡(jiǎn)單查詢：只含有父子關(guān)系或祖先子孫關(guān)系的路徑查詢；分支查詢：帶有分支謂詞的路徑查詢；帶通配符的查詢：包含通配符的路徑查詢。

四、小結(jié)

本文結(jié)合現(xiàn)有的OEM模型，通過對(duì)OEM模型圖的遍歷，把OEM模型所對(duì)應(yīng)的圖結(jié)構(gòu)轉(zhuǎn)換為相應(yīng)的XML文檔，生成XML數(shù)據(jù)，實(shí)現(xiàn)半結(jié)構(gòu)化數(shù)據(jù)向XML文檔的映射。基于所生成的XML文檔，通過分析XML文檔和數(shù)據(jù)庫(kù)技術(shù)的相互映射方法，采用一種基于前綴編碼的模型映射方法，實(shí)現(xiàn)XML數(shù)據(jù)和數(shù)據(jù)庫(kù)的映射。

參考文獻(xiàn)：

[1]蒙德龍等.半結(jié)構(gòu)化數(shù)據(jù)的模式抽取[J].計(jì)算機(jī)工程與應(yīng)用,2006(27):16

2-165.

[2]魯明羽等.基于OEM模型的半結(jié)構(gòu)化數(shù)據(jù)的模式抽取[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版）,2004年第44卷第9期:1264-1267.

[3]吳共慶等.一種基于XML的半結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)方法[J].計(jì)算機(jī)工程,2004年5月第30卷第10期:57-59.