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: | 05 Nov 2024 12:56 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: |
 https://orcid.org/0000-0001-5881-0258
|
|---|---|
| CReDIT Contributor Roles: |
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):
Download Statistics
Download Statistics
