We attempt a structured view at the ontological query answering problem by distinguishing between two antagonistic perspectives: The knowledge representation perspective considers the ontology as a part of the specified knowledge whereas the database perspective assumes it to be part of the query. These two perspectives give rise to two computation strategies: (data-driven) forward chaining and (query-driven) backward chaining, based on which di erent types of decidability criteria can be defined. We give an overview of the two views as well as ensuing conditions for decidability, focusing on existential rules as ontological formalism that has lately gained a lot of renewed interest from both the KR and DB communities.
Intelligent methods for search and management of large amounts of knowledge require a firm theoretical basis blending paradigms and approaches from databases and knowledge representation. It has been widely acknowledged that the task of retrieving information from a body of knowledge via querying can greatly benefit from a mediating logical layer between the factual data and the query. The ontological query answering framework, phrased in terms of formal logic, is to check the entailment D j= Q, where D, called the database, is a set of ground facts, , called the ontology, is a set of sentences of some logic, and Q, the query, is a logical sentence. The logical formalisms used to express and Q may di er, they are referred to as ontology language and query language, respectively. In words, the task is to find out if some statement Q follows from D given the background knowledge . One can distinguish between two perspectives di ering in whether is considered as part of the query or belonging to the data. These two viewpoints are sketched in Fig. 1.
The Knowledge Representation View. This view is characterized by the idea that
D provides only incomplete information about the state of a airs and that serves
the purpose of enriching this information with logical consequences of D [ , before
querying it via Q. The combination of D and is then often referred to as knowledge
base and is viewed as integrated and condensed description of a domain of interest. A
prominent example for this view are description logics (DLs [
DB View D j= (V ) ! Q ontology-mediated query ( ; Q) today inferencing problems of such restricted type are denoted DL standard reasoning tasks; only over the last two decades, attention has shifted toward settings where Q can be a conjunctive query.
The Database View. This perspective conceives as part of the query, enhancing the query language’s expressivity. In the plain version of this setting, is supposed to be conservative over D: there is a separation into predicates occurring in D (also called extensional database predicates, short EDBs) and those only occurring in (referred to as intensional database predicates, short IDBs), where the latter are thought to not carry meaning independent of the actual query, rather they are auxiliary predicates, used to store intermediate results toward the computation of the query. In particular, should not allow for inferring new facts over EDB predicates from D. In this scenario, the inferencing task can be rewritten into D j= 8P:(V ! Q), where P is a sequence of all IDB predicates in viewed as second-order variables. The most widespread example of this view are Datalog queries.
The two perspectives give rise to two fundamentally di erent approaches for solving the query answering problem. The KR view calls for a transformation of the knowledge base (D; ) into a more explicit representation, whereas the DB view suggests the same for the ontology-mediated query ( ; Q).
In the following, we will see how these two antagonistic generic strategies can be instantiated. As a key showcase, we will use existential rules, which will be introduced next. 2
This section introduces the framework of existential rules which are also known under many other names, including tuple-generating dependencies (TGDs), Datalog , and 89-rules.
Definition 1. An existential rule (or simply rule in the context of this paper) is a firstorder formula of the form
8x: B1 ^ : : : ^ Bk ! 9y:H1 ^ : : : ^ Hl ; where B1; : : : ; Bk; H1; : : : ; Hl (with k 0 and l 1) are atoms all of whose variables are in the scope of some quantifier, and where no variable occurs more than once in x; y. A Datalog rule is a rule with no existential quantifiers. A rule with k = 0 is called a fact (a conclusion that is unconditionally true), a set of facts is also referred to as a database.
The premise of a rule is called the body while the conclusion is called the head.
The rule language hereby introduced is a syntactic fragment of first-order predicate logic (FOL), and we consider it under the according semantics.
Definition 2. Let be a set of rules. A Boolean conjunctive query (BCQ) is a formula 9v:Q where Q is a conjunction of atoms and v contains all variables in Q. A BCQ 9v:Q is entailed by if it is entailed under standard FOL semantics.
Checking BCQ entailment for unrestricted existential rules is undecidable [
Still, the existential rules have nice model-theoretic properties which often allow for more e cient reasoning compared to first-order logic in general: the existence of canonical models. For every database D and set of existential rules there exists a universal model I, i.e., I satisfies I j= D, I j= , and for each model J of D and there exists a homomorphism from J to I. Note that there may be several universal models which are not isomorphic to each other, but there is always a “smallest” one (more formal: one for which identity is the only endomorphism), which is unique up to isomorphism and normally called the core.
Universal models are particularly useful when considering entailment of logical formulae whose validity is preserved under homomorphisms, that is, formulae ' for which I j= ' implies J j= ' if a homomorphism from I to J exists. For first-order logic, the Łos-Tarski-Lyndon Theorem states that every such formula can be expressed by a positive existential sentence, and consequently by a union of BCQs.
In short: for existential rules and (unions of) Boolean conjunctive queries, query answering (an entailment problem) boils down to model checking in a universal model. Thus, computing some representation of a universal model is a central approach for reasoning with existential rules. 3
Referring back to the described views on the query answering problem, we saw that the “KR view” conceives the ontology as part of the (incomplete) data(base), meant to enrich the latter with further information. This view suggests an inferencing approach which iteratively computes the (possible) factual consequences of the ontology, thus making the knowledge base more explicit and the database less incomplete. Another way to illustrate such a strategy is to view D as a partial model, which may violate some of and is consequently “repaired” by adding new information. This may not only require adding new facts about known domain elements but it might also necessitate to add new domain elements whose existence can be inferred.
A very general example for such a “model explication” approach is the semantic
tableau method in FOL [
Luckily, the situation is better for existential rules, for which the repair strategy is
known as the chase, introduced by Maier et al. [
For arbitrary existential rules, termination of the chase cannot be guaranteed, and an infinite set of new domain elements and facts may be created. In general, the chase can thus only serve as semi-decision procedure for query entailment.
It is therefore natural to ask for conditions, under which the chase (or some modification of it) can be used as a decision procedure. In fact, many of the decidable existential rule fragments come about by establishing properties about the chase they create. Thereby, one is normally interested in properties which can be established independently from the underlying database. 3.1
Finiteness of the (core) chase (for every possibly database D) is a straightforward
criterion for ensuring decidability, and rule sets with this property are also called finite
extension sets [
A group of concrete criteria (that is, criteria which can be syntactically checked) for
chase finiteness aims at analyzing the ways how the execution of some rule may trigger
executability of other rules. If there is the possibility that, due to cyclic such triggering
relationships, more and more domain elements might have to be added when computing
the chase, non-termination may arise. The group of criteria aiming at excluding such
cyclic dependencies is referred to as acyclicity conditions. One example of this is (weak)
acyclicity [
A more relaxed condition than finiteness of the chase is that the (possibly infinite) chase enjoys a variant of the bounded treewidth property, a notion originating from graph theory but easily transferrable to databases. In words, a (possibly infinite) database D has treewidth of n, if n is the minimal number such that one can come up with an auxiliary structure (called the tree decomposition) which is a (possibly infinite) tree whose nodes (called bags) are sets containing at most n + 1 domain elements from D such that (1) whenever D contains some atom p(d), there must be a bag containing all elements from d and (2) for every domain element d from D, the substructure induced by all bags containing d is a tree. Intuitively, the treewidth is a measure of the “treeishness” of the database: the lower the treewidth, the more tree-like the database. In particular, tree-shaped databases have treewidth 1.
Now, a rule set is called a bounded-treewidth set [
Guardedness (first introduced for full first-order logic [
It turns out that all the above notions of guardedness have a nice computational
property: in the course of constructing the chase, the tree-decomposition can be built
up simultaneously in a greedy way. It turns out that if a rule set has this property (in
which case it is called a greedy bounded-treewidth set), BCQ answering can be
implemented by a generic worst-case-optimal algorithm that works on the level of the
treedecomposition and computes a finite representation of the full (infinite) chase. This is
achieved by detecting repetitions, such that the full tree decomposition can be
represented by a finite part of it plus some information how to unfold it into the full infinite
structure [
The principles of acyclicity and guardedness employ di erent strategies to ensure the
desired chase properties. Acyclicity avoids indefinite repetitions of creation of new
domain elements whereas guardedness allows to create new atoms involving known
domain elements only if these elements already occur together in an atom, thereby
preventing that formerly unconnected individuals are arbitrarily linked together by newly
created atoms. The di erent variants of guardedness presented above already indicate
that the plain guardedness criterion can be relaxed in several ways, since not all
variables in a rule are equally “dangerous”: only those variables that have the potential of
triggering the creation of new domain individuals need to be guarded. In fact, this
criterion can be further relaxed, drawing from acyclicity ideas: variables are only dangerous
if they can trigger the creation of infinitely many new domain individuals through cyclic
execution (in which case they are called glut variables), whereas variables bringing
about only finitely many new elements can still be considered well-behaved. It turns
out that it su ces to guard only the glut variables to obtain a bounded-treewidth set.
Glut-guarded and glut-frontier-guarded rules thus defined [
When taking the perspective of treating the ontology as part of the query, a
straightforward strategy is to try and transform this ontology-mediated query into a more explicit
representation (using a simpler query language). There is a wide variety of possible
target query languages for such a transformation. Figure 2 depicts some of the most
popular ones, together with two new ones that were recently introduced as favorable
trade-o between expressivity and computational intricacy [
A rather basic example for a query-rewriting approach is SLD resolution used in
logic programming, where a query is rewritten in all possible ways by factoring in the
rules of the logic program in a backward-chaining way. In the case of existential rules,
a similar strategy can be applied, with the di erence that, unlike in SLD resolution, it
cannot be performed query atom by query atom. Rather, so-called pieces (groups of
atoms which are connected via variables) have to be rewritten together [
This piece-based rewriting technique produces in every step a union of Boolean
conjunctive queries, which are subsumed by the original ontology-mediated query (that is,
whenever one BCQ of the union has a match in a database, the original query matches
as well). Moreover, if this step-wise computation stabilizes, it also subsumes the
original query and we have arrived at a perfect rewriting of the original query into a union of
BCQs. Thus, dually to the finite chase condition, one can define finite unification sets
as rule sets where this rewriting procedure applied to ( ; Q) terminates for arbitrary
BCQs Q [
FOL CQ AC0 models closed not closed under homomorphisms
Datalog linear Datalog C2RPQ u n d q ce eu iad ry b c MSO le on t a ed in
m icd en ab t
NEMODEQ le
MODEQ monadic
Datalog
NLogSpace PTime d a t a c o m p l ex i t y o f q u e r y a n s w e r i n g
PH Unfortunately, rewriting into queries expressible in first-order logic is not always possible. In fact, most of the known existential rule fragments have a data complexity beyond AC0, which proves that they cannot be first-order rewritable.
Since considerably more of the known existential rule fragments have PTime data
complexity, and Datalog is a well-established querying formalism supported by highly
optimized tools, several rewritings into Datalog have been proposed [
The fact that most known formalisms with PTime data complexity allow for a
rewriting into Datalog may give rise to the hope that any existential rule fragment with PTime
data complexity might be Datalog rewritable. Such a general finding would also
resonate well with the fact that the result is easy to prove for databases with a little bit of
extra information: a linear order on the elements. While this would have been a very
desirable result, it turns out not to be the case. The following was shown via a pumping
argument for Datalog derivations:
Proposition 1 ([
Our negative result now follows from the existence of an existential rule query that expresses Q using an appropriate Turing machine simulation. 4.3
While rewriting into Datalog queries is applicable to many logical fragments, Datalog
queries are much more di cult to handle than (unions of) conjunctive queries when
it comes to certain tasks which are important for database management. In particular,
checking query containment is known to be undecidable for Datalog queries [
In some cases the ontology turns out to be structured in a way that as a whole is not suited for any of the two presented approaches, but it can be partitioned into two parts 1 and 2 such that the knowledge base (D; 2) allows for answering queries of some type into which ( 1; Q) can be rewritten. This situation is depicted in Fig. 3.
Typically, this requires that 1 is “on top of” 2 applying some notion of
stratification. For example, this stratification can be characterized in terms of conservative
extensions or – in case 1 and 2 are sets of existential rules – via rule dependencies [
stratifiable ontology ”Neutral” D j= Q and Q can be rewritten into another conjunctive 2-way regular path query Q’ to be executed against the knowledge base (D; 2) (where D and 2 are referred to as ABox and TBox, respectively, in description logic terms). 6
We have reviewed the state of the art in ontological query answering, while focusing on the particular case of existential rules. We argued that the currently available approaches can be roughly separated into two large groups (and combinations thereof) one rewriting the data, the other rewriting the query. While this already helps getting a clearer picture of the field, the ultimate goal would be a joint characterization, capturing these two classes by means of a common criterion. Hopefully, this would allow for defining more expressive, decidable querying frameworks.
Much of the synopsis provided in this paper is based on joint research with many colleagues to which I am deeply indebted, most notably Jean-François Baget, Georg Gottlob, Markus Krötzsch, Marie-Laure Mugnier, Magdalena Ortiz, Mantas Šimkus, and Michaël Thomazo. Moreover, I am very grateful for enlightening discussions with Michael Benedikt, Diego Calvanese, Bruno Courcelle and Detlef Seese.