%0 Journal Article %1 2016-AIJ-games-inseparability %A Botoeva, Elena %A Kontchakov, Roman %A Ryzhikov, Vladislav %A Wolter, Frank %A Zakharyaschev, Michael %D 2016 %J Artificial Intelligence %K Computational Conjunctive Description Games Knowledge Query base, complexity, graphs, inseparability, logic, on optique-project query, %P 78--119 %R 10.1016/j.artint.2016.01.010 %T Games for Query Inseparability of Description Logic Knowledge Bases %U http://www.sciencedirect.com/science/article/pii/S0004370216300017 %V 234 %X We consider conjunctive query inseparability of description logic knowledge bases with respect to a given signature—a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query inseparability and develop worst-case optimal decision algorithms for fragments of Horn-ALCHI, including the description logics underpinning OWL 2 QL and OWL 2 EL. We also determine the data and combined complexity of deciding query inseparability. While query inseparability for all of these logics is P-complete for data complexity, the combined complexity ranges from P- to ExpTime- to 2ExpTime-completeness. We use these results to resolve two major open problems for OWL 2 QL by showing that TBox query inseparability and the membership problem for universal conjunctive query solutions in knowledge exchange are both ExpTime-complete for combined complexity. Finally, we introduce a more flexible notion of inseparability which compares answers to conjunctive queries in a given signature over a given set of individuals. In this case, checking query inseparability becomes NP-complete for data complexity, but the ExpTime- and 2ExpTime-completeness combined complexity results are preserved.

@article{2016-AIJ-games-inseparability, abstract = {We consider conjunctive query inseparability of description logic knowledge bases with respect to a given signature—a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query inseparability and develop worst-case optimal decision algorithms for fragments of Horn-ALCHI, including the description logics underpinning OWL 2 QL and OWL 2 EL. We also determine the data and combined complexity of deciding query inseparability. While query inseparability for all of these logics is P-complete for data complexity, the combined complexity ranges from P- to ExpTime- to 2ExpTime-completeness. We use these results to resolve two major open problems for OWL 2 QL by showing that TBox query inseparability and the membership problem for universal conjunctive query solutions in knowledge exchange are both ExpTime-complete for combined complexity. Finally, we introduce a more flexible notion of inseparability which compares answers to conjunctive queries in a given signature over a given set of individuals. In this case, checking query inseparability becomes NP-complete for data complexity, but the ExpTime- and 2ExpTime-completeness combined complexity results are preserved.}, added-at = {2016-11-02T04:00:58.000+0100}, audience = {academic}, author = {Botoeva, Elena and Kontchakov, Roman and Ryzhikov, Vladislav and Wolter, Frank and Zakharyaschev, Michael}, biburl = {https://www.bibsonomy.org/bibtex/2b781b04a7bdba12b3c03054570667469/calvanese}, doi = {10.1016/j.artint.2016.01.010}, interhash = {96e7cd7aef687fa785777d1ff4c33185}, intrahash = {b781b04a7bdba12b3c03054570667469}, journal = {Artificial Intelligence}, keywords = {Computational Conjunctive Description Games Knowledge Query base, complexity, graphs, inseparability, logic, on optique-project query,}, pages = {78--119}, partneroptique = {FUB}, timestamp = {2016-11-02T04:02:37.000+0100}, title = {Games for Query Inseparability of Description Logic Knowledge Bases}, url = {http://www.sciencedirect.com/science/article/pii/S0004370216300017}, volume = 234, wpoptique = {WP6}, year = 2016, yearoptique = {Y4} }