基于索引的XML數(shù)據(jù)庫的優(yōu)化研究

涂海燕 鄒云松 賴祥

摘 要 本文基于Native XML數(shù)據(jù)庫的特性，提出了一種自適應(yīng)的優(yōu)化索引方法，該方法能夠根據(jù)XML數(shù)據(jù)文件的特點，結(jié)合ISP原理實現(xiàn)自動優(yōu)化的KeyX索引。實驗結(jié)果表明，它能有效地實時優(yōu)化索引，保證XML數(shù)據(jù)庫持續(xù)高效運行。

關(guān)鍵詞 Native XML數(shù)據(jù)庫 KeyX索引 ISP原理

中圖分類號：TP311.131 文獻(xiàn)標(biāo)識碼：A

Optimization of the XML Database Based on Index

TU Haiyan, ZOU Yunsong, LAI Xiang

(Military and Economics College, Wuhan, Hubei 430035)

Abstract Based on the characteristics of Native XML Database, an adaptive optimal indexing methods, the method according to the characteristics of XML data files, combined with the the ISP principle of automatic optimization KeyX index. The experimental results show that it can effectively real-time optimization of the index, to ensure that the XML database continued efficient operation.

Key words Native XML database; KeyX index; ISP principle

0 引言

Native XML數(shù)據(jù)庫（Native Xml Database）是為XML數(shù)據(jù)量身定做的數(shù)據(jù)庫，能在XML數(shù)據(jù)爆炸式增長時，對數(shù)據(jù)有效存儲、查詢和管理。Native XML數(shù)據(jù)庫充分考慮到XML數(shù)據(jù)的特點，以一種自然的方式來處理XML數(shù)據(jù)，能夠從各個方面很好的支持XML的存儲和查詢。它是現(xiàn)在唯一的純XML數(shù)據(jù)庫，應(yīng)用十分廣泛。

當(dāng)XML數(shù)據(jù)比較龐大時，查詢變得相當(dāng)耗時，因此使用索引來加速查詢十分必要。一般的Native XML數(shù)據(jù)庫主要使用值索引、節(jié)點名索引、邊或路徑索引，其中值索引應(yīng)用最為廣泛。本文使用的KeyX索引是最新提出的值索引類型，它能提供通配符、多路徑、范圍查找等其它值索引類型所不具備的功能，該索引已開始逐步引入實際應(yīng)用，并在不斷地完善之中。通常情況下，數(shù)據(jù)庫的索引是在開發(fā)階段設(shè)計完成的，不能滿足此后數(shù)據(jù)庫的擴(kuò)展需求，在XML數(shù)據(jù)庫中尤為突出，所以對索引進(jìn)行優(yōu)化是非常有必要的。本文使用ISP（Index Selection Problem）原理對索引進(jìn)行實時自動優(yōu)化，保證XML數(shù)據(jù)庫持續(xù)高效運行。

1 Native Xml數(shù)據(jù)庫索引KeyX

KeyX是一種為Native XML 數(shù)據(jù)庫量身訂做的XML索引結(jié)構(gòu)，KeyX還能夠提供通配符、多路徑、范圍查找等其它值索引結(jié)構(gòu)所不具備的功能。對一組頻繁使用的查詢表達(dá)式，從其查詢的原XML數(shù)據(jù)中提取相關(guān)關(guān)鍵詞，并將其存儲在一個經(jīng)過優(yōu)化的搜索結(jié)構(gòu)中，以便于以后能對關(guān)鍵詞進(jìn)行高效的檢索，這些搜索結(jié)構(gòu)包括哈希表、Tries、B+Tree等。

創(chuàng)建索引的過程如下。XPath表達(dá)式： = // [ = ]，將所有author的內(nèi)容與對比，并將所有在路徑///中的author元素作為關(guān)鍵詞從XML數(shù)據(jù)中提取出來。每一個關(guān)鍵詞都和XML數(shù)據(jù)中的一個或多個節(jié)點（元素或?qū)傩裕┯嘘P(guān)。實驗結(jié)果表明，KeyX將XML數(shù)據(jù)查詢速度提高了105~106倍，并且隨著XML數(shù)據(jù)量的增大，加速能力將更強。

2 利用ISP原理優(yōu)化Native Xml數(shù)據(jù)庫索引

定義合適的索引對優(yōu)化數(shù)據(jù)庫非常必要。為使索引能滿足日后數(shù)據(jù)庫擴(kuò)展的需要，本文使用了ISP原理進(jìn)行優(yōu)化。所有的數(shù)據(jù)庫操作都將以包的形式記錄下來，即工作量workload，記為，每次對XML數(shù)據(jù)庫的操作（operation,= ）所使用的路徑表達(dá)式，被查詢優(yōu)化器定義為一組“備選索引”，這些“備選索引”能夠有效地加速對數(shù)據(jù)庫的操作。

與一般索引結(jié)構(gòu)不同的是，“備選索引”不是由編碼而來的，它是由查詢優(yōu)化器提取出來。表達(dá)式具有三種類型：第一種由關(guān)鍵詞和路徑組成，記為，如//，這種類型使用最多；第二種是帶通配符的路徑，記為，如//*；第三種由純路徑組成，記為，如//。在使用中根據(jù)實際需要選取提取方法。

由于工作量是由索引決定的，所以我們在考察時，只需分析所有的索引即可，記（Total Index Candidate） = ，由所有和工作量相關(guān)的索引組成。

