US5659728A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for generating uniqueness information for optimizing an SQL query
Assignee: International Business Machines Corp
•
Filing: 1994-12-30
•
Granted: 1997-08-19
•
Expires: 2014-12-30
Abstract
Abstract A system and method of determining uniqueness properties of an expression. A root of the expression is first determined, where the root is one of a base relation, a unary operation or a binary operation. Once the root is determined, a first procedure of an augmented unique process is called to determine uniqueness properties of a child of that root. The procedure called is chosen based on the determined root. Where the root is a base relation, a first procedure of a uniqueness process is applied to determine the uniqueness properties of the base relation. Where the root is a unary or binary operation, the called procedure is suspended, a second procedure of the augmented unique process is called to determine the uniqueness properties of the child of the operation, and this process is repeated until a base relation is reached. Once a base relation is reached, the first procedure of the uniqueness process is applied to determine the uniqueness properties of the reached base relation. A next procedure of a uniqueness process is applied to determine the uniqueness properties of a parent operator of the based relation. The procedure applied is chosen based on a type of operation represented by the parent. The process then unwinds to determine the uniqueness properties for each ancestor of the base relation(s).
Inventors
- 👤 Gautam Bhargava
- 👤 Piyush Goel
- 👤 Balakrishna R. Iyer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 19:11
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
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
233 words
A method of determining uniqueness properties of an expression for query optimization, comprising the steps of: a) determining a root of the expression, wherein said root is one of a base relation, a unary operation or a binary operation; b) calling a first one of a plurality of procedures of an augmented unique process to determine uniqueness properties of a child of the root, wherein the procedure called is chosen based on said determined root; c) where said root is a base relation, applying a first procedure of a uniqueness process to determine the uniqueness properties of said base relation; d) where said root is a unary or binary operation, i suspending the called procedure, ii calling a second one of a plurality of procedures of said augmented unique process to determine the uniqueness properties of the child of said unary or binary operation, iii repeating said steps i and ii until a base relation is reached, and iv applying a first procedure of a uniqueness process to determine the uniqueness properties of said reached base relation; and e) applying a second of a plurality of procedures of a uniqueness process to determine the uniqueness properties of a parent operator of said base relation, wherein said procedure applied is chosen based on a type of operation represented by said parent; and f) repeating said step (e) for each ancestor of a base relation.
Claim 2
Independent Claim
233 words
A method of determining uniqueness properties of an expression for query optimization, comprising the steps of: a) determining a root of the expression, wherein said root is one of a base relation, a unary operation or a binary operation; b) calling a first one of a plurality of procedures of an augmented unique process to determine uniqueness properties of a child of the root, wherein the procedure called is chosen based on said determined root; c) where said root is a base relation, applying a first procedure of a uniqueness process to determine the uniqueness properties of said base relation; d) where said root is a unary or binary operation, i suspending the called procedure, ii calling a second one of a plurality of procedures of said augmented unique process to determine the uniqueness properties of the child of said unary or binary operation, iii repeating said steps i and ii until a base relation is reached, and iv applying a first procedure of a uniqueness process to determine the uniqueness properties of said reached base relation; and e) applying a second of a plurality of procedures of a uniqueness process to determine the uniqueness properties of a parent operator of said base relation, wherein said procedure applied is chosen based on a type of operation represented by said parent; and f) repeating said step (e) for each ancestor of a base relation.
Claim 3
Dependent Claim
55 words
The method of claim 1, wherein said first procedure of said uniqueness process comprises the steps of: setting a unique set for said base relation equal to a key set for said base relation; and defining a strongly bound set, a weakly bound set and a join attribute set as empty sets for the expression.
Claim 4
Dependent Claim
153 words
The method of claim 1, wherein if said root is a selector operation, said second of a plurality of procedures of said uniqueness process comprises the steps of: determining whether there exists a set of attributes, K, in a unique set of a child of the expression such that all attributes in K are strongly bound by a predicate to determine whether a one-tuple condition exists; if said one-tuple condition exists, adding all attributes currently in a node to a unique set of said node and to a strongly bound set of said node; if said one-tuple condition does not exist, adding attributes in K that are not strongly bound to said unique set and to said strongly bound set of said node; defining a weakly bound set and a join attribute set as empty sets for said node; and defining each attribute that is strongly bound as being a level one attribute.
Claim 5
Dependent Claim
144 words
The method of claim 1, wherein if said root is a delta projection operation, said second of a plurality of procedures of said uniqueness process comprises the steps of: (a) defining an attribute set as including all attributes for the projection; (b) determining whether said attribute set contains a joining attribute set of a child of the projection; (c) if said attribute set contains a joining attribute set of the child, then for each attribute in said attribute set that is found in a weakly bound set of its child as well as in said attribute set, determining whether a level of said attribute is lower than the level of another attribute in said attribute set; and (d) if said level of said attribute is lower than the level of another attribute in said attribute set, removing said first attribute from said attribute set.
Claim 6
Dependent Claim
38 words
The method of claim 4, wherein said second of a plurality of procedures of said uniqueness process further comprises the step of removing from said attribute set all of said attributes that are strongly bound in the child.
Claim 7
Dependent Claim
94 words
The method of claim 5, wherein said second of a plurality of procedures of said uniqueness process further comprises the steps of: determining whether there are any attributes remaining in said attribute set; if no attributes remain in said attribute set, a unique set is defined as all of said attributes originally in said defined attribute set; and if one or more of said attributes remain in said attribute set, said unique set is defined as all of the attributes in the child combined with all of said attributes remaining in said attribute set.
Claim 8
Dependent Claim
83 words
The method of claim 6, wherein said second of a plurality of procedures of said uniqueness process further comprises the steps of: defining a strongly bound set as the intersection of a strongly bound set of the child with a set comprising all of said attributes originally in said defined attribute set; and defining a weakly bound set as the intersection of a weakly bound set of the child with a set comprising all of said attributes originally in said defined attribute set.
Claim 9
Dependent Claim
108 words
The method of claim 1, wherein if said root is a non-duplicate removing projection operation, said second of a plurality of procedures of said uniqueness process comprises the steps of: defining a unique set as a unique set of a child of the root; defining a strongly bound set as the intersection of a strongly bound set of the child with a set of all attributes of said root; defining a weakly bound set as the intersection of a weakly bound set of the child with a set of all attributes of said root; and defining a join attribute set as a join attribute set of the child.
Claim 10
Dependent Claim
226 words
The method of claim 1, wherein if said root is a binary operator having a left child and a right child, said second of a plurality of procedures of said uniqueness process comprises the steps of: concentrating each element in a unique set of a left child with each element in a unique set of the right child to create a first set; if the operator is a join or left outer join operator, and a predicate P LR is an equi-join, and if the attributes that are common to both a schema of the predicate and a schema of the right child are in a unique set of the right child, then a second set is defined as a unique set of the left child, otherwise, said second set is defined as an empty set; if the operator is a join or right outer join operator, and the predicate P LR is an equi-join, and if the attributes that are common to both the schema of the predicate and the schema of the left child are in the unique set of the left child, then a third set is defined as a unique set of the left child, otherwise said third set is defined as the empty set; and defining uniqueness properties of the operator as minimum attributes of said first, second and third sets.
Claim 11
Dependent Claim
336 words
The method of claim 9, wherein if said root is a join operation, said second of a plurality of procedures of said uniqueness process further comprises the steps of: defining a strongly bound set of said attributes as the union of a strongly bound set of the left child and the strongly bound set of the right child; and defining a weakly bound set of said attributes as the union of a weakly bound set of the left child and the weakly bound set of the right child; wherein if said root is a left-outer join operation, said second of a plurality of procedures of said uniqueness process further comprises the steps of: defining a strongly bound set of said attributes as a strongly bound set of the left child; and defining a weakly bound set of said attributes as the union of a weakly bound set of the left child and the weakly bound set of the right child and the strongly bound set of the right child; wherein if said root is a right-outer join operation, said second of a plurality of procedures of said uniqueness process further comprises the steps of: defining a strongly bound set of said attributes as the strongly bound set of the right child; and defining a weakly bound set of said attributes as the union of a weakly bound set of the left child and the weakly bound set of the right child and the strongly bound set of the left child; and wherein if said root is a full-outer join operation, said second of a plurality of procedures of said uniqueness process further comprises the steps of: defining a strongly bound set of said attributes as an empty set; and defining a weakly bound set of said attributes as the union of a weakly bound set of the left child and the weakly bound set of the right child and the strongly bound set of the left child and the strongly bound set of the right child.
Claim 12
Dependent Claim
118 words
The method of claim 10, further comprises the steps of: for each attribute in said strongly bound set and said weakly bound set, determining a closure of a predictor set under the predicate, wherein if the predicate contains subclause A=B, one of the following steps is performed (1) if said root is a join operation or a full-outer join operation, the attribute level of B is the same as the level of A, (2) if said root is a left-outer join, the attribute level of B is one lower than the attribute level of A, and (3) if said root is a right-outer join, the attribute level of B is one higher than the attribute level of A.
Claim 13
Dependent Claim
162 words
The method of claim 9, wherein if said root is a binary intersect operator, said second of a plurality of procedures of said uniqueness process further comprises the steps of: defining a strongly bound set as a minimum of a renamed combination of a strongly bound set of the left child and a strongly bound set of the right child; defining a weakly bound set and a join attribute set as the empty set; if the intersect operator is an intersect distinct operator, defining a unique set as the minimum of the renamed set of the combination of the output attributes of the intersect distinct and the unique set of the left child and the unique set of the right child; and if the intersect operator is not an intersect distinct operator, defining the unique set as the minimum of the renamed set of the combination of the unique set of the left child and the unique set of the right child.
Claim 14
Dependent Claim
52 words
The method of claim 9, wherein said second of a plurality of procedures of said uniqueness process comprises the steps of: defining a join attribute set as the union of the attribute set of the left child and the attribute set of the right child and the attributed mentioned in the predicate.
Claim 15
Dependent Claim
19 words
The method of claim 1, further comprising the step of using said uniqueness properties to optimize an SQL query.
References Cited (Backward Citations)
US5551031A
Cited
US5423035A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-08-18 | 2001-02-17 | 2001-08-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-08-18 | 2005-02-17 | 2005-08-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-08-18 | 2009-02-17 | 2009-08-19 | $7700.00 | Window Closed / Lapsed |