基于前綴編碼的模型映射改進方法研究

孫天翔

[摘要]提出基于前綴編碼的模型映射改進方法，實現XML半結構化數據到關系數據庫的映射，從而為將半結構化數據管理轉化為傳統關系數據庫管理奠定基礎。

[關鍵詞]半結構化數據 關系數據庫 XML 前綴編碼

中圖分類號：TP3 文獻標識碼：A 文章編號：1671－7597（2009）0120057－01

一、引言

互聯網上存在著各種形式的數據，其數據結構的組織方式也各不相同，因此，半結構化數據模型應運而生，其無模式及自描述的特點適宜于描述網上數據。但傳統的數據庫管理系統主要用于管理結構化的數據，半結構化數據與傳統的數據庫管理系統的模式有很大不同。如何對半結構化數據實施有效的管理成為新的研究領域。

二、半結構化數據的描述

（一）XML半結構數據

Internet的發展使XML成為互聯網上數據交換或數據瀏覽的轉換媒介，XML數據屬于半結構數據模型。專用的半結構化數據管理系統目前仍處于初步實驗階段。但是可行的方法是將半結構化數據轉化為結構化數據，采用關系數據庫對XML數據進行存儲和操作。這樣才有可能把Web上海量的半結構化信息結構化，進行統一的管理、控制和操作。

（二）半結構化數據的描述

目前對半結構化數據的自動抽取、數據模型、查詢語言等一種常見的描述方法的模型是OEM模型[1]。OEM模型由表示對象的結點和帶標簽的有向邊構成的圖。在OEM模型中所有的實體均為對象，每個對象用一個四元組來表示：(ID,LBL, type, value)。其中LBL是對象的標簽描述，type是對象類型。OEM模型可以用一個帶根有向圖G(r,V,E)來表示，其中r表示根節點；V表示對象集；E是有向邊的集合，邊上的標簽表示對象之間的關系，記作，他表示對象I通過標簽為L的邊指向另一個對象J。每一個圖都有一個對應的存儲表示方法，鄰接矩陣和鄰接表是圖的兩種最常用的存儲結構。OEM模型是一個有向圖，于是就可以采用有向圖的存儲表示方法來表示OEM模型。

三、XML半結構化數據到關系數據庫的映射

隨著XML技術的出現和對XML技術的深入研究，半結構化數據和XML數據模型之間的對應關系越來越明顯，因而把XML數據到關系數據庫的映射為是至關重要的一步。

（一）XML文檔編碼

XML文檔可以被描述為樹模型，文檔中的元素、屬性和值對應于樹模型中的結點，其中屬性用@前綴區別，文檔中元素與元素、元素與結點以及元素與值對應于樹模型中的邊。

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

（二）XML文檔存儲結構

對XML文檔樹編碼工作完成之后，設計若干關系來存儲XML文檔樹中的結點信息、結點值信息和結構信息。本文使用三個表來存儲XML文檔，存儲XML文檔的關系存儲模式如下所示：

Document (DocID, XMLDoc)

Code_Path (DocID, Code, Pathexp)

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

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

（三）XML查詢

基于關系存儲的XML查詢最終都要將XML查詢轉化為SQL查詢，并將SQL查詢得到的平坦表形式的結果再轉化為XML文檔返回給用戶或應用。但是XML查詢語言比SQL要復雜得多，它們一般通過路徑表達式來對XML文檔中的嵌套結構進行查詢，而且路徑表達式中可以包含各種查詢軸和謂詞，謂詞中又可以包含路徑表達式、操作符和函數等。轉換XML查詢為SQL查詢對于基于關系的XML數據庫的發展前途起到決定性的作用。

XPath是一個XML查詢語言，它用來描述在一個XML文檔樹中的查詢導航。

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

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

四、小結

本文結合現有的OEM模型，通過對OEM模型圖的遍歷，把OEM模型所對應的圖結構轉換為相應的XML文檔，生成XML數據，實現半結構化數據向XML文檔的映射。基于所生成的XML文檔，通過分析XML文檔和數據庫技術的相互映射方法，采用一種基于前綴編碼的模型映射方法，實現XML數據和數據庫的映射。

參考文獻：

[1]蒙德龍等.半結構化數據的模式抽取[J].計算機工程與應用,2006(27):16

2-165.

[2]魯明羽等.基于OEM模型的半結構化數據的模式抽取[J].清華大學學報（自然科學版）,2004年第44卷第9期:1264-1267.

[3]吳共慶等.一種基于XML的半結構化數據存儲方法[J].計算機工程,2004年5月第30卷第10期:57-59.