Query Inseparability for Description Logic Knowledge Bases

Botoeva, E, Kontchakov, R, Ryzhikov, V, Wolter, F and Zakharyaschev, M (2014) Query Inseparability for Description Logic Knowledge Bases. .

Text
query-insep14.pdf - Published version
Download (605kB)

Official URL: http://www.aaai.org/Library/KR/kr14contents.php

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 OWL2 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 (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	24 Jul 2015 09:33
Last Modified:	15 Dec 2022 10:10
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/2016103