Polynomial Rewritings for Linear Existential Rules
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 2992-2997.
Abstract
We consider the scenario of ontology-based query answering. It is generally accepted that true scalability in this setting can only be achieved via query rewriting, which in turn allows for the exploitation of standard RDBMSs. In this work, we close two open fundamental questions related to query rewriting. We establish that linear existential rules are polynomially combined rewritable, while full linear rules are polynomially (purely) rewritable; in both cases, the target query language consists of first-order or non-recursive Datalog queries. An immediate consequence of our results is that DLR-Lite_R, the extension of DL-Lite_R with n-ary roles, is polynomially combined rewritable.
@inproceedings{ijcai2015p423,
title = {Polynomial Rewritings for Linear Existential Rules},
author = {Gottlob, Georg and Manna, Marco and Pieris, Andreas},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {2992--2997},
year = {2015},
month = {7},
note = {Special Track on Knowledge Representation and Reasoning},
url = {https://ijcai.org/proceedings/2015/423},
}
TY - CPAPER TI - Polynomial Rewritings for Linear Existential Rules AU - Gottlob, Georg AU - Manna, Marco AU - Pieris, Andreas T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 2992 EP - 2997 UR - https://ijcai.org/proceedings/2015/423 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
