Conjunctive Queries with Output Access Patterns under Updates
share
We study the dynamic evaluation of conjunctive queries with output access patterns. An access pattern is a partition of the free variables of the query into input and output.The query returns tuples over the output variables given a tuple over the input variables. Our contribution is threefold. First, we give a syntactic characterisation of queries that admit constant time per single-tuple update and whose output tuples can be enumerated with constant delay given an input tuple. Second, we define a class of queries that admit optimal, albeit non-constant, update time and delay. Their optimality is predicated on the Online Matrix-Vector Multiplication conjecture. Third, we chart the complexity trade-off between preprocessing, update time and enumeration delay for such queries. Our results recover prior work on the dynamic evaluation of conjunctive queries without access patterns.
READ FULL TEXT