2026-07-23T04:51:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10321 2024-03-06T10:45:48Z ddc:004 open_access

Additive First-Order Queries Berger, Gerald Otto, Martin Pieris, Andreas Surinx, Dimitri Van den Bussche, Jan Expressive power A database query q is called additive if q(A U B) = q(A) U q(B) for domain-disjoint input databases A and B. Additivity allows the computation of the query result to be parallelised over the connected components of the input database. We define the "connected formulas" as a syntactic fragment of first-order logic, and show that a first-order query is additive if and only if it expressible by a connected formula. This characterisation specializes to the guarded fragment of first-order logic. We also show that additivity is decidable for formulas of the guarded fragment, establish the computational complexity, and do the same for positive-existential formulas. Our results hold when restricting attention to finite structures, as is common in database theory, but also hold in the unrestricted setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gerald Berger and Martin Otto and Andreas Pieris and Dimitri Surinx and Jan Van den Bussche 2019 Is Part Of LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2019.19 urn:nbn:de:0030-drops-103217 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.19 eng https://creativecommons.org/licenses/by/3.0/legalcode