Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
复制标题
DOI：
10.1613/jair.3949
复制
发表时间：
2013-05
期刊：
影响因子：
--
通讯作者：
B. C. Grau;Ian Horrocks;M. Krötzsch;C. Kupke;Despoina Magka;B. Motik;Zhe Wang
中科院分区：
文献类型：
--
作者：
B. C. Grau;Ian Horrocks;M. Krötzsch;C. Kupke;Despoina Magka;B. Motik;Zhe Wang
在与存在规则扩展的一组事实上回答连词查询（CQS）是知识表示和数据库中的一个突出问题。可以使用Chase算法解决此问题，该算法将给定的事实扩展到具有新鲜事实以满足规则的情况。如果追逐终止，则可以直接在由此产生的事实集中评估CQ。但是，追逐不一定要终止，并检查追逐是否在给定的一组规则和事实上终止。提出了许多无环概念作为追逐终止的足够条件。在本文中，我们提出了两个新的环体概念，称为模型忠实环保（MFA）和模型夏令性无环（MSA）。此外，我们研究了已知的无环概念的景观，并为我们所知的所有概念建立了完整的分类法。最后，我们表明MFA和MSA概括了大多数这些概念。存在规则与OWL 2本体语言的角片段密切相关。此外，几位著名的猫头鹰2推理者通过使用追逐来实现所有相关事实来实现CQ回答。为了避免终止问题，其中许多系统仅处理猫头鹰2的owl 2 RL轮廓；此外，某些系统超出了OWL 2 RL，但没有任何终止保证。在本文中，我们还研究了各种环形概念是否可以针对这些问题提供原则性和实用的解决方案。从理论方面来说，我们表明对无环本体的询问比一般本体学的复杂性低。从实际方面来说，我们表明许多常用的猫头鹰2本体论都是MSA，并且实体化获得的事实数量并不太大。因此，我们的结果表明，基于物质化的OWL 2推理者的原则发展实际上是可行的。
Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved using the chase algorithm, which extends the given set of facts with fresh facts in order to satisfy the rules. If the chase terminates, then CQs can be evaluated directly in the resulting set of facts. The chase, however, does not terminate necessarily, and checking whether the chase terminates on a given set of rules and facts is undecidable. Numerous acyclicity notions were proposed as sufficient conditions for chase termination. In this paper, we present two new acyclicity notions called model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA). Furthermore, we investigate the landscape of the known acyclicity notions and establish a complete taxonomy of all notions known to us. Finally, we show that MFA and MSA generalise most of these notions. Existential rules are closely related to the Horn fragments of the OWL 2 ontology language; furthermore, several prominent OWL 2 reasoners implement CQ answering by using the chase to materialise all relevant facts. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2; furthermore, some systems go beyond OWL 2 RL, but without any termination guarantees. In this paper we also investigate whether various acyclicity notions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 ontologies are MSA, and that the number of facts obtained by materialisation is not too large. Our results thus suggest that principled development of materialisation-based OWL 2 reasoners is practically feasible.