基于智能技術(shù)的Top-N關(guān)系查詢處理和優(yōu)化.pdf

1、數(shù)據(jù)庫系統(tǒng)正在經(jīng)歷巨大的變化，智能技術(shù)已經(jīng)引入到數(shù)據(jù)庫系統(tǒng)的研究中。2004年在SIGMOD國際會(huì)議上，Jim Gray說：“我們正沿著一條有價(jià)值的鏈條從數(shù)據(jù)到信息到知識(shí)到智慧在慢慢地攀爬”。數(shù)據(jù)庫研究的核心問題之一為查詢處理和優(yōu)化。近年來top-N查詢倍受關(guān)注，成為國際上非?；钴S的研究課題。top-N查詢比傳統(tǒng)查詢的應(yīng)用更廣泛、更靈活、功能更強(qiáng)大，能夠解決傳統(tǒng)數(shù)據(jù)庫管理系統(tǒng)(DBMS)無法處理的查詢問題；其主要應(yīng)用包括：數(shù)據(jù)挖掘、搜索

2、引擎、決策支持系統(tǒng)、多媒體數(shù)據(jù)庫、信息檢索、Web智能和Web數(shù)據(jù)庫等。 在查詢的研究中，關(guān)鍵是對(duì)查詢準(zhǔn)確和快速地處理，因此需要研究查詢處理的理論、方法、技術(shù)及優(yōu)化策略。本文主要對(duì)top-N查詢進(jìn)行研究。top-N查詢就是，對(duì)于用戶指定的正整數(shù)N，如N=10，20或100，檢索出N個(gè)元組使其最好地匹配查詢條件，但不一定完全匹配查詢條件；輸出的結(jié)果集合按所用的距離函數(shù)排序。具體內(nèi)容如下： 1．基于學(xué)習(xí)的top-N查詢處理：

3、本文運(yùn)用基于學(xué)習(xí)的策略，給出top-N查詢處理的一種新方法。其主旨為，在初始階段，對(duì)于少數(shù)隨機(jī)的top-N查詢，找出其最佳搜索區(qū)域并將相關(guān)信息存儲(chǔ)在一個(gè)知識(shí)庫中；然后用知識(shí)庫中的知識(shí)處理新提交的top-N查詢；隨著被處理的top-N查詢的增加，原始知識(shí)庫將被不斷更新，因而能夠更好地處理頻繁提交的查詢。另外，給出知識(shí)庫的維護(hù)方法并且用時(shí)間序列的理論和方法討論知識(shí)庫的穩(wěn)定性。最后，用大量的實(shí)驗(yàn)來驗(yàn)證基于學(xué)習(xí)策略的性能，且與其它方法進(jìn)行比較。

4、實(shí)驗(yàn)結(jié)果表明基于學(xué)習(xí)的方法不僅可以很好地處理低維數(shù)據(jù)，而且能夠很好地處理高維數(shù)據(jù)，不懼怕“維數(shù)災(zāi)難”；與現(xiàn)有其它方法比較，其效率更有優(yōu)勢(shì)。 2．基于區(qū)域聚類的多top-N查詢優(yōu)化：在很多數(shù)據(jù)庫應(yīng)用中，存在同時(shí)處理多個(gè)提交的top-N查詢的情形。通常，同時(shí)處理多個(gè)查詢的開銷比單個(gè)地逐一處理更有效。對(duì)于關(guān)系數(shù)據(jù)庫，本文提出了同時(shí)處理多個(gè)top-N查詢的一種新方法，其基本思想是區(qū)域聚類。區(qū)域聚類把各個(gè)top-N查詢的搜索區(qū)域聚集成一些

