Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 1330-1336.
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.
@inproceedings{ijcai2016p192,
title = {Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering},
author = {Zhang, Heng and Zhang, Yan and You, Jia-Huai},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {1330--1336},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/192},
}
TY - CPAPER TI - Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering AU - Zhang, Heng AU - Zhang, Yan AU - You, Jia-Huai T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 1330 EP - 1336 UR - https://ijcai.org/proceedings/2016/192 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
