www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/19796

Title: Datalog Queries Distributing over Components
Authors: Ameloot, Tom
Ketsman, Bas
Neven, Frank
Zinn, Daniel
Issue Date: 2015
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Citation: Arenas, Marcelo; Ugarte, Martín (Ed.). 18th International Conference on Database Theory, p. 308-323
Series/Report: LIPIcs
Series/Report no.: 31
Abstract: We investigate the class D of queries that distribute over components. These are the queries that can be evaluated by taking the union of the query results over the connected components of the database instance. We show that it is undecidable whether a (positive) Datalog program distributes over components. Additionally, we show that connected Datalog¬ (the fragment of Datalog¬ where all rules are connected) provides an effective syntax for Datalog¬ programs that distribute over components under the stratified as well as under the well-founded semantics. As a corollary, we obtain a simple proof for one of the main results in previous work, namely, that the classic win-move query is in F2 (a particular class of coordination-free queries).
Notes: Ameloot, TJ (reprint author), Hasselt Univ, Hasselt, Belgium tom.ameloot@uhasselt.be; bas.ketsman@uhasselt.be; frank.neven@uhasselt.be; danielqzinn@gmail.com
URI: http://hdl.handle.net/1942/19796
DOI: 10.4230/LIPIcs.ICDT.2015.308
ISI #: 000399803800005
ISBN: 978-3-939897-79-8
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A510.1 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.