Characterization of the Expressivity of Existential Rule Queries

1 Introduction

The field of logic-based knowledge representation comprises a great variety of formalisms for specifying and querying knowledge. Given the tradeoff between declarative expressivity on the one hand and computational cost on the other hand, there is no unique formalism universally deployable in all of the numerous different usage scenarios. Thus, the available formalisms need to be categorized along the dimensions of expressive power and hardness of computation. For both aspects, the categorization can be relative or absolute.

Considering relative expressivity means to ask if every sentence or query 1 of one logic formalism can be equivalently expressed in the other. Investigating relative computational properties means to determine if the satisfaction problem in one formalism can be translated into the satisfaction problem in the other formalism using appropriate reductions (such as many-to-one or Turing reductions).

∗Research supported by the Alexander von Humboldt Foundation.

While these comparative investigations allow to relate and rank the considered formalisms, absolute characterizations typically provide much more profound insights into the true nature of logical languages. Absolute results relate logical formalisms to external measures of expressivity and computation. Among other benefits, such findings help establishing non-expressibility and non-reducibility results which are hard to obtain otherwise.

An absolute computational characterization of a logical formalism is achieved by determining the complexity or decidability or recursive enumerability of the corresponding satisfaction problem. Proving such computational properties of a given formalism is often a standard exercise. Contrariwise, showing that a logical formalism is capable of expressing every query exhibiting certain computational properties is usually a nontrivial undertaking and constitutes the subject of the field of descriptive complexity theory [Immerman, 1999]. As an example result from that line of research, it was established that first-order logic sentences exactly correspond to the properties of interpretations verifiable in AC0 , i.e., they can be checked by polynomial-size Boolean circuits of bounded depth.

One way of absolutely categorizing expressivity aspects of logical languages in a syntax-independent way, is via modeltheoretic considerations. Intuitively, a formalism is more expressive than another if it allows for distinguishing two interpretations which are indistinguishable by the other formalism. Indistinguishability often can be characterized by the set of models of a certain type of queries being closed under certain operations. Examples for this are manifold: closure under intersection for Horn logics, bisimulation invariance in modal logics, closure under disjoint union of firstorder sentences where no universal quantifier occurs inside the scope of an existential quantifier, and many more (see, e.g., [Chang and Keisler, 1973] for more examples). A very natural such property is closure under homomorphism. It particularly holds for query languages that are supposed to check if substructures of a certain shape exist in an interpretation or database, a prominent example being Datalog and its various fragments (cf. [Rudolph and Kr¨otzsch, 2013]). While it is typically not difficult to establish that such a model class closure property holds for a logical formalism, showing a converse property tends to be much more intricate. Next to a few others, a classical example of such a non-trivial result is the Lyndon-Łos-Tarski-Theorem stating that the set of models of a first-order sentence is homomorphism-closed if and only if it can be expressed in positive existential first-order logic, i.e., without using negation or universal quantification.

1 Since we are only concerned with satisfaction, we do not distinguish between the notions of a logical sentence and a (Boolean) query in this paper. All queries dealt with in this paper are assumed to be Boolean.

Inspecting this last result, we find that the obtained characterization of positive existential first-order logic is still somewhat relative since it refers to general first-order logic. However, with the aforementioned descriptive complexity result in place, one could combine the model-theoretic and the computational perspective to arrive at a characterization not referring to any other logical formalism: The class of queries expressible in positive existential first-order logic coincides with the class of queries that can be evaluated in AC0 and whose set of models is closed under homomorphisms.

