Query pruning using interior rectangles in an R-tree index

• US 7,080,065 B1
• Filed: 06/22/2001
• Issued: 07/18/2006
• Est. Priority Date: 06/22/2001
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ravada, Siva, Kothuri, Ravi Kanth V., Geringer, Daniel
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US09/886,487
• Time in Patent Office: 1,852 Days
• Field of Search: 707/100, 707 1- 6, 707/104.1, 345/441
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/24558 Binary matching operations
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

To determine relationships among objects represented in a database at least one interior rectangle lying entirely within a first geometric shape is define. A minimum bounding area for the first geometry and a minimum bounding area for a second geometry are defined and compared with one another to determine if the second geometry fulfills a primary filter condition of an interaction between the first and second geometries. Based on the fulfillment of the primary condition by the second geometry, it is determined whether an intermediate filter condition of interaction between the first and second geometries is fulfilled by analyzing the distribution of the second geometry with respect to at least one interior rectangle within the first geometry. It is determined whether the second geometry fulfills a secondary filter condition by comparing the second geometry with the first geometry if the second geometry fulfills the primary filter condition.

Claims

1. A computer implemented method for determining relationships among objects represented in a database, the method comprising the steps of:

receiving a query including at least a first geometry and a desired relationship between the first geometry and a second geometry;

providing the query to a primary filter operable to;

define at least one interior rectangle that lies entirely within the first geometry;

define a minimum bounding rectangle for the first geometry;

define a minimum bounding rectangle for the second geometry; and

compare the minimum bounding rectangle for the first geometry with the minimum bounding rectangle for the second geometry to determine if the second geometry fulfills a primary filter condition comprising an interaction of the first geometry and the second geometry;

if the second geometry fulfills the primary filter condition, providing the first geometry and the second geometry to an intermediate filter operable to;

determine whether the second geometry fulfills an intermediate filter condition comprising an interaction of the at least one interior rectangle within the first geometry and the minimum bounding rectangle for the second geometry by analyzing the distribution of the minimum bounding rectangle for the second geometry with respect to the at least one interior rectangle within the first geometry;

if the second geometry is confirmed as fulfilling the intermediate filter condition, including the second geometry in a final result set of objects that satisfy the desired relationship;

if the second geometry is confirmed as deviating from the intermediate filter condition, excluding the second geometry from the final result set that satisfy the desired relationship;

otherwise, providing the first geometry and the second geometry to a secondary filter operable to;

determine whether the second geometry fulfills a secondary filter condition by comparing the second geometry with the first geometry; and

if the second geometry fulfills the secondary filter condition, including the second geometry in the final result set of objects that satisfy the desired relationship.

2. A computer program product for performing a process of determining relationships among objects represented in a database, comprising:

a computer readable medium; and

computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of;

receiving a query including at least a first geometry and a desired relationship between the first geometry and a second geometry;

providing the query to a primary filter operable to;

define at least one interior rectangle that lies entirely within the first geometry;

define a minimum bounding rectangle for the first geometry;

define a minimum bounding rectangle for the second geometry; and

compare the minimum bounding rectangle for the first geometry with the minimum bounding rectangle for the second geometry to determine if the second geometry fulfills a primary filter condition comprising an interaction of the first geometry and the second geometry;

if the second geometry fulfills the primary filter condition, providing the first geometry and the second geometry to an intermediate filter operable to;

determine whether the second geometry fulfills an intermediate filter condition comprising an interaction of the at least one interior rectangle within the first geometry and the minimum bounding rectangle for the second geometry by analyzing the distribution of the minimum bounding rectangle for the second geometry with respect to the at least one interior rectangle within the first geometry;

if the second geometry is confirmed as fulfilling the intermediate filter condition, including the second geometry in a final result set of objects that satisfy the desired relationship;

if the second geometry is confirmed as deviating from the intermediate filter condition, excluding the second geometry from the final result set that satisfy the desired relationship;

otherwise, providing the first geometry and the second geometry to a secondary filter operable to;

determine whether the second geometry fulfills a secondary filter condition by comparing the second geometry with the first geometry; and

if the second geometry fulfills the secondary filter condition, including the second geometry in the final result set of objects that satisfy the desired relationship.

3. A system for performing a process of determining relationships among objects represented in a database, comprising:

a processor operable to execute computer program instructions; and

a memory operable to store computer program instructions executable by the processor, for performing the steps of;

receiving a query including at least a first geometry and a desired relationship between the first geometry and a second geometry;

providing the query to a primary filter operable to;

define at least one interior rectangle that lies entirely within the first geometry;

define a minimum bounding rectangle for the first geometry;

define a minimum bounding rectangle for the second geometry; and

