US6629094B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for rewriting relational database queries
Assignee: Workday Inc
•
Filing: 2000-09-01
•
Granted: 2003-09-30
•
Expires: 2020-09-01
Abstract
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.
Inventors
- 👤 Latha S. Colby
- 👤 Richard L. Cole
- 👤 Edward P. Haslam
- 👤 Nasi Jazayeri
- 👤 Galt Johnson
- 👤 William McKenna
- 👤 Lee E. Schumacher
- 👤 David G. Wilhite, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 20:28
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24539; G06F16/28; G06F16/283; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/954; Y10S707/956; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99941; Y10S707/99943; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
56 words
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.
Claim 2
Independent Claim
56 words
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.
Claim 3
Dependent Claim
15 words
The method of claim 1 , wherein the database query is a relational database query.
Claim 4
Dependent Claim
34 words
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.
Claim 5
Dependent Claim
36 words
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.
Claim 6
Dependent Claim
37 words
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.
Claim 7
Dependent Claim
57 words
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.
Claim 8
Dependent Claim
42 words
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 (*).
Claim 9
Dependent Claim
45 words
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.
Claim 10
Dependent Claim
45 words
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.
Claim 11
Dependent Claim
41 words
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.
Claim 12
Dependent Claim
37 words
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.
Claim 13
Dependent Claim
39 words
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.
Claim 14
Dependent Claim
33 words
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.
Claim 15
Dependent Claim
47 words
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.
Claim 16
Dependent Claim
35 words
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.
Claim 17
Dependent Claim
32 words
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.
Claim 18
Dependent Claim
40 words
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.
Claim 19
Dependent Claim
35 words
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.
Claim 20
Dependent Claim
25 words
The method of claim 18 , wherein rewriting of the query is performed if the query includes at least one of aggregation, distinct, and grouping.
Claim 21
Dependent Claim
34 words
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.
Claim 22
Dependent Claim
33 words
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.
Claim 23
Dependent Claim
30 words
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.
Claim 24
Dependent Claim
16 words
The method of claim 22 , wherein the derivation of the table occurs in real time.
Claim 25
Dependent Claim
15 words
The method of claim 1 , wherein the determination includes evaluating foreign key-primary key relationships.
Claim 26
Dependent Claim
28 words
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.
Claim 27
Dependent Claim
20 words
The method of claim 1 , wherein one of the functional dependencies is based on a foreign key/primary key relationship.
Claim 28
Dependent Claim
27 words
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.
Claim 29
Independent Claim
60 words
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.
Claim 30
Independent Claim
60 words
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.
Claim 31
Dependent Claim
67 words
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.
Claim 32
Dependent Claim
67 words
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.
Claim 33
Dependent Claim
38 words
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.
References Cited (Backward Citations)
US5369761A
Cited
US5367675A
Cited
US6430548B1
Cited
US5659725A
Cited
US5598559A
Cited
US5600829A
Cited
US5659728A
Cited
US6026390A
Cited
US6061676A
Cited
US5987450A
Cited
US5897632A
Cited
US6006214A
Cited
US6212524B1
Cited
US6334128B1
Cited
US5991754A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-09-29 | 2007-03-31 | 2007-09-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-09-29 | 2011-03-31 | 2011-09-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-09-29 | 2015-03-31 | 2015-09-30 | $7700.00 | Window Closed / Lapsed |