Encapsulation of multiplicity and sparsity in multidimensional query execution systems

• US 8,463,745 B2
• Filed: 10/18/2011
• Issued: 06/11/2013
• Est. Priority Date: 10/18/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Grosset, Robin N., Vazquez, Jose, Zou, Yu
• Primary Examiner(s): Lee, Wilson
• Application Number:
  US13/276,194
• Publication Number:
  US 20130097200A1
• Time in Patent Office: 602 Days
• Field of Search: 707615-619, 707/626, 707633-639, 707736-754, 713/164, 713/194
• US Class Current: 707/634
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Provided are techniques for processing a multidimensional query. For each multidimensional expression in the multidimensional query, the multidimensional expression is evaluated to generate a representation that includes an evaluation context, a degeneration status, and condensed value storage that does not store data that would be replicated due to degeneration, and the representation is stored.

Claims

1. A computer program product for processing a multidimensional query, the computer program product comprising:

a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code, when executed by a processor of a computer, is configured to perform;

in response to determining that a multidimensional expression includes an operator with multiple operands;

finding a non-degenerated set of an evaluation result of the operation as a minimum combination that contains non-degenerated sets of the multiple operands for the operation;

evaluating the multidimensional expression by iterating through values of evaluation results of the multiple operands to find value pairs used to calculate the operation and to generate a representation that includes an evaluation context, a degeneration status, and a condensed value storage that does not store data that would be replicated due to degeneration; and

storing the representation.

2. The computer program product of claim 1, wherein the iteration simultaneously iterates over multiple evaluation results, while finding the value pairs based on the evaluation context and while taking into consideration the degeneration status of the operands.

3. The computer program product of claim 1, wherein the iteration skips empty combinations.

4. The computer program product of claim 1, wherein the degeneration status represents hierarchies in which a result of the evaluation of the multidimensional expression is the same for all cells that differ only in member selections on the hierarchies.

5. The computer program product of claim 1, wherein the evaluation context matches a result of the evaluation with a corresponding tuple in the evaluation context.

6. The computer program product of claim 1, wherein the condensed value storage stores non-empty cells within a subspace of non-degenerated hierarchies without storing repeated values for hierarchies that are degenerated.

7. The computer program product of claim 1, wherein the computer readable program code, when executed by the processor of the computer, is configured to perform:

parsing the multidimensional query to identify each multidimensional expression.

16. The computer program product of claim 1, wherein the computer readable program code, when executed by the processor of the computer, is configured to perform:

in response to determining that the multidimensional expression includes the operator with a single operand, evaluating the multidimensional expression to generate a new representation that includes an evaluation context, a degeneration status, and condensed value storage that does not store data that would be replicated due to degeneration.

8. A computer system for processing a multidimensional query, comprising:

a processor; and

a storage device coupled to the processor, wherein the storage device has stored thereon a program, and wherein the processor is configured to execute instructions of the program to perform operations, wherein the operations comprise;

in response to determining that a multidimensional expression includes an operator with multiple operands;

finding a non-degenerated set of an evaluation result of the operation as a minimum combination that contains non-degenerated sets of the multiple operands for the operation;

evaluating the multidimensional expression by iterating through values of evaluation results of the multiple operands to find value pairs used to calculate the operation and to generate a representation that includes an evaluation context, a degeneration status, and a condensed value storage that does not store data that would be replicated due to degeneration; and

storing the representation.

9. The computer system of claim 8, wherein the iteration simultaneously iterates over multiple evaluation results, while finding the value pairs based on the evaluation context and while taking into consideration the degeneration status of the operands.

10. The computer system of claim 8, wherein the iteration skips empty combinations.

11. The computer system of claim 8, wherein the degeneration status represents hierarchies in which a result of the evaluation of the multidimensional expression is the same for all cells that differ only in member selections on the hierarchies.

12. The computer system of claim 8, wherein the evaluation context matches a result of the evaluation with a corresponding tuple in the evaluation context.

13. The computer system of claim 8, wherein the condensed value storage stores non-empty cells within a subspace of non-degenerated hierarchies without storing repeated values for hierarchies that are degenerated.

14. The computer system of claim 8, wherein the operations further comprise:

parsing the multidimensional query to identify each multidimensional expression.

15. The computer system of claim 8, wherein the operations further comprise:

in response to determining that the multidimensional expression includes the operator with a single operand, evaluating the multidimensional expression to generate a new representation that includes an evaluation context, a degeneration status, and condensed value storage that does not store data that would be replicated due to degeneration.