Monadic Datalog, Tree Validity, and Limited ...
Type de document :
Compte-rendu et recension critique d'ouvrage
DOI :
Titre :
Monadic Datalog, Tree Validity, and Limited Access Containment
Auteur(s) :
Benedikt, Michael [Auteur]
Computing Science Laboratory - Oxford University
Bourhis, Pierre [Auteur]
Self-adaptation for distributed services and large software systems [SPIRALS]
Gottlob, Georg [Auteur]
Computing Science Laboratory - Oxford University
Senellart, Pierre [Auteur]
Value from Data [VALDA ]
Data, Intelligence and Graphs [DIG]
Computing Science Laboratory - Oxford University
Bourhis, Pierre [Auteur]
Self-adaptation for distributed services and large software systems [SPIRALS]
Gottlob, Georg [Auteur]
Computing Science Laboratory - Oxford University
Senellart, Pierre [Auteur]
Value from Data [VALDA ]
Data, Intelligence and Graphs [DIG]
Titre de la revue :
ACM Transactions on Computational Logic
Pagination :
6:1-6:45
Éditeur :
Association for Computing Machinery
Date de publication :
2020
ISSN :
1529-3785
Mot(s)-clé(s) en anglais :
Monadic datalog
Access patterns
Deep Web
Query containment
Binding patterns
Access patterns
Deep Web
Query containment
Binding patterns
Discipline(s) HAL :
Informatique [cs]/Base de données [cs.DB]
Résumé en anglais : [en]
We reconsider the problem of containment of monadic datalog (MDL) queries in unions of conjunctive queries (UCQs). Prior work has dealt with special cases of the problem, but has left the precise complexity characterization ...
Lire la suite >We reconsider the problem of containment of monadic datalog (MDL) queries in unions of conjunctive queries (UCQs). Prior work has dealt with special cases of the problem, but has left the precise complexity characterization open. In addition, the complexity of one important special case, that of containment under access patterns, was not known before. We start by revisiting the connection between MDL/UCQ containment and containment problems involving regular tree languages. We then present a general approach for getting tighter bounds on the complexity of query containment, based on analysis of the number of mappings of queries into tree-like instances. We give two applications of the machinery. We first give an important special case of the MDL/UCQ containment problem that is in EXPTIME, and use this bound to show an EXPTIME bound on containment under access patterns. Secondly we show that the same technique can be used to get a new tight upper bound for containment of tree automata in UCQs. We finally show that the new MDL/UCQ upper bounds are tight. We establish a 2EXPTIME lower bound on the MDL/UCQ containment problem, resolving an open problem from the early 1990s. This bound holds for the MDL/CQ containment problem as well. We also show that changes to the conditions given in our special cases can not be eliminated, and that in particular slight variations of the problem of containment under access patterns become 2EXPTIME-complete.Lire moins >
Lire la suite >We reconsider the problem of containment of monadic datalog (MDL) queries in unions of conjunctive queries (UCQs). Prior work has dealt with special cases of the problem, but has left the precise complexity characterization open. In addition, the complexity of one important special case, that of containment under access patterns, was not known before. We start by revisiting the connection between MDL/UCQ containment and containment problems involving regular tree languages. We then present a general approach for getting tighter bounds on the complexity of query containment, based on analysis of the number of mappings of queries into tree-like instances. We give two applications of the machinery. We first give an important special case of the MDL/UCQ containment problem that is in EXPTIME, and use this bound to show an EXPTIME bound on containment under access patterns. Secondly we show that the same technique can be used to get a new tight upper bound for containment of tree automata in UCQs. We finally show that the new MDL/UCQ upper bounds are tight. We establish a 2EXPTIME lower bound on the MDL/UCQ containment problem, resolving an open problem from the early 1990s. This bound holds for the MDL/CQ containment problem as well. We also show that changes to the conditions given in our special cases can not be eliminated, and that in particular slight variations of the problem of containment under access patterns become 2EXPTIME-complete.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-02307999/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-02307999/document
- Accès libre
- Accéder au document
- https://ora.ox.ac.uk/objects/uuid:4f6fcbe8-61ad-4ac8-bae1-646c1b68db8a/download_file?safe_filename=mdl.pdf&file_format=application%2Fpdf&type_of_work=Journal+article
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-02307999/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- mdl.pdf
- Accès libre
- Accéder au document
- download_file
- Accès libre
- Accéder au document