Method and apparatus for dynamically representing aggregated and segmented data views using view element sets

• US 6,535,872 B1
• Filed: 04/08/1999
• Issued: 03/18/2003
• Est. Priority Date: 04/08/1999
• Status: Active Grant

• Current Assignee: SINOEAST CONCEPT LIMITED (Tencent Holdings Limited)
• Original Assignee: International Business Machines Corporation
• Inventors: Castelli, Vittorio, Smith, John R., Li, Chung-Sheng
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/288,580
• Time in Patent Office: 1,440 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5-6, 707/100, 707/102, 707/205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Apparatus and method for generating a view element representation of multiple-attribute tabular data are provided, including converting tabular data into a multidimensional lattice form whereby each functional attribute of the relational data is mapped to a dimension in the lattice, and each cell in the lattice corresponds to an aggregation over records in the data table. The mechanism further provides for generating a view element representation of multidimensional lattice data comprising decomposing the multidimensional data into view elements such that the view elements retain sufficient information to reconstruct the original lattice data. Alternatively, the mechanism for generating a view element data representation including iterative decomposition of the lattice data into aggregated and residual view elements or by spatially partitioning the lattice data. Further taught are an apparatus and a method for generating a view element data representation including the decomposition of the lattice data by iteratively and jointly aggregating and spatially partitioning the lattice data. Under the system for representing the data using view element sets, costs and benefits are assigned to the view elements and the view element sets are formed on the bases of the costs and benefits. A view of the data from a set of view elements is synthesized by selecting view elements from the view element sets and assembling the view elements together to construct the views.

Claims

1. A computerized method of generating a representation of multidimensional data using view element sets comprising the steps of:

decomposing the data into an indexed hierarchy of view elements using a view element graph by one of aggregating and segmenting multidimensional lattice data using partial aggregation and residual aggregation operator pairs;

assigning a cost and benefit of materialization to each view element;

searching through a population of candidate view element sets and evaluating the costs and benefits of each one;

selecting a view element set based on said evaluation; and

storing and indexing the view elements in the selected view element set.

9. A computerized method of generating a representation of multidimensional data according to claim 1, wherein the view elements correspond to spatial partitions of the multidimensional data.

10. A computerized method of generating a representation of multidimensional data according to claim 1, therein the view elements correspond to aggregations and aggregation residuals of the multidimensional data.

11. A computerized method of generating a representation of multidimensional data according to claim 1, wherein the view elements correspond to a spectral partitions of the multidimensional data.

12. A computerized method of generating a representation of multidimensional data according to claim 1 wherein said view elements correspond one of the group consisting of spatial, aggregated, residual, and/or spectral decompositions of the multidimensional data and combinations thereof.

2. A computerized method of constructing views of multidimensional data by retrieving and assembling view elements stored for said data comprising the steps of:

identifying which view elements, in a view element hierarchy data structure generated from a multidimensional lattice by one of aggregating and segmenting the lattice data using partial aggregation and residual aggregation operator pairs, support the view;

retrieving the necessary view elements, and

materializing said view from said view elements.

3. The method of claim 2 further comprising the step of further decomposing the view elements to construct the view.

4. The method of claim 2 further comprising the step of synthesizing the view elements together to construct the view.

5. A computerized method of dynamically reconfiguring a data representation comprising a stored set of view elements stored in a view element hierarchy data structure of multidimensional stored data to adapt to patterns of view access comprising the steps of:

determining the frequency of access of each view;

performing cost-benefit analysis to select a new view element set comprising view elements decomposed using partial aggregation and residual aggregation operator pairs;

comparing said stored view element set to said new view element set; and

storing said new view element set in the view element hierarchy data structure when said stored view element set and said new view element set are different.

6. The method of claim 5 wherein said determining comprises estimating the likelihood of access of said view.

7. The method of claim 5 wherein previous access records are maintained and wherein said determining comprises consulting said previous access records.

8. The method of claim 5 wherein said storing of said new view element set comprises replacing only those view elements in said stored view element set which do not appear in said new view element set.

13. A system for generating a representation of multidimensional data using view element sets comprising:

decomposition means for decomposing the data into an indexed hierarchy of view elements using a view element graph by one of aggregating and segmenting multidimensional lattice data with partial aggregation and residual aggregation operator pairs;

view element cost assignment means for assigning a cost and benefit of materialization to each view element;

means for searching through a population of candidate view element sets and evaluating the costs and benefits of each one;

means for selecting a view element set based on said evaluation; and

means for storing and indexing the view elements in the selected view element set.

14. A system for constructing views of multidimensional stored data by retrieving and assembling view elements stored for said data comprising:

means for identifying which view elements, in a view element hierarchy data structure generated from a multidimensional lattice by one of aggregating and segmenting the lattice data using partial aggregation and residual aggregation operator pairs, support the view;

retrieval means for retrieving the necessary view elements; and

means for materializing said view from said view elements.

15. A system for dynamically reconfiguring a data representation comprising a stored set of view elements stored in a view element hierarchy data structure of multidimensional stored data decomposed using partial aggregation and residual aggregation operator pairs;

to adapt to patterns of view access comprising;

means for determining the frequency of access of each view;

means for performing cost-benefit analysis to select a new view element set;

means for comparing said stored view element set to said new view element set; and

storage means for storing said new view element set in the view element hierarchy data structure when said stored view element set and said new view element set are different.