Nondeterministic, Nonmonotonic Logic Databases.
AbstractWe consider in this paper an extension of Datalog with mechanisms for temporal, nonmonotonic, and nondeterministic reasoning, which we refer to as Datalog++. We show, by means of examples, its flexibility in expressing queries concerning aggregates and data cube. Also, we show how iterated fixpoint and stable model semantics can be combined to the purpose of clarifying the semantics of Datalog++ programs and supporting their efficient execution. Finally, we provide a more concrete implementation strategy on which basis the design of optimization techniques tailored for Datalog++ is addressed.
Introduction
Motivations. The name Datalog++ is used in this paper to refer to Datalog
extended with mechanisms supporting:
- a limited form of temporal reasoning, by means of temporal, or stage, arguments
of relations, ranging over a discrete temporal domain, in the style
of [5];
- nonmonotonic reasoning, by means of a form of stratified negation w.r.t. the
stage arguments, called XY-stratification [26];
nondeterministic reasoning, by means of the nondeterministic choice construct
[12].
which is essentially a fragment of LDL++ [2], and is advocated
in [27, Chap. 10], revealed a highly expressive language, with applications in
diverse areas such as AI planning [4], active databases [25], object databases
[8], semistructured information management and Web restructuring [10], data
mining and knowledge discovery in databases [15, 3, 11]. However, a thorough
study of the semantics of Datalog++ is still missing, which provides a basis to
sound and efficient implementations and optimization techniques. A preliminary
study of the semantics of Datalog++ is sketched in [4], by discussing the relation
between a declarative (model-theoretic) semantics and a fixpoint (bottom-up)
semantics. This discussion is however informal, and moreover fails to achieve
a precise coincidence of the two semantics for arbitrary programs. We found
therefore motivated an in-depth study of the semantics of Datalog++ programs,
which also explains the reason of the missing coincidence of semantics in [4], and
proposes a general condition which ensures such coincidence.
Objectives and contributions. This paper is aimed at
1. illustrating the expressiveness and flexibility of Datalog++ as a query language

