[發明專利]一種空間數據庫中分組反向輪廓查詢方法

有效

• 申請號: 201410007699.4
• 申請日: 2014-01-07
• 公開（公告）號: CN103778198B
• 公開（公告）日: 2017-04-12
• 發明（設計）人: 高云君;柳晴;苗曉曄;陳璐;趙靖文;秦旭
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天正專利事務所有限公司33201
• 代理人: 王兵,黃美娟

技術領域

本發明涉及數據庫的索引與查詢技術，特別是一種空間數據庫中分組反向輪廓查詢方法。

背景技術

空間數據庫通?；谕ㄓ脭祿旃芾硐到y構建。不同的空間數據庫系統實現時選取的數據庫管理系統平臺與操作系統平臺不盡相同?？臻g數據庫引擎是以屏蔽操作系統和數據庫管理系統差異為目的，在應用層和數據庫層之間構建基于高效空間搜索的數據訪問中間件，是向應用層提供數據存儲、高效檢索、數據管理、網絡通信、事務處理和簡單數據處理功能的程序集合。空間數據庫引擎基于傳統的關系數據庫，但它能對空間數據信息進行有效的處理和管理，并提供特定的空間數據關系運算和空間數據分析功能。

在所有空間數據庫的索引技術中，R樹及其變體因為簡單易用和有效性而受到廣泛地應用。R樹空間索引結構是一個高度平衡的數據結構，它是基于對經典的B⁺樹索引結構的改進與擴展，從而能夠有效地處理空間數據信息。R樹的每個結點包含一個矩形區域的索引碼，該矩形區域由對應結點的所有孩子結點的最小外包矩形嵌套組成，其中最小外包矩形的每一條邊都和一個全局坐標系的坐標軸平行，同時每個結點還包括一系列的子索引項，每個子索引項包括對應的子結點指針和子結點的矩形索引碼。

輪廓查詢問題也稱為極大向量問題，是一個典型的多目標優化問題，對它的研究最早可以追溯到1975年。具體而言，輪廓查詢是指從一個給定的空間對象集合S中選擇一個子集，該子集中的點都不能被S中的任意一個其他點所控制，滿足這個條件的點稱為輪廓點SP。反向輪廓查詢則是輪廓查詢的一個重要變體，它與輪廓查詢的執行立場剛好相反，目前已受到了專家學者們的重視。

在現實情況中，所給的數據之中可以根據某些屬性分成若干組。傳統的反向輪廓查詢只能在整個數據集上返回整體的反向輪廓。如果要返回每一組的反向輪廓，則要對每一組的數據都建立一棵R樹，然后在每一棵R樹上返回相應的結果，但這樣的查詢效率極低。

發明內容

本發明的目的在于提供一種空間數據庫中分組反向輪廓查詢方法。

本發明解決其技術問題采用技術方案的步驟如下：

步驟（1）：根據分組反向輪廓查詢本身的特性以及用戶的需求選用一個合適的數據庫管理系統；

步驟（2）：開發一個空間數據庫引擎，能與步驟1）中選用的數據庫管理系統平臺交互，并選用空間數據庫索引技術；

步驟（3）：開發一個用于分組反向輪廓查詢的分組引擎；

步驟（4）：在步驟（2）中構建的空間數據庫和步驟（3）中構建的分組引擎的基礎上實現各組全局輪廓計算引擎，包括第一層和第二層全局輪廓計算；

步驟（5）：開發一個全局輪廓比較引擎，對步驟（4）中得到的結果進行驗證；

步驟（6）：對步驟（5）中的結果進行分組，以得到最終的查詢結果。

所述的步驟（1）中選用的數據庫管理系統平臺應支持基本的SQL查詢，目前大部分的數據庫管理系統都滿足這一要求，像Oracle、SQL?Server、MySQL。

所述的步驟（2）中的空間數據庫引擎是構建在應用層和數據庫層之間的一種中間件，它必須與步驟（1）中選用的數據庫管理系統相互配合，接受上層查詢引擎的命令并轉化為SQL語句在數據庫管理系統中運行，空間數據庫索引一般選用R樹。

所述的步驟（3）中的分組引擎，它主要根據對象原有的屬性對其進行分組，需考慮兩種情況：

3.1）該結點是中間索引結點，不做任何操作，因為中間結點所包含的對象可能來自不同組；

3.2）該結點是數據索引結點，那么將其分到相應的組中。

所述的步驟（4）中計算各組全局輪廓的方法如下：

4.1）初始化一個最小堆，并將根結點放入堆，該最小堆根據R樹索引結點到查詢點的最小距離進行排序；初始化兩個對象集合，一個用來保存第一層全局輪廓，另外一個用來保存第二層全局輪廓；

4.2）如果最小堆為空，則過濾算法結束，返回兩個對象集合，即第一層和第二層全局輪廓；否則取出堆頂元素；

4.3）計算取出的堆頂元素被該組當前已經找到的第一層和第二層全局輪廓點所全局控制的次數。對于R樹索引結點被全局控制的次數，需考慮兩種情況：

a）該結點是中間索引結點，這種狀況下根據其被全局控制的次數分為兩種情況：

i）該中間結點最多只被一個該組第一層全局輪廓點所全局控制，那么將其索引孩子結點都加入到最小堆中，并跳到4.2）。