Enhancing Existential Rules by Closed-World Variables

Enhancing Existential Rules by Closed-World Variables

Giovanni Amendola, Nicola Leone, Marco Manna, Pierfrancesco Veltri

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1676-1682. https://doi.org/10.24963/ijcai.2018/232

Existential rules generalize Datalog with existential quantification in the head. Natively, Datalog is interpreted under a closed-world semantics, while existential rules typically employ the open-world assumption. The interpretation domain in the latter case is enlarged by infinitely many "anonymous" individuals. Then, in any rule, each variable ranges over all individuals, even if not needed or required. In this paper, we enhance existential rules by closed-world variables to consciously reason on the properties of "known" (non-anonymous) and arbitrary individuals in different ways. Accordingly, we uniformly generalize the basic classes of existential rules that ensure decidability of ontology-based query answering. For them, after observing that decidability is preserved, we prove that a strict increase in expressiveness is gained, and in most cases the computational complexity is not altered.
Keywords:
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Knowledge Representation and Reasoning: Knowledge Representation Languages
Knowledge Representation and Reasoning: Logics for Knowledge Representation
Multidisciplinary Topics and Applications: Intelligent Database Systems