< Back to previous page

Publication

Datalog Queries Distributing over Components

Journal Contribution - Journal Article

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).
Journal: ACM Transactions on Computational Logic
ISSN: 1529-3785
Issue: 1
Volume: 18
Pages: 1 - 35
Publication year:2017
Keywords:datalog, stratified semantics, well-founded semantics, coordination-free evaluation, distributed databases
BOF-keylabel:yes
IOF-keylabel:yes
BOF-publication weight:0.1
CSS-citation score:1
Authors:International
Authors from:Higher Education
Accessibility:Closed