Existential rule languages are a family of ontology languages that have been
widely used in ontology-mediated query answering (OMQA). However, for most of
them, the expressive power of representing domain knowledge for OMQA, known as
the program expressive power, is not well-understood yet. In this paper, we
establish a number of novel characterizations for the program expressive power
of several important existential rule languages, including tuple-generating
dependencies (TGDs), linear TGDs, as well as disjunctive TGDs. The
characterizations employ natural model-theoretic properties, and
automata-theoretic properties sometimes, which thus provide powerful tools for
identifying the definability of domain knowledge for OMQA in these languages.

本文研究了存在规则语言家族在本体 - 媒介查询应答中的作用，特别是它们对领域知识表达的程序表达能力的影响，并提出了基于自然模型和自动机的特征值，从而为这些语言中领域知识的可定义性提供了强有力的工具。

表征存在规则语言的程序表达能力

Characterizing the Program Expressive Power of Existential Rule  Languages

Counting answers to a query is an operation supported by virtually all
database management systems. In this paper we focus on counting answers over a
Knowledge Base (KB), which may be viewed as a database enriched with background
knowledge about the domain under consideration. In particular, we place our
work in the context of Ontology-Mediated Query Answering/Ontology-based Data
Access (OMQA/OBDA), where the language used for the ontology is a member of the
DL-Lite family and the data is a (usually virtual) set of assertions. We study
the data complexity of query answering, for different members of the DL-Lite
family that include number restrictions, and for variants of conjunctive
queries with counting that differ with respect to their shape (connected,
branching, rooted). We improve upon existing results by providing a PTIME and
coNP lower bounds, and upper bounds in PTIME and LOGSPACE. For the latter case,
we define a novel query rewriting technique into first-order logic with
counting.

本文探讨了在具有背景领域知识的数据库 Knowledge Base 中对查询答案进行计数的数据复杂度，并提供了一种基于 DL-Lite 族成员的本体引介式查询答案 / 本体基础的数据访问语言来实现此目标。作者提出了一种具有重要意义的查询重写技术以及 P 时间、coNP 下限和 P 时间、LOGSPACE 上限的算法实现。

对 DL-Lite 知识库中的计数查询答案的扩展版

Counting Query Answers over a DL-Lite Knowledge Base (extended version)

Existential rules are a positive fragment of first-order logic that
generalizes function-free Horn rules by allowing existentially quantified
variables in rule heads. This family of languages has recently attracted
significant interest in the context of ontology-mediated query answering.
Forward chaining, also known as the chase, is a fundamental tool for computing
universal models of knowledge bases, which consist of existential rules and
facts. Several chase variants have been defined, which differ on the way they
handle redundancies. A set of existential rules is bounded if it ensures the
existence of a bound on the depth of the chase, independently from any set of
facts. Deciding if a set of rules is bounded is an undecidable problem for all
chase variants. Nevertheless, when computing universal models, knowing that a
set of rules is bounded for some chase variant does not help much in practice
if the bound remains unknown or even very large. Hence, we investigate the
decidability of the k-boundedness problem, which asks whether the depth of the
chase for a given set of rules is bounded by an integer k. We identify a
general property which, when satisfied by a chase variant, leads to the
decidability of k-boundedness. We then show that the main chase variants
satisfy this property, namely the oblivious, semi-oblivious (aka Skolem), and
restricted chase, as well as their breadth-first versions. This paper is under
consideration for publication in Theory and Practice of Logic Programming.

研究论文探讨了基于本体的查询应答中的万有模型问题，特别关注存在规则边界问题，提出了一般性质并证明了一些经典的 chase 变体满足该性质，进而解决了这些变体的有限深度问题。