Walking the Complexity Lines for Generalized Guarded Existential Rules
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.
Cite
Text
Baget et al. "Walking the Complexity Lines for Generalized Guarded Existential Rules." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-126Markdown
[Baget et al. "Walking the Complexity Lines for Generalized Guarded Existential Rules." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/baget2011ijcai-walking/) doi:10.5591/978-1-57735-516-8/IJCAI11-126BibTeX
@inproceedings{baget2011ijcai-walking,
title = {{Walking the Complexity Lines for Generalized Guarded Existential Rules}},
author = {Baget, Jean-François and Mugnier, Marie-Laure and Rudolph, Sebastian and Thomazo, Michaël},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {712-717},
doi = {10.5591/978-1-57735-516-8/IJCAI11-126},
url = {https://mlanthology.org/ijcai/2011/baget2011ijcai-walking/}
}