Aggregation, Enumeration, and Updates on Sparse Databases via Circuits

We propose an algebraic framework for studying efficient algorithms for query evaluation, aggregation, enumeration, and maintenance under updates, on sparse databases. Our framework allows to treat those problems in a unified way, by considering various semirings, depending on the considered problem. We propose two query languages extending first-order logic by forms of semiring aggregation. In the first language, a query is evaluated in a fixed semiring. For various considered semirings, we obtain efficient algorithms for the evaluation and maintenance of query outputs. By employing the provenance semiring, we obtain as an application a linear-time algorithm which inputs a first-order query and a sparse database, and computes a dynamic data structure which allows to enumerate the answers to the query with constant delay. The data structure can be updated in constant time, upon updates to the database that do not modify its Gaifman graph. Our second query language extends the first one by allowing aggregates from multiple semirings simultaneously. We show that such queries can be evaluated in linear time on sparse databases.

Authors

• Szymon Toruńczyk.

Keywords

No keywords are indexed for this paper.