{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T02:40:41Z","timestamp":1784860841123,"version":"3.55.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,11,2]],"date-time":"2016-11-02T00:00:00Z","timestamp":1478044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Austrian Academy of Sciences under a DOC Fellowship"},{"name":"CPER Nord-Pas de Calais\/FEDER DATA Advanced Data Science and Technologies","award":["2015-2020"],"award-info":[{"award-number":["2015-2020"]}]},{"name":"ANR Aggreg Project","award":["ANR-14-CE25-0017"],"award-info":[{"award-number":["ANR-14-CE25-0017"]}]},{"name":"Vienna University of Technology"},{"name":"Italian Ministry of University and Research","award":["PON03PE_00001_1"],"award-info":[{"award-number":["PON03PE_00001_1"]}]},{"name":"Austrian Science Fund","award":["Y698 and P25207-N23"],"award-info":[{"award-number":["Y698 and P25207-N23"]}]},{"name":"INRIA Northern European Associate Team Integrated Linked Data"},{"name":"Italian Ministry of Economic Development","award":["F\/020016\/01-02\/X27"],"award-info":[{"award-number":["F\/020016\/01-02\/X27"]}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","award":["ICT12-015"],"award-info":[{"award-number":["ICT12-015"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2016,12,23]]},"abstract":"<jats:p>\n            We perform an in-depth complexity analysis of query answering under guarded-based classes of disjunctive tuple-generating dependencies (DTGDs), focusing on (unions of) conjunctive queries ((U)CQs). We show that the problem under investigation is very hard, namely 2E\n            <jats:sc>xp<\/jats:sc>\n            T\n            <jats:sc>ime<\/jats:sc>\n            -complete, even for fixed sets of dependencies of a very restricted form. This is a surprising lower bound that demonstrates the enormous impact of disjunction on query answering under guarded-based tuple-generating dependencies, and also reveals the source of complexity for expressive logics such as the guarded fragment of first-order logic. We then proceed to investigate whether prominent subclasses of (U)CQs (i.e., queries of bounded treewidth and hypertree-width, and acyclic queries) have a positive impact on the complexity of the problem under consideration. We show that queries of bounded treewidth and bounded hypertree-width do not reduce the complexity of our problem, even if we focus on predicates of bounded arity or on fixed sets of DTGDs. Regarding acyclic queries, although the problem remains 2E\n            <jats:sc>xp<\/jats:sc>\n            T\n            <jats:sc>ime<\/jats:sc>\n            -complete in general, in some relevant settings the complexity reduces to E\n            <jats:sc>xp<\/jats:sc>\n            T\n            <jats:sc>ime<\/jats:sc>\n            -complete. Finally, with the aim of identifying tractable cases, we focus our attention on atomic queries. We show that atomic queries do not make the query answering problem easier under classes of guarded-based DTGDs that allow more than one atom to occur in the body of the dependencies. However, the complexity significantly decreases in the case of dependencies that can have only one atom in the body. In particular, we obtain a P\n            <jats:sc>time<\/jats:sc>\n            -completeness if we focus on predicates of bounded arity, and\n            <jats:italic>\n              AC\n              <jats:sub>0<\/jats:sub>\n            <\/jats:italic>\n            -membership when the set of dependencies and the query are fixed. Interestingly, our results can be used as a generic tool for establishing complexity results for query answering under various description logics.\n          <\/jats:p>","DOI":"10.1145\/2976736","type":"journal-article","created":{"date-parts":[[2016,11,4]],"date-time":"2016-11-04T12:49:04Z","timestamp":1478263744000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Guarded-Based Disjunctive Tuple-Generating Dependencies"],"prefix":"10.1145","volume":"41","author":[{"given":"Pierre","family":"Bourhis","sequence":"first","affiliation":[{"name":"CNRS CRIStAL, University of Lille 1 and INRIA Lille"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Manna","sequence":"additional","affiliation":[{"name":"University of Calabria, Rende (CS), Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Morak","sequence":"additional","affiliation":[{"name":"Vienna University of Technology, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Pieris","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Scotland, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,11,2]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068412000257"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004275029985"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1734953.1734954"},{"key":"e_1_2_2_5_1","unstructured":"Franz Baader Diego Calvanese Deborah L. McGuinness Daniele Nardi and Peter F. Patel-Schneider (Eds.). 2003. The Description Logic Handbook: Theory Implementation and Applications. Cambridge University Press.   Franz Baader Diego Calvanese Deborah L. McGuinness Daniele Nardi and Peter F. Patel-Schneider (Eds.). 2003. The Description Logic Handbook: Theory Implementation and Applications. Cambridge University Press."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.03.002"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283516.2283519"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-10(2:3)2014"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2701414"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the 8th International Colloquium on Automata, Languages, and Programming. 73--85","author":"Beeri Catriel"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1636"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 796--802","author":"Bourhis Pierre","year":"2013"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44522-8_9"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning. 70--80","author":"Cal\u00ec Andrea","year":"2008"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2591248.2591252"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2012.03.001"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.27"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.08.002"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-007-9078-x"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.10.003"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90075-8"},{"key":"e_1_2_2_22_1","volume-title":"Logic Programming and Databases","author":"Ceri Stefano"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02088013"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2008.05.001"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376938"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656436"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/4.4.423"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261126"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.02.012"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292615"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366108"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_1"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.2307\/2586808"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90081-3"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283516.2283559"},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning.","author":"Leone Nicola","year":"2012"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71070-7_16"},{"key":"e_1_2_2_41_1","volume-title":"Computational Complexity","author":"Papadimitriou Christos H."},{"key":"e_1_2_2_42_1","volume-title":"inverses, counting, and conjunctive queries or: Why infinity is your friend&excl","author":"Rudolph Sebastian"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00962071"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90078-X"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283516.2283580"},{"key":"e_1_2_2_46_1","volume-title":"Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning.","author":"Thomazo Micha\u00ebl","year":"2012"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/28659.28660"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.212474"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2976736","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2976736","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:16Z","timestamp":1750222576000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2976736"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,2]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12,23]]}},"alternative-id":["10.1145\/2976736"],"URL":"https:\/\/doi.org\/10.1145\/2976736","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,2]]},"assertion":[{"value":"2015-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}