Skip to Main content Skip to Navigation
New interface
Conference papers

Monadic Datalog Containment

Abstract : We reconsider the problem of containment of monadic data- log (MDL) queries in unions of conjunctive queries (UCQs). Prior work has dealt with special cases, but has left the precise complexity character- ization open. We begin by establishing a 2EXPTIME lower bound on the MDL/UCQ containment problem, resolving an open problem from the early 90's. We then present a general approach for getting tighter bounds on the complexity, based on analysis of the number of mappings of queries into tree-like instances. We use the machinery to present an important case of the MDL/UCQ containment problem that is in co-NEXPTIME, and a case that is in EXPTIME. We then show that the technique can be used to get a new tight upper bound for containment of tree automata in UCQs. We show that the new MDL/UCQ upper bounds are tight.
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Émilien Antoine Connect in order to contact the contributor
Submitted on : Monday, April 8, 2013 - 8:46:17 PM
Last modification on : Tuesday, November 24, 2020 - 11:00:14 AM
Long-term archiving on: : Monday, April 3, 2017 - 2:33:47 AM


Files produced by the author(s)


  • HAL Id : hal-00809306, version 1



Michael Benedikt, Pierre Bourhis, Pierre Senellart. Monadic Datalog Containment. ICALP (2), Jul 2012, Warwick, United Kingdom. pp.79-91. ⟨hal-00809306⟩



Record views


Files downloads