US6032144A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimization of queries using relational algebraic theta-semijoin operator
Assignee: Nokia of America Corp
•
Filing: 1997-05-23
•
Granted: 2000-02-29
•
Expires: 2017-05-23
Abstract
Abstract A collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator is used to generate relational algebraic expressions equivalent to a computer programming language query. These expressions may be employed as a search space which is utilized by, for example, optimizing software or software that determines the equivalency of queries. Cost formulas for the multiset version of the theta-semijoin operator may be used in computing cost estimates for the generated expressions. Based on these computed cost estimates, the least costly implementation of a complex query is determined. Thus, queries are cost-based optimized on both a local and global basis by use of the relational algebraic theta-semijoin operator.
Inventors
- 👤 Divesh Srivastava
- 👤 Peter J. Stuckey
- 👤 Sundararajarao Sudarshan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 16:50
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24537; G06F16/24542; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
68 words
A method comprising the steps of receiving a computer programming language database system query; generating at least one relational algebraic expression in response to said query by employing at least one of a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator; selecting at least one of said relational algebraic expressions; and accessing said computer programming language database based on said selected expression.
Claim 2
Independent Claim
68 words
A method comprising the steps of receiving a computer programming language database system query; generating at least one relational algebraic expression in response to said query by employing at least one of a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator; selecting at least one of said relational algebraic expressions; and accessing said computer programming language database based on said selected expression.
Claim 3
Dependent Claim
22 words
The method of claim 1 wherein said selecting comprises the step of estimating processing costs for at least one of said expressions.
Claim 4
Dependent Claim
15 words
The method of claim 2 wherein said selecting is based on said estimated processing costs.
Claim 5
Dependent Claim
12 words
The method of claim 1 wherein said computer programming language is SQL.
Claim 6
Dependent Claim
31 words
The method of claim 4 wherein said query is selected from the group consisting of queries with aggregation views, queries with SELECT DISTINCT views, and queries with correlated subqueries and outerjoins.
Claim 7
Dependent Claim
22 words
The method of claim 4 wherein said query is selected from the group consisting of queries with views and queries with subqueries.
Claim 8
Independent Claim
13 words
The method of claim I wherein said query is a decision support query.
Claim 9
Dependent Claim
23 words
The method of claim 4 wherein said query is at least one magic set rewriting of a second computer programming language database query.
Claim 10
Dependent Claim
49 words
A computer programming language query optimizer comprising means for receiving a computer database language query; and means for generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the relational algebraic theta-semijoin operator, said expression being equivalent to said query.
Claim 11
Dependent Claim
49 words
A computer programming language query optimizer comprising means for receiving a computer database language query; and means for generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the relational algebraic theta-semijoin operator, said expression being equivalent to said query.
Claim 12
Dependent Claim
70 words
A computer processor programmed to perform method steps for optimizing an SQL query, said method steps comprising generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the relational algebraic theta-semijoin operator, said expression equivalent to said query; and performing cost-based algebraic optimization of said algebraic expressions, said cost-based algebraic optimization using at least one cost formula for said theta-semijoin operator.
Claim 13
Dependent Claim
70 words
A computer processor programmed to perform method steps for optimizing an SQL query, said method steps comprising generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the relational algebraic theta-semijoin operator, said expression equivalent to said query; and performing cost-based algebraic optimization of said algebraic expressions, said cost-based algebraic optimization using at least one cost formula for said theta-semijoin operator.
Claim 14
Dependent Claim
49 words
A program storage device embodying a computer program to perform method steps comprising: receiving an SQL query; and generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the relational algebraic theta-semijoin operator, said expression equivalent to said SQL query.
Claim 15
Dependent Claim
49 words
A program storage device embodying a computer program to perform method steps comprising: receiving an SQL query; and generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the relational algebraic theta-semijoin operator, said expression equivalent to said SQL query.
Claim 16
Dependent Claim
37 words
A storage device embodying a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator, said rules input to software employing relational algebraic expressions, said expressions responsive to a computer language database query.
Claim 17
Dependent Claim
37 words
A storage device embodying a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator, said rules input to software employing relational algebraic expressions, said expressions responsive to a computer language database query.
Claim 18
Independent Claim
57 words
A method of optimizing a computer programming language query, the improvement comprising the steps of receiving said query, generating a search space, said search space comprised of at least one relational algebraic expression equivalent to said query, said expression involving the multiset version of the theta-semijoin operator; and optimizing said query by estimating cost for said expression.
Claim 19
Independent Claim
57 words
A method of optimizing a computer programming language query, the improvement comprising the steps of receiving said query, generating a search space, said search space comprised of at least one relational algebraic expression equivalent to said query, said expression involving the multiset version of the theta-semijoin operator; and optimizing said query by estimating cost for said expression.
Claim 20
Independent Claim
102 words
A method of retrieving information from a computer database comprising the steps of receiving a computer database language query; translating said query into a first relational algebraic expression; generating at least one relational algebraic expression in response to said first relational algebraic expression by employing at least one equivalence rule involving the multiset version of the theta-semijoin; generating a cost estimate for each of said expressions by employing at least one cost formula for said theta-semijoin operator; selecting one of said expressions, said selection based on said generated cost estimates; and employing said selected expression to retrieve said information from said database.
Claim 21
Independent Claim
102 words
A method of retrieving information from a computer database comprising the steps of receiving a computer database language query; translating said query into a first relational algebraic expression; generating at least one relational algebraic expression in response to said first relational algebraic expression by employing at least one equivalence rule involving the multiset version of the theta-semijoin; generating a cost estimate for each of said expressions by employing at least one cost formula for said theta-semijoin operator; selecting one of said expressions, said selection based on said generated cost estimates; and employing said selected expression to retrieve said information from said database.
Claim 22
Independent Claim
69 words
A method comprising the steps of receiving at least a first and a second computer database language queries; generating at least one relational algebraic expression for each said query by employing at least one equivalence rule involving the multiset version of the theta-semijoin operator; and determining equivalency of any of said generated relational algebraic expressions from said first query to said generated relational algebraic expressions of said second query.
Claim 23
Independent Claim
69 words
A method comprising the steps of receiving at least a first and a second computer database language queries; generating at least one relational algebraic expression for each said query by employing at least one equivalence rule involving the multiset version of the theta-semijoin operator; and determining equivalency of any of said generated relational algebraic expressions from said first query to said generated relational algebraic expressions of said second query.
Claim 24
Independent Claim
49 words
An apparatus for determining equivalence of SQL queries, comprising means for accepting at least two SQL queries; and means for generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the theta-semijoin operator, said generated expressions equivalent to respective queries.
Claim 25
Independent Claim
49 words
An apparatus for determining equivalence of SQL queries, comprising means for accepting at least two SQL queries; and means for generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the theta-semijoin operator, said generated expressions equivalent to respective queries.
Claim 26
Independent Claim
102 words
A method comprising the steps of receiving a computer programming language database system query; generating at least one relational algebraic expression in response to said query by employing at least one of a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator; selecting at least one of said relational algebraic expressions; and accessing said computer programming language database based on said selected expression, said multiset version defined as ##EQU52## where R1 and R2 denote relations, and θ(t 2 ) denotes the predicate θ with attributes of R 2 replaced by their values from tuple t 2 .
Claim 27
Independent Claim
102 words
A method comprising the steps of receiving a computer programming language database system query; generating at least one relational algebraic expression in response to said query by employing at least one of a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator; selecting at least one of said relational algebraic expressions; and accessing said computer programming language database based on said selected expression, said multiset version defined as ##EQU52## where R1 and R2 denote relations, and θ(t 2 ) denotes the predicate θ with attributes of R 2 replaced by their values from tuple t 2 .
Claim 28
Dependent Claim
38 words
The method of claim 17 wherein said collection includes equivalence rule ##EQU53## where E (with or without subscripts) denotes relational expressions, θ (with or without subscripts) denotes predicates,.sub.θ denotes the θ-join operator, and .sub.θ denotes the θ-semijoin operator.
Claim 29
Dependent Claim
38 words
The method of claim 17 wherein said collection includes equivalence rule ##EQU54## E (with or without subscripts) denotes relational expressions, θ (with or without subscripts) denotes predicates, .sub.θ denotes the θ-join operator, and .sub.θ denotes the θ-semijoin operator.
Claim 30
Dependent Claim
58 words
The method of claim 17 wherein said collection includes equivalence rule ##EQU55## where E (with or without subscripts) denotes relational expressions, θ (with or without subscripts) denotes predicates, .sub.θ denotes the θ-join operator, .sub.θ denotes the θ-semijoin operator, g F f denotes a grouping/aggregation operator, and θ involves only the attributes in a and attrs (E 2 ).
Claim 31
Dependent Claim
70 words
A storage device embodying a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator, said rules input to software employing relational algebraic expressions, said expressions responsive to a computer language database query, said multiset version defined as ##EQU56## where R1 and R2 denote relations, θ(t 2 ) denotes the predicate θ with attributes of R 2 replaced by their values from tuple t 2 .
Claim 32
Dependent Claim
70 words
A storage device embodying a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator, said rules input to software employing relational algebraic expressions, said expressions responsive to a computer language database query, said multiset version defined as ##EQU56## where R1 and R2 denote relations, θ(t 2 ) denotes the predicate θ with attributes of R 2 replaced by their values from tuple t 2 .
Claim 33
Dependent Claim
69 words
A storage device embodying a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator, said rules input to software employing relational algebraic expressions, said expressions responsive to a computer language database query, said rules including rule ##EQU57## where E (with or without subscripts) denotes relational expressions, θ (with or without subscripts) denotes predicates, .sub.θ denotes the θ-join operator, and .sub.θ denotes the θ-semijoin operator.
Claim 34
Dependent Claim
69 words
A storage device embodying a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator, said rules input to software employing relational algebraic expressions, said expressions responsive to a computer language database query, said rules including rule ##EQU57## where E (with or without subscripts) denotes relational expressions, θ (with or without subscripts) denotes predicates, .sub.θ denotes the θ-join operator, and .sub.θ denotes the θ-semijoin operator.
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) | 2003-02-28 | 2003-08-30 | 2004-02-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-02-28 | 2007-08-30 | 2008-02-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-02-28 | 2011-08-30 | 2012-02-29 | $7700.00 | Window Closed / Lapsed |