Datalog queries distributing over components

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

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

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 [Zinn et al. 2012], namely that the classic win-move query is in F2 (a particular class of coordination-free queries).

Original languageEnglish
Article number5
Pages (from-to)1-35
JournalACM Transactions on Computational Logic
Volume18
Issue number1
DOIs
Publication statusPublished - Feb 2017

Keywords

  • Coordination-free evaluation
  • Datalog
  • Distributed databases
  • Stratified semantics
  • Well-founded semantics

Fingerprint

Dive into the research topics of 'Datalog queries distributing over components'. Together they form a unique fingerprint.

Cite this