XML壓縮數(shù)據(jù)庫的查詢優(yōu)化

本文首先在ETA代數(shù)中引入解壓縮操作，將原代數(shù)擴展到XML壓縮數(shù)據(jù)庫領(lǐng)域。提出了一個新的基于代價估計的查詢優(yōu)化算法，該算法采用動態(tài)編程技術(shù)，對三種解壓縮策略皆適用。

【關(guān)鍵詞】XML數(shù)據(jù)庫 壓縮數(shù)據(jù)庫 查詢優(yōu)化 瞬時解壓縮

1 引言

隨著互聯(lián)網(wǎng)的快速普及和使用互聯(lián)網(wǎng)已經(jīng)誕生了許多以XML為典型代表的相關(guān)邏輯業(yè)務(wù)數(shù)據(jù)，這些數(shù)據(jù)與文本數(shù)據(jù)、關(guān)系數(shù)據(jù)、視頻數(shù)據(jù)、語音數(shù)據(jù)進行比較過程中，這些數(shù)據(jù)均具有更多的復(fù)雜關(guān)系，支持了更多的互聯(lián)網(wǎng)運行和發(fā)展，同時XML數(shù)據(jù)也面臨著更多、更大的挑戰(zhàn)。目前，為了能夠提高數(shù)據(jù)解壓縮的效率，人們經(jīng)過多年的應(yīng)用和研究，已經(jīng)提出了三個關(guān)鍵的解壓縮策略，分別是先解壓策略、后解壓策略、瞬時解壓策略。數(shù)據(jù)解壓操作過程中，如何從數(shù)據(jù)壓縮的三種策略中選擇一個，是非常困難的，主要原因包括兩個關(guān)鍵方面：一是如果采用瞬時壓縮策略，字符型數(shù)據(jù)屬性的解壓縮策略就可以大大的提高I/O開銷，這是因為字符型屬性的數(shù)據(jù)都通常長于數(shù)字型數(shù)據(jù)，同時字符型屬性數(shù)據(jù)更容易進行解壓縮；二是字符型屬性的解壓縮操作起來通常耗費更多的解壓縮代價。

2 壓縮操作符

壓縮數(shù)據(jù)庫的查詢操作主要包括兩個關(guān)鍵內(nèi)容，為了更加充分的驗證本文算法的類型，針對這兩個類型進行舉例操作，在ETA代數(shù)查詢優(yōu)化操作的基礎(chǔ)上引入相關(guān)的XML解壓縮操作。假設(shè)存在一個良好的數(shù)據(jù)庫D及相關(guān)的查詢事務(wù)Q，查詢事務(wù)Q包括一個查詢計劃，這個查詢計劃可以使用一個注釋樹進行描述和表示，行為符號是（V，E）操作內(nèi)容，其中V可以描述注釋樹的結(jié)點，E可以描述注釋樹的邊，因此這個E就可以使用結(jié)點V之間的聯(lián)系，因此可以獲取EV×V。內(nèi)部節(jié)點可以描述壓縮數(shù)據(jù)庫查詢操作的實例，葉子結(jié)點可以描述事務(wù)數(shù)據(jù)庫中的相關(guān)數(shù)據(jù)集內(nèi)容，如果可以形式化描述一條邊從子結(jié)點v1，...，vk到父結(jié)點v，表示操作v1，...，vk的輸出是操作v的輸入。壓縮數(shù)據(jù)庫查詢事務(wù)計劃包括兩個關(guān)鍵部分，分別是語法樹，其中語法樹也有一個結(jié)點集合V和E邊集合，EV×V；查詢事務(wù)計劃可以描述相關(guān)的tag，tag可以實現(xiàn)一個函數(shù)操作描述流程v∈V到tag（v）的映射，v的操作結(jié)果可以保持一個更好的壓縮樹操作狀態(tài)，語法樹與以前是相同的，在此基礎(chǔ)上，我們引入壓縮操作和tag標識。每個結(jié)點的tag表示該操作的輸出數(shù)據(jù)集中保持壓縮狀態(tài)的元素。

