Exchanging OWL 2 QL Knowledge Bases
This addresses a fundamental issue in data exchange and knowledge representation for OWL 2 QL users, but it is incremental as it builds on existing work in description logics.
The paper tackles the problem of knowledge base exchange for OWL 2 QL, focusing on computing universal solutions and UCQ-representations, with complexity results ranging from NP to EXPTIME and NLOGSPACE-completeness.
Knowledge base exchange is an important problem in the area of data exchange and knowledge representation, where one is interested in exchanging information between a source and a target knowledge base connected through a mapping. In this paper, we study this fundamental problem for knowledge bases and mappings expressed in OWL 2 QL, the profile of OWL 2 based on the description logic DL-Lite_R. More specifically, we consider the problem of computing universal solutions, identified as one of the most desirable translations to be materialized, and the problem of computing UCQ-representations, which optimally capture in a target TBox the information that can be extracted from a source TBox and a mapping by means of unions of conjunctive queries. For the former we provide a novel automata-theoretic technique, and complexity results that range from NP to EXPTIME, while for the latter we show NLOGSPACE-completeness.