US5761653A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for estimating cardinalities for query processing in a relational database management system
Assignee: International Business Machines Corp
•
Filing: 1996-04-03
•
Granted: 1998-06-02
•
Expires: 2016-04-03
Abstract
Abstract The present invention provides a method for estimating cardinalities for query processing in a relational database management system. The present method is suitable for use with a query optimizer for estimating cardinalities for sets of columns or keys resulting from a grouping operation or a duplicate removal operation.
Inventors
- 👤 Bernhard Schiefer
- 👤 Lori G. Strain
- 👤 Weipeng P. Yan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 11:25
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; G06F16/24545; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/954; Y10S707/99931; Y10S707/99932; Y10S707/99933
Claims Analysis
Total Claims: 61
Claim 1
Independent Claim
126 words
A method for estimating cardinalities for a key formed from a grouping of columns in a table for use in a query optimizer for a relational database management system, wherein selectivities and keys associated with columns in the table are provided in a catalog, said method comprising the steps of: (a) determining an equivalence class for each column in said key; (b) for each said equivalence class determining an effective column cardinality for each of said columns belonging to said equivalence class; (c) determining a cardinality for each of said equivalence classes by choosing the minimum effective cardinality for the columns belonging to said equivalence class; and (d) estimating a cardinality value for said key from the product of said cardinalities for all said equivalence classes.
Claim 2
Independent Claim
126 words
A method for estimating cardinalities for a key formed from a grouping of columns in a table for use in a query optimizer for a relational database management system, wherein selectivities and keys associated with columns in the table are provided in a catalog, said method comprising the steps of: (a) determining an equivalence class for each column in said key; (b) for each said equivalence class determining an effective column cardinality for each of said columns belonging to said equivalence class; (c) determining a cardinality for each of said equivalence classes by choosing the minimum effective cardinality for the columns belonging to said equivalence class; and (d) estimating a cardinality value for said key from the product of said cardinalities for all said equivalence classes.
Claim 3
Dependent Claim
47 words
The method for estimating cardinalities for a key as recited in claim 1, wherein said effective column cardinality is determined according to the expression: |C1|*ff.sub.-- 1 where: |C1| is the base column cardinality ff -- 1 is the selectivity of a local predicate on the column C1.
Claim 4
Dependent Claim
44 words
The method for estimating cardinalities for a key as recited in claim 1, wherein step (a) comprises forming a set of keys from said key and other keys selected from said catalog and determining an equivalence class for each column belonging to said set.
Claim 5
Dependent Claim
58 words
The method for estimating cardinalities for a key as recited in claim 1, further including following said step (a) and before said step (b) the steps of: obtaining functional dependencies for columns belonging to said grouping; deleting a column which is functionally determined by another column, and repeating said step until all functionally determined columns have been deleted.
Claim 6
Dependent Claim
21 words
The method for estimating cardinalities for a key as recited in claim 4, wherein said functional dependencies include statistical functional dependencies.
Claim 7
Dependent Claim
74 words
The method for estimating cardinalities for a key as recited in claim 1, wherein said effective column cardinality is determined according to the expression: |C1|*ff.sub.-- 1*(1-(1-ff.sub.-- C).sup.(|T|/|C1|)) where: |T| is the base table cardinality, |C1| is the base column cardinality, ff -- is the selectivity of a local predicate on the column C1, and ff -- C is the product of the selectivities of local predicates on other columns belonging to said equivalence class.
Claim 8
Independent Claim
134 words
A method for estimating cardinalities for a key formed from a grouping of columns in a table for use in a query optimizer for a relational database management system, wherein selectivities and index keys are provided in a catalog, said method comprising the steps of: (a) forming one or more partitions from the columns in said grouping, said partition having a plurality of subsets with each of said subsets comprising a column or an index key; (b) determining an index key cardinality for each of said subsets; (c) obtaining a cardinality for said partition from the product of the index key cardinalities for each subset belonging to said partition; and (d) obtaining a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said partitions.
Claim 9
Independent Claim
134 words
A method for estimating cardinalities for a key formed from a grouping of columns in a table for use in a query optimizer for a relational database management system, wherein selectivities and index keys are provided in a catalog, said method comprising the steps of: (a) forming one or more partitions from the columns in said grouping, said partition having a plurality of subsets with each of said subsets comprising a column or an index key; (b) determining an index key cardinality for each of said subsets; (c) obtaining a cardinality for said partition from the product of the index key cardinalities for each subset belonging to said partition; and (d) obtaining a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said partitions.
Claim 10
Dependent Claim
102 words
The method for estimating cardinalities for a key as recited in claim 7, wherein said index key cardinality in said step (b) is determined according to the expression: |K|*ff.sub.-- K*(1-(1-ff.sub.notC).sup.(|T|/|K|)) where: K is the first n key of an index and n can be 1 to the number of columns in the index, |T| is the base table cardinality, |K| is the first n index key cardinality, ff -- K is the product of selectivities of local predicates on columns in K, and ff notC is the product of selectivities of local predicates on columns in the table but not in K.
Claim 11
Independent Claim
114 words
A method for estimating cardinalities for a key formed from a grouping of columns belonging to a table for use in query optimizer for a relational database management system, wherein selectivities and functional dependencies associated with columns belonging to the table are provided in a catalog, said method comprising the steps of: (a) obtaining functional dependencies for the columns belonging to said key; (b) deleting a column which is functionally determined by another column in said key; (c) repeating step (b) until all functionally determined columns have been deleted; (d) determining an effective column cardinality for each remaining column; and (e) estimating a cardinality for said key from the product of said effective cardinalities.
Claim 12
Independent Claim
114 words
A method for estimating cardinalities for a key formed from a grouping of columns belonging to a table for use in query optimizer for a relational database management system, wherein selectivities and functional dependencies associated with columns belonging to the table are provided in a catalog, said method comprising the steps of: (a) obtaining functional dependencies for the columns belonging to said key; (b) deleting a column which is functionally determined by another column in said key; (c) repeating step (b) until all functionally determined columns have been deleted; (d) determining an effective column cardinality for each remaining column; and (e) estimating a cardinality for said key from the product of said effective cardinalities.
Claim 13
Dependent Claim
69 words
The method for estimating cardinalities as recited in claim 9, wherein said effective column cardinality is determined according to the expression: |C1|*ff.sub.-- 1*(1-(1-ff.sub.-- C).sup.(|T|/|C1|)) where: |T| is the base table cardinality, |C1| is the base column cardinality, ff -- 1 is the selectivity of a local predicate on the column C1, and ff -- C is the product of the selectivities of local predicates on the other remaining columns.
Claim 14
Independent Claim
287 words
A method for estimating cardinalities for a key formed from a grouping of columns in a table for use in a query optimizer for a relational database management system, wherein selectivities and unique keys and index keys are provided in a catalog, said method comprising the steps of: (a) forming a set of keys comprising said key and selected unique keys; (b) determining an equivalence class for each column belonging to said set; (c) for each said equivalence class determining an effective column cardinality for each of said columns belonging to said equivalence class; (d) determining an equivalence class cardinality for each of said equivalence classes by choosing the minimum effective column cardinality for the columns belonging to said equivalence class; (e) forming a combination of columns by choosing a column from each of said equivalence classes; (f) dividing said combination into one or more partitions, each said partition having a plurality of subsets with each said subset comprising a column or a selected index key from said catalog; (g) determining an effective index key cardinality for each of said subsets; (h) obtaining a cardinality for said partition from the product of said effective index key cardinalities for each subset belonging to said partition; (i) determining a cardinality for said combination by choosing the minimum cardinality for said partitions; (j) repeating said steps (e) to (i) for other combinations; (k) obtaining a cardinality value for said set formed in said step (a) by choosing the minimum cardinality of all said combinations; (l) repeating said steps (a) to (d) for other keys selected from said catalog; and (m) obtaining a key cardinality for the grouping of columns by choosing the minimum cardinality value of all said selected keys.
Claim 15
Independent Claim
287 words
A method for estimating cardinalities for a key formed from a grouping of columns in a table for use in a query optimizer for a relational database management system, wherein selectivities and unique keys and index keys are provided in a catalog, said method comprising the steps of: (a) forming a set of keys comprising said key and selected unique keys; (b) determining an equivalence class for each column belonging to said set; (c) for each said equivalence class determining an effective column cardinality for each of said columns belonging to said equivalence class; (d) determining an equivalence class cardinality for each of said equivalence classes by choosing the minimum effective column cardinality for the columns belonging to said equivalence class; (e) forming a combination of columns by choosing a column from each of said equivalence classes; (f) dividing said combination into one or more partitions, each said partition having a plurality of subsets with each said subset comprising a column or a selected index key from said catalog; (g) determining an effective index key cardinality for each of said subsets; (h) obtaining a cardinality for said partition from the product of said effective index key cardinalities for each subset belonging to said partition; (i) determining a cardinality for said combination by choosing the minimum cardinality for said partitions; (j) repeating said steps (e) to (i) for other combinations; (k) obtaining a cardinality value for said set formed in said step (a) by choosing the minimum cardinality of all said combinations; (l) repeating said steps (a) to (d) for other keys selected from said catalog; and (m) obtaining a key cardinality for the grouping of columns by choosing the minimum cardinality value of all said selected keys.
Claim 16
Dependent Claim
72 words
The method for estimating cardinalities as recited in claim 11, wherein said effective column cardinality is determined according to the expression: |C1|*ff.sub.-- 1*(1-(1-ff.sub.-- C).sup.(|T|/|C1|)) where: |T| is the base table cardinality, |C1| is the base column cardinality, ff -- 1 is the selectivity of a local predicate on the column C1, and ff -- C is the product of the selectivities of local predicates on other columns belonging to said equivalence class.
Claim 17
Dependent Claim
101 words
The method for estimating cardinalities for a key as recited in claim 12, wherein said effective index key cardinality is determined according to the expression: |K|*ff.sub.-- K*(1-(1-ff.sub.notC).sup.(|T|/|K|)) where: |T| is the base table cardinality, |K| is the first n key cardinality of an index, where n is 1 to number of columns in the index; and cardinality is the first n key cardinality obtained from the catalog ff -- K is the product of selectivities of local predicates on columns in index key, and ff notC is the product of selectivities of local predicates on columns not belonging in index key.
Claim 18
Dependent Claim
58 words
The method for estimating cardinalities for a key as recited in claim 11, further including following said step (a) and before said step (b) the step of: obtaining functional dependencies for columns belonging to said grouping; deleting a column which is functionally determined by another column, and repeating said step until all functionally determined columns have been deleted.
Claim 19
Dependent Claim
183 words
A relational database management system for use with a computer system wherein queries are entered for retrieving data from tables and wherein said system includes a catalog for providing selectivities and keys associated with columns in the tables, said system comprising: means for processing queries; means for optimizing said queries and generating a plurality of query plans; said means for optimizing having means for estimating cardinalities for a key for said query plans and means for selecting one of said query plans for execution using said estimated cardinalities; said means for estimating cardinalities including, (a) means for determining an equivalence class for columns belonging to said key; (c) means for determining an effective cardinality for each column belonging to said equivalence classes; (d) means for choosing the minimum effective cardinality for the columns belonging to each said equivalence class; (e) means for generating a cardinality value for said key from the product of the minimum effective cardinality for each of said equivalence classes; and (f) said means for selecting being responsive to said key cardinality value for choosing a query plan for execution.
Claim 20
Dependent Claim
183 words
A relational database management system for use with a computer system wherein queries are entered for retrieving data from tables and wherein said system includes a catalog for providing selectivities and keys associated with columns in the tables, said system comprising: means for processing queries; means for optimizing said queries and generating a plurality of query plans; said means for optimizing having means for estimating cardinalities for a key for said query plans and means for selecting one of said query plans for execution using said estimated cardinalities; said means for estimating cardinalities including, (a) means for determining an equivalence class for columns belonging to said key; (c) means for determining an effective cardinality for each column belonging to said equivalence classes; (d) means for choosing the minimum effective cardinality for the columns belonging to each said equivalence class; (e) means for generating a cardinality value for said key from the product of the minimum effective cardinality for each of said equivalence classes; and (f) said means for selecting being responsive to said key cardinality value for choosing a query plan for execution.
Claim 21
Dependent Claim
73 words
The system as recited in claim 15, wherein said means for determining an effective column cardinality includes means for executing the expression: |C1|*ff.sub.-- 1*(1-(1-ff.sub.-- C).sup.(|T|/|C1|)) where: |T| is the base table cardinality, |C1| is the base column cardinality, ff -- 1 is the selectivity of a local predicate on the column C1, and ff -- C is the product of the selectivities of local predicates on other columns belonging to said equivalence class.
Claim 22
Dependent Claim
211 words
A relational database management system for use with a computer system wherein queries are entered for retrieving data from tables and wherein said system includes a catalog for providing selectivities and keys and index keys associated with columns in the tables, said system comprising: means for processing queries; means for optimizing said queries and generating a plurality of query plans; said means for optimizing having means for estimating cardinalities for a key for said query plans and means for selecting one of said query plans for execution using said estimated cardinalities; said means for estimating cardinalities including, (a) means for forming a partition from the columns in said key, said partition having a plurality of subsets with each said subset comprising a column or a selected index key; (b) means for determining an index key cardinality for each of said subsets; (c) means for obtaining a cardinality for said partition from the product of the index key cardinalities for each subset belonging to said partition; (d) means for generating a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said partitions; and (e) said means for selecting being responsive to said key cardinality value for choosing a query plan for execution.
Claim 23
Dependent Claim
211 words
A relational database management system for use with a computer system wherein queries are entered for retrieving data from tables and wherein said system includes a catalog for providing selectivities and keys and index keys associated with columns in the tables, said system comprising: means for processing queries; means for optimizing said queries and generating a plurality of query plans; said means for optimizing having means for estimating cardinalities for a key for said query plans and means for selecting one of said query plans for execution using said estimated cardinalities; said means for estimating cardinalities including, (a) means for forming a partition from the columns in said key, said partition having a plurality of subsets with each said subset comprising a column or a selected index key; (b) means for determining an index key cardinality for each of said subsets; (c) means for obtaining a cardinality for said partition from the product of the index key cardinalities for each subset belonging to said partition; (d) means for generating a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said partitions; and (e) said means for selecting being responsive to said key cardinality value for choosing a query plan for execution.
Claim 24
Dependent Claim
97 words
The system as recited in claim 17, wherein said means for determining an index key cardinality includes means for executing the expression: |K|*ff.sub.-- K*(1-(1-ff.sub.notC).sup.(|T|/|K|)) where: K is the first n key of an index and n can be 1 to the number of columns in the index, |T| is the base table cardinality, |K| is the first n index key cardinality, ff -- K is the product of selectivities of local predicates on columns in index key; and ff notC is the product of selectivities of local predicates on columns in the table but not in K.
Claim 25
Independent Claim
116 words
A method for estimating cardinalities for a key formed from a grouping of columns in a table for use in query optimizer for a relational database management system, wherein information associated with columns in the table are provided in a catalog, said method comprising the steps of: obtaining functional dependencies for columns belonging to said grouping of columns; deleting a column which is functionally determined by another column, and repeating said step until all functionally determined columns have been deleted; determining an effective columns cardinality for each of said remaining columns; and obtaining a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said remaining columns.
Claim 26
Independent Claim
116 words
A method for estimating cardinalities for a key formed from a grouping of columns in a table for use in query optimizer for a relational database management system, wherein information associated with columns in the table are provided in a catalog, said method comprising the steps of: obtaining functional dependencies for columns belonging to said grouping of columns; deleting a column which is functionally determined by another column, and repeating said step until all functionally determined columns have been deleted; determining an effective columns cardinality for each of said remaining columns; and obtaining a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said remaining columns.
Claim 27
Dependent Claim
68 words
The method for estimating cardinalities as recited in claim 19, wherein said effective column cardinality is determined according to the expression: |C1|*ff.sub.-- 1*(1-(1-ff.sub.-- C).sup.(|T|/|C1|)) where: |T| is the base table cardinality, |C1| is the base column cardinality, ff -- 1 is the selectivity of a local predicate on the column C1, and ff -- C is the product of the selectivities of local predicates on the remaining columns.
Claim 28
Dependent Claim
15 words
The method as recited in claim 20, wherein said functional dependencies include statistical functional dependencies.
Claim 29
Dependent Claim
15 words
The method as recited in claim 19, wherein said functional dependencies include statistical functional dependencies.
Claim 30
Independent Claim
82 words
A method for estimating cardinalities for a key formed from a grouping of columns in a table for use in a query optimizer for a relational database management system, wherein selectivities and unique keys associated with columns are provided in a catalog, said method comprising the steps of: forming a set of keys from said key and unique keys selected from said catalog; and obtaining a cardinality for said key by choosing the minimum cardinality value for said keys comprising said set.
Claim 31
Independent Claim
82 words
A method for estimating cardinalities for a key formed from a grouping of columns in a table for use in a query optimizer for a relational database management system, wherein selectivities and unique keys associated with columns are provided in a catalog, said method comprising the steps of: forming a set of keys from said key and unique keys selected from said catalog; and obtaining a cardinality for said key by choosing the minimum cardinality value for said keys comprising said set.
Claim 32
Dependent Claim
135 words
A computer program product for use on a computer wherein queries are entered for retrieving data from a database having a catalog for providing selectivities and keys and index keys, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a grouping of columns; (b) determining an equivalence class for each column in said grouping; (c) for each said equivalence class determining an effective cardinality for each of said columns belonging to said equivalence class; (d) determining a cardinality for each of said equivalence classes by choosing the minimum effective cardinality for the columns belonging to said equivalence class; and (e) estimating a cardinality value for said grouping of columns from the product of said cardinalities for all said equivalence classes.
Claim 33
Dependent Claim
135 words
A computer program product for use on a computer wherein queries are entered for retrieving data from a database having a catalog for providing selectivities and keys and index keys, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a grouping of columns; (b) determining an equivalence class for each column in said grouping; (c) for each said equivalence class determining an effective cardinality for each of said columns belonging to said equivalence class; (d) determining a cardinality for each of said equivalence classes by choosing the minimum effective cardinality for the columns belonging to said equivalence class; and (e) estimating a cardinality value for said grouping of columns from the product of said cardinalities for all said equivalence classes.
Claim 34
Dependent Claim
147 words
A computer program product for use on a computer wherein queries are entered for retrieving data from a database having a catalog for providing selectivities and keys and index keys, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a grouping of columns; (b) forming one or more partitions from columns in said grouping, said partition having a plurality of subsets with each said subset comprising a column or a selected index key; (c) determining an index key cardinality for each of said subsets; (d) obtaining a cardinality for said partition from the product of the effective index key cardinalities for each subset belonging to said partition; and (e) obtaining a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said partitions.
Claim 35
Dependent Claim
147 words
A computer program product for use on a computer wherein queries are entered for retrieving data from a database having a catalog for providing selectivities and keys and index keys, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a grouping of columns; (b) forming one or more partitions from columns in said grouping, said partition having a plurality of subsets with each said subset comprising a column or a selected index key; (c) determining an index key cardinality for each of said subsets; (d) obtaining a cardinality for said partition from the product of the effective index key cardinalities for each subset belonging to said partition; and (e) obtaining a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said partitions.
Claim 36
Dependent Claim
200 words
A database system for retrieving data stored in tables having columns and rows and including a catalog for providing selectivities and keys associated with data stored in said tables, said system comprising: a computer having storage means for storing said data and means for entering queries for retrieving data from said tables; means for processing said queries; said means for processing including means for optimizing said queries and generating a plurality of query plans; said means for optimizing having means for estimating cardinalities for a key for said query plans and means for selecting one of said query plans for execution using said estimated cardinalities; said means for estimating cardinalities including, (a) means for determining an equivalence class for columns belonging to said key; (b) means for determining an effective cardinality for each column belonging to said equivalence classes; (c) means for choosing the minimum effective cardinality for the columns belonging to each said equivalence class; (d) means for generating a cardinality value for said key from the product of the minimum effective cardinality for each of said equivalence classes; and (e) said means for selecting being responsive to said key cardinality value for choosing a query plan for execution.
Claim 37
Dependent Claim
200 words
A database system for retrieving data stored in tables having columns and rows and including a catalog for providing selectivities and keys associated with data stored in said tables, said system comprising: a computer having storage means for storing said data and means for entering queries for retrieving data from said tables; means for processing said queries; said means for processing including means for optimizing said queries and generating a plurality of query plans; said means for optimizing having means for estimating cardinalities for a key for said query plans and means for selecting one of said query plans for execution using said estimated cardinalities; said means for estimating cardinalities including, (a) means for determining an equivalence class for columns belonging to said key; (b) means for determining an effective cardinality for each column belonging to said equivalence classes; (c) means for choosing the minimum effective cardinality for the columns belonging to each said equivalence class; (d) means for generating a cardinality value for said key from the product of the minimum effective cardinality for each of said equivalence classes; and (e) said means for selecting being responsive to said key cardinality value for choosing a query plan for execution.
Claim 38
Dependent Claim
72 words
The system as recited in claim 26, wherein said means for determining an effective cardinality includes means for executing the expression: |C1|*ff.sub.-- 1*(1-(1-ff.sub.-- C).sup.(|T|/|C1|)) where: |T| is the base table cardinality, |C1| is the base column cardinality, ff -- 1 is the selectivity of a local predicate on the column C1, and ff -- C is the product of the selectivities of local predicates on other columns belonging to said equivalence class.
Claim 39
Dependent Claim
33 words
The system as recited in claim 26, further including means for obtaining functional dependencies for columns belonging to said key and means for deleting a column which is functionally determined by another column.
Claim 40
Dependent Claim
225 words
A database system for retrieving data stored in tables having columns and rows and including a catalog for providing selectivities and keys and index keys associated with said data, said system comprising: a computer having storage means for storing said data and means for entering queries for retrieving data from said tables; means for processing said queries; said means for processing including means for optimizing said queries and generating a plurality of query plans; said means for optimizing having means for estimating cardinalities for a key for said query plans and means for selecting one of said query plans for execution using said estimated cardinalities; said means for estimating cardinalities including, (a) means for forming a partition from the columns in said key, said partition having a plurality of subsets with each said subset comprising a column or a selected index key; (b) means for determining an index key cardinality for each of said subsets; (c) means for obtaining a cardinality for said partition from the product of the index key cardinalities for each subset belonging to said partition; (d) means for generating a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said partitions; and (e) said means for selecting being responsive to said key cardinality value for choosing a query plan for execution.
Claim 41
Dependent Claim
225 words
A database system for retrieving data stored in tables having columns and rows and including a catalog for providing selectivities and keys and index keys associated with said data, said system comprising: a computer having storage means for storing said data and means for entering queries for retrieving data from said tables; means for processing said queries; said means for processing including means for optimizing said queries and generating a plurality of query plans; said means for optimizing having means for estimating cardinalities for a key for said query plans and means for selecting one of said query plans for execution using said estimated cardinalities; said means for estimating cardinalities including, (a) means for forming a partition from the columns in said key, said partition having a plurality of subsets with each said subset comprising a column or a selected index key; (b) means for determining an index key cardinality for each of said subsets; (c) means for obtaining a cardinality for said partition from the product of the index key cardinalities for each subset belonging to said partition; (d) means for generating a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said partitions; and (e) said means for selecting being responsive to said key cardinality value for choosing a query plan for execution.
Claim 42
Dependent Claim
97 words
The system as recited in claim 29, wherein said means for determining an index key cardinality includes means for executing the expression: |K|*ff.sub.-- K*(1-(1-ff.sub.notC).sup.(|T|/|K|)) where: K is the first n key of an index and n can be 1 to the number of columns in the index, |T| is the base table cardinality, |K| is the first n index key cardinality, ff -- K is the product of selectivities of local predicates on columns in index key, and ff notC is the product of selectivities of local predicates on columns in the table but not in K.
Claim 43
Dependent Claim
33 words
The system as recited in claim 29, further including means for obtaining functional dependencies for columns belonging to said key and means for deleting a column which is functionally determined by another column.
Claim 44
Dependent Claim
117 words
A computer program product for use on a computer wherein queries are entered for retrieving data from a database having a catalog for providing selectivities and keys, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a grouping of columns; (b) obtaining functional dependencies for the columns belonging to said key; (c) deleting a column which is functionally determined by another column in said key; (d) repeating step (c) until all functionally determined columns have been deleted; (e) determining an effective column cardinality for each remaining column; and (e) estimating a cardinality for said key from the product of said effective cardinalities.
Claim 45
Dependent Claim
117 words
A computer program product for use on a computer wherein queries are entered for retrieving data from a database having a catalog for providing selectivities and keys, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a grouping of columns; (b) obtaining functional dependencies for the columns belonging to said key; (c) deleting a column which is functionally determined by another column in said key; (d) repeating step (c) until all functionally determined columns have been deleted; (e) determining an effective column cardinality for each remaining column; and (e) estimating a cardinality for said key from the product of said effective cardinalities.
Claim 46
Dependent Claim
132 words
A computer program product for use on a computer wherein queries are entered for retrieving data from a database having a catalog for providing information associated with columns in a table, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a grouping of columns; (b) obtaining functional dependencies for columns belonging to said grouping of columns; (c) deleting a column which is functionally determined by another column, and repeating said step until all functionally determined items have been deleted; (d) determining an effective columns cardinality for each of said remaining columns; and (e) obtaining a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said remaining columns.
Claim 47
Dependent Claim
132 words
A computer program product for use on a computer wherein queries are entered for retrieving data from a database having a catalog for providing information associated with columns in a table, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a grouping of columns; (b) obtaining functional dependencies for columns belonging to said grouping of columns; (c) deleting a column which is functionally determined by another column, and repeating said step until all functionally determined items have been deleted; (d) determining an effective columns cardinality for each of said remaining columns; and (e) obtaining a cardinality value for the grouping of columns by choosing the minimum cardinality from the cardinalities determined for each of said remaining columns.
Claim 48
Dependent Claim
85 words
A computer program product for use on a computer wherein queries are entered for retrieving data from a database having a catalog for providing selectivities and keys, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a set of keys from said key and unique keys selected from said catalog; and (b) obtaining a cardinality for said key by choosing the minimum cardinality value for said key comprising said set.
Claim 49
Dependent Claim
85 words
A computer program product for use on a computer wherein queries are entered for retrieving data from a database having a catalog for providing selectivities and keys, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a set of keys from said key and unique keys selected from said catalog; and (b) obtaining a cardinality for said key by choosing the minimum cardinality value for said key comprising said set.
Claim 50
Dependent Claim
153 words
A memory for storing data for access by a program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a grouping of data objects as columns; a data object as an equivalence class for each column in said grouping; a data object representing an equivalence class determining an effective cardinality for each of said columns belonging to said equivalence class; a data object representing a cardinality for each set of equivalence classes by being chosen as the minimum effective cardinality for the columns belong to said equivalence class; and a data object representative of a cardinality value for said grouping of columns from the product of said cardinalities for said equivalence classes.
Claim 51
Dependent Claim
153 words
A memory for storing data for access by a program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a grouping of data objects as columns; a data object as an equivalence class for each column in said grouping; a data object representing an equivalence class determining an effective cardinality for each of said columns belonging to said equivalence class; a data object representing a cardinality for each set of equivalence classes by being chosen as the minimum effective cardinality for the columns belong to said equivalence class; and a data object representative of a cardinality value for said grouping of columns from the product of said cardinalities for said equivalence classes.
Claim 52
Dependent Claim
168 words
A memory for storing data for access by a program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a data object representing a grouping of columns; a data object representing one or more partitions from columns in said grouping, said partitions having a plurality of subsets with each set subset comprising a column or a selected index key; a data object representing an index key cardinality for each of said subsets; a data object representing a cardinality for said partition from the product of the effective index key cardinalities for each subset belonging to said partition; and a data object representative of a cardinality value for a grouping of columns being chosen to represent the minimum cardinality from the cardinalities determined for each of said partitions.
Claim 53
Dependent Claim
168 words
A memory for storing data for access by a program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a data object representing a grouping of columns; a data object representing one or more partitions from columns in said grouping, said partitions having a plurality of subsets with each set subset comprising a column or a selected index key; a data object representing an index key cardinality for each of said subsets; a data object representing a cardinality for said partition from the product of the effective index key cardinalities for each subset belonging to said partition; and a data object representative of a cardinality value for a grouping of columns being chosen to represent the minimum cardinality from the cardinalities determined for each of said partitions.
Claim 54
Dependent Claim
144 words
A memory for data processing or access by a program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a data object for functional dependencies for a column belonging to a key formed from a grouping of columns belonging to a table; a column deletion data object which is functionally determined by another column in said key; a data object for repeating column deletion until all functionally determined columns are deleted; a data object representative of an effective column cardinality for each remaining column; and a data object representing a cardinality for said key being chosen from a minimum of said effective cardinalities.
Claim 55
Dependent Claim
144 words
A memory for data processing or access by a program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a data object for functional dependencies for a column belonging to a key formed from a grouping of columns belonging to a table; a column deletion data object which is functionally determined by another column in said key; a data object for repeating column deletion until all functionally determined columns are deleted; a data object representative of an effective column cardinality for each remaining column; and a data object representing a cardinality for said key being chosen from a minimum of said effective cardinalities.
Claim 56
Dependent Claim
203 words
A memory for storing data for access by a program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a data object for a key formed from a grouping of columns in a table; a data object functionally dependent on the columns belonging to said grouping of columns; a data object obtained by deleting a column which is functionally determined by another column, such deletion being effected until all functionally determined columns have been deleted; a data object representing an effective columns cardinality for each of the remaining columns; and a data object representing a cardinality value for the grouping of columns, such object being chosen by the minimum cardinality from the cardinalities determined for each of the remaining columns.
Claim 57
Dependent Claim
203 words
A memory for storing data for access by a program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a data object for a key formed from a grouping of columns in a table; a data object functionally dependent on the columns belonging to said grouping of columns; a data object obtained by deleting a column which is functionally determined by another column, such deletion being effected until all functionally determined columns have been deleted; a data object representing an effective columns cardinality for each of the remaining columns; and a data object representing a cardinality value for the grouping of columns, such object being chosen by the minimum cardinality from the cardinalities determined for each of the remaining columns.
Claim 58
Dependent Claim
137 words
A memory for storing data for access by a program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a data object representing a key from a grouping of columns in a table, the columns being provided in a catalog, and the grouping of columns as being used for estimating cardinalities for a key; a data object representing a set of keys from said key and unique keys selected from the catalog; and a data object representing a cardinality for said key having been chosen by the minimum cardinality value for said keys comprising said set.
Claim 59
Dependent Claim
137 words
A memory for storing data for access by a program being executed on a data processing system, comprising: a data structure stored in said memory, said data structure including information resident in a database used by said program and including; a plurality of data objects stored in said memory, each of said data objects containing different information from said database; a data object representing a key from a grouping of columns in a table, the columns being provided in a catalog, and the grouping of columns as being used for estimating cardinalities for a key; a data object representing a set of keys from said key and unique keys selected from the catalog; and a data object representing a cardinality for said key having been chosen by the minimum cardinality value for said keys comprising said set.
Claim 60
Dependent Claim
95 words
A computer program product for use on a computer wherein queries involving a grouping operation that forms a grouping key are entered for retrieving data from a database having a catalog having information about keys and for providing selectivities, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a set of keys from unique keys selected from said catalog; and (b) obtaining a cardinality for said grouping key by choosing the minimum cardinality value among the set of unique keys.
Claim 61
Dependent Claim
95 words
A computer program product for use on a computer wherein queries involving a grouping operation that forms a grouping key are entered for retrieving data from a database having a catalog having information about keys and for providing selectivities, said computer program product comprising: a recording medium; means recorded on said medium for instructing said computer to perform the steps of, (a) forming a set of keys from unique keys selected from said catalog; and (b) obtaining a cardinality for said grouping key by choosing the minimum cardinality value among the set of unique keys.
References Cited (Backward Citations)
US4769772A
Cited
US5325525A
Cited
US5345585A
Cited
US5367675A
Cited
US5469568A
Cited
US5544355A
Cited
US5598559A
Cited
US5615361A
Cited
US5608904A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-06-01 | 2001-12-01 | 2002-06-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-06-01 | 2005-12-01 | 2006-06-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-06-01 | 2009-12-01 | 2010-06-02 | $7700.00 | Window Closed / Lapsed |