License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2015.308
URN: urn:nbn:de:0030-drops-49920
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4992/
Go to the corresponding LIPIcs Volume Portal

Ameloot, Tom J. ; Ketsman, Bas ; Neven, Frank ; Zinn, Daniel

Datalog Queries Distributing over Components

pdf-format:
19.pdf (0.5 MB)

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 with Negation (the fragment of Datalog with Negation where all rules are connected) provides an effective syntax for Datalog with Negation 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 [Zinn, Green, and Ludäscher, ICDT2012], namely, that the classic win-move query is in F_2 (a particular class of coordination-free queries).

BibTeX - Entry

@InProceedings{ameloot_et_al:LIPIcs:2015:4992,
  author =	{Tom J. Ameloot and Bas Ketsman and Frank Neven and Daniel Zinn},
  title =	{{Datalog Queries Distributing over Components}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{308--323},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Marcelo Arenas and Mart{\'i}n Ugarte},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4992},
  URN =		{urn:nbn:de:0030-drops-49920},
  doi =		{10.4230/LIPIcs.ICDT.2015.308},
  annote =	{Keywords: Datalog, stratified semantics, well-founded semantics, coordination-free evaluation, distributed databases}
}

Keywords: Datalog, stratified semantics, well-founded semantics, coordination-free evaluation, distributed databases
Collection: 18th International Conference on Database Theory (ICDT 2015)
Issue Date: 2015
Date of publication: 19.03.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI