Existential Rule Languages with Finite Chase: Complexity and Expressiveness

Authors

  • Heng Zhang University of Western Sydney
  • Yan Zhang University of Western Sydney
  • Jia-Huai You University of Alberta

DOI:

https://doi.org/10.1609/aaai.v29i1.9404

Keywords:

existential rules, finite chase, complexity, expressiveness, succinctness

Abstract

Finite chase, or alternatively chase termination, is an important condition to ensure the decidability of existential rule languages. In the past few years, a number of rule languages with finite chase have been studied. In this work, we propose a novel approach for classifying the rule languages with finite chase. Using this approach, a family of decidable rule languages, which extend the existing languages with the finite chase property, are naturally defined. We then study the complexity of these languages. Although all of them are tractable for data complexity, we show that their combined complexity can be arbitrarily high. Furthermore, we prove that all the rule languages with finite chase that extend the weakly acyclic language are of the same expressiveness as the weakly acyclic one, while rule languages with higher combined complexity are in general more succinct than those with lower combined complexity.

Downloads

Published

2015-02-18

How to Cite

Zhang, H., Zhang, Y., & You, J.-H. (2015). Existential Rule Languages with Finite Chase: Complexity and Expressiveness. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9404

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning