The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates

Modern computing tasks such as real-time analytics require refresh of query results under high update rates. Incremental View Maintenance (IVM) approaches this problem by materializing results in order to avoid recomputation. IVM naturally induces a trade-off between the space needed to maintain the materialized results and the time used to process updates.

In this talk, we show that the full materialization of results is a barrier for more general optimization strategies. In particular, we present a new approach for evaluating queries under updates. Instead of the materialization of results, we require a data structure that allows: (1) linear time maintenance under updates, (2) constant-delay enumeration of the output, (3) constant-time lookups in the output, while (4) using only linear space in the size of the database. We call such a structure a Dynamic Constant delay Linear Representation (DCLR) for the query. We show that Dyn, a dynamic version of the Yannakakis algorithm, yields DCLRs for the class of free-connex acyclic CQs. We show that this is optimal in the sense that no DCLR can exist for CQs that are not free-connex acyclic. Moreover, we identify a sub-class of queries for which Dyn features constant-time update per tuple and show that this class is maximal. An experimental validation of Dyn shows that it is highly effective in practice.

The talk will conclude with current insights on ongoing research on how Dyn can be extended to also allow processing of more general classes of queries, in particular queries that feature in-equality joins rather than equality joins. Such in-equality joins are important in relational-style queries, but are also prominently present in the area of Complex Event Recognition.