US5619692A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Semantic optimization of query order requirements using order detection by normalization in a query compiler system
Assignee: International Business Machines Corp
•
Filing: 1995-02-17
•
Granted: 1997-04-08
•
Expires: 2015-02-17
Abstract
Abstract A procedure for detecting a reordering requirement in a directed record stream during query execution in a relational database processing system. The query compiler component of a relational database processing system includes procedures for building query execution plans (QEPs) for evaluation preparatory to selecting an optimal plan for execution. These plans are constructed from the bottom up using an internal graphical representation for the user query that has a number of relation nodes interconnected by directed record streams (data flows). A relational operation within each node imposes an "order requirement" on the outflow stream represented by an order requirement vector O R . The records within each directed record stream have an "order property" represented by an order property vector O P . Order detection occurs when these two vectors are compared to determine whether the order property satisfies the order requirement. Order detection by normalization (ODN) according to this invention first normalizes the two order specification vectors to remove all attributes made redundant by the effects of predicates and functional dependencies. Query execution plans constructed using ODN are found to execute an order of magnitude faster than those constructed using order detection without normalization.
Inventors
- 👤 Timothy R. Malkemus
- 👤 Eugene J. Shekita
- 👤 David E. Simmen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 20:15
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24537; G06F16/2452; G06F16/24526; G06F16/24542; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
235 words
A method for order detection during processing of a query in a relational database processing system having a stored database including a plurality of base-relations {T} and a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O Ri , wherein each said relation node N i is connected to at least one other said relation node N j by a directed record stream R ij representing a record stream output from said each relation node N i and a record stream input to said other relation node N j ordered according to an order property vector O Pi , wherein i and j are positive integers, said method comprising the steps of: (a) normalizing said order property vector O Pi to produce a normalized order property vector O PNi for said input record stream R ji of a first said relation node N i ; (b) normalizing said order requirement vector O Ri to produce a normalized order requirement vector O RNi for said first relation node N i ; and (c) comparing said normalized order requirement vector O RNi to said normalized order property vector O PNi to detect an ordering requirement for said first relation node N i .
Claim 2
Independent Claim
235 words
A method for order detection during processing of a query in a relational database processing system having a stored database including a plurality of base-relations {T} and a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O Ri , wherein each said relation node N i is connected to at least one other said relation node N j by a directed record stream R ij representing a record stream output from said each relation node N i and a record stream input to said other relation node N j ordered according to an order property vector O Pi , wherein i and j are positive integers, said method comprising the steps of: (a) normalizing said order property vector O Pi to produce a normalized order property vector O PNi for said input record stream R ji of a first said relation node N i ; (b) normalizing said order requirement vector O Ri to produce a normalized order requirement vector O RNi for said first relation node N i ; and (c) comparing said normalized order requirement vector O RNi to said normalized order property vector O PNi to detect an ordering requirement for said first relation node N i .
Claim 3
Dependent Claim
199 words
The method of claim 1 wherein said order property vector O Pi includes a first ordered list of relation attributes (P 1 , . . . , P P ), said order requirement vector O Ri includes a second ordered list of relation attributes (R 1 , . . . , R r ), said relation attributes each belong to a class of equivalent attributes including a head attribute, 0≦p, r are non-negative integers and wherein said normalizing steps (a) and (b) comprise the steps of: (a.1) replacing in said order property vector O Pi each said relation attribute P P in said first ordered list with the head attribute P Hp from said equivalence class containing said each relation attribute P P ; (a.2) eliminating relation attribute duplicates from said first ordered list in said order property vector O Pi ; (b.1) replacing in said order requirement vector O Ri each said relation attribute R r in said second ordered list with the head attribute R Hr from said equivalence class containing said each relation attribute R r ; and (b.2) eliminating relation attribute duplicates from said second ordered list in said order requirement vector O Pi .
Claim 4
Dependent Claim
146 words
The method of claim 2 wherein said order property vector O Pi includes at least one functionally-dependent relation attribute P j that is fully determined by one or more said relational attributes {P k } ordered ahead of said functionally-dependent relation attribute P j in said first ordered list or said order requirement vector O Ri includes at least one functionally-dependent relation attribute R j that is fully determined by one or more said relational attributes {R k } ordered ahead of said functionally-dependent relation attribute R j in said second ordered list, 1≦k≦j are positive integers and wherein said normalizing steps (a) and (b) further comprise the steps of: (a. 3) eliminating each said functionally-dependent relation attribute P j from said order property vector O Pi ; and (b.3) eliminating each said functionally-dependent relation attribute R j from said order requirement vector O Ri .
Claim 5
Dependent Claim
85 words
The method of claim 3 wherein said order property vector O Pi or said order requirement vector O Ri includes at least one bound relation attribute that has the same value for every record in said input record stream R ji and wherein said normalizing steps (a) and (b) further comprise the steps of: (a.4) eliminating each said bound relation attribute from said order property vector O Pi ; and (b.4) eliminating each said bound relation attribute from said order requirement vector O Ri .
Claim 6
Dependent Claim
212 words
The method of claim 1 wherein said order property vector O Pi includes a first ordered list of relation attributes (P 1 , . . . , P p ), said order requirement vector O Ri includes a second ordered list of relation attributes (R 1 , . . . , R r ), said order property vector O Pi includes at least one functionally-dependent relation attribute P j that is fully determined by one or more said relational attributes {P k } ordered ahead of said functionally-dependent relation attribute P j in said first ordered list or said order requirement vector O Ri includes at least one functionally-dependent relation attribute R j that is fully determined by one or more said relational attributes {R k } ordered ahead of said functionally-dependent relation attribute R j in said second ordered list, said relation attributes each belong to a class of equivalent attributes including a head attribute, 1≦k≦j are positive integers, 0≦p, r are non-negative integers and wherein said normalizing steps (a) and (b) comprise the steps of: (a.1) eliminating each said functionally-dependent relation attribute P j from said order property vector O Pi ; and (b.1) eliminating each said functionally-dependent relation attribute R j from said order requirement vector O Ri .
Claim 7
Dependent Claim
227 words
A query compiler system in a relational database processing system comprising: a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O Ri , wherein each said relation node N i is connected to at least one other said relation node N j by a directed record stream R ij representing a record stream output from said each relation node N i and a record stream input to said other relation node N j ordered according to an order property vector O Pi , wherein i and j are positive integers; normalizing means in said data processor for normalizing said order property vector O Pi to produce a normalized order property vector O PNi for said input record stream P ji of a first said relation node N i and for normalizing said order requirement vector O Ri to produce a normalized order requirement vector O RNi for said first relation node N i ; and order detection means coupled to said normalizing means for comparing said normalized order requirement vector O RNi to said normalized order property vector O PNi to detect an ordering requirement for said first relation node N i .
Claim 8
Dependent Claim
227 words
A query compiler system in a relational database processing system comprising: a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O Ri , wherein each said relation node N i is connected to at least one other said relation node N j by a directed record stream R ij representing a record stream output from said each relation node N i and a record stream input to said other relation node N j ordered according to an order property vector O Pi , wherein i and j are positive integers; normalizing means in said data processor for normalizing said order property vector O Pi to produce a normalized order property vector O PNi for said input record stream P ji of a first said relation node N i and for normalizing said order requirement vector O Ri to produce a normalized order requirement vector O RNi for said first relation node N i ; and order detection means coupled to said normalizing means for comparing said normalized order requirement vector O RNi to said normalized order property vector O PNi to detect an ordering requirement for said first relation node N i .
Claim 9
Dependent Claim
199 words
The system of claim 6 wherein said order property vector O Pi includes a first ordered list of relation attributes (P 1 , . . . , P p ), said order requirement vector O Ri includes a second ordered list of relation attributes (R 1 , . . . , R r ), said relation attributes each belong to a class of equivalent attributes including a head attribute, 0≦p, r are non-negative integers and wherein said normalizing means comprises: equivalence substitution means for replacing in said order property vector O Pi each said relation attribute P p in said first ordered list with the head attribute P Hp from said equivalence class containing said each relation attribute P p and for replacing in said order requirement vector O Ri each said relation attribute R r in said second ordered list with the head attribute R Hr from said equivalence class containing said each relation attribute R r ; and duplicates squeezing means for eliminating relation attribute duplicates from said first ordered list in said order property vector O Pi and for eliminating relation attribute duplicates from said second ordered list in said order requirement vector O Pi .
Claim 10
Dependent Claim
141 words
The system of claim 7 wherein said order property vector O Pi includes at least one functionally-dependent relation attribute P j that is fully determined by one or more said relational attributes {P k } ordered ahead of said functionally-dependent relation attribute P j in said first ordered list or said order requirement vector O Ri includes at least one functionally-dependent relation attribute R j that is fully determined by one or more said relational attributes {R k } ordered ahead of said functionally-dependent relation attribute R j in said second ordered list, 1≦k<j are positive integers and wherein said normalizing means further comprises: functional-dependencies squeezing means for eliminating each said functionally-dependent relation attribute P j from said order property vector O Pi and for eliminating each said functionally-dependent relation attribute R j from said order requirement vector O Ri .
Claim 11
Dependent Claim
81 words
The system of claim 8 wherein said order property vector O Pi or said order requirement vector O Ri includes at least one bound relation attribute that has the same value for every record in said input record stream R ji and wherein said normalizing means further comprises: redundancies squeezing means for eliminating each said bound relation attribute from said order property vector O Pi and for eliminating each said bound relation attribute from said order requirement vector O Ri .
Claim 12
Dependent Claim
208 words
The system of claim 6 wherein said order property vector O Pi includes a first ordered list of relation attributes (P 1 , . . . , P p ), said order requirement vector O Ri includes a second ordered list of relation attributes (R 1 , . . . , R r ), said order property vector O Pi includes at least one functionally-dependent relation attribute P j that is fully determined by one or more said relational attributes {P k } ordered ahead of said functionally-dependent relation attribute P j in said first ordered list or said order requirement vector O Ri includes at least one functionally-dependent relation attribute R j that is fully determined by one or more said relational attributes {R k } ordered ahead of said functionally-dependent relation attribute R j in said second ordered list, said relation attributes each belong to a class of equivalent attributes including a head attribute, 1≦k<j are positive integers, 0≦p, r are non-negative integers and wherein said normalizing means comprises: functional-dependencies squeezing means for eliminating each said functionally-dependent relation attribute P j from said order property vector O Pi and for eliminating each said functionally-dependent relation attribute R j from said order requirement vector O Ri .
Claim 13
Dependent Claim
230 words
A database processing system comprising: a stored database including a plurality of base-relations {T}; a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O Ri , wherein each said relation node N i is connected to at least one other said relation node N j by a directed record stream R ij representing a record stream output from said each relation node N i and a record stream input to said other relation node N j ordered according to an order property vector O Pi , wherein i and j are positive integers; normalizing means in said data processor for normalizing said order property vector O Pi to produce a normalized order property vector O PNi for said input record stream R ji of a first said relation node N i and for normalizing said order requirement vector O Ri to produce a normalized order requirement vector O RNi for said first relation node N i ; and order detection means coupled to said normalizing means for comparing said normalized order requirement vector O RNi to said normalized order property vector O PNi to detect an ordering requirement for said first relation node N i .
Claim 14
Dependent Claim
230 words
A database processing system comprising: a stored database including a plurality of base-relations {T}; a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O Ri , wherein each said relation node N i is connected to at least one other said relation node N j by a directed record stream R ij representing a record stream output from said each relation node N i and a record stream input to said other relation node N j ordered according to an order property vector O Pi , wherein i and j are positive integers; normalizing means in said data processor for normalizing said order property vector O Pi to produce a normalized order property vector O PNi for said input record stream R ji of a first said relation node N i and for normalizing said order requirement vector O Ri to produce a normalized order requirement vector O RNi for said first relation node N i ; and order detection means coupled to said normalizing means for comparing said normalized order requirement vector O RNi to said normalized order property vector O PNi to detect an ordering requirement for said first relation node N i .
Claim 15
Dependent Claim
199 words
The system of claim 11 wherein said order property vector O Pi includes a first ordered list of relation attributes (P 1 , . . . , P p ), said order requirement vector O Ri includes a second ordered list of relation attributes (R 1 , . . . , R r ), said relation attributes each belong to a class of equivalent attributes including a head attribute, 0≦p, r are non-negative integers and wherein said normalizing means comprises: equivalence substitution means for replacing in said order property vector O Pi each said relation attribute P p in said first ordered list with the head attribute P Hp from said equivalence class containing said each relation attribute P p and for replacing in said order requirement vector O Ri each said relation attribute R r in said second ordered list with the head attribute R Hr from said equivalence class containing said each relation attribute R r ; and duplicates squeezing means for eliminating relation attribute duplicates from said first ordered list in said order property vector O Pi and for eliminating relation attribute duplicates from said second ordered list in said order requirement vector O Pi .
Claim 16
Dependent Claim
141 words
The system of claim 12 wherein said order property vector O Pi includes at least one functionally-dependent relation attribute P j that is fully determined by one or more said relational attributes {P k } ordered ahead of said functionally-dependent relation attribute P j in said first ordered list or said order requirement vector O Ri includes at least one functionally-dependent relation attribute R j that is fully determined by one or more said relational attributes {R k } ordered ahead of said functionally-dependent relation attribute R j in said second ordered list, 1≦k<j are positive integers and wherein said normalizing means further comprises: functional-dependencies squeezing means for eliminating each said functionally-dependent relation attribute P j from said order property vector O Pi and for eliminating each said functionally-dependent relation attribute R j from said order requirement vector O Ri .
Claim 17
Dependent Claim
81 words
The system of claim 13 wherein said order property vector O Pi or said order requirement vector O Ri includes at least one bound relation attribute that has the same value for every record in said input record stream R ji and wherein said normalizing means further comprises: redundancies squeezing means for eliminating each said bound relation attribute from said order property vector O Pi and for eliminating each said bound relation attribute from said order requirement vector O Ri .
Claim 18
Dependent Claim
208 words
The system of claim 11 wherein said order property vector O Pi includes a first ordered list of relation attributes (P 1 , . . . , P p ), said order requirement vector O Ri includes a second ordered list of relation attributes (R 1 , . . . , R r ), said order property vector O Pi includes at least one functionally-dependent relation attribute P j that is fully determined by one or more said relational attributes {P k } ordered ahead of said functionally-dependent relation attribute P j in said first ordered list or said order requirement vector O Ri includes at least one functionally-dependent relation attribute R j that is fully determined by one or more said relational attributes {R k } ordered ahead of said functionally-dependent relation attribute R j in said second ordered list, said relation attributes each belong to a class of equivalent attributes including a head attribute, 1≦k<j are positive integers, 0≦p, r are non-negative integers and wherein said normalizing means comprises: functional-dependencies squeezing means for eliminating each said functionally-dependent relation attribute P j from said order property vector O Pi and for eliminating each said functionally-dependent relation attribute R j from said order requirement vector O Ri .
Claim 19
Dependent Claim
266 words
A computer program product, for use with a relational database processing system having a stored database including a plurality of base-relations {T} and a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O Ri , wherein each said relation node N i is connected to at least one other said relation node N j by a directed record stream R ij representing a record stream output from said each relation node N i and a record stream input to said other relation node N j ordered according to an order property vector O Pi , wherein i and j are positive integers, said computer program product comprising: a recording medium; means, recorded on said recording medium, for directing said data processor to normalize said order property vector O Pi to produce a normalized order property vector O PNi for said input record stream R ji of a first said relation node N i ; means, recorded on said recording medium, for directing said data processor to normalize said order requirement vector O Ri to produce a normalized order requirement vector O RNi for said first relation node N i ; and means, recorded on said recording medium, for directing said data processor to compare said normalized order requirement vector O RNi to said normalized order property vector O PNi to detect an ordering requirement for said first relation node N i .
Claim 20
Dependent Claim
266 words
A computer program product, for use with a relational database processing system having a stored database including a plurality of base-relations {T} and a data processor for processing queries represented by query graphs {G}, wherein each said query graph G includes a plurality of relation nodes {N i } each representing a relational operation associated with a record ordering requirement represented by an order requirement vector O Ri , wherein each said relation node N i is connected to at least one other said relation node N j by a directed record stream R ij representing a record stream output from said each relation node N i and a record stream input to said other relation node N j ordered according to an order property vector O Pi , wherein i and j are positive integers, said computer program product comprising: a recording medium; means, recorded on said recording medium, for directing said data processor to normalize said order property vector O Pi to produce a normalized order property vector O PNi for said input record stream R ji of a first said relation node N i ; means, recorded on said recording medium, for directing said data processor to normalize said order requirement vector O Ri to produce a normalized order requirement vector O RNi for said first relation node N i ; and means, recorded on said recording medium, for directing said data processor to compare said normalized order requirement vector O RNi to said normalized order property vector O PNi to detect an ordering requirement for said first relation node N i .
Claim 21
Dependent Claim
241 words
The computer program product of claim 16 wherein said order property vector O Pi includes a first ordered list of relation attributes (P 1 , . . . , P p ), said order requirement vector O Ri includes a second ordered list of relation attributes (R 1 , . . . , R r ), said relation attributes each belong to a class of equivalent attributes including a head attribute and wherein 0≦p, r are non-negative integers, said computer program product further comprising: means, recorded on said recording medium, for directing said data processor to replace in said order property vector O Pi each said relation attribute P p in said first ordered list with the head attribute P Hp from said equivalence class containing said each relation attribute P p ; means, recorded on said recording medium, for directing said data processor to eliminate relation attribute duplicates from said first ordered list in said order property vector O Pi ; means, recorded on said recording medium, for directing said data processor to replace in said order requirement vector O Ri each said relation attribute R r in said second ordered list with the head attribute R Hr from said equivalence class containing said each relation attribute R r ; and means, recorded on said recording medium, for directing said data processor to eliminate relation attribute duplicates from said second ordered list in said order requirement vector O Pi .
Claim 22
Dependent Claim
164 words
The computer program product of claim 17 wherein said order property vector O Pi includes at least one functionally-dependent relation attribute P j that is fully determined by one or more said relational attributes {P k } ordered ahead of said functionally-dependent relation attribute P j in said first ordered list or said order requirement vector O Ri includes at least one functionally-dependent relation attribute R j that is fully determined by one or more said relational attributes {R k } ordered ahead of said functionally-dependent relation attribute R j in said second ordered list and wherein 1≦k<j are positive integers, said computer program product further comprising: means, recorded on said recording medium, for directing said data processor to eliminate each said functionally-dependent relation attribute P j from said order property vector O Pi ; and means, recorded on said recording medium, for directing said data processor to eliminate each said functionally-dependent relation attribute R j from said order requirement vector O Ri .
Claim 23
Dependent Claim
103 words
The computer program product of claim 18 wherein said order property vector O Pi or said order requirement vector O Ri includes at least one bound relation attribute that has the same value for every record in said input record stream R ji , said computer program product further comprising: means, recorded on said recording medium, for directing said data processor to eliminate each said bound relation attribute from said order property vector O Pi ; and means, recorded on said recording medium, for directing said data processor to eliminate each said bound relation attribute from said order requirement vector O Ri .
Claim 24
Dependent Claim
231 words
The computer program product of claim 16 wherein said order property vector O Pi includes a first ordered list of relation attributes (P 1 , . . . , P p ), said order requirement vector O Ri includes a second ordered list of relation attributes (R 1 , . . . , R r ), said order property vector O Pi includes at least one functionally-dependent relation attribute P j that is fully determined by one or more said relational attributes {P k } ordered ahead of said functionally-dependent relation attribute P j in said first ordered list or said order requirement vector O Ri includes at least one functionally-dependent relation attribute R j that is fully determined by one or more said relational attributes {R k } ordered ahead of said functionally-dependent relation attribute R j in said second ordered list, said relation attributes each belong to a class of equivalent attributes including a head attribute, 1≦k<j are positive integers and wherein 0≦p, r are non-negative integers, said computer program product comprising: means, recorded on said recording medium, for directing said data processor to eliminate each said functionally-dependent relation attribute P j from said order property vector O Pi ; and means, recorded on said recording medium, for directing said data processor to eliminate each said functionally-dependent relation attribute R j from said order requirement vector O Ri .
References Cited (Backward Citations)
US5276870A
Cited
US5241648A
Cited
US5369761A
Cited
US5345585A
Cited
US5367675A
Cited
US5301317A
Cited
US5412804A
Cited
US5546576A
Cited
US5546570A
Cited
US5548755A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-04-07 | 2000-10-07 | 2001-04-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-04-07 | 2004-10-07 | 2005-04-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-04-07 | 2008-10-07 | 2009-04-08 | $7700.00 | Window Closed / Lapsed |