compare the minimum bounding rectangle for the first geometry with the minimum bounding rectangle for the second geometry to determine if the second geometry fulfills a primary filter condition comprising an interaction of the first geometry and the second geometry;

if the second geometry fulfills the primary filter condition, providing the first geometry and the second geometry to an intermediate filter operable to;

determine whether the second geometry fulfills an intermediate filter condition comprising an interaction of the at least one interior rectangle within the first geometry and the minimum bounding rectangle for the second geometry by analyzing the distribution of the minimum bounding rectangle for the second geometry with respect to the at least one interior rectangle within the first geometry;

if the second geometry is confirmed as fulfilling the intermediate filter condition, including the second geometry in a final result set of objects that satisfy the desired relationship;

if the second geometry is confirmed as deviating from the intermediate filter condition, excluding the second geometry from the final result set that satisfy the desired relationship;

otherwise, providing the first geometry and the second geometry to a secondary filter operable to;

determine whether the second geometry fulfills a secondary filter condition by comparing the second geometry with the first geometry; and

if the second geometry fulfills the secondary filter condition, including the second geometry in the final result set of objects that satisfy the desired relationship.

4. A computer implemented method for determining relationships among objects represented in a database, the method comprising the steps of:

receiving a query including at least a first geometry and a desired relationship between the first geometry and a second geometry;

providing the query to a primary filter operable to;

define at least one interior geometric shape that lies entirely within the first geometry;

define an approximation of the first geometry;

define an approximation of the second geometry; and

compare the approximation of the first geometry with the approximation of the second geometry to determine if the second geometry fulfills a primary filter condition comprising an interaction of the first geometry and the second geometry;

if the second geometry fulfills the primary filter condition, providing the first geometry and the second geometry to an intermediate filter operable to;

determine whether the second geometry fulfills an intermediate filter condition comprising an interaction of the first geometry and the second geometry by analyzing the distribution of the approximation of the second geometry with respect to the at least one interior geometric shape within the first geometry;

if the second geometry is confirmed as fulfilling the intermediate filter condition, including the second geometry in a final result set of objects that satisfy the desired relationship;

if the second geometry is confirmed as deviating from the intermediate filter condition, excluding the second geometry from the final result set that satisfy the desired relationship;

otherwise, providing the first geometry and the second geometry to a secondary filter operable to;

determine whether the second geometry fulfills a secondary filter condition by comparing the second geometry with the first geometry; and

if the second geometry fulfills the secondary filter condition, including the second geometry in the final result set of objects that satisfy the desired relationship.

5. A system for performing a process of determining relationships among objects represented in a database, comprising:

a processor operable to execute computer program instructions; and

a memory operable to store computer program instructions executable by the processor, for performing the steps of;

receiving a query including at least a desired relationship between a first geometry and a second geometry; and

providing the first geometry and the second geometry to a filter; and

the filter operable to;

determine whether the second geometry fulfills a filter condition comprising an interaction of at least one interior rectangle defined for the first geometry that lies entirely within the first geometry and a minimum bounding rectangle defined for the second geometry by analyzing the distribution of the minimum bounding rectangle for the second geometry with respect to the at least one interior rectangle within the first geometry;

include the second geometry in a final result set of objects that satisfy the desired relationship if the second geometry is confirmed as fulfilling the filter condition;

exclude the second geometry from the final result set the satisfy the desired relationship if the second geometry is confirmed as deviating from the filter condition; and

provide the first geometry and the second geometry to a secondary filter if the second geometry cannot be confirmed as fulfilling, or deviating from, the filter condition.

6. A computer program product for performing a process of determining relationships among objects represented in a database, comprising:

a computer readable medium; and

computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of;

receiving a query including at least a desired relationship between a first geometry and a second geometry; and

providing the first geometry and the second geometry to a filter; and

the filter operable to;

determine whether the second geometry fulfills a filter condition comprising an interaction of at least one interior rectangle defined for the first geometry that lies entirely within the first geometry and a minimum bounding rectangle defined for the second geometry by analyzing the distribution of the minimum bounding rectangle for the second geometry with respect to the at least one interior rectangle within the first geometry;

include the second geometry in a final result set of objects that satisfy the desired relationship if the second geometry is confirmed as fulfilling the filter condition;

exclude the second geometry from the final result set the satisfy the desired relationship if the second geometry is confirmed as deviating from the filter condition; and

provide the first geometry and the second geometry to a secondary filter if the second geometry cannot be confirmed as fulfilling, or deviating from, the filter condition.

7. A computer implemented method for determining relationships among objects represented in a database, the method comprising the steps of:

receiving a query including at least a desired relationship between a first geometry and a second geometry; and

providing the first geometry and the second geometry to a filter operable to;

