Enhancing Disjunctive Datalog by Constraints.
AbstractThis paper presents an extension of Disjunctive Datalog (${\rm{DATALOG}}^{\vee,}{^\neg}$) by integrity constraints. These are of two types: strong, that is, classical integrity constraints and weak, that is, constraints that are satisfied if possible. While strong constraints must be satisfied, weak constraints express desiderata, that is, they may be violatedactually, their semantics tends to minimize the number of violated instances of weak constraints. Weak constraints may be ordered according to their importance to express different priority levels. As a result, the proposed language (call it, ${\rm{DATALOG}}^{\vee,}{^{\neg,}}{^c}$) is well-suited to represent common sense reasoning and knowledge-based problems arising in different areas of computer science such as planning, graph theory optimizations, and abductive reasoning. The formal definition of the language is first given. The declarative semantics of ${\rm{DATALOG}}^{\vee,}{^{\neg,}}{^c}$ is defined in a general way that allows us to put constraints on top of any existing (model-theoretic) semantics for ${\rm{DATALOG}}^{\vee,}{^\neg}$ programs. Knowledge representation issues are then addressed and the complexity of reasoning on ${\rm{DATALOG}}^{\vee,}{^{\neg,}}{^c}$ programs is carefully determined. An in-depth discussion on complexity and expressiveness of ${\rm{DATALOG}}^{\vee,}{^{\neg,}}{^c}$ is finally reported. The discussion contrasts ${\rm{DATALOG}}^{\vee,}{^{\neg,}}{^c}$ to ${\rm{DATALOG}}^{\vee,}{^\neg}$ and highlights the significant increase in knowledge modeling ability carried out by constraints.
Introduction
Disjunctive Datalog (or DATALOG ;: ) programs [18, 15] are nowadays widely recognized as
a valuable tool for knowledge representation and commonsense reasoning [2, 34, 25, 20]. An
important merit of DATALOG ;: programs over normal (that is, disjunction-free) Datalog
programs is their capability to model incomplete knowledge [2, 34]. Much research work has
been done so far on the semantics of disjunctive programs and several alternative proposals
have been formulated [5, 20, 40, 46, 47, 48, 51, 59]. One which is widely accepted is the
extension to the disjunctive case of the stable model semantics of Gelfond and Lifschitz.
According to this semantics [20, 46], a disjunctive program may have several alternative
models (possibly none), each corresponding to a possible view of the reality. In [11, 15],
Eiter, Gottlob and Mannila show that DATALOG ;: has a very high expressive power, as
(under stable model semantics) the language captures the complexity class \Sigma P(i.e., it allows
us to express every property which is decidable in non-deterministic polynomial time with
an oracle in NP).
In this paper, we propose an extension of DATALOG ;: by constraints. In particular, besides
classical integrity constraints (that we call trongconstraints), we introduce the notion
of weak constraints, that is, constraints that should possibly be satisfied. Contrary to strong
constraints, that express conditions that must be satisfied, weak constraints allow us to express
desiderata. The addition of (both weak and strong) constraints to DATALOG ;: makes
the language (call it DATALOG ;:;c ) well-suited to represent a wide class of knowledge-based
problems (including, e.g., planning problems, NP optimization problems, and abductive rea-
soning) in a very natural and compact way.
As an example, consider the problem SCHEDULING which consists in the scheduling of
examinations for courses. That is, we want to assign course exams to time slots in such a
way that no two exams are assigned with the same time slot if the respective courses have
a student in common (we call such courses  ncompatible"). Supposing that there are
three time slots available, namely, ts 1 , ts 2 and ts 3 , we express the problem in DATALOG ;:;c
by the following program
ts 1 )  assign(X; ts 2 )  assign(X; ts 3 ) / course(X)
Here we assumed that the courses and the pair of incompatible courses are specified by a
number of input facts with predicate course and incompatible, respectively. Rule r 1 says
that every course is assigned to either one of the three time slots ts 1 , ts 2 or ts 3 ; the strong
constraint s 1 (a rule with empty head) expresses that no two incompatible courses can be
overlapped, that is, they cannot be assigned to the same time slot. In general, the presence
of strong constraints modifies the semantics of a program by discarding all models which do
not satisfy some of them. Clearly, it may happen that no model satisfies all constraints. For
instance, in a specific instance of problem above, there could be no way to assign courses to
time slots without having some overlapping between incompatible courses. In this case, the
problem does not admit any solution. However, in real life, one is often satisfied with an
approximate solution, that is, one in which constraints are satisfied as much as possible. In
this light, the problem at hand can be restated as follows (APPROX SCHEDULING): assign
courses to time slots trying to not overlap incompatible courses". To express this problem
we resort to the notion of weak constraint, as shown by the following program P a sch :
ts 1 )  assign(X; ts 2 )  assign(X; ts 3 ) / course(X)
From a syntactical point of view, a weak constraint is like a strong one where the implication
symbol / is replaced by (. The semantics of weak constraints minimizes the number of
violated instances of constraints. An informal reading of the above weak constraint w 1 is:
"preferably, do not assign the courses X and Y to the same time slot if they are incompati-
ble". Note that the above two programs P sch and P a sch have exactly the same models if all
incompatible courses can be assigned to different time slots (i.e., if the problem admits an
"exact" solution).
In general, the informal meaning of a weak constraint, say, ( B, is try to falsify Bor "B
is preferably false", etc. (thus, weak constraints reveal to be very powerful for capturing the
concept of preference n commonsense reasoning).
Since preferences may have, in real life, different priorities, weak constraints in DATALOG ;:;c
can be assigned with different priorities too, according to their  mportance". 1 For ex-
ample, assume that incompatibilities among courses may be either strong or weak (e.g., basic
courses with common students can be considered strongly incompatible, while complementary
courses give weak incompatibilities). Consider the following problem (SCHEDULING
WITH PRIORITIES): chedule courses by trying to avoid overlapping between strongly
incompatible courses first, and by trying to avoid overlapping between weakly incompatible
courses then"(i.e., privilege the elimination of overlapping between strongly incompatible
courses). If strong and weak incompatibilities are specified through input facts with
predicates strongly incompatible and weakly incompatible, respectively, we can represent
SCHEDULING WITH PRIORITIES by the following program P
ts 1 )  assign(X; ts 2 )  assign(X; ts 3 ) / course(X)
strongly incompatible(X; Y )
where the weak constraint w 2 is defined tronger than"w 3 . The models of the above program
are the assignments of courses to time slots that minimize the number of overlappings
between strongly incompatible courses and, among these, those which minimize the number
of overlappings between weakly incompatible courses.
The main contributions of the paper are the following:
ffl We add weak constraints to DATALOG ;: and provide a formal definition of the language
DATALOG ;:;c . The semantics of constraints is given in a general way that
1 Note that priorities are meaningless among strong constraints, as all of them must be satisfied.
allows us to define them on top of any existing model-theoretic semantics for Disjunctive
Datalog.
ffl We show how constraints can be profitably used for knowledge representation and
reasoning, presenting several examples of DATALOG ;:;c encoding. DATALOG ;:;c
turns out to be both general and powerful, as it is able to represent in a simple and
coincise way hard problems arising in different domains ranging from planning, graph
theory, and abduction.
ffl We analyze the computational complexity of reasoning with DATALOG ;:;c (propo-
sitional case under stable model semantics). The analysis pays particular attention
to the impact of syntactical restrictions on DATALOG ;:;c programs in the form of
limited use of weak constraints, strong constraints, disjunction, and negation. It appears
that, while strong constraints do not affect the complexity of the language,
constraints "mildly" increase the computational complexity. Indeed, we show
that brave reasoning is \Delta P
programs. Interestingly, priorities among constraints affect the com-
plexity, which decreases to \Delta P[O(log n)] (\Delta P[O(log n)] for DATALOG :;c ) if priorities
are disallowed. The complexity results may support in choosing an appropriate fragment
of the language, which fits the needs in practice (see Section 5).
ffl We carry out an in-depth discussion on expressiveness and complexity of DATALOG ;:;c ,
contrasting the language to DATALOG ;: . Besides adding expressive power from the
theoretical view point (as DATALOG ;:;c can encode problems which cannot be represented
at all in DATALOG ;: ), it turns out that constraints improve also usability
and knowledge modeling features of the language. Indeed, well-known problems can
be encoded in a simple and easy-to-understand way in DATALOG ;:;c ; while their
DATALOG ;: encoding is unusable (long and difficult to understand).
Even if strong constraints (traditionally called integrity constraints) are well-known in the
logic programming community (see, e.g., [15, 10, 17, 33, 12]), to our knowledge this is the
first paper which formally studies weak constraints and proposes their use for knowledge representation
and reasoning. Related works can be considered the interesting papers of Greco
and Sacc'a [24, 23] which analyze other extensions of Datalog to express NP optimizations
problems. Related studies on complexity of knowledge representation languages have been
carried out in [15, 50, 8, 14, 21, 39, 52, 9, 12]. Priority levels have been used also in the
context of theory update and revision [16] and [22], in prioritized circumscription [31], in
the preferred subtheories approach for default reasoning [6], and in the preferred answer set
semantics for extended logic programs [7].
The paper is organized as follows. In Section 2 we provide both the syntax and the semantics
of the language. Then, in Section 3 we describe the knowledge representation capabilities
of DATALOG ;:;c by a number of examples. In particular, we show how the language can
be used to easily formulate complex knowledge-based problems arising in various areas of
computer science, including planning, graph theory and abduction. In Section 4 we analyze
the complexity of the language under the possibility version of the stable model semantics.
Finally, Section 5 reports an in-depth discussion on the language and draws our conclusions


