Monadic Datalog Containment
We reconsider the problem of containment of monadic datalog (MDL) queries in unions of conjunctive queries (UCQs). Prior work has dealt with special cases, but has left the precise complexity characterization open. We begin by establishing a 2EXPTIME lower bound on the MDL/UCQ containment problem, r...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2012
|
| _version_ | 1797067205026775040 |
|---|---|
| author | Benedikt, M Bourhis, P Senellart, P |
| author_facet | Benedikt, M Bourhis, P Senellart, P |
| author_sort | Benedikt, M |
| collection | OXFORD |
| description | We reconsider the problem of containment of monadic datalog (MDL) queries in unions of conjunctive queries (UCQs). Prior work has dealt with special cases, but has left the precise complexity characterization 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. © 2012 Springer-Verlag Berlin Heidelberg. |
| first_indexed | 2024-03-06T21:53:02Z |
| format | Journal article |
| id | oxford-uuid:4bf6f691-7680-4290-807e-2cb0bf66a90a |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T21:53:02Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:4bf6f691-7680-4290-807e-2cb0bf66a90a2022-03-26T15:46:37ZMonadic Datalog ContainmentJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:4bf6f691-7680-4290-807e-2cb0bf66a90aEnglishSymplectic Elements at Oxford2012Benedikt, MBourhis, PSenellart, PWe reconsider the problem of containment of monadic datalog (MDL) queries in unions of conjunctive queries (UCQs). Prior work has dealt with special cases, but has left the precise complexity characterization 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. © 2012 Springer-Verlag Berlin Heidelberg. |
| spellingShingle | Benedikt, M Bourhis, P Senellart, P Monadic Datalog Containment |
| title | Monadic Datalog Containment |
| title_full | Monadic Datalog Containment |
| title_fullStr | Monadic Datalog Containment |
| title_full_unstemmed | Monadic Datalog Containment |
| title_short | Monadic Datalog Containment |
| title_sort | monadic datalog containment |
| work_keys_str_mv | AT benediktm monadicdatalogcontainment AT bourhisp monadicdatalogcontainment AT senellartp monadicdatalogcontainment |