Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Inria Links Connect in order to contact the contributor
Submitted on : Tuesday, December 30, 2014 - 12:04:37 PM
Last modification on : Thursday, January 20, 2022 - 5:30:44 PM
Long-term archiving on: : Tuesday, March 31, 2015 - 10:16:27 AM


Files produced by the author(s)


  • HAL Id : hal-01098974, version 1


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



Record views


Files downloads