Victor Vianu
email: vianu@ucsd.edu

Datalog Unchained

This is the companion paper of a talk in the Gems of PODS series, that reviews the development, starting at PODS 1988, of a family of Datalog-like languages with procedural, forward chaining semantics, providing an alternative to the classical declarative, model-theoretic semantics. These languages also provide a unified formalism that can express important classes of queries including fixpoint, while, and all computable queries. They can also incorporate in a natural fashion updates and nondeterminism. Datalog variants with forward chaining semantics have been adopted in a variety of settings, including active databases, production systems, distributed data exchange, and data-driven reactive systems.

INTRODUCTION

Datalog emerged in the 80's as a simple, elegant formalism providing the basis for deductive databases and the study of recursion in database languages. Datalog was introduced as a specialization of logic programming to databases (a discussion of the history can be found in [START_REF] Maier | Computing with Logic: Logic Programming with Prolog[END_REF][START_REF] Maier | Datalog: concepts, history, and outlook[END_REF]). Datalog ¬ , its extension with negation, was also studied through the lens of logic programming and non-monotonic reasoning, by which programs are viewed as specifications of consistent states of the world, best understood via model-theoretic semantics. This approach has led, most prominently, to stratified Datalog ¬ [START_REF] Apt | Towards a theory of declarative knowledge[END_REF][START_REF] Chandra | Horn clause queries and generalizations[END_REF][START_REF] Van Gelder | Negation as failure using tight derivations for general logic programs[END_REF][START_REF] Lifschitz | On the declarative semantics of logic programs with negation[END_REF]. While stratified semantics provides a very natural interpretation for negation, it is limited to programs without recursion through negation. The quest to provide semantics to all Datalog ¬ programs culminated with the elegant well-founded semantics [START_REF] Van Gelder | The well-founded semantics for general logic programs[END_REF]. However, its conceptual complexity, involving 3valued models (or equivalently, alternating fixpoints), has precluded its widespread adoption in practice.

At PODS 1988, two articles [START_REF] Abiteboul | Procedural and declarative database update languages[END_REF][START_REF] Kolaitis | Why not negation by fixpoint?[END_REF] independently suggested an alternative approach, aptly captured by the title of [START_REF] Kolaitis | Why not negation by fixpoint?[END_REF]: "Why not negation by fixpoint?". Both articles proposed to depart from the declarative approach and adopt a procedural semantics for Datalog ¬ based on forward chaining of rules, called inflationary fixpoint semantics. As shown in [START_REF] Abiteboul | Procedural and declarative database update languages[END_REF], Datalog ¬ with inflationary semantics combines simplicity with expressiveness: it captures precisely the robust class of fixpoint queries, previously defined by extensions of first-order logic with a fixpoint operator.

The two PODS 1988 articles initiated a line of research [START_REF] Abiteboul | Non-deterministic languages to express deterministic transformations[END_REF][START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF][START_REF] Abiteboul | Non-determinism in logic-based languages[END_REF][START_REF] Abiteboul | Fixpoint extensions of first-order logic and Datalog-like languages[END_REF][START_REF] Abiteboul | Non-determinism in logic-based languages[END_REF][START_REF] Picouet | Semantics and expressiveness issues in active databases[END_REF][START_REF] Vianu | Rule-based languages[END_REF] that extended the forward chaining approach to an entire family of Datalog-like languages, providing an alternative paradigm for database queries, with natural counterparts to classical query languages including the fixpoint and while queries, and all the way to computable queries. The forward chaining approach turned out to also be suitable for studying nondeterministic languages, yielding an appealing unifying formalism. The present paper tells the story of this development.

After a brief review of classical query languages, we turn to Datalog and its extensions. We begin with an informal overview of Datalog and Datalog ¬ with stratified and well-founded semantics. We then present the procedural, forward chaining semantics of Datalog ¬ . One of the nicest results in regard to expressive power is the convergence of the procedural and declarative semantics to the fixpoint queries. We also present a further extension denoted Datalog ¬¬ that allows for explicit retraction of facts and expresses the while queries. Finally, we discuss Datalog ¬ new , a variant of Datalog that allows for the invention of new values in heads of rules, and expresses all computable queries. Value invention also arises in the object-oriented context, where object creation is a very useful and common feature [START_REF] Abiteboul | Object identity as a query language primitive[END_REF].

Deterministic languages, including rule-based languages, have well-known limitations of expressive power. For example, there is no known language that expresses precisely the ptime queries (e.g., see [START_REF] Grohe | The quest for a logic capturing PTIME[END_REF]). This limitation is overcome in the presence of an order. For example, Datalog ¬ with inflationary or well-founded semantics expresses on ordered databases exactly the queries computable in polynomial time (and so do the weaker semi-positive and stratified Datalog ¬ ). Another approach, intimately related to the first, trades off determinism for expressiveness. Indeed, as shown in [START_REF] Abiteboul | Non-deterministic languages to express deterministic transformations[END_REF][START_REF] Abiteboul | Non-determinism in logic-based languages[END_REF][START_REF] Abiteboul | Fixpoint extensions of first-order logic and Datalog-like languages[END_REF], nondeterministic variants of Datalog with negation can express all (deterministic and nondeterministic) queries computable in polynomial time. The nondeterminism arises from the firing of rule instantiations in arbitrary order. As argued in [START_REF] Abiteboul | Non-determinism in logic-based languages[END_REF], nondeterminism can be a very useful feature, independently of issues of expressiveness. Indeed, nondeterminism has long been present in expert systems and production systems (e.g., see [START_REF] Brownston | Programming Expert Systems in OPS5[END_REF]).

The paper is organized as follows. Some background is provided in Section 2. The declarative approach is briefly surveyed next. This reviews Datalog, stratified Datalog ¬ , and Datalog ¬ with wellfounded semantics. The procedural, forward chaining approach is presented in Section 4, together with results on the relative expressive power of the declarative and procedural languages. Nondeterministic languages are discussed in Section 5. A brief review of intervening Datalog research is outlined in Section 6. To conclude, we compare the forward chaining and declarative semantics for Datalog and discuss the adoption of the forward chaining semantics in practice. The presentation relies largely on material from [START_REF] Abiteboul | Non-deterministic languages to express deterministic transformations[END_REF][START_REF] Abiteboul | Procedural and declarative database update languages[END_REF][START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF][START_REF] Abiteboul | Non-determinism in logic-based languages[END_REF][START_REF] Abiteboul | Fixpoint extensions of first-order logic and Datalog-like languages[END_REF][START_REF] Abiteboul | Non-determinism in logic-based languages[END_REF][START_REF] Vianu | Rule-based languages[END_REF]. The work surveyed in this paper is joint with Serge Abiteboul.

BACKGROUND

In this section, we review some terminology relating to relational databases. In particular, we recall some of the traditional query languages, including extensions of first-order logic with recursion (the fixpoint [START_REF] Chandra | Structure and complexity of relational queries[END_REF][START_REF] Moschovakis | Elementary Induction on Abstract Structures[END_REF] and while [START_REF] Chandra | Programming primitives for database languages[END_REF] queries).

We assume the existence of four infinite and pairwise disjoint sets of symbols: the set rel of relation symbols, the set att of attributes, the set dom of constants, and the set var of variables. A relation schema is a relation symbol together with a finite set of attributes. The set of attributes of a relation R is denoted by att(R). A database schema is a finite set of relation schemas. A free tuple over a relational schema R is a mapping from att(R) into dom ∪ var. A constant tuple over a relational schema R is a mapping from att(R) into dom. An instance over a relation schema R is a finite set of constant tuples over R. An instance I over a database schema R is a mapping from R such that for each R in R, I(R) is an instance over R. The set of all instances over a schema R is denoted by inst(R). Note that we only consider finite instances. For an instance I, we denote by adom(I) the set of elements of dom occurring in I.

A deterministic database query is a mapping from inst(R) to inst(answer), where R is a database schema and answer is a relation schema not in R. We also discuss nondeterministic queries. A nondeterministic query is a subset of inst(R) × inst(answer) for some R and answer (so it is a relation rather than a mapping). Some settings use a more general notion of database transformation allowing answer schemas with several relations, some of which may be part of the input schema (thus capturing updates).

Queries are usually required to obey three conditions: welltypedness, computability and genericity [START_REF] Aho | Universality of data retrieval languages[END_REF][START_REF] Chandra | Computable queries for relational data bases[END_REF]. Well-typedness requires that the results of the query be instances of a fixed relation schema. A query is computable if there is a Turing machine that, given any standard encoding of an input database (depedent on a total order on the domain), produces a standard encoding of the query answer. Genericity requires that the graph of a database query be closed under isomorphisms of the domain that fix a specified finite set of constants depending on the query.

