Show simple item record

dc.contributor.authorBotoeva E
dc.contributor.authorKontchakov R
dc.contributor.authorRyzhikov V
dc.contributor.authorWolter F
dc.contributor.authorZakharyaschev M
dc.date.accessioned2018-05-29T09:23:28Z
dc.date.available2018-05-29T09:23:28Z
dc.date.issued2016
dc.identifier.issn0004-3702
dc.identifier.urihttp://dx.doi.org/10.1016/j.artint.2016.01.010
dc.identifier.urihttps://www.sciencedirect.com/science/article/pii/S0004370216300017
dc.identifier.urihttp://hdl.handle.net/10863/5102
dc.description.abstractWe 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 2 ExpTime-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.en_US
dc.language.isoenen_US
dc.rights
dc.titleGames for Query Inseparability of Description Logic Knowledge Basesen_US
dc.typeArticleen_US
dc.date.updated2018-05-15T13:07:00Z
dc.language.isiEN-GB
dc.journal.titleArtificial Intelligence
dc.description.fulltextopenen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record