After making clear the general motivation and the thrust of our investigation by means of this low-level example, we now set out to achieve an absolute characterization for a very expressive formalism which has drawn a lot of attention in the last years: existential rules, which are known under a variety of other names (tuple-generating dependencies [Abiteboul et al., 1994], Datalog± [Cal`ı et al., 2013], conceptual graph rules [Mugnier, 2009]). Their original use was to impose integrity constraints on a database, but they have been more recently used as a modeling language for ontologies. This formalism can also be seen, as in this paper, as a query language, as it was originally the case for its parent, Datalog, the language of deductive databases.

Surprisingly enough, an absolute characterization of plain existential rule queries has not been attempted so far. Trivial upper bounds can be proposed: First, the well-known chase procedure constitutes a semi-decision procedure for answering existential rule queries. Consequently, the set of finite relational structures (also referred to as databases) satisfying an existential rule query must be recursively enumerable. 2 Second, it is well-known and easy to show that this set is also closed under homomorphisms. The central contribution of this paper is to show that these two conditions together are in fact tight: any query Q, where the set of databases satisfying Q is both recursively enumerable and closed under homomorphisms, is equivalent to an existential rule query. Thereby, we arrive at the wanted characterization:

A query is expressible with existential rules iff its set of satisfying databases is recursively enumerable and homomorphism-closed.

2 More precisely, we should say recursively enumerable up to isomorphism. To avoid these technicalities, we assume the individuals of databases to come from a countably infinite reservoir of standard names.

While this result fits very well with intuition and may seem rather straightforward, establishing the "if" part is not at all trivial. To prove it, we simulate the computation of a Turing machine recognizing a query with the given properties. 3 Simulating a Turing machine given a correctly represented tape is classical with existential rules [Baget et al., 2011a]. However, creating the representation of a tape from a database only through the use of existential rules requires some work. Indeed, existing techniques to create such a tape heavily rely on the use of two ingredients: a linear order on the elements of the domain, and a restricted form of negation. The first is in particular used to enumerate tuples, while the second is used to check the absence of facts. The most prominent use of these ingredients may be the capturing result of PTIME queries by semi-positive Datalog on linearly ordered databases [Abiteboul et al., 1994].

Instead of considering a linear order, the existential rule query that we define for a given Turing machine will generate all finite lists containing elements of the domain. Some of these lists do not correspond to a linear order of the domain elements. We will present in Section 3 how to create a Turing machine tape from a database and such a list. An important question that needs to be tackled is the following: is it problematic if a Turing machine accepts when the tape has been created based on an enumeration that was not a linear order? Answering this question negatively is the topic of Section 4.

Last, we will need, given an enumeration of the terms of a database, to generate the corresponding tape. Without input negation, it is not possible to create a unique tape containing exactly the information corresponding to the actual database. Instead, we generate all possible databases on a given vocabulary. From all those "database candidates", we single out those databases inconsistent with the initial data. We then run the Turing machine on the tape corresponding to each candidate. We show that if each candidate is either inconsistent with the original data or leads to an accepting state of the Turing machine, then the query recognizes the structure parameterized by the enumeration. This is the topic of Section 5. Proofs not presented here are available at: https://ddll.inf.tudresden.de/web/Techreport3019/en.

2 Preliminaries

We assume the reader to be familiar with Turing machines (see [Papadimitriou, 1994] or [Arora and Barak, 2009]). A language is recursively enumerable if there is a Turing machine that accepts on any word of the language and does not terminate on any word that does not belong to the language. We are interested in decision problems on databases: the encoding of the database on a Turing machine tape is of importance. We describe the considered encoding in Section 3.

We consider two countable disjoint sets V and ∆ of variables and domain elements, respectively. Elements of V ∪∆ are also called terms. We consider two finite disjoint sets Pi and Pe of intensional predicates and extensional predicates. Each predicate is either intensional or extensional and possesses an arity n ∈ N. We assume w.l.o.g. that all extensional predicates have the same arity k. An atom is an expression a of the form p(x1, . . . , xn) where p is a predicate of arity n and x1, . . . , xn are terms. The terms of a are denoted by terms(a). The terms of a set of atoms A are defined by ∪a∈Aterms(a). Given two sets of atoms A and B, a homomorphism from A to B is a mapping π from terms(A) to terms(B) such that if p(x1, . . . , xn) ∈ A, then p(π(x1), . . . , π(xn)) ∈ B. An isomorphism from A to B is a bijective homomorphism π from A to B for which π-1 is also a homomorphism. A database (on some set P of predicates) is a finite set D of atoms with terms from ∆ and predicates from P. We assume (w.l.o.g.) that there exists a predicate p ∈ Pe, denoted by ACDom such that ACDom(x) holds for every term x ∈ terms(D). Given a set of extensional predicates Pe, a (Boolean) query is a subset of the databases on Pe that is closed under isomorphism. 4 A query q is said to be closed under homomorphism if for all D1 ∈ q, if there is a homomorphism from D1 to D2, then D2 ∈ q. An existential rule is a first-order formula of the form

3 As made more formal later, it is convenient to "semantically identify" a query with the set of databases satisfying it. This justifies to speak of a query itself being recognized by a Turing machine or closed under homomorphisms or recursively enumerable. For the sake of brevity, we will make extensive use of such wordings.

where ¯x, ¯ y and ¯ z are tuples of variables, B is a conjunction of atoms (of intensional or extensional predicates) such that terms(B) = {¯x, ¯ y} and H is a conjunction of atoms (of intensional predicates) such that terms(H) = {¯ y, ¯ z}. A rule ∀¯x ∀¯ y B[¯x, ¯ y] → ∃¯ z H[¯ y, ¯ z] is applicable to a database D if there is a homomorphism from B to D. The result of this application is a new database D ∪H′ , where H′ is equal to H with each variable replaced by its image under π if defined, and by a some "new element" from ∆ \ terms(D). We now briefly introduce the chase [Maier et al., 1979; Beeri and Vardi, 1984]. Given a set of existential rules R, a breadth-first application of applicable rules generates a potentially infinite sequence of databases. Their union is uniquely defined (up to homomorphic equivalence) and is called the Rchase of D with respect to R. We call the domain elements present in the chase but not in the original database (i.e., those added by some rule application) fresh elements.

An existential rule query qR is a query represented by a set R of existential rules with a special predicate goal. A database D belongs to this query if goal belongs to the chase of Dwith respect to R. It is clear that existential rule queries are closed under homomorphisms. Moreover, as constructing the chase and continuously checking for containedness of goal is a semi-decision procedure for D ∈ qR, these queries are also recursively enumerable.

For the sake of brevity, we will from now on omit quantifiers from existential rules, adopting the following convention: all variables occurring in the body B are universally quantified, all others existentially quantified.

4 This definition reflects the common understanding of a query that it "[...] should be independent of the representation of the data in a data base and should treat the elements of the data base as uninterpreted objects" [Chandra and Harel, 1980]. This understanding also justifies why we do not distinguish the domain elements into constants and labeled nulls, as it sometimes done in the literature, and why we do not allow for constants in existential rules.

3 TuringMachine: Tape Representation

In this section, we describe the tape representation used to simulate a Turing machine with existential rules. We split the presentation in two: first, we describe how to transform a database (i.e., a set of facts, endowed with some additional structure) into a linearized tape representation. Second, we explain how to represent such a tape as a relational structure and how to simulate the Turing machine using existential rules.

3.1 Tape Representation of a Database

To represent deterministically a database on a tape, we make use of a linear order on its terms. However, since we do not have access to a linear order, we present a more general transformation associating a database and a sequence (potentially with repetitions) of its terms with a tape. Let us thus consider a database D and ℓ a sequence of its domain elements. The elements of ℓ are denoted by the binary representation of their rank in the sequence. Let us remark that this implies that a single domain individual of the database may have several representations, as seen in Example 1.

Definition 1 (D-list) Let D be a database. A D-list is a sequence (possibly with repetitions) of terms of D, denoted by (t1, . . . , tn). A representation of a term t of D appearing in a D-list ℓ is a binary representation of a rank of t in ℓ.

Since a term may appear several times in a D-list, it may thus have several representations.

Example 1 (Representations of an individual) Let {a, b} be the domain elements of a database D. A D-list is (a, b, a, a). Thus, a has three representations, 00, 10 and 11, while b has one representation 01.

A D-list naturally induces a linear order on the binary representations of its elements. We next describe how, relying on ℓ, we can come up with a tape representation of D. Remember that we assume w.l.o.g. that all our database predicates have a uniform arity of k. The linear order on representations in ℓ induces a linear order on k-tuples of representations in ℓ which we use for constructing our tape: after a "beginning of tape" symbol (#), we start from the first k-tuple according to the mentioned order, write some information about it, and proceed to the next tuple until the last tuple is treated. For each tuple (r1, . . . , rk) of representations, we write for each predicate (in lexicographic order) p if p(t1, . . . , tk) holds in D or not, where where t1, . . . , tk are the domain elements represented by r1, . . . , rk, respectively.

Example 2 Let us consider a database De having as domain {a, b} and two facts: r(a, b) and p(a, a). We consider the following D-list, which is a linear order : (a, b). The representation is the following:

#p1r0p0r1p0r0p0r0

The first p1 means that p(a, a) holds. The first r0 means that r(a, a) does not hold. The rest is interpreted similarly.

Given a database D and a D-list ℓ, we will denote by T (D, ℓ) the tape representation that we described so far.

Last, we already pointed out that Turing machines work on strings that are representations of the input. More specifically, by a recursively enumerable query q, we mean a query for which there exists a Turing machine Mq which recognizes the following language:

{T (D, ℓ) | D is contained in q and

ℓ is a linear order on the elements of D}.

3.2 Encoding a Tape in a Database

We now describe how a tape T (D, ℓ) is represented by means of database atoms.

Definition 2 (Relational representation of T (D, ℓ)) Let D be a database and let ℓ be a D-list. Let n be the number of extensional predicates and t the number of tuples. The relational representation of the tape T (D, ℓ) is given by the following atoms over some domain individuals db (representing the database itself) and cell0, . . . , cell2nt (representing the tape cells) using the predicates begin (binary, associating the database-representing individual with the first tape cell), next (binary, associating each tape cell with the subsequent one), as well as, for every symbol σ that might occur on the tape, symbolσ (unary, used to assign to each cell its content):

• begin(tape, cell)
• symbol#(cell0)
• next(cell i, cell i+1) for every i < 2n(t + 1)
• symbolp (cell2nj+2i) for p being the ith predicate and j ≤ t
• symbol1 (cell2nj+2i+1) if p(t1, . . . , tk) holds for the ith predicate p and jth tuple (r1, . . . , rk) representing (t1, . . . , tk)
• symbol0 (cell2nj+2i+1) if not symbol1 (cell2nj+2i+1).

Given such a representation of T (D, ℓ) and an according representative xℓ of ℓ, crafting a set of existential rules RMq that simulate a given Turing Mq machine on that tape and derive rec(db, xell) exactly if Mq accepts T (D, ℓ) is common knowledge. The interested reader can consult [Baget et al., 2011a] for this.

4 Correct and Incorrect Orderings

In the previous section, we presented the tape representation of a pair (D, ℓ), where D is a database and ℓ a D-list. We now present how to create D-lists through existential rules. We make use of the predicate ACDom that holds for each individual of the database.

Definition 3 (List annotator) The list annotator, denoted by Ra is the following set of rules:

• ACDom(x) → link(x, y) ∧ first(y) ∧ last(y)
• ACDom(x) → link(x, y) ∧ first(y) ∧ partial(y)
• ACDom(x) ∧ partial(y) → succ(y, z) ∧ link(x, z) ∧ partial(z)
• ACDom(x) ∧ partial(y) → succ(y, z) ∧ link(x, z) ∧ last(z).

Intuitively, the list annotator makes, for every D-list ℓ, the representations of ℓ available as additional domain elements in our database, defines a unary predicate first to mark the first element of ℓ, a unary predicate last to denote the last, a binary predicate succ which connects a representation element with its immediate successor and a binary predicate link which links a representation element back to the original domain element it represents in ℓ. Note that, with these predicates in place, it is classical (see for instance [Abiteboul et al., 1994]) to specify Datalog rules that define a linear order on the set of all k-tuples of representation elements, (where k is the maximum arity of a predicate in the original database).

Definition 4 (Representative of a D-list) Let D be a database, and ℓ = (a1, . . . , an) be a D-list. Assume there are fresh elements x1, . . . , xn such that:

• first(x1) and last(xn) hold in D;
• for all i such that 1 ≤ i < n, succ(xi, xi+1) holds in D;
• for all i such that 1 ≤ i ≤ n, link(ai, xi) holds in D;
• no other atom of predicates last, succ, link has some xi as argument.

Then xn is called a representative of ℓ.

Example 3 (ℓ-annotation) Figure 1 shows part of the structure that is created by the list annotator on the database p(a, a) ∧ r(a, b). xℓ is a representative of the D-list (a, b, b).

The list annotations that interest us are the ones that correspond to some linear order. However, given the list annotator introduced, many more will be generated: domain elements might be left out or referenced multiple times. This raises the following question: if q is a homomorphism-closed query, Mq is a Turing machine for q, is it possible that Mq accepts T (D, ℓ) for some pair (D, ℓ), while D does not belong to q? In other words: may the creation of annotations that do not correspond to proper linear orders lead to "false positives"? Luckily, we can answer this question negatively, where the intuitive argument is the following: with each pair (D, ℓ), we associate a pair (D′ , ℓ′ ) such that T (D, ℓ) = T (D′ , ℓ′ ), with the additional condition that ℓ′ is a linear order on a subset of the domain elements of D′ . Therefore, Mq accepting T (D′ , ℓ′ ) proves that D′ belongs to q. Then by showing that there is a homomorphism from D′ to D allows to conclude that D, in fact, belongs to q.

Definition 5 (Singularized Database) Let D be a database instance, let ℓ be a D-list. The singularization sing(D, ℓ) = (D′ , ℓ′ ) of D with respect to ℓ is defined as follows:

• ℓ′ has the same length as ℓ, and the ith element of ℓ′ is the ith element of ℓ with an additional i superscript,
• p(xi1 1 , . . . , xik k ) ∈ D′ iff p(x1, . . . , xk) ∈ D.

Example 4 Let us consider the database De of Example 2 with a D-list ℓ being (a, b, b). The singularization of De with respect to ℓ is (D′e , ℓ′ ) with D′e = {r(a1 , b2 ), r(a1 , b3 ), p(a1 , a1 )} and ℓ′ = (a1 , b2 , b3 ).

Proposition 1 For any database D and any D-list ℓ, T (D, ℓ) = T (sing(D, ℓ)).

Proof: We put ℓ = (x1, . . . , xp) and ℓ′ = (x′1 , . . . , x′p ). The binary representation of xi and x′i are equal. By construction of sing(D, ℓ), the every predicate that holds for the tuple (x′1 , . . . , x′k ) holds as well for the tuple (x1, . . . , xk). For each tuple, the same word is thus written on the tape, and exactly the same tuples are considered. □

Proposition 2 Let D be a database, let ℓ be a D-list, and (D′ , ℓ′ ) = sing(D, ℓ). There is a homomorphism from D′ to D.

Proof: Let us consider π, that associates the ith term of ℓ′ with the ith term of ℓ. This function is well-defined, since all terms of ℓ′ are distinct. π is a homomorphism from D to D′ : indeed, p(xi1 1 , . . . , xik k ) belongs to D′ if and only if p(x1, . . . , xk) belongs to D. □

Proposition 3 Let q be a query closed under homomorphism. Let Mq be a Turing machine recognizing q. If Mq recognizes the tape representation of (D, ℓ) with ℓ being an arbitrary D-list, then D belongs to q.

Proof: Let us consider the singularization of D with respect to ℓ. By Proposition 1, the tape representing sing(D, ℓ) = (D′ , ℓ′ ) is the same as the tape representing (D, ℓ). Thus, Mq accepts on that tape. Since ℓ is a linear order on the terms of D′ , by definition of the Turing machine, D′ belongs to q. Since q is closed under homomorphisms, and by Proposition 2, D belongs as well to q. □

5 Database Completion

5.1 General Description

We now describe how to initialize the tape of the Turing machine. The first step is, given a D-list ℓ, to generate all the possible databases on Pe with terms from ℓ. Moreover, we want to do this in such a way that through existential rules, one can decide if a given atom is present or not in the generated database. The second step is to write the generated databases on tapes (which are parameterized by the D-list under consideration and the generated database).

To generate all possible databases, we enumerate tuples according to the D-list, making every possible choice regarding the validity of atoms referring to the given tuple. This choice is represented by fresh intensional predicates,

Ω = {ωP | P ⊆ Pe}. These predicates have arity k + 2. The first k positions are filled with the tuple under consideration. The k + 1th position is filled by a fresh element representing the portion of the database that has been generated so far, while the last position is used to remember (the representative of) the D-list currently used. Intuitively, ωP (x1, . . . , xk, x, xℓ) holds if and only if, for any p ∈ Pe, p(y1, . . . , yk) holds in the partial database represented by x iff p ∈ P, where yi is the unique term such that linkℓ(yi, xi).

Once these databases have been generated, we create the corresponding tapes and simulate the Turing machine Mq on each of those tapes. If a generated database contains (at least) all the atoms of the original D, the simulation accepts. Otherwise, the simulation may not terminate, but we shortcut this case by "exceptionally accepting" all generated databases where a we detect discrepancies to the original database.

5.2 Formalization of the Construction

Generation of the databases We finally introduce the rules for the part Rc of the query, dealing with database generation and tape creation. For each tuple, we consider every possible choice regarding which predicates hold for this tuple. We create |Ω| rules for the first tuple:

For each application of such a rule, the fresh element created by the instantiation of x represents a database where the atoms for the first tuple are fully specified, but no other tuple is known. To make choices for the other tuples as well, one uses the successor relation on tuples built from the D-list. We allow for any possible choice, thus creating |Ω|2 rules.

To ease the construction of the tape, we propagate the "Ωchoices" already made for earlier tuples from one partial representation to the next:

Of course, such "blind" choices may lead to inconsistencies with the present facts: we may choose that p(a, b) does not hold, whereas it is stated in the original data. We check such inconsistencies (and trigger an "exceptional accept" as explained before) as follows:

When reaching lastk(x1, . . . , xk, xℓ), a choice has been made for every predicate and every tuple, thus we have obtained a fully described database Dx,xℓ over the representations of elements in ℓ, which is represented by the fresh element x. It remains to verify that this fully specified database belongs to the query. To this end, we create a tape representing this database, and run the Turing machine Mq on it. Before describing how to perform these tasks, let us assume that if Dx,xℓ belongs to the query, then rec(x, xℓ) is derived. We propagate this information to the representatives of ever more partial databases, starting from the complete ones (i.e., those where the lastk predicate holds for the tuple treated last:

The acceptance information (irrespective if exceptional or regular) is then propagated through the tree of partial database representations:

If allaccept has been propagated up to the root, each possible way of completing the data associated with terms of ℓ is either inconsistent with D or is finally encoded into a tape accepted by Mq. We mark then ℓ as an accepting enumeration.

Creation of the tape We last present, for each x representing a database Dx,xℓ the creation of the initial tape on which the Turing machine is run. This is done as follows: we enumerate the tuples in the order induced by ℓ. For a given tuple, (x1, . . . , xk), there is exactly one atom of the form ωP (x1, . . . , xk, x, xℓ). We thus add at the end of the tape built so far all the information regarding this tuple. We first initialize by creating the first cell.

The needed predicate indicates which tuple should be written to the right of the current cell. This operation is done thanks to the following rules:

where there is such a rule for each P ⊆ Pe, and δpi,P denotes 1 if pi ∈ P and 0 otherwise. In English, this rule states that if at the cell c0 of the tape on which we write the representation of Dx,xℓ the information concerning the tuple ¯x is required, if ωP describes this information, and if ¯ y is the next tuple in lexicographic order, then we create 2n new cells with the relevant information and we declare that the information regarding ¯ y is needed at its right.

5.3 Sketch of Proof of the Construction

We now consider the query qR with R = Ra ∪ Rc ∪ RMq . Let D be a database, and ℓ be a D-list. We first prove that for any guessed database D′ on the terms of sing(D, ℓ), there is a fresh element xD′ representing D′ (Proposition 4). Then we show that the rules create the representation of the tape associated with (D′ , ℓ) when applied fromxD′ (Proposition 5). Finally, assuming that rec(xD′ , xℓ) is derived whenever T (D′ , ℓ) is accepted by Mq, we show that accenum(xℓ) is derived whenever T (D, ℓ) is accepted by Mq (Proposition 6).

Definition 6 (Alternative) Let D be a database, ℓ be a Dlist. An alternative D′ for (D, ℓ) is a database on the terms of sing(D, ℓ). A representation of D′ is a set of atoms of the form ωP (¯ t, x, xℓ), where x is a free variable, xℓ a representative of ℓ, and ωP is such that p(¯ t) ∈ D′ if and only if p ∈ P.

Proposition 4 Let D be a database, ℓ a D-list. Let D′ be an alternative for (D, ℓ). There exists xD′ in the (Ra ∪Rc)- chase of D such that the set of atoms of the form ωP (¯ t, xD′ , ℓ) in the chase is a representation of D′ .

A fresh element xD′ as described in the previous property is then called a representative of D′ .

Proposition 5 Let D be a database, let ℓ be a D-list. Let D′ be an alternative for (D, ℓ), xD′ a representative of D′ . There exists a sequence of fresh elements in the (Ra ∪Rc)-chase of D that form a representation of the tape T (D′ , ℓ).

Proposition 6 Let D be a database, let ℓ be a D-list. T (D, ℓ) is accepted by Mq if and only if there exists a representative xℓ of ℓ in the (RMq ∪ Ra ∪ Rc)-chase of D for which accenum(xℓ) holds.

Proof (sketch): Notice that an alternative for (D, ℓ) is either detected by Rule (4) or there is a homomorphism from sing(D, ℓ) into it. Thus, if D belongs to a homomorphismclosed query, then rec(x, xℓ) holds for all representatives x of alternatives of (D, ℓ) in the canonical model, with xℓ being a representative of ℓ. We conclude by Rules (6) and (7). □

Last, by Proposition 3, we know that a database D belongs to q if and only if there exists a D-list ℓ such that T (D, ℓ) is recognized by Mq. This thus proves the following theorem.

Theorem 1 Let q be a homomorphism-closed query, and Mq a Turing machine recognizing it. The existential rule query qR with R = RMq ∪ Ra ∪ Rc ∪ {accenum(xℓ) → goal} is such that a database D on Pe belongs to q if and only if D belongs to qR.

This in turn implies our main result: every homomorphism-closed recursively enumerable query is expressible as an existential rule query.

6 Discussion and FutureWork

In this work, we have considered existential rule queries. Existential rules have been intensively studied in recent years as a prominent formalism in knowledge representation and databases. Quite surprisingly, the expressivity of this formalism when considered as a query language has not been studied so far. We provided a clear characterization of this expressive power by showing that there are no further limits beyond the obvious: existential rule queries are exactly those queries which are preserved under homomorphisms and for which a semi-decision procedure exists. The beauty of this result lies in the absence of additional requirements regarding the database (such as a linear order on the domain elements or the presence of complement predicates). Consequently the major hurdle to be overcome was to generate appropriate tape representations without relying on a predefined linear order nor on input negation. We showed that this can be achieved by a brute force approach of creating all enumerations of domain elements and for every such enumeration all corresponding full databases. The final trick was to organize these proliferating enumerations and guessed databases in a way that a query match is correctly detected, despite the existence of "fake" linear orders and the side-by-side existence of incoherent databases, overly filled databases, and correct databases. The assumption that the query is preserved under homomorphism had to be heavily exploited.

Besides its elegance, the established result can be useful for clarifying expressivity questions. It is now clear that every query for which homomorphism preservation and semidecidability in any Turing-equivalent computing paradigm can be established (by whatever means) must be expressible as an existential rule query. Conversely we know that every query not expressible via existential rules must violate one of these two conditions. Moreover, since we have shown the formalism to be complete for the class of queries satisfying the two conditions, it does not make sense to look for more expressive extensions of existential rule queries which are homomorphism-closed. On a side note, since our proof is constructive, we have provided a generic way of turning a Turing machine formulation of the query into an existential rule query, although in most cases certainly a suboptimal one.

Our ongoing work is focused on finding similar capturing results for homomorphism-closed classes of queries on different complexity levels (P, NP, PSPACE, EXPTIME, and others) ideally linked to natural syntactic restrictions of existential rules. To this end, we may draw on prior work on complexities of different decidable fragments of existential rules [Baget et al., 2011b; Kr¨otzsch and Rudolph, 2011], exploit existing results linking certain complexities to existential rules classes extended by mild forms of negation [Abiteboul et al., 1994; Gottlob et al., 2014], and develop results in the spirit of [Feder and Vardi, 2003], showing that negation can be removed when considering only homomorphism preserved queries. However, results might not turn out as elegant as desired. For instance, the natural candidate for capturing the class of homomorphism-preserving polytime-computable queries, Datalog, has recently been shown to not fully capture that class [Dawar and Kreutzer, 2008].