We will refer to complexity classes of queries. For each Turing machine complexity class c, there is a corresponding complexity class of (nondeterministic) queries denoted (n)db-c. In particular, the class of nondeterministic queries which can be computed by a (nondeterministic) Turing machine in polynomial time is denoted (n)db-ptime. It is important to distinguish between classes ndb-c of nondeterministic queries and classes of deterministic queries defined using nondeterministic devices. For example, by Savitch's theorem, pspace = npspace, so db-pspace = db-npspace. Both are classes of deterministic queries. However, ndb-pspace contains nondeterministic queries, so db-pspace ndb-pspace (and ndbpspace db-npspace). Similarly, db-np is not to be confused with ndb-ptime ! Below are some informal examples. All queries take as input a binary relation representing edges in a graph:

• The query whose answer consists of all vertices lying on a cycle is a query in db-ptime. Some query languages. Most practical query languages in relational databases are based on FO, first-order logic on relations, sometimes called relational calculus (e.g. see [START_REF] Abiteboul | Foundations of databases[END_REF]). FO has an algebraization called relational algebra [START_REF] Codd | A relational model of data for large shared data banks[END_REF]. Relational algebra provides the following operations on relations: π X (projection on attributes X ), σ C (selection of tuples satisfying condition C consisting of (in)equalities among attributes and/or constants), δ A→B (rename attribute A to B), (join of two relations), -(difference), and ∪ (union).

There are many useful queries that FO cannot express, such as the transitive closure of a graph. Numerous extensions of FO with recursion have been proposed. Most of them converge towards two very robust classes of queries: fixpoint [START_REF] Chandra | Structure and complexity of relational queries[END_REF][START_REF] Moschovakis | Elementary Induction on Abstract Structures[END_REF] and while [START_REF] Chandra | Programming primitives for database languages[END_REF]. These can be defined in various ways: by adding fixpoint operators to FO [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF][START_REF] Moschovakis | Elementary Induction on Abstract Structures[END_REF], looping constructs to relational algebra [START_REF] Chandra | Programming primitives for database languages[END_REF][START_REF] Chandra | Structure and complexity of relational queries[END_REF], or by extensions of Datalog [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF]. We briefly review here the definition of fixpoint and while based on the eponymous languages, using looping constructs (see [START_REF] Abiteboul | Foundations of databases[END_REF]).

While is an imperative language that extends FO with recursion. It provides relation variables, assignment statements of the form R := φ where φ is an FO query, and a looping construct while φ do where φ is an FO sentence. An equivalent variation uses loops of the form while change do which iterate the body as long as some change is made to some relation. Fixpoint is the same as while except the semantics of assignment is cumulative (i.e., an assignment denoted R + = φ adds φ to the current content of R). This guarantees termination of fixpoint programs in polynomial time, whereas while programs require polynomial space. On ordered databases, fixpoint expresses precisely db-ptime [START_REF] Immerman | Relational queries computable in polynomial time[END_REF][START_REF] Vardi | The complexity of relational query languages[END_REF] and while expresses db-pspace [START_REF] Vardi | The complexity of relational query languages[END_REF]. It was further shown in [START_REF] Abiteboul | Generic computation and its complexity[END_REF] that fixpoint = while iff ptime = pspace, even without the order assumption.

THE DECLARATIVE APPROACH

We briefly review the classical model-theoretic semantics of Datalog and its extension with negation. For a detailed presentation see [START_REF] Abiteboul | Foundations of databases[END_REF], and [START_REF] Maier | Datalog: concepts, history, and outlook[END_REF] for a more comprehensive survey.

Datalog

Much of the activity in deductive databases has focused on a toy language called Datalog. Some of the early history of Datalog is discussed in [START_REF] Maier | Computing with Logic: Logic Programming with Prolog[END_REF][START_REF] Maier | Datalog: concepts, history, and outlook[END_REF]. Although limited, Datalog highlights some aspects of recursion present in many practical languages. Most of the optimization techniques in deductive databases have been developed around Datalog.

As an example, following is a Datalog program that computes the transitive closure of a graph. The graph is represented in relation G and its transitive closure in relation T :

T (x, y) ← G(x, y) T (x, y) ← G(x, z),T (z, y).
A Datalog program "defines" the relations occurring in heads of rules, from the other relations. The definition is recursive, so defined relations can also occur in bodies of rules. Thus, a Datalog program is interpreted as a mapping from instances over the relations occurring in the bodies only, to instances over the relations occurring in the heads. For example, the program above maps a relation over G (a graph) to a relation over T (its transitive closure).

We now define the syntax of Datalog.

Definition 3.1. A (Datalog) rule is an expression of the form: The set of constants occurring in a Datalog program P is denoted adom(P); and for an instance I, we use adom(P, I) as an abbreviation for adom(P) ∪ adom(I).

R 1 (u 1 ) ← R 2 (u 2 ), . . . , R n (u n ) where n ≥ 1, R 1 , . . . ,
Let P be a Datalog program. An extensional relation is a relation occurring only in the body of the rules. An intensional relation is a relation occurring in the head of some rule of P. The extensional (database) schema, denoted edb(P), consists of the set of all extensional relation names; whereas the intensional schema idb(P) consists of all the intensional ones. The schema of P, denoted sch(P) is the union of edb(P) and idb(P). The semantics of a Datalog program is a mapping from database instances over edb(P) to database instances over idb(P). Typically, one relation of idb(P) is designated as the answer relation.

The key idea of the declarative approach of deductive databases is to view the program as a set of first-order sentences that describes the desired answer. To a Datalog rule

ρ : R 1 (u 1 ) ← R 2 (u 2 ), . . . , R n (u n )
we can associate the logical sentence:

∀x 1 , . . . , x m (R 1 (u 1 ) ← R 2 (u 2 ) ∧ . . . ∧ R n (u n ))
where x 1 , . . . , x m are the variables occurring in the rule; and "←" is the standard logical implication. For a program P, the set of sentences associated with the rules of P is denoted by Σ P . It turns out that for each Datalog program P, and input I, there is a minimum model of Σ P extending I. This model is the semantics of P on input I and is denoted by P(I).

Stratified Datalog ¬

Datalog ¬ extends Datalog with negations in the bodies of rules. The syntax of Datalog ¬ is a straightforward extensions of Datalog. A Datalog ¬ rule is an expression of the form R 1 (u 1 ) ← L 1 , ..., L n where: R 1 is a relation, u 1 a free tuple, and each L i is a literal of the form R i (u i ) (in which case it is called positive) or ¬R i (u i ) (in which case it is called negative). Each variable in u 1 must occur in some literal L i of the body.

A Datalog ¬ program is a non-empty finite set of Datalog ¬ rules. As for Datalog programs, sch(P) denotes the database schema consisting of all relations involved in the program P; the relations occurring in heads of rules are the idb relations of P, and the others are the edb relations of P.

Similarly to Datalog, we can associate to a Datalog ¬ program P the set Σ P of FO sentences corresponding to the rules of P. For Datalog, the model-theoretic semantics of a program P is given by the unique minimal model of Σ P extending the input. Unfortunately, this simple solution no longer works for Datalog ¬ , since uniqueness of a minimal model extending the input is not guaranteed. Short of this guarantee, a model-based semantics must specify an "intended" model that is intuitive and easy to compute. This is the core problem of "non-monotonic reasoning": make sense in a consistent way of the co-existence of negative and positive facts, in a way that reflects a natural reasoning process.

The most intuitive and widely accepted declarative semantics for Datalog ¬ requires a syntactic restriction that, informally, prohibits recursion through negation. The resulting syntactic class is called stratified Datalog ¬ . Intuitively, the restriction allows to "read" the program so that, for each idb relation R, the portion of P defining R comes before the negation of R is used. Once R is computed, the set of negative facts over R (restricted to the active domain) is well defined. For example, consider the following stratified Datalog ¬ program P defining the complement of transitive closure of a graph G:

T (x, y) ← G(x, y) T (x, y) ← G(x, z),T (z, y) CT (x, y) ← ¬T (x, y).

According to stratified semantics, the idb relation T is defined by the first two rules, and then its negation is used in the rule defining CT . Thus, the first two rules are applied before the third. This approach can be naturally extended to any stratified Datalog ¬ program. Not surprisingly, this appealing semantics has been independently proposed by quite a few investigators [START_REF] Apt | Towards a theory of declarative knowledge[END_REF][START_REF] Chandra | Horn clause queries and generalizations[END_REF][START_REF] Van Gelder | Negation as failure using tight derivations for general logic programs[END_REF][START_REF] Lifschitz | On the declarative semantics of logic programs with negation[END_REF].

The Well-Founded Semantics

While stratification provides a simple and elegant approach to defining semantics of Datalog ¬ programs, it has two major limitations. First, it does not provide semantics to all Datalog ¬ programs. Second, stratified Datalog ¬ programs are not quite satisfactory with regard to expressive power. From a computational point of view, they provide recursion and negation. Therefore, one might expect that they express the fixpoint queries. Unfortunately, as shown [START_REF] Kolaitis | The expressive power of stratified logic programs[END_REF] (making use of earlier results from [START_REF] Dalhaus | Skolem normal forms concerning the least fixpoint[END_REF] and [START_REF] Chandra | Structure and complexity of relational queries[END_REF]), stratified Datalog ¬ programs fall short of expressing all fixpoint queries. Intuitively, this is due to the fact that the stratification condition prohibits recursive application of negation, whereas in other languages expressing fixpoint this computational restriction does not exist.

