Query prunning using exterior tiles in an R-tree index

• US 20040215641A1
• Filed: 05/10/2004
• Published: 10/28/2004
• Est. Priority Date: 06/22/2001
• Status: Active Grant

• 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
• Granted Patent: US 7,219,108 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• 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 method for determining relationships among objects represented in a database, the method comprising:

defining an approximation of a first geometry;

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 the plurality of times;

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

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.

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 1, further comprising:

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

7. 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.

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

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 method for determining relationships among objects represented in a database, the method comprising:

defining a minimum bounding rectangle of a first geometry;

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

determining whether a second geometry intersects any of the tiles; and

if the second geometry intersects any of the tiles, carrying out a mathematical comparison of the first geometry and the second geometry.

14. 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

defining an approximation of a first geometry;

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 the plurality of times;

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

if the second geometry fulfills the first filter condition with respect to any of the tiles defined in the first geometrycarrying out a mathematical comparison of the first geometry and the second geometry.

15. 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;

defining an approximation of a first geometry;

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 the plurality of times;

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

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.