US5890148A
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: 1997-12-08
•
Granted: 1999-03-30
•
Expires: 2017-12-08
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-11-01 07:03
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: 6
Claim 1
Independent Claim
275 words
A method of identifying a keySet(e) of an expression e=LR, where e is the expression, ⊙ is a root of the expression, said root being a binary operator, P LR is a predicate, L is a left child, and R is a right child, the keySet(e) being used to increase the efficiency of processing a query, wherein the keySet(e) is used to denote the set containing all minimal keys of the expression e, comprising the steps of: identifying a keySet (L) and a keySet(R); generating a first set S 1 by concantenating each element in said keySet (L) with each element in said keySet(R); generating a second set S 2 , wherein if the binary operator is a join or a left outer join, and if said predicate is equi-join, and if attributes that are common to both a schema of the predicate and a schema of the right child R are in said keySet (R), then said second set S 2 is defined as said keySet(L), otherwise said second set S 2 is an empty set; generating a third set S 3 , wherein if the binary operator is a join or a right outer join, and if the predicate is equi-join, and if attributes that are common to both a schema of the predicate and a schema of the left child L are in said keySet(L), then said third set S 3 is defined as said keySet (R), otherwise said third set S 3 is an empty set; and defining the keySet(e) as equal to the union of S 1 , S 2 , and S 3 , such that keySet(e)=S.sub.1 ∪S.sub.2 ∪S.sub.3.
Claim 2
Independent Claim
275 words
A method of identifying a keySet(e) of an expression e=LR, where e is the expression, ⊙ is a root of the expression, said root being a binary operator, P LR is a predicate, L is a left child, and R is a right child, the keySet(e) being used to increase the efficiency of processing a query, wherein the keySet(e) is used to denote the set containing all minimal keys of the expression e, comprising the steps of: identifying a keySet (L) and a keySet(R); generating a first set S 1 by concantenating each element in said keySet (L) with each element in said keySet(R); generating a second set S 2 , wherein if the binary operator is a join or a left outer join, and if said predicate is equi-join, and if attributes that are common to both a schema of the predicate and a schema of the right child R are in said keySet (R), then said second set S 2 is defined as said keySet(L), otherwise said second set S 2 is an empty set; generating a third set S 3 , wherein if the binary operator is a join or a right outer join, and if the predicate is equi-join, and if attributes that are common to both a schema of the predicate and a schema of the left child L are in said keySet(L), then said third set S 3 is defined as said keySet (R), otherwise said third set S 3 is an empty set; and defining the keySet(e) as equal to the union of S 1 , S 2 , and S 3 , such that keySet(e)=S.sub.1 ∪S.sub.2 ∪S.sub.3.
Claim 3
Dependent Claim
364 words
A computer program product for use with a computer system, said computer program product comprising: a computer usable medium having computer readable program code means embodied in said medium for causing the computer system to identify a keySet(e) of an expression e=LR , where e is the expression, ⊙ is a root of the expression, said root being a binary operator, P LR is a predicate, L is a left child, and R is a right child, the keySet(e) being used to increase the efficiency of processing a query, wherein said keySet(e) is used to denote a set containing all minimal keys of said expression e, said computer readable program code means comprising: computer readable program code means for enabling the computer system to identify a keySet (L) and a keySet(R); computer readable program code means for enabling the computer system to generate a first set S 1 by concantenating each element in said keySet(L) with each element in said keySet(R); computer readable program code means for enabling the computer system to generate a second set S 2 , wherein if said binary operator is a join or a left outer join, and if said predicate is equi-join, and if attributes that are common to both a schema of said predicate and a schema of said right child R are in said keySet (R), then said second set S 2 is defined as said keySet(L), otherwise said second set S 2 is an empty set; computer readable program code means for enabling the computer system to generate a third set S 3 , wherein if said binary operator is a join or a right outer join, and if said predicate is equi-join, and if attributes that are common to both a schema of said predicate and a schema of said left child L are in said keySet(L), then said third set S 3 is defined as said keySet(R), otherwise said third set S 3 is an empty set; and computer readable program code means for enabling the computer system to define said keySet(e) as equal to the union of S 1 , S 2 , and S 3 , such that keySet(e)=S.sub.1 ∪S.sub.2 ∪S.sub.3.
Claim 4
Dependent Claim
364 words
A computer program product for use with a computer system, said computer program product comprising: a computer usable medium having computer readable program code means embodied in said medium for causing the computer system to identify a keySet(e) of an expression e=LR , where e is the expression, ⊙ is a root of the expression, said root being a binary operator, P LR is a predicate, L is a left child, and R is a right child, the keySet(e) being used to increase the efficiency of processing a query, wherein said keySet(e) is used to denote a set containing all minimal keys of said expression e, said computer readable program code means comprising: computer readable program code means for enabling the computer system to identify a keySet (L) and a keySet(R); computer readable program code means for enabling the computer system to generate a first set S 1 by concantenating each element in said keySet(L) with each element in said keySet(R); computer readable program code means for enabling the computer system to generate a second set S 2 , wherein if said binary operator is a join or a left outer join, and if said predicate is equi-join, and if attributes that are common to both a schema of said predicate and a schema of said right child R are in said keySet (R), then said second set S 2 is defined as said keySet(L), otherwise said second set S 2 is an empty set; computer readable program code means for enabling the computer system to generate a third set S 3 , wherein if said binary operator is a join or a right outer join, and if said predicate is equi-join, and if attributes that are common to both a schema of said predicate and a schema of said left child L are in said keySet(L), then said third set S 3 is defined as said keySet(R), otherwise said third set S 3 is an empty set; and computer readable program code means for enabling the computer system to define said keySet(e) as equal to the union of S 1 , S 2 , and S 3 , such that keySet(e)=S.sub.1 ∪S.sub.2 ∪S.sub.3.
Claim 5
Dependent Claim
274 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for identifying a keySet(e) being a binary operator, P LR is a predicate, L is a left child, and R is a right child, the keySet(e) being used to increase the efficiency of processing a query, wherein the keySet(e) is used to denote the set containing all minimal keys of the expression e, comprising the method steps of: identifying a keySet(L) and a keySet(R); generating a first set S 1 by concantenating each element in said keySet(L) with each element in said keySet(R); generating a second set S 2 , wherein if the binary operator is a join or a left outer join, and if the predicate is equi-join, and if attributes that are common to both a schema of the predicate and a schema of the right child R are in said keySet(R), then said second set S 2 is defined as said keySet(L), otherwise said second set S 2 is an empty set; generating a third set S 3 , wherein if the binary operator is a join or a right outer join, and if the predicate is equi-join, and if attributes that are common to both a schema of the predicate and a schema of the left child L are in said keySet(L), then said third set S 3 is defined as said keySet(R), otherwise said third set S 3 is an empty set; and defining the keySet(e) as equal to the union of S 1 , S 2 , and S 3 , such that keySet(e)=S.sub.1 ∪S.sub.2 ∪S.sub.3.
Claim 6
Dependent Claim
274 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for identifying a keySet(e) being a binary operator, P LR is a predicate, L is a left child, and R is a right child, the keySet(e) being used to increase the efficiency of processing a query, wherein the keySet(e) is used to denote the set containing all minimal keys of the expression e, comprising the method steps of: identifying a keySet(L) and a keySet(R); generating a first set S 1 by concantenating each element in said keySet(L) with each element in said keySet(R); generating a second set S 2 , wherein if the binary operator is a join or a left outer join, and if the predicate is equi-join, and if attributes that are common to both a schema of the predicate and a schema of the right child R are in said keySet(R), then said second set S 2 is defined as said keySet(L), otherwise said second set S 2 is an empty set; generating a third set S 3 , wherein if the binary operator is a join or a right outer join, and if the predicate is equi-join, and if attributes that are common to both a schema of the predicate and a schema of the left child L are in said keySet(L), then said third set S 3 is defined as said keySet(R), otherwise said third set S 3 is an empty set; and defining the keySet(e) as equal to the union of S 1 , S 2 , and S 3 , such that keySet(e)=S.sub.1 ∪S.sub.2 ∪S.sub.3.
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-03-29 | 2002-09-28 | 2003-03-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-29 | 2006-09-28 | 2007-03-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-29 | 2010-09-28 | 2011-03-30 | $7700.00 | Window Closed / Lapsed |