基于XML Schema的模式樹查詢最小化技術(shù)研究.pdf

1、隨著數(shù)據(jù)庫技術(shù)的不斷發(fā)展，查詢優(yōu)化技術(shù)已經(jīng)形成了一個相對成熟的研究領(lǐng)域。查詢優(yōu)化的目的是為所給定的查詢表達式的計算選擇一個高效的執(zhí)行策略。XML查詢優(yōu)化涉及多個方面，主要包括邏輯優(yōu)化和物理優(yōu)化。邏輯優(yōu)化通過一系列等價轉(zhuǎn)換規(guī)則改寫查詢表達式，達到簡化查詢的調(diào)優(yōu)執(zhí)行順序的目的。物理優(yōu)化通過估計不同執(zhí)行策略的代價，找到最優(yōu)的執(zhí)行策略。XML查詢執(zhí)行的效率與查詢本身的復雜度和查詢的大小有很大的關(guān)系，查詢最小化可通過刪除冗余部分或者改寫來精簡 X

2、ML查詢語句，降低查詢的大小，從源頭上降低查詢的大小以及查詢的復雜性，為查詢的進一步優(yōu)化打下了基礎(chǔ)。
　　本文主要對XML查詢最小化的國內(nèi)外現(xiàn)狀進行了分析，基于模式進行了模式樹最小化技術(shù)研究：
　　1.分析了XML模式的約束信息，基于{-，？，*，+}約束，研究了三種完整性約束：準孩子約束、準后裔約束、同步約束，并運用形式化的語言給出了這三種完整性約束的定義；
　　2.研究了時間復雜度為O(n2m2)的結(jié)點刪除算法，該

3、算法利用三種完整性約束刪除模式樹中的冗余結(jié)點。結(jié)點刪除算法主程序分為三步，分別實現(xiàn)了：簡單葉結(jié)點冗余判斷、葉結(jié)點冗余判斷、非葉結(jié)點冗余判斷，達到了降低模式樹的規(guī)模的目的，并研究了算法正確性的證明過程；
　　3.在XML模式完整性約束的基礎(chǔ)上，通過廣泛研究查詢優(yōu)化算法，分別給出了準后裔約束以及同步約束產(chǎn)生算法，對模式掃描過程進行優(yōu)化。準后裔約束產(chǎn)生算法和同步約束算法利用了二維表高效的數(shù)據(jù)結(jié)構(gòu)，成功的減少了對模式的反復遍歷，使用擴展的