Method and apparatus for populating sparse matrix entries from corresponding data

• US 6,212,515 B1
• Filed: 11/03/1998
• Issued: 04/03/2001
• Est. Priority Date: 11/03/1998
• Status: Expired due to Term

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Platinum Technology Incorporated (Broadcom, Inc.)
• Inventors: Rogers, James P.
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US09/185,366
• Time in Patent Office: 882 Days
• Field of Search: 707/2, 707/3-5, 707/6, 707/9, 707/10, 707/100-104, 707/501, 707/503, 709/201-203, 709/219, 709/229, 713/200, 713/201, 713/202, 714/819, 711/117, 711/149
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system is provided for selecting an appropriate aggregated fact data table to use as the basis for calculating an aggregation request from a set of stored aggregated fact data tables. An estimate is established of the amount of processing time required to aggregate each of the tables. The table with the lowest estimate is then used to perform the aggregation.

Claims

1. A system for aggregating data comprising:

means for storing data in fact data tables at one of a plurality of levels in a plurality of dimensions;

means for providing an estimate of the amount of processing required to aggregate each fact data table to a requested set of levels from a set of plural dimensions;

means for selecting the fact data table associated with the lowest estimate with which to perform the aggregation; and

means for aggregating the data in the selected fact data table.

2. A system for aggregating data in accordance with claim 1, wherein said means for providing an estimate comprises partition objects, each of which includes information relating to one of said data tables, and each of which is provided with functionality to return a bid in response to a request for data at said set of levels, the value of the bid being a function of the requested set of levels and the stored set of levels.

3. A system in accordance with claim 1 wherein the estimate returned is proportional to the product over all requested dimensions of the ratio, in each dimension, of the number of members in the stored level to the number of members in the requested level.

4. A method for aggregating data comprising:

storing data as fact data table objects at one of a plurality of levels in a plurality of dimensions;

providing an estimate of the amount of processing required to aggregate each fact data table object to a requested set of levels from a set of plural dimensions;

selecting the fact data table object returning the lowest estimate with which to perform the aggregation; and

aggregating the data in the selected fact data table object.

5. A method in accordance with claim 4, wherein said step of providing an estimate comprises sending a request for a bid to a partition object, said partition object including information relating to one of said data tables, including the set of levels stored therein, and said partition object furthermore being provided with functionality to return a bid in response to a request for data at said set of levels, the value of said bid being a function of the requested set of levels and the stored set of levels.

6. A system in accordance with claim 5 wherein the estimate returned is proportional to the product over all requested dimensions of the ratio, in each dimension, of the number of members in the stored level to the number of members in the requested level.

7. A method in accordance with claim 4 wherein if one of said fact data tables contains a virtual partition forcing use of a predetermined fact data table, aggregating the data in said predetermined fact data table to the requested set of levels.

8. A system for aggregating data comprising:

a data store module for storing data in fact data tables at one of a plurality of levels in a plurality of dimensions;

an aggregate estimator providing an estimate of the amount of processing required to aggregate each fact data table to a requested set of levels from a set of plural dimensions;

wherein the data in a selected fact data table having the lowest estimated aggregation processing is aggregated.