Methods and apparatus for maintaining consistency during analysis of large data sets

• US 20060288046A1
• Filed: 06/15/2005
• Published: 12/21/2006
• Est. Priority Date: 06/15/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Interlace Systems, Inc. (Oracle Corporation)
• Inventors: Gupta, Anurag, Ramaiyer, Kumar, Xiao, John, Shore, Matthew
• Granted Patent: US 7,571,192 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Methods and apparatus for updating a database using a multi-dimensional data model in which data corresponding to the database are organized in multi-dimensional data blocks. Each data block has summary information associated therewith corresponding to a current state of evolution of the associated data block. Dependency information is maintained in the data model which identifies data dependencies within and among the data blocks. A list of change entries identifies changes made to the data blocks and times at which the changes were made. A request to apply a change entry to a data block is received. The change entry is applied to the data block, including generating a dependency list of data blocks whose data depends directly or indirectly from the updated data block. The data blocks in the dependency list are processed in accordance with a dependency update algorithm to update the data blocks in the dependency list.

Claims

1. An on-change applicator for applying changes to multi-dimensional data blocks in a database using a multi-dimensional data model, wherein each data block includes a plurality of data elements, the on-change applicator comprising computer program code for:

receiving a request to update one or more data elements in a data block;

obtaining a change information entry from a list of change information entries; and

updating the data elements in the data block in accordance with one or more rules selected based on the data elements that are affected by the update, the updating using only the obtained change information entry and data elements already existing in the data block, whereby the on-change applicator ensures that all data utilized in the updating is as of a consistent point in time.

2. The on-change applicator of claim 1, wherein the rules include one or more mathematical formulas defining expressions for updating each type of data element in the data block.

3. The on-change applicator of claim 1, wherein the change information entries include at least the following elements:

a change information entry number describing when the change entry was created, locations of one or more data elements that are affected by the change information entry, old values for the data elements, and new values for the data elements.

4. The on-change applicator of claim 1, wherein the change information entry includes a vector of new values for the data elements, and the computer program code for updating the data elements includes computer program code for updating several data elements of the data block in a single operation using the vector.

5. The on-change applicator of claim 1, further comprising computer program code for determining when to apply the change information entry to the data block with reference to updates performed by other on-change applicators, wherein the determination is made with respect to a dependency structure in the data model that identifies data dependencies between data elements within and among the data blocks.

6. The on-change applicator of claim 5, further comprising computer program code for determining when to calculate data values within the data block between application of two separate on-change applicators, wherein the determination is made with respect to a dependency structure in the data model that identifies data dependencies between data elements within the data blocks and the change information entries.

7. The on-change applicator of claim 1, further including computer program code for retrieving data from other data blocks and non-multidimensional data structures in the database.

8. The on-change applicator of claim 1, further including computer program code for generating the one or more on-change applicator rules based on a changed operand and a resultant, by redefining a mathematical formula using inverse operations for one or more unchanged operands.

9. The on-change applicator of claim 1, further including computer program code for determining data values to be stored in a change information entry, wherein the determination is made with respect to a dependency structure in the data model that identifies operands required for each on-change applicator for a particular type of change information entries.

10. A computer-implemented method for updating a database using a multi-dimensional data model in which data corresponding to the database are organized in multi-dimensional data blocks, each data block having summary information associated therewith corresponding to a current state of evolution of the associated data block, the method comprising:

maintaining dependency information in the data model which identifies data dependencies within and among the data blocks;

maintaining a list of change entries which identifies changes made to particular ones of the data blocks and times at which the changes were made;

receiving a request to apply a change entry to a data block;

applying the change entry to the data block, including generating a dependency list of data blocks whose data depends directly or indirectly from the updated data block; and

processing the data blocks in the dependency list in accordance with a dependency update algorithm to update the data blocks in the dependency list.

11. The method of claim 10, wherein processing includes processing a data block in the dependency list if the processing of the data block will generate a new change entry.

12. The method of claim 10, wherein each data block includes one or more data elements, and wherein processing includes processing a data block in the dependency list if the processing of the data block may generate a new change entry as a result of an expression for a specific data element that sparse summarizes.

13. The method of claim 10, wherein each data block includes one or more data elements, and wherein processing includes processing a data block in the dependency list if the application of a change entry may result in a new change entry that falls out of the evaluation of any expression for any sparse summarizing measure.

14. The method of claim 10, wherein processing includes processing each data block in the dependency list.

15. The method of claim 10, wherein processing includes storing only non-transient changes into the list of change entries.

16. The method of claim 10, wherein maintaining change information entries includes maintaining a calculation change list number which identifies a point in time at which all change entries have been processed, whereby the calculation change list defines an earliest starting point processing of the data blocks in the dependency list.

17. The method of claim 16, wherein several calculation change list numbers are maintained for subsets of the database, wherein the collection of subsets form a partition over the data model.

18. The method of claim 16, wherein the applying step and the processing step are part of a same operation.

19. The method of claim 10, wherein processing includes processing is deferred until a data block in the dependency list is queried or until a change list entry is to be applied to a data block in the dependency list.

20. The method of claim 10, wherein processing includes processing the data blocks in the dependency list in accordance with a scoping relationship defined by a user'"'"'s capabilities within the database.

21. The method of claim 10, wherein applying a change entry includes applying a compound change entry defining a change that repeats over multiple time periods.

