US5659725A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Query optimization by predicate move-around
Assignee: Nokia of America Corp
•
Filing: 1994-06-06
•
Granted: 1997-08-19
•
Expires: 2014-06-06
Abstract
Abstract Query optimization which is done by making a graph of the query and moving predicates around in the graph so that they will be applied early in the optimized query generated from the graph. Predicates are first propagated up from child nodes of the graph to parent nodes and then down into different child nodes. After the predicates have been moved, redundant predicates are detected and removed. Predicates are moved through aggregation operations and new predicates are deduced from aggregation operations and from functional dependencies. The optimization is not dependent on join order and works where nodes of the graph cannot be merged.
Inventors
- 👤 Alon Yitzchak Levy
- 👤 Inderpal Singh Mumick
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 18:46
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24537; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99935
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
181 words
A method of operation of a data base system for optimizing a query having predicates applicable to attributes involved in the query, the method comprising the steps of: making a query graph data structure for the query by creating a label with at least one predicate applicable to the attributes mentioned in at least one node; in a parent node of the query graph data structure, inferring a first at least one new predicate in the parent node's label from a predicate in a label belonging to any child node of the parent, and propagating the inferred first at least one new predicate to the parent node; in a child node of the query graph data structure, inferring a second at least one new predicate in the child node's label from a predicate in a label belonging to any parent of the node and propagating the inferred second at least one new predicate to children of the parent node; and generating an optimized query from the query graph data structure by removing from the query graph data structure any redundant predicates.
Claim 2
Independent Claim
181 words
A method of operation of a data base system for optimizing a query having predicates applicable to attributes involved in the query, the method comprising the steps of: making a query graph data structure for the query by creating a label with at least one predicate applicable to the attributes mentioned in at least one node; in a parent node of the query graph data structure, inferring a first at least one new predicate in the parent node's label from a predicate in a label belonging to any child node of the parent, and propagating the inferred first at least one new predicate to the parent node; in a child node of the query graph data structure, inferring a second at least one new predicate in the child node's label from a predicate in a label belonging to any parent of the node and propagating the inferred second at least one new predicate to children of the parent node; and generating an optimized query from the query graph data structure by removing from the query graph data structure any redundant predicates.
Claim 3
Dependent Claim
24 words
The method set forth in claim 1 further comprising the step of: reducing the number of the predicates in the query graph data structure.
Claim 4
Dependent Claim
29 words
The method set forth in claim 2 wherein: the step of reducing the number of the predicates reduces the predicates such that no predicate is applied more than once.
Claim 5
Dependent Claim
34 words
The method set forth in claim 2 wherein the step of reducing comprises the step of: removing any predicate from a given node's label which is applied at a descendant of the given node.
Claim 6
Dependent Claim
35 words
The method set forth in either claim 2 or claim 4 wherein the step of reducing comprises the step of: removing any predicate in a label which is implied by another predicate in the label.
Claim 7
Dependent Claim
89 words
The method set forth in either claim 1 or claim 2 wherein: the step of inferring a first at least one new predicate in the parent node's label is repeatedly performed beginning with a child node which is a leaf node and ending when the parent node has no parent; and the step of inferring a second at least one new predicate in the child node's label is repeatedly performed beginning with a parent node which has no parent and ending when the child node is a leaf node.
Claim 8
Dependent Claim
80 words
The method set forth in either claim 1 or claim 2 wherein: each node of the query graph data structure represents a computation in the query; the predicate used to infer the first at least one new predicate is a predicate on an exported attribute, the exported attribute appearing in the result of the computation represented by the child node; and the predicate used to infer the second at least one new predicate is a predicate on an exported attribute.
Claim 9
Dependent Claim
48 words
The method set forth in claim 7 wherein the step of inferring the first at least one new predicate from the predicate on the exported attribute comprises: applying the predicate on the exported attribute to a local attribute local to the node which corresponds to the exported attribute.
Claim 10
Dependent Claim
48 words
The method set forth in claim 7 wherein the step of inferring the second at least one new predicate from the predicate on the exported attribute comprises: applying the predicate on the exported attribute to a local attribute local to the node which corresponds to the exported attribute.
Claim 11
Dependent Claim
37 words
The method set forth in claim 1 or claim 2 wherein: in the step of inferring a first at least one new predicate, the predicate on the label belonging to the child node includes an aggregation operation.
Claim 12
Dependent Claim
47 words
The method set forth in claim 10 wherein the step of inferring a first at least one new predicate comprises the step of: inferring the first at least one new predicate such that the first at least one new predicate limits the result of the aggregation operation.
Claim 13
Dependent Claim
39 words
The method set forth in claim 1 or claim 2 wherein: in the step of inferring a second at least one new predicate, the predicate on the label belonging to the parent of the node includes an aggregation operation.
Claim 14
Dependent Claim
47 words
The method set forth in claim 10 wherein the step of inferring a second at least one new predicate comprises the step of: inferring the second at least one new predicate such that the second at least one new predicate limits the result of the aggregation operation.
Claim 15
Dependent Claim
36 words
The method set forth in claim 1 or claim 2 further comprising the step performed in the parent node of: adding a third at least one new predicate which is implied by predicates in the label.
Claim 16
Dependent Claim
38 words
The method set forth in either claim 1 or claim 2 wherein the step making a query graph data structure further comprises the step of: inferring a predicate from a function on an attribute of a base relation.
Claim 17
Dependent Claim
36 words
The method set forth in claim 1 or claim 2 further comprising the step performed in the child node of: adding a fourth at least one new predicate which is implied by predicates in the label.
Claim 18
Dependent Claim
28 words
The method set forth in either claim 1 or 2 wherein the step of removing the predicates: reduces the number of predicates to an equivalent smaller number thereof.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-08-18 | 2001-02-17 | 2001-08-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-08-18 | 2005-02-17 | 2005-08-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-08-18 | 2009-02-17 | 2009-08-19 | $7700.00 | Window Closed / Lapsed |