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

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

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ù)進(jìn)行比較過程中，這些數(shù)據(jù)均具有更多的復(fù)雜關(guān)系，支持了更多的互聯(lián)網(wǎng)運(yùn)行和發(fā)展，同時(shí)XML數(shù)據(jù)也面臨著更多、更大的挑戰(zhàn)。目前，為了能夠提高數(shù)據(jù)解壓縮的效率，人們經(jīng)過多年的應(yīng)用和研究，已經(jīng)提出了三個(gè)關(guān)鍵的解壓縮策略，分別是先解壓策略、后解壓策略、瞬時(shí)解壓策略。數(shù)據(jù)解壓操作過程中，如何從數(shù)據(jù)壓縮的三種策略中選擇一個(gè)，是非常困難的，主要原因包括兩個(gè)關(guān)鍵方面：一是如果采用瞬時(shí)壓縮策略，字符型數(shù)據(jù)屬性的解壓縮策略就可以大大的提高I/O開銷，這是因?yàn)樽址蛯傩缘臄?shù)據(jù)都通常長(zhǎng)于數(shù)字型數(shù)據(jù)，同時(shí)字符型屬性數(shù)據(jù)更容易進(jìn)行解壓縮；二是字符型屬性的解壓縮操作起來通常耗費(fèi)更多的解壓縮代價(jià)。

2 壓縮操作符

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

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

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

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

4 結(jié)論和展望

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

參考文獻(xiàn)

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

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

[3]高?？担合辂?，李華昱.基于區(qū)間編碼的XML數(shù)據(jù)壓縮方法[J].中國(guó)科技論文，2015（08）：905-911.

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

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

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

作者簡(jiǎn)介

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

作者單位

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