DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2019.19

Additive First-Order Queries

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

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract

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.

Cite as

Gerald Berger, Martin Otto, Andreas Pieris, Dimitri Surinx, and Jan Van den Bussche. Additive First-Order Queries. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:LIPIcs.ICDT.2019.19,
  author =	{Berger, Gerald and Otto, Martin and Pieris, Andreas and Surinx, Dimitri and Van den Bussche, Jan},
  title =	{{Additive First-Order Queries}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.19},
  URN =		{urn:nbn:de:0030-drops-103217},
  doi =		{10.4230/LIPIcs.ICDT.2019.19},
  annote =	{Keywords: Expressive power}
}

Search Results

Documents authored by Berger, Gerald

Additive First-Order Queries

Abstract

Cite as

Thanks for your feedback!

Could not send message