Proc. of the 26th Int. Workshop on Description Logics (DL 2013). Volume 1014 of CEUR Workshop Proceedings, https://ceur-ws.org/. 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 2013)", pages = "4--16", volume = "1014", publisher = "CEUR-WS.org", series = "CEUR Workshop Proceedings, https://ceur-ws.org/", }pdf url