The Dynamic Complexity of Acyclic Conjunctive Queries

Conjunctive queries (CQs) are a simple but important class of first-order definable queries. They correspond to SELCT-PROJECT-JOIN SQL queries, so they are part of almost every database query language. While the evaluation problem for CQs is in general NP-complete, there are interesting special cases of this problem that admit very fast algorithms (both in theory and in practise). For example the combined complexity (that means when both the CQ and the database are part of the input) of the evaluation problem for acyclic conjunctive queries (ACQs) is extremely low (it lies in the class LOGCFL, which means that it can be solved in polylogarithmic parallel time). The same holds for determining whether a CQ is acyclic.

In this talk we study the combined complexity of the evaluation problem in acyclic conjunctive queries from a dynamic point of view. The goal of dynamic complexity is to determine the minimum resources needed for maintaining the answer to a problem when the input changes dynamically. An important dynamic complexity class is the class DynFO which contains all problems that can be maintained using first order formulas after single tuple insertions and deletions into/from the input. We show that the result of the evaluation of an ACQ can be maintained in DynFO after insertions and deletions of atoms into/from the query and also that it is very unlikely that the evaluation result of an ACQ can be maintained in DynFO after both changes in the database and the query. Finally we show that determining whether a query is acyclic can also be maintained in DynFO. This is joint work in progress with Nils Vortmeier.