Hi(OWL 2 QL) is a new ontology language with the OWL2QL syntax and a specific semantics designed to support metamodeling and metaquerying. 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 OWL 2 QL. 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.

Answering metaqueries over Hi(OWL 2 QL) ontologies / Lenzerini, Maurizio; Lepore, Lorenzo; Poggi, Antonella. - In: IJCAI. - ISSN 1045-0823. - ELETTRONICO. - (2016), pp. 1174-1180. (Intervento presentato al convegno 25th International Joint Conference on Artificial Intelligence (IJCAI 2016) tenutosi a New York; USA nel 9–15 July 2016).

Answering metaqueries over Hi(OWL 2 QL) ontologies

LENZERINI, Maurizio;LEPORE, LORENZO;POGGI, Antonella
2016

Abstract

Hi(OWL 2 QL) is a new ontology language with the OWL2QL syntax and a specific semantics designed to support metamodeling and metaquerying. 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 OWL 2 QL. 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.
2016
25th International Joint Conference on Artificial Intelligence (IJCAI 2016)
Combined complexity; Conjunctive queries; Meta-querying; Metamodeling; Ontology language; Query answering; Specific class; Specific semantics;
04 Pubblicazione in atti di convegno::04c Atto di convegno in rivista
Answering metaqueries over Hi(OWL 2 QL) ontologies / Lenzerini, Maurizio; Lepore, Lorenzo; Poggi, Antonella. - In: IJCAI. - ISSN 1045-0823. - ELETTRONICO. - (2016), pp. 1174-1180. (Intervento presentato al convegno 25th International Joint Conference on Artificial Intelligence (IJCAI 2016) tenutosi a New York; USA nel 9–15 July 2016).
File allegati a questo prodotto
File Dimensione Formato  
Lenzerini_Answering-metaqueries-over_2016.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 685.91 kB
Formato Adobe PDF
685.91 kB Adobe PDF
Lenzerini_Frontespizio-indice_Answering-metaqueries-over_2016.pdf

accesso aperto

Tipologia: Altro materiale allegato
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.04 MB
Formato Adobe PDF
2.04 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/870751
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? ND
social impact