涂海燕 鄒云松 賴祥

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

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

中圖分類號(hào)：TP311.131 文獻(xiàn)標(biāo)識(shí)碼：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ù)庫(kù)（Native Xml Database）是為XML數(shù)據(jù)量身定做的數(shù)據(jù)庫(kù)，能在XML數(shù)據(jù)爆炸式增長(zhǎng)時(shí)，對(duì)數(shù)據(jù)有效存儲(chǔ)、查詢和管理。Native XML數(shù)據(jù)庫(kù)充分考慮到XML數(shù)據(jù)的特點(diǎn)，以一種自然的方式來處理XML數(shù)據(jù)，能夠從各個(gè)方面很好的支持XML的存儲(chǔ)和查詢。它是現(xiàn)在唯一的純XML數(shù)據(jù)庫(kù)，應(yīng)用十分廣泛。

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

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

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

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

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

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

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

由于工作量是由索引決定的，所以我們?cè)诳疾鞎r(shí)，只需分析所有的索引即可，記（Total Index Candidate） = ，由所有和工作量相關(guān)的索引組成。

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

由ISP原理：

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

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

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

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

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

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

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

實(shí)驗(yàn)結(jié)果證明本文提出的方法能有效地自適應(yīng)優(yōu)化XML數(shù)據(jù)查詢，不再需要人工定義和維護(hù)索引，在設(shè)計(jì)XML文檔時(shí)也不需要使用DTD或XML Schema定義格式，而是通過系統(tǒng)的自適應(yīng)、自優(yōu)化功能完成索引的維護(hù)。應(yīng)用于Native XML數(shù)據(jù)庫(kù)索引類型較多，盡管本文僅對(duì)提出的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] 萬(wàn)常選.XML數(shù)據(jù)庫(kù)技術(shù).北京:清華大學(xué)出版社,2005.

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

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

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