基于關(guān)系模式下XML大容量文檔查詢方法的研究和實驗*

王曉燕

（太原大學(xué)，山西太原 030009）

XML己經(jīng)成為Internet上數(shù)據(jù)的表示標(biāo)準(zhǔn)和交換工具，然而XML數(shù)據(jù)的一個明顯特征是數(shù)據(jù)冗余較大，冗余既造成了存儲空間的浪費，又增加了查詢處理的時間，降低了效率。目前，減小XML文檔大小的一種有效的方法就是壓縮，但是壓縮后的XML文檔需要解壓后才能對其進行驗證、查詢等操作。

眾所周知，XML獲得廣泛應(yīng)用的關(guān)鍵是XML數(shù)據(jù)資源的查詢與檢索。所以，研究XML數(shù)據(jù)的檢索和查詢自然就成了世界性的熱門課題。

1 索引模塊的設(shè)計

搜索引擎的索引部分是整個搜索引擎最關(guān)鍵的部分，衡量索引的好壞主要看它本身占據(jù)多少額外的磁盤空間和查詢時的檢索速度。在對XML文檔數(shù)據(jù)建立索引時，根據(jù)需要，設(shè)計一個索引模塊，并給出一種新的倒排索引方法。

XML文檔包括結(jié)構(gòu)信息和內(nèi)容信息，這些都要編入索引，把XML文檔看成一棵樹，樹中的節(jié)點作為一個基本的存儲單元，每個節(jié)點有一個唯一的標(biāo)識符，這個標(biāo)識符是由解析模塊中的節(jié)點編碼器分配的，將其簡記為Id，其標(biāo)識符為一個編碼，形式為（start，end）。

XML文檔經(jīng)過節(jié)點編碼器后生成DOM（文檔對象模型）樹，再經(jīng)過節(jié)點結(jié)構(gòu)構(gòu)造器后產(chǎn)生的節(jié)點結(jié)構(gòu)仍是一顆樹，樹的最下一層是葉子節(jié)點，即文本部分，其余都是中間節(jié)點，即結(jié)構(gòu)部分。

索引采用倒排表的方式來實現(xiàn)，本文共設(shè)計了三種索引表。

1.1 文檔結(jié)構(gòu)表

一篇讀入的XML文檔，經(jīng)過節(jié)點結(jié)構(gòu)構(gòu)造器后，解析為一個樹狀結(jié)構(gòu)，索引器首先建立這樣一個表，即文檔結(jié)構(gòu)表，用來存放每篇文檔的結(jié)構(gòu)。

文檔Id即該文檔的編碼，由文檔加入數(shù)據(jù)庫的次序決定，從零開始編碼，表中每個節(jié)點的數(shù)據(jù)結(jié)構(gòu)為節(jié)點結(jié)構(gòu)結(jié)構(gòu)器已經(jīng)構(gòu)造的節(jié)點結(jié)構(gòu)。以先序遍歷的順序存儲文檔樹，遇到Id編碼的兩個值相等的情況不予存儲，即不存儲葉子節(jié)點。

1.2 文檔信息表

文檔的結(jié)構(gòu)索引是用來提高查準(zhǔn)率，體現(xiàn)面向XML文檔索引的優(yōu)勢的，還應(yīng)該有一個表，記錄文檔的一些基本信息，如地址、主題等。

1.3 關(guān)鍵詞索引表

用戶查詢一般情況下都是輸入關(guān)鍵詞，所以關(guān)鍵詞索引表是非常重要的，這部分屬于內(nèi)容索引。將葉子節(jié)點處的文本內(nèi)容進行處理，去掉無意義的詞，提取關(guān)鍵詞。對文檔空間中的所有關(guān)鍵詞，在關(guān)鍵詞索引表中都建立一條相應(yīng)的記錄。這些詞按字母順序存放，可加快查找速度。在關(guān)鍵詞索引表中，每個文檔按與關(guān)鍵詞的相關(guān)度排序記錄，每插入一個新的文檔，也要計算其與關(guān)鍵詞的相關(guān)度，并插入到相應(yīng)的位置。相關(guān)度按照一定的算法算出。

2 利用高頻路徑產(chǎn)生索引機制

高頻路徑的所有子連續(xù)路徑也是高頻路徑，所以要對算法得到的高頻路徑擴展（找出所有高頻路徑的子連續(xù)路徑）以得到全部的高頻路徑。

對文檔庫用路徑查找算法得到的高頻路徑的集合為:

再經(jīng)過擴展得到的所有高頻路徑的集合為:

然后將這些路徑視為一個regular set，通過自動機的轉(zhuǎn)換，產(chǎn)生最小化有限狀態(tài)機（MFA），作為索引構(gòu)造的條件。

3 關(guān)系型數(shù)據(jù)和XML結(jié)構(gòu)轉(zhuǎn)換

XML是層次結(jié)構(gòu)的，它可以對非關(guān)系型的數(shù)據(jù)進行編碼。但是，目前服務(wù)器上維護的數(shù)據(jù)來自關(guān)系型數(shù)據(jù)庫，關(guān)系數(shù)據(jù)庫的基本組成單位是表，這里定義一個映射實現(xiàn)表和XML數(shù)據(jù)文檔之間的轉(zhuǎn)換。