2. providing a declarative semantics for Datalog++, which integrates the tem-
poral, nonmonotonic and nondeterministic mechanisms, and which justifies
the adoption of an iterated fixpoint semantics for the language;
3. providing the basis for query optimization in Datalog++, thus making it
viable an efficient implementation.
To this purpose, we proceed as follows:
1. the use of Datalog++ as a query language is discussed in Section 2;
2. a natural, purely declarative, semantics for Datalog++ is assigned using the
notion of a stable model in Section 3; a constructive semantics is then assigned
using an iterative procedure which exploits the stratification induced by the
progression of the temporal argument;
3. in the main result of this paper, we show that the two semantics are equiva-
lent, provided that a natural syntactic restriction is fulfilled, which imposes
a disciplined use of the temporal argument within the choice construct.
4. On the basis of this result, we introduce in Section 4 a more concrete operational
semantics using relational algebra operators, and, in Section 5, a
repertoire of optimization techniques, especially tailored for Datalog++. In
particular, we discuss how it is possible to support efficient history-insensitive
temporal reasoning by means of real side-effects during the iterated computation
[19].
The material in Sections 2 and 3 is based on results presented in more compact
form in [9, 14], while the material in Sections 4 and 5 is new. In conclusion, this
paper provides a thorough account of the pragmatics, semantics and implementation
of Datalog++.
Related Work. Nondeterminism is introduced in deductive databases by means
of the choice construct. The original proposal in [17] was later revised in [23],
and refined in [12]. These studies exposed the close relationship connecting non-monotonic
reasoning with nondeterministic constructs, leading to the definition
of a stable model semantics for choice. While the declarative semantics
of choice is based on stable model semantics which is intractable in general,
choice is amenable to efficient implementations, and it is actually supported in
the logic database language LDL [20] and its evolution LDL++ [2].
On the other side, stratification has been a crucial notion for the introduction
of nonmonotonic reasoning in deductive databases. From the original idea in [1]
of a static stratification based on predicate dependencies, stratified negation has
been refined to deal with dynamic notions, as in the case of locally stratified
programs [21] and modularly stratified programs [22]. Dynamic, or local, stratification
has a close connection with temporal reasoning, as the progression of
time points yields an obvious stratification of programs-consider for instance
1S [5]. It is therefore natural that non monotonic and temporal reasoning
are combined in several deductive database languages, such as those in [18], [16],
However, a striking mismatch is apparent between the above two lines of
nondeterminism leads to a multiplicity of (stable) models, whereas
stratification leads to a unique (perfect) model. So far, no comprehensive study
has addressed the combination of the two lines, which occurs in Datalog++, and
which requires the development of a non deterministic iterated fixpoint proce-
dure. We notice however the mentioned exception of [4], where an approach to
this problem is sketched with reference to locally stratified programs augmented
with choice. In the present paper, we present instead a thorough treatment of
programs, and repair an inconvenience of the approach in [4] concerning
the incompleteness of the iterated fixpoint procedure.
Preliminaries. We assume that the reader is familiar with the concepts of
relational databases and of the Datalog language [24]. Various extensions of
are considered in this paper:
- Datalog: is the language with unrestricted use of negation in the body of
the rules;
is the subset of Datalog: consisting of (predicate-)stratified pro-
grams, in the sense of [1];
is the language introduced in [5], where each predicate may have a
designated argument, called a stage argument, ranging over natural numbers
(where each natural number n is represented by the term s n (nil));
1S is the language Datalog 1S with an unrestricted use of negation in
rule bodies;
- Datalog++ is the subset of
1S where negation is used in a disciplined
manner, according to the mechanisms of XY-stratification and nondeterministic
choice, which are introduced in the next Section 2.
Query Answering with Datalog++
Datalog, the basis of deductive databases, is essentially a friendly syntax to express
relational queries, and to extend the query facilities of the relational calculus
with recursion. Datalog's simplicity in expressing complex queries impacted
on the database technology, and nowadays recursive queries/views have become
part of the SQL3 standard. Recursive queries find natural applications in all
areas of information systems where computing transitive closures or traversals
is an issue, such as in bill-of-materials queries, route or plan formation, graph
traversals, and so on.
However, it is widely recognized that the expressiveness of Datalog's (recur-
sive) rules is limited, and several extensions, along various directions, have been
proposed. In this paper, we address in particular two such directions, namely
nondeterministic and nonmonotonic reasoning, supported respectively by the
choice construct and the notion of XY-stratification. We introduce these mechanisms
by means of a few examples, which are meant to point out the enhanced
query capabilities.
Nondeterministic choice. The choice construct is used to nondeterministically
select subsets of answers to queries, which obey a specified FD constraint.
For instance, the rule
st ad(St; Ad) / major(St; Area); faculty(Ad; Area); choice((St); (Ad)):
assigns to each student a unique, arbitrary advisor from the same area, since
the choice goal constrains the st ad relation to obey the FD (St ! Ad). There-
fore, if the base relation major is formed by the tuples f!smith, db?, !gray,
se?g and the base relation faculty is formed by the tuples f!brown, db?,
!scott, db?, !miller, se?g, then there are two possible outcomes for the
query st ad(St,Ad): either f!smith, brown?, !gray, miller?g or f!smith,
scott?, !gray, miller?g. In practical systems, such as LDL++, one of these
two solutions is computed and presented as a result.
Thus, a first use of choice is in computing nondeterministic, nonrecursive
queries. However, choice can be combined with recursion, as in the following
rules which compute an arbitrary ordering of a given relation r:
Here root is a fresh constant, conveniently used to simplify the program. If the
base relation r is formed by k tuples, then there are k! possible outcomes for the
query ord r(X; Y), namely a set:
ford r(root; root); ord r(root; t 1
for each permutation ft 1
g of the tuples of r. Therefore, in each possible
outcome of the mentioned query, the relation ord r is a total ordering of the
tuples of r. The double choice constraint in the recursive rule specifies that the
successor and predecessor of each tuple of r is unique.
Interestingly, choice can be employed to compute new deterministic queries,
which are inexpressible in Datalog, as well as in pure relational calculus. A
remarkable example is the capability of expressing aggregates, as in the following
program which computes the summation aggregate over a relation r, which uses
an arbitrary ordering of r computed by ord r:
sum r(root; 0):
sum r(Y; N) / sum r(X; M); ord r(X; Y);
total sum r(N) / sum r(X; N); :ord r(X;
Here, sum r(X,N) is used to accumulate in N the summation up to X, with respect
to the order given by ord r. Therefore, the total sum is reconstructed from
sum r(X; N) when X is the last tuple in the order. Notice the use of (stratified)
negation to the purpose of selecting the last tuple. In practical languages, such
as LDL++, some syntactic sugar for aggregation is used as an abbreviation of
the above program [26]:
total sum r(sum ! X ?) / r(X):
On the basis of this simple example, more sophisticated forms of aggregation,
such as datacube and other OLAP functions, can be built. As an example, consider
a relation sales(Date, Department, Sale), and the problem of aggregating
sales along the dimensions Date and Department. Three aggregation patterns
are then possible, corresponding to the various facets of the datacube: !Date,*?,
!*,Department?, !*?. The former two patterns correspond to the aggregation
of sales along a single dimension (respectively Department and Date), and
can be obtained from the original relation by applying the method shown above.
The latter pattern, then, can be obtained by recursively applying such method
to one of the two patterns previously computed, in order to aggregate along the
remaining dimension. In case of several dimensions along which to aggregate we
can simply repeat the process, aggregating at each step along a new (i.e., still
non-aggregated) dimension.
A thorough account on programming with nondeterminism in deductive
databases can be found in [7, 13].
The semantics of choice is assigned using the so-called stable model semantics
of Datalog: programs, a concept originating from autoepistemic logic, which
was applied to the study of negation in Horn clause languages by Gelfond and
Lifschitz [6]. To define the notion of a stable model we need to introduce a
transformation H which, given an interpretation I , maps a Datalog: program
P into a positive Datalog program H(P; I):
Next, we define:
Then, M is said to be a stable model of P if SP In general, Datalog:
programs may have zero, one or many stable models. The multiplicity of stable
models can be exploited to give a declarative account of nondeterminism.
We can in fact define the stable version of a program
Given a Datalog: program P , its stable version
defined as the program obtained from P by replacing all the references
to the choice atom in a rule r : H / B; choice((X); (Y)) (X and Y are
disjunct vectors of variables, that appear also in B) with the atom chosen r
(X; Y).
The chosen r predicate is defined by the following rules:
chosen r
diffchoice r
In the above definition, for any fixed value of X, each choice for Y inhibits all
the other possible ones via diffchoice r
, so that in the stable models of SV (P )
there is (only) one of them. Notice that, by construction, each occurrence of a
choice atom has its own pair of chosen and diffchoice atoms, thus bounding
the scope of the atom to the rule it appears in. The various stable models of
the transformed program SV (P ) thus correspond to the choice models of the
original program.
XY-programs. Another notion used in this paper is that of XY-programs originally
introduced in [26]. The language of such programs is
1S , which admits
negation on body atoms and a unary constructor symbol, used to represent
a temporal argument usually called the stage argument. A general definition of
XY-programs is the following:
(XY-stratification). A set P of
1S rules defining mutually
recursive predicates, is an XY-program if it satisfies the following conditions:
1. each recursive predicate has a distinguished stage argument;
2. every recursive rule r is either an X-rule or a Y-rule, where:
- r is an X-rule when the stage argument in every recursive predicates in
r is the same variable,
- r is a Y-rule when (i) the head of r has a stage argument s(J), where J
is a variable, (ii) some goal of r has J as its stage argument, and (iii) the
remaining recursive goals have either J or s(J) as their stage argument.
Intuitively, in the rules of XY-programs, an atom p(J; ) denotes the extension
of relation p at the current stage (present time) J, whereas an atom p(s(J); )
denotes the extension of relation p at the next stage (future time) s(J). By
using a different primed predicate symbol p 0 in the p(s(J); ) atoms, we obtain
the so-called primed version of an XY-program. We say that an XY-program
is XY-stratified if its primed version is a stratified program. Intuitively, if the
dependency graph of the primed version has no cycles through negated edges,
then it is possible to obtain an ordering on the original rules modulo the stage
1 For ease of presentation, here we include the definition of SV (P ) for the case of at
most one choice atom per rule. The definition for the general case can be found
in [13].
arguments. As a consequence, an XY-stratified program is also locally stratified,
and has therefore a unique stable model that coincides with its perfect model
[21].
Let P be an XY-stratified program. Then, for each i ? 0, define P i as
I is the stage argument of the head of rg
(here r[x=I ] stands for r where I is replaced by x) i.e., P i is the set of rule
instances of P that define the predicates with stage argument s i
the iterated fixpoint procedure for computing the (unique) minimal model of P
can be defined as follows:
1. compute M 0 as the minimal model of P
2. for each j ? 0 compute M j as the minimal model of
Notice that for each j  0, P j is stratified by the definition, and hence its perfect
model M j is computable via an iterated fixpoint procedure.
In this paper, we use the name Datalog++ to refer to the language of XY-
programs augmented with choice goals.
3 A Semantics for
When choice constructs are allowed in XY-programs, a multiplicity of stable
models exists for any given program, and therefore it is needed to clarify how
this phenomenon combines with the iterated fixpoint semantics of choice-free
XY-programs. This task is accomplished in three steps.
1. First, we present a general result stating that, whenever a Datalog: program
P is stratifiable into a hierarchy of recursive cliques (i.e., minimal sets
of mutually recursive rules) any stable model of the entire
program P can be reconstructed by iterating the construction of approximating
stable models, each associated to a clique.
2. Second, we observe that, under a syntactic restriction on the use of the
choice construct that does not compromise expressiveness, Datalog++ programs
can be naturally stratified into a hierarchy of recursive cliques
by using the temporal arguments of recursive predicates.
3. Third, by the observation in 2., we can apply the general result in 1. to
programs, thus obtaining that the stable models of the entire
program can be computed by an iterative fixpoint procedure which follows
the stratification induced by the temporal arguments.
Given a (possibly infinite) program P , consider a (possibly infinite) topological
sort of its distinct recursive cliques Q 1 OE induced by the
dependency relation over the predicates of P . Given an interpretation I , we use
the notation I i to denote the subset of atoms of I whose predicate symbols are
predicates defined in clique Q i .
The following observations are straightforward:
I , and analogously
- the predicates defined in Q i+1 depend only on the definitions in
as a consequence, the interpretation of Q i+1 is I
can ignore
The next definition shows how to transform each recursive clique, within the
given topological ordering, in a self-contained program which takes into account
the information deduced by the previous cliques. Such transformation resembles
the Gelfond-Lifschitz transformation reported in Sect. 2.
Definition 3. Consider a program P , a topological sort of its recursive cliques
and an interpretation I =
I i . Now define
are defined in Q i
are defined in (Q
ut
The idea underlying the transformation is to remove from each clique Q i all the
dependencies induced by the predicates which are defined in lower cliques. We
abbreviate Q red(I)
i by Q red
when the interpretation I is clear by the context.
Example 1. Consider the program and the
recursive cliques r:g. Now, consider
the interpretation I = fs; q; rg. Then Q red
red
The following Lemma 1 states the relation between the models of the transformed
cliques and the models of the program. We abbreviate I
I (i) , and analogously for Q (i) .
Lemma 1. Given a (possibly infinite) Datalog: program P and an interpretation
be the topological sorts on
P and I induced by the dependency relation of P . Then the following statements
are equivalent:
1. SP
2. 8i ? 0: S Q red
3. 8i ? 0: S Q (i)
Proof sketch. The proof is structured as follows: (1) () (3) and (2) () (3).
(3) =) (1) We next show that (a) SP (I) ' I , and (b) I ' SP (I).
(a) Each rule in H(P; I) comes from a rule r of P , which in turn appears
in Q (i) for some i, and then I (i) is a model of r, by the hypothesis. No
atom in I n I (i) appears in r, so also I is model of r. I is then a model
of H(P; I), and hence SP (I) ' I .
(b) If A 2 I , then A 2 I (i) for some i, so (by the hypothesis and definition
of SP ) for each I   such that I  I   . Moreover, for
each I 0 such that I readily checked that for each i
I
(1) =) (3) We observe that I = minfI   j I  which implies:
I
I   (i)
)g.
(2) =) (3) We proceed by induction on i. The base case is trivial. In the
inductive case, we next show that (a) S Q (i) (I (i) ) ' I (i) , and (b) vice versa.
(a) Notice that from the induction hypothesis, I (i)
suffices to show that I (i) (by a simple case analysis).
(b) Exploiting the induction hypothesis, we have I (i\Gamma1) ' S Q (i\Gamma1)
(by definition of H(P; I)). We now show by
induction on n that 8n  0 T n
red
. The base case
In the induction case (n ? 0), if A 2 T n
red
, then
there exists a rule A / b red
red
. Now, by definition of H and Q red
i , there exists a rule:
in Q i such that fc
:e l . Observe now that by definition of H , A / b
Furthermore, by the induction hypothesis and I (i\Gamma1) '
we have the following: fb
Hence, by definition of
, that is A 2 S Q (i) (I (i) ). This
completes the innermost induction, and we obtain that I
(3) =) (2) We proceed is a way similar to the preceding case. To see that
suffices to verify that for each rule instance r with head
A, the following property holds: 8n A 2 T n
red
. For
the converse, we simply observe that I i is a model of Q red
This result states that an arbitrary Datalog: program has a stable model
if and only if each its approximating clique, according to the given topological
sort, has a local stable model. This result gives us an intuitive idea for computing
the stable models of an approximable program by means of the computation of
the stable models of its approximating cliques.
Notice that Lemma 1 holds for arbitrary programs, provided that a stratification
into a hierarchy of cliques is given. In this sense, this result is more
widely applicable than the various notions of stratified programs, such as that of
modularly stratified programs [22], in which it is required that each clique Q red
is locally stratified. On the contrary, we do not require here that each clique is,
in any sense, stratified. This is motivated by the objective of dealing with non
determinism, and justifies why we adopt the (nondeterministic) stable model
semantics, rather than other deterministic semantics for (stratified) Datalog:
programs, such as, for instance, perfect model semantics [21].
We turn now our attention to XY-programs. The result of instantiating the
clauses of an XY-program P with all possible values (natural numbers) of the
stage argument, yields a new program SG(P ) (for stage ground). More precisely,
is a rule of I is the stage argument of rg:
The stable models of P and SG(P ) are closely related:
Lemma 2. Let P be an XY-program. Then, for each interpretation I:
Proof sketch. We show by induction that 8n:T n
which implies the thesis. The base case is trivial. For the inductive case, observe
that since P is XY-stratified, if A 2 T n+1
H(P;I) (;) then for each A /B
I) such that fB
H(SG(P );I) (;), we have that
Vice versa, if A 2 T n+1
(;) then for each A /
such that fB
H(P;I) (;), we have A/
I). ut
However, the dependency graph of SG(P ) (which is obviously the same as P )
does not induce necessarily a topological sort, because in general XY-programs
are not predicate-stratified, and therefore Lemma 1 is not directly applicable.
To tackle this problem, we distinguish the predicate symbol p in the program
fragment P i from the same predicate symbol in all other fragments P j with j 6= i,
by differentiating the predicate symbols using the temporal argument. Therefore,
if p(i; x) is an atom involved in some rule of P i , its modified version is p i
(x). More
precisely, we introduce, for any XY-program P , its modified version SO(P ) (for
stage-out), defined by SO(P
is obtained from
the program fragment P i of SG(P ) by extracting the stage arguments from any
atom, and adding it to the predicate symbol of the atom. Similarly, the modified
version SO(I) of an interpretation I is defined. Therefore, the atom p(i; x) is
in I iff the atom p i
(x) is in SO(I), where i is the value in the stage argument
position of relation p.
Unsurprisingly, the stable models of SG(P ) and SO(P ) are closely related:
Lemma 3. Let P be an XY-program. Then, for each interpretation I:
Proof sketch. It is easy to see that SO(SG(P Hence, the least
Herbrand models of SO(H(SG(P ); I)) and H(SO(P ); SO(I)) coincide. ut
Our aim is now to conclude that, for a given
is the topological sort over SO(P ) in the hypothesis
of Lemma recall that, for i  0, the clique SO(P consists of the rules
from SO(P ) with stage argument i in their heads;
(b) by Lemmas 1, 2 and 3, an interpretation I is a stable model of P iff I can be
constructed as
i0 I i , where, for i  0, I i is a stable model of SO(P ) red(I (i) )
i.e. the clique SO(P reduced by substituting the atoms deduced at stages
earlier than i.
On the basis of (b) above, it is possible to define an iterative procedure to
construct an arbitrary stable model M of P as the union of the interpretations
defined as follows:
Iterated stable model procedure.
Base case. M 0 is a stable model of the bottom clique SO(P
Induction case. For i ? 0, M i is a stable model of SO(P ) red(M (i) )
i.e. the
clique SO(P reduced with respect to M 0 [
The interpretation
is called an iterated stable model of P .
It should be observed that this construction is close to the procedure called
iterated choice fixpoint in [4]. Also, following the approach of [13], each local
stable model M i can in turn be efficiently constructed by a nondeterministic
fixpoint computation, in polynomial time.
Unfortunately, the desired result that the notions of stable model and iterated
stable model coincide does not hold in full generality, in the sense that the iterative
procedure is not complete for arbitrary Datalog++ programs, giving rise to
the inconveniences in [4] mentioned in the introduction. In fact, as demonstrated
by the example below, an undisciplined use of choice in Datalog++ programs
may cause the presence of stable models that cannot be computed incrementally
over the hierarchy of cliques.
Example 2. Consider the following simple
In the stable version SV (P ) of P , the rule defining predicate p is replaced by:
chosen(X) / q(I; X); :diffchoice(X):
In general, SO(P ) i can be composed by more than one clique, so that in the above
expression it should be replaced by SO(P
. However, for ease of
presentation we ignore it, since such general case is trivially deduceable from what
follows.
It is readily checked that SV (P ) admits two stable models, namely fq(0; a);
but only the first model
is an iterated stable models, and therefore the second model cannot be computed
using the iterated choice fixpoint of [4]. ut
The technical reason for this problem is that the free use of the choice construct
inhibits the possibility of defining a topological sort on SO(P ) based on the value
of the stage argument. In the Example 2, the predicate dependency relation of
dependency among stage i and the stages j ? i, because
of the dependency of the chosen predicate from the predicates q i
for all stages
To prevent this problem, it is suffices to require that choice goals refer the
stage argument I in the domain of the associated functional dependency. The
programs which comply with this constraint are called choice-safe.
The following is a way to turn the program of Example 2 into a choice-safe
program (with a different semantics):
This syntactic restriction, moreover, does not greatly compromise the expressiveness
of the query language, in that it is possible to simulate within this
restriction most of the general use of choice (see [19]).
The above considerations are summarized in the following main result of
the paper, which, under the mentioned restriction of choice-safety, is a direct
consequence of Lemmas 1, 2 and 3.
Theorem 1 (Correctness and completeness of the iterated stable model
procedure).
Let P be a choice-safe Datalog++ program and I an interpretation. Then I is a
stable model of SV (P ) iff it is an iterated stable model of P . ut
The following example shows a computation with the iterated stable model
procedure.
Example 3. Consider the following Datalog++ version of the seminaive pro-
gram, discussed in [26], which non-deterministically computes a maximal path
from node a over a graph g:
Assume that the graph is given by eig. The following
interpretations are carried out at each stage of the iterated stable model
procedure:
1. I
(a)g.
2. I
(b)g.
3. I 1
(c)g,
I 2
(d)g
4. I 1
(b); all 3
5. I
By Theorem 1, we conclude that there are two stable models for the program:
I
2 and I
3 . Clearly, any realistic implementation,
such as that provided in LDL++, computes non deterministically only one of
the possible stable models. ut
4 An Operational Semantics for
We now translate the iterated stable model procedure into a more concrete form,
by using relational algebra operations and control constructs. Following the style
of [24], we associate with each predicate p a relation P - same name capitalized.
The elementary deduction step TQ (I) is translated as an assignment to appropriate
relations:
I 0 := TQ (I) /!
i.e., the relations defined in
the clique Q together with the extensional relations, and EVAL(p; Rels) denotes,
in the notation of [24], a single evaluation step of the rules for predicate p with
respect to the current extension of relations in Rels.
We show the translation of Datalog++ cliques incrementally in three steps,
starting with simple Datalog programs and stratified negation, then introducing
the Choice construct and eventually describing how to translate the full language.
The translation of a whole program can be trivially obtained by gathering the
single translated cliques in the natural order.
with stratified negation. We can apply straightforwardly the transformation
given in [24] for safe stratified Datalog programs, where each negative
literal referring to a previously computed or extensional relation is translated to
the complement of the relation w.r.t. the universe of constants:
Translation Template 1
8p defined in
repeat
8p defined in Q last
until 8p defined in Q last P
The translation is illustrated in the following:
Example 4. The program:
is translated to the following naive evaluation procedure, where EVAL(: : :) is
instanced with an appropriate RA query:
repeat
last
last
last P:
Adding Choice. Now we need to translate in relational algebra terms the operations
which compose a nondeterministic computation. Following the approach
of [13, 12], we partition the rules of SV (Q) (the stable version of Q) into three
sets:
chosen rules
diffChoice rules
(i.e., the remaining rules)
Now, the non-deterministic fixpoint procedure which computes the stable models
of a choice program is represented by the following:
Translation Template 2
0: Init
8p defined in SV
1: Saturation
repeat
8p defined in O : last P := P
until 8p defined in O : last
2: Gather choices
8chosen r defined in C : Chosen 0
3: Termination test
if 8chosen r defined in C : Chosen 0
4: Choice
Execute (fairly) the following
a. Choose Chosen 0
b. Choose t 2 Chosen 0
r
5: Inhibit other choices
8diffchoice r defined in D : Diffchoice r
EVAL(diffchoice r
At step 1, the procedure tries to derive all possible atoms from the already
given choices (none at the first iteration), so that at step 2 it can collect all
candidate atoms which can be chosen later. If there is any such atom (i.e., we
have not reached the fixpoint of the evaluation), then we can nondeterministically
choose one of them (step 4) and then propagate the effects of such choice (step
5) in order to force the FD which it implies. We are then ready to repeat the
process.
Example 5. The stable version of the students-advisors example seen in section
2 is the following:
st ad(St; Ad) / major(St; Area); faculty(Ad; Area); chosen(St; Ad):
Following the above translation schema, then, we obtain the following procedure:
0: St ad := ;; Chosen := ;; Diffchoice := ;;
1: St ad := St;Ad (Major(St; Area) ./ F aculty(Ad; Area) ./ Chosen(St;
2: Chosen 0 :=
St;Ad
Major(St; Area) ./ F aculty(Ad; Area) ./ Diffchoice(St; Ad)
3: if Chosen
4c: Chosen := Chosen [ f! st; ad ?g;
5: Diffchoice := Diffchoice [
st ?g \Theta f! ad ?g
Notice that some steps have been slightly modified: (i) step 1 has been sim-
plified, since the only rule in O is not recursive (modulo the chosen predicate);
(ii) here we have only one choice rule, so step 4a becomes useless and then it has
been ignored; (iii) step 5 is rewritten in a brief and more readable form, which
has exactly the same meaning of that shown in the above general schema.
Adding XY-stratification. Analyzing the evaluation procedure of an XY-
cliques Q, it is easy to see that at each step n the only atoms which can be
derived are of the form all with the same stage argument, and
then the syntactic form of the rules ensures that such rules refer only to atoms
Then, the stage arguments in each rule serve only to
distinguish the literals computed in the actual stage I from those computed in
the previous stage I \Gamma 1.
Therefore, we can safely omit the stage argument from each XY-recursive
predicate, renaming the literals referring to a previous stage (i.e., those having
stage I inside a rule with head having stage I + 1) by adding the prefix "old ".
This does not apply to exit-rules, in which the stage argument value is significant
and then must be preserved. We denote by Q 0 the resulting rules, and by p 0 the
predicate obtained from each p.
Example 6. The program Q:
is translated into the new program
it suffices to store in an external register J the value of the stage
under evaluation. We can (i) fire the exit-rules having the same stage argument
as J , and then (ii) to evaluate the new rules in Q 0 (which are now stratified
and possibly with choice) as described in the last two sections. When we have
completely evaluated the actual stage, we need to store the newly derived atoms
p in the corresponding old p, to increment J and then to repeat the process in
order to evaluate the next stage. The resulting procedure is the following.
Translation Template 3
0: Init
defined in Q
1: Fire exit rules
8exit-rule
2: Fire Q'
Translate following the translation templates 1 and 2
3: Update relations
defined in Q
4: J := J
Here we simply reduce the evaluation of the XY-clique to the iterated evaluation
of its stage instances (step 2) in a sequential ascending order (step 4).
Each stage instance is stratified modulo choice and then it can be broken into
subcliques (step 2) which can be translated by template 1 (if choice-free) or
template 2 (if with choice). The resulting relations (step can be easily obtained
by collecting at each stage J the relations P 0 and translating them into
the corresponding P , i.e. adding to them the stage argument J .
Example 7. Let g=2 be an extensional predicate representing the edges of a
graph. Consider the following clique Q:
The corresponding transformed clique Q is:
can be partitioned into: exit-rule r 0 , subclique Q 0
and subclique
g. Applying the translation template 3 we obtain:
0: J := 0; old
old All 0 := ;; All 0 := ;;
1: if
3: old
old All 0 := All
4: J := J
Notice that steps 2a and 2b have been simplified w.r.t. translation template 1,
because Q 0 is not recursive and then the iteration cycle is useless (indeed it would
reach saturation on the first step and then exit on the second one).
5 Optimization of Datalog++ queries
A systematic study of query optimization techniques is realizable on the basis
of the concrete implementation of the iterated stable model procedure discussed
in the previous section. We now sketch a repertoire of ad hoc optimizations for
by exploiting the particular syntactic structure of programs and
queries, and the way they use the temporal arguments.
First of all, we observe that the computations of translation template 3 never
terminate. An obvious termination condition is to check that the relations computed
at two consecutive stages are empty. To this purpose, the translation
template 3 can be modified by inserting the following instruction between step
2 and 3:
if 8p defined in Q
A more general termination condition is applicable to deterministic cliques, under
the assumption that the external calls to the predicates of the clique do not
specify particular stages, i.e., external calls are of the form In this case,
the termination condition above can be simplified as follows:
if 8p defined in Q
Forgetful-fixpoint computations. In many applications (e.g., modeling updates
and active rules [25, 10]) queries are issued with reference to the final
stage only (which represents the commit state of the database). Such queries
often exhibit the form
with the intended meaning "find the value X of p in the final state of p". This
implies that (i) when computing the next stage, we can forget all the preceding
states but the last one (see [26]), and (ii) if a stage I such that p(I; X); :p(s(I); )
is unique, we can quit the computation process once the above query is satisfied.
For instance, the program in Example 7 with the query \Delta(I ; X); :\Delta(s(I); )
computes the leaf nodes at maximal depth in a breadth-first visit of the graph
rooted in a. To the purpose of evaluating this query, it suffices to (i) keep track
of the last computed stage only, (ii) exit when the current \Delta is empty. The code
for the program of Example 7 is then optimized by:
(i) replacing step 3
3: old
old All 0 := All
i.e., dropping the instructions that record previous stages;
(ii) insert between steps 2 and 3 the instruction:
if old
Another interesting case occurs when the answer to the query is distributed
along the stages, e.g., when we are interested in the answer to a query such as
which ignores the stage argument. In this case, we can collect the partial
answers via a gathering predicate defined with a copy-rule. For instance, the
all predicate in Example 7 collects all the nodes reachable from a. Then the
query all(I; X); :all(s(I); ), which is amenable for the described optimization,
is equivalent to the query \Delta( ; X), which on the contrary does not allow it. There-
fore, by (possibly) modifying the program with copy-rules for the all predicate,
we can apply systematically the space optimized forgetful-fixpoint.
Delta-fixpoint computations. We already mentioned the presence of a copy-
rule in Example 7:
Its effect is that of copying all the tuples from the stage I to the next one, if
any. We can avoid such useless space occupation, by maintaining for each stage
only the modifications which are to be applied to the original relation in order to
obtain the actual version. For example, the above rule represents no modification
at all, and hence it should not have any effect; indeed, it suffices to keep track
of the additions to the original database requested by the other rule:
which can be realized by a supplementary relation all + containing, at each
stage, the new tuples produced. In the case that we replace the copy-rule with
a delete-rule of the form:
we need simply to keep track of the negative contribution due to literal :q(X),
which can be stored in a relation all
\Gamma . Each can then be obtained
by integrating with all the all
J  I . This method is particularly effective when is a large relation.
To illustrate this point, let us assume that the program of Example 7 is modified
by adding a new exit rule for relation all:
where r is an extensional predicate. The resulting code is then the following:
0: J := 0; old
old All
1: if
3: old
old All 0 := All
4: J := J
In this way we avoid the construction of relation All, i.e., the replication of
relation r at each stage. In fact, All is reconstructed on the fly when needed
(step 2a).
Side-effect computations. A direct combination of the previous two techniques
gives rise to a form of side-effect computation. Let us consider, as an ex-
ample, the nondeterministic ordering of an array performed by swapping at each
step any two elements which violate ordering. Here, the array a =! a 1
is represented by the relation a with extension a(1; a 1
ar(0;
At each stage i we nondeterministically select an unordered pair x; y of
elements, delete the array atoms ar(i; p1; x) and ar(i; p2; y) where they ap-
pear, and add the new atoms ar(s(i); p1; y) and ar(s(i); p2; x) representing the
swapped pair. The query allows a forgetful-fixpoint computation (in particular,
stage selected by the query is unique), and the definition of predicate ar is composed
by delete-rules and an add-rules. This means that at each step we can
(i) forget the previously computed stages (but the last), and (ii) avoid copying
most of relation ar, keeping track only of the deletions and additions to be per-
formed. If the requested update are immediately performed, the execution of the
proposed program, then, boils down to the efficient iterative computation of the
following (nondeterministic) Pascal-like program:
while 9I a[I
6 Conclusions
The work reported in this paper, concerning fixpoint/operational semantics and
optimization of a logic database language for non deterministic and nonmonotonic
reasoning, constitutes the starting point for an actual implemented sys-
tem. Such project is currently in progress, on the basis of the LDL++ system
developed at UCLA. We plan to incorporate the proposed optimization into the
LDL++ compiler, to the purpose of
evaluating how effective the proposed optimizations are for realistic LDL++
programs, i.e., whether they yield better performance or not,
evaluating how applicable the proposed optimizations are for realistic LDL++
programs, i.e., how often they can be applied,
- experimenting the integration of the proposed optimizations with the classical
optimization techniques, such as magic-sets.



--R

Towards a theory of declarative knowledge.

A Classification-based Methodology for Planning Audit Strategies in Fraud Detection
The Logic of Totally and Partially Ordered Plans: a Deductive Database Approach.
Temporal deductive databases.
The Stable Model Semantics for logic programming.
Programming with non Determinism in Deductive Databases.

Query Answering in Non deterministic Non monotonic logic databases.
A Deductive Data Model for Representing and Querying Semistructured Data.
Experiences with a logic-based knowledge discovery support environment

Semantics and Expressive Power of Non Deterministic Constructs for Deductive Databases.
On the Effective Semantics of Temporal
Integration of deduction and induction for mining supermarket sales data.
ELS programs and the efficient evaluation of non-stratified programs by transformation to ELS

A logical framework for active rules.
Nondeterminism and XY-Stratification in Deductive Databases (in Italian)
A Logic Language for Data and Knowledge Bases.
Every logic program has a natural stratification and an iterated fix point model.
Modular Stratification and Magic Sets for Datalog Program with Negation.
Stable Models and Non-determinism in Logic Programs with Negation
Principles of Database and Knowledge-base Systems
Active Database Rules with Transaction Conscious Stable Model Se- mantics
Negation and Aggregates in Recursive Rules: The LDL

--TR

--CTR
Christos Nomikos , Panos Rondogiannis , Manolis Gergatsoulis, Temporal stratification tests for linear and branching-time deductive databases, Theoretical Computer Science, v.342 n.2-3, p.382-415, 7 September 2005
Fosca Giannotti , Giuseppe Manco , Franco Turini, Specifying Mining Algorithms with Iterative User-Defined Aggregates, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1232-1246, October 2004
stable models;negation;nondeterminism;logic programming;databases