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. CEUR-WS.org (KAR id:91305)

PDF Publisher pdf
Language: English


Download (443kB) Preview
[thumbnail of paper_86.pdf]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL
http://ceur-ws.org/Vol-1193/paper_86.pdf

Abstract

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: https://kar.kent.ac.uk/id/eprint/91305 (The current URI for this page, for reference purposes)
  • Depositors only (login required):