我們可以建立數(shù)據(jù)庫模式（database schema）和XML數(shù)據(jù)模式（xml schema）之間的映射關(guān)系，實現(xiàn)信息的轉(zhuǎn)化。需要注意的是當(dāng)XML文檔不是由數(shù)據(jù)庫中導(dǎo)出，而是由應(yīng)用程序來指定XML文檔的數(shù)據(jù)結(jié)構(gòu)時，從XML數(shù)據(jù)模式映射到數(shù)據(jù)庫模式時存在一些問題:首先是映射到表的時候需要將字段的數(shù)據(jù)類型設(shè)定，DTD文檔無法準(zhǔn)確定義元素的數(shù)據(jù)類型，在引入schema之后可以解決此問題。其次在XML文檔中，大小寫是區(qū)分的，而在數(shù)據(jù)庫中大小寫是不區(qū)分的，假如在XML文檔中存在兩個PCDATA的元素，它們的名稱除了大小寫不同外都一樣，則轉(zhuǎn)換程序會將其轉(zhuǎn)換成兩個字段，這會導(dǎo)致在數(shù)據(jù)庫中錯誤的發(fā)生;另外XML數(shù)據(jù)是有順序的，而數(shù)據(jù)庫中的數(shù)據(jù)是無序結(jié)構(gòu)表達的，辦法之一是添加一個sort字段。

消除查詢表達式中出現(xiàn)的#。一般地，正則表達式E1#E2匹配從E1開始，經(jīng)一條或多條邊到達E2的所有路徑。消除#需遍歷整個映射圖，將映射圖中以E1為起點，E2為終點的子圖轉(zhuǎn)化為與之等價的正則表達式。將一個圖轉(zhuǎn)化為正則表達式的問題是一個已知問題，采用適當(dāng)?shù)乃惴ㄎ覀兛梢詫⒈磉_式中的#部分轉(zhuǎn)化為與之匹配的映射子圖對應(yīng)的正則表達式，從而消除#。

將XML查詢轉(zhuǎn)換為關(guān)系系統(tǒng)中的查詢過程為:首先將XML查詢中的變量消去，把正則路徑表達式重寫為簡單路徑表達式，再將SPE表達式的查詢轉(zhuǎn)化SQL查詢。

4 XML數(shù)據(jù)庫事務(wù)處理和版本控制

XML數(shù)據(jù)庫一般提供事務(wù)處理功能，包括提交、撤回和日志文件，也包含對XML文檔的版本控制功能。

事務(wù)為數(shù)據(jù)庫的一組操作，這些操作組成一個邏輯單元。事務(wù)遵循的ACID性質(zhì)（原子性、一致性、獨立性和持久性），通過提供事務(wù)日志機制，紀(jì)錄系統(tǒng)執(zhí)行的每個事務(wù)的詳細情況，保證事務(wù)處理穩(wěn)定地運行和系統(tǒng)出現(xiàn)問題后完全恢復(fù)。

處于版本控制之下的文檔都有自己的歷史信息，紀(jì)錄修改文檔的作者以及時間等，使用者可以根據(jù)文檔或用戶或日期來查看整個的版本歷史信息。XML數(shù)據(jù)庫版本控制，允許用戶通過查詢更新原信息，用戶應(yīng)用程序可以檢入 或檢出XML文檔，利用版本號、日期或者標(biāo)簽獲得以前版本的文檔，以及顯示XML文檔的版本歷史信息。版本控制允許用戶查詢更新原信息，通過更新引擎注釋、修改和精煉信息。內(nèi)置的版本系統(tǒng)跟蹤信息的變化，提供這些變化的歷史信息。

5 基于XML的路徑查找算法

在XML文檔中，所有的信息都存儲在葉子節(jié)點處。信息的存取是由根節(jié)點沿著某路徑（path）到葉子節(jié)點完成的?？梢园裍ML文檔看作成樹狀結(jié)構(gòu)，節(jié)點間存在一種次序（order）關(guān)系。用搜索連續(xù)路徑的方法，快速檢索出文件中重要的連續(xù)路徑。

XML的路徑查找算法，使用二維Hash table存儲事務(wù)，一邊是含有事務(wù)節(jié)點名稱的hash array，可加快路徑搜索的速度;另一邊是含有事務(wù)長度的length list所構(gòu)成的array，以便在查找時找到當(dāng)前的最長路徑。

［1］吳敏，徐德智，N Damas.基于離散模式的XML數(shù)據(jù)查詢的 CSP 實現(xiàn)［J］.計算機應(yīng)用，2011，23（4）:31-34.

［2］徐德智，H.Sidi..基于樹模型的XML查詢［J］.企業(yè)技術(shù)開發(fā)，2009（4）:7-8.

［3］呂建華，王國仁，于戈.XML數(shù)據(jù)的路徑表達式查詢優(yōu)化技術(shù)［J］.軟件學(xué)報，2010，14（9）:1615-1620.

［4］吳敏，徐德智，陳學(xué)工.XML模式蘊含及查詢優(yōu)化研究［J］.計算機應(yīng)用，2011，11（8）:7-30.

［5］萬常選，劉云生，徐升華，等.基于區(qū)間編碼的XML索引結(jié)構(gòu)的有效結(jié)構(gòu)［J］.計算機學(xué)報，2005（1）:113-127.