移動(dòng)數(shù)據(jù)查詢優(yōu)化處理(數(shù)據(jù)庫)

時(shí)間：2022-12-04 22:30:01 | 來源：信息時(shí)代

時(shí)間：2022-12-04 22:30:01 來源：信息時(shí)代

    移動(dòng)數(shù)據(jù)查詢優(yōu)化處理 : 在傳統(tǒng)分布式數(shù)據(jù)庫查詢處理與優(yōu)化技術(shù)的基礎(chǔ)上,利用多種查詢優(yōu)化方法,消除帶寬多樣性、斷接等因素造成的影響,使查詢引擎能夠根據(jù)當(dāng)前可用網(wǎng)絡(luò)條件采取恰當(dāng)?shù)膬?yōu)化策略。針對(duì)移動(dòng)計(jì)算機(jī)有限的電源能力,合理地組織本地?cái)?shù)據(jù)庫管理、遠(yuǎn)程數(shù)據(jù)庫訪問等耗電能較多的操作,達(dá)到節(jié)能目的,延長(zhǎng)關(guān)鍵數(shù)據(jù)的可用時(shí)間。
1.移動(dòng)數(shù)據(jù)的查詢優(yōu)化處理
移動(dòng)數(shù)據(jù)庫自身的特點(diǎn),決定了在移動(dòng)數(shù)據(jù)庫的查詢與優(yōu)化方面必須采取與普通數(shù)據(jù)庫不同或更優(yōu)化的策略。由于移動(dòng)通信費(fèi)用較高,移動(dòng)客戶機(jī)與網(wǎng)絡(luò)的連接處于頻繁的斷接狀態(tài),因而縮短移動(dòng)數(shù)據(jù)庫查詢的響應(yīng)時(shí)間,減少網(wǎng)絡(luò)延遲是移動(dòng)數(shù)據(jù)庫查詢優(yōu)化必須解決的問題。
移動(dòng)數(shù)據(jù)庫中,與時(shí)空關(guān)聯(lián)的查詢,按照查詢謂詞的數(shù)量可以分為單謂詞查詢和多謂詞查詢。謂詞可以包括范圍謂詞、K鄰近謂詞等。對(duì)于多謂詞的查詢更需要進(jìn)行優(yōu)化,選擇執(zhí)行代價(jià)最小的查詢計(jì)劃。如下為兩個(gè)多謂詞查詢的實(shí)例。
例如,某人開車行駛在高速公路上,他想知道最近的汽車旅館在哪兒。為此,他需要知道位于他前方公路旁的汽車旅館。在這種情況下,他或許會(huì)提交一個(gè)連續(xù)查詢來監(jiān)測(cè)在他前方(一個(gè)范圍謂詞)的最近的旅館(一個(gè)K鄰近謂詞)。
又如公安人員想要找出任意時(shí)刻城市中嫌疑犯的人數(shù)大于警察的人數(shù)的區(qū)域。這個(gè)查詢首先要找到每個(gè)區(qū)域的警察和嫌疑犯(兩個(gè)范圍謂詞),并對(duì)每個(gè)區(qū)域的對(duì)象分組,從而得到兩個(gè)組各自的人數(shù),然后執(zhí)行連接選擇獲得嫌疑犯多于警察的區(qū)域。在這種情況下,警察和嫌疑犯都可以是連續(xù)運(yùn)動(dòng)的。
這兩個(gè)查詢實(shí)例說明了在移動(dòng)數(shù)據(jù)庫中多謂詞時(shí)空查詢的重要性。這種應(yīng)用帶來的一個(gè)最直接的挑戰(zhàn)是如何建立一個(gè)查詢?cè)u(píng)估計(jì)劃來響應(yīng)多謂詞時(shí)空查詢。另外一個(gè)挑戰(zhàn)就是這個(gè)查詢?cè)u(píng)估計(jì)劃是否最優(yōu)或者是否有其他計(jì)劃會(huì)產(chǎn)生更少的系統(tǒng)負(fù)載。例如,假設(shè)用戶希望獲得正在通過某個(gè)區(qū)域的卡車的信息。這個(gè)查詢結(jié)果取決于范圍謂詞(在這個(gè)區(qū)域)和選擇謂詞(類型=“卡車”)的選取,這樣用戶可能會(huì)得到兩個(gè)不同的查詢優(yōu)化評(píng)估計(jì)劃。
在移動(dòng)數(shù)據(jù)庫中,建立完整框架來支持查詢優(yōu)化的關(guān)鍵問題包括: 對(duì)于不斷演化的時(shí)空數(shù)據(jù)的選擇性評(píng)估,考慮如周期和相互關(guān)聯(lián)之類的屬性; 基于選擇性評(píng)估,建立用于時(shí)空查詢的代價(jià)評(píng)估模型;使用連續(xù)時(shí)空查詢的自適應(yīng)性查詢優(yōu)化和擴(kuò)展移動(dòng)數(shù)據(jù)庫查詢優(yōu)化以覆蓋多謂詞時(shí)空查詢。
2. 移動(dòng)數(shù)據(jù)查詢優(yōu)化面臨的挑戰(zhàn)
實(shí)現(xiàn)多謂詞查詢以及變換這些不同謂詞的選擇性,給移動(dòng)數(shù)據(jù)的查詢優(yōu)化提出了一些挑戰(zhàn)性問題:
(1)時(shí)空管道操作挑戰(zhàn):目前大多數(shù)算法都是處理移動(dòng)對(duì)象的單謂詞時(shí)空查詢,這些算法都是非管道的。這些操作的輸入是移動(dòng)對(duì)象位置更新的數(shù)據(jù)流,輸出是滿足查詢的移動(dòng)對(duì)象。查詢結(jié)果或者是周期地報(bào)告,或者是遞增地報(bào)告。周期結(jié)果標(biāo)識(shí)形成結(jié)果集的所有對(duì)象。而對(duì)于遞增的情況,結(jié)果集遞增地報(bào)告正負(fù)更新序列。一個(gè)正更新表明一個(gè)新的對(duì)象加入到結(jié)果集,而負(fù)更新則表明從結(jié)果集中去除一個(gè)對(duì)象。由于當(dāng)前的操作在格式和語義上都不同于它們的輸出,顯然,對(duì)于多謂詞的查詢需要構(gòu)造查詢操作的管道。
(2)時(shí)間挑戰(zhàn): 移動(dòng)對(duì)象分布隨時(shí)間不斷變化。例如,上午9點(diǎn)到下午5點(diǎn)有許多車輛進(jìn)入了市區(qū),使郊區(qū)的車輛很少; 晚上,大多數(shù)車輛停在了停車場(chǎng),不會(huì)與服務(wù)器通信。結(jié)果,在數(shù)據(jù)庫中就缺少了許多車輛的信息。因此,需要建立動(dòng)態(tài)查詢計(jì)劃,用以有效地響應(yīng)長(zhǎng)期的連續(xù)時(shí)空查詢。
(3)空間挑戰(zhàn):把一個(gè)查詢映射成一個(gè)高效的查詢計(jì)劃不是同時(shí)一對(duì)一的映射,對(duì)象在空間的分布大大影響最優(yōu)查詢計(jì)劃的選擇。
(4)時(shí)空挑戰(zhàn):查詢計(jì)劃的選擇性不僅取決于移動(dòng)對(duì)象空間分布,而且取決于移動(dòng)查詢的焦點(diǎn)對(duì)象的位置。當(dāng)一個(gè)查詢有多個(gè)焦點(diǎn)對(duì)象、并且這些對(duì)象都是運(yùn)動(dòng)的時(shí)候,連續(xù)查詢的查詢計(jì)劃就不容易很快地達(dá)到最優(yōu)。
3.移動(dòng)數(shù)據(jù)庫查詢優(yōu)化的目標(biāo)
基于以上挑戰(zhàn),可以得到移動(dòng)數(shù)據(jù)庫查詢優(yōu)化的以下目標(biāo):
(1)多謂詞時(shí)空查詢需要特殊處理,不能僅僅通過簡(jiǎn)單地堆砌已有的時(shí)空操作來實(shí)現(xiàn)。
(2)不同查詢操作的選擇性隨著時(shí)間和空間會(huì)不斷變化,故查詢操作的代價(jià)也會(huì)隨著時(shí)間和空間不斷變化。因此,最優(yōu)執(zhí)行計(jì)劃應(yīng)隨著時(shí)間和空間不斷變化。
(3)關(guān)鍵要考慮自適應(yīng)的查詢優(yōu)化技術(shù)。
4.選擇性評(píng)估技術(shù)
為了高效處理選擇查詢,需要有精確的選擇性評(píng)估技術(shù)。選擇性評(píng)估被定義為查詢結(jié)果中數(shù)據(jù)量與數(shù)據(jù)庫中總數(shù)據(jù)量的比值。通過評(píng)估每種查詢計(jì)劃的代價(jià),查詢優(yōu)化器在所有可能的查詢計(jì)劃中選擇一個(gè)高效的執(zhí)行計(jì)劃。選擇評(píng)估的精確性會(huì)大大影響一種高效查詢計(jì)劃的選擇。
目前,已提出一些移動(dòng)對(duì)象的選擇性評(píng)估方法,目標(biāo)是精確地評(píng)估移動(dòng)對(duì)象的選擇性。查詢優(yōu)化評(píng)估方法方法主要有:
(1)時(shí)空直方圖法:最初用于對(duì)預(yù)測(cè)的時(shí)空查詢的選擇性評(píng)估,主要針對(duì)一維移動(dòng)對(duì)象。多維對(duì)象的選擇性評(píng)估通過每個(gè)維的選擇性評(píng)估相乘得到。通過建立時(shí)空直方圖,可以得到更精確的選擇性評(píng)估。對(duì)于數(shù)據(jù)流應(yīng)用,流入數(shù)據(jù)不能完全存儲(chǔ),故建立直方圖時(shí),連續(xù)查詢模型無法掃描整體數(shù)據(jù)。所以一個(gè)時(shí)空直方圖可以遞增地建立和求精,因此,可以利用來自查詢結(jié)果的反饋來在線更新時(shí)空直方圖。每個(gè)操作定期地報(bào)告它所監(jiān)測(cè)范圍的實(shí)際選擇性。這種統(tǒng)計(jì)在操作內(nèi)進(jìn)行,不需要給查詢帶來額外代價(jià)。
(2)采樣法:采樣法不基于直方圖,旨在減少最優(yōu)評(píng)估所需要的采樣數(shù)量。主要思想是每個(gè)移動(dòng)對(duì)象有一個(gè)關(guān)鍵查詢集合,僅當(dāng)這些移動(dòng)對(duì)象開始或者終止?jié)M足關(guān)鍵查詢的時(shí)候,它們才開始向服務(wù)器傳送新的位置信息。