{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T06:06:05Z","timestamp":1672553165080},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,2,22]],"date-time":"2017-02-22T00:00:00Z","timestamp":1487721600000},"content-version":"vor","delay-in-days":22,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2017,1,31]]},"abstract":"\n We investigate the class\n \n D<\/jats:bold>\n <\/jats:italic>\n 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\u00ac (the fragment of Datalog\u00ac where all rules are connected) provides an effective syntax for Datalog\u00ac 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\n \n F<\/jats:bold>\n <\/jats:italic>\n 2<\/jats:sub>\n (a particular class of coordination-free queries).\n <\/jats:p>","DOI":"10.1145\/3022743","type":"journal-article","created":{"date-parts":[[2017,2,27]],"date-time":"2017-02-27T13:06:52Z","timestamp":1488200812000},"page":"1-35","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Datalog Queries Distributing over Components"],"prefix":"10.1145","volume":"18","author":[{"given":"Tom J.","family":"Ameloot","sequence":"first","affiliation":[{"name":"Hasselt University 8 transnational University of Limburg"}]},{"given":"Bas","family":"Ketsman","sequence":"additional","affiliation":[{"name":"Hasselt University 8 transnational University of Limburg"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[{"name":"Hasselt University 8 transnational University of Limburg"}]},{"given":"Daniel","family":"Zinn","sequence":"additional","affiliation":[{"name":"LogicBlox, Inc."}]}],"member":"320","published-online":{"date-parts":[[2017,2,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065214"},{"key":"e_1_2_1_2_1","unstructured":"S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley. S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816639"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 18th International Conference on Database Theory. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 308--323","author":"Ameloot T. J.","unstructured":"T. J. Ameloot , B. Ketsman , F. Neven , and D. Zinn . 2015. Datalog queries distributing over components . In Proceedings of the 18th International Conference on Database Theory. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 308--323 . T. J. Ameloot, B. Ketsman, F. Neven, and D. Zinn. 2015. Datalog queries distributing over components. In Proceedings of the 18th International Conference on Database Theory. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 308--323."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2809784"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450151"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3060621.3060752"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2734"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273560"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391230"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_14"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66929"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/788023.789065"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/112198.112224"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860704"},{"key":"e_1_2_1_16_1","volume-title":"ILOG: Declarative creation and manipulation of object identifiers. In VLDB. Morgan Kaufmann, 455--468.","author":"Hull R.","year":"1990","unstructured":"R. Hull and M. Yoshikawa . 1990 . ILOG: Declarative creation and manipulation of object identifiers. In VLDB. Morgan Kaufmann, 455--468. R. Hull and M. Yoshikawa. 1990. ILOG: Declarative creation and manipulation of object identifiers. In VLDB. Morgan Kaufmann, 455--468."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375557"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00153-A"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142485"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(93)90040-N"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90024-Q"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274588"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3022743","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T06:29:06Z","timestamp":1672468146000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3022743"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,31]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1,31]]}},"alternative-id":["10.1145\/3022743"],"URL":"https:\/\/doi.org\/10.1145\/3022743","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,31]]},"assertion":[{"value":"2015-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}