US6006214A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Database management system, method, and program for providing query rewrite transformations for nested set elimination in database views
Assignee: International Business Machines Corp
•
Filing: 1996-12-04
•
Granted: 1999-12-21
•
Expires: 2016-12-04
Abstract
Abstract The system, method, and program of this invention, referred to herein as nest elimination, performs query rewrite transformations, within a database management system (DBMS), for a certain class of object queries over views that involve derived nested sets. The nest elimination algorithm uses query rewriting to avoid computing these nested sets in certain common cases. For each quantifier in a query (if the quantifier is defined over a nested set that is a part of a view or if the quantifier is implemented by a subquery that projects a NEST aggregate) the following functions are performed: a) resetting an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; b) adding a null testing predicate to the rewritten database query; c) adding quantifiers defined within the nest subquery to the rewritten database query; d) adding predicates from the nest subquery of the view to the rewritten database query; and e) rewriting each expression involving a quantifier over an instance into a path expression. The resulting rewritten query is then further processed by the DBMS such as through a query optimizer, etc. By avoiding nested set computations for a certain class of queries, the rewritten query can result in improved processing performance.
Inventors
- 👤 Michael J. Carey
- 👤 Gerald George Kiernan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 19:47
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/28; G06F16/289; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24547; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
59 words
A method, in a computer system, for processing a query, the method comprising: transforming the query into a rewritten query that eliminates a need for a nested collection computation if the query is over an object-oriented view containing a collection and the query unnests the nested collection; and processing the rewritten query independently of performing the nested collection computation.
Claim 2
Independent Claim
59 words
A method, in a computer system, for processing a query, the method comprising: transforming the query into a rewritten query that eliminates a need for a nested collection computation if the query is over an object-oriented view containing a collection and the query unnests the nested collection; and processing the rewritten query independently of performing the nested collection computation.
Claim 3
Independent Claim
76 words
A method of processing a database query by a database management system, the method comprising: rewriting the database query into a rewritten database query by performing the following steps-- resetting an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; and adding quantifiers defined within the nest subquery to the rewritten database query; and processing the rewritten database query.
Claim 4
Independent Claim
76 words
A method of processing a database query by a database management system, the method comprising: rewriting the database query into a rewritten database query by performing the following steps-- resetting an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; and adding quantifiers defined within the nest subquery to the rewritten database query; and processing the rewritten database query.
Claim 5
Dependent Claim
22 words
The method of claim 2 wherein rewriting the database query further comprises adding a null testing predicate to the rewritten database query.
Claim 6
Dependent Claim
26 words
The method of claim 2 wherein rewriting the database query further comprises adding predicates from the nest subquery of the view to the rewritten database query.
Claim 7
Dependent Claim
25 words
The method of claim 2 wherein rewriting the database query further comprises rewriting each expression involving a quantifier over an instance into a path expression.
Claim 8
Independent Claim
113 words
A method of processing a database query by a database management system, the method comprising: rewriting the database query into a rewritten database query by performing the following steps-- resetting an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; adding a null testing predicate to the rewritten database query; adding quantifiers defined within the nest subquery to the rewritten database query; adding predicates from the nest subquery of the view to the rewritten database query; and rewriting each expression involving a quantifier over an instance into a path expression; and processing the rewritten database query.
Claim 9
Independent Claim
113 words
A method of processing a database query by a database management system, the method comprising: rewriting the database query into a rewritten database query by performing the following steps-- resetting an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; adding a null testing predicate to the rewritten database query; adding quantifiers defined within the nest subquery to the rewritten database query; adding predicates from the nest subquery of the view to the rewritten database query; and rewriting each expression involving a quantifier over an instance into a path expression; and processing the rewritten database query.
Claim 10
Dependent Claim
28 words
The method of claim 2 or 6 wherein rewriting the database query further comprises replacing quantifiers ranging over views with a quantifier from a definition of the view.
Claim 11
Independent Claim
54 words
The method of claims 2, 3, 4, 5 or 6 wherein the steps for rewriting the database query are performed for each quantifier in the database query if the quantifier is over a nested set defined in a view type or if the quantifier is implemented by a subquery using the nest aggregate function.
Claim 12
Dependent Claim
77 words
A computer program, on a computer usable medium, for rewriting a database query, the program comprising: program code means for causing a transformation of the query into a rewritten query that eliminates a need for a nested collection computation if the query is over an object-oriented view containing a collection and the query unnests the nested collection; and program code means for causing the rewritten query to be further processed independently of performing the nested collection computation.
Claim 13
Dependent Claim
77 words
A computer program, on a computer usable medium, for rewriting a database query, the program comprising: program code means for causing a transformation of the query into a rewritten query that eliminates a need for a nested collection computation if the query is over an object-oriented view containing a collection and the query unnests the nested collection; and program code means for causing the rewritten query to be further processed independently of performing the nested collection computation.
Claim 14
Dependent Claim
71 words
A computer program, on a computer usable medium, for rewriting a database query, the program comprising: program code means for causing a resetting of an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; and program code means for causing an adding of quantifiers defined within the nest subquery to a rewritten database query.
Claim 15
Dependent Claim
71 words
A computer program, on a computer usable medium, for rewriting a database query, the program comprising: program code means for causing a resetting of an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; and program code means for causing an adding of quantifiers defined within the nest subquery to a rewritten database query.
Claim 16
Dependent Claim
24 words
The program of claim 10 further comprising program code means for causing an adding of a null testing predicate to the rewritten database query.
Claim 17
Dependent Claim
28 words
The program of claim 10 further comprising program code means for causing an adding of predicates from the nest subquery of the view to the rewritten database query.
Claim 18
Dependent Claim
27 words
The program of claim 10 further comprising program code means for causing a rewriting of each expression involving a quantifier over an instance into a path expression.
Claim 19
Dependent Claim
129 words
A computer program, on a computer usable medium for rewriting a database query, the program comprising: program code means for causing a resetting of an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; program code means for causing an adding of a null testing predicate to a rewritten database query; program code means for causing an adding of quantifiers defined within the nest subquery to the rewritten database query; program code means for causing an adding of predicates from the nest subquery of the view to the rewritten database query; and program code means for causing a rewriting of each expression involving a quantifier over an instance into a path expression.
Claim 20
Dependent Claim
129 words
A computer program, on a computer usable medium for rewriting a database query, the program comprising: program code means for causing a resetting of an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; program code means for causing an adding of a null testing predicate to a rewritten database query; program code means for causing an adding of quantifiers defined within the nest subquery to the rewritten database query; program code means for causing an adding of predicates from the nest subquery of the view to the rewritten database query; and program code means for causing a rewriting of each expression involving a quantifier over an instance into a path expression.
Claim 21
Dependent Claim
30 words
The program of claim 10 or 14 further comprising program code means for causing a replacing of quantifiers ranging over views with a quantifier from a definition of the view.
Claim 22
Dependent Claim
51 words
The program of claim 10, 11, 12, 13 or 14 wherein the program code means are activated for each quantifier in the database query if the quantifier is over a nested set defined in a view type or if the quantifier is implemented by a subquery using the nest aggregate function.
Claim 23
Independent Claim
60 words
A system for processing a database query, the system comprising: means for transforming the query into a rewritten query that eliminates a need for a nested collection computation if the query is over an object-oriented view containing a collection and the query unnests the nested collection; and means for processing the rewritten query independently of performing the nested collection computation.
Claim 24
Independent Claim
60 words
A system for processing a database query, the system comprising: means for transforming the query into a rewritten query that eliminates a need for a nested collection computation if the query is over an object-oriented view containing a collection and the query unnests the nested collection; and means for processing the rewritten query independently of performing the nested collection computation.
Claim 25
Independent Claim
79 words
A system for processing a database query, the system comprising: means for rewriting the database query into a rewritten database query, the means for rewriting having means for resetting an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; and means for adding quantifiers defined within the nest subquery to the rewritten database query; and means for processing the rewritten database query.
Claim 26
Independent Claim
79 words
A system for processing a database query, the system comprising: means for rewriting the database query into a rewritten database query, the means for rewriting having means for resetting an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; and means for adding quantifiers defined within the nest subquery to the rewritten database query; and means for processing the rewritten database query.
Claim 27
Dependent Claim
27 words
The system of claim 18 wherein the means for rewriting the database query further comprises means for adding a null testing predicate to the rewritten database query.
Claim 28
Dependent Claim
31 words
The system of claim 18 wherein the means for rewriting the database query further comprises means for adding predicates from the nest subquery of the view to the rewritten database query.
Claim 29
Dependent Claim
30 words
The system of claim 18 wherein the means for rewriting the database query further comprises means for rewriting each expression involving a quantifier over an instance into a path expression.
Claim 30
Independent Claim
122 words
A system for processing a database query, the system comprising: means for rewriting the database query into a rewritten database query, the means for rewriting having means for resetting an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; means for adding a null testing predicate to the rewritten database query; means for adding quantifiers defined within the nest subquery to the rewritten database query; means for adding predicates from the nest subquery of the view to the rewritten database query; and means for rewriting each expression involving a quantifier over an instance into a path expression; and means for processing the rewritten database query.
Claim 31
Independent Claim
122 words
A system for processing a database query, the system comprising: means for rewriting the database query into a rewritten database query, the means for rewriting having means for resetting an element to which a quantifier is bound in the database query to an argument of a nest aggregate function in a nest subquery of a view; means for adding a null testing predicate to the rewritten database query; means for adding quantifiers defined within the nest subquery to the rewritten database query; means for adding predicates from the nest subquery of the view to the rewritten database query; and means for rewriting each expression involving a quantifier over an instance into a path expression; and means for processing the rewritten database query.
Claim 32
Dependent Claim
33 words
The system of claim 18 or 22 wherein the means for rewriting the database query further comprises means for replacing quantifiers ranging over views with a quantifier from a definition of the view.
Claim 33
Dependent Claim
127 words
A query rewrite engine in a database management system, the query rewrite engine comprising: means for disregarding a subquery that implements a nested element if a query does not reference the nested element; means for computing a nested set it the query references the nested element in the projection list and the nested set is to be a part of a result of the query; and means for rewriting the query if the query unnests the nested set, wherein the means for rewriting further comprises means for resetting an element to which a quantifier is bound in the query to an argument of a nest aggregate function in a nest subquery of a view, and adding quantifiers defined within the nest subquery to a rewritten database query.
Claim 34
Dependent Claim
127 words
A query rewrite engine in a database management system, the query rewrite engine comprising: means for disregarding a subquery that implements a nested element if a query does not reference the nested element; means for computing a nested set it the query references the nested element in the projection list and the nested set is to be a part of a result of the query; and means for rewriting the query if the query unnests the nested set, wherein the means for rewriting further comprises means for resetting an element to which a quantifier is bound in the query to an argument of a nest aggregate function in a nest subquery of a view, and adding quantifiers defined within the nest subquery to a rewritten database query.
Claim 35
Independent Claim
120 words
A method of processing a database query in a database management system, the method comprising: disregarding a subquery that implements a nested element if a query does not reference the nested element; computing a nested set if the query references the nested element in the projection list and the nested set is to be a part of a result of the query; and rewriting the query if the query unnests the nested set, wherein the step of rewriting further comprises resetting an element to which a quantifier is bound in the query to an argument of a nest aggregate function in a nest subquery of a view, and adding quantifiers defined within the nest subquery to a rewritten database query.
Claim 36
Independent Claim
120 words
A method of processing a database query in a database management system, the method comprising: disregarding a subquery that implements a nested element if a query does not reference the nested element; computing a nested set if the query references the nested element in the projection list and the nested set is to be a part of a result of the query; and rewriting the query if the query unnests the nested set, wherein the step of rewriting further comprises resetting an element to which a quantifier is bound in the query to an argument of a nest aggregate function in a nest subquery of a view, and adding quantifiers defined within the nest subquery to a rewritten database query.
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) | 2002-12-20 | 2003-06-21 | 2003-12-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-20 | 2007-06-21 | 2007-12-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-20 | 2011-06-21 | 2011-12-21 | $7700.00 | Window Closed / Lapsed |