Skip to main content

Computing Solutions in OWL 2 QL Knowledge Base Exchange

Arenas, Marcelo, Botoeva, Elena, Calvanese, Diego, Ryzhikov, Vladislav (2013) Computing Solutions in OWL 2 QL Knowledge Base Exchange. In: CEUR Workshop Proceedings. Informal Proceedings of the 26th International Workshop on Description Logics, Ulm, Germany, July 23 - 26, 2013. 1014. pp. 4-16. (KAR id:91306)

PDF Publisher pdf
Language: English

Download (442kB) Preview
[thumbnail of paper_87.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL:


The problem of exchanging knowledge bases from a source signature to a target signature connected through a mapping has recently attracted attention 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 the membership problem.

Item Type: Conference or workshop item (Proceeding)
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Amy Boaler
Date Deposited: 03 Nov 2021 14:56 UTC
Last Modified: 16 Nov 2021 10:27 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year