Logic as a Query Language.
AbstractResearch in nonmonotonic reasoning has focused largely on the idea of representing knowledge about the world via rules that are generally true but can be defeated. Even if relational databases are nowadays the main tool for storing very large sets of data, the approach of using nonmonotonic AI formalisms as relational database query languages has been investigated to a much smaller extent. In this work, we propose a novel application of Reiter's default logic by introducing a default query language (DQL) for finite relational databases, which is based on default rules. The main result of this paper is that DQL is as expressive as SO, the existential-universal fragment of second-order logic. This result is not only of theoretical importance: We exhibit querieswhich are useful in practicethat can be expressed with DQL and cannot with other query languages based on nonmonotonic logics such as DATALOG with negation under the stable model semantics. In particular, we show that DQL is well-suited for diagnostic reasoning.
Introduction
F OR the purpose of Knowledge Representation, non-monotonic
reasoning (NMR henceforth) formalisms
can be used in two dierent ways:
as languages for representing knowledge about the
world, via rules that are generally true but can be de-
feated. Retrieving information from a non-monotonic
knowledge base of this kind amounts to prove a theorem

As an example, we can use default logic to state that
\birds generally
y". In order to prove that the bird
Tweety
ies, we try to prove that a specic formula
follows {in the default logic semantics{ from the set of
general rules plus a set of specic facts;
as relational database query languages. Retrieving information
amounts to computing the set of tuples belonging
to an intensional relation, starting from some
extensional relations. As an example, we can query
a relational database by means of a DATALOG : program
{i.e., a DATALOG program with negated literals
in the body of the rules{ equipped with a specic semantics
for negation.
Research in NMR has focused largely on the former idea,
and remarkable results about the computational complex-
A preliminary and partial version of this paper appears in the
Proceedings of the Fourth International Conference on Principles of
Knowledge Representation and Reasoning (KR-94), Bonn, Germany,
May 1994. Morgan Kaufmann Publishers, Inc. San Francisco, Ca.
M. Cadoli is with the Dipartimento di Informatica e Sistemistica,
Universita di Roma \La Sapienza", Via Salaria 113, I-00198 Roma,
Italy. E-mail: cadoli@dis.uniroma1.it
T. Eiter and G. Gottlob are with the Information Systems Depart-
ment, Technical University of Vienna, Paniglgasse 16, A-1040 Wien,
Austria. E-mail: (eiterjgottlob)@dbai.tuwien.ac.at
ity of several formalisms have been obtained by many authors
(cf. [1] for a survey on this topic).
Even if relational databases are nowadays the main tool
for storing very large sets of data, the latter approach has
been investigated to a much smaller extent.
One of the most important aspects of a query language
for relational databases is its expressive power, i.e., the set
of relations that we can compute by querying. The expressive
power of relational database query languages has
been studied for some twenty years now (cf. [2]). Research
has focused mainly on monotonic query languages, i.e., languages
such that if the extensional relations grow then the
intensional ones grow as well.
Recently some interesting works investigating the expressive
power of non-monotonic query languages appeared.
Kolaitis and Papadimitriou study in [3] the expressive
power of two semantics for DATALOG : programs. In particular
they prove that DATALOG : with xed-point semantics
is as expressive as SO 9 , the existential fragment
of second-order logic. Schlipf proves in [4] an analogous
result for DATALOG : with stable model semantics for
logic programs [5] (stable models are called default models
in [6], [7]); in the following, we refer to this variant
of DATALOG as DATALOG :
stable . Sacca gives in [8] further
insight on the expressive power of interesting variants
of
stable . Van Gelder analyzes in [9] the expressive
power of DATALOG : with well-founded semantics
[10]. In all these papers, databases are modeled as
nite structures, i.e., nite interpretations of theories.
In this work we are concerned with default logic as a query
language. Default logic [11] is one of the most popular
NMR formalisms and has been extensively investigated
both from the semantical and the computational point of
view. It has also been proposed in [7] as a tool for inferencing
in logical databases (i.e., databases which are theories).
Anyway the behavior of default logic on nite structures
(i.e., on relational databases) has not been analyzed so far.
Here we propose a novel application of default logic by
introducing a default query language (DQL) for nite relational
databases, which is based on default rules. The
main result of this paper is that DQL is more expressive
than
stable . In particular DQL is as expressive
as SO 98 , the existential-universal fragment of second-order
logic. This result is not only of theoretical importance: We
exhibit queries {which are useful in practice{ that can be
expressed with DQL and can not with DATALOG :
stable .
Two of the queries are taken from the realm of economics,
while another one deals with diagnostic reasoning on a cir-
cuit; it appears that DQL allows for an easy formalization
of this process.
An alternative way of describing our main result is to
say that DQL \captures" the complexity class  p
2 of the
CADOLI, EITER AND GOTTLOB: DEFAULT LOGIC AS A QUERY LANGUAGE 101
polynomial hierarchy, while DATALOG :
stable \just" captures
the class NP. Therefore DQL is more expressive than
stable provided  p
hierarchy does not collapse {a property that has
been widely conjectured and that will be assumed through-out
this work.
We remind that  p
2 -completeness of credulous propositional
default reasoning has been recently proven [12],
[13]. It is therefore important to remark that the expressive
power of a language is not necessarily the same as
its complexity. Several languages with this property are
known, cf. [14], [15]. As an example, a language which does
not capture NP {even if it has an underlying NP-complete
problem{ has been shown by Stewart in [16].
To show that DQL is well-suited for formulating useful
and practical queries in dierent domains, we present
several examples. One of the examples deals with troubleshooting
for electric circuits. It appears that DQL allows
for an elegant implementation of advanced diagnostic
reasoning principles (in particular, abductive model-based
diagnosis [17], [18]). Other examples deal with relevant
queries in business administration.
The structure of the paper is the following. Section II
provides some motivating examples. In Section III we state
necessary preliminaries on query languages for relational
databases and provide a brief introduction to default logic.
In Section IV we give the denition of the query language
DQL, providing syntax and semantics. In Section V we give
a formal proof of the fact that DQL captures  p
2 . More-
over, we brie
y address the computational complexity of
DQL, and we consider the sublanguage of normal DQL
queries, which is analogous to normal default theories. In
Section VI we show how complex problems like those presented
in Section II can be solved in DQL. We draw some
conclusions and compare DQL with some query languages
arising from logic programming in the nal Section VII. In
order to increase the readability, the proofs of all results
have been moved to an appendix.
II. Motivating examples
Before diving into the technical part of the paper, let us
motivate with some examples, why query languages with
higher expressiveness than DATALOG :
stable are needed.
These examples will be dealt with in much more detailed
way in Section VI.
Our rst example here is from the domain of model-based
diagnosis (MBD) of electric devices. This very promising
eld is an active research area in AI cf. [19], [20]. It would
therefore be interesting to integrate the paradigm of MBD
into relational databases, as the descriptions of large electric
systems (e.g., of power networks) should benecially
be stored in a database.
Example 1: (Electric circuit troubleshooting) An
electric circuit has several components. All of them might
be in some way malfunctioning, or even misdesigned (e.g.,
the resistance value of a resistor could be too small).
In the (simplied) electric circuit represented in Figure 1,
we have a battery, two resistors and two fuses, and a conF
Fig. 1. Electric circuit
trol light with a bulb. The higher the battery's voltage the
higher the current's amperage. Similarly, the smaller the
resistor's resistance the higher the amperage. If the am-
perage in the circuit exceeds a certain amount, one of the
fuses melts; the circuit is interrupted, and the control light
is o. It is not predictable which one of the fuses will melt,
or even if both of them will.
In the kind of MBD known as abductive diagnosis, it is
customary to to say that when a component does not work
properly, one or more eects can show up. Moreover, an
eect is originated by a set of causes, and a set of causes
does not originate univocally an eect. In the above circuit,
melting of a fuse is a eect, and battery's voltage being too
high is a cause. Similarly, a melted fuse {as well as a broken
bulb{ is a cause for the eect of the control light being
(cf. [21], [17], [18], [22] for a background and overview on
results on abductive diagnosis).
In abductive diagnosis, knowledge about a circuit such as
the above one is typically described by a diagnostic theory
that consists of rules of the form
where the C i 's are causes and the E j 's are eects. As an
example, the following rule states that melting of one of the
fuses will occur whenever both resistance values are low
Not necessarily all of the antecedents of a rule of the kind
(1) are possible causes. As an example, we might be sure
that the rst resistor is not underdimensioned; in such a
case, R 1 -low would not be a possible cause. The possible
causes are called hypotheses. Finally, in each specic situation
we make a set of observations, e.g., the control light
is o.
Given a situation, described by a set of rules of the kind
(1), a set of hypotheses and a set of observations, abductive
diagnosis looks for an explanation of the observations we
make. An explanation is a minimal set of hypotheses (wrt
inclusion), such that their validity implies through the rules
all observations. In a general situation it is possible that
one, many, or no explanations exist. The hypotheses that
belong to at least one explanation of the diagnostic problem
are called relevant for the problem; computing the relevant
facts of a diagnostic problem is an important subtask in
troubleshooting, for being able to focus fault localization
on a subset of the possible causes.
It is easy to conceive a database that stores rules on
causes and eects, as well as hypotheses and observations.
Anyway, from results on the complexity of propositional
abduction in [22], it follows easily that computing the relevant
facts for troubleshooting problems is a problem that
is hard for the complexity class  p
2 of the polynomial hierarchy
(cf. [23]); in fact, already deciding if a specic fact
is relevant is hard. This means that it is not possible to
compute the relevant facts in DATALOG :
stable (the reason
why is discussed in Section III-A). Similarly, it is not possible
to formulate a Boolean query in DATALOG :
stable that
decides if a specic fact is relevant. On the other hand, in
Section VI we will show how it is possible to write a DQL
query that computes all facts relevant for the problem. 2
The remaining examples in this section deal with business
applications in a somewhat simplied economic world.
Example 2: (Strategic companies) Suppose a holding
owns some companies. Each company produces a set of
products. Each product is produced by at most two com-
panies. As an example, pasta is produced by Barilla and
Saiwa, while wine is produced only by Barilla 1 .
Suppose the holding experiences a crisis and has to sell
one company. The holding's policy is to keep on producing
all products. This clearly makes it impossible to sell
some companies {as an example the Barilla company in the
above situation, because it would be impossible to produce
wine. Anyway the managers are even more cautious: They
know that in the future it may be necessary to sell more
companies, and they do not want to get into a situation in
which they will not be able to produce all products. More
formally, they are interested in the minimal sets of companies
that produce all products. A company is strategic if it
is in at least one of such minimal sets. Therefore a query
which is very relevant to the managers is whether a company
is strategic or not: They prefer to sell a non-strategic
company rst, because after the transaction the minimal
sets of companies that produce all products remain the
same.
Now let us consider a slightly more complex situation,
in which up to three (say) companies can control another
company. As an example, companies Barilla and Saiwa
together have control over company Frutto.
Assume now that the following constraint is imposed for
determining strategic companies: A company A which is
controlled by the companies can be sold only
if also one of the companies is sold. This constraint
completely changes the minimal sets of companies
that produce all products.
In the former case {no controlled companies{ the problem
of deciding whether a company is strategic is in the
complexity class NP (cf. [24]), while in the latter case the
same problem is easily shown to be complete for the class
coincidence with existing companies is purely
casual.
2 of the polynomial hierarchy (cf. [25]). As a consequence
(cf. Section III-A), the former query is expressible
in
stable , while the latter is not. In Section VI
we will show how it is possible to write two DQL queries
that compute the sets of the strategic companies in the two
cases. 2
Example 3: (Maximal trust) In a set of companies it
is possible to make agreements. A company may have an
agreement with another company, and of course it can have
simultaneously several agreements with dierent compa-
nies. A trust is a set T of companies such that each one
has an agreement with each other company in T ; a trust T
is maximal if there is no trust T 0 that has more companies
than T , i.e., jT 0 j > jT j. Now, the following query rises:
which companies belong to a maximal trust?
Computing this query is an NP-hard problem, and also a
co-NP-hard problem. As a consequence (cf. Section III-A)
the query can not be written in DATALOG :
stable (unless
some unexpected collapse of complexity classes). On the
other hand, the query can be expressed in DQL. 2
III. Preliminaries
A. Relational databases
For a background on relational databases and query lan-
guages, the reader is referred to [26], [27]. A database
schema R is a nite set fR of relation schemata.
A relation schema R i has a name N i and a nite list of attributes
i. It will sometimes be denoted
as R i
). The number l i is the arity of the relation
We assume that there is an underlying set
U of objects that can be used in relations (the so-called do-
main). The domain U is arbitrarily large but nite. Given
a relation schema R i , a relation instance is a set of tuples
of the form ha
database instance W is a set of relation instances. The
set of objects occurring in a database (the so-called active
domain) is a subset {possibly not strict{ of U .
A database query (or often, simply query) is a mapping
from the set of all database instances of a xed database
schema R (intuitively, the input relations) to the database
instances of a xed database schema S (the output rela-
tions). It is assumed that the mapping is computable and
generic (i.e., invariant under renamings of the constants in
U).
A query language, with its syntax and semantics, evaluates
a well-formed formula (the query) over any database
instance and returns an answer, which is a database in-
stance; thus, each query denes a database query. The
answer of an I/O query is a set of relation instances, while
the answer of a boolean query is either yes or no (in this
case, the schema S consists of a single propositional letter,
or technically, of a 0-ary relation).
The expressive power of relational database query languages
is one of the most studied topics in database theory.
Basically one is interested in knowing which relations can
be expressed by a query language and which relations can
not. A relation is expressible in a query language, if there
CADOLI, EITER AND GOTTLOB: DEFAULT LOGIC AS A QUERY LANGUAGE 103
is a query in the language that, on any input database instance
returns precisely the desired relation as the answer.
For an example, transitive closure of a graph is expressible
in DATALOG [26].
One way of presenting a result in this area is to say that a
query language can/can not express a specic relation. For
example, it is well-known that relational calculus can not
express the transitive closure of a relation [28]; the relation
of satisable propositional clause sets can be computed by
a xed program in DATALOG :
stable but not in DATALOG
(unless P=NP), cf. [4].
Measuring the complexity of Boolean queries is straight-
forward. Usually, this is dened by referring to the following
problem: Given a database instance, decide if the query
evaluates to yes. The complexity of a query language is
the complexity of this problem for the queries of this lan-
guage. This is also termed as data complexity. If the query
is not xed, i.e., the query and the database are given for
input, we analogously obtain the combined complexity of
the query language, which is often much higher.
In order to deal with the complexity and expressive
power of I/O queries, we use the key concept of query recognizability

Denition III.1: (cf. [29]) Let C be a complexity class.
A query mapping database instances over R into database
instances over S is C-recognizable, if deciding whether a
tuple t belongs to a certain output relation S i 2 S is in C.
Then, the data and combined complexity of an I/O query
language can be dened in terms of query-recognizability
similar as for Boolean queries.
Typically, the expressive power of a query language is
represented as a set of logical sentences. As an exam-
ple, the results in [4] entail that the expressive power of
stable under brave semantics is SO 9 , the existential
fragment of second-order logic, i.e., the set of sentence

where S is a list of predicate symbols and (S) is a function-free
rst-order formula in which (among possibly others)
the predicates in S occur.
The traditional notion of a query language capturing a
complexity class C is that the queries denable in this language
are precisely those which are recognizable in C. For
example, Fagin's celebrated theorem is that class of SO 9 -
queries captures the class NP [30].

Figure

describes well-known relations between the expressive
powers of several query languages and correspondences
to complexity classes, cf. [31], [32], [2]. Each
edge denotes inclusion, i.e., less expressive power, which
{assuming that complexity classes do not collapse{ is always
strict.
As well-known, DATALOG does not express all queries
computable in polynomial time, and is incomparable to
rst-order logic. Stratied DATALOG and in
ationary
DATALOG have increasing expressive power; they can express
all rst-order queries, but still not all polynomial time
computable queries queries. The latter is possible {already
for DATALOG with negation of input relations{ if a linear
ordering < of the universe is given, cf. [33].
First-order logic is equivalent with relational algebra [28].
Note that DATALOG can express queries whose computation
is P-complete, and hence, unless
is not included in the class of queries computable by
NC-circuits. The queries denable in rst-order logic with
a linear ordering < are the same as the AC 0 -queries [31]
(AC 0 is the class of problems solvable by uniform families
of constant depth circuits of polynomial size, where the fan-in
of gates is unbounded). The AC 0 -queries are a proper
subclass of the NC-queries (NC is the class of problems
solvable in polylog parallel time with polynomial amount
of total work), which are a {most likely proper{ subclass
of the queries computable in polynomial time.
The While-queries constitute a class of queries denable
in a programming-style query language, which provides assignments
of rst-order expressions to tuple variables, sequencing
of statements, and while statements. This class
appears to be quite powerful, since PSPACE-hard queries
can be expressed. On the other hand, not all queries computable
in PSPACE can be expressed (e.g., if the universe
has even size); however, this is possible if a linear ordering
< of the universe is provided.
As already mentioned above,
stable under
brave semantics is equivalent to the SO 9 fragment of
second-order logic and thus captures NP. The queries den-
able in the existential-universal second-order logic, SO 98 ,
i.e., the set of sentences
on a relational function-free vocabulary where S; T are disjoint
lists of predicate symbols and (S; T) is rst-order,
are of particular interest in this paper. The query language
based on default logic we present in Section IV, DQL, can
express exactly SO 98 . This fragment of second-order logic
captures the class  p
2 of the polynomial hierarchy, which
consists of all decision problems that can be solved by a
non-deterministic Turing machine in polynomial time with
use of an oracle for a problem (i.e., a subroutine for solving
this problem in unit time) in NP (cf. [23]). Consequently,
unless  p
(which is widely conjectured to be false),
DQL is much more expressive than DATALOG :
stable . Fi-
nally, the queries denable in full second-order logic are
those computable within the polynomial hierarchy [34],
[35].
B.
Default logic has been introduced by Reiter in [11]; it
is one of the most extensively studied non-monotonic for-
malisms. For a detailed treatment of this formal system,
the reader is referred to [36]. Interesting relations between
default logic and database theory have been shown by
Bidoit and Froidevaux in [37]. They used default logic for
dening a semantics for negation in deductive databases.
In default logic the knowledge about the world is divided
into two parts, representing certain knowledge and defeasible
rules, respectively. The rst part (denoted with W )
(Horn clause queries)
queries
First-order queries
9 First-order queries =
First-order queries \ DATALOG
Stratified
existential fixed-point queries
First-order queries
Relational Algebra
While-queries
NC-queries
Inflationary DATALOG
Fixed-point queries
Polynomial-time queries
Fixed-point-queries
stable
Second-order queries
While-queries
Fig. 2. Query languages (noncollapsing complexity classes)
is a set of closed rst-order formulae, while the second one
(denoted with D) is a collection of special inference rules
called defaults. A default is a rule of the form
where
are well-formed formulas
whose free variables are among those of
(x) is called the prerequisite of the default,  1
are called justications and
(x) is the con-
sequence. When then the propositional constant >
(true) is implicitly assumed as the justication of the de-
fault. For convenience, we will omit writing (x) if the pre-requisite
is >. A default is closed if none of ;
contains free variables. A default theory hD; W i is closed
all the defaults in D are closed. A default or default
theory which is not closed is called open.
The semantics of a closed default theory hD; W i is based
on the notion of extension, which is a possible state of the
world according to the knowledge base. Formally, an extension
can be dened using a quasi-inductive construction
as follows. Dene that for any set E of rst order formulae,
where Cons() denotes classical deductive closure. Then, E
is an extension of hD; W
E is deductively closed, and hence an innite object.
Each extension E of hD; W i is identied by its generating
defaults, which allow for a compact representation
of E. The generating defaults of E, which we denote by
GD(E; hD; W i), are the defaults
from D such
that
2 E, for all
constructible from W and GD(E; hD; W i) as follows:
Lemma 1: ([11, Theorem 2.5]) Let E be an extension
of the closed default theory
The denition of extension is extended to open default
theories by assuming that the defaults with free variables
implicitly stand for the innite set of closed defaults obtained
by replacing the free variables with terms of the
Herbrand Universe of the default theory.
A default theory can have one, multiple or no extensions
2 Actually, this is a an equivalent characterization for extensions
rather than the original denition in terms of the xed-points of an
operator .
CADOLI, EITER AND GOTTLOB: DEFAULT LOGIC AS A QUERY LANGUAGE 105
in general. Therefore, dening entailment of a formula
from a default theory hD; W i is not straightforward. The
standard variants are credulous entailment, under which
is entailed if  belongs to at least one extension of hD; W i,
and skeptical entailment, under which  follows if  belongs
to all extensions of hD; W i. From the computational
side, credulous and skeptical reasoning have been extensively
studied in the literature [38], [12], [13].
We conclude this section with a well-known example for
a default theory.
Example 4: (Nixon diamond) Assume that
where Q, and R are propositional atoms with meaning
that someone is a pacist, a quaker, and a republican, re-
spectively. The default theory has two exten-
sions: Cons(f g). In the
rst extension, a republican that is also a quaker is a paci-
st, while in the second he is not; the former extension has
the generating default Q:P
P , and the latter R::P
:P .
Thus, under credulous semantics, we can conclude that the
person is a pacist, as well as that (s)he is not a pacist;
under cautious semantics, we can conclude neither. 2
IV. Default Query Language (DQL)
In this section we give syntax and semantics of the default
query language DQL, and we consider a simple example
for more examples and applications will be
considered in Section VI.
A. Syntax
A DQL Input/Output query Q is pair (B; D) of a set B of
rst-order formulas (the background knowledge) and a set
D of open default rules, where the rst-order language is
function-free and quantier-free, plus a set of output relation
schemata g. The set of predicate symbols
occurring in the defaults of Q contains all the names
of the relation schemata of the database (the extensional
relations) and possibly other symbols (the intensional re-
lations). Output relations are intensional. The intuitive
meaning of the query is the following: We want to compute
all tuples in the S i relations which can be inferred under
the credulous default semantics. (See the next section for
a formal denition.) In particular we apply the credulous
default semantics to the propositional instantiation of the
open defaults and the background knowledge in the query,
plus the database.
A DQL Boolean query is a set of open default rules plus
a ground formula . The intuitive meaning of the query is
the following: We want to know whether  follows {under
the credulous default semantics{ from the propositional instantiation
of the defaults in the query plus the database.
Example 5: (Mary's oce) We have two relation
schemes PROG (for \programmer") and MGR (for \man-
which both have a single attribute NAME. The
database instance W is as in the following table:
Peter
Paul
Mary
MGR NAME
Mary
The I/O query Q has (B; D) as follows: the background
knowledge B is empty, and
small-o ice(x)
S consists of the single relation scheme SMALL-
OFFICE(NAME).
The relational database states that Peter, Paul, and
Mary are programmers and that Mary is a manager. The
query is made out of three open defaults. The rst one
states that a person who is provably a programmer {and
that can not be proven to be exceptional{ has a small oce
by default. The second default states that people who can
not be proven to be exceptional should be regarded as not
exceptional. The third default states the rule that people
who are provably both programmers and managers are ex-
ceptional. The intuitive meaning of the query is that we
want to know the set of people having small oces.
For an example of a Boolean query, consider the same set
of defaults, plus the ground formula small-o ice(P eter).
The intuitive meaning of the query is that we want to know
whether Peter has a small oce or not. 2
B. Semantics
The semantics of a DQL Q is dened in terms of a default
theory obtained by instantiating the query over the domain
of the database, cf. [2], [14].
Let W be a database instance over the set of relation
schemata g. For each relation instance R i , let
R i jW be the set of tuples in W belonging to R i . We denote
as COMP (W ) the completion of the database, i.e., the set
of the following ground literals:
for each tuple ha
(This is the standard translation from databases-as-models
into databases-as-complete-theories (essentially), as shown
for example in [39]).
Let (x) be a formula whose free variables are among
be a list of objects from
U . Then, we denote by [x=] the result of simultaneously
substituting  i for x i in , for all
Let (B; D) be pair of background knowledge and open
defaults of a (Boolean or I/O) query Q. We denote by
INST (B) the instantiation of B, which is the set of ground
Similarly, we denote by INST (D) the instantiation of D,
which is the set of ground defaults
106 IEEE TRANSACTIONS ON KNOWLEDGE AND
Then, for any database W for R over domain U , we
denote by Q+W the default theory with defaults INST (D)
and rst-order formulas COMP (W
Now, the credulous semantics of query Q is dened as follows

If Q is an I/O query, i.e., the pair (B; D) plus a set
of output relations, then the answer to
Q is the database instance W 0 for S over domain U dened
as follows: For each S i 2 S, S i jW 0 is the set of all ground
tuples t over U such that S i (t) follows from Q+W under
credulous semantics, i.e., it is in at least one extension of
Q+W .
If Q is a Boolean query, then the answer is yes if the
distinguished ground formula  in Q follows from Q
under the credulous default semantics; otherwise, the answer
is no.
The skeptical semantics of query Q is dened analo-
gously. (That is, if Q is an I/O query, the S i jW 0 contains
all tuples t such that S i (t) follows from Q+W under the
skeptical semantics; if Q is Boolean, the answer is yes if
follows from Q skeptical semantics and no
otherwise.)
Remark: We notice that, in the semantics for DQL queries,
two sorts of non-monotonic reasoning are involved: rst of all, the
database is completed (COMP (W )), secondly, default rules are applied
(D)). Completion of the database prohibits that new
positive facts are concluded about input predicates. This is a usual
requirement in a setting of strict relational databases.
In fact, the whole mechanism could be made homogeneous by using
default rules for obtaining completion of the database as well. One
way to achieve this is to use the following method:
for each extensional relation R i
, introduce a new predicate R 0
(of the same arity) that does not occur elsewhere;
build a set D 0 consisting of the following defaults (1  i  n):
as the set of all ground atoms R 0
each tuple
jW and R i
It can be shown that the default theory
provides the same answers (to both Boolean and I/O queries) as
Q+W . Intuitively, the R 0
predicates serve to transfer the extension
of the input relations to the respective predicate letters R i
. In fact,
in any extension of , R 0
is complete (i.e., every ground atom is true
or false) by the rst default, and R 0
must coincide with R i
by the
second and third default.
Note that if one does not allow occurrence of extensional relations
in the conclusions of user defaults (a similar restriction is often made
in logical query languages, e.g. in DATALOG) and in B, then also
the default theory
(D
where W is seen as set of ground atoms R i
and R i
R, provides the same answers as Q+W .
Note that the background theory can be used to state integrity constraints
on the input. This is e.g. possible by using a designated atom
\invalid", whose derivability indicates that the integrity constraints
are violated. E.g., a functional dependency constraint on relation R
can be implemented by the formula r(x; y)^r(x; z)^y 6= z ! invalid.
It appears that the credulous and the skeptical variant
of DQL are dual with respect to complements in their expressive
capability. In fact, all forthcoming results about
complexity and expressiveness of credulous DQL apply to
skeptical DQL in the dualized form, i.e., if each complexity
class is replaced by its complementary complexity class.
For instance, forthcoming Theorem 1 for credulous DQL
can be rephrased for skeptical DQL by saying that the
Boolean (skeptical) DQL queries precisely capture the class
2 . We will not carry out such rephrasements,
but leave this (as well as adaptations of proofs) to the interested
reader. Moreover, we will for brevity mainly use
credulous DQL in our examples and applications; notice
that credulous semantics and skeptical semantics coincide
if the Q + W has only one extension, which is often the
case.
Let us see how the semantics of DQL works in the example
shown in the previous subsection.
Example 5 (Mary's oce {continued) We assume that
the domain is fP eter; P aul; Mary g, i.e., that the domain
is the same as the active domain. Then,
prog(P aul); :mgr(P aul); prog(Mary); mgr(Mary)g;
prog(Mary)::ex(Mary)
small-o ice(Mary)
small-o ice(Paul)
prog(P eter)::ex(P eter)
small-o ice(P eter)
ex(P eter)
The default theory Q + W has one extension, whose generating
defaults are:
small-o ice(Paul)
prog(P eter)::ex(P eter)
small-o ice(P eter)
The answer to the I/O query (under credulous as well as
skeptical semantics) is the relation instance:
Peter
Paul
In other words, Peter and Paul have small oces, and Mary
does not have a small oce. The answer to the Boolean
query is yes. 2
V. Expressive power of DQL
In the previous section we have seen that default logic
is suitable as a query language, i.e., as a language for manipulating
relations. A very interesting question is the fol-
lowing: Which relations can be computed by DQL? Which
CADOLI, EITER AND GOTTLOB: DEFAULT LOGIC AS A QUERY LANGUAGE 107
relations can not? In other words, what is the expressive
power of DQL?
In this section we show that the expressive power of DQL
is SO 98 , the existential universal fragment of second order
logic. This result is derived for Boolean queries as well as
for general I/O queries. In order to do so, we rst derive the
result on Boolean DQL queries and, by using this result,
derive then the result for general DQL I/O queries.
Having established the expressive power of DQL, we
will then analyze the expressive power of two natural sub-languages
of DQL, namely normal DQL and semi-normal
DQL, which allow only for normal and semi-normal defaults
in the query, respectively. These restrictions of DQL
correspond to the classes of normal and semi-normal default
theories, which constitute important fragments of default
logic.
A. Boolean DQL queries
We are now ready to prove our main result, which concerns
DQL Boolean queries. The following theorem says
that DQL is capable of all and only those Boolean queries
whose complexity is in the class  p
2 . For the practitioner,
this provides very helpful information about what can be
expressed in DQL and what not. As soon as we know
the complexity of a query that we want to implement, we
can often immediately tell whether this query is feasible in
DQL or not. For example, all queries in Section II have
complexity in  p
. As a consequence, they all can be expressed
in DQL (cf. Section VI). On the other hand, if
the complexity is higher than  p
then it is impossible (or
extremely unlikely) that the query can be implemented in
DQL. As a consequence, a query that tells whether a player
has a win in a given situation of the GO-GAME (stored in
the database) can not be written in DQL, since this is a
PSPACE-complete problem (cf. e.g., [40]).
Theorem 1: The Boolean DQL queries precisely capture
the class  p
.
Notice that there are query languages that can express
part of the queries in  p
{and even  p
-hard queries{ but
fail to express very simple queries [15]. For such languages,
it is in general not easy to tell whether a certain (even
simple) query can be expressed, and leaves the programmer
with the uncertainty whether the query can be implemented
at all.
From the result on the expressiveness of DQL, we can
immediately derive a result on the complexity of DQL. In
particular, we obtain the following characterization of the
data complexity, i.e., of evaluating a xed query Q over
varying databases. The following theorem tells us that
this is a  p
-complete problem in general. Roughly speak-
ing, this means that query evaluation is still NP-complete,
even if we have an oracle (i.e., a subprogram) for solving
NP-complete problems available and do not account
for calls to this oracle. Practically speaking, this means
that we can not reduce query evaluation to solving an NP-complete
problem (e.g., checking classical satisability of
a set of propositional clauses) eciently. In particular, an
ecient reduction to integer programming methods, which
have been investigated in the context of logic programming
[41], is not feasible.
Theorem 2: The data complexity of Boolean DQL is  p
complete.
We remark that complexity grows a lot if the query
is not xed, i.e., in case of evaluating a given query on
a given database (combined complexity). In fact, there
is an exponential increase in complexity, and the combined
complexity can be shown to be complete for the
class NEXPTIME NP , which is the exponential analogue
for  p
B. DQL I/O queries
Now we consider DQL queries that compute output rela-
tions. Using Theorem 1, we show the following more general
theorem, which tells that all and only the I/O queries
with complexity in  p
2 can be expressed in DQL. As in the
case of Boolean queries, this gives again valuable information
about what can be implemented and what not. For
example, we immediately know that a query computing the
transitive closure of a graph can be implemented in DQL,
since its complexity is polynomial.
Theorem 3: A database query is  p
-recognizable if and
only if it is denable as a DQL I/O query.
C. Normal DQL queries
Fragments of default logic resulting by imposing syntactical
restrictions on the default rules, have been considered
already by Reiter in his seminal paper [11].
Common restrictions are rules of the forms
called normal default rules, and
(x) , which
are called seminormal default rules; a default theory is
called normal (resp. semi-normal) i every default is normal
semi-normal).
The classes of normal and semi-normal default theories
are important and well-studied fragments of default logic.
In particular, normal default theories model jumping to a
conclusion if and only if it is possible. Semi-normal defaults
allow for expressing priorities between otherwise normal
defaults. In many applications default knowledge can be
represented by a normal or semi-normal default theory (cf.
e.g. [42] for an extensive treatment.)
This motivates to consider the sublanguages of DQL
which correspond to normal and semi-normal default the-
ories, respectively.
Denition V.1: A default query Q is called normal
each default in D is normal
semi-normal), i.e., of the form
Clearly, normal DQL queries are also semi-normal, and
thus a proper syntactical restriction.
Example (Students and employees) Assume that
R consists of the two relation scheme R relation schemes
MARRIED and STUDENT, which both have a single
attribute NAME. The I/O query specied by (B; D)
is used to compute instances of the output relations
ADULT(NAME) and EMPLOYEE(NAME):
The background knowledge is that married people are
adults. The rst default in D states that students are typically
not employed, and the second that adults are usually
employed. Consider the following instance W of R, where
the domain is f John; Sue; Betty g:
MARRIED NAME
Sue
John
Sue
The query computes the following output:
Sue
SueThe question rises if normal DQL and semi-normal DQL
are less powerful than general DQL. It turns out that normal
DQL is already as powerful as general DQL, and thus
can express all queries in  p
2 . This can be shown by slight
modications of the default theories constructed in the
proofs of Theorems 1 and 3. Again, these theorems sharply
describe what can be implemented in this language and
what not; the advantage is that from the complexity of a
query, one can mostly immediately tell whether it can be
implemented or not (although, this does not give us a clue
of how the query program may look like).
Theorem 4: The Boolean normal DQL queries precisely
capture the class  p
.
Theorem 5: The normal I/O DQL queries precisely capture
the class of  p
-recognizable queries.
As an immediate corollary, we obtain analogous results
for seminormal DQL.
Corollary 1: The seminormal Boolean DQL queries
capture the class  p
2 (resp. the class
of  p
-recognizable queries).
We remark that Theorems 4 and 5 can be proved, though
less instructive, by combining results in [37], [43] and recent
results of some of the authors [15].
VI. Applications of DQL
In this section we will show how to write DQL queries
solving some of the problems mentioned in Section II.
Example 1 (Electric circuit troubleshooting {
continued) Rules on causes and eects of the kind (1)
are stored in an appropriate relation.
Note that we can assume that all rules are of a uniform
type
since we can encode rules with more than two causes and/or
eects easily by a small number of such rules using new
dummy facts. A conjunction disjunction
can be represented by a new fact F (resp. G),
and the rules
Then, for instance the rule C 1
rewritten to F ^C 3 ! G_D 3 ; it should be clear how other
rules can be rewritten. Note that a general clause set can
be transformed by this method into a uniform clause set in
polynomial time.
It is assumed that symbols T and F represent the empty
cause (which is intuitively always true) and the empty effect
(which is always false), respectively, and that there are
special relations TRUE(CAUSE) and FALSE(EFFECT)
which contain always only the single tuple T and F , respectively

In our example, the following relation instances describe
rules for causes and eects of the circuit in Figure 1:
B-high
-melts F 2
-melts
-low R 2
-low F 1
-melts F 2
-melts
-melts T Light-o F
Bulb-broken T Light-o F
The meaning of the rst tuple in RULE is: whenever the
battery's voltage is too high, one of the fuses or both of
them might melt, even if the resistors are ok. The second
tuple states that melting of fuses will occur whenever both
resistors are low (cf. rule(2)). The other tuples state that
a melted fuse or a broken bulb causes the control light to
be o.
The set of possible causes are stored in another relation.
As already mentioned, not necessarily all of the names cited
in the rst three columns of the above relation are possible
causes.
HYPOTHESIS FACT
B-high
Bulb-broken
This organization of knowledge is useful when one wants to
decouple static knowledge (such as the knowledge on the
circuit) and dynamic knowledge (such as knowing whether
a specic device is malfunctioning).
The set of observations we are making in a spe-
cic situation is stored in a third relation, OBSERVA-
TION(SYMPTOM).
OBSERVATION SYMPTOM
As already mentioned, an explanation is a minimal set S of
facts (wrt inclusion), taken from the relation HYPOTHE-
SIS, such that their validity implies from the causes-eects
CADOLI, EITER AND GOTTLOB: DEFAULT LOGIC AS A QUERY LANGUAGE 109
relationships in RULE all facts in the relation OBSERVA-
TION, i.e., in every truth value assignment to the remaining
facts which is compatible with all causes-eects rela-
tionships, the facts from OBSERVATION must be true.
In our example, the set fBulb-brokeng is an explanation:
all of its elements occur in the HYPOTHESIS relation, and
the fact Light-o is explained from the rule represented by
the last tuple in RULE. Note that the set fBulb-broken,
R 2 -lowg is not an explanation, since it is not minimal wrt
to inclusion. fB-highg is the only alternative explanation
possible.
The set of explanations of a diagnosis instance can be
computed by means of the following background knowledge
B and open defaults D:
The intuitive meaning of t(x) is \x is true", i.e., it can be
proven using knowledge on the circuit and observations,
and the intuitive meaning of exp(x) is \x is part of the
explanation". The other predicates exp 0 (x; y), t 0 (x; y), and
remove(x) are used for assuring the minimality of an explanation
(we will explain this in more detail below).
The rst and the second default in D represent a choice
whether a fact F is considered to be in the explanation or
out; the rst formula in B represents the constraint that in
the former case, F must appear in HYPOTHESIS and is
considered to be true (by assumption). The third default
in D claries how a fact can be inferred to be true using the
diagnostic rules; the fourth default states that each fact F
in OBSERVATION must be provable. (For if not, i.e., it is
consistent to assume the negation :F , then we can infer a
contradiction.)
The remaining part of the default theory serves for assuring
that the explanation is indeed minimal wrt inclusion;
it exploits the simple fact that a set of facts S entailing
all observations is an explanation, if for any fact F from
S, after removal of F no longer all observed facts are entailed
(cf. [22] for the easy proof). Now, for each fact F ,
represents by the second formula in B the set
S described by exp after removal of F ; the last formula in
states that the facts from this set are considered to be
true. The fth default in D produces a copy of the diagnostic
rules for F , which is used to verify that, if F occurs
in S, S fFg does not entail all observations. This test is
implemented by the last two defaults in D: if F occurs in
S, then :remove(F ) must be provable.
It can be shown that the extensions of the instantiated
default theory correspond one-to-one to the explana-
tions, such that fact F belongs to an explanation exactly
belongs to the corresponding default extension.
Consequently, the credulous DQL I/O query with output
relation EXP(FACT) computes all the facts that belong to
at least one explanation of the diagnostic problem, i.e., the
relevant facts. Notice that the analog cautious version of
this DQL I/O query computes all facts necessary for an ex-
planation, i.e., the facts that belong to every explanation.
As a nal remark, we note that requiring minimality
of explanations is not a source of complexity. By the results
in [22],  p
2 -hardness of deciding relevance holds also if
non-minimal explanations are admissible; in fact, a default
query for this case would be even much simpler. 2
Example 2 (Strategic companies {continued) A possible
situation for products and companies is described by
the following database instance:
PRODUCERS
PRODUCT COMPANY #1 COMPANY #2
Pasta Barilla Saiwa
Tomatoes Frutto Barilla
Wine Barilla {
Bread Saiwa Panino
Here, the symbol \{" means that the entry is void (for-
mally, we represent this by a special object in the domain,
which is specied by a relation VOID(OBJECT) ).
In such a situation, both Barilla and Saiwa are strate-
gic, because fBarilla, Saiwag produce all products, while
neither fBarillag nor fSaiwag do that. On the other hand,
Frutto is not strategic.
The following relation instance describes control of companies
over other companies:
CONTROL
CONTROLLED CONT #1 CONT #2 CONT #3
Frutto Barilla Saiwa {
The meaning of the tuple is that companies Barilla and
Saiwa together have control over Frutto.
Taking into account that Frutto can be sold only if either
Barilla or Saiwa are also sold, the minimal sets of companies
that produce all products are completely changed. As
an example, fBarilla, Saiwag is no longer such a set, while
fBarilla, Saiwa, Fruttog is.
In the case there are no controlled companies, a manager
can easily express a DQL Boolean query whose answer tells
if a specic company C is strategic, by writing the set of
open defaults D:
producers(x;
strat(y) _ strat(z)
and adding as  the formula strat(C) (B is empty). The
intuitive meaning of the defaults is that for each product
x at least one of the producers y; z are strategic compa-
nies, and that companies are non-strategic by default. The
answer to the above Boolean query is yes precisely if the
company C is strategic.
If we add the default
strat(w)
to D, then the Boolean query having strat(C) as  gives
the desired answer for the case in which there are controlled
companies.
As a nal remark, we note that in this example we could
allow unbounded numbers of producers for each product
and controllers for each company, although the queries
would get more involved. 2
Example 3 (Maximal trust {continued) We can
straightforwardly represent agreements in our database
of companies by using a relation AGREE(COMP#1,
COMP#2), where a tuple (Barilla, Saiwa) in the relation
stands for an agreement between the companies Barilla and
Saiwa.
The query: \which companies belong to a maximal
trust?" (which computes an output relation MAX(COMP)
listing the searched companies) is  p
-recognizable, where
2 is the class of problems decidable by a deterministic
Turing machine in polynomial time with an oracle for an
NP problem (cf. [23]). Thus, since  p
2 , the query is
-recognizable, and can be expressed in DQL. In fact, a
little extra work shows that the query is even  p
recognizable, where  p
[O(log n)] is the subclass of  p
2 in
which the number of oracle calls is bound by O(log n),
where n is the size of the input (cf. [23]).
On the other hand, we have that the maximal trust
query can not be expressed in DATALOG :
stable unless
[O(log n)], which is widely assumed to be false. Indeed,
computing the maximal trust query is  p
since deciding, given an instance of AGREE and a certain
company C, whether C belongs to a maximal trust is an
n)]-hard problem; this follows trivially from the
[O(log n)]-hardness of deciding whether a given node belongs
to some clique of maximum size in a graph [44]. 2
VII. Conclusions
In this paper we have dened DQL, a query language for
relational databases based on default logic. The expressiveness
and complexity of DQL have been investigated
both for boolean queries and for I/O queries. The results
we have shown are not only of theoretical importance:
We have presented queries which are useful in practice
that can be handled with DQL, but can not with other
query languages based on non-monotonic logics such as
stable .
Let us compare and contrast DQL's expressive power
in more detail with expressive power and computational
paradigms for logic programs with stable semantics; the
results are displayed in Figure 3.
The expressive power of DATALOG :
stable under credulous
semantics is NP, i.e., precisely those queries can be
formulated by general logic programs using stable mod-
els, whose complexity is in NP (this follows by the results
in [4]). This expressiveness result has been preceded by
complexity results for credulous reasoning from propositional
logic programs, which is NP-complete for the stable
semantics [37], [45]. These results also explain that it is
possible to reduce the computation of stable models e-
L-stable
Polynomial-time queries
choice
Fig. 3. Expressiveness of stable models (noncollapsing complexity
classes)
ciently to linear programming, which has been shown as
a promising approach for implementing stable model semantics
[41]. On the other hand, the expressive power of
DQL is  p
2 . This means that strictly more queries can be
formulated, and that linear programming methods can not
be eciently applied for implementing DQL queries (un-
less complexity classes collapse that are strongly believed
to be dierent). Disjunctive logic programs are endowed
with the same expressive power as DQL: As shown in [15],
the expressive power of disjunctive DATALOG programs
using stable models (DATALOG _;:
stable ) is  p
. The same
expressive power is also available with so called least undened
partial stable (L-stable) models [46] for normal logic
programs (DATALOG :
stable ), which are a relaxation of
the concept of stable model.
An alternative to allow negation in DATALOG in order
to increase expressive power is the choice operator introduced
in [47]. Roughly, the choice operator allows for
atoms choice(x; y) in rule bodies, which choose precisely
one instantiation of the y variables for each instantiation of
the x variables. Since several possibilities exist for that in
general, the language computes non-deterministic queries
(i.e., several outputs are possible) rather than deterministic
ones (which we consider here). It is shown in [48], the semantics
of the choice operator is subsumed by stable mod-
els, and in [49], that DATALOG 6= augmented with dynamic
choice expresses exactly the non-deterministic queries computable
in polynomial time. The deterministic fragment of
this language (DET-DATALOG precisely
all queries computable in polynomial time (cf.[50]);
however, it can not be recognized. Notice that it is conjectured
that no query language for precisely the polynomial
time queries exists (see [29]).
We conclude by outlining possible issues for future work
on DQL. In the denition of query {Section IV-A{ open defaults
are quantier and function-free. One direction is a
generalization of DQL by allowing rst-order formulas with
quantiers and/or functions. Another direction is identifying
tractable fragments of DQL, in particular fragments
which resemble a subclass of the polynomial-time
CADOLI, EITER AND GOTTLOB: DEFAULT LOGIC AS A QUERY LANGUAGE 111
computable queries, and determining their expressive pow-
ers. A good starting point for this project is [38], where
several important tractable fragments of default logic have
been identied.


Appendix


Theorem 1 The Boolean DQL queries precisely capture
the class  p
.
PROOF The easy part is to show that every Boolean
DQL can be expressed as a  p
-recognizable Boolean query.
To this end, it is sucient to prove that the data complexity
of DQL (i.e., regarding the query as being xed)
is in  p
2 . We notice that the semantics of DQL given in
Section IV-B transforms query answering into credulous
reasoning in a propositional default theory. The transformation
is clearly polynomial in the size of the database. It
has been proven in [12], [13] that the problem of credulous
inference in propositional default theories is in  p
this part of the proof is complete.
The more dicult part is to show that each Boolean
query expressible as a sentence of SO 98 can be expressed
in DQL. As we already noticed in the introduction, we can
not take advantage of the fact that propositional credulous
default reasoning is  p
-hard, because the expressiveness of
a query language is not necessarily the same as its complexity

Without loss of generality, we assume that sentence (3)
is of form
where S, T are lists of predicate symbols, x; y are lists of
individual variables, and is a rst order formula in which
no function symbol or quantier occurs. The pass from
(3) to (4), which is well-known in Logic, is justied in the
report [51].
Now we have to show that for each query QSO98 of the
form (4) there is a DQL query QDQL such that the two
queries give the same answer on all possible database instances
W over the unquantied relations in (4).
We outline the idea for QDQL . The formula
encoded as follows. We use a predicate
< that denes a linear order on the set of all y-tuples,
together with associated predicates F (y),
which state that y is the rst tuple, y 0 is the successor of
y, and y is the last tuple in <, respectively. Furthermore,
we use a predicate Z(x; y) which intuitively states that for
each tuple y 0 from the initial segment of < up to y, the
designated propositional letter
A indicates if for some x-tuple a, Z(a; b) is true, where
b is the last y-tuple. Then, (9x)(8y) (x; y) will be true
just in case A is derivable. We encode this by default rules,
such that in every extension that contains A, a valuation
for the S-predicates is dened and for every valuation of
the T-predicates some Z(a; b) is true, i.e., the sentence (4)
is true over the underlying database W .
Formally, QDQL consists of the ground formula A and
the pair (B; D) as follows. The background knowledge B
contains a set of axioms which state that < is a linear order,
i.e.,
(y < y
(Equality between tuples
The set D contains the following open defaults.
For each predicate P from S and for <:
y < y
:(y < y
rules for the associated predicates:
:(y < y
derivation of A (i.e., checking if (9x)(8y) (x; y) is true):
Let W be any database instance, and denote by  the
default theory QDQL +W .
It is easy to see that  has only consistent extensions.
(Formally, this can be easily proved by Lemma 1.)
We claim that the atom A belongs to an extension of
if and only if W
\(". Assume that W That
is,
for some valuation S 0 of the S predicates. Dene a set
F of formulas as follows. Let < 0 be an arbitrary linear
order of all y-tuples, and let F 0 be the associated
extensions for F , S, and L. In what follows, let a; a
denote tuples of appropriate arities over the domain. The
set
contains the following formulas:
is an extension of  such that
To show this, we rst note that E is consistent.
Indeed, extend the valuations given by W ,
assigning \true" to A, by letting Z 0 be the set of
all possible tuples, and by letting the remaining predicates
T have an arbitrary extension. This valuation satises F .
Moreover, E is an extension of . This can be easily
shown from the denition of extension: we obtain that
Hence,
is an extension
of .
To prove the claim, it remains to show that A 2 E. Since
suces to show that A is true in every
valuation that satises F . Consider an arbitrary valuation
that satises F . Let T 0 be the valuation of T and Z 0 the
valuation of Z. Then, from (5) we have that
Let a be an arbitrary tuple such that
By nite induction on < 0 , we show that (a; b) 2 Z 0 , for all
b.
(Basis). Let b 0 be the rst tuple of < 0 . Since b 0 2 F 0 , we
have (a; b 0
true. Thus, (a; b 0
(Induction). Assume the statement holds for tuple b. We
show that it holds also for b 0 , where (b; b 0 We have
that by the induction
hypothesis, (a; b) 2 Z 0 , and by (6), (a; b 0 ) is true. Hence,
it follows that Z(a; b 0 ) is true, i.e., (a; b 0 This shows
the induction case.
in particular we have that
is the last tuple in < 0 , i.e., b 1 2 L 0 .
However, we have that Z(a; b 1
that A has value \true" in the valuation. Consequently, we
have shown that A 2 E.
This concludes the \(" part of the proof.
be an extension of  such that A 2 E. Notice
that E is consistent.
denes a valuation S 0 for the S predicates, i.e., for
each P from S, we have P (a) 2 E or :P (a) 2 E for each
tuple a. This follows since the defaults : P (a)
:P (a)
are in INST (D). Moreover, E denes a valuation < 0 for
< such that < 0 satises the axioms for a linear order of all
tuples of the arity of y.
Furthermore, it follows from the instantiated default
rules for the predicates associated to < that E denes a
total valuation of F , S, and L, and that :F (a)
is not the rst tuple in < 0 , that :S(a; a 0
the successor of a 0 in < 0 , and that :L(a) 2 E i a is not
the last tuple in < 0 .
We claim that
To prove this, assume this is false. Hence, there exists a
valuation T 0 of T such that
We extend this valuation to a model of E that has A false.
Let for each tuple a for x be m(a) the rst tuple b for y
in < 0 such that W;S b). Notice that m(a)
exists for each a.
Dene a valuation Z 0 for Z by Z
m(a) g; and assign A the value \false".
This valuation of the predicates denes a model of E.
To prove this, it is by Lemma 1 sucient to show that the
valuation is a model of
G;
GD(E;)g. Since COMP (W )[
are left to show that G
is satised. It is easy to see that every
in which Z does
not occur is satised. Consider any remaining
(i.e., a
conclusion of a default for deriving A). Then, we have
three cases:
(a)
is is the rst tuple in
the formula is certainly satised.
(b)
is is the
successor of b in < 0 . By considering the three cases (1)
it is readily checked from the denition of Z 0 that the
formula is satised.
(c)
is A. Then, b is the last tuple in < 0 . By
denition of Z 0 , we have that Z(a; b) is false; hence,
since A is false, the formula is satised.
Thus, the valuation satises COMP (W
and hence also E. Since A is false in this model of E, we
have that
2 E. This is a contradiction, however. Hence,
claim (7) is proved. Now claim (7) means
This concludes the \)" part of the proof.
Remark: All defaults in D can be made prerequisite-free
by deleting the prerequisite  and rewriting the conclusion
as
. 2
Theorem 2 The data complexity of Boolean DQL is  p
complete.
PROOF From Theorem 1, we have that every Boolean
DQL query denes a  p
database property; this gives the
membership part. For the hardness part, we notice that
for every SO 98 sentence as in (3), an equivalent sentence
CADOLI, EITER AND GOTTLOB: DEFAULT LOGIC AS A QUERY LANGUAGE 113
of the form (4) in the proof of Theorem 1 can be constructed
(cf. Appendix), for which the equivalent default
query QDQL can be easily constructed (even in polynomial
time). Consequently, the problem of deciding whether a
xed sentence (3) is valid in a given database instance W ,
which is  p
2 -hard, is transformable to a Boolean DQL query
in polynomial time. 2
Theorem 3 A database query is  p
-recognizable if and
only if it is denable as a DQL I/O query.
PROOF \(": Deciding whether a tuple t belongs to a
certain output relation S i 2 S transforms in polynomial
time into credulous reasoning in a propositional default
theory (cf. Proof of Theorem 1). Hence,  p
-recognizability
follows.
be a  p
-recognizable query. We
dene from q a database property P on the relation scheme
in the following way: For each instance W of
only if S i jW  S i jq(WR ) for each
denotes the restriction of W to the
relations of R. That is, P(W ) is true i each tuple t that
belongs to S i jW is computed by q on the instance WR of
R.
Notice that P is in fact a database property. Moreover, it
is easy to see that P is  p
-recognizable. Consequently, by
Theorem 1, P can be expressed by a Boolean DQL query
DQL . Without loss of generality, we may assume that
DQL has the form of the query QDQL constructed in the
proof of Theorem 1; notice that the database relations of
DQL are R [ S. From Q P
DQL we construct a DQL I/O
query Q q
DQL as follows. The background knowledge is the
one of Q P
DQL , i.e. B, and the open defaults D 0 are dened
by
The database relations are given by R and the output relations
by S.
The rules :S i (x)
enforce a total valuation of
the S i predicates. Intuitively, these defaults simulate all
extensions of an instance W of R to an instance W 0 of
which is then processed by the defaults of query
DQL . The default : :A
cutts extensions in
which the atom A is not contained; hence, only default
extensions EW 0 for W 0 are left such that P(W 0 ) is true.
The query Q q
DQL collects under the brave semantics all
tuples t for S i such that S i (t) belongs to some default
extension EW 0 ; from the denition of P , this means that
exactly those tuples t are collected that q computes for S i
on the database W . In other words, Q q
DQL computes on
database W the same as q, i.e., Q q
DQL denes q in DQL.
More formally, we show the following. Let W be an
instance of R, and dene the set of formulas G by
where F is as in the proof of Theorem 1. Let W 0 be the
extension of W to R
is an extension of Q P
it is easy to see from the denition of extension that E is
also an extension of Q q
DQL +W . It follows that
To show that Q q
DQL and q compute the same on W , it
thus remains to show that
Let E be an extension of Q q
. Notice that A 2
Then, it is easy to see that E is also an extension of
is the extension of W to R 0 such
that Consequently, P(W 0 ) is true.
This means that
It follows that S i jQ q
Thus we have shown that Q q
DQL denes q, which concludes
the \)" part of the proof. This proves the theorem.Theorem 4 The Boolean normal DQL queries precisely
capture the class  p
.
PROOF Reconsider the Boolean DQL query QDQL constructed
in the proof of Theorem 1. Let Q 0
DQL be the
DQL query resulting from QDQL by replacing (B; D) with
are obtained from D and B, re-
spectively, by removing every non-normal default  :
for
the associated predicates and by adding  !
to B.
Notice that each  is a Boolean formula built on atoms
from < ; since the defaults : y<y 0
y<y
to both D and D 0 , it is easy to see that the default theories
have the same extensions for
every instance W , and thus express the same query.
Now let D 00 be the result of replacing in D 0 every non-normal
default, i.e. rule :
for deriving A, by
, and
DQL be the query obtained from Q 0
DQL by replacing
D 0 with D 00 . Notice that Q 00
DQL is a normal DQL query.
One can easily show that, for every database instance W
of R, a set E is an extension of Q 00
only if
E is an extension of Q
DQL +W .
Hence, it follows that Q 00
has an extension E
such that A 2 E i W y). The
result follows. 2
Theorem 5 The normal I/O DQL queries precisely capture
the class of  p
-recognizable queries.
PROOF We show this by a modication of the construction
in the proof of Theorem 3.
Without loss of generality, we assume that the Boolean
DQL query Q P
DQL for expressing P has the form of the
query Q 00
DQL in Theorem 4 (instead of QDQL in Theorem
1). Then, by analogous lines as in the proof Theorem
3, we obtain that the I/O query Q q
DQL constructed
from Q P
DQL by adding the defaults :S i (x)
? expresses the query q.
Now let Q be the query obtained from Q q
DQL by replacing
each occurrence of every S i 2 S by S 0
new
predicate of the same arity, and by replacing the default
? with the defaults
Let W be an instance of R. Notice that A belongs to
every extension of Q q
and that an atom S i (t)
belongs to an extension E of Q belongs to
E. Thus, it is easy to see that a set E is an extension of
DQL +W only if
is an extension of Q On the other hand, if E is an
extension of Q+W such that A 2 E, then
is an extension of Q q
Thus, it follows that Q
computes on W the same as Q q
DQL .
Consequently, Q and Q q
DQL represent the same query.
Since Q is a normal DQL I/O query, the result follows.
Acknowledgements

The authors are grateful to Torsten Schaub for interesting
comments on semantics of DQL. They also appreciate
the very useful comments of the anonymous reviewers,
which helped to improve the reading of the paper. The
rst author has been partially supported by ESPRIT Basic
Research Action 6810 COMPULOG II and by Progetto Finalizzato
Informatica of the CNR (Italian Research Coun-
cil). The second and third authors have been partially
supported by the Christian Doppler Laboratory for Expert
Systems.



--R




















Readings in Model-Based Diagnosis
Abductive Inference Models for Diagnostic Problem Solving




Principles of Database and Knowledge Base Sys- tems
Foundations of Databases












Computational Complexity

Ellis Horwood Lim- ited








--TR

--CTR
Thomas Eiter , Axel Polleres, Towards automated integration of guess and check programs in answer set programming: a meta-interpreter and applications, Theory and Practice of Logic Programming, v.6 n.1-2, p.23-60, January 2006
Binding Propagation Techniques for the Optimization of Bound Disjunctive Queries, IEEE Transactions on Knowledge and Data Engineering, v.15 n.2, p.368-385, February
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
Thomas Eiter , Wolfgang Faber , Nicola Leone , Gerald Pfeifer, Declarative problem-solving using the DLV system, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2000
Cristinel Mateis, Quantitative Disjunctive Logic Programming: semantics and computation, AI Communications, v.13 n.4, p.225-248, December 2000
Victor W. Marek , Jeffrey B. Remmel, On the expressibility of stable logic programming, Theory and Practice of Logic Programming, v.3 n.4, p.551-567, 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
Gianluigi Greco , Sergio Greco , Ester Zumpano, A Logical Framework for Querying and Repairing Inconsistent Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1389-1408, November
Logic programming and knowledge representation-the A-prolog perspective, Artificial Intelligence, v.138 n.1-2, p.3-38, June 2002
Thomas Eiter , Georg Gottlob , Heikki Mannila, Disjunctive datalog, ACM Transactions on Database Systems (TODS), v.22 n.3, p.364-418, Sept. 1997
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
expressive power;default logic;relational databases;query languages;nonmonotonic reasoning