System and method for rewriting relational database queries

• US 6,629,094 B1
• Filed: 09/01/2000
• Issued: 09/30/2003
• Est. Priority Date: 03/27/1998
• Status: Expired due to Term

• Current Assignee: Workday Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: McKenna, William, Schumacher, Lee E., Cole, Richard L., Johnson, Galt, Colby, Latha S., Wilhite, David G. Jr., Haslam, Edward P., Jazayeri, Nasi
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US09/654,208
• Time in Patent Office: 1,124 Days
• Field of Search: 707/1-7, 707/100-104
• US Class Current: 707/713
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and method for answering a relational database query is presented. According to an embodiment of the present invention, a database query is received. It is then determined whether that query can be rewritten in such a manner as to be able to utilize a precomputed view, such that an answer to the rewritten query is equivalent to an answer to the original query. If the query can be rewritten, it is determined whether the rewritten query can more efficiently derive the answer than the original query. The query which has the most efficiently derived answer is the query which is utilized to derive that answer.

Claims

1. A method for answering a database query comprising the acts of:

receiving a database query;

determining if the database query should be rewritten; and

rewriting the database query by utilizing functional dependencies, the rewriting being performed if it is determined that the query should be rewritten, and wherein each of the functional dependencies comprises a constraint.

2. The method of claim 1, wherein the database query is a relational database query.

3. The method of claim 1, wherein the step of determining if the query should be rewritten includes a substep of determining if a first precomputed view may be utilized to rewrite the query.

4. The method of claim 3, wherein the substep of determining if the first precomputed view may be utilized to rewrite the query further includes a substep of determining whether the query includes a select statement.

5. The method of claim 3, wherein the substep of determining if the first precomputed view may be utilized to rewrite the query further includes a substep of determining whether the first precomputed view matches the query.

6. The method of claim 3, wherein the substep of determining if the first precomputed view may be utilized to rewrite the query further includes a substep of determining whether at least one aggregate expression in the query is defined over a table, wherein the table is referenced by both the query and the first precomputed view.

7. The method of claim 3, wherein the substep of determining if the first precomputed view may be utilized to rewrite the query further includes a substep of determining whether at least one aggregate expression in the query is a count (*).

8. The method of claim 3, wherein the substep of determining if the first precomputed view may be utilized to rewrite the query further includes a substep of determining if at least one grouping expression of the query and the first precomputed view is acceptable.

9. The method of claim 3, wherein the substep of determining if the first precomputed view may be utilized to rewrite the query further includes a substep of determining if at least one column reference of the query and the first precomputed view is acceptable.

10. The method of claim 3, wherein the substep of determining if the first precomputed view may be utilized to rewrite the query further includes a substep of determining if at least one aggregate expression included in the query is acceptable.

11. The method of claim 3, further including a substep of determining if a second precomputed view may be utilized to rewrite the query if the first precomputed view may not be used to rewrite the query.

12. The method of claim 1, wherein the step of determining if the query should be rewritten includes a substep of determining if answering a first rewritten query is estimated to be more cost effective than answering the query.

13. The method of claim 12, further including a substep of utilizing the first rewritten query if answering the first rewritten query is estimated to be more cost effective than answering the query.

14. The method of claim 12, further including a substep of determining if answering a second rewritten query is estimated to be more cost effective than answering the query, if answering the first rewritten query is not estimated to be more cost effective than answering the query.

15. The method of claim 1, wherein the step of determining if the query should be rewritten includes a substep of determining an estimated most cost effective rewritten query from a plurality of rewritten queries.

16. The method of claim 1, further including a substep of determining if answering the estimated most cost effective rewritten query is estimated to be more cost effective than answering the query.

17. The method of claim 16, further including a substep of utilizing of the estimated most cost effective rewritten query if answering the estimated most cost effective rewritten query is estimated to be more cost effective than answering the query.

18. The method of claim 1, wherein the step of determining if the query should be rewritten includes a sub step of determining if the query includes at least one of aggregation, distinct, and grouping.

19. The method of claim 18, wherein rewriting of the query is performed if the query includes at least one of aggregation, distinct, and grouping.

20. The method of claim 1, wherein the query includes at least one subquery, and wherein the rewriting of the query includes a substep of recursively attempting to rewrite the at least one subquery.

21. The method of claim 1, wherein the predefined hierarchy of data allows a rollup of aggregates on points in a dimension to other points of courser coarser granularity in the same dimension.

22. The method of claim 1, wherein the step of rewriting the query includes a substep of deriving a table to facilitate utilizing a precomputed view to rewrite the query.

23. The method of claim 22, wherein the derivation of the table occurs in real time.

24. The method of claim 1, wherein the determination includes evaluating foreign key-primary key relationships.

25. The method of claim 1, wherein one of the functional dependencies is from a primary key of a database table to a column in the database table.

26. The method of claim 1, wherein one of the functional dependencies is based on a foreign key/primary key relationship.

27. The method of claim 1, wherein the query includes one or more subqueries, and wherein the rewriting step comprises rewriting only a portion of the query.

28. A system for answering a database query, the system comprising:

means for receiving a database query;

means for determining if the query should be rewritten; and

means for rewriting the database query by utilizing functional dependencies, the rewriting being performed if it is determined that the query should be rewritten, and wherein each of the functional dependencies comprises a constraint.

29. A computer program product, for answering a database query, the computer program product comprising:

computer code for receiving a database query;

computer code for determining if the query should be rewritten; and

computer code for rewriting the database query by utilizing functional dependencies, the rewriting being performed if it is determined that the query should be rewritten, and wherein each of the functional dependencies comprises a constraint.

30. The computer program product of claim 29, wherein the computer readable medium is selected from the group consisting of CD-ROM, floppy disk, tape, flash memory, system memory, hard drive, and data signal embodied in a carrier wave.