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

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
Pages19:1-19:14
Number of pages15
Volume127
ISBN (Electronic)978-3-95977-101-6
DOIs
Publication statusPublished - 19 Mar 2019
Event22nd International Conference on Database Theory - Lisbon, Portugal
Duration: 26 Mar 201929 Mar 2019
http://edbticdt2019.inesc-id.pt/

Publication series

NameLIPICS
Volume127
ISSN (Electronic)1868-8969

Conference

Conference22nd International Conference on Database Theory
Abbreviated titleICDT 2019
Country/TerritoryPortugal
CityLisbon
Period26/03/1929/03/19
Internet address

Keywords

  • Expressive power
  • query languages

Fingerprint

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

Cite this