Skip to main content

Query Inseparability by Games

Botoeva, Elena, Kontchakov, Roman, Ryzhikov, Vladislav, Wolter, Frank, Zakharyaschev, Michael (2014) Query Inseparability by Games. In: CEUR Workshop Proceedings. Informal Proceedings of the 27th International Workshop on Description Logics, Vienna, Austria, July 17-20, 2014. 1193. pp. 83-95. (KAR id:91305)

PDF Publisher pdf
Language: English

Download (443kB) Preview
[thumbnail of paper_86.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL


We investigate conjunctive query inseparability of description logic knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We develop a game-theoretic technique for checking query inseparability of KBs expressed in fragments of Horn-ALCHI, and show a number of complexity results ranging from P to EXPTIME and 2EXPTIME. We also employ our results to 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 EXPTIME complete for combined complexity

Item Type: Conference or workshop item (Proceeding)
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 14:50 UTC
Last Modified: 05 Nov 2021 09:38 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):