{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:08Z","timestamp":1750220888698,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T00:00:00Z","timestamp":1570147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M005852\/1"],"award-info":[{"award-number":["EP\/M005852\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"<jats:p>We reconsider the problem of containment of monadic datalog (MDL) queries in unions of conjunctive queries (UCQs). Prior work has dealt with special cases of the problem but has left the precise complexity characterization open. In addition, the complexity of one important special case, that of containment under access patterns, was not known before. We start by revisiting the connection between MDL\/UCQ containment and containment problems involving regular tree languages. We then present a general approach for getting tighter bounds on the complexity of query containment, based on analysis of the number of mappings of queries into tree-like instances. We give two applications of the machinery. We first give an important special case of the MDL\/UCQ containment problem that is in EXPTIME, and we use this bound to show an EXPTIME bound on containment under access patterns. Second, we show that the same technique can be used to get a new tight upper bound for containment of tree automata in UCQs. We finally show that the new MDL\/UCQ upper bounds are tight. We establish a 2EXPTIME lower bound on the MDL\/UCQ containment problem, resolving an open problem from the early 1990s. This bound holds for the MDL\/CQ containment problem as well. We also show that changes to the conditions given in our special cases can not be eliminated, and that in particular slight variations of the problem of containment under access patterns become 2EXPTIME-complete.<\/jats:p>","DOI":"10.1145\/3344514","type":"journal-article","created":{"date-parts":[[2019,10,7]],"date-time":"2019-10-07T12:20:59Z","timestamp":1570450859000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Monadic Datalog, Tree Validity, and Limited Access Containment"],"prefix":"10.1145","volume":"21","author":[{"given":"Michael","family":"Benedikt","sequence":"first","affiliation":[{"name":"The University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Bourhis","sequence":"additional","affiliation":[{"name":"CRIStAL, CNRS, University of Lille 8 Inria, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[{"name":"The University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Senellart","sequence":"additional","affiliation":[{"name":"DI ENS, ENS, CNRS, PSL University 8 Inria 8 LTCI, T\u00e9l\u00e9com Paris, IP Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,10,4]]},"reference":[{"volume-title":"Foundations of Databases","author":"Abiteboul Serge","key":"e_1_2_1_1_1","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Pearson , London . Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Pearson, London."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Antoine Amarilli Pierre Bourhis and Pierre Senellart. 2015. Provenance Circuits for Trees and Treelike Instances (Extended Version). CoRR abs\/1511.08723.  Antoine Amarilli Pierre Bourhis and Pierre Senellart. 2015. Provenance Circuits for Trees and Treelike Instances (Extended Version). CoRR abs\/1511.08723.","DOI":"10.1007\/978-3-662-47666-6_5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699500"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_11"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989309"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.36"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85238-4_10"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_17"},{"key":"e_1_2_1_9_1","volume-title":"Conjunctive query containment over trees using schema information. Acta Informatica","author":"Bj\u00f6rklund Henrik","year":"2016","unstructured":"Henrik Bj\u00f6rklund , Wim Martens , and Thomas Schwentick . 2016. Conjunctive query containment over trees using schema information. Acta Informatica ( 2016 ). Henrik Bj\u00f6rklund, Wim Martens, and Thomas Schwentick. 2016. Conjunctive query containment over trees using schema information. Acta Informatica (2016)."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the PODS.","author":"Bonatti Piero A.","year":"2004","unstructured":"Piero A. Bonatti . 2004 . On the decidability of containment of recursive datalog queries . In Proceedings of the PODS. Piero A. Bonatti. 2004. On the decidability of containment of recursive datalog queries. In Proceedings of the PODS."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the SEBD.","author":"Cal\u00ec Andrea","year":"2006","unstructured":"Andrea Cal\u00ec and Diego Calvanese . 2006 . Containment of conjunctive queries under access limitations . In Proceedings of the SEBD. Andrea Cal\u00ec and Diego Calvanese. 2006. Containment of conjunctive queries under access limitations. In Proceedings of the SEBD."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87877-3_24"},{"key":"e_1_2_1_13_1","volume-title":"Giuseppe De Giacomo, and Moshe Y. Vardi","author":"Calvanese Diego","year":"2005","unstructured":"Diego Calvanese , Giuseppe De Giacomo, and Moshe Y. Vardi . 2005 . Decidable containment of recursive queries. Theoret. Comput. Sci . 336, 1 (2005). Diego Calvanese, Giuseppe De Giacomo, and Moshe Y. Vardi. 2005. Decidable containment of recursive queries. Theoret. Comput. Sci. 336, 1 (2005)."},{"key":"e_1_2_1_14_1","volume-title":"Maurizio Lenzerini, and Moshe Y. Vardi.","author":"Calvanese Diego","year":"2000","unstructured":"Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, and Moshe Y. Vardi. 2000 . Containment of conjunctive regular path queries with inverse. In Proceedings of the KR. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2000. Containment of conjunctive regular path queries with inverse. In Proceedings of the KR."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"e_1_2_1_16_1","volume-title":"Vardi","author":"Chaudhuri Surajit","year":"1992","unstructured":"Surajit Chaudhuri and Moshe Y . Vardi . 1992 . On the equivalence of recursive and nonrecursive datalog programs. In Proceedings of the PODS. Surajit Chaudhuri and Moshe Y. Vardi. 1992. On the equivalence of recursive and nonrecursive datalog programs. In Proceedings of the PODS."},{"key":"e_1_2_1_17_1","volume-title":"Vardi","author":"Chaudhuri Surajit","year":"1994","unstructured":"Surajit Chaudhuri and Moshe Y . Vardi . 1994 . On the complexity of equivalence between recursive and nonrecursive datalog programs. In Proceedings of the PODS. Surajit Chaudhuri and Moshe Y. Vardi. 1994. On the complexity of equivalence between recursive and nonrecursive datalog programs. In Proceedings of the PODS."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1452"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/9118.9125"},{"key":"e_1_2_1_20_1","unstructured":"Hubert Comon Max Dauchet R\u00e9mi Gilleron Florent Jacquemard Denis Lugiez Sophie Tison and Marc Tommasi. 2002. Tree Automata Techniques and Applications. Retrieved from http:\/\/www.grappa.univ-lille3.fr\/tata\/.  Hubert Comon Max Dauchet R\u00e9mi Gilleron Florent Jacquemard Denis Lugiez Sophie Tison and Marc Tommasi. 2002. Tree Automata Techniques and Applications. Retrieved from http:\/\/www.grappa.univ-lille3.fr\/tata\/."},{"key":"e_1_2_1_21_1","volume-title":"Vardi","author":"Cosmadakis Stavros S.","year":"1988","unstructured":"Stavros S. Cosmadakis , Haim Gaifman , Paris C. Kanellakis , and Moshe Y . Vardi . 1988 . Decidable optimization problems for database logic programs. In Proceedings of the STOC. Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, and Moshe Y. Vardi. 1988. Decidable optimization problems for database logic programs. In Proceedings of the STOC."},{"key":"e_1_2_1_22_1","volume-title":"Recursive queries and context-free graph grammars. Theoret. Comput. Sci. 78, 1","author":"Courcelle Bruno","year":"1991","unstructured":"Bruno Courcelle . 1991. Recursive queries and context-free graph grammars. Theoret. Comput. Sci. 78, 1 ( 1991 ). Bruno Courcelle. 1991. Recursive queries and context-free graph grammars. Theoret. Comput. Sci. 78, 1 (1991)."},{"key":"e_1_2_1_23_1","volume-title":"Levy","author":"Duschka Oliver M.","year":"1997","unstructured":"Oliver M. Duschka and Alon Y . Levy . 1997 . Recursive plans for information gathering. In Proceedings of the IJCAI. Oliver M. Duschka and Alon Y. Levy. 1997. Recursive plans for information gathering. In Proceedings of the IJCAI."},{"volume-title":"Handbook of Formal Languages","author":"G\u00e9cseg Ferenc","key":"e_1_2_1_24_1","unstructured":"Ferenc G\u00e9cseg and Magnus Steinby . 1997. \u201c Tree languages .\u201d In Handbook of Formal Languages , G. Rozenberg and A. Salomaa (Eds.). Vol. 3 . Springer Verlag , 1\u201368. Ferenc G\u00e9cseg and Magnus Steinby. 1997. \u201cTree languages.\u201d In Handbook of Formal Languages, G. Rozenberg and A. Salomaa (Eds.). Vol. 3. Springer Verlag, 1\u201368."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/502030.502032"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00028-4"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601869"},{"key":"e_1_2_1_28_1","volume-title":"Ullman","author":"Rajaraman Anand","year":"1995","unstructured":"Anand Rajaraman , Yehoshua Sagiv , and Jeffrey D . Ullman . 1995 . Answering queries using templates with binding patterns. In Proceedings of the PODS. Anand Rajaraman, Yehoshua Sagiv, and Jeffrey D. Ullman. 1995. Answering queries using templates with binding patterns. In Proceedings of the PODS."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(93)90040-N"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(75)90058-3"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the STACS.","author":"Cate Balder","year":"2011","unstructured":"Balder ten Cate and Luc Segoufin . 2011 . Unary negation . In Proceedings of the STACS. Balder ten Cate and Luc Segoufin. 2011. Unary negation. In Proceedings of the STACS."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3344514","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3344514","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:25Z","timestamp":1750203865000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3344514"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,4]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3344514"],"URL":"https:\/\/doi.org\/10.1145\/3344514","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2019,10,4]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}