US5960427A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Reordering of complex SQL queries involving groupbys, joins, outer joins and full outer joins
Assignee: International Business Machines Corp
•
Filing: 1997-08-01
•
Granted: 1999-09-28
•
Expires: 2017-08-01
Abstract
Abstract A method, apparatus, and article of manufacture for query simplification by applying generalized inference propagation and generalized transitive closure in SQL queries having selection, projection, join, outer join, and intersection operations. The disclosed transformations and enumeration method unify and solve the problems of 1) unnesting join aggregate queries, and 2) complete enumeration of queries containing outer joins, when the outer join predicate references an aggregated value, or the predicate references more than two base relations in a query subtree. The system first eliminates redundant sub-expressions and modifies expensive binary operations to inexpensive binary operations, then converts complex predicates to simple predicates by application of a generalized selection (GS) operator.
Inventors
- 👤 Piyush Goel
- 👤 Balakrishna Raghavendra Iyer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 23:09
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24537; G06F16/24547; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 54
Claim 1
Independent Claim
84 words
A method of simplifying a query performed by a computer to retrieve data from a relational database stored in a electronic storage device coupled to the computer, the method comprising the steps of: (a) eliminating redundant sub-expressions from the query and modifying expensive binary operations in the query to inexpensive binary operations, so that only simple and complex predicates remain in the query; and (b) converting the complex predicates remaining in the query to simple predicates by application of a generalized selection (GS) operator.
Claim 2
Independent Claim
84 words
A method of simplifying a query performed by a computer to retrieve data from a relational database stored in a electronic storage device coupled to the computer, the method comprising the steps of: (a) eliminating redundant sub-expressions from the query and modifying expensive binary operations in the query to inexpensive binary operations, so that only simple and complex predicates remain in the query; and (b) converting the complex predicates remaining in the query to simple predicates by application of a generalized selection (GS) operator.
Claim 3
Dependent Claim
22 words
The method of claim 1, further comprising the step of applying a simplification identity to a SELECT DISTINCT operator in the query.
Claim 4
Dependent Claim
24 words
The method of claim 1, further comprising the step of applying a simplification identity for a push-up of a GROUPBY operator in the query.
Claim 5
Dependent Claim
142 words
The method of claim 1, wherein the GS operator, σ * p r 2 , r 3 ! (r 1 ), of relation r 1 with respect to relations r 2 and r 3 comprises the relation (R 1 , V 1 , E'), wherein: E'=σ.sub.p (r.sub.1){π.sup.c.sub.R.sbsb.2.sub.V.sbsb.2 (r.sub.1)-π.sup.c.sub.R.sbsb.2.sub.V.sbsb.2 (σ.sub.p (r.sub.1))} {π.sup.c.sub.R.sbsb.3.sub.V.sbsb.3 (r.sub.1)-π.sup.c.sub.R.sbsb.3.sub.V.sbsb.3 (σ.sub.p (r.sub.1))} and wherein r 1 =(R 1 , V 1 , E 1 ), r 2 =(R 2 , V 2 , E 2 ), and r 3 =(R 3 , V 3 , E 3 ) comprise three relations such that R 2 .OR right.R 1 , R 3 .OR right.R 1 , R 2 ∩R 3 =.o slashed., V 2 .OR right.V 1 , V 3 .OR right.V 1 , and V 2 ∩V 3 =.o slashed., and p denotes a null-intolerant predicate in R 1 .
Claim 6
Dependent Claim
54 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU22## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 7
Dependent Claim
54 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU23## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 8
Dependent Claim
46 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU24## where ⊙.di-elect cons.{→, ←, ⃡}wherein X.sub.i =(R.sub.i, V.sub.i, E.sub.i) are relational expressions for 1≦i≦3, and p.sub.i,j denote the predicates between expressions X.sub.i and X.sub.j.
Claim 9
Dependent Claim
59 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU25## where ⊙.di-elect cons.{→, ←, ⃡} wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 10
Dependent Claim
54 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU26## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 11
Dependent Claim
54 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU27## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 12
Dependent Claim
54 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU28## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 13
Dependent Claim
54 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU29## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 14
Dependent Claim
54 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU30## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 15
Dependent Claim
54 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU31## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 16
Dependent Claim
54 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU32## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 17
Dependent Claim
54 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU33## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 18
Dependent Claim
54 words
The method of claim 1, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU34## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 19
Independent Claim
79 words
An apparatus for simplifying a query performed by a computer to retrieve data from a relational database stored in a electronic storage device, comprising: (a) means for eliminating redundant sub-expressions from the query and modifying expensive binary operations in the query to inexpensive binary operations, so that only simple and complex predicates remain in the query; and (b) means for converting the complex predicates remaining in the query to simple predicates by application of a generalized selection (GS) operator.
Claim 20
Independent Claim
79 words
An apparatus for simplifying a query performed by a computer to retrieve data from a relational database stored in a electronic storage device, comprising: (a) means for eliminating redundant sub-expressions from the query and modifying expensive binary operations in the query to inexpensive binary operations, so that only simple and complex predicates remain in the query; and (b) means for converting the complex predicates remaining in the query to simple predicates by application of a generalized selection (GS) operator.
Claim 21
Dependent Claim
21 words
The apparatus of claim 18, further comprising means for applying a simplification identity to a SELECT DISTINCT operator in the query.
Claim 22
Dependent Claim
23 words
The apparatus of claim 18, further comprising means for applying a simplification identity for a push-up of a GROUPBY operator in the query.
Claim 23
Dependent Claim
141 words
The apparatus of claim 18, wherein the GS operator, σ * p r 2 , r 3 ! (r 1 ), of relation r 1 with respect to relations r 2 and r 3 comprises the relation (R 1 , V 1 , E'), wherein: E'=σ.sub.p (r.sub.1){π.sup.c.sub.R.sbsb.2.sub.V.sbsb.2 (r.sub.1)-π.sup.c.sub.R.sbsb.2.sub.V.sbsb.2 (σ.sub.p (r.sub.1))}{π.sup.c.sub.R.sbsb.3.sub.V.sbsb.3 (r.sub.1)-π.sup.c.sub.R.sbsb.3.sub.V.sbsb.3 (σ.sub.p (r.sub.1))} and wherein r 1 =(R 1 , V 1 , E 1 ), r 2 =(R 2 , V 2 , E 2 ), and r 3 =(R 3 , V 3 , E 3 ) comprise three relations such that R 2 .OR right.R 1 , R 3 .OR right.R 1 , R 2 ∩R 3 =.o slashed., V 2 .OR right.V 1 , V 3 .OR right.V 1 , and V 2 ∩V 3 =.o slashed., and p denotes a null-intolerant predicate in R 1 .
Claim 24
Dependent Claim
54 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU35## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 25
Dependent Claim
54 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU36## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 26
Dependent Claim
47 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU37## where ⊙.di-elect cons.{, →, ←, ⃡}wherein X.sub.i =(R.sub.i, V.sub.i, E.sub.i) are relational expressions for 1≦i≦3, and p.sub.i,j denote the predicates between expressions X.sub.i and X.sub.j.
Claim 27
Dependent Claim
47 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU38## where ⊙.di-elect cons.{, →, ←, ⃡}wherein X.sub.i =(R.sub.i, V.sub.i, E.sub.i) are relational expressions for 1≦i≦3, and p.sub.i,j denote the predicates between expressions X.sub.i and X.sub.j.
Claim 28
Dependent Claim
54 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU39## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 29
Dependent Claim
54 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU40## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 30
Dependent Claim
54 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU41## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 31
Dependent Claim
54 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU42## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 32
Dependent Claim
54 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU43## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 33
Dependent Claim
54 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU44## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 34
Dependent Claim
54 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU45## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 35
Dependent Claim
54 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU46## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 36
Dependent Claim
54 words
The apparatus of claim 18, wherein the means for converting comprises means for applying a simplification expression to the query comprising: ##EQU47## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 37
Dependent Claim
95 words
An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of simplifying a query performed by a computer to retrieve data from a relational database stored in a electronic storage device, the method comprising the steps of: (a) eliminating redundant sub-expressions from the query and modifying expensive binary operations in the query to inexpensive binary operations, so that only simple and complex predicates remain in the query; and (b) converting the complex predicates remaining in the query to simple predicates by application of a generalized selection (GS) operator.
Claim 38
Dependent Claim
95 words
An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of simplifying a query performed by a computer to retrieve data from a relational database stored in a electronic storage device, the method comprising the steps of: (a) eliminating redundant sub-expressions from the query and modifying expensive binary operations in the query to inexpensive binary operations, so that only simple and complex predicates remain in the query; and (b) converting the complex predicates remaining in the query to simple predicates by application of a generalized selection (GS) operator.
Claim 39
Dependent Claim
27 words
The article of manufacture of claim 35, wherein the method further comprises the step of applying a simplification identity to a SELECT DISTINCT operator in the query.
Claim 40
Dependent Claim
29 words
The article of manufacture of claim 35, wherein the method further comprises the step of applying a simplification identity for a push-up of a GROUPBY operator in the query.
Claim 41
Dependent Claim
143 words
The article of manufacture of claim 35, wherein the GS operator, σ * p r 2 , r 3 ! (r 1 ), of relation r 1 with respect to relations r 2 and r 3 comprises the relation (R 1 , V 1 , E'), wherein: E'=σ.sub.p (r.sub.1){π.sup.c.sub.R.sbsb.2.sub.V.sbsb.2 (r.sub.1)-π.sup.c.sub.R.sbsb.2.sub.V.sbsb.2 (σ.sub.p (r.sub.1))}{π.sup.c.sub.R.sbsb.3.sub.V.sbsb.3 (r.sub.1)-π.sup.c.sub.R.sbsb.3.sub.V.sbsb.3 (σ.sub.p (r.sub.1))} and wherein r 1 =(R 1 , V 1 , E 1 ), r 2 =(R 2 , V 2 , E 2 ), and r 3 =(R 3 , V 3 , E 3 ) comprise three relations such that R 2 .OR right.R 1 , R 3 .OR right.R 1 , R 2 ∩R 3 =.o slashed., V 2 .OR right.V 1 , V 3 .OR right.V 1 , and V 2 ∩V 3 =.o slashed., and p denotes a null-intolerant predicate in R 1 .
Claim 42
Dependent Claim
56 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU48## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 43
Dependent Claim
56 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU49## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 44
Dependent Claim
49 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU50## where ⊙.di-elect cons.{, →, ←, ⃡}wherein X.sub.i =(R.sub.i, V.sub.i, E.sub.i) are relational expressions for 1≦i≦3, and p.sub.i,j denote the predicates between expressions X.sub.i and X.sub.j.
Claim 45
Dependent Claim
49 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU51## where ⊙.di-elect cons.{, →, ←, ⃡}wherein X.sub.i =(R.sub.i, V.sub.i, E.sub.i) are relational expressions for 1≦i≦3, and p.sub.i,j denote the predicates between expressions X.sub.i and X.sub.j.
Claim 46
Dependent Claim
56 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU52## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 47
Dependent Claim
56 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU53## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 48
Dependent Claim
56 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU54## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 49
Dependent Claim
56 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU55## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 50
Dependent Claim
56 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU56## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 51
Dependent Claim
56 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU57## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 52
Dependent Claim
56 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU58## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 53
Dependent Claim
56 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU59## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
Claim 54
Dependent Claim
56 words
The article of manufacture of claim 35, wherein the converting step comprises the step of applying a simplification expression to the query comprising: ##EQU60## wherein X i =(R i , V i , E i ) are relational expressions for 1≦i≦3, and p i ,j denote the predicates between expressions X i and X j .
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-09-27 | 2003-03-29 | 2003-09-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-27 | 2007-03-29 | 2007-09-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-27 | 2011-03-29 | 2011-09-28 | $7700.00 | Window Closed / Lapsed |