The quest for declarative semantics for all Datalog ¬ program has resulted in various proposals, of which the most prominent is the well-founded semantics [START_REF] Van Gelder | The well-founded semantics for general logic programs[END_REF]. It relies on a fundamental revision of the expectations on the answer to a Datalog ¬ program. Previously, the answer was required to provide information on the truth or falsehood of every fact. The well-founded semantics is based on the idea that a given program may not necessarily provide such information on all facts. Instead, some facts may simply be indifferent to it, and the answer should be allowed to say that the truth value of those facts is unknown. Relaxing expectations about the answer in this fashion allows to provide an elegant, model-theoretic semantics to all Datalog ¬ programs. The price to pay is that the answer is no longer guaranteed to provide total information. In particular, the model-theoretic semantics requires a 3-valued logic.

Example 3.2. [START_REF] Van Gelder | The well-founded semantics for general logic programs[END_REF][START_REF] Gelfond | The stable model semantics for logic programs[END_REF] The example concerns a game with states, a, b, . . . . The game is between two players. The possible moves of the games are held in a binary relation moves. A tuple ⟨a, b⟩ in moves indicates that when in state a, one can choose to move to state b. A player loses if they are in a state from which there are no moves. The goal is to compute the set of winning states, i.e., the set of states such that there exists a winning strategy for a player in this state. These are obtained in a unary predicate win.

Consider the input K with the following value for moves:

K(moves) = {⟨b, c⟩, ⟨c, a⟩, ⟨a, b⟩, ⟨a, d⟩, ⟨d, e⟩, ⟨d, f ⟩, ⟨f , д⟩}
It is easily seen that there are indeed winning strategies from states d (move to e) and f (move to д). Slightly more subtle is the fact that there is no winning strategy from any of states a, b, or c. Indeed, a given player can prevent the other from winning, essentially by forcing a non-terminating sequence of moves. Now consider the following nonstratifiable program P win :

win(x) ← moves(x, y), ¬win (y)
Intuitively, P win states that a state x is in win if there is at least one state y that one can move to from x, for which the opposing player looses. Following is a 3-valued model J of P win , that agrees with K on moves, and is in fact the well-founded semantics of P win on input K. Instance J is such that J(moves) = K(moves) and the values of win-atoms are given as follows:

true win(d), win(f ) false win(e), win(д) unknown win(a), win(b), win(c).

The well-founded semantics can be compared against classical 2valued model-theoretic semantics by casting its 3-valued semantics into a 2-valued model by taking the true facts as the answer to a program. In fact, it turns out that for every Datalog ¬ program P there is a Datalog ¬ program P whose well-founded semantics yields a classical 2-valued model whose true facts are the same as those of P under well-founded semantics [START_REF] Flum | Total and partial wellfounded Datalog coincide[END_REF][START_REF] Flum | Games and total Datalog¬ queries[END_REF]. It was shown in [START_REF] Van Gelder | The alternating fixpoint of logic programs with negation[END_REF] that with the 2-valued interpretation, well-founded semantics has the same expressive power as the fixpoint queries, and can also be evaluated in ptime. This non-trivial result makes use of an equivalent formulation of the well-founded semantics as an alternating fixpoint computation [START_REF] Van Gelder | The alternating fixpoint of logic programs with negation[END_REF]. Thus, well-founded semantics overcomes the expressiveness limitations of stratified Datalog ¬ .

Research on well-founded semantics, and the related notion of 3-stable model, has its roots in investigations of stable and default model semantics. Stable model semantics was introduced in [START_REF] Gelfond | The stable model semantics for logic programs[END_REF] and default model semantics in [START_REF] Bidoit | Minimalism subsumes default logic and circumscription[END_REF][START_REF] Bidoit | General logic databases and programs: Default logic semantics and stratification[END_REF]. Stable semantics is based on Moore's autoepistemic logic [START_REF] Moore | Semantics considerations on non-monotonic logic[END_REF], and default semantics is based on Reiter's default logic [START_REF] Reiter | A logic for default reasoning[END_REF]. The equivalence between autoepistemic and default logic in the general case has been shown in [START_REF] Konolige | On the relation between default and autoepistemic logic[END_REF]. The equivalence between stable model semantics and default model semantics was shown in [START_REF] Bidoit | General logic databases and programs: Default logic semantics and stratification[END_REF].

Several equivalent definitions of the well-founded semantics have been proposed. The 3-valued model-theoretic approach is due to [START_REF] Przymusinski | Well-founded semantics coincides with three-valued stable semantics[END_REF]. In addition to the alternating fixpoint computation of [START_REF] Van Gelder | The alternating fixpoint of logic programs with negation[END_REF], other approaches for computing the well-founded semantics are exhibited in [START_REF] Bidoit | General logic databases and programs: Default logic semantics and stratification[END_REF][START_REF] Przymusinski | Every logic program has a natural stratification and an iterated least fixpoint model[END_REF]. Historically, the first definition of the well-founded semantics was proposed in [START_REF] Van Gelder | The well-founded semantics for general logic programs[END_REF][START_REF] Van Gelder | The well-founded semantics for general logic programs[END_REF].

In summary, the stratified semantics provides a very natural, intuitive interpretation for the sublass of Datalog ¬ without recursion through negation. While the well-founded semantics provides model-theoretic semantics to all Datalog ¬ programs, it is far less intuitive and its widespread use remains unlikely. In terms of expressiveness, Datalog ¬ with well-founded semantics overcomes the limitations of stratified Datalog ¬ by capturing the fixpoint queries. At the time, no model-theoretic semantics had been defined for Datalog-like languages that yielded expressiveness beyond fixpoint. These limitations motivated the study of the forward chaining approach to Datalog-like languages, that had already been in practical use in production systems [START_REF] Brownston | Programming Expert Systems in OPS5[END_REF] and active databases [START_REF] Widom | Active Database Systems: Triggers and Rules for Advanced Database Processing[END_REF].

THE FORWARD CHAINING APPROACH

We describe next the forward chaining semantics of Datalog ¬ (expressing the fixpoint queries) and two extensions: Datalog ¬¬ (allowing negations in heads of rules and expressing the while queries) and Datalog ¬ new (allowing for the "invention" of new values, and expressing all computable queries).

Datalog ¬

The forward chaining (or inflationary) semantics of Datalog ¬ is intuitively very simple: the rules of the program are fired in parallel with all applicable instantiations, until a fixpoint is reached. We first illustrate this straightforward semantics with an example. (d(a,b) is infinite if there is no path from x to y.) The program is:

closer (x, y, x ′ , y ′ ) = {⟨x, y, x ′ , y ′ ⟩ | d(x, y) ≤ d(x ′ , y ′ )},
T (x, y) ← G(x, y) T (x, y) ← T (x, z), G(z, y) closer (x, y, x ′ , y ′ ) ← T (x, y), ¬T (x ′ , y ′ ).
The program is evaluated as follows. The rules are fired simultaneously with all applicable valuations. At each such firing, some facts are inferred. This is repeated until no new facts can be inferred. A negative fact such as ¬T (x ′ , y ′ ) is true if T (x ′ , y ′ ) has not been inferred so far. This does not preclude T (x ′ , y ′ ) from being inferred at a later firing of the rules. One firing of the rules is called a "stage" in the evaluation of the program. In the above program, the transitive closure of G is computed in T . Consider the consecutive stages in the evaluation of the program. Note that, if the fact T (x, y) is inferred at stage n, then d(x, y) = n. So, if T (x ′ , y ′ ) has not been inferred yet, this means that the distance between x and y is less than that between x ′ and y ′ . Thus, if T (x, y) and ¬T (x ′ , y ′ ) hold at some stage n, then d(x, y) ≤ n and d(x ′ , y ′ ) > n and closer (x, y, x ′ , y ′ ) is then inferred.

Formally, the forward chaining semantics of Datalog ¬ is defined as follows. Let P be a Datalog ¬ program and K an instance over sch(P). An instantiation of a rule A ← L 1 , . . . , L n with respect to K is a rule ν (A) ← ν (L 1 ), . . . , ν(L n ) where ν is a valuation which maps each variable into adom(P, K). A fact A ′ is an immediate consequence for K and

P if A ′ ∈ K(R) for some edb relation R, or A ′ ← L ′ 1 , ..., L ′
n is an instantiation of a rule in P and: each positive L ′ i is a fact in K, and for each negative

L ′ i = ¬A ′ i , A ′ i K.
The immediate consequence operator of P, denoted Γ P , is now defined as follows. For each K over sch(P),

Γ P (K) = K ∪ {A | A is an immediate consequence for K and P }.
Given an instance I over edb(P), one can compute Γ P (I), Γ 2 P (I), Γ 3 P (I), etc. As suggested in Example 4.1, each application of Γ P is called a stage in the evaluation. From the definition of Γ P , it follows that Γ P (I) ⊆ Γ 2 P (I) ⊆ Γ 3 P (I) ⊆ . . . As for Datalog, the sequence reaches a fixpoint, denoted Γ ω P (I), after a finite number of steps. The restriction of this to the idb relations (or some subset thereof) is called the image (or answer) of P on I.

In the procedural semantics described above, increasing sets of facts are inferred by firings of the rules. For that reason, this semantics is also referred to as the inflationary semantics for Datalog ¬ (there is an "inflation" of tuples!). The language Datalog ¬ with inflationary semantics is also referred to as inflationary Datalog ¬ . This semantics was first proposed for Datalog ¬ in [START_REF] Abiteboul | Procedural and declarative database update languages[END_REF][START_REF] Kolaitis | Why not negation by fixpoint?[END_REF]. It extends the fixpoint semantics proposed for Datalog in [START_REF] Chandra | Horn clause queries and generalizations[END_REF], also considered earlier in the context of logic programming [START_REF] Apt | Contributions to the theory of logic programming[END_REF][START_REF] Van Emden | The semantics of predicate logic as a programming language[END_REF].

In the case of Datalog, the minimum model semantics and the inflationary fixpoint semantics coincide. For Datalog ¬ , this perfect match of declarative and procedural semantics is lost. First, a Datalog ¬ program may not have a unique minimal model. Moreover, while the result produced by inflationary semantics is a model of the program, it is not necessarily a minimal one.

Datalog ¬ with inflationary semantics provides recursion and negation, and it is straightforward to see that every query it expresses is a fixpoint query. The converse would seem unlikely, since Datalog ¬ is a much simpler language than those previously known to express the fixpoint queries. Surprisingly, the following was shown in [START_REF] Abiteboul | Procedural and declarative database update languages[END_REF][START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF]: Theorem 4.2. Inflationary Datalog ¬ expresses precisely the fixpoint queries.

The simulation of fixpoint by inflationary Datalog ¬ presents two main difficulties, related to the simulation of the control capabilities available in fixpoint. The first involves delaying the firing of a rule until after the completion of a fixpoint by another set of rules. Intuitively, this is hard because checking that the fixpoint has been reached involves checking the non-existence rather than the existence of some valuation, and Datalog ¬ is more naturally geared towards checking the existence of valuations. The solution to this difficulty is illustrated in the following example.

Example 4.3. The following Datalog ¬ program computes the complement of the transitive closure of a graph G. The example illustrates the technique used to delay the firing of a rule (computing the complement) until the fixpoint of a set of rules (computing the transitive closure) has been reached, i.e., until the application of the transitivity rule yields no new tuples. To monitor this, the relations old-T , old-T -except-f inal are used. old-T follows the computation of T , but is one step behind it. The relation old-T -except-f inal is identical to old-T , but includes a clause which prevents it from firing when T has reached its last iteration. Thus, old-T and old-Texcept-f inal differ only in the iteration after the transitive closure T reaches its final value. In the subsequent iteration, the program recognizes that the fixpoint has been reached, and fires the rule computing the complement in relation CT . The program is:

T (x, y) ← G(x, y) T (x, y) ← G(x, z),T (z, y) old-T (x, y) ← T (x, y) old-T -except-f inal(x, y) ← T (x, y),T (x ′ , z ′ ),T (z ′ , y ′ ), ¬T (x ′ , y ′ ) CT (x, y) ← ¬T (x, y), old-T (x ′ , y ′ ), ¬old-T -except-f inal(x ′ , y ′ ).
(It is assumed that G is not empty.)

The second difficulty concerns keeping track of iterations of the body in the computation of a loop. Given a loop while chanдe do body the simulation of body itself may involve numerous relations, whose behavior may be "sabotaged" by an overly zealous application of iteration. To overcome this we separate the "internal" computation of the body from the "external" iteration, as illustrated in the following example. Note that the query computes the set of nodes in G that are not reachable from a cycle. (In other words, the nodes such that the lengths of paths leading to them are bounded.) One iteration is achieved by the Datalog ¬ program P: bad(x) ← G(y, x), ¬дood(y) delay ← дood(x) ← delay, ¬bad(x) Simply iterating P does not yield the desired result. Intuitively, the relations delay and bad, which are used as "scratch paper" in the computation of a single iteration of the loop, cannot be re-initialized, and so cannot be effectively re-used to perform the computation of subsequent iterations.

To overcome this problem, we essentially create a version of P for each iteration The versions are distinguished by using "timestamps". The nodes themselves serve as timestamps. The timestamps marking iteration i are the values newly introduced in relation good at iteration i -1. Relations delay and delay-stamped are used to delay the derivation of new tuples in дood until bad and bad-stamped (respectively) have been computed in the current iteration. The process continues until no new values are introduced in an iteration. The full program is the union of the three rules given above, which perform the first iteration, and the following rules, which perform the iteration with timestamp t: bad-stamped(x, t) ← G(y, x), ¬дood(y), дood(t) delay-stamped(t) ← дood(t) дood(x)

← delay-stamped(t), ¬bad-stamped(x, t).

Datalog ¬¬

Recall that in Datalog ¬ with inflationary semantics, a fact that has been inferred can never be retracted. Datalog ¬¬ allows explicit retraction of a previously inferred fact (thus, the semantics of Datalog ¬¬ is "noninflationary") [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF] 1 . Syntactically, this is done using negations in heads of rules, interpreted as deletions of facts. Moreover, input relations are allowed in heads of rules, thus providing the ability to perform updates. The resulting language is denoted by Datalog ¬¬ , to indicate that negations are allowed in both heads and bodies of rules. The immediate consequence operator Γ P and semantics of a Datalog ¬¬ program are analogous to those for Datalog ¬ with the following important proviso. If a negative literal ¬A is inferred, the fact A is removed, unless A is also inferred in the same firing of the rules. This gives priority to inference of positive over negative facts and is somewhat arbitrary. Other possibilities are: (i) give priority to negative facts, (ii) interpret the simultaneous inference of A and ¬A as a "no-op", i.e., including A in the new instance only if it is there in the old one; and (iii) interpret the simultaneous inference of A and ¬A as a contradiction which makes the result undefined. The chosen semantics has the advantage over (iii) that the result is always defined. In any case, the choice of semantics is not crucial: it results in equivalent languages. With the semantics chosen above, termination is no longer guaranteed. For instance, the program

T (0) ← T (1) ¬T (1) ← T (1) T (1)
← T (0) ¬T (0) ← T (0) never terminates on input T (0). Indeed, the value of T flip-flops between {⟨0⟩} and {⟨1⟩} so no fixpoint is reached.

By a method similar to the above, it can be shown that Datalog ¬¬ expresses precisely the while queries [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF].

How about the relationship between Datalog ¬ and Datalog ¬¬ ? Clearly, Datalog ¬ is subsumed by Datalog ¬¬ . Intuitively, it is tempting to believe that Datalog ¬¬ is more powerful than Datalog ¬ (considering only terminating queries). However, this is far from obvious. Indeed, the following is a consequence of results in [START_REF] Abiteboul | Generic computation and its complexity[END_REF] on the relationship between fixpoint and while: Theorem 4.5. Inflationary Datalog ¬ is strictly less expressive than Datalog ¬¬ iff ptime pspace.

Since it is open whether ptime pspace, the relationship between inflationary (or well-founded) Datalog ¬ and Datalog ¬¬ remains open. However, the strict inclusion is conjectured to be true. 1 The language Datalog ¬¬ is denoted in [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF] by Datalog ¬⋆

Datalog ¬ new

All the languages considered so far express queries within dbpspace. Intuitively, this is so because each program uses a fixed number of relations of fixed arity, which are filled in the course of the computation with tuples over the elements of the input. Thus, such programs can build an amount of space which is no more than polynomial in the number of elements of the input.

Suppose that we wish to have a complete language, i.e. a language expressing all queries. One way to break the polynomial "space barrier", first suggested in [START_REF] Abiteboul | A transaction language complete for database update and specification[END_REF], is to allow programs to invent new values in the course of the computation. Besides the computational justification, this is useful in object-oriented databases, where the creation of new object identifiers is a useful and very common feature. Such a feature was studied in the object-oriented language IQL [START_REF] Abiteboul | Object identity as a query language primitive[END_REF].

We describe an extension of Datalog ¬ , defined in [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF], that expresses all deterministic queries. This extension introduces new values in the course of the computation (but not in the answer). We informally describe the language, denoted by Datalog ¬ new . The syntax is the same as that of Datalog ¬ , except that variables that do not appear in body of a rule may appear in its head. The inflationary semantics of this language is similar to that of Datalog ¬ . The only difference consists in the use of the variables that occur only in heads of rules: these are valuated outside the current active domain, thus resulting in the "invention" of new values. Specifically, in the application of the immediate consequence operator, each instantiation of a rule body in the current active domain is extended with one instantiation of the remaining variables with distinct values outside the active domain. The choice of the particular new values is nondeterministic. However, this is the only source of nondeterminism. If the final result contains only values from the input, which can be enforced by a straightforward syntactic safety restriction, then the query defined by such a program is deterministic. Furthermore, Datalog ¬ new is complete: Theorem 4.6.

