Additive first-order queries

Gerald Berger, Martin Otto, Andreas Pieris, Dimitri Surinx, Jan Van den Bussche

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

A database query q is called additive if q(AB) = q(A) ∪ 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 characterization 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.
Original languageEnglish
Title of host publication22nd International Conference on Database Theory (ICDT 2019)
EditorsPablo Barcelo, Marco Calautti
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Number of pages15
ISBN (Electronic)978-3-95977-101-6
Publication statusPublished - 19 Mar 2019
Event22nd International Conference on Database Theory - Lisbon, Portugal
Duration: 26 Mar 201929 Mar 2019

Publication series

ISSN (Electronic)1868-8969


Conference22nd International Conference on Database Theory
Abbreviated titleICDT 2019
Internet address

Keywords / Materials (for Non-textual outputs)

  • Expressive power
  • query languages


Dive into the research topics of 'Additive first-order queries'. Together they form a unique fingerprint.

Cite this