First-Order Rewritability of Atomic Queries in Horn Description Logics
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 754-759.
Abstract
One of the most advanced approaches to querying data in the presence of ontologies is to make use of relational database systems, rewriting the original query and the ontology into a new query that is formulated in SQL or, equivalently, in first-order logic (FO). For ontologies written in many standard description logics (DLs), however, such FO-rewritings are not guaranteed to exist. We study FO-rewritings and their existence for a basic class of queries and for ontologies formulated in Horn DLs such as Horn-SHI and EL. Our results include characterizations of the existence of FO-rewritings, tight complexity bounds for deciding whether an FO-rewriting exists (ExpTime and PSpace), and tight bounds on the (worst-case) size of FO-rewritings, when presented as a union of conjunctive queries.
@inproceedings{ijcai2013p118,
title = {First-Order Rewritability of Atomic Queries in Horn Description Logics},
author = {Bienvenu, Meghyn and Lutz, Carsten and Wolter, Frank},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {754--759},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/118},
}
TY - CPAPER TI - First-Order Rewritability of Atomic Queries in Horn Description Logics AU - Bienvenu, Meghyn AU - Lutz, Carsten AU - Wolter, Frank T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 754 EP - 759 UR - https://ijcai.org/proceedings/2013/118 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
