Sparsity management system for multi-dimensional databases

• US 5,943,677 A
• Filed: 10/31/1997
• Issued: 08/24/1999
• Est. Priority Date: 10/31/1997
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Hicks, Grant E.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Loomis, John C.
• Application Number:
  US08/961,640
• Time in Patent Office: 662 Days
• Field of Search: 707/1, 707/100, 707/102, 707/205, 707/503
• US Class Current: 707/610
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

In a multi-dimensional database, a composite data construct is created to accommodate sparse dimensions. When the database is defined, sparse dimensions are identified and composites of those sparse dimensions are created. The composites are stored in a linearized array. The amount of storage space allocated is chosen by the database administrator to satisfy reasonable expected growth of the sparse data.

Claims

1. A method of storing data in a multi-dimensional database, comprising the steps:

receiving input data dimensioned by a plurality of base dimensions wherein there is a combination of base dimensions sparsely populated with data;

defining a composite of the sparse base dimensions; and

storing the populated data of the composite in a first block of data cells, the first block having a pre-selected size.

2. The method of claim 1 wherein the step of storing comprises allocating a linearized array of data cells for the first block.

3. The method of claim 1 wherein the step of storing comprises sizing the first block of data cells to accommodate an expected maximum size for the populated data over time.

4. The method of claim 1 wherein the step of storing comprises:

locating a target data cell for storing a data value from information stored in a descriptor; and

storing the data value into the target data cell.

5. The method of claim 4 wherein the step of storing comprises pre-allocating a subsection of the first block to include the target data cell.

6. The method of claim 4 wherein the step of storing the data value comprises:

annexing a second block of data cells to the first block, the second block including the target data cell; and

modifying the descriptor to localize the target data cell in the second block.

7. The method of claim 1 further comprising the step of generating a multi-dimensional report to include data stored the first block.

8. The method of claim 7 wherein the report is limited by the sparsely populated base dimensions.

9. The method of claim 1 wherein the step of defining comprises synchronizing the sparsely populated base dimensions with the composite.

10. The method of claim 9 wherein the step of synchronizing comprises incorporating a status of the sparsely populated base dimensions into a status of the composite.

11. An article of manufacture comprising:

a computer-readable medium;

in the computer-readable medium, a computer-implemented method for storing data in a multidimensional database, the program comprising the program steps of;

receiving input data dimensioned by a plurality of base dimensions wherein there is a combination of base dimensions sparsely populated with data;

defining a composite of the sparse base dimensions; and

storing the populated data of the composite in a first block of data cells, the first block having a pre-selected size.

12. The article of claim 11 wherein the program step of storing comprises allocating a linearized array of data cells for the first block.

13. The article of claim 11 wherein the program step of storing comprises sizing the first block of data cells to accommodate an expected maximum size for the populated data over time.

14. The article of claim 11 wherein the program step of storing comprises:

locating a target data cell for storing a data value from information stored in a descriptor; and

storing the data value into the target data cell.

15. The article of claim 14 wherein the program step of storing comprises pre-allocating a subsection of the first block to include the target data cell.

16. The article of claim 14 wherein the program step of storing the data value comprises:

annexing a second block of data cells to the first block, the second block including the target data cell; and

modifying the descriptor to localize the target data cell in the second block.

17. The article of claim 11 further comprising the program step of generating a multi-dimensional report to include data stored the first block.

18. The article of claim 17 wherein the report is limited by the sparsely populated base dimensions.

19. The article of claim 11 wherein the program step of defining comprises synchronizing the sparsely populated base dimensions with the composite.

20. The article of claim 19 wherein the program step of synchronizing comprises incorporating a status of the sparsely populated base dimensions into a status of the composite.

21. A system for storing data in a multi-dimensional database, comprising:

input data dimensioned by a plurality of base dimensions, wherein there is a combination of base dimensions sparsely populated with data;

a composite defined from the sparse base dimensions; and

a first block of data cells storing the populated data of the composite, the first block having a pre-selected size.

22. The system of claim 21 wherein the first block is a linearized array of data cells.

23. The system of claim 22 wherein the first block is sized to accommodate an expected maximum size for the populated data cells over time.

24. The system of claim 21 further comprising a descriptor for locating a target data cell to store a data value from information stored in the descriptor.

25. The system of claim 24 wherein a subsection of the first block is pre-allocated to include the target data cell.

26. The system of claim 24 further comprising:

a second block of data cells annexed to the first block, the second block including the target data cell; and

a modification to the descriptor to localize the target data cell in the second block.

27. The system of claim 21 further comprising a report generator to generate a multi-dimensional report to include data stored the first block.

28. The system of claim 27 wherein the report is limited by the sparsely populated base dimensions.

29. The system of claim 21 wherein the sparsely populated base dimensions are synchronized with the composite.

30. The system of claim 29 wherein a status of the sparsely populated base dimensions is incorporated into a status of the composite.