[發明專利]有效地尋找空間得分最佳的實體

有效

• 申請號: 201380047822.9
• 申請日: 2013-04-11
• 公開（公告）號: CN104641373B
• 公開（公告）日: 2018-09-07
• 發明（設計）人: K.A.本特利;R.B.本特利
• 申請（專利權）人: 本特利系統有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 張凌苗;陳嵐

在一個實施例中，在具有空間索引的數據庫中尋找滿足空間標準和實體過濾標準兩者的特定數量的最佳實體。針對其邊界框符合空間標準的在空間索引中的目標集中的每個，計算目標的空間得分。如果空間得分小于在最佳實體的當前圖中的最小空間得分且如果當前圖是滿的，則目標被排除在進一步考慮之外。如果空間得分不小于最小空間得分，則當目標是符合實體過濾標準的實體時，當前圖被更新以存儲所述實體和該實體的空間得分。當在空間索引中的目標中的每個已經經受了測試或被排除在考慮之外時，將當前圖返回作為最終結果。

技術領域

本公開一般地涉及在關系型數據庫中的空間數據的操縱，并且更具體地涉及基于空間和實體過濾標準兩者有效地尋找實體。

背景技術

關系型數據庫是在行和列的表格中存儲相關的數據的電子數據庫，并且允許在具有匹配字段的表格之間建立鏈接使得可以同時詢問多個表格。許多關系型數據庫采用某個版本的SQL語言，該SQL語言是適于管理數據的專用編程語言。SQL代碼可以由關系型數據庫系統來實現，所述關系型數據庫系統執行作為分離的過程并且由客戶端應用訪問。例如，SQL代碼可以由可從開源獲得的MySQL?數據庫系統、可從Oracle公司獲得的Oracle數據庫或者可從Microsoft公司獲得的Microsoft SQL Server數據庫系統執行。替代地，SQL代碼可以由通過自持的編程庫實現的關系型數據庫系統實現，所述自持的編程庫可以被集成在客戶端應用其自身之內。例如，SQL代碼可以由在公共域中可獲得的SQLite?嵌入式SQL數據庫系統來執行。

除其他使用之外，關系型數據庫還可以被利用來存儲描述在多維空間中的實體的位置、形狀和方向的空間數據。實體的位置、形狀和方向通常使用空間參考系統表示。除其他功能之外，空間參考系統還提供坐標系（例如，笛卡爾坐標系），通過其可以限定空間信息。例如，在實體上的點可由x軸、y軸和z軸坐標限定。

存儲在關系型數據庫中的空間數據通常使用被設計成加快空間詢問的空間索引來進行索引。經常，空間索引被結構化為R樹（R-tree）。R樹是以使用邊界框（bounding box）為前提的一種平衡樹數據結構。邊界框是多維空間的區域，所述多維空間的區域從相關實體或實體群組的最小程度跨越到相關實體或實體群組的最大程度。通常，邊界框與所采用的坐標系的軸線對齊，并且因此被稱為軸對齊的邊界框（AABB）。例如，在2D空間數據中，特定實體的邊界框可以是從實體的最小x軸坐標跨越到其最大x軸坐標并且從其最小y軸坐標跨越到其最大y軸坐標的矩形。在3D空間數據的情況下，特定實體的邊界框可以是從所述實體的最小x軸坐標跨越到其最大x軸坐標、從其最小y軸坐標跨越到其最大y軸坐標并且從其最小z軸坐標跨越到其最大z軸坐標的矩形棱柱。

在其最低級別處的R樹具有包括一個或多個單獨實體的葉節點。如果葉節點包括單個實體，則該葉節點的邊界框僅僅是該單獨實體自身的邊界框。如果葉節點包括多個實體，則該葉節點的邊界框是包圍了被包括在該葉節點中的單獨實體的所有邊界框的最小尺寸的框。在較高的級別處，R樹包括表示葉節點的群組的內部節點或者其他內部節點。每個內部節點的邊界框是包圍了該群組的所有邊界框的最小尺寸的框。在R樹的最高級別處是根節點。根節點的邊界框是包圍了由R樹進行索引的所有實體的所有邊界框的最小尺寸的框。

使用R樹的搜索一般在根節點處開始，并且通過樹的各級別向下進行。例如，如果用戶期望尋找定位于感興趣的區域（即，詢問框）內的實體，則基于該詢問框啟動搜索詢問。在根節點處，做出哪些較低級別的內部節點具有與詢問框重疊的邊界框的確定。搜索然后進行到這些較低級別的內部節點，在其處確定哪些更低級別的內部節點具有與詢問框重疊的邊界框。過程沿R樹往下繼續，通過與可能存在的級別一樣多的級別，直到最終遇到葉節點為止。相對于詢問框測試被包括在所遇到的葉節點中的單獨實體的邊界框，并且如果它們的邊界框與詢問框重疊，則將相應的實體放置到針對搜索詢問的結果集合中。