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.
Type de document :
Communication dans un congrès
ICALP (2), Jul 2012, Warwick, United Kingdom. pp.79-91, 2012
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

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

Fichier

benedikt2012monadic.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00809306, version 1

Citation

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

Partager

Métriques

Consultations de la notice

169

Téléchargements de fichiers

103