Tractable Queries for Lightweight Description Logics
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 768-773.
Abstract
It is a classic result in database theory that conjunctive query (CQ) answering, which is NP-complete in general, is feasible in polynomial time when restricted to acyclic queries. Subsequent results identified more general structural properties of CQs (like bounded treewidth) which ensure tractable query evaluation. In this paper, we lift these tractability results to knowledge bases formulated in the lightweight description logics DL-Lite and ELH. The proof exploits known properties of query matches in these logics and involves a query-dependent modification of the data. To obtain a more practical approach, we propose a concrete polynomial-time algorithm for answering acyclic CQs based on rewriting queries into datalog programs. A preliminary evaluation suggests the interest of our approach for handling large acyclic CQs.
@inproceedings{ijcai2013p120,
title = {Tractable Queries for Lightweight Description Logics},
author = {Bienvenu, Meghyn and Ortiz, Magdalena and Simkus, Mantas and Xiao, Guohui},
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 = {768--773},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/120},
}
TY - CPAPER TI - Tractable Queries for Lightweight Description Logics AU - Bienvenu, Meghyn AU - Ortiz, Magdalena AU - Simkus, Mantas AU - Xiao, Guohui 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 - 768 EP - 773 UR - https://ijcai.org/proceedings/2013/120 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
