Patent US5864847A successfully refreshed from Google Patents.
US5864847A
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-07-30
•
Granted: 1999-01-26
•
Expires: 2017-07-30
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-11-08 09:12
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: 21
Claim 1
Independent Claim
80 words
A method of reordering a query in a computer having a memory wherein the query has a plurality of relations and at least one binary operator amongst two or more of the relations, and wherein the query is performed by the computer to retrieve data from a data storage device connected to the computer comprising the steps of: (a) determining a generalized selection (GS) operator for the query relations; and (b) using the GS operator to obtain a query result.
Claim 2
Independent Claim
80 words
A method of reordering a query in a computer having a memory wherein the query has a plurality of relations and at least one binary operator amongst two or more of the relations, and wherein the query is performed by the computer to retrieve data from a data storage device connected to the computer comprising the steps of: (a) determining a generalized selection (GS) operator for the query relations; and (b) using the GS operator to obtain a query result.
Claim 3
Dependent Claim
55 words
The method of claim 1, the query further having a unary operator amongst two or more of the relations, the determining step further comprising the steps of: analyzing the unary and binary operators between the relations to determine the need to evaluate the GS operator; and if the GS operator is-needed, computing the GS operator.
Claim 4
Dependent Claim
136 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 1 ), wherein: E.sup.1 =σ.sub.p (r.sub.1) {π.sub.R.sup.c.sbsb.2.sub.V.sbsb.2 (r.sub.1)-π.sub.R.sup.c.sub.V.sbsb.2 (σ.sub.p (r.sub.1))} {π.sub.R.sbsb.3.sup.c.sub.V.sbsb.3 (r.sub.1)-π.sub.R.sbsb.3.sup.c.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 =φ, V 2 .OR right.V 1 , V 3 .OR right.V 1 , and V 2 ∩V 3 =φ, and p denotes a null-intolerant predicate in R 1 .
Claim 5
Independent Claim
51 words
An apparatus for reordering a query having a plurality of relations and at least one binary operator amongst two or more of the relations, comprising: (a) means for determining a generalized selection (GS) operator for the query relations; and (b) means for using the GS operator to obtain a query result.
Claim 6
Independent Claim
51 words
An apparatus for reordering a query having a plurality of relations and at least one binary operator amongst two or more of the relations, comprising: (a) means for determining a generalized selection (GS) operator for the query relations; and (b) means for using the GS operator to obtain a query result.
Claim 7
Dependent Claim
58 words
The apparatus of claim 4, the query further having a unary operator amongst two or more of the relations, the means for determining further comprising: means for analyzing the unary and binary operators between the relations to determine the need to evaluate the GS operator; and means for computing the GS operator, if the GS operator is needed.
Claim 8
Dependent Claim
139 words
The apparatus of claim 4, 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 1 ), wherein: e.sup.1 =σ.sub.p (r.sub.1) {π.sub.R.sbsb.2.sup.c.sub.V.sbsb.2 (r.sub.1)-π.sub.R.sbsb.2.sup.c.sub.v.sbsb.2 (σ.sub.p (r.sub.1))} {π.sub.R.sbsb.3.sup.c.sub.V.sbsb.3 (r.sub.1)-π.sub.R.sbsb.3.sup.c.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 =φ, V 2 .OR right.V 1 , V 3 .OR right.V 1 , and V 2 ∩V 3 =φ, and p denotes a null-intolerant predicate in R 1 .
Claim 9
Dependent Claim
65 words
An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of reordering a query having a plurality of relations and at least one binary operator amongst two or more of the relations, comprising the steps of: (a) determining a generalized selection (GS) operator for the query relations; and (b) using the GS operator to obtain a query result.
Claim 10
Dependent Claim
65 words
An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of reordering a query having a plurality of relations and at least one binary operator amongst two or more of the relations, comprising the steps of: (a) determining a generalized selection (GS) operator for the query relations; and (b) using the GS operator to obtain a query result.
Claim 11
Dependent Claim
58 words
The article of manufacture of claim 7, the query further having a unary operator amongst two or more of the relations, the determining step further comprising the steps of: analyzing the unary and binary operators between the relations to determine the need to evaluate the GS operator; and if the GS operator is needed, computing the GS operator.
Claim 12
Dependent Claim
140 words
The article of manufacture of claim 7, 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 1 ), wherein: E.sup.1 =σ.sub.p (r.sub.1) {π.sub.R.sbsb.2.sup.c.sub.v.sbsb.2 (r.sub.1)-π.sub.R.sbsb.2.sup.c.sub.V.sbsb.2 (σ.sub.p (r.sub.1))} {π.sub.R.sbsb.3.sup.c.sub.V.sbsb.3 (r.sub.1)-π.sub.R.sbsb.3.sup.c.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 =φ, V 2 .OR right.V 1 , V 3 .OR right.V 1 , and V 2 ∩V 3 =φ, and p denotes a null-intolerant predicate in R 1 .
Claim 13
Independent Claim
59 words
A method of computing an outer join between two or more relations in a query that is performed in a memorv of a computer to retrieve data from a data storage device, comprising the steps of: (a) determining a generalized selection (GS) operator for the relations; and (b) applying the GS operator to a cross product of the relations.
Claim 14
Independent Claim
59 words
A method of computing an outer join between two or more relations in a query that is performed in a memorv of a computer to retrieve data from a data storage device, comprising the steps of: (a) determining a generalized selection (GS) operator for the relations; and (b) applying the GS operator to a cross product of the relations.
Claim 15
Dependent Claim
137 words
The method of claim 10, 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 1 , wherein: E.sup.1 =σ.sub.p (r.sub.1) {π.sub.R.sbsb.2.sup.c.sub.V.sbsb.2 (r.sub.1)-π.sub.R.sbsb.2.sup.c.sub.V.sbsb.2 (σ.sub.p (r.sub.1))} {π.sub.R.sbsb.3.sup.c.sub.V.sbsb.3 (r.sub.1)-π.sub.R.sbsb.3.sup.c.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 =φ, V 2 .OR right.V 1 , V 3 .OR right.V 1 , and V 2 ∩V 3 =100, and p denotes a null-intolerant predicate in R 1 .
Claim 16
Independent Claim
43 words
An apparatus for computing an outer join between two or more relations in a query, comprising: (a) means for determining a generalized selection (GS) operator for the relations; and (b) means for applying the GS operator to a cross product of the relations.
Claim 17
Independent Claim
43 words
An apparatus for computing an outer join between two or more relations in a query, comprising: (a) means for determining a generalized selection (GS) operator for the relations; and (b) means for applying the GS operator to a cross product of the relations.
Claim 18
Dependent Claim
138 words
The apparatus of claim 12, 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 1 ) wherein: E.sup.1 =σ.sub.p (r.sub.1) {π.sub.R.sbsb.2.sup.c.sub.v.sbsb.2 (r.sub.1)-π.sub.R.sbsb.2.sup.c.sub.V.sbsb.2 (σ.sub.p (r.sub.1))} {π.sub.R.sbsb.3.sup.c.sub.v.sbsb.3 (r.sub.1)-π.sub.R.sbsb.3.sup.c.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 =φ, V 2 .OR right.V 1 , V 3 .OR right.V 1 , and V 2 ∩V 3 =φ, and p denotes a null-intolerant predicate in R 1 .
Claim 19
Dependent Claim
59 words
An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of computing an outer join between two or more relations in a query, the method comprising the steps of: (a) determining a generalized selection (GS) operator for the relations; and (b) applying the GS operator to a cross product of the relations.
Claim 20
Dependent Claim
59 words
An article of manufacture comprising a computer program carrier embodying one or more instructions of a method of computing an outer join between two or more relations in a query, the method comprising the steps of: (a) determining a generalized selection (GS) operator for the relations; and (b) applying the GS operator to a cross product of the relations.
Claim 21
Dependent Claim
138 words
The article of manufacture of claim 14, 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 1 ), wherein: E.sup.1 =σ.sub.p (r.sub.1) {π.sub.R.sbsb.2.sup.c.sub.V.sbsb.2 (r.sub.1)-π.sub.R.sbsb.2.sup.c.sub.V.sbsb.2 (σ.sub.p (r.sub.1))} {π.sub.R.sbsb.3.sup.c.sub.V.sbsb.3 (r.sub.1)-π.sub.R.sbsb.3.sup.c.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 =φ, V 2 .OR right.V 1 , V 3 .OR right.V 1 , and V 2 ∩V 3 =φ, and p denotes a null-intolerant predicate in R 1 .
References Cited (Backward Citations)
US5557791A
Cited
US5367675A
Cited
US5412804A
Cited
US5680603A
Cited
US5701455A
Cited
US5724568A
Cited
US5659728A
Cited
US5701454A
Cited
US5713015A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-01-25 | 2002-07-27 | 2003-01-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-01-25 | 2006-07-27 | 2007-01-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-01-25 | 2010-07-27 | 2011-01-26 | $7700.00 | Window Closed / Lapsed |