US5832475A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Database system and method employing data cube operator for group-by operations
Assignee: International Business Machines Corp
•
Filing: 1996-03-29
•
Granted: 1998-11-03
•
Expires: 2016-03-29
Abstract
Abstract Disclosed is a system and method for performing database queries including GROUP-BY operations, in which aggregate values for attributes are desired for distinct, partitioned subsets of tuples satisfying a query. A special case of the aggregation problem is addressed, employing a structure, called the data cube operator, which provides information useful for expediting execution of GROUP-BY operations in queries. Algorithms are provided for constructing the data cube by efficiently computing a collection of GROUP-BYs on the attributes of the relation. Decision support systems often require computation of multiple GROUP-BY operations on a given set of attributes, the GROUP-BYs being related in the sense that their attributes are subsets or supersets of each other. The invention extends hash-based and sort-based grouping methods with optimizations, including combining common operations across multiple GROUP-BYs and using pre-computed GROUP-BYs for computing other GROUP-BYs. An extension of the cube algorithms handles any given collection of aggregates.
Inventors
- 👤 Rakesh Agrawal
- 👤 Ashish Gupta
- 👤 Sunita Sarawagi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 04:59
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; G06F16/24554; G06F16/24556; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99937
Claims Analysis
Total Claims: 72
Claim 1
Independent Claim
116 words
A method, for execution by a database system, for performing GROUP-BY operations on a dataset of attributes, the method comprising the steps of: generating an operator which represents (i) possible GROUP-BY operations on the dataset of attributes and (ii) hierarchies of the possible GROUP-BY operations, using a predetermined optimization technique; computing a first GROUP-BY operation on a first subset of the dataset of attributes using the operator; and computing a second GROUP-BY operation on a second subset of the dataset of attributes using the operator, the second subset being a proper subset of the first subset, based on the results of the step of computing a first GROUP-BY operation on the first subset of the attributes.
Claim 2
Independent Claim
116 words
A method, for execution by a database system, for performing GROUP-BY operations on a dataset of attributes, the method comprising the steps of: generating an operator which represents (i) possible GROUP-BY operations on the dataset of attributes and (ii) hierarchies of the possible GROUP-BY operations, using a predetermined optimization technique; computing a first GROUP-BY operation on a first subset of the dataset of attributes using the operator; and computing a second GROUP-BY operation on a second subset of the dataset of attributes using the operator, the second subset being a proper subset of the first subset, based on the results of the step of computing a first GROUP-BY operation on the first subset of the attributes.
Claim 3
Dependent Claim
20 words
A method as recited in claim 1, wherein the step of generating an operator includes generating a data cube operator.
Claim 4
Dependent Claim
100 words
A method as recited in claim 1, wherein: the method further includes using the operator to identify, for a given one of possible GROUP-BY operations for the attributes of the relation, parent ones of the possible GROUP-BY operations from which the given GROUP-BY operation may be computed; and the step of computing a second GROUP-BY operation includes computing the second GROUP-BY operation based on the results of one of the parent ones of the possible GROUP-BY operations, identified for the second GROUP-BY operation in the step of identifying, which is smallest of the parent ones of the possible GROUP-BY operations.
Claim 5
Dependent Claim
60 words
A method as recited in claim 1, wherein the step of generating an operator includes using an optimization technique of: computing a first GROUP-BY to produce results thereof; storing the results of the first GROUP-BY in cache memory; and computing another GROUP-BY based on the results of the first GROUP-BY operation stored in cache memory by the step of storing.
Claim 6
Dependent Claim
59 words
A method as recited in claim 1, further comprising using an optimization technique of: computing a first GROUP-BY to produce results thereof; storing the results of the first GROUP-BY in disk storage; scanning the results of the first GROUP-BY in disk storage; and computing a plurality of other GROUP-BYs concurrently based on the scanned results of the first GROUP-BY.
Claim 7
Dependent Claim
22 words
A method as recited in claim 1, wherein the steps of computing first and second GROUP-BYs are performed using a sort-based method.
Claim 8
Dependent Claim
19 words
A method as recited in claim 6, further comprising the step of computing multiple GROUP-BYs using a single sort.
Claim 9
Dependent Claim
26 words
A method as recited in claim 7, wherein the step of computing multiple GROUP-BYs using a single sort includes computing the GROUP-BYs in a pipelined fashion.
Claim 10
Dependent Claim
110 words
A method as recited in claim 7, wherein the step of computing multiple GROUP-BYs using a single sort includes the steps of: identifying respective levels within the operator generated by the step of generating an operator, the levels having a hierarchy based on the number of attributes in each GROUP-BY in the levels; and determining, for each level having a successively smaller number of attributes per GROUP-BY, a lowest-cost way of computing the GROUP-BYs of that level, based on results of computations of GROUP-BYs for a previous level whose GROUP-BYs have one greater number of attributes, the step of determining being made based on a reduction to weighted bipartite patching.
Claim 11
Dependent Claim
22 words
A method as recited in claim 1, wherein the steps of computing first and second GROUP-BYs are performed using a hash-based method.
Claim 12
Dependent Claim
38 words
A method as recited in claim 10, further comprising the steps of: producing hash tables for multiple GROUP-BYs; and storing the hash tables in cache memory; and computing successive GROUP-BYs from the hash tables stored in cache memory.
Claim 13
Dependent Claim
45 words
A method as recited in claim 11, wherein the step of producing hash tables includes one of (i) employing a multidimensional array, and (ii) concatenating a predetermined number of bits for each attribute, based on how sparse is a distribution of data for the attributes.
Claim 14
Dependent Claim
33 words
A method as recited in claim 10, further comprising the steps of: partitioning based on an attribute; and computing multiple GROUP-BYs which include the attribute upon which the step of partitioning was based.
Claim 15
Dependent Claim
20 words
A method as recited in claim 13, wherein the step of partitioning is performed on a portion of the dataset.
Claim 16
Dependent Claim
44 words
A method as recited in claim 1, further comprising the steps of: estimating a size of a GROUP-BY; and selecting, based on the estimated size, whether the step of computing the GROUP-BY is to be done using a sort-based method or a hash-based method.
Claim 17
Dependent Claim
61 words
A method as recited in claim 1, further comprising the steps of: estimating a size of a GROUP-BY; and selecting, based on the estimated size, whether the step of computing the GROUP-BY is to be done using a hash-based method including producing hash tables by (I) employing a multidimensional array, and (ii) concatenating a predetermined number of bits for each attribute.
Claim 18
Dependent Claim
88 words
A method as recited in claim 1, further comprising the steps of: identifying respective levels within the operator generated by the step of generating an operator, the levels having a hierarchy based on the number of attributes in each GROUP-BY in the levels; and determining, for each level having a successively smaller number of attributes per GROUP-BY, a lowest-cost way of computing the GROUP-BYs of that level, based on results of computations of GROUP-BYs for a previous level whose GROUP-BYs have more than one greater number of attributes.
Claim 19
Dependent Claim
48 words
A method as recited in claim 1, wherein: the method is performed responsive to a received query which requests a subset of all possible GROUP-BY operations; and the step of generating an operator includes generating GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset.
Claim 20
Dependent Claim
50 words
A method as recited in claim 18, wherein the step of generating GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset includes: generating an intermediate GROUP-BY operation not included in the requested subset; and generating one of the requested GROUP-BY operations from the intermediate GROUP-BY operation.
Claim 21
Dependent Claim
32 words
A method as recited in claim 18, wherein the step of generating GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset includes generating a minimal cost Steiner tree.
Claim 22
Dependent Claim
31 words
A method as recited in claim 18, wherein the step of generating GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset is performed using a sort-based method.
Claim 23
Dependent Claim
31 words
A method as recited in claim 18, wherein the step of generating GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset is performed using a hash-based method.
Claim 24
Dependent Claim
118 words
A method as recited in claim 1, wherein: one of the attributes of the dataset has a hierarchy of levels defined on it; the method is performed responsive to a received query which requests GROUP-BY operations in which different designated levels of the hierarchy for the attribute are requested; and the step of generating an operator includes using an optimization technique of identifying, for a given one of the GROUP-BY operations including a higher level of the hierarchy for the attribute having a hierarchy of levels, a parent one of the GROUP-BY operations which includes a lower level of the hierarchy for the attribute having a hierarchy of levels, from which the given GROUP-BY operation may be computed.
Claim 25
Dependent Claim
114 words
A database system, for performing GROUP-BY operations on a dataset of attributes, the system comprising: means for generating an operator which represents (i) possible GROUP-BY operations on the dataset of attributes and (ii) hierarchies of the possible GROUP-BY operations, using a predetermined optimization technique; means for computing a first GROUP-BY operation on a first subset of the dataset of attributes using the operator; and means for computing a second GROUP-BY operation on a second subset of the dataset of attributes using the operator, the second subset being a proper subset of the first subset, based on the results of the means for computing a first GROUP-BY operation on the first subset of the attributes.
Claim 26
Dependent Claim
114 words
A database system, for performing GROUP-BY operations on a dataset of attributes, the system comprising: means for generating an operator which represents (i) possible GROUP-BY operations on the dataset of attributes and (ii) hierarchies of the possible GROUP-BY operations, using a predetermined optimization technique; means for computing a first GROUP-BY operation on a first subset of the dataset of attributes using the operator; and means for computing a second GROUP-BY operation on a second subset of the dataset of attributes using the operator, the second subset being a proper subset of the first subset, based on the results of the means for computing a first GROUP-BY operation on the first subset of the attributes.
Claim 27
Dependent Claim
22 words
A system as recited in claim 24, wherein the means for generating an operator includes means for generating a data cube operator.
Claim 28
Dependent Claim
104 words
A system as recited in claim 24, wherein: the system further includes means for using the operator to identify, for a given one of possible GROUP-BY operations for the attributes of the relation, parent ones of the possible GROUP-BY operations from which the given GROUP-BY operation may be computed; and the means for computing a second GROUP-BY operation includes means for computing the second GROUP-BY operation based on the results of one of the parent ones of the possible GROUP-BY operations, identified for the second GROUP-BY operation by the means for identifying, which is smallest of the parent ones of the possible GROUP-BY operations.
Claim 29
Dependent Claim
62 words
A system as recited in claim 24, wherein the means for generating an operator includes means for using an optimization technique of: computing a first GROUP-BY to produce results thereof; storing the results of the first GROUP-BY in cache memory; and computing another GROUP-BY based on the results of the first GROUP-BY operation stored in cache memory by the step of storing.
Claim 30
Dependent Claim
61 words
A system as recited in claim 24, further comprising means for using an optimization technique of: computing a first GROUP-BY to produce results thereof; storing the results of the first GROUP-BY in disk storage; scanning the results of the first GROUP-BY in disk storage; and computing a plurality of other GROUP-BYs concurrently based on the scanned results of the first GROUP-BY.
Claim 31
Dependent Claim
23 words
A system as recited in claim 24, wherein the means for computing first and second GROUP-BYs include means for using a sort-based method.
Claim 32
Dependent Claim
19 words
A system as recited in claim 29, further comprising the means for computing multiple GROUP-BYs using a single sort.
Claim 33
Dependent Claim
29 words
A system as recited in claim 30, wherein the means for computing multiple GROUP-BYs using a single sort includes means for computing the GROUP-BY s in a pipelined fashion.
Claim 34
Dependent Claim
111 words
A system as recited in claim 30, wherein the means for computing multiple GROUP-BYs using a single sort includes: means for identifying respective levels within the operator generated by the means for generating an operator, the levels having a hierarchy based on the number of attributes in each GROUP-BY in the levels; and means for determining, for each level having a successively smaller number of attributes per GROUP-BY, a lowest-cost way of computing the GROUP-BYs of that level, based on results of computations of GROUP-BYs for a previous level whose GROUP-BYs have one greater number of attributes, the means for determining being made based on a reduction to weighted bipartite patching.
Claim 35
Dependent Claim
23 words
A system as recited in claim 24, wherein the means for computing first and second GROUP-BYs include means for using a hash-based method.
Claim 36
Dependent Claim
41 words
A system as recited in claim 33, further comprising: means for producing hash tables for multiple GROUP-BYs; and means for storing the hash tables in cache memory; and means for computing successive GROUP-BYs from the hash tables stored in cache memory.
Claim 37
Dependent Claim
47 words
A system as recited in claim 34, wherein the means for producing hash tables includes means for one of (i) employing a multidimensional array, and (ii) concatenating a predetermined number of bits for each attribute, based on how sparse is a distribution of data for the attributes.
Claim 38
Dependent Claim
35 words
A system as recited in claim 33, further comprising: means for partitioning based on an attribute; and means for computing multiple GROUP-BYs which include the attribute upon which the means for of partitioning was based.
Claim 39
Dependent Claim
19 words
A system as recited in claim 36, wherein the means for partitioning operates on a portion of the dataset.
Claim 40
Dependent Claim
44 words
A system as recited in claim 24, further comprising: means for estimating a size of a GROUP-BY; and means for selecting, based on the estimated size, whether the means for computing the GROUP-BY is to operate using a sort-based method or a hash-based method.
Claim 41
Dependent Claim
61 words
A system as recited in claim 24, further comprising: means for estimating a size of a GROUP-BY; and means for selecting, based on the estimated size, whether the means for computing the GROUP-BY is to operate using a hash-based method including producing hash tables by (I) employing a multidimensional array, and (ii) concatenating a predetermined number of bits for each attribute.
Claim 42
Dependent Claim
89 words
A system as recited in claim 24, further comprising: means for identifying respective levels within the operator generated by the means for generating an operator, the levels having a hierarchy based on the number of attributes in each GROUP-BY in the levels; and means for determining, for each level having a successively smaller number of attributes per GROUP-BY, a lowest-cost way of computing the GROUP-BYs of that level, based on results of computations of GROUP-BYs for a previous level whose GROUP-BYs have more than one greater number of attributes.
Claim 43
Dependent Claim
50 words
A system as recited in claim 24, wherein: the system is operative responsive to a received query which requests a subset of all possible GROUP-BY operations; and the means for generating an operator includes means for generating GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset.
Claim 44
Dependent Claim
54 words
A system as recited in claim 41, wherein the means for generating GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset includes: means for generating an intermediate GROUP-BY operation not included in the requested subset; and means for generating one of the requested GROUP-BY operations from the intermediate GROUP-BY operation.
Claim 45
Dependent Claim
32 words
A system as recited in claim 41, wherein the means for generating GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset includes generating a minimal cost Steiner tree.
Claim 46
Dependent Claim
31 words
A system as recited in claim 41, wherein the means for generating GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset is performed using a sort-based method.
Claim 47
Dependent Claim
31 words
A system as recited in claim 41, wherein the means for generating GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset is performed using a hash-based method.
Claim 48
Dependent Claim
120 words
A system as recited in claim 24, wherein: one of the attributes of the dataset has a hierarchy of levels defined on it; the system is operative responsive to a received query which requests GROUP-BY operations in which different designated levels of the hierarchy for the attribute are requested; and the means for generating an operator includes means for using an optimization technique of identifying, for a given one of the GROUP-BY operations including a higher level of the hierarchy for the attribute having a hierarchy of levels, a parent one of the GROUP-BY operations which includes a lower level of the hierarchy for the attribute having a hierarchy of levels, from which the given GROUP-BY operation may be computed.
Claim 49
Dependent Claim
171 words
A computer program product, for use with a database and processing system, for directing the system to perform GROUP-BY operations on a dataset of attributes, the computer program product comprising: a computer readable medium; means, provided on the computer-readable medium, for directing the database and processing system to generate an operator which represents (i) possible GROUP-BY operations on the dataset of attributes and (ii) hierarchies of the possible GROUP-BY operations, using a predetermined optimization technique; means, provided on the computer-readable medium, for directing the database and processing system to compute a first GROUP-BY operation on a first subset of the dataset of attributes using the operator; and means, provided on the computer-readable medium, for directing the database and processing system to compute a second GROUP-BY operation on a second subset of the dataset of attributes using the operator, the second subset being a proper subset of the first subset, based on the results of the means for directing to compute a first GROUP-BY operation on the first subset of the attributes.
Claim 50
Dependent Claim
171 words
A computer program product, for use with a database and processing system, for directing the system to perform GROUP-BY operations on a dataset of attributes, the computer program product comprising: a computer readable medium; means, provided on the computer-readable medium, for directing the database and processing system to generate an operator which represents (i) possible GROUP-BY operations on the dataset of attributes and (ii) hierarchies of the possible GROUP-BY operations, using a predetermined optimization technique; means, provided on the computer-readable medium, for directing the database and processing system to compute a first GROUP-BY operation on a first subset of the dataset of attributes using the operator; and means, provided on the computer-readable medium, for directing the database and processing system to compute a second GROUP-BY operation on a second subset of the dataset of attributes using the operator, the second subset being a proper subset of the first subset, based on the results of the means for directing to compute a first GROUP-BY operation on the first subset of the attributes.
Claim 51
Dependent Claim
38 words
A computer program product as recited in claim 47, wherein the means for directing to generate an operator includes means, provided on the computer-readable medium, for directing the database and processing system to generate a data cube operator.
Claim 52
Dependent Claim
135 words
A computer program product as recited in claim 47, wherein: the method CPP further includes means, provided on the computer-readable medium, for directing the database and processing system to use the operator to identify, for a given one of possible GROUP-BY operations for the attributes of the relation, parent ones of the possible GROUP-BY operations from which the given GROUP-BY operation may be computed; and the means for directing to compute a second GROUP-BY operation includes means, provided on the computer-readable medium, for directing the database and processing system to computing the second GROUP-BY operation based on the results of one of the parent ones of the possible GROUP-BY operations, identified for the second GROUP-BY operation by the means for directing to identify, which is smallest of the parent ones of the possible GROUP-BY operations.
Claim 53
Dependent Claim
78 words
A computer program product as recited in claim 47, wherein the means for directing to generate an operator includes means, provided on the computer-readable medium, for directing the database and processing system to use an optimization technique of: computing a first GROUP-BY to produce results thereof; storing the results of the first GROUP-BY in cache memory; and computing another GROUP-BY based on the results of the first GROUP-BY operation stored in cache memory by the step of storing.
Claim 54
Dependent Claim
75 words
A computer program product as recited in claim 47, further comprising means, provided on the computer-readable medium, for directing the database and processing system to use an optimization technique of: computing a first GROUP-BY to produce results thereof; storing the results of the first GROUP-BY in disk storage; scanning the results of the first GROUP-BY in disk storage; and computing a plurality of other GROUP-BYs concurrently based on the scanned results of the first GROUP-BY.
Claim 55
Dependent Claim
39 words
A computer program product as recited in claim 47, wherein the means for directing to compute first and second GROUP-BYs include means, provided on the computer-readable medium, for directing the database and processing system to use a sort-based method.
Claim 56
Dependent Claim
33 words
A computer program product as recited in claim 52, further comprising the means, provided on the computer-readable medium, for directing the database and processing system to compute multiple GROUP-BYs using a single sort.
Claim 57
Dependent Claim
45 words
A computer program product as recited in claim 53, wherein the means for directing to compute multiple GROUP-BYs using a single sort includes means, provided on the computer-readable medium, for directing the database and processing system to compute the GROUP-BY s in a pipelined fashion.
Claim 58
Dependent Claim
143 words
A computer program product as recited in claim 53, wherein the means for directing to compute multiple GROUP-BYs using a single sort includes: means, provided on the computer-readable medium, for directing the database and processing system to identify respective levels within the operator generated by the means for directing to generate an operator, the levels having a hierarchy based on the number of attributes in each GROUP-BY in the levels; and means, provided on the computer-readable medium, for directing the database and processing system to determine, for each level having a successively smaller number of attributes per GROUP-BY, a lowest-cost way of computing the GROUP-BYs of that level, based on results of computations of GROUP-BYs for a previous level whose GROUP-BYs have one greater number of attributes, the means for directing to determine being made based on a reduction to weighted bipartite patching.
Claim 59
Dependent Claim
39 words
A computer program product as recited in claim 47, wherein the means for directing to compute first and second GROUP-BYs include means, provided on the computer-readable medium, for directing the database and processing system to use a hash-based method.
Claim 60
Dependent Claim
79 words
A computer program product as recited in claim 56, further comprising: means, provided on the computer-readable medium, for directing the database and processing system to producing hash tables for multiple GROUP-BYs; and means, provided on the computer-readable medium, for directing the database and processing system to storing the hash tables in cache memory; and means, provided on the computer-readable medium, for directing the database and processing system to computing successive GROUP-BYs from the hash tables stored in cache memory.
Claim 61
Dependent Claim
64 words
A computer program product as recited in claim 57, wherein the means for directing to produce hash tables includes means, provided on the computer-readable medium, for directing the database and processing system to perform one of (I) employ a multidimensional array, and (ii) concatenate a predetermined number of bits for each attribute, based on how sparse is a distribution of data for the attributes.
Claim 62
Dependent Claim
60 words
A computer program product as recited in claim 56, further comprising: means, provided on the computer-readable medium, for directing the database and processing system to partition based on an attribute; and means, provided on the computer-readable medium, for directing the database and processing system to compute multiple GROUP-BYs which include the attribute upon which the step of partitioning was based.
Claim 63
Dependent Claim
23 words
A computer program product as recited in claim 59, wherein the means for directing to partition operates on a portion of the dataset.
Claim 64
Dependent Claim
74 words
A computer program product as recited in claim 47, further comprising the steps of: means, provided on the computer-readable medium, for directing the database and processing system to estimate a size of a GROUP-BY; and means, provided on the computer-readable medium, for directing the database and processing system to select, based on the estimated size, whether the means for directing to compute the GROUP-BY is operable using a sort-based method or a hash-based method.
Claim 65
Dependent Claim
88 words
A computer program product as recited in claim 47, further comprising: means, provided on the computer-readable medium, for directing the database and processing system to estimate a size of a GROUP-BY; and means, provided on the computer-readable medium, for directing the database and processing system to select, based on the estimated size, whether the means for directing to compute the GROUP-BY is operable using a hash-based method including producing hash tables by (I) employing a multidimensional array, and (ii) concatenating a predetermined number of bits for each attribute.
Claim 66
Dependent Claim
117 words
A computer program product as recited in claim 47, further comprising: means, provided on the computer-readable medium, for directing the database and processing system to identify respective levels within the operator generated by the means for directing to generate an operator, the levels having a hierarchy based on the number of attributes in each GROUP-BY in the levels; and means, provided on the computer-readable medium, for directing the database and processing system to determine, for each level having a successively smaller number of attributes per GROUP-BY, a lowest-cost way of computing the GROUP-BYs of that level, based on results of computations of GROUP-BYs for a previous level whose GROUP-BYs have more than one greater number of attributes.
Claim 67
Dependent Claim
68 words
A computer program product as recited in claim 47, wherein: the computer program product is operable responsive to a received query which requests a subset of all possible GROUP-BY operations; and the means for directing to generating an operator includes means, provided on the computer-readable medium, for directing the database and processing system to generate GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset.
Claim 68
Dependent Claim
82 words
A computer program product as recited in claim 64, wherein the means for directing to generate GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset includes: means, provided on the computer-readable medium, for directing the database and processing system to generate an intermediate GROUP-BY operation not included in the requested subset; and means, provided on the computer-readable medium, for directing the database and processing system to generate one of the requested GROUP-BY operations from the intermediate GROUP-BY operation.
Claim 69
Dependent Claim
36 words
A computer program product as recited in claim 64, wherein the means for directing to generate GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset includes generating a minimal cost Steiner tree.
Claim 70
Dependent Claim
35 words
A computer program product as recited in claim 64, wherein the means for directing to generate GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset is performed using a sort-based method.
Claim 71
Dependent Claim
35 words
A computer program product as recited in claim 64, wherein the means for directing to generate GROUP-BY operations based on whether the GROUP-BY operations are within the requested subset is performed using a hash-based method.
Claim 72
Dependent Claim
138 words
A computer program product as recited in claim 47, wherein: one of the attributes of the dataset has a hierarchy of levels defined on it; the computer program product is operative responsive to a received query which requests GROUP-BY operations in which different designated levels of the hierarchy for the attribute are requested; and the means for directing to generate an operator includes means, provided on the computer-readable medium, for directing the database and processing system to use an optimization technique of identifying, for a given one of the GROUP-BY operations including a higher level of the hierarchy for the attribute having a hierarchy of levels, a parent one of the GROUP-BY operations which includes a lower level of the hierarchy for the attribute having a hierarchy of levels, from which the given GROUP-BY operation may be computed.
References Cited (Backward Citations)
US5280547A
Cited
US5412804A
Cited
US5542073A
Cited
US5613109A
Cited
US5497486A
Cited
US5717915A
Cited
US5537589A
Cited
US5598559A
Cited
US5642502A
Cited
US5548755A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-02 | 2002-05-04 | 2002-11-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-02 | 2006-05-04 | 2006-11-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-02 | 2010-05-04 | 2010-11-03 | $7700.00 | Window Closed / Lapsed |