Computing Solutions in OWL 2 QL Knowledge Base Exchange

Marcelo Arenas, Elena Botoeva, Diego Calvanese, and Vladislav Ryzhikov

Proc. of the 26th Int. Workshop on Description Logics (DL 2013). 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.

   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 2013)",
   pages = "4--16",
   volume = "1014",
   series = "CEUR Workshop Proceedings,",
pdf url