determine whether the second geometry fulfills a filter condition comprising an interaction of at least one interior rectangle defined for the first geometry that lies entirely within the first geometry and a minimum bounding rectangle defined for the second geometry by analyzing the distribution of the minimum bounding rectangle for the second geometry with respect to the at least one interior rectangle within the first geometry; and

if the second geometry is confirmed as fulfilling the filter condition, including the second geometry in a final result set of objects that satisfy the desired relationship;

if the second geometry is confirmed as deviating from the filter condition, excluding the second geometry from the final result set that satisfy the desired relationship;

otherwise, providing the first geometry and the second geometry to a secondary filter.

8. The method according to claim 7, wherein the first geometry and the second geometry comprise data geometries stored in a database.

9. The method according to claim 7, wherein the first geometry comprises a data geometry stored in a database and the second geometry comprises a query geometry.

10. The method according to claim 9, wherein determining whether the first geometry and the second geometry fulfill the secondary filter condition comprises mathematically comparing the fist geometry and the second geometry.

11. The method according to claim 9, wherein the secondary filter condition is fulfilled if the first geometry and the second geometry overlap.

12. The method according to claim 9, wherein the secondary filter condition is fulfilled if a boundary of the first geometry touches a boundary of the second geometry.

13. The method according to claim 9, wherein the secondary filter condition is fulfilled if the first geometry and the second geometry intersect.

14. A method according to claim 9, further comprising providing the first geometry and the second geometry to a secondary filter operable to:

determine whether the second geometry fulfills a secondary filter condition by comparing the second geometry with the first geometry; and

if the second geometry fulfills the secondary filter condition, including the second geometry in the final result set of objects that satisfy the desired relationship, otherwise excluding the second geometry from the final result set of objects that satisfy the desired relationship.

15. The method according to claim 7, wherein the first geometry is larger than the second geometry.

16. The method according to claim 7, wherein minimum bounding rectangles are defined for a plurality of second geometries.

17. The method according to claim 7, wherein the first geometry is a collection of geometries each including a separate interior.

18. The method according to claim 7, wherein providing the first geometry and the second geometry to the filter is in response to the second geometry fulfilling a primary filter condition comprising any intersection between the minimum bounding rectangle for the first geometry and a minimum bounding rectangle defined for the second geometry.

19. The method according to claim 7, wherein the at least one interior rectangle that lies entirely within the first geometry is defined by dividing the dividing the minimum bounding rectangle for the first geometry into a plurality of pieces and defining a largest possible interior rectangle lying completely within the first geometry and the plurality of pieces.

20. The method according to claim 19, wherein the plurality of pieces are rectangles.

21. The method according to claim 20, wherein the plurality of pieces are five rectangles having similar sizes.

22. The method according to claim 20, wherein the minimum bounding rectangle for the first geometry is divided into four rectangles having similar sizes.

23. The method according to claim 7, wherein a minimum bounding rectangle defined for the second geometry comprises a smallest rectangle that at most intersects a boundary of the second geometry.

24. The method according to claim 7, wherein the filter condition is fulfilled if a minimum bounding rectangle defined for the second geometry lies entirely within the minimum bounding rectangle of the first geometry.

25. The method according to claim 7, wherein the primary filter condition is one of:

a minimum bounding rectangle defined for the second geometry lying entirely within the minimum bounding rectangle of the first geometry;

the minimum bounding rectangle of the second geometry intersecting the minimum bounding rectangle of the first geometry;

a border of the minimum bounding rectangle of the second geometry touching a border of the minimum bounding rectangle of the first geometry;

the minimum bounding rectangle of the first geometry lying entirely within the minimum bounding rectangle of the second geometry; and

the minimum bounding rectangle of the second geometry is disjoint from the minimum bounding rectangle of the first geometry.

26. The method according to claim 7, wherein the first geometry is divided into five interior rectangles.

27. The method according to claim 7, wherein one of the first geometry and the second geometry comprise objects in a database.

28. The method according to claim 27, wherein the objects in the database comprises locations in a geographic region.

29. The method according to claim 27, wherein the database is organized in an R-tree hierarchy.

30. The method according to claim 27, wherein the database comprises a spatial database.

31. The method according to claim 27, wherein the first geometry and the second geometry comprise objects on a surface.

32. The method according to claim 31, wherein the database stores exact geometries and approximations of geometries.

33. The method according to claim 7, wherein at least one of the first geometry and the second geometry is convex.

34. The method according to claim 33, wherein at least one of the first geometry and the second geometry comprises a plurality of separate interiors.

35. The method according to claim 7, wherein at least one of the first geometry and the second geometry is concave.

36. A computer implemented method for determining relationships among objects represented in a database, the method comprising the steps of:

receiving a query including at least a desired relationship between a first geometry and a second geometry;

