Conjunctive Queries with Output Access Patterns under Updates

06/17/2022
by   Ahmet Kara, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset