Skip to main content
Kent Academic Repository

Query Inseparability for Description Logic Knowledge Bases

Botoeva, Elena, Kontchakov, Roman, Ryzhikov, Vladislav, Wolter, Frank, Zakharyaschev, Michael (2014) Query Inseparability for Description Logic Knowledge Bases. In: Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning. . pp. 238-247. Association for the Advancement of Artificial Intelligence ISBN 978-1-57735-657-8. (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:91290)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided.
Official URL:
http://www.aaai.org/ocs/index.php/KR/KR14/paper/vi...

Abstract

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 OWL2QL and OWL 2 EL. While all of these DLs are P-complete for data complexity, the combined complexity ranges from P to EXPTIME and 2EXPTIME. We also resolve two major open problems for OWL2QL by showing that TBox query inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both EXPTIME-complete for combined complexity.

Item Type: Conference or workshop item (Proceeding)
Uncontrolled keywords: Theory of computation; Logic
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 11:25 UTC
Last Modified: 10 Oct 2023 12:00 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/91290 (The current URI for this page, for reference purposes)

University of Kent Author Information

Botoeva, Elena.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.