providing the first geometry and the second geometry to a filter operable to;

determine whether the second geometry fulfills a filter condition comprising an interaction of at least one interior rectangle defined for the first geometry that lies entirely within the first geometry and a minimum bounding rectangle defined for the second geometry by analyzing the distribution of the minimum bounding rectangle for the second geometry with respect to the at least one interior rectangle within the first geometry; and

if the second geometry is confirmed as fulfilling the filter condition, including the second geometry in a final result set of objects that satisfy the desired relationship;

if the second geometry is confirmed as deviating from the filter condition, excluding the second geometry from the final result set that satisfy the desired relationship;

otherwise, providing the first geometry and the second geometry to a secondary filter.

37. The method according to claim 36, further comprising providing the query to a primary filter operable to:

define at least one interior rectangle that lies entirely within the first geometry;

define a minimum bounding rectangle for the first geometry; and

define a minimum bounding rectangle for the second geometry.

38. The method according to claim 37, wherein the primary filter is operable to compare the minimum bounding rectangle for the first geometry with the minimum bounding rectangle for the second geometry to determine if the second geometry fulfills a primary filter condition comprising an interaction of the first geometry and the second geometry.

39. A method according to claim 38, wherein the secondary filter is operable to:

determine whether the second geometry fulfills a secondary filter condition by comparing the second geometry with the first geometry; and

if the second geometry fulfills the secondary filter condition, including the second geometry in the final result set of objects that satisfy the desired relationship, otherwise excluding the second geometry from the final result set of objects that satisfy the desired relationship.

40. The method according to claim 36, wherein at least one of the first geometry and the second geometry is convex.

41. The method according to claim 40, wherein at least one of the first geometry and the second geometry comprises a plurality of separate interiors.

42. The method according to claim 36, wherein at least one of the first geometry and the second geometry is concave.

43. The method according to claim 42, wherein concave geometries are approximated utilizing convex pieces.

44. The method according to claim 42, wherein concave geometries are approximated utilizing tiles.

45. The method according to claim 44, wherein a minimum bounding rectangle is tiled and tiles interior to the geometry are identified.

46. The method according to claim 44, wherein the tiling level is 5.

47. The method according to claim 44, wherein the tiling level is 4.

48. The method according to claim 44, wherein the tiling level is 3.

49. The method according to claim 44, further comprising determining whether a primary filter condition is fulfilled by comparing interior tiles.

50. The method according to claim 42, wherein the approximation of the first geometry comprises a minimum bounding rectangle and an approximation defined for the second geometry comprises a minimum bounding rectangle and wherein comparing the interior tiles comprises:

dividing the second geometry minimum bounding rectangle into tiles;

assigning X and Y values to the tiles;

determining which tiles lie interior to the second geometry;

determining X and Y location of each tile;

storing the interior tiles in an array ordered first by X location;

storing the interior tiles in an array ordered first by Y location; and

comparing at least one of the tiles or the minimum bounding rectangle of the first geometry with the interior tiles of the second geometry to determine the relationships among the geometries.

51. The method according to claim 50, wherein comparing the minimum bounding rectangle of the first geometry with the interior tiles of the second geometry comprises determining whether each side of the minimum bounding rectangle of first geometry is inside the interior tiles of the second geometry which comprises:

determining X and Y locations within the tiles of corners of the minimum bounding rectangle of the first geometry;

determining X and Y locations within the tiles of second geometry for two corners of each side of the first geometry; and

determining whether all tiles between the two corners of each side of the first geometry are interior to the second geometry by comparing a difference in an x-location or a y-locations of the two corners to the number of interior tiles between these two corners.

52. The method according to claim 51, wherein whether the x-location or the y-location is compared depends upon whether the side is parallel to y-axis or x-axis.

53. The method according to claim 51, wherein the second geometry is not a simple polygon.

54. The method according to claim 51, wherein the second geometry is a compound geometry comprising multiple polygons or a geometry comprising holes, and wherein determining if the minimum bounding rectangle of the first geometry is interior to the interior tiles of second geometry by comparing the interior of the minimum bounding rectangle of first geometry to the interior tiles of second geometry.

55. The method according to claim 50, wherein comparing the minimum bounding rectangle of the first geometry with the interior tiles of the second geometry comprises determining whether each side of the minimum bounding rectangle of first geometry is inside the interior tiles of the second geometry which comprises:

determining X and Y locations within the tiles of corners of the minimum bounding rectangle of the first geometry;

determining X and Y locations within the tiles of second geometry for two corners of line interior to the MBR of the first geometry; and

determining whether all tiles between the two corners any line interior to the MBR of the first geometry are interior to the second geometry by comparing a difference in an x-location or a y-locations of the two corners to the number of interior tiles between these two corners.