XML壓縮數據庫的查詢優化

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

【關鍵詞】XML數據庫 壓縮數據庫 查詢優化 瞬時解壓縮

1 引言

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

2 壓縮操作符

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

3 查詢優化算法

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

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

4 結論和展望

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

參考文獻

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

[2]孫偉.一種XML代數及其查詢優化方法[J].哈爾濱工程大學學報，2007（08）.

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

[4]劉明珠，丁亦楠，鄭云非.XML數據公交信息查詢優化算法及實現[J].哈爾濱理工大學學報，2015，20（02）：85-90.

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

[6]何炎祥，喻濤，陳彥釗，等.物聯網環境中數據存儲與查詢機制研究[J].計算機科學，2015，42（03）：185-190.

作者簡介

劉勝軍（1974-），男，安徽省和縣人。計算機專業碩士，主要研究方向為機器學習、數據挖掘。

作者單位

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