Skip to Main content Skip to Navigation
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 metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-00809306
Contributor : Émilien Antoine <>
Submitted on : Monday, April 8, 2013 - 8:46:17 PM
Last modification on : Friday, July 31, 2020 - 10:44:05 AM
Long-term archiving on: : Monday, April 3, 2017 - 2:33:47 AM

File

benedikt2012monadic.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00809306, version 1

Collections

Citation

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

Share

Metrics

Record views

221

Files downloads

281