| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [18 references]
https://hal.inria.fr/hal-00809306
Contributor : Émilien Antoine <>
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
Contributor : Émilien Antoine <>
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
File
benedikt2012monadic.pdf
Files produced by the author(s)