11 October 2024, 10:30-11:30.
ENS, room S16.
Datalog boundedness over temporal databases
Abstract: We augment datalog with operators of linear temporal logic in order to query dynamic structures where relationships between objects change over time (e.g., in social network graphs, friendships may break but may later be restored). Unlike standard datalog, where queries are either bounded (and thus can be evaluated in AC^0) or unbounded (and thus their evaluation is LogSpace-hard), temporal datalog provides a more refined hierarchy of data complexity, featuring, in addition, queries whose evaluation is in ACC^0 or NC^1-complete. I will present a work-in-progress on how to decide the exact data complexity of a given query.
Without time, boundedness is known to be undecidable for binary queries, but decidable for monadic ones. Temporal monadic queries fall in-between, with time serving as a kind of second variable hidden behind temporal operators. Whether this leads to undecidability depends on which operators are permitted.