Appendix

A shows the encoding of a number of classical optimization problems in
reports the proofs of the complexity results for the fragments
of DATALOG ;:;c where disjunction is either disallowed or constrained to the head
2 The DATALOG ;:;c Language
We assume that the reader is familiar with the basic concepts of deductive databases [55, 34]
and logic programming [32]. We describe next the extension of Disjunctive Datalog by
constraints.
2.1 Syntax
A term is either a constant or a variable 2 . An atom is a is a predicate of
are terms. A literal is either a positive literal p or a negative literal
:p, where p is an atom.
A (disjunctive) rule r is a clause of the form
a
where a are atoms. The disjunction a 1  \Delta \Delta \Delta  a n is the head of r, while
the conjunction is the body of r. If (i.e., the head is -free),
then r is normal; if (the body is :-free), then r is positive. A DATALOG ;: program
LP is a finite set of rules; LP is normal (resp., positive) if all rules in LP are normal (resp.
positive).
A strong constraint is a syntactic of the form /
literal (i.e., it is a rule with empty head).
A weak constraint is a syntactic of the form (
literal.
simply program") is a triple
where LP is a DATALOG ;: program, S a (possibly empty) finite set of strong constraints
and is a (possibly empty) finite list of components, each consisting of a
finite set of weak constraints. If w then we say that w 0 is tronger
thanor more important than"w (hence, the last component W n is the strongest).
2 Note that function symbols are not considered in this paper.
Example 2 Consider the program P p sch of Section 1. Here, LP p sch
and W p sch (that is, w 2 is stronger than w 3 ).2.2 General Semantics
program. The Herbrand universe U P of P is the set of all
constants appearing in P. The Herbrand base B P of P is the set of all possible ground
atoms constructible from the predicates appearing in P and the constants occurring in
U P (clearly, both U P and B P are finite). The instantiation of rules, strong and weak
constraints is defined in the obvious way over the constants in U P , and are denoted by
ground(LP ), ground(S) and ground(W ), respectively; we denote the instantiation of P by
A (total) interpretation for P is a subset I of B P . A ground positive literal a is true (resp.,
w.r.t. I if a 2 I (resp., a =
I). A ground negative literal :a is true (resp., false) w.r.t.
I if a =
I (resp., a 2 I).
Let r be a ground rule in ground(LP ). Rule r is satisfied (or true) w.r.t. I if its head is
true w.r.t. I (i.e., some head atom is true) or its body is false (i.e., some body literal is false)
w.r.t. I. A ground (strong or weak) constraint c in (ground(S) [ ground(W )) is satisfied
w.r.t. I if (at least) one literal appearing in c is false w.r.t. I; otherwise, c is violated.
We next define the semantics of DATALOG ;:;c in a general way which does not rely on a
specific semantical proposal for DATALOG ;: ; but, rather, it can be applied to any semantics
of Disjunctive Datalog. 3 To this end, we define a candidate model for as an
interpretation M for P which satisfies every rule r 2 ground(LP ). A ground semantics for P
is a finite set of candidate models for P. Clearly, every classical semantics for LP provides a
ground semantics for P. For example the semantics presented in [20, 40, 46, 47, 48, 51, 59]
can be taken as ground semantics.
Now, to define the meaning of a program in the context of a given ground
semantics, we need to take into account the presence of constraints. To this end, since
constraints may have different priorities, we associate with each component W i 2 W ,
inductively defined as follows:
where jground(W )j denotes the total number of ground instances of the weak constraints
appearing in W . Further, given an interpretation M for a program P, we denote by H P;M
the following sum of products:
3 Note that, although we consider only total model semantics in this paper, the semantics of weak constraints
simply extends to the case of partial model semantics.
n) is the number of ground instances of weak constraints in the
component W i which are violated in M .
Now, we are ready to define the notion of model for w.r.t. a given ground
semantics.
Definition 3 Given a ground semantics \Gamma for of P is a candidate
model every strong constraint s 2 ground(S) is satisfied w.r.t. M ,
and (2) H P;M is minimum, that is, there is no candidate model verifying Point (1)
such that H P;N ! H P;M
Thus, a \Gamma-model M of P, by minimizing H P;M selects those candidate models that, besides
satisfying strong constraints, minimize the number of unsatisfied (instances of) weak constraints
according to their importance - that is, those with the minimal number of violated
constraints in W n are chosen, and, among these, those with the minimal number of violated
constraints in W n\Gamma1 , and so on and so forth.
2.3 Stable Model Semantics
Using the notion of candidate model we have parametrized the semantics of DATALOG ;:;c
programs, that is, the actual semantics of a program P relies on the semantics we choose
for LP . Several proposals can be found in the literature for disjunctive logic programs
[5, 20, 40, 46, 47, 48, 51]. One which is generally acknowledged is the extension of the stable
model semantics to take into account disjunction [20, 46]. We next report a brief discussion
on this semantics.
In [40], Minker proposed a model-theoretic semantics for positive (disjunctive) programs,
whereby a positive program LP is assigned with a set MM(LP ) of minimal models, each
representing a possible meaning of LP (recall that a model M for LP is minimal if no proper
subset of M is a model for LP ).
Example 4 For the positive program /g the (total) interpretations fag and
fbg are its minimal models (i.e., MM(LP
The stable model semantics generalises the above approach to programs with negation.
Given a program LP and a total interpretation I, the Gelfond-Lifschitz transformation of
LP with respect to I, denoted by LP I , is the positive program defined as follows:
a
let I be an interpretation for a program LP . I is a stable model for LP if I 2
I ) (i.e., I is a minimal model of the positive program LP I ). We denote the set of
all stable models for LP by SM(LP ).
Example 5 Let fbg.
It is easy to verify that I is a minimal model for LP I ; thus, I is a stable model for LP . 4
Clearly, if LP is positive then LP I coincides with ground(LP ). It turns out that, for a
positive program, minimal and stable models coincide. A normal positive programs LP has
exactly one stable model which coincides with the least model of LP (i.e., it is the unique
minimal model of LP ). When negation is allowed, however, even a normal program can
admit several stable models.
We conclude this section observing that Definition 3 provides the stable model semantics
of a DATALOG ;:;c program the choosen ground semantics is SM(LP ),
the set of the stable models of LP .
Definition 6 A \Gamma-model for a program stable model for
Example 7 Consider the program P sch sch ) of Section
According to the stable model semantics, LP sch has as many
stable models as the possibilities of assigning all courses, say n, to 3 time slots (namely, 3 n ).
The stable models of P sch are the stable models of LP sch satisfying the strong constraint s 1 ,
that is, those (if any) for which no two incompatible courses are assigned with the same time
slot.
The program P a sch = (LP a sch ; S a sch ; W a sch ) of Section 1, where LP a sch
; and W a sch = hfw 1 gi, is obtained from LP sch by replacing s 1 by w 1 (note that LP a sch =
LP sch ). The stable models of P a sch are the stable models of LP a sch which minimize the
number of violated instances of w 1 , that is, the number of incompatible courses assigned to
the same time slots. Thus, P a sch provides a different solution from P a sch only if the latter
does not admit any stable model, i.e., the problem has no "exact" solution - there is no way
to assign different time slots to all incompatible courses. Otherwise, the two programs have
exactly the same stable models.
Finally, consider the program P sch ) of Section 1, where LP
"). Each stable model
of LP p sch is a possible assignment of courses to time slots. The stable models of P p sch are
the stable models of LP p sch that, first of all, minimize the number of violated instance of w 2
and, in second order, minimize the number of violated instances of w 3 . 4
It is worth noting that a DATALOG ;:;c program P may have several stable models (there
can also be no one). The modalities of brave and cautious reasoning are used to handle this.
Brave reasoning (or credulous reasoning) infers that a ground literal Q is true in P (denoted
brave Q) iff Q is true w.r.t. M for some stable model M of P.
Cautious reasoning (or skeptical reasoning) infers that a ground literal Q is true in P
(denoted P cautious Q) iff Q is true w.r.t. M for every stable model M of P.
The inferences brave and cautious extend to sets of literals as usual.
Knowledge Representation in DATALOG ;:;c
In this section we provide a number of examples that show how DATALOG ;:;c can be used
to easily formulate many interesting and difficult knowledge-based problems. Among those,
we consider planning problems, classical optimization problems from Graph Theory and
various forms of abductive reasoning. We show how the language provides natural support
for their representation. A number of further examples are reported in AppendixA.
As we shall see, most programs have a common structure of the form guess, check, choose-
best. Candidate solutions are first nondeterministically generated (through disjunctive
mandatory properties are checked (through strong constraints), finally, solutions
that best satisfy desiderata are selected (through weak constraints). Such a modular
structure shows quite natural for expressing complex problems and, further, makes programs
easy to understand.
3.1 Planning
A first example of planning, namely the APPROX SCHEDULING problem, has been presented
in the introduction. A further example is next reported.
Example 8 PROJECT GROUPS. Consider the problem of organizing a given set of employees
into two (disjoint) project groups p1 and p2. We wish each group to be possibly
heterogeneous as far as skills are concerned. Further, it is preferable that couple of persons
married to each other do not work in the same group. And, finally, we would like that the
members of the same group already know each other. We consider the former two requirements
more important than the latter one. Supposing that the information about employees,
skills, known and married persons, are specified through a number of input facts a simple
way of solving this problem is given by the following program
are stronger than w 1 (i.e., gi. The first rule r 1 above
assigns each employee to either one of the two projects p1 and p2 (recall that, by minimality
of a stable model, exactly one of member(X; p1) and member(X; p2) is true in it, for each
employee X). The weak constraint w 1 expresses the aim of forming groups with persons that
possibly already know each other; w 2 , in turn, expresses the preference of having groups with
no persons married each other; and, finally, the weak constraint w 3 tries avoid that persons
4 For notational simplicity, in the examples we represent programs just as sets of rules and constraints.
Observe also that we use the inequality predicate 6= as a built-in, this is legal as inequality can be easily
simulated in DATALOG ;:;c .
with the same skill work in same project. It is easy to recognize that each stable model of the
is a possible assignment of employees to projects. Due
to the priority of weak constraints (recall that w 2 and w 3 are both tronger than"w 1 ) the
stable models of P proj are those of LP that minimize the overall number of violated instances
of both w 2 and w 3 and, among these, those minimizing the number of violated instances of
. For an instance, suppose that the employees are a; b; c; d; e, of which a and b have
the same skill, c and d are married to each other and, finally, the following pairs know
reciprocally: (b; c), (c; d), (a; e), (d; e). In this case, P proj has two stable models M 1 and
which correspond to the following division in project teams (we list only the atoms with
predicate member of the two models).
Observe that both M 1 and M 2 violate only two instances of w 1 (as a and b do not know
each other), and they satisfy all instances of w 2 and w 3 . 4
3.2 Optimization from Graph Theory
In the above example we have regarded weak constraints essentially as desiderata - that is,
conditions to be possibly satisfied. However, a useful way of regarding weak constraints is as
objective functionsof optimization problems. That is, a program with a weak constraint of
the form ( B can be regarded as modeling a minimization problem whose objective function
is the cardinality of the relation B (from this perspective, a strong constraint / B can then
be seen as a particular case in which the cardinality of the relation B is required to be zero).
This suggests us to use DATALOG ;:;c to model optimization problems. Next we show
some classical NP optimization problems from graph theory formulated in our language. A
number of further examples can be found in AppendixA.
Example 9 MAX CLIQUE : Given a graph find a maximum clique, that is,
a subset of maximum cardinality C of V such that every two vertices in C are joined by an
edge in E. To this end, we define the following program
Here, r 1 partitions the set of vertices into two subsets, namely, c and not c - i.e., it guesses
a clique c. The strong constraint s 1 checks the guess, that is, every pair of vertices in c (the
clique) must be joined by an edge. Finally, the weak constraint w 1 minimizes the number of
vertices that are not in the clique c (thus, maximizing the size of c, by discarding all cliques
whose size is not maximum). It holds that each stable model of P cliq is a maximum clique of
G. 4
COLORING. Given a graph coloring of G is an assignment
of colors to vertices, in such a way that every pair of vertices joined by an edge have
different colors. A coloring is minimum if it uses a minimum number of colors. We determine
a minimum coloring by the following program
used col(I) / col(X; I)
used col(I)
The first rule r 1 guesses a graph coloring; col(X; I) says that vertex X is assigned to color I
and not col(X; I) that it is not. Strong constraints s 1 -s 3 check the guess: two joined vertices
cannot have the same color (s 1 ), and each vertex is assigned to exactly one color (s 2 and
Finally, the weak constraint w 1 requires the cardinality of the relation used col to be
minimum (i.e., the number of used colors is minimum). It holds that there is a one-to-one
correspondence between the stable models of P col and the minimum colorings of the graph G.3.3 Abduction
We next show that some important forms of abduction over (disjunctive) logic programs,
namely abduction with prioritization and abduction under minimum-cardinality solution
preference [14], can be represented in a very easy and natural way in DATALOG ;:;c (while,
in general, they cannot be encoded in DATALOG ;: ).
Abduction, first studied by Peirce [43], is an important kind of reasoning, having wide
applicability in different areas of computer science; in particular, it has been recognized as
an important principle of common-sense reasoning. For these reasons, abduction plays a
central role in Artificial Intelligence, and has recently received growing attention also in the
field of Logic Programming.
Abductive logic programming deals with the problem of finding an explanation for ob-
servations, based on a theory represented by a logic program [35, 36]. Roughly speaking,
abduction is an inverse of modus ponens: Given the clause a / b and the observation a,
abduction concludes b as a possible explanation. Following [13, 35, 36], an abductive logic
programming problem (LPAP) can be formally described as a tuple
where Hyp is a set of ground atoms (called hypotheses), Obs is a set of ground literals
(called manifestations or observations), and LP is a logic program (with disjunction and
negation allowed). An explanation for P is a subset E ' Hyp which satisfies the following
property:
c
d
e
a

Figure

1: A computer network
brave Obs, i.e., there exists a stable model M of LP [E, where all literals in Obs
are true.
In general, an LPAP may have no, a single, or several explanations. In accordance with
Occam's principle of parsimony [42], which states that from two explanations the simpler
explanation is preferable, some minimality criterion is usually imposed on abductive expla-
nations. Two important minimality criterions are Minimum Cardinality and Prioritization
[14]. The minimum cardinality criterion states that a solution A ' Hyp is preferable to a
solution denotes the cardinality of set X). According to
this criterion, the acceptable solutions of P are restricted to the explanations of minimum
cardinality (that are considered the most likely).
Example 11 ABDUCTION Consider the computer network depicted in Figure 1. We make
the observation that, sitting at machine a, which is online, we cannot reach machine e. Which
machines are offline?
This can be easily modeled as the LPAP P net = hHyp net ; Obs net ; LP net i, where the theory
LP net is
and the hypotheses and observations are
and
respectively.
For example, according with the intuition, line(b)g is an explanation for P net ;
but also line(c)g is an explanation and even
off line(c); off line(d); off line(e) g is an explanation. However, under the minimum cardinality
criterion, only line(e)g are the solutions of P net
(we can see them as the most probable ones).Abduction with minimum cardinality can be represented very simply in DATALOG ;:;c .
Given a LPAP pr(P) be the DATALOG ;:;c program (LP [
G;
positive literal, and (for each h 2 Hyp, not h
denotes a new symbol). It is easy to see that the stable models of pr(P) correspond exactly
to the minimum cardinality solutions of P 5 . Intuitively, the clauses in G "guess" a solution
(i.e., a set of hypoteses), the strong constraints in S check that the observations are entailed,
and the weak constraints in W 0 enforce the solution to have minimum cardinality.
Example 12 (cont'd) The DATALOG ;:;c program for our network problem is pr(P net
net [ G; net is the theory of P net and
The stable models of LP net [ G that satisfy both strong constraints / off line(a) and /
reaches(a; e) encode one-to-one the abductive explanations of P net ; among them, the weak
constraints in W 0 select the explanations with minimum cardinality. Indeed, pr(P net ) has
only two stable models: one contains off line(b) and the other contains off line(e).The method of abduction with priorities [14] is a refinement of the above minimality cri-
terion. Roughly speaking, it operates as follows. The set of hypotheses Hyp is partitioned
into groups with different priorities, and explanations which are (cardinality) minimal on the
lowest priority hypotheses are selected from the solutions. The quality of the selected solutions
on the hypotheses of the next priority level is taken into account for further screening;
5 Without loss of generality, we assume that no hypothesis in Hyp appears in the head of a rule in LP .
this process is continued over all priority levels. As pointed out in [14], prioritization is also
a qualitative version of probability, where the different priorities levels represent different
magnitude of probabilities. It is well suited in case no precise numerical values are known,
but the hypotheses can be grouped in clusters such that the probabilities of hypotheses
belonging to the same cluster do not (basically) differ compared to the difference between
hypotheses from different clusters [14].
Example 13 (cont'd) Suppose that statistical data about the computers in the network of

Figure

1 tell us that b falls down very often, e is always online, while c and d sometimes
are offline. Then, we restate the LPAP P net as an abductive problem with prioritization
net ; Obs net ; LP net i, where
According with the prioritization, the abductive explainations are ordered as follows:
Therefore, foff line(b)g becomes the preferred (i.e., most likely) solution. (Note that, differently
from the convention we adopted for weak constraints, the hypotheses of the smallest
priority level are the most important here).By using priorities among weak constraints, we obtain a very natural encoding of abduction
with prioritization. Given pr(P) be the DATALOG ;:;c
G;
and S and G are defined as above. Then, the stable models of pr(P) correspond exactly to
the preferred solutions of P according with the prioritization.
Example 14 (cont'd)
The DATALOG ;:;c program simulating abduction with priorities for the network of Example
11 is pr(P 0
net G; are as above, and
(recall that W 3 is the strongest component). It is easy to see that pr(P 0
net ) has only one stable
model M which contains (only) the hypothesys off line(b).
4 The Complexity of Constraints: Propositional Case
In this section we analyze the complexity of brave reasoning over disjunctive Datalog programs
with constraints. Since the complexity is not independent from the underlying ground
semantics, we consider in this section the stable model semantics [20, 46], which is a widely
acknowledged semantics for normal and disjunctive Datalog programs.
4.1 Preliminaries on Complexity Theory
For NP-completeness and complexity theory, cf. [41]. The classes \Sigma P
k of the
Polynomial Hierarchy (PH) (cf. [53]) are defined as follows:
In particular,
denotes the class
of problems that are solvable in polynomial time on a deterministic (resp. nondeterministic)
Turing machine with an oracle for any problem  in the class C.
The oracle replies to a query in unit time, and thus, roughly speaking, models a call to a
subroutine for  that is evaluated in unit time. If C has complete problems, then instances
of any problem  0 in C can be solved in polynomial time using an oracle for any C-complete
problem , by transforming them into instances of ; we refer to this by stating that an
oracle for C is used. Notice that all classes C considered here have complete problems.
The classes \Delta P
refined by the class \Delta P
k [O(log n)], in which the number
of calls to the oracle is in each computation bounded by O(log n), where n is the size of the
input.
Observe that for all k  1,
each inclusion is widely conjectured to be strict. Note that, by the rightmost inclusion,
all these classes contain only problems that are solvable in polynomial space. They allow,
however, a finer grained distinction between NP-hard problems that are in PSPACE.
The above complexity classes have complete problems under polynomial-time transformations
involving Quantified Boolean Formulas (QBFs). A QBF is an expression of the
where E is a Boolean expression whose atoms are from pairwise disjoint nonempty sets of
variables and the Q i 's are alternating quantifiers from f9; 8g, for all
If then we say the QBF is k-existential, otherwise it is k-universal. Validity of QBFs
is defined in the obvious way by recursion to variable-free Boolean expressions. We denote
by QBF k;9 (resp., QBF k;8 ) the set of all valid k-existential (resp., k-universal) QBFs (1).
Given a k-existential QBF \Phi (resp. a k-universal QBF \Psi), deciding whether \Phi 2 QBF k;9
classical \Sigma P
k has also complete problems for all k  2; for example, given a formula E on variables
deciding whether the with
respect to hX 1 lexicographically minimum truth assignment 6 OE to X
that (where such a OE is known to exist) fulfills OE(X n
(cf. [37, 58]). 7 Also \Delta P
[O(log n)] has complete problems for all k  1; for example, given
, such that \Phi
is odd ([58, 14]).
The problems remain as hard under the following restrictions: (a) E in (1) is in conjunctive
normal form and each clause contains three literals (3CNF) if Q
disjunctive normal form and each monom contains three literals (3DNF) if Q
4.2 Complexity Results
We analyze the complexity of the propositional case; therefore, throughout this section we
assume that the programs and query literals are ground (i.e., variable-free). The complexity
results, however, can be easily extended to data complexity [57].
Given a program we denote by maxH(P) the value that H P;M
assumes when the interpretation M violates all the ground instances of weak constraints
(in each component). More precisely,
is the cardinality of the set of the ground instances of the constraints in W i .
Observe that maxH(P) is exponential in the number of components of P; indeed, from the
(inductive) definition of f(W i ) (see Section 2.2), it can be easily seen that
It turns out that (the value of) maxH(P) can be exponential in the size
of the input; however, it is computable in polynomial time (its binary representation has
polynomial size).
We next report detailed proofs of all complexity results of DATALOG ;:;c programs where
full disjunction is allowed (these proofs are the most involved and technically interesting).
The demonstrations of the results on disjunction-free programs and on head-cycle free disjunctive
programs are reported in AppendixB. All complexity results are sumarized in Table
1, and discussed in-depth in Section 5.
First of all, we look for an upper bound to the complexity of brave reasoning on DATALOG ;:;c .
To this end, we provide two preliminary lemmata.
Lemma 15 Given a DATALOG ;:;c program positive integer n as
input, it is in \Sigma Pdeciding whether there exists a stable model M of LP satisfying S such
that H P;M  n.
6 OE is lexicographically greater than / w.r.t. hX false for the least j
such that OE(X j )
is the set of all variable-free true formulas.
Proof. We can decide the problem as follows. Guess check that: (1) M is
a stable model of LP , (2) all constraints in S are satisfied, and (3) H P;M  n. Clearly,
property (2) and (3) can be checked in polynomial time; while (1) can be decided by a single
call to an NP oracle [39, 15]. The problem is therefore in \Sigma P. 2
Lemma Given a DATALOG ;:;c program positive integer n, and a
literal q as input, it is in \Sigma Pdeciding whether there exists a stable model M of LP satisfying
S such that H and q is true w.r.t. M .
Proof. We can decide the problem as follows. Guess check that: (1) M is
a stable model of LP , (2) all constraints in ground(S) are satisfied, (3) H
q is true w.r.t. M . Clearly, property (2), (3), and (4) can be checked in polynomial time;
while (1) can be decided by a single call to an NP oracle [39, 15]. The problem is therefore
in \Sigma P
Now, we are in the position to determine the upper bound to brave reasoning on full
DATALOG ;:;c programs.
Theorem 17 Given a DATALOG ;:;c program literal q as input,
deciding whether q is true in some stable model of P is in \Delta P
3 .
Proof. We first call a \Sigma Poracle to verify that P admits some stable model satisfying S
(otherwise, q cannot be a brave consequence). We compute then (in polynomial time)
maxH(P). After that, by binary search on [0::k], we determine the cost \Sigma of the stable
models of P, by a polynomial number of calls to an oracle deciding whether there exists a
stable model M of LP satisfying S such that H P;M  n (n = k=2 on the first call; then if
the oracle answers "yes", otherwise, n is set to k=2 + k=4, and so on, according
to standard binary search) - the oracle is in \Sigma P
2 by virtue of Lemma 15. (Observe that the
number of calls to the oracle is logarithmic in k, and, as a consequence, is polynomial in the
size of the input, as the value k is O(2 jP j ).) Finally, a further call to a \Sigma P
oracle verifies
that q is true in some stable model of P, that is a stable model M of LP satisfying S with
(this is doable in \Sigma P
2 from Lemma 16). 2
We will next strenghten the above result on \Delta P-membership, to a completeness result
in this class. Hardness will be proven by reductions from QBFs into problems related to
stable models of DATALOG ;:;c programs; the utilized disjunctive Datalog programs will
be suitable adaptations and extensions of the disjunctive program reported next (which has
been first described in [12]).
Let \Phi be a formula of form 8Y E, where E is a Boolean expression over propositional
variables from X [ Y , where g. We assume that E is
in 3DNF, i.e., and each D is a conjunction of literals
L i;j . Define the following (positive) Disjunctive Datalog program LP (\Phi):
for each
where oe maps literals to atoms as follows:
Intuitively, x 0
i corresponds to :x i and y 0
j corresponds to :y j .
Given a truth assignment OE(X) to g, we denote by M OE ' B LP (\Phi) the
following interpretation
fy 0
Moreover, given an interpretation M of LP (\Phi), we denote by OE M the truth assignment to
Lemma (\Phi) be the formula and the disjunctive Datalog program
defined above, respectively. Then, there is a one-to-one correspondence between the truth
assignments OE(X) to such that \Phi valid and the stable
models of LP (\Phi) which contain the atom v. In particular:
1. if \Phi
2. if M 2 SM(LP (\Phi)) contains v, then \Phi OE M
Proof. It follows from Theorems 3.1 of [12]. 2
Note that LP (\Phi) is constructible from \Phi in polynomial time.
We are now ready to determine exactly the complexity of reasoning over programs with
Theorem 19 Given a DATALOG ;:;c program literal q as input,
deciding whether q is true in some stable model of P is \Delta P-complete.
Proof. From Theorem 17 it remains to prove only hardness. \Delta P-hardness is shown by
exhibiting a DATALOG ;:;c program that, under brave reasoning, solves the following
complete problem \Pi: let OE(X), g, be the lexicographically minimum truth
assignment with respect to hx 1 ; :::; x n i such that \Phi assume such a
OE exists); now, is it true that OE(x n W.l.o.g. we assume that E is in 3DNF of the
form defined above. Let P be a DATALOG ;:;c program where LP (\Phi) is
the positive disjunctive Datalog program defined above, and W
:vgi. We next show that the answer to \Pi is true iff x n is true in some stable model of P 0 .
Let SM v (LP (\Phi)) denote the set of the stable models of LP (\Phi) which contain v. From
Lemma we know that there is a one-to-one correspondence between SM v (LP (\Phi)) and
the set of truth assignments OE which make \Phi OE valid. Since \Phi OE is valid by hypothesis, this
implies that SM v (LP (\Phi)) 6= ;. Consequently, P 0 has some stable models (as there is no
strong constraint in P 0 ), and each stable model of P 0 contains v as ( :v is the strongest
constraint in W 0 . The priorities among constraints ff( x n impose a total
order on SM v (LP (\Phi)). In particular, given two stable models M and M 0 in SM v (LP (\Phi)),
the truth assignment OE M 0 is greater than OE M in the lexicographically order.
Therefore, P 0 has a unique stable model M (which is in SM v (LP (\Phi))), corresponding to the
lexicographically minimum truth assignment OE such that \Phi Hence, the
lexicographically minimum truth assignment OE(X) making \Phi OE valid fulfills OE(x n
and only if x n is true in some stable model of P 0 . Therefore, brave reasoning is \Delta P
3 -hard for
DATALOG ;:;c . 2
Next we show that neither strong constraints nor negation affect the complexity of DATALOG ;:;c
that remains unchanged even if we disallow both of them.
Corollary 20 Given a DATALOG ;:;c program literal q as input,
deciding whether q is true in some stable model of P is \Delta P-complete even if strong constraints
are disallowed and LP is stratified or even positive.
Proof. Membership in \Delta P
3 trivially holds from Theorem 17. As far as hardness is concerned,
observe that in the reduction of Theorem 19 the DATALOG ;:;c program P 0 has no strong
constraints (i.e., its logic program LP (\Phi) is positive (and therefore stratified).Thus, the syntactic restrictions imposed in Corollary 20 do not decrease the complexity
of DATALOG ;:;c . Interestingly, the complexity of the language decreases if we disallow
priorities among weak constraints.
Theorem 21 Given a DATALOG ;:;c program consists of a
single component, and a literal q as input, deciding whether q is true in some stable model
of P is \Delta P
3 [O(log n)]-complete.
Proof. \Delta P[O(log n)]-Membership. We proceed exactly as in the proof of Theorem 17. How-
ever, since W consists of one only component, this time
programs with priorities is O(2 jP j )), as there is only one component in W and its weight is
1. Consequently, the number of calls to the \Sigma P
2 oracle is logarithmic in the size of the input,
as it is logarithmic in k (because we perform a binary search on [0::k]).
n)]-Hardness. Let \Phi be 2-existential QBFs, such that \Phi
m. We next reduce the \Delta P
3 [O(log n)]-hard problem of deciding
is odd to brave reasoning on DATALOG ;:;c
programs without priorities (i.e., with one only component in W ). W.l.o.g. we assume that
is even, 2) the same propositional variable does not appear in two distinct QBFs. and
the QBFs \Phi are as in the proof of Theorem 19.
a) and LP (\Phi i ) is defined as
in Theorem 19 apart from replacing each occurrence of v by v
c)
The weak constraints in W 0 enable to select the stable models of LP (\Phi) where the number
of valid QBFs is maximum. Then, is odd if and only if odd
is true in some stable model of P. 2
As for DATALOG ;:;c programs with prioritized weak constraints, the complexity is not
affected at all by negation and strong constraints.
Corollary 22 Let program where W has a single
component. Then, brave reasoning is \Delta P
3 [O(log n)]-complete even if P is subject to the
following restrictions:
LP is stratified or even positive.
Proof. Membership in \Delta P
3 [O(log n)] comes from Theorem 21. Hardness under the restriction
1 for stratified programs comes from the hardness proof of Theorem 21, as the reduction
there does not make use of both priorities and strong constraints and utilizes only stratified
negation. To complete the proof we have only to demonstrate hardness for the case of
positive programs. To this end, we just need to eliminate negation from the logic program
(of the proof of Theorem 21) as follows:
1. Eliminate from LP 0 all rules with head odd (that are the only rules containing nega-
tion).
2. Insert the following weak constraints in W :
even (1  i  m=2)5 Discussion on Complexity and Expressiveness of DATALOG ;:;c
In this section we discuss the results on the complexity of DATALOG ;:;c that we established
in the previous section. Interestingly, these results allow us to draw some useful remarks also
on the expressive power of our language, which turns out to be strictly more powerful than
disjunctive Datalog (without constraints). We show also that the increased expressive power
of our language has a relevance even from the practical side, providing some meaningful
examples that can be represented very naturally in DATALOG ;:;c , while their disjunctive
encoding is impossible (or so complex to be unusable).
Table

1: The Complexity of Brave Reasoning in various Extensions of Datalog with Constraints
(Propositional Case under Stable Model Semantics)

Table

1 sumarizes the complexity results of the previous section, complemented with other
results (on the complexity of programs without constraints) already known in the literature.
Therein, each column refers to a specific form of constraints, namely:
strong constraints, constraints with priorities,
priorities (i.e., W has only one component). The lines of Table 1 specify the allowance of
disjunction and negation; in particular, : s stands for stratified negation [45] and  h stands
for HCF disjunction [3] (see AppendixB). Each entry of the table provides the complexity
class of the corresponding fragment of the language. For an instance, the entry (8; 5) defines
the fragment of DATALOG ;:;c allowing disjunction and stratified negation
as far as constraints is concerned, only weak constraints with priorities (fw ! g); that is,
unstratified negation and strong constraints are disallowed in this fragment. The languages
correspond to the fragments (3,1) and (9,1), respectively.
Full DATALOG ;:;c is the fragment (9,6), whose complexity is reported in the lower right
corner of the table. The corresponding entry in the table, namely \Delta P, expresses that the
brave reasoning for DATALOG ;:;c is \Delta P
3 -complete.
The first observation is that DATALOG ;:;c is strictly more expressive than DATALOG ;: .
Indeed, the former language can express all problems that can be represented in the lat-
ter, as DATALOG ;:;c is an extension of DATALOG ;: . Moreover, the \Delta P-completeness
of DATALOG ;:;c witnesses that DATALOG ;:;c can express some \Delta P
3 -complete problems,
while DATALOG ;: cannot (unless the Polynomial Hierarchy collapses) [15]. An example of
encoding of a \Delta P
3 -complete problem has been reported in the proof of Theorem 19. To see
another example, consider again abductive reasoning addressed in Section 3.3. A hypothesis
is relevant for a logic programming abductive problem P if it occurs in some explanation of
under minimum cardinality (resp. prioritized) abduction, relevance requires membership
to a minimum cardinality solution (resp. minimal solution according to the prioritization).
From the results of [13, 14], deciding relevance is \Delta P
3 [O(log n)]-complete for abduction with
minimum cardinality criterion, while it is \Delta P-complete for prioritized abduction. There-
fore, relevance of an hypothesis h for a logic programming abduction problem cannot be
expressed reasoning on disjunctive Datalog (as \Sigma Pis an upper bound to the complexity of
brave reasoning on DATALOG ;: [15]). On the other hand, from the translation we provided
in Section 3.3, it is easy to see that h is relevant for P iff it is a brave consequence of pr(P)
(i.e., relevance can be reduced to brave reasoning on DATALOG ;:;c ). 8
Considering that DATALOG ;:;c is a linguistic extension of DATALOG ;: by constraints,
it turns out that constraints do add expressive power to DATALOG ;: . However, it is not
the case of strong constraints, as it can be seen from Table 1. Indeed, if we look at the various
fragments of the language that differ only for the presence of strong constraints, we can note
that complexity is constant (compare column 1 to 2, or 3 to 4, or 5 to 6). In fact, under stable
model semantics, a strong constraint of the form / B is actually a shorthand for p / B; :p.
As an example, consider the problem SCHEDULING of Section 1. The program P sch we used
to express SCHEDULING relies on HCF disjunction with stratified negation and contains
only one strong constraint (no weak constraints occur in it - fragment (5,2)). This problem
can be easily formulated in HCF DATALOG ;: with unstratified negation (fragment (6,1))
simply by replacing the strong constraint / assign(X; S); assign(Y; S); incompatible(X; Y )
by the DATALOG : rule
where p is a new atom. 9 It is worth noting that brave reasoning allows us to simulate strong
constraints if negation is not allowed in the program: replace each strong constraint / B
by the rule p / B (where p is a fresh atom), and require that :p is a brave consequence.
Thus, it is rather clear that strong constraints do not affect at all the complexity and
expressiveness of the language. Therefore, the increased expressive power of DATALOG ;:;c
(w.r.t. DATALOG ;: ) is due entirely to weak constraints. However, weak constraints do not
8 Note that we have \Delta P-hardness only if disjunction is allowed in the abductive theory LP . Thus, example
P net is not an hard instance of the problem; but the translation we gave is general and holds also for hard
instances with disjunction in the abductive theory LP .
9 actually, the SCHEDULING problem can be even formulated in DATALOG : , as HCF disjunction
can be simulated by unstratified negation. Indeed, the "guess" expressed by the disjunctive rule can be
implemented by the following three nondisjunctive rules
ts 1
ts 2
ts 3
ts 2
ts 1
ts 3
ts 3
ts 1
ts 2
cause a tremendous increase of the computational cost, they "mildly" increase the complexity,
as we can see by comparing column 1 to columns 3 and 5 of Table 1. For example, if
we add weak constraints to HCF disjunction (with or without negation - see lines 4-6)
we increase the complexity from NP to \Delta P[O(log n)] or \Delta P, depending on whether weak
constraints are prioritized or not, respectively. Note that the program P cliq of Example 9
consists of a weak constraint on top of an HCF program. Likewise, weak constraints added
to DATALOG ;: increase its complexity from \Sigma Pto \Delta P[O(log n)] or \Delta P, depending on the
possible prioritization of weak constraints (see lines 7-9). Therefore, adding weak constraints,
the complexity of the language always remains at the same level of the polynomial hierarchy;
for instance, from NP we can reach \Delta P
2 , but we will never jump to \Sigma P
2 or to
other classes of the second level of the polynomial hierarchy.
Clearly, weak constraints do not impact on the complexity of fragments admitting a unique
stable model (see lines 1 and 2).
Further remarks on the complexity of the various fragments of the language are the fol-
lowing. First, the presence of negation does not impact on the complexity of the fragments
allowing disjunction (see lines 4 to 9). Second, the complexity of the -free fragments
with full negation (see line coincides with that of HCF disjunction (lines 4 to 6) and
lies one level down in the polynomial hierarchy with respect to fragments based on plain
DATALOG ;: (see line 9).
Besides the increase in theoretical expressiveness - the ability to express problems that
cannot be represented in DATALOG ;: - DATALOG ;:;c provides another even more important
advantage: several problems that can be represented also in DATALOG ;: (whose
complexity is thus not greater than \Sigma P) admit a much more natural and easy-to-understand
encoding in DATALOG ;:;c . This is because coupling both disjunction and constraints, provides
a powerful and elegant tool to encode knowledge. To better appreciate the simplicity
and readability of DATALOG ;:;c , consider again the problem MAX CLIQUE, that has
been represented very simply and elegantly in DATALOG ;:;c (see Example 9). We next
show that it can be encoded also in DATALOG ;: but, unfortunately, the resulting program
is very tricky and difficult to understand. The technique we use to build a DATALOG ;:
version of MAX CLIQUE is that described in [15], based on a modular approach. A first
module LP 1 generates candidate solutions (cliques in this case) and a second module LP 2
discards those that do not satisfy certain criteria (maximal cardinality here).
The above disjunctive program LP 1 generates all cliques and their sizes. We have assumed
that the nodes are ordered by the relation succ that is provided in input (but could also be
"guessed" by another module). Rule r 1 guesses a clique c and rule r 2 enforces the constraint
that every two nodes in c must be joined by an edge. By this rule the constraint must be
satisfied in every stable model (if the constraint is unsatisfiable, then no stable model exist).
The atom count(I; J) expresses that the node I is the J-th node of the clique c. Thus, rule
r 6 defines the size (number of nodes) of c.
Now, to restrict to only maximum size cliques, we add to LP 1 the following DATALOG ;:
program LP 2 which discards clique nonmaximal in size.
r 0: c 0 (X)  not c 0 (X) / node(X)
r 0: count1(I; J) / count1(A; B); succ(A; I); succ(B; J); c 0 (I)
r 0: c 0 size(K) / greatestV ertex(N); count1(N; K)
r 0: notGreater / c
r 0: not c 0 (X) / node(X); notGreater
Here, r 0
1 guesses another clique c 0 . notGreater is true if c 0 is not a clique. count1 counts
the elements of c 0 and c 0 size define the size of c 0 . If the size of c 0 is less than or equal to
that of c then notGreater is true. If so, c 0 and not c 0 are assigned the maximum extension
by rules r 0
8 and r 0
9 . In this way, if all cliques c 0 are smaller than c then all stable models of
collapse into a single stable model with the maximum extension for both c and c 0 and
containing notGreater. If, on the contrary, there is some clique c 0 bigger than c, then no
stable model of LP 2 contains notGreater. Thus, the rule r 0imposes every stable model to
contain notGreater (if any). It is easy to recognize that, for the program
there is a one-to-one correspondence between stable models and maximum cliques of G.
Comparing the above DATALOG ;: program with the DATALOG ;:;c version of Example
it is quite apparent the advantage that weak constraints provide in terms of simplicity
and naturalness of programming.
Concluding, we would like to bring reader's attention to the fragment of DATALOG ;:;c
with HCF disjunction and stratified negation ((5,6) in Table 1): it has a very clear and easy-
to-understand semantics and, at the same time, allows us to express several hard problems
(up to \Delta P
-complete problems) in a natural and compact fashion. (In our opinion, recursion
through disjunction or negation makes programs more difficult to understand).
Perhaps our DATALOG ;: encoding of MAX CLIQUE is not the best; but we are very skeptical on the
existence of a DATALOG ;: encoding which is simpler than the DATALOG ;:;c encoding (of example 9).


--R

Logic Programming and Negation: A Survey
Logic Programming and Knowledge Representation Journal of Logic Programming
Propositional Semantics for Disjunctive Logic Pro- grams
Reasoning with Minimal Models: Efficient Algorithms and Applications.
Disjunctive Semantics Based upon Partial and Bottom-Up Evaluation
Nonmonotonic Reasoning: Logical Foundations of Commonsense.
Preferred Answer Sets for Extended Logic Programs
A Survey of Complexity Results for Non-monotonic Logics
Generalized Closed World Assumption is
A slick procedure for integrity checking in deductive databases
Adding Disjunction to Datalog
On the Computational Cost of Disjunctive Logic Pro- gramming: Propositional Case
Abduction From Logic Programs: Semantics and Complexity.
The Complexity of Logic-Based Abduction
Disjunctive
On the Semantics of Updates in Databases
Disjunctive LP
Semantics of Disjunctive Deductive Databases
Computers and Intractability - A Guide to the Theory of NP-Completeness
Classical Negation in Logic Programs and Disjunctive Databases
Complexity and Expressive Power of Disjunctive Logic Pro- gramming

Extending Datalog with Choice and Weak Constraints

"Disjunctive Logic Programming and Disjunctive Data- bases,"

The Complexity of Optimization Problems.
A theorem-proving approach to database integrity
Declarative and Fixpoint Characterizations of Disjunctive Stable Models
Disjunctive Stable Models: Unfounded Sets
Computing Circumscription
Foundations of Logic Programming.
constraint checking in stratified databases
Foundations of Disjunctive Logic Programming MIT Press
Generalized stable models: a semantics for abduction
Abductive Logic Programming.
Generalizations of OptP to the Polynomial Hierarchy
The Relationship between Logic Program Semantics and Non-Monotonic Reasoning
Autoepistemic Logic
On Indefinite Data Bases and the Closed World Assumption
Computational Complexity
Abductive Inference Models for Diagnostic Problem Solving
Abduction and induction
Weakly Perfect Model Semantics for Logic Programs
"Foundations of deductive databases and logic programming,"
Stable Semantics for Disjunctive Programs
Static Semantics for Normal and Disjunctive Logic Programs
"Deductive and Object-Oriented Databases,"
Modular Stratification and Magic Sets for Datalog Programs with Negation
The Expressive Powers of Stable Models for Bound and Unbound DATALOG Queries
Possible model semantics for disjunctive databases
The Expressive Powers of Logic Programming Semantics
Classifying the Computational Complexity of Problems
Word Problems Requiring Exponential Time
Principles of Database and Knowledge-Base Systems
The Well-Founded Semantics for General Logic Programs
Complexity of relational query languages
Bounded query classes




--TR

--CTR
Alfredo Garro , Luigi Palopoli , Francesco Ricca, Exploiting agents in e-learning and skills management context, AI Communications, v.19 n.2, p.137-154, April 2006
Alfredo Garro , Luigi Palopoli , Francesco Ricca, Exploiting agents in e-learning and skills management context, AI Communications, v.19 n.2, p.137-154, January 2006
On the rewriting and efficient computation of bound disjunctive datalog queries, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.136-147, August 27-29, 2003, Uppsala, Sweden
Gianluigi Greco , Sergio Greco , Irina Trubitsyna , Ester Zumpano, Optimization of bound disjunctive queries with constraints, Theory and Practice of Logic Programming, v.5 n.6, p.713-745, November 2005
Simona Perri , Francesco Scarcello , Nicola Leone, Abductive logic programs with penalization: semantics, complexity and implementation, Theory and Practice of Logic Programming, v.5 n.1-2, p.123-159, January 2005
Francesco Calimeri , Giovambattista Ianni, Template programs for Disjunctive Logic Programming: An operational semantics, AI Communications, v.19 n.3, p.193-206, August 2006
Filippo Furfaro , Sergio Greco , Sumit Ganguly , Carlo Zaniolo, Pushing extrema aggregates to optimize logic queries, Information Systems, v.27 n.5, p.321-343, July 2002
Thomas Eiter , Michael Fink , Hans Tompits, A knowledge-based approach for selecting information sources, Theory and Practice of Logic Programming, v.7 n.3, p.249-300, May 2007
Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki, Answer sets for consistent query answering in inconsistent databases, Theory and Practice of Logic Programming, v.3 n.4, p.393-424, July
Nicola Leone , Gerald Pfeifer , Wolfgang Faber , Thomas Eiter , Georg Gottlob , Simona Perri , Francesco Scarcello, The DLV system for knowledge representation and reasoning, ACM Transactions on Computational Logic (TOCL), v.7 n.3, p.499-562, July 2006
Christoph Koch , Nicola Leone , Gerald Pfeifer, Enhancing disjunctive logic programming systems by SAT checkers, Artificial Intelligence, v.151 n.1-2, p.177-212, December
Thomas Eiter , Michael Fink , Giuliana Sabbatini , Hans Tompits, Using methods of declarative logic programming for intelligent information agents, Theory and Practice of Logic Programming, v.2 n.6, p.645-709, November 2002
Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001
disjunctive datalog;deductive databases;knowledge representation;computational complexity;nonmonotonic reasoning