Index for set emptiness in temporal databases

摘要

A temporal database system, method, and computer-readable storage medium in which a database is provided with sets of entities defined by initial tuples having a set ID, a unique timestamp, and a member increment. A write transaction is performed for sets of entities, wherein the write transaction designates the set by said set ID and produces an increment, wherein the increment is a number of entities to be added to or removed from the designated respective set of entities. New tuples including the set ID, the increment, and a new unique timestamp are created for the write transaction. Following the write transaction, an asynchronous compaction operation is performed on the new tuples. The compaction operation aggregates the increment of each new tuple into summary point counts. The compaction operation facilitates efficient queries without contention with write transactions.

主权项

1. A computer-implemented method for a temporal database system, comprising:
providing the temporal database with at least one set of entities defined by initial tuples having a set ID and a first unique timestamp; performing at least two parallel write transactions for respective sets of the at least one set of entities, wherein each write transaction designates the respective set by said set ID and produces an increment, wherein the increment is a number of entities to be added to or removed from the designated respective set of entities; creating new tuples including the set ID, the increment, and a second unique timestamp for each write transaction, the second unique timestamp being a time within a predetermined time period before completion of each respective write transaction, wherein said creating is performed before completion of the parallel write transactions; and performing a compaction operation on the new tuples upon completion of the parallel write transactions that created the new tuples, wherein the compaction operation aggregates the increment of each new tuple into summary point counts.