Ontology-based data access is concerned with querying incomplete data sources
in the presence of domain-specific knowledge provided by an ontology. A central
notion in this setting is that of an ontology-mediated query, which is a
database query coupled with an ontology. In this paper, we study several
classes of ontology-mediated queries, where the database queries are given as
some form of conjunctive query and the ontologies are formulated in description
logics or other relevant fragments of first-order logic, such as the guarded
fragment and the unary-negation fragment. The contributions of the paper are
three-fold. First, we characterize the expressive power of ontology-mediated
queries in terms of fragments of disjunctive datalog. Second, we establish
intimate connections between ontology-mediated queries and constraint
satisfaction problems (CSPs) and their logical generalization, MMSNP formulas.
Third, we exploit these connections to obtain new results regarding (i)
first-order rewritability and datalog-rewritability of ontology-mediated
queries, (ii) P/NP dichotomies for ontology-mediated queries, and (iii) the
query containment problem for ontology-mediated queries.

本文研究了本体基础数据查询的各种类别，包括关系数据库查询与本体、描述逻辑或其他相关一阶逻辑和联结查询。研究结果包括三个方面，首先用不相交的 Datalog 片段来表达了本体中介查询的表达能力。其次，本体中介查询与约束满足问题（CSP）及其逻辑泛化 MMSNP 公式有密切联系。最后，利用这些联系得出了有关本体中介查询的新结果，如 i）本体中介查询的一阶重写和 Datalog 重写，ii）本体中介查询的 P / NP 二分法，以及 iii）本体中介查询的查询包容性问题。

基于本体的数据访问：通过 Disjunctive Datalog、CSP 和 MMSNP 的研究

Ontology-based Data Access: A Study through Disjunctive Datalog, CSP,  and MMSNP

Datalog is one of the best-known rule-based languages, and extensions of it
are used in a wide context of applications. An important Datalog extension is
Disjunctive Datalog, which significantly increases the expressivity of the
basic language. Disjunctive Datalog is useful in a wide range of applications,
ranging from Databases (e.g., Data Integration) to Artificial Intelligence
(e.g., diagnosis and planning under incomplete knowledge). However, in recent
years an important shortcoming of Datalog-based languages became evident, e.g.
in the context of data-integration (consistent query-answering, ontology-based
data access) and Semantic Web applications: The language does not permit any
generation of and reasoning with unnamed individuals in an obvious way. In
general, it is weak in supporting many cases of existential quantification. To
overcome this problem, Datalogex has recently been proposed, which extends
traditional Datalog by existential quantification in rule heads. In this work,
we propose a natural extension of Disjunctive Datalog and Datalogex, called
Datalogexor, which allows both disjunctions and existential quantification in
rule heads and is therefore an attractive language for knowledge representation
and reasoning, especially in domains where ontology-based reasoning is needed.
We formally define syntax and semantics of the language Datalogexor, and
provide a notion of instantiation, which we prove to be adequate for
Datalogexor. A main issue of Datalogex and hence also of Datalogexor is that
decidability is no longer guaranteed for typical reasoning tasks. In order to
address this issue, we identify many decidable fragments of the language, which
extend, in a natural way, analog classes defined in the non-disjunctive case.
Moreover, we carry out an in-depth complexity analysis, deriving interesting
results which range from Logarithmic Space to Exponential Time.

本文介绍了 Datalog 的扩展形式 Disjunctive Datalog，Datalogex 和 Datalogexor，并提供语法和语义的定义，以及解决了语言可决性问题，这些语言都是知识表示和推理方面的有吸引力的，特别是在需要基于本体论的推理的领域中。

具存在量词的分离 Datalog：语义、可决定性和复杂性问题

Disjunctive Datalog with Existential Quantifiers: Semantics,  Decidability, and Complexity Issues

In this paper, a new technique for the optimization of (partially) bound
queries over disjunctive Datalog programs with stratified negation is
presented. The technique exploits the propagation of query bindings and extends
the Magic Set (MS) optimization technique.
An important feature of disjunctive Datalog is nonmonotonicity, which calls
for nondeterministic implementations, such as backtracking search. A
distinguishing characteristic of the new method is that the optimization can be
exploited also during the nondeterministic phase. In particular, after some
assumptions have been made during the computation, parts of the program may
become irrelevant to a query under these assumptions. This allows for dynamic
pruning of the search space. In contrast, the effect of the previously defined
MS methods for disjunctive Datalog is limited to the deterministic portion of
the process. In this way, the potential performance gain by using the proposed
method can be exponential, as could be observed empirically.
The correctness of MS is established thanks to a strong relationship between
MS and unfounded sets that has not been studied in the literature before. This
knowledge allows for extending the method also to programs with stratified
negation in a natural way.
The proposed method has been implemented in DLV and various experiments have
been conducted. Experimental results on synthetic data confirm the utility of
MS for disjunctive Datalog, and they highlight the computational gain that may
be obtained by the new method w.r.t. the previously proposed MS methods for
disjunctive Datalog programs. Further experiments on real-world data show the
benefits of MS within an application scenario that has received considerable
attention in recent years, the problem of answering user queries over possibly
inconsistent databases originating from integration of autonomous sources of
information.

本文介绍了一种新的技术，通过利用查询绑定的传播并扩展魔法集（MS）优化技术来优化（部分）绑定查询，从而对分层否定性的分离 Datalog 程序进行优化，通过对具体应用进行实验，可以得到该方法带来了显著的计算收益。