Games for query inseparability of description logic knowledge bases

详细信息    查看全文

• 作者：Elena Botoeva^a ; ^{botoeva@inf.unibz.it" class="auth_mail" title="E-mail the corresponding author} ; Roman Kontchakov^b ; ^{roman@dcs.bbk.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Vladislav Ryzhikov^a ; ^{ryzhikov@inf.unibz.it" class="auth_mail" title="E-mail the corresponding author} ; Frank Wolter^c ; ^{wolter@liverpool.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Michael Zakharyaschev^b ; ^{michael@dcs.bbk.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Description logic ; Knowledge base ; Conjunctive query ; Query inseparability ; Games on graphs ; Computational complexity
• 刊名：Artificial Intelligence
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：234
• 期：Complete
• 页码：78-119
• 全文大小：1654 K

文摘

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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0004370216300017&_mathId=si1.gif&_user=111111111&_pii=S0004370216300017&_rdoc=1&_issn=00043702&md5=021f885be64a0edb0c6970b8f635e1d8" title="Click to view the MathML source">Horn-ALCHIclass="mathContainer hidden">class="mathCode">$\text{<italic>Horn-</italic>}\mathcal{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 class="smallcaps">P-complete for data complexity, the combined complexity ranges from class="smallcaps">P- to class="smallcaps">ExpTime- to 2class="smallcaps">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 class="smallcaps">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 class="smallcaps">NP-complete for data complexity, but the class="smallcaps">ExpTime- and 2class="smallcaps">ExpTime-completeness combined complexity results are preserved.