Query Inseparability for Description Logic Knowledge Bases

a signature consisting of concept and role names. We call KBs K1 and K2 Σ-query inseparable and write K1 ≡Σ K2 if any CQ formulated in Σ has the same answers over K1 and K2. Note that even for Σ containing all concept and role names, Σ-query inseparability does not necessarily imply logical equivalence. The relativisation to (smaller) signatures is crucial to support the tasks mentioned above: We investigate conjunctive query inseparability of description logic (DL) knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We study the data and combined complexity of deciding KB query inseparability for fragments of Horn-ALCHI, including the DLs underpinning OWL 2 QL and OWL 2 EL. While all of these DLs are P-complete for data complexity, the combined complexity ranges from P to E XP T IME and 2E XP T IME. We also resolve two major open problems for OWL 2 QL by showing that TBox query inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both E XP T IME-complete for combined complexity. (versioning) When comparing two versions K1 and K2 of a KB with respect to their answers to CQs in a relevant signature Σ, the basic task is to check whether K1 ≡Σ K2. (modularisation) A Σ-module of a KB K is a KB K0 ⊆ K such that K0 ≡Σ K. If we are only interested in answering CQs in Σ over K, then we can achieve our aim by querying any Σ-module of K instead of K itself. (knowledge exchange) In knowledge exchange, we want to transform a KB K1 in a signature Σ1 to a new KB K2 in a disjoint signature Σ2 connected to Σ1 via a declarative mapping specification given by a TBox T12. Thus, the target KB K2 should satisfy the condition K1 ∪ T12 ≡Σ2 K2, in which case it is called a universal UCQ-solution (CQ and UCQ inseparabilities coincide for Horn DLs). (forgetting) A KB K0 results from forgetting a signature Σ in a KB K if K0 ≡sig(K)\Σ K and sig(K0) ⊆ sig(K) \ Σ. Thus, the result of forgetting Σ does not use Σ and gives the same answers to CQs without symbols in Σ as K.

Authors

• Elena Botoeva
• Roman Kontchakov
• Vladislav Ryzhikov
• Frank Wolter
• Michael Zakharyaschev

Keywords

No keywords are indexed for this paper.