Abstract
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.