Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/28420
Title: | Additive first-order queries | Authors: | Berger, Gerald Otto, Martin Pieris, Andreas SURINX, Dimitri VAN DEN BUSSCHE, Jan |
Issue Date: | 2019 | Source: | Barcelo, Pablo; Calautti, Marco (Ed.). 22nd International Conference on Database Theory (ICDT 2019),p. 1-14 (Art N° 19) | Series/Report: | LIPIcs – Leibniz International Proceedings in Informatics | Abstract: | A database query q is called additive if q(A ∪ B) = 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 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. | Keywords: | Expressive power | Document URI: | http://hdl.handle.net/1942/28420 | Link to publication/dataset: | http://drops.dagstuhl.de/opus/volltexte/2019/10321/ | ISBN: | 978-3-95977-101-6 | DOI: | 10.4230/LIPIcs.ICDT.2019.19 | Rights: | Gerald Berger, Martin Otto, Andreas Pieris, Dimitri Surinx, and Jan Van den Bussche; licensed under Creative Commons License CC-BY | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
LIPIcs-ICDT-2019-19.pdf | Published version | 497.66 kB | Adobe PDF | View/Open |
Page view(s)
46
checked on Sep 7, 2022
Download(s)
12
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.