APPARATUS AND METHOD FOR DYNAMICALLY MATERIALIZING A MULTI-DIMENSIONAL DATA STREAM CUBE

• US 20090327330A1
• Filed: 06/27/2008
• Published: 12/31/2009
• Est. Priority Date: 06/27/2008
• Status: Active Grant

• Current Assignee: SAP France SA (SAP SE)
• Original Assignee: Business Objects SA (SAP SE)
• Inventors: ABOUZIED, Azza Mohamed Nagib Mohamed, Slonim, Jacob, McAllister, Michael Joseph
• Granted Patent: US 8,024,287 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/958 Data cubes

Abstract

A computer readable storage medium comprises executable instructions to generate a stream cube to store data received from multiple data sources. A plurality of multi-dimensional data streams are generated to represent the received data. A materialization strategy is repeatedly determined for the stream cube. The stream cube is materialized according to the materialization strategy to record the multi-dimensional data streams.

Claims

1. A computer readable storage medium, comprising executable instructions to:

generate a stream cube to store data received from multiple data sources;

generate a plurality of multi-dimensional data streams to represent the received data;

repeatedly determine a materialization strategy for the stream cube; and

materialize the stream cube according to the materialization strategy to record the multi-dimensional data streams.

2. The computer readable storage medium of claim 1, wherein the multi-dimensional data streams comprise a plurality of multi-dimensional data tuples, each data tuple associated with a timestamp.

3. The computer readable storage medium of claim 2, wherein the stream cube comprises a plurality of sub-cubes associated with a plurality of time ranges each sub-cube aggregating multi-dimensional data for a given time range.

4. The computer readable storage medium of claim 3, wherein each sub-cube comprises a plurality of cuboids, each cuboid representing a set of dimensions and measures.

5. The computer readable storage medium of claim 3, wherein the plurality of sub-cubes are grouped by a set of time ranges.

6. The computer readable storage medium of claim 1, wherein the executable instructions to repeatedly determine a materialization strategy for the stream cube comprise executable instructions to repeatedly evaluate system conditions and users'"'"' requests and determine how to materialize the stream cube in response to the system conditions and users'"'"' requests.

7. The computer readable storage medium of claim 6, wherein the materialization strategy comprises a materialization strategy selected from the group consisting of on-demand materialization, full materialization, and partial materialization.

8. The computer readable storage medium of claim 7, wherein the executable instructions to repeatedly determine a materialization strategy for the stream cube comprise executable instructions to repeatedly determine a materialization path for the stream cube according to a predetermined criterion and a cost function.

9. The computer readable storage medium of claim 8, wherein the executable instructions to materialize the stream cube comprise executable instructions to record the plurality of multi-dimensional data streams along the materialization path.

10. A computer readable storage medium, comprising executable instructions to:

generate a stream cube for representing multi-dimensional data streams;

repeatedly determine a materialization path for the stream cube based on a predetermined criterion and a cost function; and

record the multi-dimensional data streams into the stream cube according to the materialization path.

11. The computer readable storage medium of claim 10, wherein the multi-dimensional data streams comprise a plurality of multi-dimensional data tuples, each data tuple associated with a timestamp.

12. The computer readable storage medium of claim 11, wherein the stream cube comprises a plurality of sub-cubes associated with a plurality of time ranges, each sub-cube aggregating multi-dimensional data for a given time range.

13. The computer readable storage medium of claim 12, wherein each sub-cube comprises a plurality of cuboids, each cuboid representing a set of dimensions and measures.

14. The computer readable storage medium of claim 13, wherein the executable instructions to repeatedly determine a materialization path comprise executable instructions to repeatedly evaluate the predetermined criterion to determine when to compute the materialization path.

15. The computer readable storage medium of claim 14, wherein the predetermined criterion is selected from a group consisting of a query-based criterion, a threshold-based criterion, and a time-based criterion.

16. The computer readable storage medium of claim 14, wherein the executable instructions to repeatedly determine a materialization path comprise executable instructions to compute the cost function for each cuboid.

17. The computer readable storage medium of claim 16, wherein the cost function comprises a function of a set of parameters and a set of weights assigned to the cuboid parameters.

18. The computer readable storage medium of claim 17, wherein the cuboid parameters are selected from a group consisting of cuboid materialization memory cost, cuboid popularity, and cuboid update potential.

19. The computer readable storage medium of claim 16, further comprising executable instructions to determine a cost for each potential materialization path in the stream cube.

20. The computer readable storage medium of claim 19, further comprising executable instructions to select the materialization path from all potential materialization paths that has the lowest cost.

21. The computer readable storage medium of claim 20, wherein the executable instructions to select the materialization path comprise executable instructions to use an optimization technique selected from the group consisting of dynamic programming, integer programming and simulated annealing.

22. The computer readable storage medium of claim 13, wherein the executable instructions to record the multi-dimensional data streams into the stream cube according to the materialization path comprise executable instructions to update measures for cuboids along the materialization path within each sub-cube in the plurality of sub-cubes.

23. A method for dynamically materializing a multi-dimensional stream cube having a plurality of cuboids, comprising:

computing a cost for materializing each cuboid in the stream cube;

computing a cost for each potential materialization path in the stream cube; and

selecting a materialization path from the potential materialization paths in the stream cube that has the lowest cost.

24. The method of claim 23, further comprising:

iterating through all cuboids in the stream cube from a first cuboid to a second cuboid to determine a predecessor cuboid for each cuboid, the predecessor cuboid associated with a cost value;

storing the predecessor cuboid and its associated cost value; and

backtracking from the second cuboid to the first cuboid to generate a materialization path for the stream cube.

25. The method of claim 24, further comprising refreshing the stream cube according to the materialization path.