Time slider operator for temporal data aggregation

Patent metadata

Field	Value
Publication number	US-9720942-B2
Application number	US-201414265042-A
Country	US
Kind code	B2
Filing date	Apr 29, 2014
Priority date	Dec 23, 2011
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

Abstract

Calculation of aggregated values in a history database table can be optimized using an approach in which an ordered history table is accessed. The ordered history table can include a sequential listing of commit identifiers associated with updates, insertions, and/or deletions to values in the database table. The ordered history table can be traversed in a single pass to calculate an aggregation function using an optimized algorithm. The optimized algorithm can enable calculation of an aggregated metric of the values based on a selected method for tracking invalidated values to their corresponding commit identifiers. The calculated metric is generated for a current version of the database table; and promoted.

First claim

What is claimed is:

1. A non-transitory computer program product storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
accessing an ordered history table of a relational database, the ordered history table comprising a plurality of commit identifiers corresponding to one or more of respective updates, insertions, and deletions to values in a database table, the ordered history table being further sorted by a sequential listing of the commit identifiers identifying first occurrences of respective changes to one or more of the values;
calculating an aggregation function by traversing the sequential listing of the commit identifiers in a single pass using an optimized algorithm, the aggregation function comprising an aggregated metric of the values that correspond to a current version of the database table, the calculating comprising calculating the aggregated metric based on tracking invalidated values to their corresponding commit identifiers in the ordered history table using one or more of an invalidation index, a separate bitlist for each of the commit identifiers, or a previous version array generated by the optimized algorithm;
and
promoting the calculated aggregated metric.

2. A computer program product as in claim 1 , wherein the promoting comprises one or more of storing the aggregated metric, presenting the aggregated metric via a user interface display, and sending an electronic message comprising the calculated metric.

3. A computer program product as in claim 1 , wherein the operations further comprise selecting the optimized algorithm dependent on the aggregation function from a plurality of algorithms, the selecting comprising assessing one or more attributes of the database table in relation to a set of optimization criteria for each of the plurality of algorithms.

4. A computer program product as in claim 1 , wherein the traversing comprises one or more of incrementing a variable based on changes to the values at each commit identifiers, creating a chained list corresponding to each commit identifier, and creating a sorted list corresponding to each commit identifier.

5. A computer program product as in claim 1 , wherein the aggregated metric comprises one or more of a sum, a count, an average, a minimum value, a maximum value, a median, a mode, and skewness.

6. A system comprising:
at least one programmable processor; and
a machine-readable medium storing instructions that, when executed by the at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
accessing an ordered history table of a relational database, the ordered history table comprising a plurality of commit identifiers corresponding to one or more of respective updates, insertions, and deletions to values in a database table, the ordered history table being further sorted by a sequential listing of the commit identifiers identifying first occurrences of respective changes to one or more of the values;
calculating an aggregation function by traversing the sequential listing of the commit identifiers in a single pass using an optimized algorithm, the aggregation function comprising an aggregated metric of the values that correspond to a current version of the database table, the calculating comprising calculating the aggregated metric based on tracking invalidated values to their corresponding commit identifiers in the ordered history table using one or more of an invalidation index, a separate bitlist for each of the commit identifiers, or a previous version array generated by the optimized algorithm;

and
promoting the calculated aggregated metric.

7. A system as in claim 6 , wherein the promoting comprises one or more of storing the aggregated metric, presenting the aggregated metric via a user interface display, and sending an electronic message comprising the aggregated metric.

8. A system as in claim 6 , wherein the operations further comprise selecting the optimized algorithm from a plurality of algorithms, the selecting comprising assessing one or more attributes of the database table in relation to a set of optimization criteria for each of the plurality of algorithms.

9. A system as in claim 6 , wherein the traversing comprises one or more of incrementing a variable based on changes to the values at each commit identifiers, creating a chained list corresponding to each commit identifier, and creating a sorted list corresponding to each commit identifier.

10. A system as in claim 6 , wherein the aggregated metric comprises one or more of a sum, a count, an average, a minimum value, a maximum value, a median, a mode, and a skewness.

11. A computer-implemented method performed by one or more programmable processors, the computer-implemented method comprising:
accessing an ordered history table of a relational database, the ordered history table comprising a plurality of commit identifiers corresponding to one or more of respective updates, insertions, and deletions to values in a database table, the ordered history table being further sorted by a sequential listing of the commit identifiers identifying first occurrences of respective changes to one or more of the values;
calculating an aggregation function by traversing the sequential listing of the commit identifiers in a single pass using an optimized algorithm, the aggregation function comprising an aggregated metric of the values that correspond to a current version of the database table, the calculating comprising calculating the aggregated metric based on tracking invalidated values to their corresponding commit identifiers in the ordered history table using one or more of an invalidation index, a separate bitlist for each of the commit identifiers, or a previous version array generated by the optimized algorithm;
and
promoting the calculated aggregated metric.

12. A computer-implemented method as in claim 11 , wherein the promoting comprises one or more of storing the aggregated metric, presenting the aggregated metric via a user interface display, and sending an electronic message comprising the aggregated metric.

13. A computer-implemented method as in claim 11 , further comprising selecting the optimized algorithm from a plurality of algorithms, the selecting comprising assessing one or more attributes of the database table in relation to a set of optimization criteria for each of the plurality of algorithms.

14. A computer-implemented method as in claim 11 , wherein the traversing comprises one or more of incrementing a variable based on changes to the values at each commit identifiers, creating a chained list corresponding to each commit identifier, and creating a sorted list corresponding to each commit identifier.

15. A computer-implemented method as in claim 11 , wherein the aggregated metric comprises one or more of a sum, a count, an average, a minimum value, a maximum value, a median, a mode, and a skewness.

16. The computer-implemented method as in claim 11 , the optimized algorithm further performing operations comprising generating an invalidation index.

17. The computer-implemented method as in claim 11 , the optimized algorithm further performing operations comprising generating a separate bitlist for each of the commit identifiers.

18. The computer-implemented method as in claim 11 , the optimized algorithm further performing operations comprising generating a previous version array.

Assignees

• Kaufmann Martin
• May Norman
• Tonder Andreas
• Kossmann Donald
• Sap Se

Inventors

• Kaufmann Martin
• May Norman
• Tonder Andreas
• Kossmann Donald

Classifications

• G06F16/2477

  Temporal data queries · CPC title

• G06F16/219 Primary

  Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477) · CPC title

• G06F16/2365

  Ensuring data consistency and integrity · CPC title

• G06F16/2322 Primary

  using timestamps · CPC title

• G06F17/30353

  Physics · mapped topic