[6] Datalog ¬ new expresses all deterministic queries.

Intuitively, the proof uses the invented values to simulate the Turing machine computing the query, as well as the encodings of the input database on the initial Turing tape, and the decoding of the output. Each total order of the active domain generates one standard encoding, and the computation is carried out in parallel on all the encodings. The new values provide the unbounded amount of space needed for the simulation, thus overcoming the pspace barrier.

The relative expressive power of the various rule-based languages is summarized in Figure 1. The arrow ⇑ indicates strict inclusion and the arrow ↑ indicates strict inclusion iff ptime pspace.

We note that Datalog extensions with forward chaining semantics that model various active databases are investigated in [START_REF] Picouet | Semantics and expressiveness issues in active databases[END_REF]. The results provide insight into the programming paradigm of active databases, the interplay of various features, and their impact on expressiveness and complexity. In particular, this yields highly expressive active database languages capturing pspace, exptime, expspace, as well as all computable queries, on ordered databases.

Datalog ¬

new ≡ all computable queries ⇑ Datalog ¬¬ ≡ while ↑ well-founded Datalog ¬ ≡ inflationary Datalog ¬ ≡ fixpoint ⇑ stratified Datalog ¬ ⇑ Datalog

Limitations in expressive power

Although the languages discussed here are quite powerful, they have certain shortcomings with regard to expressive power. Indeed, there are very "simple" queries that none of the languages can express. The prototypical example is the evenness query on a unary relation:

even(R) = true if | R | is even f alse if | R | is odd.
where |R| is the number of elements in R.

This difficulty is not specific to rule-based languages. Indeed, it extends to most deterministic languages. To understand the difficulty involved, consider the natural way to compute the query: remove elements from R one at a time, and keep a binary counter. However, the elements of R are logically undistinguishable one from another, so no deterministic language that adheres to the data independence principle can perform the algorithm just described. There are two ways out: (i) sacrifice data independence, or (ii) sacrifice determinism by allowing a nondeterministic construct to pick an arbitrary element from a set. We will explore each of these tradeoffs in turn. Suspending the data independence principle is modeled by access to an order among the elements in the database (which is a reasonable mathematical metaphor for access to the additional symmetry-breaking information provided by the internal storage).

Intuitively, there is a strong connection between the use of order (i.e., information on the internal storage) and nondeterminism. If a query is implemented using information on internal storage, then the answer may depend on such information and thus appear nondeterministic at the logical level.

The impact of order

The assumption that databases are ordered can have dramatic impact on the expressive power of languages. In ordered databases, the schema is assumed to contain a binary relation providing a total order on the active domain of each instance. With this assumption, it turns out that stratified Datalog ¬ , inflationary Datalog ¬ , and Datalog ¬ with well-founded semantics are all equivalent and express precisely db-ptime. Furthermore, the apparently much weaker semi-positive Datalog ¬ , consisting of Datalog ¬ where negation is only applied to edb relations, is almost as powerful as these languages. The "almost" is due to a technicality concerning the order: we also need to assume that the minimum and maximum constants are explicitly given. Surprisingly, these constants, that can be computed with an FO query if an order is given, cannot be computed with semi-positive programs. Theorem 4.7. Stratified Datalog ¬ , Datalog ¬ with well-founded semantics, and inflationary Datalog ¬ are equivalent on ordered databases and express exactly the db-ptime queries. They are also equivalent to semi-positive Datalog ¬ on ordered databases with min and max and express exactly the db-ptime queries.

The result that semi-positive Datalog ¬ expresses db-ptime on ordered databases with min and max is due to [START_REF] Papadimitriou | A note on the expressive power of prolog[END_REF]. The result that inflationary Datalog ¬ expresses db-ptime follows from results in [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF] (equivalence of inflationary Datalog ¬ and fixpoint) and [START_REF] Immerman | Relational queries computable in polynomial time[END_REF][START_REF] Vardi | The complexity of relational query languages[END_REF] (who showed that fixpoint expresses db-ptime on ordered databases).

Without the order assumption, there is no known deterministic language that expresses precisely the db-ptime queries. Indeed, the existence of such a language remains one of the main open problems in the theory of query languages (e.g., see [START_REF] Grohe | The quest for a logic capturing PTIME[END_REF]).

The following characterizes the power of Datalog ¬¬ on ordered databases. It follows from a result of [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF] showing the equivalence of Datalog ¬¬ and while, and from a result of [START_REF] Vardi | The complexity of relational query languages[END_REF] showing that while expresses db-pspace on ordered databases. Theorem 4.8. Datalog ¬¬ expresses exactly the db-pspace queries on ordered databases.

NONDETERMINISTIC LANGUAGES

