Abstract
In this PhD thesis we present a series of place-sweeping algorithms for effectively performing interval joins and aggregation in temporal databases. We support interval joins on different conditions, such as the SQL:2011 temporal predicates and Allen’s interval relations. Using a new data structure—the gapless hash map that optimizes memory access patterns while performing the joins—and a lazy evaluation technique, we are able to achieve performance gains by exploiting features of contemporary CPU architectures. For aggregation, we provide solutions for temporal aggregation on fixed intervals, such as a sliding windows or GROUP BY ROLLUP aggregation, and improve the existing algorithm for computing MIN/MAX temporal aggregates on constant intervals. Our method for selective aggregation relies on a new and very space-efficient data structure called MAX Skyline. All our algorithms employ the Timeline Index, which already supports temporal joins, time travel and temporal aggregation on constant intervals, and has the potential of becoming a universal index for temporal database systems. We therefore extend the set of operations supported by the Timeline Index and provide more efficient alternatives to several existing algorithms. In an experimental evaluation we compare our algorithms with the state-of-the-art. In some cases we improve the performance by orders of magnitude. In other cases our approach provides more functionality or does not depend on specialized access methods precomputed for a single query.