Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering
Abstract
Existential rules, also known as data dependencies in Databases, have been recently rediscovered as a promising family of languages for Ontology-based Query Answering. In this paper, we prove that disjunctive embedded dependencies exactly capture the class of recursively enumerable ontologies in Ontology-based Conjunctive Query Answering (OCQA). Our expressive completeness result does not rely on any built-in linear order on the database. To establish the expressive completeness, we introduce a novel semantic definition for OCQA ontologies. We also show that neither the class of disjunctive tuple-generating dependencies nor the class of embedded dependencies is expressively complete for recursively enumerable OCQA ontologies. PDF
Cite
Text
Zhang et al. "Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering." International Joint Conference on Artificial Intelligence, 2016.Markdown
[Zhang et al. "Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/zhang2016ijcai-expressive/)BibTeX
@inproceedings{zhang2016ijcai-expressive,
title = {{Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering}},
author = {Zhang, Heng and Zhang, Yan and You, Jia-Huai},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2016},
pages = {1330-1337},
url = {https://mlanthology.org/ijcai/2016/zhang2016ijcai-expressive/}
}