22. The method of claim 10, wherein processing includes applying a compound change entry defining a change that repeats over multiple data elements along one or more dense dimensions defining the block.

23. The method of claim 10, wherein applying a change entry includes applying a change entry using an on-change applicator.

24. The method of claim 10, wherein processing includes applying a change entry using an on-change applicator.

25. The method of claim 10, wherein receiving a request includes:

receiving a user input value into a cell of a data block that is designated to contain a derived value; and

monitoring any constraint violations resulting from the user input value until the constraint violations have been resolved.

26. The method of claim 25, wherein processing includes:

determining whether the cell with the user input value has any dependent values in one or more other blocks; and

when the cell with the user input value has a dependent value in another block, creating a compensating derived change list entry that adjusts the dependent values in the one or more other blocks.

27. The method of claim 26, wherein processing includes:

determining whether the cell with the user input value has any dependent values in one or more other blocks that are user input and are derived; and

when a data value is modified and depends on both the user input derived values, assigning the compensating derived change list entry to only an innermost user input derived value.

28. The method of claim 27, wherein processing includes:

determining whether all values depending from the cell with the user input value are in the same block;

when all values depending from the cell with the user input value are determined to be in the same block, reserving additional disk space to indicate that the derived data value has been modified by a user input; and

ensuring that the user input value is not overridden by a derived value.

29. The method of claim 10, further comprising:

creating a mapping between one or more data elements in a row source and one or more data elements in a data block in order to apply calculation rules to the data blocks that access data elements stored in a row source format.

30. The method of claim 29, wherein the mapping defines one or more of:

a scoping, a dimension map specification and a temporal transformation.

31. The method of claim 29, further comprising:

using the mapping to transform a change list entry for a row source into one or more change list entries for a target cube dependent upon the row source, whereby changes to the row source can be propagated to the target cube.

32. The method of claim 29, further comprising:

using the mapping to transform a dependency relationship of data values within a row source to a dependency relationship within a cube.

33. The method of claim 10, further comprising:

creating a mapping between one or more data elements in a first cube and one or more data elements in a second cube, wherein the mapping defines one or more of;

allocation operations, transformation operations and aggregation operations.

34. The method of claim 33, wherein the mapping defines one or more of:

a scoping, a dimension map specification and a temporal transformation.

35. The method of claim 33, further comprising:

using the mapping to transform a change list entry for the first cube into one or more change list entries for the second cube, wherein the second cube depends upon the first cube, whereby changes to the data elements in the first cube can be propagated to data elements in the second cube.

36. The method of claim 33, further comprising:

using the mapping to transform a dependency relationship of data values within a cube to a dependency relationship of data values across cubes.

37. A computer-implemented method for running multiple scenarios using data from an underlying database, the data being organized according to a multi-dimensional data model in which the data are organized in multi-dimensional blocks, each block having summary information associated therewith corresponding to a current state of evolution of the associated block, the data model further comprising dependency information which identifies data dependencies within and among the blocks, the method comprising:

running a first scenario process, the first scenario process maintaining first change information which identifies first changes made to copies of first ones of the blocks and times at which the first changes were made, the first scenario process facilitating recalculation of the copies of the first blocks and copies of first dependent blocks to incorporate the first changes;

running a second scenario process substantially simultaneously with the first scenario process, the second scenario process maintaining second change information which identifies second changes made to copies of second ones of the blocks and times at which the second changes were made, the second scenario process facilitating recalculation of the copies of the second blocks and copies of second dependent blocks to incorporate the second changes;

wherein the first changes are not available to the second scenario process until committed to the underlying database and the second changes are not available to the first scenario process until committed to the underlying database; and

updating the underlying database with reference to the dependency information, the summary information, and the first change information, thereby making the first changes available to the second scenario process,

wherein the updating includes a reconciliation of the second change information with the first change information, ensuring that the second scenario sees data as if all the first scenario'"'"'s change information is applied to data blocks before any of the second scenario'"'"'s change information, thereby preserving data consistency.

38. The method of claim 37, wherein updating includes:

determining a sequence in which the first changes and the second changes were committed to the underlying database;

in order of the determined sequence,

applying the change information to the database, including generating a dependency list of data changes whose data depends directly or indirectly from the prior changed data changes; and

processing the data changes in the dependency list in accordance with a dependency update algorithm to update the data changes in the dependency list.

39. The method of claim 37, wherein the first and second scenario processes are organized in a hierarchical relationship and further comprising:

collecting garbage blocks relating to a scenario process when one or more of the following situations occur;

when a child scenario process is discarded or committed to the database, when changes are committed to a scenario process, or when a reconciliation of two scenario processes occurs.

40. The method of claim 37, wherein a child scenario process is committed to the database only when no reconciliation is needed with a parent scenario process;

and

wherein updating comprises replacing blocks in the parent scenario process with corresponding blocks from the child scenario process.

41. The method of claim 37, further comprising:

for each scenario process, whenever a change occurs to a block involved in a scenario process, also evolving blocks that are not affected by the change to a current state.

42. The method of claim 41, wherein each block is segmented in to a header portion and a data portion, and evolving includes:

determining whether the data portion of the block will remain the same after evolution as before evolution; and

when it is determined that the data portion will remain the same, only evolving the header information of the block to a current state.