[發明專利]一種基于CD直方圖的空間查詢選擇性估計方法

無效

• 申請號: 200910076930.4
• 申請日: 2009-01-14
• 公開（公告）號: CN101826076A
• 公開（公告）日: 2010-09-08
• 發明（設計）人: 程昌秀;陳榮國;周成虎;張明波;謝炯;盧戰偉;顏勛;朱焰爐;陳應東;趙彥慶;景寧;熊偉;陳宏盛;馮登國;徐震;張敏;陳馳
• 申請（專利權）人: 中國科學院地理科學與資源研究所;中國人民解放軍國防科學技術大學;中國科學院軟件研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京科迪生專利代理有限責任公司 11251
• 代理人: 李新華;徐開翟

技術領域

本發明屬于空間數據查詢與處理技術領域，涉及一種基于CD直方圖的空間查詢選擇性 估計方法。

背景技術

在數據庫中，查詢處理可分為查詢分析、查詢檢查、查詢優化和查詢執行4個階段。每 個查詢都會有許多可供選擇的執行策略和操作算法，查詢優化就是選擇一個高效執行的查詢 處理策略。查詢代價估算(模型)是一種常用的查詢優化方法。

目前，關系數據庫中的查詢代價估算研究已較為成熟；而空間數據庫的空間查詢代價估 算方法的研究尚處于研究階段。空間查詢的代價取決于兩個因素。第一因素為具體使用的查 詢處理算法的CUP代價和I/O代價；第二個因素為輸出查詢結果的I/O代價。前者可以通過 查詢處理算法的時間復雜度和所用索引的性能來評價；后者則由查詢結果集的大小(查詢選 擇性)來決定。因此，空間查詢選擇性估計結果的準確性將直接影響空間查詢代價估算的結 果，間接影響到執行策略的選擇，最終影響到空間查詢的執行效率。因此，提高空間查詢選 擇性估計算結果的準確性對于提高空間查詢的執行效率有很重要的意義。

空間直方圖是一種有效的、估算查詢結果集的大小的方法之一。其基本思想：采用某種 策略將數據空間劃分為數個子空間，一個記錄單元對應一個子空間；在記錄單元中統計落在 其對應子空間內的對象數目；用某種方法對這些統計值進行估計，得到查詢結果集的大小的 估計值。這些記錄單元稱為桶，桶的集合稱為直方圖。

目前，國內常見的空間直方圖有MinSkew、CD、Euler、GH、PH等，其中，CD直方圖 用LL、LR、UL、UR四張直方圖記錄了空間對象MBR左下、右下、左上、右上角點落入第 0行、第0列格子左下角點至第i行、第j列格子右上角點對應矩形區域內的總數，能較為精 確地反映空間對象MBR落入空間區域(桶)內數量的情況，是一種查詢命中準確率相對較 高的空間直方圖。然而，CD直方圖僅給出了查詢區域四條邊與直方圖網格的分界線重合情況 下的選擇性估計方法。然而，在實際應用中，用戶給定的空間查詢區域的四邊與直方圖網格 分界線重合的概率及低。如果簡單地將用戶給定的查詢區域映射到直方圖的某些格子上，其 估計結果集的大小往往與實際值相差較遠。“如何對空間查詢區域和CD直方圖查詢結果集的 大小進行修正，并使之更接近實際值”是空間直方圖在實際應用中面臨的重要難題。

2004年，Kim等人針對查詢區域的四邊與分界線不重合的問題，提出了兩種基于CD直 方圖選擇性估計的修正方法。其修正的方法之一是在原CD直方圖選擇性計算結果的基礎上 乘以查詢區域面積與查詢區域所覆蓋的直方圖格子面積之比。此方法蘊涵著一個假設：查詢 區域所覆蓋的多個格子區域內的矢量數據分布是均勻的，即空間對象的大小基本相同、分布 密度相對均勻。因此，對于分布不均勻的矢量數據此方法估計值的誤差較大。尤其當查詢區 域較大時，更難滿足上述假設，從而加大估計誤差。

針對此問題，Kim等人在原有4張CD直方圖的基礎上增加了1個iArea(i，j)的直方圖， iArea(i，j)用于反映第i行、第j列格子內空間對象所占面積與該格子面積之比；并在原CD 直方圖選擇性計算結果的基礎上乘以一種經iArea(i，j)和Area_i，j(Q)(第i行、第j列格子內空 間查詢區域所占面積與該格子面積之比)修正的概率值，如下面公式所示：