The arguments in favor of nondeterministic languages are both practical and theoretical. The first is that nondeterminism occurs naturally in many practical settings. There are natural nondeterministic queries and updates, whose implementation using deterministic languages is contrived and inefficient. There are well-known applications in Artificial Intelligence which naturally lead to nondeterminism, and expert systems shells (such as KEE or OPS5 [START_REF] Brownston | Programming Expert Systems in OPS5: An Introduction to Rule-Based Programming[END_REF][START_REF] Forgy | OPS5 user's manual[END_REF]) whose rule-based components work nondeterministically. Reactive systems, such as data-driven workflows, are usually nondeterministic (e.g., see [START_REF] Abiteboul | The Active XML project: an overview[END_REF][START_REF] Abiteboul | A rule-based language for web data management[END_REF][START_REF] Abiteboul | Collaborative data-driven workflows: think global, act local[END_REF][START_REF] Green | ORCHESTRA: facilitating collaborative data sharing[END_REF]). The theoretical arguments for nondeterminism involve primarily the expressive power of nondeterministic languages. Indeed, the use of nondeterminism circumvents some of the expressiveness limitations discussed above, associated with deterministic languages. As mentioned, it is conjectured that there is no deterministic language expressing exactly the queries computable in polynomial time. On the other hand, there are nondeterministic languages expressing exactly the (deterministic and nondeterministic) queries computable in polynomial time.

Nondeterministic Datalog ¬(¬)

We next consider nondeterministic versions of the Datalog ¬(¬) languages. Recall that the procedural, deterministic semantics for these languages was the result of evaluating programs by repeatedly firing all rules in parallel, up to a fixpoint. The nondeterministic semantics is obtained by firing one instantiation of a rule at a time, based on a nondeterministic choice. For instance consider the program:

¬G(x, y) ← G(x, y), G(y, x).
With deterministic semantics, the program removes from the graph G all cycles of length two. With the nondeterministic semantics, the program computes one of several possible "orientations" for G (i.e., for every pair of edges (x, y) and (y, x) in G, one of the edges is removed).

We first define the syntax of the nondeterministic version of Datalog ¬¬ , denoted N-Datalog ¬¬ [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF]. The difference with the deterministic version is that heads of rules may contain several literals, and equality can be used in bodies. It can be seen that these features would be redundant with the deterministic semantics. Definition 5.1. A N-Datalog ¬¬ program is a finite set of rules of the form

A 1 ,...,A k ← B 1 ,...,B n (k ≥ 1, n ≥ 0)
, where each A j is a literal of the form (¬) Q(x 1 ,...,x m ) (m ≥ 0), and each B i is a literal of the same form, or (¬) x 1 = x 2 (the x i 's are variables or constants). It is required that each variable occurring in the head of a rule also occur positively bound in the body. □ To formally define the nondeterministic semantics, we introduce the notion of (nondeterministic) immediate successor of a set of facts using a rule. Let r be an N-Datalog ¬¬ rule. Let I be a set of facts and r ′ be an instantiation of r such that (i) each literal of the body of r ′ is true in I , (ii) the head of r ′ is consistent and (iii) each variable is valuated to some constant occurring in I . Then the instance J obtained from I by deleting the facts A such that ¬A is in the head of r ′ , and inserting the facts A in the head of r ′ , is called an immediate successor of I using r .

By condition (ii) above, an instantiation of a rule is not considered if its head contains a literal and its negation. Definition 5.2. Let P be an N-Datalog ¬¬ program. The effect of P is a relation over sets of facts defined as follows: for each I , (I, J ) is in eff(P) iff there exists a sequence I 0 = I, ..., I n = J such that (i) for each i, I i+1 is an immediate successor of I i using some r in P, and (ii) there is no immediate successor J ′ J of J using some rule in P. □

The language N-Datalog ¬ is a specialization of N-Datalog ¬¬ obtained by disallowing negative literals in heads of rules (thus, negation can only occur in bodies of rules).

Expressive power

We present several results on the expressive power of N-Datalog ¬ and N-Datalog ¬¬ . As discussed earlier, the most significant result involves expressibility of ndb-ptime.

We consider first the expressive power of N-Datalog ¬¬ .

Theorem 5.3.

[6] N-Datalog ¬¬ expresses exactly ndb-pspace.

Consider next the expressive power of N-Datalog ¬ . It is easy to see that each N-Datalog ¬ query is in ndb-ptime. It turns out that there are simple ndb-ptime queries that cannot be expressed in N-Datalog ¬ . We show this next, and then show how N-Datalog ¬ can be augmented to increase the expressive power to ndb-ptime.

The strict inclusion in ndb-ptime is shown using the following example [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF].

Example 5.4. Let R = {P(A),Q(AB)}. It can be shown that there is no N-Datalog ¬ program which computes Pπ A (Q).

The precise characterization of the power of N-Datalog ¬ is open. We note, however, that N-Datalog ¬ expresses exactly ndb-ptime in the presence of order. As seen in the example above, there are very simple queries that N-Datalog ¬ cannot compute. We now look at the origin of this weakness and show how it can be corrected. Note that N-Datalog ¬ does not provide sufficient control capability to simulate the composition of two programs. Indeed, P -π A (Q) can be obtained as the composition of the mappings defined by the following two rules:

T (x) ← Q(x, y), and answer (x) ← P(x), ¬T (x).

The weak control capability of N-Datalog ¬ makes it impossible for programs in this language to simulate the explicit control necessary to compute ndb-ptime queries. Note that, in the case of N-Datalog ¬¬ , the control needed is provided by deletions. For example, the query in Example 5.4 is computed by the following N-Datalog ¬¬ program:

answer (x) ← P(x) ¬answer (x), ¬P(x) ← Q(x, y).
The constructs we add to N-Datalog ¬ essentially provide sufficient control to simulate composition (in an inflationary manner). We consider two alternative constructs. The first construct allows for an "inconsistency" symbol ⊥ to appear in heads of rules. The resulting language is denoted N-Datalog ¬ ⊥. The idea is that if such a symbol is derived in a computation, that particular computation is abandoned. The second construct is universal quantification in bodies of rules and yields the language N-Datalog ¬ ∀. We first present N-Datalog ¬ ⊥, then N-Datalog ¬ ∀. These languages are from [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF].

N-Datalog ¬ ⊥: The language N-Datalog ¬ is extended with the symbol ⊥ that can occur only as a literal in the head of rules. A pair (I,J) is in the effect of a N-Datalog ¬ ⊥ program iff J is obtained by a computation where ⊥ is not derived.

N-Datalog ¬ ∀: The language N-Datalog ¬ is extended to allow rules of the form:

A 1 , ..., A q ← ∀ì xB 1 , ..., B n ,
where ì

x is a sequence of variables occurring only in the body of the rule. Let ì y be the vector of the variables occurring in B 1 , ..., B n and not in ì

x, and v be a valuation of ì y. The rule is fired with valuation v if for each extension v of v to the variables in ì

x (which valuates variables in ì

x in the active domain), vB 1 ∧ ... ∧ vB n holds. To illustrate these two languages, we show how to compute the query of Example 5.4 with N-Datalog ¬ ∀ or N-Datalog ¬ ⊥ programs.

Example 5.5. The mapping Pπ A (Q) is computed by the following N-Datalog ¬ ∀ program: answer (x) ← ∀yP(x), ¬Q(x, y).

A N-Datalog ¬ ⊥ program computing the same query is:

PRO J (x)
← ¬done-with-proj, Q(x, y) done-with-proj ← ⊥ ← done-with-proj, Q(x, y), ¬PRO J (x) answer (x) ← done-with-proj, P(x), ¬PRO J (x).

Intuitively, in N-Datalog ¬ ∀, one can check that a stage is completed (using ∀) before proceeding to the next one; this allows simulating composition. In N-Datalog ¬ ⊥, a detected error leads to the derivation of ⊥. The following shows that in fact these constructs provide sufficient power to bridge the gap between N-Datalog ¬ and ndb-ptime. Theorem 5.6. [START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF] For each query τ the following are equivalent:

• τ is in ndb-ptime,
• τ is defined by a N-Datalog ¬ ⊥ program, and • τ is defined by a N-Datalog ¬ ∀ program.

We have seen so far nondeterministic languages capturing ndbpspace and ndb-ptime. Similarly to the deterministic case, a complete language can be obtained by augmenting N-Datalog ¬ with the ability to create new values. The resulting language is denoted N-Datalog ¬ new .

Theorem 5.7.

[6] N-Datalog ¬ new expresses all nondeterministic queries.

It turns out that the nondeterministic languages described above are closely related to nondeterministic extensions of fixpoint logics, introduced in [START_REF] Abiteboul | Fixpoint extensions of first-order logic and Datalog-like languages[END_REF] (see also [START_REF] Abiteboul | Non-determinism in logic-based languages[END_REF]). In these languages, nondeterminism is provided by a witness operator W . Informally, W xφ( x) results in nondeterministically choosing a value of x that satisfies φ( x). The addition of W to fixpoint logics yields nondeterministic extensions FO + IFP + W of inflationary fixpoint logic, and FO + PFP + W of partial fixpoint logic. It is shown in [START_REF] Abiteboul | Fixpoint extensions of first-order logic and Datalog-like languages[END_REF] that N-Datalog ¬¬ is equivalent to FO + PFP + W , and N-Datalog ¬ ∀ (as well as N-Datalog ¬ ⊥) is equivalent to FO + IFP + W .

We note that another way to introduce nondeterminism in rulebased languages is provided by the choice operator first presented in [START_REF] Krishnamurthy | Nondeterministic choice in datalog[END_REF]. This construct has been included in the language LDL, an implementation of Datalog ¬ [START_REF] Naqvi | A language for data and knowledge bases[END_REF]. Variations of the choice operator, and its connection with stable models of Datalog ¬ programs, are further studied in [START_REF] Giannotti | Nondeterminism in deductive databases[END_REF][START_REF] Saccà | Stable models and non-determinism in logic programs with negation[END_REF]. The expressive power of the choice operator in the context of Datalog is investigated in [START_REF] Corciulo | Datalog with non-deterministic choice computes NDB-PTIME[END_REF]. The main result exhibits a language expressing exactly ndb-ptime. Further Datalog languages using the choice operator and expressing the Boolean hierarchy are exhibited in [START_REF] Greco | Extending stratified datalog to capture complexity classes ranging from P to QH[END_REF].

Connections with Determinism

Recall that one of the motivations for considering nondeterministic languages is their ability to express more deterministic queries. In this section we consider the ability of various nondeterministic languages to express deterministic queries. We also consider the deterministic queries definable by considering the "possible" and "certain" answers of a nondeterministic query, in the spirit of queries on databases with incomplete information. The results are from [START_REF] Abiteboul | Non-deterministic languages to express deterministic transformations[END_REF].

The notion of deterministic fragment expressed by a language is defined next.

Definition 5.8. The deterministic fragment of a (nondeterministic) language is the set of deterministic queries defined by programs in the language. The deterministic fragment of a language L is denoted det(L). □

In the previous section we characterized the nondeterministic queries expressible in the various languages. These results can be used to characterize the deterministic fragments expressible in these languages. Thus, we have: Theorem 5.9.

(1) det(N-Datalog ¬ ∀) = det(N-Datalog ¬ ⊥) = db-ptime.

(2) det(N-Datalog ¬¬ ) = db-pspace.

It is important to note that (1) does not provide a language expressing db-ptime, since it is undecidable whether a N-Datalog ¬ ∀ or N-Datalog ¬ ⊥ program defines a deterministic query.

An alternative way of obtaining deterministic queries using nondeterministic programs is suggested by the work of [START_REF] Imielinski | The relational model of data and cylindric algebras[END_REF] on incomplete information. Indeed, there is a natural connection between incomplete information and nondeterminism. As noted in [START_REF] Abiteboul | Update semantics for incomplete databases[END_REF], incomplete information can be seen as resulting from incompletely specified (therefore nondeterministic) updates. The notions of possible and certain answers in [START_REF] Imielinski | The relational model of data and cylindric algebras[END_REF] suggest the following definition: The poss or cert semantics yield significant power: Theorem 5.11.

(1) poss(N-Datalog ¬ ∀) = poss(N-Datalog ¬ ⊥) = db-np.

(2) cert(N-Datalog ¬ ∀) = cert(N-Datalog ¬ ⊥) = db-co-np.

(3) cert(N-Datalog ¬¬ ) = poss(N-Datalog ¬¬ ) = db-pspace.

Observe that, for N-Datalog ¬¬ , the poss and cert semantics do not yield additional power. In particular, these semantics can be simulated within the deterministic fragment of N-Datalog ¬¬ . This concludes our review of the Datalog-like languages with forward chaining semantics, studied in [START_REF] Abiteboul | Non-deterministic languages to express deterministic transformations[END_REF][START_REF] Abiteboul | Procedural and declarative database update languages[END_REF][START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF][START_REF] Abiteboul | Non-determinism in logic-based languages[END_REF][START_REF] Abiteboul | Fixpoint extensions of first-order logic and Datalog-like languages[END_REF][START_REF] Abiteboul | Non-determinism in logic-based languages[END_REF][START_REF] Vianu | Rule-based languages[END_REF]. We next discuss briefly some of the developments in Datalog research since these languages have been proposed, and situate them in the broader context.

DATALOG REDUX

Over time, research on recursive queries has been received by the database systems community with varying degrees of enthusiasm. By the end of the 80's, the attitude towards Datalog research had turned largely negative. This is perhaps best exemplified by the influential Laguna Beach report of 1989 [START_REF]Future directions in DBMS research[END_REF], which includes this statement: "The participants were unanimously negative on the prospective research contribution of general recursive query processing, and interfaces between a DBMS and Prolog. " As late as 1998, the no less influential [START_REF]Readings in Database Systems[END_REF], stated that "No practical applications of recursive query processing have been found to date".

And yet they persisted. Despite the ups-and-downs in popularity, work on Datalog-like languages continued in the database and logic programming communities in the 80's and 90's. On the theoretical front, there was much work on the expressiveness and complexity of Datalog-like languages (for a comprehensive survey, see [START_REF] Dantsin | Complexity and expressive power of logic programming[END_REF]). Driven by theoretical and practical considerations, many extensions of Datalog have been put forward. They include arithmetic, sets, disjunction, aggregation, constraints, object-oriented constructs, complex objects, updates, etc. This has resulted in an entire ecosystem of languages, many of which were implemented. An excellent survey of these developments is provided in [START_REF] Maier | Datalog: concepts, history, and outlook[END_REF].

Research on Datalog was eventually rehabilitated in the database systems community and beyond. In an invited PODS 2010 talk [START_REF] Hellerstein | Datalog redux: experience and conjecture[END_REF] and companion paper [START_REF] Hellerstein | The declarative imperative: experiences and conjectures in distributed logic[END_REF], Joe Hellerstein delivered an impassioned rehabilitation of Datalog from the viewpoint of the systems community, pointing out the widespread use and effectiveness of Datalog-like languages in areas as diverse as security and privacy protocols, program analysis, natural language processing, probabilistic inference, modular robotics, multiplayer games, telecom diagnosis, networking, and distributed systems.

The last two decades have seen a robust "Datalog Spring" in which Datalog research has expanded with renewed energy. The sequence of Datalog workshops on the theme of the "Resurgence of Datalog in Academia and Industry" [START_REF]Datalog 2.0 2019 -3rd International Workshop on the Resurgence of Datalog in Academia and Industry co-located with the 15th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2019) at the Philadelphia Logic Week 2019[END_REF][START_REF]Datalog in Academia and Industry -Second International Workshop, Datalog 2[END_REF][START_REF]Datalog Reloaded -First International Workshop, Datalog 2010[END_REF] was emblematic of this optimism. A broad account of this renewed activity, within and beyond the database community, can be found in [START_REF] Maier | Datalog: concepts, history, and outlook[END_REF]. Notable in the database theory community has been an increased symbiosis between theoretical research and practice (even yielding a number of start-ups!), as well as increased presence in adjacent areas such as AI and Knowledge Representation. Following are a few representative examples.

Datalog for networking Networking is an area where recursive processing and reasoning occurs naturally, and has led to the rise of "declarative networking", in which Datalog variants are used to specify and reason about distributed protocols and services (e.g., see [START_REF] Hellerstein | The declarative imperative: experiences and conjectures in distributed logic[END_REF][START_REF] Boon | Declarative networking[END_REF][START_REF] Boon | Recent advances in declarative networking[END_REF]). These languages extend Datalog with a variety of features, including location identifiers, timestamps, and states (in the spirit of Statelog [START_REF] Lausen | On active deductive databases: The Statelog approach[END_REF]). Dedalus and Bloom, both Datalog variants, were put forward by Hellerstein's team as a promising foundation for programming and reasoning about distributed systems [START_REF] Alvaro | Consistency analysis in Bloom: a CALM and collected approach[END_REF][START_REF] Alvaro | Dedalus: Datalog in time and space[END_REF]. Their investigation of consistency properties of distributed systems led to the so called "CALM conjecture", [START_REF] Hellerstein | Datalog redux: experience and conjecture[END_REF][START_REF] Hellerstein | The declarative imperative: experiences and conjectures in distributed logic[END_REF] which was subsequently studied in the database theory community using a model of communicating transducers [START_REF] Tom | Declarative networking: Recent theoretical work on coordination, correctness, and declarative semantics[END_REF][START_REF] Ameloot | Deciding eventual consistency for a simple class of relational transducer networks[END_REF][START_REF] Ameloot | Putting logic-based distributed systems on stable grounds[END_REF][START_REF] Ameloot | Weaker forms of monotonicity for declarative networking: A more fine-grained answer to the calm-conjecture[END_REF][START_REF] Ameloot | Relational transducers for declarative networking[END_REF]. The use of the declarative approach in network monitoring was also explored in [START_REF] Abiteboul | Diagnosis of asynchronous discrete event systems: datalog to the rescue![END_REF]. It should be noted that the term "declarative" refers broadly to Datalog-like rule-based languages, with a mix of declarative and procedural semantics (e.g., see [START_REF] Antonio | Operational semantics for declarative networking[END_REF]). Negation, when present, is typically restricted to be stratified (and interpreted under stratified semantics). See [START_REF] Boon | Recent advances in declarative networking[END_REF] for a survey on declarative networking circa 2012.

Datalog for data extraction The Lixto project [START_REF] Baumgartner | Visual web information extraction with lixto[END_REF][START_REF] Gottlob | The lixto data extraction project -back and forth between theory and practice[END_REF] is a poster child for successful practical applications of Datalog relying on significant theoretical foundations. Lixto focuses on Web data extraction and has at its core Monadic Datalog over trees. The approach relies on deep and elegant theoretical results on the expressiveness and complexity of Monadic Datalog on trees and structures of bounded tree width [START_REF] Gottlob | Monadic queries over tree-structured data[END_REF][START_REF] Gottlob | Monadic datalog and the expressive power of languages for web information extraction[END_REF][START_REF] Gottlob | Function symbols in tuple-generating dependencies: Expressive power and computability[END_REF][START_REF] Gottlob | Bounded treewidth as a key to tractability of knowledge representation and reasoning[END_REF][START_REF] Gottlob | Tractable database design through bounded treewidth[END_REF][START_REF] Gottlob | Abduction with bounded treewidth: From theoretical tractability to practically efficient computation[END_REF][START_REF] Gottlob | Monadic datalog over finite structures of bounded treewidth[END_REF]. In particular, it is shown in [START_REF] Gottlob | Monadic datalog and the expressive power of languages for web information extraction[END_REF] that Monadic Datalog captures exactly Monadic Second Order logic over trees. This provides the expressiveness needed by wrappers for Web data extraction, while also guaranteeing efficiency. The Lixto project has been incorporated in a commercial product, McKinsey Periscope. A follow-up project, DIADEM, aimed to achieve fully automatic wrapper generation and uses at its core a related language based on Datalog [START_REF] Furche | DIADEM: thousands of websites to a single database[END_REF].

Datalog for ontologies Datalog has proven to be an effective formalism for specifying and answering queries over ontologies. In particular, it provides an elegant unifying formalism that subsumes well-known description logics. Datalog+/-is a family of Datalog variants put forward for this purpose [START_REF] Calì | Datalog ± : a unified approach to ontologies and integrity constraints[END_REF][START_REF] Calì | Datalog ± : a unified approach to ontologies and integrity constraints[END_REF][START_REF] Calì | Datalog+/-: A family of logical knowledge representation and query languages for new applications[END_REF]. The Datalog+/-languages are obtained by first extending Datalog with existentially quantified variables in heads of rules, then considering various restrictions (guarded, linear, and weakly guarded) to ensure tractability. Other extensions, such as falsity in heads of rules, keys, and stratified negation, are also considered, and their complexity characterized. Importantly, the Datalog+/-family of languages can express the popular DLite family [START_REF] Calvanese | Dl-lite: Tractable description logics for ontologies[END_REF][START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF] of descriprion logics. It also subsumes F-logic Lite [START_REF] Calì | Containment of conjunctive object meta-queries[END_REF], a tractable fragment of the well-known F-logic [START_REF] Kifer | Logical foundations of objectoriented and frame-based languages[END_REF], central in deductive object-oriented databases.

Datalog for knowledge graphs An outgrowth of Datalog+/-, Vadalog is a Datalog-based language geared towards reasoning about knowledge graphs [START_REF] Bellomarini | Swift logic for big data and knowledge graphs[END_REF][START_REF] Bellomarini | The Vadalog system: Datalog-based reasoning for knowledge graphs[END_REF][START_REF] Berger | The space-efficient core of Vadalog[END_REF]. Vadalog has at its core Warded Datalog+/-, a variant of Datalog+/-that has good properties in terms of expressiveness and complexity [START_REF] Arenas | Expressive languages for querying the semantic web[END_REF][START_REF] Gottlob | Beyond SPARQL under OWL 2 QL entailment regime: Rules to the rescue[END_REF]. Vadalog is part of the VADA project [START_REF] Konstantinou | The VADA architecture for costeffective data wrangling[END_REF]112], in which Vadalog is extended with various features, including access to external resources such as text processing, data analytics and machine learning, modeled uniformly as transducers. The VADA project has generated considerable interest from industrial partners. Data analytics on big graphs is also provided by the BigDatalog system [START_REF] Shkapsky | Big data analytics with datalog queries on spark[END_REF] that relies on Datalog extended with aggregates, with fixpoint semantics [START_REF] Zaniolo | Fixpoint semantics and optimization of recursive datalog programs with aggregates[END_REF].

