Expressive Completeness of Existential Rule Languages for Ontology-Based Query Answering

1 Introduction

Ontology-based Query Answering (OQA) has been a central issue in Ontological Reasoning and Knowledge Representation, and played an essential role in the Semantic Web, Data Modelling, and Data Exchange and Integration. Generally speaking, the problem of OQA may be stated as follows: Given a database D, an ontology (usually, a logical theory) ⌃ and a query q(~x) with free variables ~x, we need to find some answers ~a such that D [ ⌃ ♣= q(~a) holds. In this setting, D consists of a set of facts that have been observed, ⌃ represents the domain knowledge, and q describes the question about which we need to inquire. A major topic in OQA is to identify proper languages for expressing ontologies ⌃.

Over the years, many languages have been developed for representing ontologies in OQA. In Description Logics, the DL-Lite family [Calvanese et al., 2007], EL family [Baader et al., 2005], and other variants have been proposed and extensively studied. More recently, existential rules, also known as data dependencies in Databases, and Datalog◦ in Knowledge Representation, have been rediscovered as a promising family of OQA languages, in which existential quantifiers, conjunctions and disjunctions may appear in the rule heads; see, e.g., [Baget et al., 2011; Cal`ı et al., 2012; Alviano et al., 2012; Bourhis et al., 2013]. It is also worth noting some work on expressing ontologies by second-order logic, see, e.g., [Fagin et al., 2005; Bourhis et al., 2015].

While all these languages are of their specific features and hence are useful in different problem domains, some natural questions imposed to us are: Do we need to implement each of them? Can we have a universal language for OQA? On the other hand, as there are a large number of building blocks that have been introduced for specifying ontologies, it would be also interesting to know which of them is necessary for specifying ontologies in OQA. In this work, we try to answer these questions. In particular, we would like to know whether there is an expressively complete language for OQA.

Expressive completeness is one of the major principles for designing languages in Computer Science and Logic. For example, almost all the traditional programming languages, including Prolog, are known to be Turing complete; propositional logic can express all boolean functions; and by the well-known Lindstr¨om theorem, first-order logic is as expressive as any logic that enjoys both the compactness and the L¨owenheim-Skolem property, see [Ebbinghaus et al., 1994]. In Databases, the first-order language is shown to be complete for all the queries decidable in AC0 , and Datalog complete for the PTIME queries, see, e.g., [Immerman, 1999].

Very recently, by regarding existential rules as traditional database query languages, Gottlob et al. [2014b] showed that weakly-guarded existential rules capture the class of EXPTIME queries, and Rudolph and Thomazo [2015] proved that tuple-generating dependencies capture the class of recursively enumerable queries. Both of these interesting characteraztions shed new insights on understanding the expressiveness of existential rules. However, it is also worth noting that, towards a full understanding of the expressiveness of OQA languages, treating them as traditional query languages is not enough. For example, many languages in the DL-Lite family are UCQ-rewritable, and almost all known tractable OQA languages are Datalog-rewritable; however, it is clearly not convenient to use UCQ and Datalog as OQA languages.

In this paper, we investigate the expressiveness of OQA languages in a more precise sense, and focus on Ontologybased Conjunctive Query Answering (OCQA), where conjunctive queries are used as the underlying query language. Our main contributions are as follows: Firstly, we propose a semantic framework for OCQA (Section 3). Such framework is general enough to unify different OCQA languages and hence can be used as a basis for studying the expressiveness of these languages for our purpose. In this framework, we then prove that disjunctive embedded dependencies (DEDs) precisely capture the class of recursively enumerable ontologies in OCQA (Section 4). Note that every set of DEDs can be rewritten as a set of disjunctive tuple-generating dependencies (DTGDs) and equality-generating dependencies (EGDs), two important classes of dependencies that have been extensively studied in OCQA. As an immediate consequence, our result implies a characterization of the expressiveness of DEDs as a traditional query language, which is similar to Rudolph and Thomazo's characterization [2015]. We also prove that neither DTGDs nor embedded dependencies (EDs) are expressively complete for recursively enumerable OCQA ontologies (Section 4). So the expressiveness between DEDs and DTGDs and EDs is explicitly differentiated. See [Zhang et al., 2016] for a full version of this paper with more details.

2 Preliminaries

Databases, instances and structures. We assume ∆c and ∆v as infinite disjoint sets of constants and variables, respectively. Terms are constants or variables. A relational schema R is a set of relation symbols, and each of which is equipped with a natural number as its arity. Every atom over R is either an equality or a relation atom built upon terms and relation symbols in R. A fact is a variable-free relation atom. Each instance over R is a set of facts over R. Instances that are finite are called databases. For any instance I, let adom(I) denote the set of constants occurring in I. Every structure A over R consists of a nonempty set dom(A), named its domain, and an instance I(A) over R such that adom(I(A)) ✓ dom(A). For convenience, sometimes an instance I will be regarded as a structure A such that dom(A) = adom(I).

Let R be a relational schema, A and B be structures over R, and C be a subset of dom(A) \ dom(B). A function h : dom(A) ! dom(B) is a homomorphism from A to B if, for all relation symbols R 2 R and all constant tuples ¯a of a proper length, R(h(~a)) 2 I(B) if R(~a) 2 I(A). We write h : A !C B if h is a homomorphism from A to B such that h(c) = c for all c 2 C, and write h : A )C B if h : A !C B and h is injective. To simplify the presentation, h will be dropped from the notations if it is clear from the context, and C will be dropped if it is empty. Furthermore, if h : A)B and an inverse g of h exists such that g : B ) A, we call h an isomorphism from A to B, and write h : A ⇠= B. Given a relational schema S ✓ R and an instance I over R, let I♣S denote the set of facts involving relation symbols in S only.

Queries and existential rules. Let R be a relational schema. By a query over R we mean a first-order formula built upon atoms over R as usual. Given a query q, let const(q) denote the set of constants that occur in q. A query is called boolean if it has no free variables. A conjunctive query (CQ) is a query of the form 9~y▷'(~x↪ ~y) where ' is a conjunction of relation atoms. Let BCQ be short for boolean CQ. For each BCQ q, we can regard it as a database by renaming existential variables as special constants and removing all quantifiers; let [q] denote such a database. Given a BCQ q, the graph of q is an undirected graph with each atom in q as a node, and with each pair of atoms as an edge if they share an existential variable. A BCQ is called prime if its graph is connected.

Every disjunctive embedded dependency (DED) over R is a first-order sentence σ of the following form:

where k ≥ 1, φ is a conjunction of relation atoms involving terms from ~x [ ~y only, each i is a conjunction of atoms involving terms from ~x [ ~zi only, and each variable in ~x has at least one occurrence in φ. In particular, σ is called an embedded dependency (ED) if k = 1, called a disjunctive tuple-generating dependency (DTGD) if it is equality-free, and called a tuple-generating dependency (TGD) if it is both an ED and a DTGD. The right-hand side of the implication is called the body, and left-hand side the head. Given a set ⌃ of DEDs, a relation symbol in the relational schema of ⌃ is called intensional if it occurs in the head of some DED in ⌃, and extensional otherwise. For simplicity, we will omit the universal quantifiers in σ, and replace "^" in the body by ",".

Let D be a database over ⌃ and q be a database, a set of DEDs and a BCQ, respectively, with a common relational schema R. We write D[⌃ ♣= q if, for all instances I over R such that D ✓ I, if I ♣= ⌃ then I ♣= q, where the satisfaction relation ♣= is defined as usual. Let p(~x) be a CQ over R with an n-tuple of free variables, the set of answers of p w.r.t. D under ⌃, denoted Ans(D↪⌃↪ p), is defined as the set of all n-tuples ~a of constants in adom(D) such that D[⌃ ♣= p(~a).

A modular lemma. Below let us give a simple property that will be useful to verify the correctness of the OQA programming. We need to recall some notions first. An instance I is called a minimal model of a set ⌃ of DEDs if I ♣= ⌃ and there exists no instance J ⇢ I such that J ♣= ⌃. Moreover, ⌃ is well-founded if for every instance J that satisfies ⌃, there is a minimal model I of ⌃ such that I ✓ J.

Lemma 1 (Modular lemma). Let q be a BCQ, and let ⌃ and Γ be two sets of DEDs such that ⌃ is well-founded and possibly involves constants, no relation symbol from the relational schema of ⌃ is intensional in Γ, and all relation symbols from the relational schema of q are intensional in Γ. Then ⌃ [ Γ ♣= q iff I [ Γ ♣= q for all minimal models I of ⌃.

3 OCQA ontologies

As mentioned earlier, our task is to establish the expressive completeness of languages for OQA. To do this, we first have to answer the following questions firstly: What is an ontology in OQA? Can we have a general and semantic definition for OQA ontologies so that different languages can be unified in the same framework? Below we will address these issues.

3.1 Some general properties

Most languages that have been proposed for OQA are logical languages, including description logics, first-order logic, and sometimes fragments of higher-order logic. So, to study general properties that should be enjoyed by OQA ontologies, it is natural to consider those for ontologies as logical theories.

Instead of considering a specific logical language, we will regard every logical theory as a class of structures.

Definition 1. Let R be a relational schema. An abstract theory over R is a class Φ of structures over R that is closed under isomorphisms, i.e., if A⇠=B andA 2 Φ, thenB 2 Φ.

It is clear that, given a concrete theory ⌃ in any of the logical languages proposed to represent ontologies, the class of all models of ⌃ is an abstract theory even if ⌃ is infinite.

Let R be a relational schema. Let D↪Φ and q(~x) be a database, an abstract theory and a query over R, respectively. Suppose k is the length of ~x. We let Ans(D↪ Φ↪ q) denote

Slightly abusing the notation, we will not distinguish between abstract and concrete theories (e.g., TGD sets) if no confusion occurs. For instance, notations like D [ Φ ♣= q will be used.

The following proposition gives us some useful properties.

Proposition 2. Let R be a relational schema; Φ be an abstract theory over R; D↪D0 be databases over R; and q↪ q0 are boolean queries over R. Then all the following hold:

1. If q ♣= q0 and D[Φ ♣= q then D[Φ ♣= q0 .
2. If D[Φ ♣= q and D[Φ ♣= q0 then D[Φ ♣= q ^ q0 .
3. If D )C D0 and D [Φ ♣= q then D0 [Φ ♣= q, where C denotes the set of constants occurring in q.

3.2 A semantic definition of OCQA ontology

With the properties we have presented, we are now in the position to give the semantic definition for ontologies in OQA. Note that our semantic definition is a refinement of the notion proposed by Arenas et al. [2014] where ontologies are regarded as arbitrary sets of database-query-answer triples.

Definition 2. Let D↪Q be relational schemas. Every quasiOCQA ontology over (D↪ Q) is a set of pairs (D↪ q) where D is a database over D and q is a BCQ over Q with const(q) ✓ adom(D). A quasi-OCQA ontology O over (D↪ Q) is called an OCQA ontology if all the following conditions hold:

1. O is closed under query conjunctions; that is, if both (D↪ q) 2 O and (D↪ q0 ) 2 O then (D↪ q ^ q0 ) 2 O.
2. O is closed under injective database homomorphisms; that is, if D )C D0 and (D↪ q) 2 O then (D0 ↪ q) 2 O, where C denotes the set of constants occurring in q.
3. O is closed under query implications; that is, if q ♣= q0 and (D↪ q) 2 O then (D↪ q0 ) 2 O.

Remark 1. Quasi-OCQA ontologies defined above provide a rather relaxed way to define abstract OCQA ontologies. This notion is slightly more restricted than Arenas et al.'s notion (i.e., database-query-answer pairs, see [Arenas et al., 2014]) as we require: (i) all the relational symbols involved in the database (resp., query) must belong to a given relational schema D (resp., Q), and (ii) each constant involved in the query must appear in the corresponding database. Since D and Q could be the same, the first assumption actually does not lose any generality. In addition, as usual in Databases, it is also reasonable to assume that only constants that occur in the database will be involved in the query answering.

Remark 2. It is worth noting that the quasi-OCQA ontology is a very loose notion to define abstract OCQA ontologies. In fact, it is not hard to show that there are many quasi-OCQA ontologies that are not definable by any logical theory. This is the reason why we define the notion of OCQA ontologies.

Definition 3. Let D↪Q↪R be relational schemas such that R ◆ D [ Q, and Φ be an abstract theory over R. We define Sem(Φ↪ D↪ Q) as the set of ordered pairs (D↪ q) such that D is a database over D, q is a BCQ over Q, and D [ Φ ♣= q. Given an OCQA ontology O over (D↪Q), we say that O is defined by Φ over (D↪ Q) if O = Sem(Φ↪ D↪ Q).

With the above definition, any logical theory Φ can be related to abstract OCQA ontologies. By Proposition 2, we

know that Sem(Φ↪ D↪ Q) is always an OCQA ontology.

Example 1. Let ⌃ be a set consisting of only the DED:

where s(i↪ k) denotes i + 1 if i < k, and 0 otherwise. Let Dk be the database ¶A(ai↪ as(i↪k)) : 0  i < k♦[¶A(as(i↪k)↪ ai) : 0  i < k♦. It is a routine task to check that D4 [⌃ ♣= Goal, and also easy to see that D3 [ ⌃ ♣= Goal does not hold.

Let D = ¶A♦ and Q = ¶Goal♦. Then Sem(⌃↪D↪Q) is an OCQA ontology which consists of pairs (D↪ Goal) for all databases D over D with a subset that is isomorphic to D4.⇤

In Definition 3, only BCQs are considered. However, in query answering, non-boolean CQs will be used. The following fact shows that no generality will be lost in our setting.

Proposition 3. Let D↪Q↪R be relational schemas such that D [Q ✓ R, and Φ↪ be abstract theories over R such that Sem(Φ↪D↪Q) = Sem( ↪D↪Q). Then for all databases D over D and CQs q over Q, Ans(D↪Φ↪ q) = Ans(D↪ ↪ q).

3.3 Expressive (in)completeness

Next, let us consider how to express arbitrary OCQA ontologies by DEDs. Due to a theoretical interest, we consider infinite sets of DEDs here. Such an investigation will provide a rational justification for our semantic definition.

Proposition 4. Let D↪Q be two disjoint relational schemas, and O be a quasi-OCQA ontology over (D↪ Q). Then O can be defined by a possibly infinite set of DEDs iff it is an OCQA ontology.

Proof (Sketch). The direction "only-if" is by Proposition 2. To show the converse, for each database-query pair from O, it is easy to construct a DED to generate its answers.

In the above result, the DED set could be infinite. A natural question arises as whether all OCQA ontologies can be defined by a finite set of DEDs. For quasi-OCQA ontologies, the answer is negative. This is because there is some quasiOCQA ontology which is highly undecidable, but query answering for finite sets of DEDs is recursively enumerable. 1 Naively, one might hope that the properties defining OCQA ontologies will get rid of the high undecidability. However, the following result tells us that this case will never happen.

Proposition 5. There is some (highly undecidable) OCQA ontology that is not definable by any first-order sentence.

Proof (Sketch). One can encode the recurring domino problem (⌃11 -hard [Harel, 1986]) by some OCQA ontology. Note that query answering with first-order sentences is in ⌃01 .

1 Note that DEDs are first-order sentences and that the inference validity of first-order logic is recursively-enumerable complete.

4 Recursively enumerable OCQA ontologies

In the last section, we have proved that the language consisting of finite sets of TGDs is not enough to capture the entire class of OCQA ontologies. This is not surprising because in the semantic definition of OCQA ontologies we do not consider whether the OCQA ontologies are realizable or not. In this section, we will focus on realizable OCQA ontologies, or more explicitly, recursively enumerable OCQA ontologies.

4.1 Machines that recognize OCQA ontologies

Before giving the characterizations, we first recall some notions and present a useful property. In the rest of this section, every nondeterministic Turing machine (NTM) is equipped with a read-only input tape and a read-write work tape. The head on the input tape will move right in all stages. Formally, an NTM M is defined by a 6-tuple (S↪ s0↪ A↪ Γ↪ ⇤↪ δ), where

• ÷ S is a finite and nonempty set of states, s0 2 S is the initial state, and A ✓ S is a set of accepting states;
• ÷ Γ denotes the alphabet ¶0↪ 1↪ ⇤↪ ]↪ ¯0↪ ¯1♦, 2 where "⇤" will be used as the blank symbol;
• ÷ δ : (S ⇥ Γ ⇥ Γ) ! P(S ⇥ Γ ⇥ ¶L↪R♦) is a transition function, where P(X) denotes the power set of X if X is a set. Every legal transition of M is a possible transition according to the transition function δ defined as usual.

Given an integer k > 0, we say that M is k-bounded if for every triple (s↪ a↪ b) 2 S⇥Γ⇥Γ we have that ♣δ(s↪ a↪ b)♣  k. In particular, if M is 1-bounded, we call M deterministic, or directly say that M is a deterministic Turing machine (DTM). It is well-known that every NTM can be simulated by a DTM.

Given a natural number k, let b(k) denote the binary representation (using "0" and "1") of k. We also fix D and Q as two relational schemas, D as a database over D, and q as a BCQ over Q. For ⇤ 2 ¶d↪ q♦, we let w⇤ and n⇤ denote the maximum arity and the number of relation symbols in R⇤, respectively. Let c denote the size of adom(D), and e denote the number of existential quantified variables in q. Now we encode (D↪ q) by the string, denoted by [[D↪ q]], as follows:

where tvt(D) is a binary string encoding all truth values of ground atoms (built upon adom(D) and D) w.r.t. D; tvt(q) is defined similarly by regarding q as a special database; and for a given string str, let str denote the string obtained from str by substituting ¯0 and ¯1 for 0 and 1, respectively.

Example 2. Suppose D = ¶D↪ E♦ andQ= ¶Q♦, where D↪ E are unary, and Q is binary. Suppose D is a database consisting of a single fact E(a), and q denotes the BCQ 9xQ(x↪ a). Then we can encode (D↪ q) by the string

where by the string "¯0¯1" we mean that the fact D(a) is false in D, and the fact E(a) is true in D; by the string "0010" (in the last block) we mean that the atom Q(x↪ a) has an occurrence in q, while atoms Q(a↪ a)↪Q(a↪ x) and Q(x↪ x) have not. ⇤

2 For a technical reason, we use two additional symbols "¯0" and "¯1" to represent special binary strings. It is easy to see that every NTM defined here can be simulated by one with a standard setting.

Definition 4. Let D and Q be relational schemas, and O be an OCQA ontology over (D↪Q). Then O is recognized by an NTM M if, for all databases D over D and all BCQs q over Q, (D↪ q) 2 O iff M accepts [[D↪ q]]; O is recursively enumerable if O is recognized by some deterministic NTM.

To establish the desired expressive completeness, we need to simulate Turing machines by existential rules. The first obstacle to implement such a simulation is the lack of negation in the bodies of existential rules so that it would be difficult to represent the information "a fact is false in the database". Below we present a novel technique to address this issue.

Let M be an abitrary NTM (S↪ s0↪ A↪ Γ↪ ⇤↪ δ). We call M convergent if δ(s↪ ¯0↪ b) ✓ δ(s↪ ¯1↪ b) for all states s 2 S and all symbols b 2 Γ. In other words, if M is convergent, then every legal transition of M on the input symbol ¯0 should be also a legal transition of M on the input symbol ¯1.

Now let us explain the general idea of representing the negative information in a given database. Suppose D is a relation symbol in the database schema and ⌧ is a transition of some convergent NTMM. Let φ⌧(~x) be a formula that describes the preconditions to implement the transition ⌧ (except for the information about the truth of D(~x)), and ⌧(~x) be a formula that defines the effect of implementing ⌧. If D(~x) is true in the database, one can simulate the transition ⌧ by the rule

For the case where D(~x) is false in the database, by the encoding of the input we know that the bit which encodes the truth of D(~x) is ¯0. Since M is convergent, ⌧ is legal for the case where D(~x) is false implies that ⌧ is legal for the case where D(~x) is true. Thus we can now simulate ⌧ by the rule

According to the definition of the convergent NTM, it is easy to see that Rules (6) and (7) will always implement consistent actions. Note that no negation is involved in the simulation.

Now, let us present an interesting observation that will play an important role in establishing the main characterization.

Proposition 6. Every recursively enumerable OCQA ontology can be recognized by a convergent, 2-bounded NTM.

Proof. Let O be a recursively enumerable OCQA ontology. Then there is a DTM, say M, that recognizes O. We assume M = (S↪ s0↪ A↪ Γ↪ ⇤↪ δ). Let δc be defined as follows:

Now let Mc = (S↪ s0↪A↪ Γ↪⇤↪ δc). It is easy to see that Mc is a convergent and 2-bounded NTM. So, it remains to show that Mc also recognizes O. Given any input, it is clear that all accepting paths of M are accepting paths of Mc. Thus, Mc accepts all inputs [[D↪ q]] such that (D↪ q) 2 O.

Conversely, let (D↪Q) be the relational schema pair of O, D be a database over D, and q be a BCQ over Q such that Mc accepts the input ins = [[D↪ q]]. We want to show that (D↪ q) 2 O. Let P be an accepting path that accepts ins. Let ins0 be a string defined as follows: If ¯1 is scanned in the i-th stage of P, and the next transition is not implemented by original actions in δ, then let the i-th symbol of ins0 be ¯0, otherwise let it be the same as that of ins. It is easy to see that ins0 encodes a pair (D0 ↪ q) such that D0 )C D where C denotes adom(D). Moreover, it is not hard to verify that ins0 will be accepted by the original machine M, which means that (D0 ↪ q) 2 O. Since O is closed under injective database homomorphisms, we obtain that (D↪ q) 2 O as desired.

4.2 Expressive (in)completeness

In the following we present the main theorem, which states that the disjunctive embedded dependencies are expressively complete for recursively enumerable OCQA ontologies.

Theorem 7. Let D↪ Q be two disjoint relational schemas, and O be a quasi-OCQA ontology over (D↪Q). Then O can be defined by a finite set of DEDs iff it is a recursively enumerable OCQA ontology.

We leave the proof of this theorem to the next section.

Now, let us first present an interesting implication of our characterization. Some notions are needed. Fix R as a relational schema. A database query over R is a class of databases over R that is closed under isomorphisms. Similar to that in [Rudolph and Thomazo, 2015], let Goal be a special nullary relation symbol which does not belong to R. A database query Q is called defined by a set ⌃ of DEDs if we have D 2 Q iff D [ ⌃ ♣= Goal. By Theorem 7, we then have a characterization for classical database queries, which is similar to Rudolph and Thomazo's characterization [2015]:

Corollary 8. A database query Q is defined by a finite DED set iff Q is recursively enumerable and closed under injective homomorphisms, i.e., D 2 Q and D!D0 implies D0 2 Q.

Next, let us consider the following question: Can the main theorem be established for a simpler language? For example, can equalities (resp., disjunctions) be removed so that DTGDs (resp., EDs) are still expressively complete? The following propositions show that, to assure the expressive completeness, neither disjunctions nor equalities can be removed.

Let us first define a notion. An OCQA ontology O over a relational schema pair (D↪Q) is called first-order rewritable if for all BCQ q over Q there is a first-order sentence qO such that (D↪ q) 2 O iff D ♣= qO for all databases D over Q. With this notion, we are then in the position to present the results.

Proposition 9. There is a first-order rewritable OCQA ontology that cannot be defined by any finite set of DTGDs.

Proposition 10. There is a first-order rewritable OCQA ontology that cannot be defined by any finite set of EDs.

Proposition 9 can be proved by showing that every OCQA ontology defined by DTGDs is closed under database homomorphisms. Example 1 gives a first-order rewritable OCQA ontology that is not closed under database homomorphisms. The next proposition can be proved by showing that the complement of every OCQA ontology defined by EDs is closed under direct products; however first-order rewritable OCQA ontologies that do not have this property can be easily found.

Remark 3. The above incompleteness results show why disjunctions and equalities should be considered in identifying new first-order rewritable and tractable OCQA languages.

5 Proof of the main theorem

From now on, let us focus on the proof of Theorem 7. The direction "only-if" follows from Proposition 2 and the wellknown fact that the inference validity of first-order logic is recursively-enumerable complete. So, in this section we only consider the converse, which will be proved by constructing a finite set of DEDs. We first explain the general idea of the construction, and then implement it step by step.

5.1 General idea of the proof

In Databases, to show a language is expressively complete for a class of database queries in a certain level of complexity, a usual way is by constructing logical theories to simulate Turing machines, see, e.g., [Vardi, 1982; Rudolph and Thomazo, 2015]. However, it should be noted that establishing the expressive completeness of OQA languages is significantly different from that of classical querying languages.

The main difficulty is as follows: Although the BCQ is one part of the input for the query answering, the logical theory that simulates the query answering actually cannot access the BCQ, which means that, instead of focusing on one decision problem, we have to treat an infinite number of decision problems. Note that there are an infinite number of BCQs.

Fortunately, we have found a novel technique to overcome these obstacles. To explain it, we first define some notations, and then present a property. Let R be a relational schema, D be a class of databases over R, and C be a set of constants. We let LC D denote the instance S¶D⇤ : D 2 D♦ where, for every D 2 D, D⇤ is an isomorphic copy (a database over R) of D such that, for any pair of distinct databases D1↪D2 in D, only constants from C will be shared by D⇤ 1 and D⇤ 2 .

The following is a key lemma to our proof.

Proposition 11. Let D↪ Q be relational schemas, and O be an OCQA ontology over (D↪Q). Then for all databases D over D and BCQs q over Q, (D↪ q) 2 O iff UO(D) ♣= q, where UO(D) = LC ¶[q0 ] : (D↪ q0 ) 2 O♦ and C = adom(D).

Proof. The direction "only-if" is trivial; so we only show the converse. Let q be a BCQ over Q and D be a database over D such that UO(D) ♣= q. By definition, there exists a homomorphism h from [q] to UO(D) such that h(c) = c for all constants c from C. Let q0 be a BCQ obtained from q by substituting h(x) for all variables x such that h(x) 2 C, and let h0 be a restriction of h to all variables and constants occurring in q0 . Then it is clear that q0 ♣= q and that h0 is a homomorphism from [q0 ] to UO(D). Without loss of generality, let us write q0 in the form q01 ^ · · · ^q0k , where k ≥ 1 and each q0i is prime (see Section 2 for the definition). Take i 2 ¶1↪ ▷ ▷ ▷ ↪ k♦. Obviously, h0 is a homomorphism from [q0i ] to UO(D). Since q0i is prime, by the definition of UO(D) we know that there is at least one BCQ pi such that (D↪ pi) 2 O and that h0 (q0i ) is contained in the disjoint copy of pi in UO(D). From the latter we conclude that pi ♣= q0i . Since O is closed under query implications, we infer that (D↪ q0i ) 2 O. Furthermore, since O is closed under query conjunctions, we obtain that (D↪ q0 ) 2 O. As we have proved previously, it holds that q0 ♣= q. Again by the query implication closure of O, we conclude that (D↪ q) 2 O, which completes the proof.

With the property above, we call UO(D) a universal model of O w.r.t. D. Now, let us explain the general idea of our proof. From now on, let us fix D and Q as two disjoint relational schemas, and O as a recursively enumerable OCQA ontology over (D↪Q). Our task is to construct a finite set ⌃ of DEDs such that, for any given database D over D, UO(D) is isomorphic to the minimal model of D [ ⌃.

1. Simulate the computation of M on input ins = [[D↪ q]].

Now, we show how to construct the set ⌃ of DEDs. Suppose M is a Turing machine which recognizes O. For all possible BCQs q over Q, we let ⌃ work as follows:

1. If M accepts ins then copy [q] to the intended model.

To implement the simulation of M, we have to define natural numbers on the intended domain, which can be done in DEDs easily. Another difficulty is to encode negative information in the database as existential rules have no negations (see [Rudolph and Thomazo, 2015]). Thanks for the power of Proposition 6, this again can be overcome in a natural way.

5.2 Defining numbers and arithmetic relations

To define numbers and arithmetic relations, we have to generate a successor relation first. In particular, we require that the successor relation will travel over all the constants from the database so that every fact in the database could have a fixed encoding. Let DC be a fresh unary relation symbol that collects all the constants occurring in the intended database, which can be defined by the following DEDs:

for all relation symbols Di from the schema D, where k denotes the arity of Di. Let ⌃s denote the set that consists of all the DEDs which define DC and all the following DEDs:

where Succ(x↪ y) asserts that y is an immediate successor of x, and LT(x↪ y) states that x is strictly less than y. In this way, a linear order would be arbitrarily generated by disjunctions in DED (10) and the existential quantifier in DED (17). Note that the linear order generated by such disjunctions and existential quantifier is not always good - sometimes a cycle could be there. In this case, we simply set the nullary relation Undesired true. As we will see later, this flag will lead to giving up the intended instance under the current focus.

If the flag Undesired is false, by the transitivity and irreflexivity, we know that LT is a linear order. Thus, we have:

Proposition 12. Let D be a database over D. ThenD[⌃s is well-founded, and for each minimal model I of D [ ⌃s with Undesired 62 I, Succ defines an infinite successor relation on adom(I), Min defines the minimum element w.r.t. Succ, and Num defines the set of all elements from adom(I).

With the above relations, we can define relations such as Add, Mul, Bitb and Len, where b 2 ¶0↪ 1♦, Add(x↪ y↪ z) (Mul(x↪ y↪ z), respectively) asserts that z is the sum (product, respectively) of x and y, Bitb(x↪ y) asserts that the y-th bit of the binary representation of x is b. All of these can be defined in a routine way. For example, the addition relation can be defined by the following DEDs:

Finally, we let ⌃num denote the union of ⌃s and the set of all DEDs that define the mentioned arithmetic relations.

5.3 Simulating Turing machine

Now, we are ready to define some DEDs to simulate the Turing machine. According to Proposition 6, we only need to simulate a convergent, 2-bounded NTM M. As mentioned previously, we will simulate the computations of M on all possible input queries in parallel. Towards this end, we introduce a number of relation symbols ITapea, WTapea, IHead, WHead and States, where a is a symbol in the alphabet, and s is a state. For example, ITapea(x↪ y) asserts that, in the computation for the BCQ encoded by y, the symbol written on the input tape at position x is a; States(x↪ y↪ z) asserts that, in the computation path (encoded by) y for BCQ (encoded by) z, the state of M in time x is s. Note that, as M is 2-bounded, the (nondeterministic) choices of all stages can be represented by a binary string in an obvious way.

The simulation of M consists of three parts as follows.

Initialization. This part includes specifying the initial state, copying the string encoding a database-query pair to the input tape, and filling unused cells with the blank symbol. We only focus on the second one here. The other two are trivial.

Suppose relation symbols allowed in database (resp., BCQ) list as D0↪ ▷ ▷ ▷ ↪Dm-1 (resp., Q0↪ ▷ ▷ ▷ ↪Qn-1). We first introduce some fresh relation symbols PosDi and PosQj, where 0  i < m, 0  j < n, PosDi (resp., PosQj) is of arity k+1 if Di (resp., Qj) is k-ary. Informally, PosDi(~x↪ y) asserts that the truth value should be copied to the y-th cell of the input tape; the meaning of PosQj is defined similarly. Since it is a folklore in the KR community as how to define such relations by arithmetic relations, we omit the details here.

The DEDs below are designed to copy the database:

At a first glance, the above encodings seem problematic since ITape¯0(z↪ x) and ITape¯1(z↪ x) might be true simultaneously. However, by the convergence of M and the analysis in Subsection 4.1 we know that this does not lead to any trouble.

Next, let us fix the way to encode BCQs (e.g., the G¨odel numbering). By the arithmetic relations, we can define relations BCQ, HasQi and NHasQi for all proper indices i such that BCQ(x) asserts that x encodes some BCQ over Q, and HasQi(~x↪ y) (resp., NHasQi) asserts that Qi(~x) appears (resp., does not appear) in the BCQ encoded by y. To copy the focused BCQ, we use the following DEDs:

Transition. Simulating transitions of M is almost the same as that in the classical case, see, e.g., [Dantsin et al., 2001; Baget et al., 2011]. The only difference here is that we have to treat nondeterminism. It should be noted that this cannot be directly encoded by disjunctions. However, we can first guess a number which encodes the action choices in all transitions, and then simulate the computation on these choices, which is deterministic and can be encoded in a routine way. Note that the "guess" will be implemented in the next part.

To carry out the idea, as mentioned in the begining of this subsection, for each relation contributing to defining the computation path, we use an additional argument to specify (the number encoding) the choices. Without loss of generality, let δ(s↪ c) = ¶(s0↪ c0↪ d0)↪ (s1↪ c1↪ d1)♦ be a transition of M. Let φi(x↪ ~y) ! i(~z) be a DED to simulate the deterministic transition δ(s↪ c) = (si↪ ci↪ di) in the x-th stage of the computation. Now, our transition can be simulated by

for all i 2 ¶0↪ 1♦, where φ0i and 0i are obtained from φi and i, respectively, by adding the argument v to related atoms. Intuitively, these DEDs assert that M will perform the first action if the x-bit of v is 0, otherwise M will carry out the second one.

Acceptance. Since M is nondeterministic, to describe that M accepts an input, we have to state that there is an accepting state that can be reached from the initial state via a sequence of action choices (encoded by a number). To implement this, for each accepting state s, we construct a DED as follows:

Finally, let ⌃sim consist of all DEDs defined in this subsection. Then we have an encoding to simulate machine M.

Proposition 13. Let D be a database over D, and I be a minimal model of D[⌃num[⌃sim such that Undesired 62 I. Then, for all a 2 adom(I), Accept(a) 2 I iff a encodes a BCQ q over Q (in the fixed way) such that (D↪ q) 2 O.

5.4 Generating universal model

Now it remains to show how to generate the universal model UO(D). Let a be a number that encodes a BCQ q such that Accept(a) is true in the intended instance. For all atoms ↵ over Q, we first test whether ↵ appears in q. If the answer is yes we then copy ↵ to the universal model. Since UO(D) is defined by a disjoint union of [q], a renaming of variables in q would be necessary. As variables are encoded by numbers, the renaming can be carried out by mapping a number to another number that is big enough. It is easy to see that the desired mapping can be defined by arithmetic relations.

With this assumption, we introduce two fresh relation symbols QVar and NewV where QVar(y↪ x) asserts that y is an existential variable which appears in the BCQ encoded by x, and NewV(y↪ z↪ x) asserts that the variable y which appears in the BCQ encoded by x will be mapped to z. Now, we use them to define a new relation Name, where Name(y↪ z↪ x) means that y will be replaced with z in the copy of the BCQ encoded by x. Below are the DEDs that implement it.

where the second one means that we do not change constants.

Next, to copy all the atoms that appear in the BCQ to the intended universal model, we employ the following DEDs:

In addition, let us focus on an instance which defines a bad successor relation. To avoid changing the semantics, we have to force the instance to accept all BCQs, which can be done by defining the following DED for each k-ary Qi:

Finally, let ⌃um denote the set of all DEDs defined here.

Proposition 14. Let D be a database over D, and let I be a minimal model of D [ ⌃num [ ⌃sim [ ⌃um such that Undesired 62 I. Then I♣Q is isomorphic to UO(D).

Now, by Propositions 11 and 14 we have Theorem 7.

6 Related work and discussions

Rudolph and Thomazo [2015] identified an elegant characterization for the expressiveness of TGDs, which asserts that TGDs define all the recursively enumerable database queries which are closed under homomorphisms. However, TGDs there are treated as a classical database query language. Our work focuses on the expressiveness of DEDs as a language for ontology-based query answering. As an immediate consequence, we have also established a characterization for the expressiveness of DEDs as a classical query language.

Gottlob et al. [2014a] proved that an ontology expressed by a finite set of TGDs and negative constraints (NCs) admits first-order rewritings if, and only if, it can be expressed by a finite set of TGDs and NCs that enjoys the bounded derivation depth property, which can be regarded as a relative expressive completeness w.r.t. a semantic class of existential rules. It would be interesting to know whether their characterization can be generalized to arbitrary OCQA ontologies. Zhang et al. [2015] showed that every TGD set with finite Skolem chase can be rewritten as a weakly-acyclic one, which is known as another relatively expressive completeness result.

It is also worth mentioning some other work related to ours. Gottlob et al. [2014b] showed that, as a classical query language, the weakly-guarded TGDs with stratified negations capture the class of queries decidable in EXPTIME. Arenas et al. [2014] proposed an interesting notion called program expressive power, and used it to compare the expressiveness of several ontological languages. Our framework for OCQA ontology can be regarded as a significant refinement of theirs.

The idea presented in this paper may be applied to other languages. For example, we can use it to prove that TGDs capture all recursively enumerable OCQA ontologies that are closed under database homomorphisms. The only additional difficulty is how to define a linear order by TGDs, which can be achieved by using some techniques from [Rudolph and Thomazo, 2015; Gottlob et al., 2014b]. Our work may shed a new light on identifying decidable languages for OCQA, and in particular on identifying an expressively complete language for first-order rewritable or tractable OCQA if it exists.

Acknowledgements

We would like to thank anonymous referees for their helpful comments and suggestions for improving the paper. The first author's research was partially supported by the National Natural Science Foundation of China under grants 61173170, 61300222, 61370230, 61433006, 61572221 and U1401258.