Index for set emptiness in temporal databases

US8959048B1 · kind B1 · utility

Assignee

• Google LLC · US

Inventors

• Andreas Rossberg · Bad Säckingen, DE
• Ingo Walther · Munich, DE

Key dates

• Filing date: Oct 21, 2011
• Grant date: Feb 17, 2015
• Expiry date: Feb 19, 2033

Classification

• Technology area (CPC G): Physics
• CPC primary: G06F16/2365
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

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.