Proceedings Abstracts of the Twenty-Fifth International Joint Conference on Artificial Intelligence

Answering Metaqueries over Hi (OWL 2 QL) Ontologies / 1174
Maurizio Lenzerini, Lorenzo Lepore, Antonella Poggi

Hi(OWL 2 QL) is a new ontology language with the OWL2QL syntax and a specific semantics designed to support metamodeling and meta-querying. In this paper we investigate the problem of answering metaqueries in Hi(OWL 2 QL), which are unions of conjunctive queries with both ABox and TBox atoms. We first focus on a specific class of ontologies, called TBox-complete, where there is no uncertainty about TBox axioms, and show that query answering in this case has the same complexity (both data and combined) as in OWL2QL. We then move to general ontologies and show that answering metaqueries is coNP-complete with respect to ontology complexity, Π2p-complete with respect to combined complexity, and remains AC0 with respect to ABox complexity. Finally, we present an optimized query answering algorithm that can be used for TBox-complete ontologies.