Timeline index for partitioned temporal database tables

One or more non-transitory computer-readable media comprising computer-executable instructions causing a computing system to perform a method comprising:

• storing a plurality of tuples, respectively having a start time, in a plurality of partitions of a temporal database table partitioned according to a temporal partition technique and having respective time intervals comprising respective time interval begin times and time interval end times, wherein a given tuple is stored in a given partition for which the given tuple's start time is inside the given partition's time interval's begin time and time interval end time;
• storing a plurality of tuple events for the plurality of tuples in a plurality of partial timeline indexes respectively associated with the plurality of partitions, wherein a given partial timeline index is associated with the given partition and stores tuple events for tuples in the given partition, wherein tuple events in the given partial timeline index that occur inside the time interval of the associated given partition are stored within a local component of the given partial timeline index and tuple events in the given partial timeline index that occur outside the time interval of the associated given partition are stored within a foreign component of the given partial timeline index, wherein the tuple events comprise at least one activation event and at least one invalidation event, the activation event occurs within a time interval of a first partition, the invalidation event occurs within a time interval of a second partition different from the first partition, and the invalidation event is stored twice:
• in a partial timeline index of the first partition and in a partial timeline index of the second partition;
• generating, in parallel, a plurality of partial results of a temporal operator calculation based in part on one or more of the plurality of tuple events stored in the plurality of partial timeline indexes, wherein the generating comprises generating one partial result per partition, wherein the partial results are themselves expressed as timeline indexes;
• and
• generating a global result of the temporal operator calculation, wherein the generating comprises combining the plurality of partial results that are expressed as timeline indexes.

A system comprising one or more non-transitory computer-readable media comprising:

• a plurality of temporal partitions representing respective time intervals of a temporal database, wherein the time intervals comprise respective time interval begin times and time interval end times, wherein the respective time intervals are subsets of a timeline for the temporal database, and wherein the respective partitions of the plurality of temporal partitions respectively store tuples activated in their respective time intervals;
• a plurality of partial timeline indexes respectively indexing the plurality of temporal partitions, wherein a given partial timeline index is associated with a particular temporal partition having a particular time interval of the respective time intervals and the given partial timeline index comprises a local component and a foreign component, the local component comprising references to tuples that are activated or invalidated inside the particular time interval of the associated particular partition and the foreign component comprising references to invalidations of tuples activated in the particular time interval of the associated particular partition but invalidated outside the particular time interval of the associated partition, wherein tuple activations and invalidations are represented by tuple events, the tuple events comprise at least one activation event and at least one invalidation event, the activation event occurs within a time interval of a first partition, the invalidation event occurs within a time interval of a second partition different from the first partition, and the invalidation event is stored twice:
• in a partial timeline index of the first partition and in a partial timeline index of the second partition;
• a plurality of checkpoints, wherein a given checkpoint is associated with the given partial timeline index and comprises references to one or more tuples valid at a time interval preceding the particular time interval of the associated particular partition of the given partial timeline index;
• a plurality of partial results calculated in parallel, one per partition, wherein the partial results are themselves expressed as timeline indexes;
• and
• a global result, wherein the global result is combined from the plurality of partial results and is itself expressed as a timeline index.

One or more non-transitory computer-readable media comprising computer-executable instructions causing a computing system to perform a method comprising:

• for a temporal database table distributed into a plurality of partitions representing respective time intervals according to a system time represented by a global transaction number, storing a plurality of tuple events in a plurality of distributed partial timeline indexes respectively associated with the plurality of partitions, wherein the plurality of tuple events comprise activations or invalidations, activations comprising an indication of a start time of a given tuple and a reference to the given tuple stored in a given partition, and invalidations comprising an indication of an end time of the given tuple and the reference to the given tuple, wherein the distributed partial timeline indexes respectively comprise a local component for storing tuple events that occur within their respective time intervals and a foreign component for storing tuple events that occur outside their respective time intervals, wherein the tuple events comprise at least one activation event and at least one invalidation event, the activation event occurs within a time interval of a first partition, the invalidation event occurs within a time interval of a second partition different from the first partition, and the invalidation event is stored twice:
• in a foreign component of a partial timeline index of the first partition and in a local component of a partial timeline index of the second partition;
• storing a plurality of tuple references in a plurality of checkpoints respectively associated with the plurality of distributed partial timeline indexes, wherein a given checkpoint stores tuple references to one or more tuples valid at a time interval preceding a time interval of an associated particular partial timeline index;
• calculating in parallel a plurality of partial results for a temporal operator, wherein the calculating comprises consulting one or more of the plurality of distributed partial timeline indexes and consulting one or more of the plurality of checkpoints associated with respective of the one or more of the plurality of distributed partial timeline indexes;
• combining the plurality of partial results into a global result for the temporal operator, wherein the global result is expressed as a timeline index;
• converting the global result expressed as a timeline index into an equivalent temporal table;
• and
• outputting the converted equivalent temporal table.