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. AAAI Press 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:	17 Aug 2022 11:02 UTC
Resource URI:	https://kar.kent.ac.uk/id/eprint/91290 (The current URI for this page, for reference purposes)

Depositors only (login required):