2026-07-21T19:38:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4992 2024-03-06T10:35:40Z ddc:004 open_access

Datalog Queries Distributing over Components Ameloot, Tom J. Ketsman, Bas Neven, Frank Zinn, Daniel Datalog stratified semantics well-founded semantics coordination-free evaluation distributed databases 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tom J. Ameloot and Bas Ketsman and Frank Neven and Daniel Zinn 2015 Is Part Of LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2015.308 urn:nbn:de:0030-drops-49920 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.308 eng https://creativecommons.org/licenses/by/3.0/legalcode