Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/28420
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Berger, Gerald | - |
dc.contributor.author | Otto, Martin | - |
dc.contributor.author | Pieris, Andreas | - |
dc.contributor.author | SURINX, Dimitri | - |
dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
dc.date.accessioned | 2019-06-17T12:26:24Z | - |
dc.date.available | 2019-06-17T12:26:24Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | Barcelo, Pablo; Calautti, Marco (Ed.). 22nd International Conference on Database Theory (ICDT 2019),p. 1-14 (Art N° 19) | - |
dc.identifier.isbn | 978-3-95977-101-6 | - |
dc.identifier.issn | 1868-8969 | - |
dc.identifier.uri | http://hdl.handle.net/1942/28420 | - |
dc.description.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. | - |
dc.language.iso | en | - |
dc.relation.ispartofseries | LIPIcs – Leibniz International Proceedings in Informatics | - |
dc.rights | Gerald Berger, Martin Otto, Andreas Pieris, Dimitri Surinx, and Jan Van den Bussche; licensed under Creative Commons License CC-BY | - |
dc.subject.other | Expressive power | - |
dc.title | Additive first-order queries | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.authors | Barcelo, Pablo | - |
local.bibliographicCitation.authors | Calautti, Marco | - |
local.bibliographicCitation.conferencedate | 26-29 March 2019 | - |
local.bibliographicCitation.conferencename | 22nd International Conference on Database Theory (ICDT 2019) | - |
local.bibliographicCitation.conferenceplace | Lisbon, Portugal | - |
dc.identifier.epage | 14 | - |
dc.identifier.spage | 1 | - |
local.bibliographicCitation.jcat | C1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Proceedings Paper | - |
local.bibliographicCitation.artnr | 19 | - |
dc.identifier.doi | 10.4230/LIPIcs.ICDT.2019.19 | - |
dc.identifier.url | http://drops.dagstuhl.de/opus/volltexte/2019/10321/ | - |
local.bibliographicCitation.btitle | 22nd International Conference on Database Theory (ICDT 2019) | - |
item.contributor | Berger, Gerald | - |
item.contributor | Otto, Martin | - |
item.contributor | Pieris, Andreas | - |
item.contributor | SURINX, Dimitri | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.fulltext | With Fulltext | - |
item.fullcitation | Berger, Gerald; Otto, Martin; Pieris, Andreas; SURINX, Dimitri & VAN DEN BUSSCHE, Jan (2019) Additive first-order queries. In: Barcelo, Pablo; Calautti, Marco (Ed.). 22nd International Conference on Database Theory (ICDT 2019),p. 1-14 (Art N° 19). | - |
item.accessRights | Open Access | - |
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.