移動計算環(huán)境下語義緩存及查詢處理研究.pdf

1、移動計算環(huán)境中，由于通信帶寬窄、網(wǎng)絡(luò)斷接頻繁、移動終端資源有限等缺陷，造成了移動用戶數(shù)據(jù)存取的瓶頸，使得移動計算環(huán)境下客戶查詢請求處理面臨一定的挑戰(zhàn)。在客戶端進(jìn)行數(shù)據(jù)緩存，減少移動節(jié)點(diǎn)對數(shù)據(jù)庫服務(wù)器的訪問正是解決此瓶頸的關(guān)鍵。傳統(tǒng)的緩存技術(shù)主要包括頁面緩存和元組緩存兩種方式。其中頁面緩存采用靜態(tài)的時間和空間屬性，對數(shù)據(jù)庫的物理結(jié)構(gòu)很敏感，當(dāng)數(shù)據(jù)庫中的數(shù)據(jù)空間聚集度較差時，將會加劇消耗有限的網(wǎng)絡(luò)帶寬，占用大量的移動設(shè)備存儲空間；元組緩存會

2、造成通訊開銷昂貴、并行處理困難、不支持網(wǎng)絡(luò)斷接時的數(shù)據(jù)處理和一致性維護(hù)效率低等問題。因此，對于網(wǎng)絡(luò)連接不穩(wěn)定、網(wǎng)絡(luò)資源十分有限、網(wǎng)絡(luò)通訊代價昂貴的移動計算環(huán)境，采用傳統(tǒng)緩存技術(shù)顯然是不合適的。這就迫切需要一種新的緩存技術(shù)來支持移動客戶機(jī)在網(wǎng)絡(luò)弱連接或斷接情況下的數(shù)據(jù)訪問。語義緩存是基于客戶查詢語義相關(guān)建立的一種客戶緩存，內(nèi)容是由以往查詢的結(jié)果以及相應(yīng)的語義描述構(gòu)成。由于移動客戶進(jìn)行的數(shù)據(jù)訪問大多具有良好的語義相關(guān)性，采用語義緩存，客戶端

3、可以利用本地緩存的以往查詢的語義信息進(jìn)行推理判斷，從而確定客戶查詢是否可在本地緩存獲得全部或部分結(jié)果，盡可能地利用本地緩存處理查詢。建立在語義緩存基礎(chǔ)之上的查詢處理就可以減少對數(shù)據(jù)庫的訪問及降低網(wǎng)絡(luò)數(shù)據(jù)傳輸量，從而提高查詢響應(yīng)速度以及降低網(wǎng)絡(luò)開銷。因此語義緩存能很好地滿足移動計算環(huán)境下的查詢處理要求。目前，許多專家學(xué)者對語義緩存展開了相關(guān)研究，研究的內(nèi)容主要包括語義緩存模型、語義緩存查詢處理、語義緩存替換、語義緩存一致性維護(hù)、語義緩存查

4、詢裁剪優(yōu)化等。本文針對當(dāng)前語義緩存的研究熱點(diǎn)問題，主要在語義緩存查詢處理、語義緩存查詢裁剪優(yōu)化方面作了相關(guān)研究：在語義緩存查詢處理研究方面，本文在引出了查詢可導(dǎo)出的形式化定義，詳細(xì)探討了查詢與緩存的各種匹配關(guān)系以及在各種匹配關(guān)系下的判定條件、探測查詢和剩余查詢，并在此基礎(chǔ)上提出了基于單表的語義緩存查詢處理策略。主要工作有：1)針對原有的修補(bǔ)查詢處理涉及抽象復(fù)雜的概念且實(shí)現(xiàn)困難，提出了改進(jìn)的修補(bǔ)查詢處理(Amending Query Pr

5、ocessing)策略。在查詢包含于緩存卻不能從緩存中導(dǎo)出時，修補(bǔ)查詢以補(bǔ)充緩存所缺失的屬性，使得查詢能夠從緩存中導(dǎo)出，增加了緩存的命中率和利用率；2)提出了無效查詢處理(Invalid Query Processing)，針對用戶有時會提交無效查詢(如無效屬性、無效關(guān)系表、無效條件等)，無效查詢處理可以使無效查詢在初始階段丟棄而不作進(jìn)一步操作，從而提高了查詢處理的效率；3)對查詢計劃樹(Query Plan Tree)結(jié)點(diǎn)的存儲結(jié)構(gòu)進(jìn)

6、行了改進(jìn)，使得查詢計劃樹的每個結(jié)點(diǎn)由原先的5個屬性減少為3個屬性，降低了創(chuàng)建查詢計劃樹的空間消耗；4)設(shè)計了一個語義緩存查詢處理實(shí)驗(yàn)?zāi)Ｐ?，對單個緩存片和多個緩存片查詢處理分別進(jìn)行了實(shí)驗(yàn)?zāi)M，實(shí)驗(yàn)結(jié)果證明了本文提出的語義緩存查詢處理策略以及所涉及算法的正確性和有效性。在語義緩存查詢裁減優(yōu)化研究方面，語義緩存具有實(shí)用性的關(guān)鍵在于查詢裁剪的快速執(zhí)行和裁剪結(jié)果簡單，如果查詢裁剪過程消耗時間太多或者裁剪出的探測查詢和剩余查詢復(fù)雜度太高，均會影響查

7、詢處理的執(zhí)行效率，語義緩存的實(shí)用性也將會大大降低。本文針對查詢裁剪的時空消耗及裁剪結(jié)果的復(fù)雜度進(jìn)行了相關(guān)改進(jìn)，提出了基于邏輯規(guī)則的查詢裁剪優(yōu)化策略。主要工作有：1)深入分析了語義緩存查詢處理優(yōu)化的必要性以及優(yōu)化的理論基礎(chǔ)；2)分析了對邏輯公式運(yùn)算進(jìn)行化簡的可能性，提出了新的12條優(yōu)化規(guī)則，同時對謂詞的可滿足性進(jìn)行判斷以及優(yōu)化處理，從而大大減少查詢裁剪的中間邏輯式子的規(guī)模，使得裁剪得到的探測查詢和剩余查詢盡量簡單；3)設(shè)計了合取式優(yōu)化算法