US6061676A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Effecting constraint magic rewriting on a query with the multiset version of the relational algebric theta-semijoin operator
Assignee: Nokia of America Corp
•
Filing: 1997-05-23
•
Granted: 2000-05-09
•
Expires: 2017-05-23
Abstract
Abstract An equivalence rule having the multiset version of the relational algebraic theta-semijoin operator is used in effectuating Constraint Magic rewriting on a computer programming language query having non-equality, as well as equality, predicates. In particular, the rule effectuates Constraint Magic rewriting for a single join. When applied repeatedly on a sequence of joins, Constraint Magic rewriting is effectuated for a single block query. The rule may be used to generate relational algebraic expressions to optimize or determine the equivalency of queries. Cost estimates for alternative ways of evaluating a complex query can be efficiently computed. Based on these computed cost estimates, the least costly implementation of a complex query is determined.
Inventors
- 👤 Divesh Srivastava
- 👤 Peter J. Stuckey
- 👤 Sundararajarao Sudarshan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 07:34
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/953; Y10S707/954; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
117 words
A method comprising the steps of: receiving a computer programming language database query; generating at least one relational algebraic expression in response to said query by means of a equivalence rule involving the multiset version of the theta-semijoin operator, said rule being ##EQU63## where θ 2 involves only the attributes in attrs(Q) ∪attrs(E 1 ), ##EQU64## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join, and .sub.θ denotes the multiset θ-semijoin, and θ (with or without subscript) denotes quantifier-free predicates; 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
117 words
A method comprising the steps of: receiving a computer programming language database query; generating at least one relational algebraic expression in response to said query by means of a equivalence rule involving the multiset version of the theta-semijoin operator, said rule being ##EQU63## where θ 2 involves only the attributes in attrs(Q) ∪attrs(E 1 ), ##EQU64## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join, and .sub.θ denotes the multiset θ-semijoin, and θ (with or without subscript) denotes quantifier-free predicates; 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
29 words
The method of claim 1 wherein said generating comprises the step of repeatedly applying said rule to at least one relational algebraic expression generated in response to said query.
Claim 4
Dependent Claim
12 words
The method of claim 1 wherein said computer programming language is SQL.
Claim 5
Independent Claim
120 words
An apparatus comprising means for receiving a first relational algebraic expression responsive to an SQL query for a database; means for transforming said first expression into at least one generated relational algebraic expression, said transforming involving an equivalence rule, said rule being ##EQU65## where θ 2 involves only the attributes in attrs(Q) ∪ attrs(E 1 ), ##EQU66## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join, and .sub.θ denotes the multiset θ-semijoin, and θ (with or without subscript) denotes quantifier-free predicates; means for selecting at least one of said generated relational algebraic expressions; and means for accessing said database based on said selected expression.
Claim 6
Independent Claim
120 words
An apparatus comprising means for receiving a first relational algebraic expression responsive to an SQL query for a database; means for transforming said first expression into at least one generated relational algebraic expression, said transforming involving an equivalence rule, said rule being ##EQU65## where θ 2 involves only the attributes in attrs(Q) ∪ attrs(E 1 ), ##EQU66## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join, and .sub.θ denotes the multiset θ-semijoin, and θ (with or without subscript) denotes quantifier-free predicates; means for selecting at least one of said generated relational algebraic expressions; and means for accessing said database based on said selected expression.
Claim 7
Dependent Claim
24 words
The apparatus of claim 4 wherein said transforming means comprises means for reiteratively applying said equivalence rule to said expression responsive to said query.
Claim 8
Dependent Claim
103 words
A program storage device embodying a computer program to perform method steps for optimizing an SQL query to access a computer database, said method comprising accepting the query; generating at least one relational algebraic expression in response to said query by means of a equivalence rule involving the multiset version of the theta-semijoin operator, said rule being ##EQU67## where θ 2 involves only the attributes in attrs(Q) ∪ attrs(E 1 ), ##EQU68## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join and .sub.θ denotes the multiset θ-semijoin.
Claim 9
Dependent Claim
103 words
A program storage device embodying a computer program to perform method steps for optimizing an SQL query to access a computer database, said method comprising accepting the query; generating at least one relational algebraic expression in response to said query by means of a equivalence rule involving the multiset version of the theta-semijoin operator, said rule being ##EQU67## where θ 2 involves only the attributes in attrs(Q) ∪ attrs(E 1 ), ##EQU68## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join and .sub.θ denotes the multiset θ-semijoin.
Claim 10
Dependent Claim
27 words
The device of claim 6 wherein said generating further comprises repeatedly applying said rule to at least one relational algebraic expression generated in response to said query.
Claim 11
Dependent Claim
112 words
A storage device embodying an equivalence rule involving the multiset version of the relational algebraic theta-semijoin operator, said rule being such that when input to software employing relational algebraic expressions at least one relational algebraic expression is generated, said expression responsive to a computer language database query to access said computer language database, and said rule being ##EQU69## where θ 2 involves only the attributes in attrs(Q) ∪ attrs(E 1 ), ##EQU70## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join, and .sub.θ denotes the multiset θ-semijoin, and θ (with or without subscript) denotes quantifier-free predicates.
Claim 12
Dependent Claim
112 words
A storage device embodying an equivalence rule involving the multiset version of the relational algebraic theta-semijoin operator, said rule being such that when input to software employing relational algebraic expressions at least one relational algebraic expression is generated, said expression responsive to a computer language database query to access said computer language database, and said rule being ##EQU69## where θ 2 involves only the attributes in attrs(Q) ∪ attrs(E 1 ), ##EQU70## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join, and .sub.θ denotes the multiset θ-semijoin, and θ (with or without subscript) denotes quantifier-free predicates.
Claim 13
Independent Claim
115 words
A method comprising the steps of receiving at least two computer programming language database queries; for each query, generating at least one relational algebraic expression in response to said query by means of a equivalence rule involving the multiset version of the thetasemijoin operator, said rule being ##EQU71## where θ 2 involves only the attributes in attrs(Q) ∪ attrs(E 1 ), ##EQU72## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join, and .sub.θ denotes the multiset θ-semijoin, and θ (with or without subscript) denotes quantifier-free predicates; and determining equivalence of said queries based on said generated relational algebraic expressions.
Claim 14
Independent Claim
115 words
A method comprising the steps of receiving at least two computer programming language database queries; for each query, generating at least one relational algebraic expression in response to said query by means of a equivalence rule involving the multiset version of the thetasemijoin operator, said rule being ##EQU71## where θ 2 involves only the attributes in attrs(Q) ∪ attrs(E 1 ), ##EQU72## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join, and .sub.θ denotes the multiset θ-semijoin, and θ (with or without subscript) denotes quantifier-free predicates; and determining equivalence of said queries based on said generated relational algebraic expressions.
Claim 15
Independent Claim
108 words
A method comprising the steps of receiving a computer programming language database query; and generating at least one relational algebraic expression in response to said query by means of a equivalence rule involving the multiset version of the theta-semijoin operator such that Constraint Magic rewriting on said query is effectuated, said rule being ##EQU73## where θ 2 involves only the attributes in attrs(Q) ∪ attrs(E 1 ), ##EQU74## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join, and .sub.θ denotes the multiset θ-semijoin, and θ (with or without subscript) denotes quantifier-free predicates.
Claim 16
Independent Claim
108 words
A method comprising the steps of receiving a computer programming language database query; and generating at least one relational algebraic expression in response to said query by means of a equivalence rule involving the multiset version of the theta-semijoin operator such that Constraint Magic rewriting on said query is effectuated, said rule being ##EQU73## where θ 2 involves only the attributes in attrs(Q) ∪ attrs(E 1 ), ##EQU74## Q denotes a query, E (with or without subscripts) denotes relational expressions, attrs(X) denotes attributes of the result of X, .sub.θ denotes the multiset θ-join, and .sub.θ denotes the multiset θ-semijoin, and θ (with or without subscript) denotes quantifier-free predicates.
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-05-09 | 2003-11-08 | 2004-05-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-09 | 2007-11-08 | 2008-05-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-09 | 2011-11-08 | 2012-05-09 | $7700.00 | Window Closed / Lapsed |