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.
%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}
}