Datalog for data exchange on the Web Datalog variants are used in several approaches for high-level specifications of data sharing and exchange on the Web. Orchestra [START_REF] Green | ORCHESTRA: facilitating collaborative data sharing[END_REF][START_REF] Ives | The ORCHESTRA collaborative data sharing system[END_REF] is a collaborative data sharing system that supports the exchange of data and updates among peers and relies on an extension of Datalog with Skolem functions. Webdamlog is a Datalog variant used to exchange data among peers on the Web, with the novel twist that rules can also be exchanged, in addition to data [START_REF] Abiteboul | A rule-based language for web data management[END_REF]. Webdamlog also uses updates in heads of rules, similarly to N-Datalog ¬¬ (see Section 4.2). The semantics is nondeterministic and based on forward chaining, similarly to active rules. Interestingly, the abilty to exchange rules is more than syntactic sugar: it increases the expressiveness of the language. The exchange of rules is also used in Active XML, whose core is a rule-based language using tree patterns [START_REF] Abiteboul | The Active XML project: an overview[END_REF][START_REF] Abiteboul | Static analysis of active XML systems[END_REF].

Datalog for data management Several startups have emerged that provide full data management systems relying on Datalog variants. LogicBlox is a commercial database system that supports sophisticated analytics and is implemented on top of LogiQL, a rich extension of Datalog [START_REF] Aref | Design and implementation of the LogicBlox system[END_REF]. LogiQL can support business applications, workflows and data analytics, and is evaluated bottom-up. LogicBlox also contains updates needed for interactive features, in the spirit of Datalog ¬¬ [START_REF] Green | Datalog and recursive query processing[END_REF]. Interestingly, the LogicBlox team included a substantial number of database theoreticians and produced some remarkable algorithms, such as the leapfrog trie join, shown to be optimal [START_REF] Todd | Triejoin: A simple, worst-case optimal join algorithm[END_REF] in the sense of [START_REF] Ngo | Worst-case optimal join algorithms[END_REF]. DATOMIC is another startup that has built a full data management system driven by a Datalog-like language [START_REF] Anderson | The Datomic database[END_REF].

