Data Expiration and Aggregate Queries.
David Toman · 2009
Abstract. We investigate the space requirements for summaries needed for maintaining exact answers to aggregate queries over histories of relational databases. We show that, in general, a super-logarithmic lower bound (in the length of the history) on space needed to maintain a summary of the history in order to be able to maintain answers to counting queries. We also develop a natural restriction on the use of aggregation that allows for a logarithmic upper bound and in turn maintaining the summary of the history using counters. 1