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.
Type de document :
Communication dans un congrès
ICALP (2), Jul 2012, Warwick, United Kingdom. pp.79-91, 2012
https://hal.inria.fr/hal-00809306
Contributeur : Émilien Antoine
<>
Soumis le : lundi 8 avril 2013 - 20:46:17
Dernière modification le : samedi 3 mars 2018 - 15:12:01
Document(s) archivé(s) le : lundi 3 avril 2017 - 02:33:47
Michael Benedikt, Pierre Bourhis, Pierre Senellart. Monadic Datalog Containment. ICALP (2), Jul 2012, Warwick, United Kingdom. pp.79-91, 2012. 〈hal-00809306〉
