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

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

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

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

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

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

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

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

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

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