語義緩存查詢裁剪優化
2008-12-31 00:00:00李東葉友謝芳勇
計算機應用研究 2008年12期
（1.華南理工大學 計算機科學與工程學院， 廣州 510640; 2.華南理工大學 軟件學院， 廣州 510006）
摘 要：查詢處理是語義緩存的一個關鍵問題，但是現有的查詢處理算法在時空效率和裁剪結果的復雜度兩個方面存在很大的局限性，這在一定程度上限制了語義緩存的實用性。為了克服這些缺陷，本文對語義緩存的裁剪過程進行優化處理，減少了對服務器的無效訪問，并給出了生成探測查詢和剩余查詢的裁剪算法;算法分析從理論上證明了該優化機制的有效性，同時，仿真實驗的性能比較也表明該優化方法在提高查詢裁剪時空效率和降低剩余查詢復雜度等方面均要明顯優于沒有優化的方法。
關鍵詞：語義緩存； 查詢處理； 查詢裁剪； 優化
中圖分類號：TP301 文獻標志碼： A
文章編號：10013695(2008)12360505
Optimization technology of query trimming in semantic caching
LI Dong1， YE You1， XIE Fangyong2
(1.School of Computer Science Engineering， South China University of Technology， Guangzhou 510640， China; 2. School of Software，South China University of Technology， Guangzhou 510006， China)
Abstract:
Query processing is a key problem in semantic caching. However，there are some deficiencies in the algorithms of the existent query processing，such as low efficiency of time and space as well as the complexity of the trimming result，which restricts the application of semantic caching. For overcoming the limitations， this paper developed a new method，which optimized the query trimming and invalid accessing to database，then gave the trimming algorithm of the probe query and the remainder query. Finally， the performance analysis of simulation experiment also indicates that the optimization technology is excellent more better than the nonoptimization query trimming in improving the efficiency of time and space and reducing the complexity of trimming result.
Key words：semantic cache; query processing; query trimming; optimization
0 引言
語義緩存技術是一種基于結果集及其描述的緩存技術。相對傳統的頁緩存和元組緩存技術，它具備明顯優勢:節約網絡開銷、節省緩存容量、支持并發處理、支持網絡斷接。這使得語義緩存技術在移動計算環境下有非常廣闊的應用前景。
因為移動設備資源有限，語義緩存只能緩存被用戶頻繁訪問的那部分數據集。當用戶發出查詢請求時，查詢所要求的結果集可能只有部分或完全沒有被緩存包含。因此，語義緩存需要對用戶查詢請求進行裁剪以獲得本地緩存可以處理的探測查詢(probe query)[1]和必須送服務器處理的剩余查詢(remainder query)[1]。查詢裁剪快速執行和裁剪結果簡單是語義緩存具有實用價值的關鍵條件。如果查詢裁剪過程過于復雜或者裁剪出的探測查詢和剩余查詢復雜度太高，均會使得查詢處理的執行效率大大降低，此時，語義緩存的實用性將會大大降低。現有的語義緩存查詢處理機制在時空效率和裁剪結果復雜度兩方面存在很大的局限性。文獻[1~3]都分別對語義緩存的查詢處理作了研究，但給出的查詢處理算法都只是利用邏輯與運算和邏輯差運算裁剪出探測查詢和剩余查詢，它們都沒有對與運算和差運算的時空復雜性進行充分的考慮。雖然利用這些算法可以求得探測查詢和剩余查詢，但算法的時間復雜度是指數時間(O(mn)) ，而且求得的剩余查詢是一個指數次冪長度的析取范式(O(n×mn))。此外，這些查詢處理算法會使整個語義緩存的規模以指數次冪來增長，這樣的增長速度將很快耗盡移動設備有限的資源。文獻[4]提出優化的十一條邏輯規則，但是還不夠全面，未給出任意合取式的優化和可滿足性算法，同時并不是所有的謂詞都滿足這些規則。
現在的查詢處理機制是無法滿足用戶對語義緩存實用性要求的。對于語義緩存的查詢處理，需要給出一種優化機制來簡化其計算過程，使得查詢處理的時空復雜度盡量小，并使裁剪得到的探測查詢和剩余查詢盡量簡單。
在對實用性語義緩存技術進行研究的基礎上，本文深入討論優化語義緩存查詢處理的必要性之后，分析了對邏輯公式運算進行化簡的可能性，提出了新的優化規則，同時基于謂詞的類型，對謂詞的進行可滿足性判斷以及優化處理，從而大大減少查詢裁剪的中間邏輯式子的規模，減少對服務器的無效訪問，提高查詢裁剪的時空效率，從而為語義緩存的有效性與實用性提供了可靠保障。
本文的主要貢獻包括:a)分析了查詢裁剪優化的必要性以及優化的理論基礎；b)提出了新的優化規則，同時基于謂詞的類型，對謂詞的進行可滿足性判斷以及優化處理，從而大大減少查詢裁剪的中間邏輯式子的規模，使得裁剪得到的探測查詢和剩余查詢盡量簡單;c)仿真系統的性能分析將采用和不采用優化機制的情況進行了對比，實驗數據很好地說明了該優化機制的有效性和可靠性。
1 語義緩存模型
11 語義緩存定義
定義1數據庫D={Ri}（1≤i≤n） 屬性集合A=∪ARi（1≤i≤n）比較謂詞P=a op c(a∈A，op∈{≤，<，≥，>，=}，c是一個確定的值域)。
定義2 緩存語義段[1]形式化表示為SRC : 〈SR，SA，SP，SC，ST〉。其中：SR為緩存段的關系表；SA為緩存段的屬性集合；SP查詢謂詞；SC為緩存段結果集合；ST為緩存段最新訪問的時間戳。
定義3查詢[1]Q : 〈QR，QA，QP，QC，QT〉。其中：QR為查詢對應的關系表；QA為查詢對應的屬性集合；QP為查詢對應謂詞；QC為查詢對應的結果集合；QT為查詢發生時間。
定義4語義緩存SC(semantic cache)[1]由多個語義緩存段SRC組成的集合，形式化定義:SC={SRCi}(1≤i≤n，SRCi != SRCj if i!=j)。
12 謂詞相關定義
查詢謂詞QP形式表示為三段式[1]{attribute，operation，Data}。其中:attribute為關系中對應屬性；operation取值{＝，＜，＞，≤，≥，like，not like}；data取值{string，integer，float，double，Boolean}。
定義5數值型謂詞(numerical predicate)。當且僅當P涉及關系中的屬性為數值型，且data可以采用數值范圍來表示，如B.a≥20，則范圍取值[20，+∞)。
定義6 非數值型謂詞(nonnumerical predicate)。當且僅當謂詞P涉及關系中的屬性為非數值型，如字符型、布爾型等。
非數值型謂詞分為兩類，即字符型和布爾型。其中，字符約束型中data取值為字符串(string)型，如B.name＝ Tom，布爾約束型中data取值為{Boolean}，如B.Flag＝1。
定義7謂詞滿足（predicate satisfiable)。
分別對數值型謂詞和非數值型謂詞滿足進行定義如下：
a)數值型謂詞滿足
(a)范圍全滿足。Pi和Pj為數值型謂詞，采用數值范圍表示，若Pi 在范圍上包含Pj，稱全滿足。若Pi為{B.a，＞，5}，Pj為{B.a，＞3}，則Pj對于Pi全滿足。
(b)范圍相交滿足。Pi和Pj為數值型謂詞，采用數值范圍表示，且在范圍上相交，稱相交滿足。若Pi為{B.a＞5}，Pj為{B.a＜8}。
b)非數值型謂詞滿足
(a)字符型謂詞滿足，當且僅當Pi的attribute等于Pj的attribute，Pi的operation包含Pj的operation，且data為包含關系，如gender＝ female包含在gender like %female%中。
(b)布爾型謂詞滿足，當且僅當Pi與Pj的attribute相等，operation相等且data相等，或operation不等且data不等，則滿足；否則不滿足。
2 語義緩存查詢裁剪
21 查詢匹配和剪減
查詢匹配是語義緩存發揮作用的關鍵。語義緩存與一般緩存的不同之處就在于它不依賴數據存儲的物理結構，可以充分利用用戶查詢之間的語義關聯。查詢匹配就是尋找緩存中與當前查詢相關數據的過程。在實際應用中，語義緩存不可能滿足所有的用戶查詢。用戶查詢與緩存之間存在多種關系，即緩存與查詢相互獨立、相交和緩存包含查詢。
假定用戶查詢為Q，緩存中與它相交的語義單元為S ，~Q 和~S 分別為Q 和S 的補集。當查詢與緩存相交時，查詢與其匹配的緩存單元就分割成三個獨立的部分，即S∧~Q、S∧Q 和~S∧Q。S∧Q 和~S∧Q分別是Q 的探測查詢PQ和剩余查詢RQ。
22 優化的必要性
對于未經過優化的裁剪算法的復雜性，本文用下面的例子予以說明這一計算過程。
例1 假定語義緩存段S為(A≥30∧B>3000∨A<25∧B≤3000∨A≥25∧B<3000)。這時客戶發出的查詢請求Q為(A>10∧B<1000)。探測查詢和剩余查詢的計算方法如下：
探測查詢
PQ=(A>10∧B<1000)∧ (A≥30∧B>3000∨A<25∧B≤3000∨ A≥25∧B<3000)=(A>10∧B<1000∧A≥30∧B>3000)∨(A>10∧B<1000∧A<25∧B≤3000)∨(A>10∧B<1000∧A≥25∧B<3000)
剩余查詢
RQ=(A>10∧B<1000)∧~(A≥30∧B>3000∨A<25∧B≤3000∨A≥25∧B<3000)=(A>10∧B<1000∧A<30∧A≥25∧A<25)∨(A>10∧B<1000∧A<30∧A≥25∧B≥3000)∨(A>10∧B<1000∧A<30∧B>3000∧A<25)∨(A>10∧B<1000∧A<30∧B>3000∧B≥3000)∨(A>10∧B<1000∧B≤3000∧A≥25∧A<25)∨(A>10∧B<1000∧B≤3000∧A≥25∧B≥3000)∨(A>10∧B<1000∧B≤3000∧B>3000∧A<25)∨(A>10∧B<1000∧B≤3000∧B>3000∧B≥3000)
從上面的裁剪過程可以看出，裁剪過程非常繁瑣，而且從最終得到的探測查詢和剩余查詢在形式上也非常復雜。假定查詢Q長度是m的合取項子式，單個緩存段的n個長度為m的合取子式的析取。在最壞的情況下，探測查詢有n個長為2 m的合取子式的析取范式， 剩余查詢有mn個長為m+n的合取子式的析取范式；探測查詢的時間復雜度為O(n×m)，剩余查詢的時間和空間復雜度也分別為O(mn)和O((m+n)×mn)。
這個有mn個長m+n 的合取子式的析取范式將會被發送給服務器處理，返回數據。最終，它還會作為新的緩存片的語義而被添加進語義緩存中。那么，此時語義緩存的規模就為m×n+(m+n)×mn長度的析取范式。可以明顯看出，在這樣的查詢處理機制下，語義緩存的規模是以指數次冪遞增的。當語義緩存經過足夠多的查詢處理后，有限的移動設備將無法承載語義緩存的規模及其查詢處理的時空消耗。這在很大程度上降低了語義緩存的實用性。因此，需要一種優化機制對查詢裁剪的過程和結果進行優化。
23 查詢裁剪算法優化
231 理論基礎及優化算法
任何條件表達式均可以化簡為析取范式的形式，本文對析取范式進行優化處理，假設析取范式的形式如下:
則它們具有以下規則：
like d)1。
命題等價于：如果AB，那么A∧BB。
充分性：設x∈B，因為AB，則x∈A，所以x∈A∧B，所以B→A∧B成立。
必要性：設x∈A∧B，那么x∈A且x∈B，所以x∈B，所以A∧B→B成立。
故命題得證。
由于其他規則的證明均比較簡單直觀，限于篇幅的原因，本文不給出其證明過程。
在對謂詞進行優化前，需進行預處理，即根據謂詞的屬性名稱進行分組，然后利用以上性質對同屬性的謂詞進行優化，判斷其可滿足性或消除冗余子式。從而將謂詞化簡成更加簡單的形式。具體優化算法如算法1。
輸入：P=P1∧P2∧P3∧…∧Pn;Pi為比較謂詞。
輸出：可滿足，則輸出True，并返回優化的謂詞結果P；不可滿足，則輸出1。
(1)Ts←group（P） 對P根據每個謂詞的屬性名稱進行分組，產生分組集合Ts
首先，根據每個謂詞的屬性名稱進行分組，產生分組集合，然后對每個分組后的謂詞，分別根據其謂詞的類型進行優化處理。
對于數值型謂詞，根據優化規則11~13進行合并處理，舍棄冗余的謂詞，減少謂詞數量，然后再根據規則9~11，判斷其可滿足性，若不滿足則返回1。
對于布爾型謂詞，根據優化規則7進行合并處理，舍棄冗余的謂詞，減少謂詞數量，然后再根據規則15、16，判斷其可滿足性，若不滿足則返回1。
對于數值型謂詞，根據優化規則7、20進行合并處理，舍棄冗余的謂詞，減少謂詞數量，然后再根據規則17~19判斷其可滿足性，若不滿足則返回1。
232 對于謂詞求補（~P）的運算規則
在查詢裁剪過程中，剩余查詢（~S∧Q），以及語義緩存被裁剪的剩余部分S∧~Q 的運算均要涉及謂詞求補（~P）的操作。本文對謂詞進行分類，根據各自的類型對其進行求補操作。具體的謂詞求補（~P）的運算規則如表1、2所示。
233 探測查詢和剩余查詢優化算法
命題得證。
根據定理1 ，可以得出結論:如果按照優化的算法計算的探測查詢PQ (S∧Q)是不可滿足式的，那么剩余查詢RQ(~S∧Q)就等于客戶查詢Q，從而無須再計算剩余查詢RQ (~S∧Q)，將其直接發送給數據庫服務器處理即可。
1）優化的探測查詢裁剪
本文假定客戶查詢是合取式的形式，對于存在“或”條件的客戶查詢，可以將其轉換為析取范式的形式，將其進行分割成若干個合取式來處理。
探測查詢是能夠在本地緩存中得到部分或全部解答的查詢，探測查詢的計算過程就是化簡S∧Q 的過程。對輸入的客戶查詢Q和語義緩存段S進行與操作得S∧Q，然后根據邏輯運算規則，求得S∧Q的析取范式形式，分別對其中的每個合取子式進行優化處理，結果即為形式簡單的合取子式集合。詳細的算法描述如算法2。
算法2
2）優化的剩余查詢裁剪
剩余查詢是查詢Q不能從語義緩存塊中得到解答，而需發往服務器端處理的查詢。因此，剩余查詢的計算過程就是化簡~S∧Q的過程。對于輸入的客戶查詢Q和語義緩存S，先判斷S∧Q，即探測查詢的結果是否為空。如果為空，則剩余查詢即為客戶查詢；如果不空，則根據謂詞求補的規則表求得~S，再根據邏輯運算規則，求得~S∧Q的析取范式形式，分別對其中的每個合取子式進行優化處理，結果即為形式簡單的合取子式集合。詳細算法描述見算法3。
同樣，利用例1 中的相關假定，這里按照算法3，給出裁剪剩余查詢的優化過程。
例2 優化的剩余查詢裁剪過程
24 算法分析
假定用戶查詢是長度為m的合取子式，語義緩存段的語義描述是n個長度為m的合取子式的析取，經過邏輯規則運算，生成的剩余查詢為mn個長為m+n的合取子式組成的析取范式。優化的剩余查詢的裁剪算法可以刪除部分的合取子式和合取項，從而減少剩余查詢的長度以及運算的規模。
為了討論的方便，假設經過算法3優化的合取子式數目為θn。其中δ<1，經過算法1優化的每個合取子式的合取項數目為δm，θ<1。那么優化的剩余查詢的裁剪算法的時間復雜度為O((δm)(n))) ，空間復雜度為O((m + n)×(δm)(n) ) ，對比未優化的算法的時間復雜度為O(mn) 和空間復雜度為O((m + n)×mn) ，所以優化后的時間和空間復雜度均為原來的(δm)(n)/mn。所生成的剩余查詢的復雜度也減少為原來的δm ×θn /m ×n =δθ。這個優化是非常可觀的，如果假設m=5，δ=θ= 02，n=5，那么優化后的時間和空間復雜度為未優化的1/55。所生成的剩余查詢的復雜度也減少為原來的1/25。
3 性能分析
本文設計了模擬實驗來測試優化的查詢處理的性能，并將用沒有優化的查詢處理與本文的優化處理方法進行比較（圖1），從多個方面顯示優化所帶來的效益。
321優化和無優化查詢裁剪的時間效率和空間效率比較
本文選擇了兩項主要指標，即裁剪的時間和空間消耗，來對優化的查詢裁剪的性能進行分析。圖2和3是與無優化的情況進行對比的情況。
圖中的橫軸均表示每次發出查詢的組數，縱軸分別表示查詢裁剪消耗的時間和空間，圖中每點的數據獲取方法是:用一組查詢(包含queryCount個查詢)進行處理，對每一組查詢消耗的時間和空間最后取平均值。總體上講，查詢裁剪消耗的時間和空間隨著查詢的增加而增加，這是因為查詢越多，那么緩存的數量會增多，從而計算量增大。但是很明顯，無優化裁剪算法的時空耗費遞增的速度遠遠快于優化的裁剪算法，即使當無優化裁剪算法時空消耗巨大時，優化的裁剪算法還是比較穩定，能夠很快地完成裁剪，這樣就能夠保證及時地返回查詢結果給用戶。
322優化和無優化的剩余查詢復雜度比較
本文給出的優化的裁剪算法通過刪除多余的原子公式和析取子式、合并關聯的合取子式的方法，大大地降低了最后裁剪得出的剩余查詢的復雜度，圖3中的數據比較了無優化情況和優化情況查詢裁剪得到的剩余查詢的復雜度。
從圖3中可以明顯看到無優化查詢處理結果是:剩余查詢的復雜度遞增的速度非常快，而優化查詢處理的方法得到的剩余查詢的復雜度遞增的速度非常緩慢，而且能夠保持在較低的數量級。這些數據很好地證明了優化查詢處理方法對于降低結果剩余查詢復雜度的有效性和穩定性。
綜合上述分析，本文給出的優化查詢處理方法在提高查詢 裁剪時空效率和降低剩余查詢復雜度兩個方面均滿足了很好的指標，所以說優化方法是有效的、可靠的。
4 結束語
本文從語義緩存查詢裁剪所面臨的時空效率低、結果復雜等問題出發，給出并證明了可用于優化查詢求值的二十條邏輯規則。基于這些規則和定理，本文給出了優化查詢處理的詳細算法，使得裁剪后的探測查詢和剩余查詢的表達式大大簡化，同時也減少了對服務器的無效訪問，提高了語義緩存裁剪的效率。算法分析從理論上分析了該優化方法所帶來的效益。從仿真實驗系統中的性能分析還可以明顯看出本文給出的優化的查詢處理算法在提高查詢裁剪時空效率和降低查詢復雜度兩個方面均明顯優于沒有優化的情況，這使得語義緩存的實用性得到大大提高。
參考文獻:
[1] REN Qun， DUNHAM M H， KUMAR V. Semantic caching and query processing[J].IEEE Trans on Knowledge and Data Engineering， 2003， 15 (1):192210.
[2] 吳婷婷，周興銘.基于語義緩存的移動查詢導出[J].計算機學報，2002， 25 (10):11041110.
[3] 吳婷婷，章文嵩，周興銘.斷接下查詢的緩存處理[J].計算機學報，2003， 26 (10):13931399.
[4] 郝小衛，章陶，李磊.基于邏輯規則的語義緩存查詢處理優化技術[J].計算機學報，2005， 28 (7):10961103.
[5] AMIRI K， PARK S， TEWARI R， et al. Scalable template based query containment checking for Web semantic caches[C]//Proc of the 19th International Conference on Data Engineering. Bangalore:[s. n.]， 2003:493504.
[6] REN Qun， DUNHAM M H. Using semantic caching to manage location dependent data in mobile computing[C]//Proc of the 6th Annual International Conference on Mobile Computing and Networking. Boston:[s. n.]， 2000:210221.
[7] DAR S，FRANKLIN M J，JONSSON B T，et al. Semantic data caching and replacement[C]//Proc of the 22nd VLDB Conference. Mumbai:[s. n.]， 1996:330341.
[8] 郝小衛，章陶，李磊.子句間優化技術在語義緩存查詢求值中的應用[J].計算機科學，2005， 32 (7):6568.
[9] 李磊，左萬歷，李希春.PROLOGDBMS系統實現中的子句間優化技術[J].軟件學報，1995， 6 (3):136141.
[10] 蔡建宇，楊樹強，賈焰，等.關系數據庫語義緩存的研究進展[J].計算機工程與科學，2005， 27 (10):6264，84.[11] 吳婷婷，章文嵩，周興銘.移動查詢緩存處理的研究[J].計算機研究與發展，2004， 41 (1):187193.