5、較大的區(qū)域并且從這些較大的區(qū)域檢索元組。這種方法避免了多次訪問同一區(qū)域并且減少了對(duì)底層數(shù)據(jù)庫隨機(jī)I/O訪問次數(shù)。通過大量實(shí)驗(yàn)測(cè)試這種新策略的性能；實(shí)驗(yàn)結(jié)果表明對(duì)于低維(2，3和4維)和高維(25，50和104維)數(shù)據(jù)，這種方法明顯優(yōu)于逐一處理的樸素方法。另外，雖然區(qū)域聚類方法是為多top-N查詢優(yōu)化提出的，但可以直接運(yùn)用于多區(qū)域查詢優(yōu)化；對(duì)此，本文也進(jìn)行了研究，其性能也顯著優(yōu)于樸素方法。 3．Top-N查詢流處理：在數(shù)據(jù)庫系統(tǒng)及

6、其應(yīng)用中，另一個(gè)重要問題是處理在不同時(shí)間提交的top-N查詢所形成的查詢流。為此，改進(jìn)了上述基于學(xué)習(xí)的策略并且結(jié)合區(qū)域聚類方法，同時(shí)運(yùn)用緩存機(jī)制，對(duì)top-N查詢流進(jìn)行綜合優(yōu)化處理。這種方法使用知識(shí)庫來存儲(chǔ)一些過去查詢的相關(guān)信息，聚類以往查詢的搜索區(qū)域?yàn)檩^大的區(qū)域，進(jìn)而從這些較大區(qū)域檢索元組。為了回答一個(gè)新提交的查詢，盡量從內(nèi)存中已經(jīng)檢索的結(jié)果獲取元組。這樣，通過盡量減小搜索區(qū)域和避免訪問底層數(shù)據(jù)庫來尋求縮短響應(yīng)時(shí)間。同時(shí)，這種方法保持

7、查詢高維數(shù)據(jù)的高效性。另外，給出知識(shí)庫的維護(hù)策略。大量的實(shí)驗(yàn)用來驗(yàn)證此策略的性能，實(shí)驗(yàn)結(jié)果表明，無論是對(duì)低維數(shù)據(jù)還是高維數(shù)據(jù)，此方法的性能比樸素方法的性能明顯提高。本文也探究了用類似方法處理區(qū)域查詢流，實(shí)驗(yàn)表明其性能顯著優(yōu)于樸素方法。 4．基于語義距離的top-N查詢處理：傳統(tǒng)數(shù)據(jù)庫搜索在查詢和元組的比較過程中使用模式匹配。對(duì)于一個(gè)查詢，只有當(dāng)元組和查詢完全匹配時(shí)，元組才被檢索。本文研究具有語義的文本屬性的top-N查詢處理，通

8、過定義新的語義距離函數(shù)，實(shí)現(xiàn)數(shù)據(jù)庫搜索過程中詞與詞之間的語義匹配。目的是不僅返回與查詢完全匹配的元組，而且與查詢的語義距離靠近的元組也能被取出。實(shí)現(xiàn)方法的主旨是：基于WordNet創(chuàng)建索引將元組的詞進(jìn)行語義擴(kuò)展；通過此索引來匹配查詢?cè)~和元組的擴(kuò)展詞，運(yùn)用一個(gè)簡(jiǎn)單的SOL選擇語句于關(guān)系的自然連接檢索出候選元組；然后，用語義距離對(duì)候選元組排序，最后輸出top-N結(jié)果。大量的實(shí)驗(yàn)用于測(cè)量這種新策略的性能。 基于以上內(nèi)容的研究結(jié)果，本文

9、的主要貢獻(xiàn)在于： 1．對(duì)于top-N查詢處理，提出了基于學(xué)習(xí)的新方法，通過估計(jì)查詢的局部分布密度，確定top-N查詢的搜索區(qū)域；用時(shí)間序列的理論和方法，定義和分析知識(shí)庫的穩(wěn)定性。 2．提出了多top-N查詢優(yōu)化新問題，并且為了解決此問題，提出了區(qū)域聚類的新方法。區(qū)域聚類的對(duì)象為“n-維超矩形”，而通常聚類的對(duì)象是“點(diǎn)”。上述基于學(xué)習(xí)的和區(qū)域聚類的兩種方法，不僅可以很好地處理低維數(shù)據(jù)，而且能夠很好地處理高維數(shù)據(jù)，不怕維數(shù)災(zāi)