Project R-13653

Dissociated Processing of Recursive Queries under Updates (Research)

The ability to efficiently query changing data is a key requirement in many contemporary applications. It has recently been recognized that queries that are not efficiently processed under updates by conventional algorithms can be processed efficiently by "dissociating" the processing into two stages: (1) an update stage where only a succinct "representation" of a query result is maintained, and (2) a retrieval stage where this representation is used to efficiently enumerate query answers. The realization of dissociated update processing in concrete systems has shown orders of magnitude speedups compared to the state of the art. To date dissociated update processing has only been studied for query languages without recursion. This is in stark contrast to the rising attention for queries with recursion, most notably Datalog, which supports analytics in diverse domains such as data integration, graph analysis, and distributed machine learning, among others. In this project, we postulate that by developing dissociated update processing for recursive queries, we may open the door to similar performance improvements in the recursive context and its application domains. Concretely, we propose to (1) study the class of recursive queries that have ideal complexity in the dissociated framework; (2) integrate dissociated update processing in Datalog; and (3) study structural properties of update streams that may be exploited to facilitate dissociated processing.

01 January 2023 - 31 December 2026