3 查詢優(yōu)化算法

我們基于動態(tài)編程技術(shù)實現(xiàn)一個查詢優(yōu)化算法，動態(tài)編程技術(shù)常見于在左深度查詢計劃空間中找到最佳查詢計劃。利用動態(tài)程序設(shè)計算法可以查找最優(yōu)的查詢計劃，這個查詢計劃表達操作過程簡單，因此在查詢操作過程中僅僅考慮數(shù)據(jù)庫連接操作，這樣就可以更好的將其擴展到其他的數(shù)據(jù)庫事務(wù)查詢計劃中，如圖1所示。

與傳統(tǒng)的System R數(shù)據(jù)庫事務(wù)查詢優(yōu)化器進行比較分析，每一個連接操作的中間結(jié)果S可以輸出相關(guān)的元素tag操作，并且可以利用這個元素tag操作建立一個最優(yōu)化的查詢計劃。每一個查詢計劃都可以加入tag符號，以便能夠顯著的確定解壓縮操作的執(zhí)行位置，算法針對每一個數(shù)據(jù)庫內(nèi)容進行連接操作，連接操作的次序可以使用程序偽代碼的第三行和第五行進行描述，并且可以針對每一個列舉的查詢計劃進行分析tag類型，這些tag操作類型具有重要的作用和意義，可以存儲當(dāng)前最佳的計劃到OPTPlan中，并且能夠?qū)⑦x取代價置換到最后一個范圍內(nèi)，并且可以為用戶提供最佳的數(shù)據(jù)操作內(nèi)容。數(shù)據(jù)庫操作完成之后，查詢到最后的tag計劃就是一個空集，這個空集可以使用函數(shù)complete_cost（）潛在說明這點。

4 結(jié)論和展望

關(guān)于XML壓縮數(shù)據(jù)庫的研究才剛剛起步，相關(guān)的研究還不多。本章首先在ETA代數(shù)基礎(chǔ)上，提出一個解壓縮操作將ETA代數(shù)擴展到XML壓縮數(shù)據(jù)庫上。然后，提出一個XML壓縮數(shù)據(jù)庫的查詢優(yōu)化算法，該算法基于動態(tài)編程技術(shù)，通過查詢計劃代價估計的比較，并利用剪枝技術(shù)減小查詢計劃的候選空間得到最佳的查詢計劃。在未來的工作中，將通過仿真實驗進一步驗證算法的有效性。

參考文獻

[1]Chen ZY.Building compressed database system.Ph.D.Thesis.New York：Connell University，2002.

[2]孫偉.一種XML代數(shù)及其查詢優(yōu)化方法[J].哈爾濱工程大學(xué)學(xué)報，2007（08）.

[3]高海康，魏祥麗，李華昱.基于區(qū)間編碼的XML數(shù)據(jù)壓縮方法[J].中國科技論文，2015（08）：905-911.

[4]劉明珠，丁亦楠，鄭云非.XML數(shù)據(jù)公交信息查詢優(yōu)化算法及實現(xiàn)[J].哈爾濱理工大學(xué)學(xué)報，2015，20（02）：85-90.

[5]史濤，沈艷霞.XML文檔到關(guān)系型數(shù)據(jù)庫的模型映射方法[J].江南大學(xué)學(xué)報（自然科學(xué)版），2015，14（05）：590-595.

[6]何炎祥，喻濤，陳彥釗，等.物聯(lián)網(wǎng)環(huán)境中數(shù)據(jù)存儲與查詢機制研究[J].計算機科學(xué)，2015，42（03）：185-190.

作者簡介

劉勝軍（1974-），男，安徽省和縣人。計算機專業(yè)碩士，主要研究方向為機器學(xué)習(xí)、數(shù)據(jù)挖掘。

作者單位

安徽中科大國禎信息科技有限責(zé)任公司 安徽省合肥市 230008