Query answering over contextualized RDF/OWL knowledge with forall-existential bridge rules: Decidable finite extension classes
Query answering over contextualized RDF/OWL knowledge with forall-existential bridge rules: Decidable finite extension classes
复制标题
使用所有存在的桥接规则对上下文化 RDF/OWL 知识进行查询回答：可判定的有限扩展类
作者：
M. Joseph;G. Kuper;Till Mossakowski;L. Serafini
语义网中语境化知识的激增导致了诸如\emph{quads}这样的知识格式在语义网社区中的流行。四元组是具有三元组上下文信息的RDF三元组的扩展。在这篇文章中，我们研究了四元组上的查询回答问题，该问题增加了全存在桥规则，使得三元组之间的推理在不同的上下文中可以互操作。我们将一组四元组与这种富有表现力的桥牌规则结合在一起，称为四元系。一般来说，四系统上的查询回答是不可判定的。我们导出了四元系统的可判定类，对于这些四元系统，可以使用前向链来完成查询回答。为这些类提供了声音、完整和终止过程，它们是公知的Chase算法的改编，用于确定查询蕴涵。SAFE、MSAFE和CSAFE类四元系统将在Chase计算过程中生成的空白节点的结构限制为有界深度的有向无环图(DAG)。RR和受限RR类不允许在chase计算过程中生成空白节点。对于派生的类，已经建立了查询蕴涵的数据和组合复杂性。我们进一步证明了四元系统等价于所有存在规则，这些规则的谓词被限制为三进制模多项式时间转换。我们随后证明，安全技术严格地包含在可表现性中，一些众所周知的和可表达的技术，如联合无循环和模型忠实无循环，用于在普遍存在的规则领域中保证可判断性。
The proliferation of contextualized knowledge in the Semantic Web (SW) has led to the popularity of knowledge formats such as \emph{quads} in the SW community. A quad is an extension of an RDF triple with contextual information of the triple. In this paper, we study the problem of query answering over quads augmented with forall-existential bridge rules that enable interoperability of reasoning between triples in various contexts. We call a set of quads together with such expressive bridge rules, a quad-system. Query answering over quad-systems is undecidable, in general. We derive decidable classes of quad-systems, for which query answering can be done using forward chaining. Sound, complete and terminating procedures, which are adaptations of the well known chase algorithm, are provided for these classes for deciding query entailment. Safe, msafe, and csafe class of quad-systems restrict the structure of blank nodes generated during the chase computation process to be directed acyclic graphs (DAGs) of bounded depth. RR and restricted RR classes do not allow the generation of blank nodes during the chase computation process. Both data and combined complexity of query entailment has been established for the classes derived. We further show that quad-systems are equivalent to forall-existential rules whose predicates are restricted to ternary arity, modulo polynomial time translations. We subsequently show that the technique of safety, strictly subsumes in expressivity, some of the well known and expressive techniques, such as joint acyclicity and model faithful acyclicity, used for decidability guarantees in the realm of forall-existential rules.
DOI：
10.1613/jair.3949
发表时间：
2013-05
期刊：
J. Artif. Intell. Res.
影响因子：
--
作者：
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