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，并提供语法和语义的定义，以及解决了语言可决性问题，这些语言都是知识表示和推理方面的有吸引力的，特别是在需要基于本体论的推理的领域中。