Computing Solutions in OWL 2 QL Knowledge Base Exchange

Proc. of the 26th Int. Workshop on Description Logics (DL). Volume 1014 of CEUR Workshop Proceedings. 2013.

The problem of exchanging knowledge bases from a source signature to a target signature connected through a mapping has attracted attention recently in knowledge representation. In this paper, we study this problem for knowledge bases and mappings expressed in OWL 2 QL, one of the profiles of the standard Web Ontology Language OWL 2. More specifically, we consider the membership and non-emptiness problems associated with computing universal solutions, which have been identified as one of the most desirable translations to be materialized. We study two settings: when ABoxes are in OWL 2 QL and when null values are allowed in the ABox language. For the former case, we provide a novel technique based on reachability games on graphs to show that the non-emptiness and membership problems are in PTime. For the latter case, we report a range of complexity results from NP to ExpTime. We also consider the problem of computing universal UCQ-solutions, which provide an alternative notion of translation containing sufficient information to properly answer union of conjunctive queries, reporting a PSpace lower bound for membership in this case.

@inproceedings{DL-2013-kb-exchange,
   title = "Computing Solutions in OWL 2 QL Knowledge Base Exchange",
   year = "2013",
   author = "Marcelo Arenas and Elena Botoeva and Diego Calvanese and
Vladislav Ryzhikov",
   booktitle = "Proc. of the 26th Int. Workshop on Description Logics (DL)",
   pages = "4--16",
   volume = "1014",
   publisher = "https://ceur-ws.org/CEUR-WS.org",
   series = "CEUR Workshop Proceedings",
}