[發明專利]XPath查詢優化方法及系統

有效

• 申請號: 201210411505.8
• 申請日: 2012-10-24
• 公開（公告）號: CN102929996A
• 公開（公告）日: 2013-02-13
• 發明（設計）人: 李東;梁曉翀
• 申請（專利權）人: 華南理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 蔡茂略

技術領域

本發明涉及數據庫的技術領域，特別涉及一種XPath查詢優化方法及系統。

背景技術

近年來，越來越多的數據采用XML進行描述并在網絡上傳輸和交換，XML數據量的急速膨脹給計算機科學領域帶來了新的問題：如何有效地存儲和快速地檢索XML數據。以數據庫方式對互聯網上的海量XML數據進行存儲和查詢，是目前關于XML數據處理問題的一種主流思想。對于所有的數據庫系統來說，查詢處理都是其必不可少、最重要的功能之一。而作為查詢處理的重要組成部分，查詢優化技術往往是影響查詢效率的關鍵因素。由于XML數據模型的復雜性和其規模越來越大，及其XML查詢本身的復雜性，使得XML查詢的性能往往并不理想。人們在傳統的關系數據庫中已經運用得相當成熟的查詢優化技術，在面對XML數據的時候卻遇到了不少困難，主要表現為這些針對關系數據的查詢優化技術無法處理層次結構的XML數據，XML數據庫的查詢優化技術是目前該領域的一個研究熱點。

XML數據庫查詢優化的物理優化部分，是通過對上一階段生成的查詢計劃進行執行次序的優化。一個查詢計劃由不同的執行片段組成，這些片段執行順序的不同會導致執行時間的差異。物理優化就是要通過一些方法來估算各種執行次序的執行時間，選擇一個代價可能最小的執行次序來重構查詢計劃。

基于代價估算的XPath查詢優化方法，需要對XML數據的分布情況進行數據收集并統計，在查詢優化時利用對XML數據的各種統計信息來計算不同查詢計劃的執行代價，因此除了代價估算模型之外，這種估算方法的準確度在很大程度上依賴于統計信息的精確性。

在關系模型中，進行代價估算是基于獨立性假設和均勻分布假設這兩個通用的前提。而XML數據的不規則性是對傳統統計信息方法的重要挑戰，其數據分布情況使得一些傳統的分布假設難以成立，結構的復雜性又為獲得相對精確的統計信息帶來存儲和計算上的困難，XML數據的有序性還制約了轉換規則的靈活性。所有這些問題，都使得在xml中采用傳統的代價估計方法不切實際，會帶來很大的誤差。

發明內容

本發明的目的在于克服現有技術的缺點與不足，提供一種有效的XPath查詢語句的結構連接順序優化方法。通過對各個子路徑的選擇度進行快速估算，然后根據估算結果對原查詢計劃樹進行重構，得到優化的查詢計劃。

本發明的另一目的在于，提供一種XPath查詢優化系統。

為了達到上述第一目的，本發明采用以下技術方案：

一種XPath查詢優化方法，包括下述步驟：

S101、初始化代價估算矩陣；

S102、處理單步路徑；

S103、判斷是否存在未估算路徑，如果是，則進入步驟S104；如果否，則進入步驟S115；

S104、判斷路徑類型，若判斷得到當前路徑為長路徑，則進入步驟105，若是謂詞路徑，則進入步驟110；

S105、判斷是否存在下一種可能的連接；對于長度大于1的長路徑來說，任意的路徑Stepi/…/Stepj，都能將其看成由兩個子路徑Stepi/…/Stepk和Stepk+1/…/Stepj連接而成，其中i<=k<j，因此該路徑共有j-i種連接，k初始為i，每循環一次加1，至j-1結束，若i<=k<j時下一步進入步驟S106，估算該路徑在當前連接下消耗的代價；當k=j時表示已遍歷完該路徑所有可能的連接情況，進入步驟S109估算該路徑的結果集和結果集規模；

S106、利用文檔統計信息估算長路徑代價；

S107、判斷是否最優連接；即判斷上一步驟計算所得的長路徑執行代價是否小于已記錄于代價估算矩陣中的最小執行代價cost，若為真則進入步驟108，記錄當前連接的信息，否則無需記錄任何信息，返回步驟S105；

S108、用最優連接和代價更新代價估算矩陣；進入步驟S108則表示當前路徑在k處的分割為代價最小的連接方式，因此在代價估算矩陣中更新最小執行代價cost和最優連接分割點splitIndex，其中splitIndex=k；

S109、利用文檔統計信息估算結果集，更新結果集矩陣；

S110、判斷是否存在下一種可能的排列；

S111、利用文檔統計信息估算謂詞路徑代價；

S112、判斷是否最優排列；判斷步驟S111計算所得的謂詞路徑執行代價是否小于已記錄于代價估算矩陣中的最小執行代價cost，若為真則進入步驟S113，記錄當前謂詞排列順序的信息，否則無需記錄任何信息，返回步驟S110；