當(dāng)對數(shù)據(jù)庫進(jìn)行操作時，中的特定索引被激活，稱此動作為索引配置（index configuration），記為，記所有可能的索引配置集合為。每次激活索引，累積組合將導(dǎo)致新的索引配置，根據(jù)ISP復(fù)雜度定義可得，|| = 2||。

由ISP原理：

(1)（下轉(zhuǎn)第139頁）（上接第122頁）

其中為經(jīng)ISP優(yōu)化的索引配置，為每次進(jìn)行操作所需的時間，為進(jìn)行操作所需的存儲空間（包括內(nèi)存）。

并非所有索引配置都直接在數(shù)據(jù)庫管理系統(tǒng)中創(chuàng)建，查詢優(yōu)化器需要根據(jù)XML數(shù)據(jù)中的相關(guān)關(guān)鍵詞來預(yù)估時間和空間的需求，再由ISP在數(shù)據(jù)庫管理系統(tǒng)中創(chuàng)建索引。

3 Native XML數(shù)據(jù)庫索引優(yōu)化實驗結(jié)果及分析

本文建立的操作模型如圖1所示。其中XDBMS使用Native XDBMS Infoyte DB V3，用來存儲XML數(shù)據(jù)，Infoyte DB 內(nèi)嵌了一個XPath查詢引擎，通過查詢優(yōu)化器調(diào)用。當(dāng)一個操作需求到來后，查詢優(yōu)化器對此操作進(jìn)行處理，預(yù)估查詢表達(dá)式并在KeyX索引存儲器中檢查是否有合適的索引，如果存在，就根據(jù)索引來加速查詢；如果不存在，則轉(zhuǎn)到XPath引擎處理。在實驗中我們使用B+樹作為KeyX索引存儲器里的搜索樹。索引選擇工具（Index Selection Tool, ISP Tool）在數(shù)據(jù)庫操作期間會被周期性的觸發(fā)，然后根據(jù)操作需求找到一個盡可能好的索引配置。計算此操作的工作量并交由ISP Tool和查詢優(yōu)化器建立通信，由兩者共同決定查詢表達(dá)式以及假設(shè)的索引配置。經(jīng)過此計算和優(yōu)化過程后，查詢優(yōu)化器將此索引存儲到KeyX索引存儲器中。

圖1 Native XML數(shù)據(jù)庫索引優(yōu)化實驗?zāi)Ｐ?/p>

實驗中，我們使用的XML文檔大小為26M，包含58萬個節(jié)點，實驗用計算機配置：CPU C4 2.4G/內(nèi)存512M/硬盤80G。軟件平臺：Visual C#， Native XDBMS Infoyte DB V3。建立了27個不同的基于XPath的數(shù)據(jù)庫操作，為每一個表達(dá)式提供了一個備選索引，在初始化階段，我們隨機選擇其中25個數(shù)據(jù)庫操作。通常情況下，有些操作可能會被多次選中，有的則可能一次都未被選中。另外，每一個操作可能會通過預(yù)先定義的優(yōu)化比進(jìn)行修改。為進(jìn)一步測試該系統(tǒng)的自適應(yīng)優(yōu)化特性，在程序持續(xù)運行當(dāng)中，我們通過一個delta算法創(chuàng)建一個XPath查詢，并將其與原27個操作的其中一個進(jìn)行替換，保持27個操作總數(shù)不變。delta算法進(jìn)行的操作能保證整個工作量較小地、隨機地變化，這個算法能對現(xiàn)實數(shù)據(jù)庫操作進(jìn)行模擬。由于每次工作量變化微小，我們每進(jìn)行30次數(shù)據(jù)庫操作后調(diào)用一次ISP Tool。在實際應(yīng)用中可根據(jù)需要將參數(shù)ispFrequency進(jìn)行調(diào)整。

實驗結(jié)果證明本文提出的方法能有效地自適應(yīng)優(yōu)化XML數(shù)據(jù)查詢，不再需要人工定義和維護(hù)索引，在設(shè)計XML文檔時也不需要使用DTD或XML Schema定義格式，而是通過系統(tǒng)的自適應(yīng)、自優(yōu)化功能完成索引的維護(hù)。應(yīng)用于Native XML數(shù)據(jù)庫索引類型較多，盡管本文僅對提出的KeyX索引進(jìn)行了優(yōu)化研究，但本文的方法也可推廣到其它類型索引的優(yōu)化之中。

參考文獻(xiàn)

[1] B. C. Hammerschmidt, M. Kempa, and V. Linnermann. A selective key-oriented xml index for the index selection problem in xdbms. Proceedings of the 15th International Conference on Database and Expert Systems Applications - DEXA 04. 2005

[2] IBM Corporation. IBM DB2 XML Extender. URL: http://www-3.ibm.com/software/data/db2/extenders/xmlext/.

[3] Infonyte GmbH. InfoNyte DB. URL: http://www.infonyte.com.

[4] 萬常選.XML數(shù)據(jù)庫技術(shù).北京:清華大學(xué)出版社,2005.

[5] 向科峰,鄭曉莉.基于TPR樹的索引技術(shù)研究.電腦知識與技術(shù),2005(36).

[6] 陳婕.基于XML的數(shù)據(jù)庫統(tǒng)一的研究.硅谷,2008(11).

[7] 袁正午,程淼.時空數(shù)據(jù)庫查詢研究（英文）.重慶郵電學(xué)院學(xué)報(自然科學(xué)版),2006(4).