Query prunning using exterior tiles in an R-tree index

• US 7,219,108 B2
• Filed: 05/10/2004
• Issued: 05/15/2007
• 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: Kothuri, Ravi Kanth V., Ravada, Siva Kumar, Geringer, Daniel, Abugov, Daniel
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US10/841,540
• Publication Number:
  US 20040215641A1
• Time in Patent Office: 1,100 Days
• Field of Search: 707 1- 7, 707/100, 707/104.1, 382/261, 345/419, 345/441
• US Class Current: 707/754
• 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/954 Relational
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Determining relationships among objects represented in a database includes defining a plurality of tiles in the approximation of the first geometry by dividing the approximation of the first geometry in a first direction a plurality of times and dividing the approximation of the first geometry in a second direction perpendicular to the first direction a plurality of times. A second geometry is analyzed to determine if it fulfills a first filter condition with respect to any of the tiles defined in the approximation of the first geometry. If the second geometry fulfills the first filter condition with respect to any of the tiles defined in the first geometry carrying out a mathematical comparison of the first geometry and the second geometry.

Claims

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

providing a first filter operable to;

a plurality of tiles defined in the approximation of the first geometry by dividing the approximation of the first geometry in a first direction a plurality of times and dividing the approximation of the first geometry in a second direction perpendicular to the first direction the plurality of times;

if a second geometry fulfills a first filter condition with respect to any of the tiles defined in the approximation of the first geometry providing the first geometry and the second geometry to a second filter operable to;

carry out mathematical comparison of the first geometry and the second geometry; and

pass the second geometry to a result set based on the result of the mathematical comparison;

otherwise, excluding the second geometry from the result set.

2. The method according to claim 1, wherein the approximation of the first geometry comprises a minimum bounding rectangle of the first geometry.

3. The method according to claim 1, wherein the tiles are formed by recursively dividing the approximation of the first geometry into two parts in an x dimension and a y dimension.

4. The method according to claim 1, wherein the first filter condition comprises an intersection between at least one tile and the second geometry.

5. The method according to claim 1, wherein the second filter condition comprises an intersection between at least one tile interior to the first geometry and the second geometry.

6. The method according to claim 5, further comprising:

determining an approximation of the second geometry; and

defining a plurality of tiles in the approximation of the second geometry;

wherein determining if the second geometry fulfills the first filter condition comprises comparing the tiles of the second geometry with the tiles of the first geometry.

7. The method according to claim 6, wherein the approximation of the second geometry comprises a minimum bounding rectangle.

8. The method according to claim 1, further comprising:

ordering the tiles in the first dimension and the second dimension.

9. The method according to claim 1, wherein the first geometry comprises a query geometry and the second geometry comprises a data geometry.

10. The method according to claim 1, wherein the first filter condition comprises at least one member selected from the group comprising:

the second geometry lies entirely within the tiles defined in the approximation of the first geometry;

the second geometry intersects the tiles defined in the approximation of the first geometry; and

a border of the second geometry touches a border of the approximation of the first geometry.

11. The method according to claim 1, wherein one of the first object and the second object comprises an object in a database.

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

13. A computer-implemented method for determining relationships among objects represented in a database, the method comprising:

providing a first filter operable to;

receive an a minimum bounding rectangle defined for a first geometry having;

a plurality of tiles defined in the minimum bounding rectangle of he first geometry by recursively dividing the minimum bounding rectangle into two parts a plurality of times in an x-dimension and y-dimension;

if a second geometry fulfills a first filter condition with respect to any of the tiles defined in the approximation of the first geometry providing the first geometry and the second geometry to a second filter operable to;

carry out a mathematical comparison of the first geometry and the second geometry; and

pass the second geometry to a result set based on the result of the mathematical comparison;

otherwise, excluding the second geometry from the result set.

14. The computer implemented method according to claim 13, wherein the first filter condition comprises an intersection between at least one tile and the second geometry.

15. The computer implement method according to claim 13, wherein the first filter condition comprises at least one member selected from the group comprising:

the second geometry lies entirely within the tiles defined in the approximation of the first geometry;

the second geometry intersects the tiles defined in the approximation of the first geometry; and

a border of the second geometry touches a border of the approximation of the first geometry.

16. A computer program product for performing a process for 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

providing a first filter operable to;

receive an approximation defined for a first geometry having;

a plurality of tiles defined in the approximation of the first geometry by dividing the approximation of the first geometry in a first direction a plurality of times and dividing the approximation of the first geometry in a second direction perpendicular to the first direction the plurality of times;

if a second geometry fulfills a first filter condition with respect to any of the tiles defined in the approximation of the first geometry providing the first geometry and the second geometry to a second filter operable to;

carry out a mathematical comparison of the first geometry and the second geometry; and

pass the second geometry to a result set based on the result of the mathematical comparison;

otherwise, excluding the second geometry from the result set.

17. The computer program product according to claim 16, wherein the first filter condition comprises an intersection between at least one tile and the second geometry.

18. The a computer program product according to claim 16, wherein the tiles are formed by recursively dividing the approximation of the first geometry into two parts in an x dimension and a y dimension.

19. A system for performing a process for 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;

providing a first filter operable to;

receive an approximation defined for a first geometry having;

a plurality of tiles defined in the approximation of the first geometry by dividing the approximation of the first geometry in a first direction a plurality of times and dividing the approximation of the first geometry in a second direction perpendicular to the first direction the plurality of times;

if a second geometry fulfills a first filter condition with respect to any of the tiles defined in the approximation of the first geometry providing the first geometry and the second geometry to a second filter operable to;

carry out a mathematical comparison of the first geometry and the second geometry; and

pass the second geometry to a result set based on the result of the mathematical comparison;

otherwise, excluding the second geometry from the result set.

20. The system according to claim 19, wherein the first filter condition comprises at least one member selected from the group comprising:

the second geometry lies entirely within the tiles defined in the approximation of the first geometry;

the second geometry intersects the tiles defined in the approximation of the first geometry; and

a border of the second geometry touches a border of the approximation of the first geometry.