---
title: "Walking the Complexity Lines for Generalized Guarded Existential Rules"
authors:
  - "Jean-François Baget"
  - "Marie-Laure Mugnier"
  - "Sebastian Rudolph"
  - "Michaël Thomazo"
doi: "10.5591/978-1-57735-516-8/IJCAI11-126"
url: "https://ijcai.org/proceedings/2011/126"
pdf: "https://ijcai.org/proceedings/2011/0126.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "712-716"
track: ""
keywords:
---

# Walking the Complexity Lines for Generalized Guarded Existential Rules

Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph, Michaël Thomazo

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 712-716. DOI: [10.5591/978-1-57735-516-8/IJCAI11-126](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-126)

## Abstract

We establish complexities of the conjunctive query entailment problem for classes of existential rules (i.e. Tuple-Generating Dependencies or Datalog+/- rules). Our contribution is twofold. First, we introduce the class of greedy bounded treewidth sets (gbts), which covers guarded rules, and their known generalizations, namely (weakly) frontier-guarded rules. We provide a generic algorithm for query entailment with gbts, which is worst-case optimal for combined complexity with bounded predicate arity, as well as for data complexity. Second, we classify several gbts classes, whose complexity was unknown, namely frontier-one, frontier-guarded and weakly frontier-guarded rules, with respect to combined complexity (with bounded and unbounded predicate arity) and data complexity.