Mixing Materialization and Query Rewriting for Existential Rules
Mixing Materialization and Query Rewriting for Existential Rules
复制标题
混合实现和查询重写以实现存在规则
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
S. Rudolph
中科院分区：
文献类型：
--
作者：
M. Thomazo;S. Rudolph
基于本体的数据访问（OBDA）是一个新的范例，旨在提高数据访问考虑到本体知识。当使用存在规则作为本体语言时，查询回答是一个不可判定的问题，因此已经定义了许多可判定的本体类，从具有非常好的计算复杂性（数据复杂性中的AC0）的类到具有更大表达性的类。然而，实际上可实现的算法已经提出了非常有限的类（通常是那些符合轻量级描述逻辑）。本文的目的是展示如何处理更多的表达本体，提出了一种算法，执行物化和重写，并适用于一个显着的概括轻量级描述逻辑。为此，我们首先修改现有的算法以前提出了一个非常通用的一类规则，即贪婪有界树宽规则集。然后，我们展示了一个特殊的情况下，被称为模式不经意的规则集，显着概括的OWL LHDR描述逻辑，这是OWL 2 EL本体标准的基础，同时保持有益的最坏情况下的计算复杂度。我们最后定义了一个在多项式时间内可识别的模式不经意规则子类。
Ontology-Based Data Access (OBDA) is a recent paradigm aiming at enhancing data access by taking ontological knowledge into account. When using existential rules as ontological language, query answering is an undecidable problem, whence numerous decidable classes of ontologies have been defined, ranging from classes with very good computational complexities (AC0 in data complexity) to classes with much larger expressivity. However, actually implementable algorithms have been proposed only for very restricted classes (typically those coinciding with lightweight description logics). The aim of this paper is to show how to deal with more expressive ontologies by proposing an algorithm that performs both materialization and rewriting and is applicable for a significant generalization of lightweight description logics. To this end, we first modify an existing algorithm previously proposed for a very generic class of rules, namely greedy bounded treewidth sets of rules. We then exhibit a special case, called pattern oblivious rule sets, which significantly generalizes the ℇLHdr description logic, which underlies the OWL 2 EL ontology standard, while keeping the beneficial worst-case computational complexity. We last define a subclass of pattern oblivious rules that is recognizable in polynomial time.