Query Containment for Highly Expressive Datalog Fragments

Abstract : The containment problem of Datalog queries is well known to be undecidable. There are, however, several Datalog frag-ments for which containment is known to be decidable, most notably monadic Datalog and several "regular" query lan-guages on graphs. Monadically Defined Queries (MQs) have been introduced recently as a joint generalization of these query languages. In this paper, we study a wide range of Datalog frag-ments with decidable query containment and determine ex-act complexity results for this problem. We generalize MQs to (Frontier-)Guarded Queries (GQs), and show that the con-tainment problem is 3ExpTime-complete in either case, even if we allow arbitrary Datalog in the sub-query. If we focus on graph query languages, i.e., fragments of linear Datalog, then this complexity is reduced to 2ExpSpace. We also con-sider nested queries, which gain further expressivity by us-ing predicates that are defined by inner queries. We show that nesting leads to an exponentially increasing hierarchy for the complexity of query containment, both in the linear and in the general case. Our results settle open problems for (nested) MQs, and they paint a comprehensive picture of the state of the art in Datalog query containment.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

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

Contributeur : Inria Links <>
Soumis le : mardi 30 décembre 2014 - 12:04:37
Dernière modification le : vendredi 27 avril 2018 - 13:54:02
Document(s) archivé(s) le : mardi 31 mars 2015 - 10:16:27


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01098974, version 1


Pierre Bourhis, Markus Krötzsch, Sebastian Rudolph. Query Containment for Highly Expressive Datalog Fragments. 2014. 〈hal-01098974〉



Consultations de la notice


Téléchargements de fichiers