CONCLUSION

We have reviewed the procedural, forward chaining approach to Datalog developed in [START_REF] Abiteboul | Non-deterministic languages to express deterministic transformations[END_REF][START_REF] Abiteboul | Procedural and declarative database update languages[END_REF][START_REF] Abiteboul | Datalog extensions for database queries and updates[END_REF][START_REF] Abiteboul | Non-determinism in logic-based languages[END_REF][START_REF] Abiteboul | Fixpoint extensions of first-order logic and Datalog-like languages[END_REF][START_REF] Abiteboul | Non-determinism in logic-based languages[END_REF][START_REF] Vianu | Rule-based languages[END_REF], and briefly the state of contemporaneous Datalog research and later developments.

How does the procedural, forward chaining semantics measure up against the declarative alternative? The two paradigms are philosophically very different. The declarative approach attempts to model a natural reasoning process. In particular, consistency in the reasoning process is required: one cannot use a fact and later infer its negation, as can happen in the procedural semantics. As we have seen, the solution is ideally described as a model of the program satisfying certain desirable properties, such as minimality. However, in the presence of negation, the lack of a unique minimal model leads to the need to specify an "intended" model among several possible candidates. Beyond stratified semantics, the criteria for selecting the intended model become increasingly contrived. Furthermore, the assumption that the chosen criterion captures a fictitious programmer's natural reasoning process rests on shallow ground.

In contrast, the procedural, forward chaining approach provides semantics that is extremely simple to describe. However, the semantics is purely computational and does not yield a solution easily justifiable in model theoretic terms, beyond the fact that the answer is one model of the program. Also, despite the simplicity of the computational semantics, programs can be hard to understand, as their effect is very sensitive to timing (e.g., see Examples 4.1 and 4.3). In terms of expressiveness, the Datalog-like languages with forward chaining semantics provide a unifying formalism capable of capturing the main classes of queries, including fixpoint, while, and all the way to computable queries. They can also incorporate in a natural manner nondeterminism and updates. Declarative semantics seems to hit an expressiveness ceiling with well-founded semantics, capturing the fixpoint queries.

The final test for the various semantics has to rest with programmers and adoption in practical languages. In that respect, the forward chaining approach was an early leader, having been adopted in production systems and expert systems [START_REF] Brownston | Programming Expert Systems in OPS5: An Introduction to Rule-Based Programming[END_REF][START_REF] Forgy | OPS5 user's manual[END_REF] as well as active databases [START_REF] Widom | Active Database Systems: Triggers and Rules for Advanced Database Processing[END_REF], at a time when implementations of deductive databases were limited to prototypes (see [START_REF] Ramakrishnan | A survey of deductive database systems[END_REF] for an early survey of deductive database implementations). Subsequently, the landscape became much more diverse. There have been many implementations of Datalog variants, with declarative and procedural semantics (e.g., see [START_REF] Maier | Datalog: concepts, history, and outlook[END_REF]). Most practical Datalog-like languages use stratified negation, which emerges as the indisputable success story of declarative semantics. As seen above, Datalog-like languages with forward chaining semantics, with features including updates and nondeterminism, remain common in a limited class of applications, mostly those that can be viewed as data-driven reactive systems. Such applications include active databases, production systems, data-driven workflows, peer-to-peer data exchange, and systems supporting interactive features (e.g., see [START_REF] Abiteboul | The Active XML project: an overview[END_REF][START_REF] Abiteboul | A rule-based language for web data management[END_REF][START_REF] Calvanese | Foundations of data-aware process analysis: a database theory perspective[END_REF][START_REF] Deutsch | Automatic verification of databasecentric systems[END_REF][START_REF] Green | Datalog and recursive query processing[END_REF][START_REF] Antonio | Operational semantics for declarative networking[END_REF][START_REF] Widom | Active Database Systems: Triggers and Rules for Advanced Database Processing[END_REF]).

Overall, the forward chaining paradigm has demonstrated its theoretical appeal and persistence in practice. It will most likely continue to provide a useful alternative within the rich landscape of Datalog.

Example 4 . 1 .

 41 We present a Datalog ¬ program with input a graph in binary relation G. The program computes the relation closer (x, y, x ′ , y ′ ) defined as follows:

  where d(a, b) denotes the distance between nodes a and b in G.

Example 4 . 4 .

 44 Let G be a binary relation schema. Consider the fixpoint program дood + = ∅; while chanдe do дood + = φ where φ = ∀y (G(y, x) → дood(y)).

Figure 1 :

 1 Figure 1: Relative expressive power of Datalog variants.

Definition 5 . 10 .

 510 Given a nondeterministic program P, the image of an input I under P with the possibility semantics (denoted poss(I, P)) and the certainty semantics (denoted cert(I, P)) are defined by: poss(I, P) = {J | (I, J) ∈ eff(P)}, and cert(I, P) = {J | (I, J) ∈ eff(P)}. The deterministic queries expressed by a program P under possibility semantics is denoted poss(P), and under certainty semantics cert(P). For a language L, poss(L) = {poss(P) | P ∈ L} and cert(L) = {cert(P) | P ∈ L}.

•

  The nondeterministic query whose answer is obtained by deleting one of the edges ⟨a, b⟩ or ⟨b, a⟩ for every cycle {⟨a, b⟩, ⟨b, a⟩} is a query in ndb-ptime.• The query whose answer is a unary relation which is empty if the graph has no Hamiltonian circuit and is the set of vertices of the graph otherwise, is in db-np (because testing for Hamiltonicity has complexity np).

  R n are relation names, and u 1 , . . . , u n are free tuples (tuples of variables and constants). Each variable occurring in u 1 must occur in at least one of u 2 , . . . , u n . A Datalog program is a finite set of Datalog rules. The head of the rule is the expression R 1 (u 1 ); and R 2 (u 2 ), . . . , R n (u n ) forms the body.

ACKNOWLEDGMENTS

This work was supported in part by the ANR Headwork project ANR-16-CE23-0015 and the National Science Foundation under award III-1815247. The author is grateful to Pierre Bourhis and Luc Segoufin for their insightful comments on this paper. Special thanks to Serge Abiteboul for revisiting our joint work and providing many useful suggestions for the presentation.