Compact representations of temporal databases

This paper investigates the storage compactness of temporal merges. A temporal merge is a joint representation of a set of snapshots of the same database at different points in time. An axiomatic requirement for temporal merges is that each individual snapshot must be derivable from it. We first show that the usual temporal extension of a database is a special kind of temporal merge called a direct merge. For direct merges, finding the most compact representation is easy for separate relations. However, if snapshots feature foreign key dependencies, the representation may contain more tuples than strictly needed. We therefore study inclusion dependencies in temporal databases and show how to use them while maintaining minimality in our representation. Next, we argue that direct merges imply redundancy when they contain non-contiguous, value-equivalent tuples. We therefore introduce a more general kind of temporal merge known as a coherent merge and study its properties in depth. Deriving a minimal coherent merge from a direct one is shown to be NP-hard. However, several greedy algorithms are demonstrated to provide decent results in quadratic time. Next, an incremental algorithm for construction of coherent merges is presented. We provide experimental results on real-life data sets that support the usefulness of the contributions of this paper.