Query inseparability for ALC ontologies
Query inseparability for ALC ontologies
复制标题
ALC 本体的查询不可分离性
DOI：
10.1016/j.artint.2018.09.003
复制
发表时间：
2019
影响因子：
14.4
通讯作者：
Botoeva E
中科院分区：
文献类型：
--
作者：
Botoeva E
我们通过给定签名中的查询来研究两个ALC本体是否不可区分（或不可分割）的问题，这是本体工程任务（如本体版本控制，模块化，更新和遗忘）的基础。我们认为知识库和TBox是不可分割的。对于KBs，我们给出了关于（有限部分）同态和乘积的模型理论准则，并证明了该问题对于连接查询（CQs）是不可判定的，但是对于CQs的并集（UCQs）是2 ExpTime-complete的。如果将(U) cq替换为根(U) cq，其中每个变量都连接到一个答案变量，则结果相同。我们还证明，如果在轻量级DL EL中给定一个KB，并且对cq的签名没有任何限制，则cq的不可分性仍然是不可判定的。我们还考虑了两个ALC tbox是否对给定签名中任何ABox的任何查询给出相同的答案的问题，并表明，对于cq，这个问题也是不可判定的。然后，我们开发了Horn ALC TBoxes的模型理论准则，并使用树自动机证明，与此相反，不可分性成为可判定的，并且2 ExpTime-complete，甚至当限制为（并）根cq时，ExpTime-complete。
We investigate the problem whether two ALC ontologies are indistinguishable (or inseparable) by means of queries in a given signature, which is fundamental for ontology engineering tasks such as ontology versioning, modularisation, update, and forgetting. We consider both knowledge base (KB) and TBox inseparability. For KBs, we give model-theoretic criteria in terms of (finite partial) homomorphisms and products and prove that this problem is undecidable for conjunctive queries (CQs), but 2 ExpTime-complete for unions of CQs (UCQs). The same results hold if (U) CQs are replaced by rooted (U) CQs, where every variable is connected to an answer variable. We also show that inseparability by CQs is still undecidable if one KB is given in the lightweight DL EL and if no restrictions are imposed on the signature of the CQs. We also consider the problem whether two ALC TBoxes give the same answers to any query over any ABox in a given signature and show that, for CQs, this problem is undecidable, too. We then develop model-theoretic criteria for Horn ALC TBoxes and show using tree automata that, in contrast, inseparability becomes decidable and 2 ExpTime-complete, even ExpTime-complete when restricted to (unions of) rooted CQs.