Patent US5701455A successfully refreshed from Google Patents.
US5701455A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for reordering complex SQL queries using a modified generalized outer join operator
Assignee: International Business Machines Corp
•
Filing: 1995-06-05
•
Granted: 1997-12-23
•
Expires: 2015-06-05
Abstract
Abstract A method and apparatus for reordering complex SQL queries containing joins, outer and full outer joins. The method and apparatus first translates the query into a hypergraph representation. Required sets, conflict sets and preserved sets are then generated for the query hypergraph. Using the required sets, a plurality of plans are enumerated, wherein the plans represent associative reorderings of relations in the query. SQL operators are selectively assigned to each of the enumerated plans using the conflict sets and/or preserved sets, so that the results from the plans are identical to the original query. A novel Modified General Outer Join (MGOJ) operator may be assigned to the root of a sub-tree, wherein the MGOJ operator is a compensation operator. The operator assignment is performed recursively for the root of each sub-tree in the plan. One of the enumerated plans (generally the most optimal) is then selected for execution.
Inventors
- 👤 Gautam Bhargava
- 👤 Piyush Goel
- 👤 Balakrishna Ragmavendra Iyer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 03:30
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; G06F16/24544; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
172 words
A method of reordering an SQL query in a computer having a memory, comprising the steps of: (a) accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU51## (b) replacing the first expression with a second expression comprising: ##EQU52## wherein the MGOJ operator comprises a relation (R 1 ,2 R 3 ,V 1 ,2 V 3 ,E') and the second expression preserves relation X 1 , wherein: ##EQU53## wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples in the relation R 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples in the relation r 3 , ##EQU54## P i ,j is a predicate for ##EQU55## and π c denotes a projection operation.
Claim 2
Independent Claim
172 words
A method of reordering an SQL query in a computer having a memory, comprising the steps of: (a) accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU51## (b) replacing the first expression with a second expression comprising: ##EQU52## wherein the MGOJ operator comprises a relation (R 1 ,2 R 3 ,V 1 ,2 V 3 ,E') and the second expression preserves relation X 1 , wherein: ##EQU53## wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples in the relation R 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples in the relation r 3 , ##EQU54## P i ,j is a predicate for ##EQU55## and π c denotes a projection operation.
Claim 3
Independent Claim
172 words
A method of reordering an SQL query in a computer having a memory, comprising the steps of: (a) accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU56## (b) replacing the first expression with a second expression comprising: ##EQU57## wherein the MGOJ operator comprises a relation (R 1 ,2 R 3 ,V 1 ,2 V 3 ,E') and the second expression preserves relation X 1 , wherein: ##EQU58## wherein R 1 ,2 is a nonempty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples for the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples for the relation r 3 , ##EQU59## p i ,j is a predicate for ##EQU60## and π c denotes a projection operation.
Claim 4
Independent Claim
172 words
A method of reordering an SQL query in a computer having a memory, comprising the steps of: (a) accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU56## (b) replacing the first expression with a second expression comprising: ##EQU57## wherein the MGOJ operator comprises a relation (R 1 ,2 R 3 ,V 1 ,2 V 3 ,E') and the second expression preserves relation X 1 , wherein: ##EQU58## wherein R 1 ,2 is a nonempty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples for the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples for the relation r 3 , ##EQU59## p i ,j is a predicate for ##EQU60## and π c denotes a projection operation.
Claim 5
Independent Claim
206 words
A method of reordering an SQL query in a computer having a memory, comprising the steps of: (a) accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU61## (b) replacing the first expression with a second expression comprising: ##EQU62## wherein the MGOJ operator comprises a relation (R 1 R 2 , V 1 V 2 ,E') and the second expression preserves relations X 1 and X 3 , wherein: ##EQU63## wherein R 1 ,2 is a nonempty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples for the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples for the relation r 3 , R 1 ,2 ∩R 3 =.o slashed., V 1 ,2 ∩V 3 =.o slashed., X 1 =(R 1 ,V 1 ,E 1 ) X 1 and X 3 are relations such that ##EQU64## P i ,j is a predicate for ##EQU65## and π c denotes a projection operation.
Claim 6
Independent Claim
206 words
A method of reordering an SQL query in a computer having a memory, comprising the steps of: (a) accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU61## (b) replacing the first expression with a second expression comprising: ##EQU62## wherein the MGOJ operator comprises a relation (R 1 R 2 , V 1 V 2 ,E') and the second expression preserves relations X 1 and X 3 , wherein: ##EQU63## wherein R 1 ,2 is a nonempty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples for the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples for the relation r 3 , R 1 ,2 ∩R 3 =.o slashed., V 1 ,2 ∩V 3 =.o slashed., X 1 =(R 1 ,V 1 ,E 1 ) X 1 and X 3 are relations such that ##EQU64## P i ,j is a predicate for ##EQU65## and π c denotes a projection operation.
Claim 7
Dependent Claim
202 words
A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for reordering an SQL query in the method comprising the steps of: (a) accepting a query into the computer, wherein a first expression of the query comprises: ##EQU66## (b) replacing the first expression with a second expression comprising: ##EQU67## wherein the MGOJ operator comprises a relation (R 1 ,2 R 3 ,V 1 ,2 V 3 ,E') and the second expression preserves relation X 1 , wherein: r 1 ,2 =(X 1 → P1 ,2 X 2 )=(R 1 ,2,V 1 ,2,E 1 ,2), wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples in the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples in the relation r 3 , ##EQU68## P i ,j is a predicate for ##EQU69## and π c denotes a projection operation.
Claim 8
Dependent Claim
202 words
A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for reordering an SQL query in the method comprising the steps of: (a) accepting a query into the computer, wherein a first expression of the query comprises: ##EQU66## (b) replacing the first expression with a second expression comprising: ##EQU67## wherein the MGOJ operator comprises a relation (R 1 ,2 R 3 ,V 1 ,2 V 3 ,E') and the second expression preserves relation X 1 , wherein: r 1 ,2 =(X 1 → P1 ,2 X 2 )=(R 1 ,2,V 1 ,2,E 1 ,2), wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples in the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples in the relation r 3 , ##EQU68## P i ,j is a predicate for ##EQU69## and π c denotes a projection operation.
Claim 9
Dependent Claim
193 words
A program storage device readable by a computer having a memory, tangibly embodying a program of instructions executable by the computer to perform method steps for reordering an SQL query, the method comprising the steps of: (a) accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU70## (b) replacing the first expression with a second expression comprising: ##EQU71## wherein the MGOJ operator comprises a relation and the second expression preserves relation wherein: r 1 ,2 =(X 1 ⃡ P .sbsp.1,2 X 2 )=(R 1 ,2,V 1 ,2,E 1 ,2), wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples for the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples for the relation r 3 , ##EQU72## P i ,j is a predicate for ##EQU73## and π c denotes a projection operation.
Claim 10
Dependent Claim
193 words
A program storage device readable by a computer having a memory, tangibly embodying a program of instructions executable by the computer to perform method steps for reordering an SQL query, the method comprising the steps of: (a) accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU70## (b) replacing the first expression with a second expression comprising: ##EQU71## wherein the MGOJ operator comprises a relation and the second expression preserves relation wherein: r 1 ,2 =(X 1 ⃡ P .sbsp.1,2 X 2 )=(R 1 ,2,V 1 ,2,E 1 ,2), wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples for the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples for the relation r 3 , ##EQU72## P i ,j is a predicate for ##EQU73## and π c denotes a projection operation.
Claim 11
Dependent Claim
200 words
A program storage device readable by a computer having a memory, tangibly embodying a program of instructions executable by the computer to perform method steps for reordering an SQL query, the method comprising the steps of: (a) accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU74## (b) replacing the first expression with a second expression comprising: ##EQU75## wherein the MGOJ operator comprises a relation (R 1 R 2 ,V 1 V 1 ,E') and the second expression preserves relations X 1 and X 3 , wherein: ##EQU76## wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein real attributes, V 3 is a non-attributes, and E 3 is a set R 1 ,2 ∩R 3 =.o slashed., V 1 ,2 ∩V 3 =.o slashed., X 1 =(R 1 ,V 1 ,E 1 ), X 1 and X 3 are relations such that ##EQU77## P i ,j is a predicate for ##EQU78## and π c denotes a projection operation.
Claim 12
Dependent Claim
200 words
A program storage device readable by a computer having a memory, tangibly embodying a program of instructions executable by the computer to perform method steps for reordering an SQL query, the method comprising the steps of: (a) accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU74## (b) replacing the first expression with a second expression comprising: ##EQU75## wherein the MGOJ operator comprises a relation (R 1 R 2 ,V 1 V 1 ,E') and the second expression preserves relations X 1 and X 3 , wherein: ##EQU76## wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein real attributes, V 3 is a non-attributes, and E 3 is a set R 1 ,2 ∩R 3 =.o slashed., V 1 ,2 ∩V 3 =.o slashed., X 1 =(R 1 ,V 1 ,E 1 ), X 1 and X 3 are relations such that ##EQU77## P i ,j is a predicate for ##EQU78## and π c denotes a projection operation.
Claim 13
Independent Claim
202 words
An apparatus for reordering an SQL query, comprising: a computer having a memory, wherein the SQL query is used by the computer to direct information retrieval from a relational database stored in an electronic storage device in communication with the computer, the computer further comprising: means for accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU79## means for replacing the first expression with a second expression comprising: ##EQU80## wherein the MGOJ operator comprises a relation (R 1 ,2 R 3 ,V 1 ,2 V 3 ,E') and the second expression preserves relation X 1 , wherein: ##EQU81## wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples in the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples in the relation r 3 , ##EQU82## P i ,j is a predicate for ##EQU83## and π c denotes a projection operation.
Claim 14
Independent Claim
202 words
An apparatus for reordering an SQL query, comprising: a computer having a memory, wherein the SQL query is used by the computer to direct information retrieval from a relational database stored in an electronic storage device in communication with the computer, the computer further comprising: means for accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU79## means for replacing the first expression with a second expression comprising: ##EQU80## wherein the MGOJ operator comprises a relation (R 1 ,2 R 3 ,V 1 ,2 V 3 ,E') and the second expression preserves relation X 1 , wherein: ##EQU81## wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples in the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples in the relation r 3 , ##EQU82## P i ,j is a predicate for ##EQU83## and π c denotes a projection operation.
Claim 15
Independent Claim
202 words
An apparatus for reordering an SQL query, comprising: a computer having a memory, wherein the SQL query is used by the computer to direct information retrieval from a relational database stored in an electronic storage device in communication with the computer, the computer further comprising: means for accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU84## means for replacing the first expression with a second expression comprising: ##EQU85## wherein the MGOJ operator comprises a relation (R 1 ,2 R 3 ,V 1 ,2 V 3 ,E') and the second expression preserves relation X 1 , wherein: ##EQU86## wherein R 1 ,2 is a nonempty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples for the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples for the relation r 3 , ##EQU87## p i ,j is a predicate for ##EQU88## and π c denotes a projection operation.
Claim 16
Independent Claim
202 words
An apparatus for reordering an SQL query, comprising: a computer having a memory, wherein the SQL query is used by the computer to direct information retrieval from a relational database stored in an electronic storage device in communication with the computer, the computer further comprising: means for accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU84## means for replacing the first expression with a second expression comprising: ##EQU85## wherein the MGOJ operator comprises a relation (R 1 ,2 R 3 ,V 1 ,2 V 3 ,E') and the second expression preserves relation X 1 , wherein: ##EQU86## wherein R 1 ,2 is a nonempty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples for the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples for the relation r 3 , ##EQU87## p i ,j is a predicate for ##EQU88## and π c denotes a projection operation.
Claim 17
Independent Claim
264 words
An apparatus for reordering an SQL query, comprising: a computer having a memory, wherein the SQL query is used by the computer to direct information retrieval from a relational database stored in an electronic storage device in communication with the computer, the computer further comprising: means for accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU89## means for replacing the first expression with a second expression comprising: ##EQU90## wherein the MGOJ operator comprises a relation (R 1 R 2 ,V 1 V 2 ,E') and the second expression preserves relations X 1 and X 3 , wherein: ##EQU91## wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples for the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples for the relation r 3 , R 1 ,2 ∩R 3 =.o slashed., V 1 ,2 ∩V 3 =.o slashed., X 1 =(R 1 ,V 1 ,E 1 ), X 1 and X 3 are relations such that R x .sbsb.1 ∩R x .sbsb.3 =V x .sbsb.1 ∩V x .sbsb.3 =.o slashed., R x .sbsb.1 .OR right.R 1 ,2 and R x .sbsb.3 .OR right.R 1 ,2, ##EQU92## p i ,j is a predicate for ##EQU93## and π c denotes a projection operation.
Claim 18
Independent Claim
264 words
An apparatus for reordering an SQL query, comprising: a computer having a memory, wherein the SQL query is used by the computer to direct information retrieval from a relational database stored in an electronic storage device in communication with the computer, the computer further comprising: means for accepting a query into the memory of the computer, wherein a first expression of the query comprises: ##EQU89## means for replacing the first expression with a second expression comprising: ##EQU90## wherein the MGOJ operator comprises a relation (R 1 R 2 ,V 1 V 2 ,E') and the second expression preserves relations X 1 and X 3 , wherein: ##EQU91## wherein R 1 ,2 is a non-empty set of real attributes, V 1 ,2 is a non-empty set of virtual attributes, and E 1 ,2 is a set of tuples for the relation r 1 ,2, r 3 =X 3 =(R 3 ,V 3 ,E 3 ), wherein R 3 is a non-empty set of real attributes, V 3 is a non-empty set of virtual attributes, and E 3 is a set of tuples for the relation r 3 , R 1 ,2 ∩R 3 =.o slashed., V 1 ,2 ∩V 3 =.o slashed., X 1 =(R 1 ,V 1 ,E 1 ), X 1 and X 3 are relations such that R x .sbsb.1 ∩R x .sbsb.3 =V x .sbsb.1 ∩V x .sbsb.3 =.o slashed., R x .sbsb.1 .OR right.R 1 ,2 and R x .sbsb.3 .OR right.R 1 ,2, ##EQU92## p i ,j is a predicate for ##EQU93## and π c denotes a projection operation.
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-12-22 | 2001-06-23 | 2001-12-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-22 | 2005-06-23 | 2005-12-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-22 | 2009-06-23 | 2009-12-23 | $7700.00 | Window Closed / Lapsed |