On the complexity of data disjunctions.
We study the complexity of data disjunctions in disjunctive deductive databases (DDDBs). A data disjunction is a disjunctive ground clause R(c-1pt1)...R(ck),K  2, which is derived from the database such that all atoms in the clause involve the same predicate R. We consider the complexity of deciding existence and uniqueness of a minimal data disjunction, as well as actually computing one, both for propositional (data) and nonground (program) complexity of the database. Our results extend and complement previous results on the complexity of disjunctive databases, and provide newly developed tools for the analysis of the complexity of function computation.
Introduction
During the past decades, a lot of research has been spent to overcome the limitations of conventional
relational database systems. The field of deductive databases, which has emerged from logic programming
[29], uses logic as a tool for representing and querying information from databases. Numerous
logical query languages, which extend Horn clause programming for dealing with various aspects such as
incomplete or indefinite information, have been proposed to date, cf. [1, 33].
In particular, the use of disjunction in rule heads for expressing indefinite information was proposed
in Minker's seminal paper [32], which started interest in disjunctive logic programming [30, 10]. For
example, the rule
lives in(x; US) - lives in(x; canada) - lives in(x; mexico) / lives in(x; n america) (1)
informally states that a person living in north America lives in one of the three countries there. The
semantical and computational aspects of disjunctive logic programming, and in particular, disjunctive
deductive databases, have been investigated in many papers (see [33] for an overview).
The results of this paper have been presented at the international workshop "Colloquium Logicum: Complexity," Vienna,
October 9-10, 1998. This work was partially supported by the Austrian Science Fund Project N Z29-INF, and by the British
Council-Austria ARC Programme for collaborative research (Oracle Computations within Descriptive Complexity Theory).
In this paper, we are interested in a restricted type of disjunction, which has been previously considered
e.g. in [6, 5, 12, 19, 15]. A data disjunction [19] is a ground clause R(-c 1
which all atoms are different and involve the same predicate R. For example, the head of the rule (1) for
Joe, is a data disjunction, as well as the disjunctive fact
loves(bill; monica) - loves(bill; hillary):
A data disjunction expresses indefinite information about the truth of a predicate on a set of arguments; in
database terminology, it expresses a null value on this predicate, whose range is given by the arguments
of its atoms. In the context of deductive databases, null values of this form in the extensional
database and their complexity have been considered e.g. in [20], and in many other papers.
If, in the above example, the fact lives in(joe; n america) is known, then the data disjunction
lives in(joe; US) - lives in(joe; canada) - lives in(joe; mexico)
can be derived from rule (1). If a clause C is entailed from a database, then also any clause C 0 subsumed
by C is entailed. For example, the clause C - lives in(joe; usbekistan) is entailed by virtue of C as
well. We thus adopt the natural condition that a data disjunction C must be minimal, i.e., no proper
subclause of C is entailed.
The question we address here is the complexity of data disjunctions in a disjunctive deductive database
(DDDB).

Table

1 summarizes the problems studied in this paper (see Section 3 for precise definitions),
and the main complexity results obtained. They complement previous results on reasoning from DDDBs.
Deciding whether an arbitrary disjunction, rather than a data disjunction, follows from a DDDB has \Pi Pdata and propositional complexity, and exponentially higher expression and combined complexity [14];
various syntactic restrictions lower the complexity to coNP or even polynomial time [9]. On the other
hand, evaluating a conjunctive query over a disjunctive extensional database is coNP-complete [20], and
hence deciding entailment of a single ground atom a has coNP data and propositional complexity. Thus,
data disjunctions have intermediate complexity between arbitrary clauses and single atoms.
Observe that Table 1 contains also results on actually computing a data disjunction (assuming at most
one exists). While all the results in this table could be derived in the standard way, i.e., by proving
membership in class C and reducing a chosen C-hard problem to the problem in question, we pursue here
an "engineering" perspective of complexity analysis in databases, proposed e.g. in [18], which utilizes
tools from descriptive and succinct complexity theory and exploits properties of the deductive database
semantics. By means of these tools, hardness results can be derived at an abstracted level of consideration,
without the need for choosing a fixed C-hard problem. Such tools (in particular, complexity upgrading)
have been developed for decision problems, but are not available for function problems. We overcome
this by generalizing the tools for propositional problems in a suitable way.
Thus, the main contributions of this paper can be summarized as follows. Firstly, we determine the
complexity of data disjunctions. We obtain natural and simple logical inference problems complete for
the class \Theta P
2 of the refined polynomial hierarchy [45], and, in their computational variants, complete
problems for the function classes FP NP
k and FL NP
log [log] and their exponential analogs. Secondly, we
provide upgrading techniques for determining the complexity of function computations. They generalize
available tools for decisional problems and may be fruitfully applied in other contexts as well.
The rest of this paper is organized as follows. Section 2 states preliminaries, and Section 3 formalizes
the problems. In Section 4, the decision problems are considered, while Section 5 is devoted to computing
Data Disjunction
Input: A disjunctive deductive database a collection of (possibly disjunctive) ground
facts, and - are the inference rules, plus a distinguished relation symbol R.
propositional complexity data complexity expression complexity combined complexity
9DD: does DB have a data disjunction on R?
\Theta P
PSpace NP PSpace NP
9!DD: does DB have a unique data disjunction on R?
\Theta P
PSpace NP PSpace NP
-DD: Computation of the unique data disjunction on R.
FPSpace NP FPSpace NP
k -DD: Computation of the unique data disjunction on R, if it has at most k disjuncts (k constant).
log [log] FL NP
log [log] FPSpace NP [pol] FPSpace NP [pol]

Table

1: Complexity of Data Disjunctions.
data disjunctions. Logical characterizations of function computations are given through a generalization
of the Stewart Normal Form (SNF) [38, 39, 17], which has been first used to characterize the class \Theta P
.
For deriving the expression and combined complexity of function computations, upgrading results are
developed in Section 6. The final Section 7 applies the results to the area of closed-world reasoning and
gives some conclusions.
Preliminaries
2.1 Deductive databases
For a background on disjunctive deductive databases, we refer to [30].
Syntax. A finite relational language is a tuple where the R i are relation
symbols (also called predicate symbols) with associated arities a , and the c i are constant sym-
bols. An atom is a formula of the form R i (-v), where - v is a tuple of first order variables and constant
symbols.
A disjunctive datalog rule is a clause of the form
over a finite relational language, where the a i 's are atoms forming the head of the clause, and the b j 's are
atoms or inequalities of the form u (where u and v are variables or constants) forming the body of
the clause.
A disjunctive deductive program (short program) is a finite collection of disjunctive datalog rules; it is
ground, if no variables occur in the rules.
If a predicate symbol occurs only in rule bodies, it is called an input predicate, otherwise it is called a
derived predicate.
A disjunctive deductive program with input negation is a program where input predicates are allowed
to appear negated.
A ground fact is a clause of the form
a 1
where a 1 is a variable-free atom; a disjunctive ground fact is a clause of the form
a 1 - a n
where the a i 's are variable-free atoms.
A disjunctive deductive database (DDDB) is a tuple E) where - is a program, and E is a
finite set of disjunctive ground facts. Here, E represents the input database, also called the extensional
part, and - are inference rules, called the intensional part of the database DB.
Remark: Note that -; E, and - [ E are all disjunctive deductive programs, i.e., ground facts can be
included into the programs, and in fact we shall do this for defining the semantics. However, for methodological
and complexity issues, it is important to distinguish the input data from the inference rules. For
example, the complexity of evaluating DB is exponentially lower when - is fixed. In section 3, we shall
define data and query complexity to give a formal meaning to this intuition.
Semantics. The semantics of DDDBs has been defined in terms of their minimal models [32, 30]. For a
E), we denote by HU DB its Herbrand universe, i.e., the set of all constants occurring in
DB. The Herbrand base HB DB (resp., disjunctive Herbrand base DHB DB ) is the set of all ground atoms
disjunctive ground facts) of predicates in DB over HU DB . The ground instantiation of a program -
over a set of constants C is denoted by ground(-; C); the ground instance of DB, denoted ground(DB),
is ground(-; HB DB
An (Herbrand) interpretation of DB is a subset H ' HB DB . An interpretation H of DB is a model of
DB, if it satisfies each rule in ground(DB) in the standard sense. A model H of DB is minimal, if it does
not contain any other model of DB properly; by MM(DB) we denote the set of all minimal models of
DB. We write DB is true in every M 2 MM(DB), and say that ' is entailed from
DB.
Example 2.1 Let is the rule q(x) / p(x) and E contains the single disjunctive
fact are among the models of DB; M is
while M is not. The minimal models of DB are fq(b)gg.
Remark. It is easy to see [32] that for each positive clause C , DB only iff DB
where is satisfaction in all models of DB. We will repeatedly use this fact.
The set of minimal models of DB has been characterized in terms of a unique least model-state MS
(see [30]), i.e., a subset of DHB DB , which can be computed by least fixpoint iteration of an operator T S
generalizing the standard T P operator of logic programming [29]. In general, the computation of MS
takes exponential space and time, even if the program - of DB is fixed.
2.1.1 Negation
Introducing negation in disjunctive deductive databases is not straightforward, and gave rise to different
semantics, cf. [33]. We restrict here to input negation, i.e., the use of negated atoms :R( - t) in rule bodies
where R is an extensional predicate, and adopt a closed-world assumption (CWA) on models imposing the
following condition: any accepted model M of E), restricted to the extensional part, must be a
minimal model of E. Unless stated otherwise, a model of a DDDB must satisfy this kind of closed-world
assumption.
Observe that this condition is satisfied by each M 2 MM(DB) if - is negation-free; furthermore, if E
contains no disjunctive facts, then :R(-c) is true in every M 2 MM(DB) iff
As for complexity, it is easy to see that checking whether the restriction of M to its extensional part is
a minimal model of E is possible in polynomial time. Hence, the complexity of model checking and of
deciding DB does not increase through the CWA on models. Furthermore, if E is restricted to
disjunction-free ground facts, input negation can be eliminated in computation as follows.
Definition 2.1 Let - be a finite relational language, and let -
the class of all finite - 0 structures A where for all relations R in - , R 0 A is the complement of R A .
Proposition 2.1 Extending a given -structure to its corresponding NEG - 0 structure and replacing literals
in a program - by R 0 possible in LOGSPACE.
In the derivation of hardness results, we shall consider DDDBs E) using input negation but
where E is disjunction-free. Hence, all hardness results in this paper hold for DDDBs without negation
and non-disjunctive (i.e., relational) facts as well.
2.2 Complexity
In this section, we introduce some of the more specific complexity classes and notions employed in
the paper; we assume however some familiarity with basic notions of complexity theory such as oracle
computations, NP, PSpace, L etc.
The class \Theta P
2 contains the languages which are polynomial-time truth-table reducible to sets in NP. It
has a wide range of different characterizations [45, 21]. In particular, the following classes coincide with
\Theta P
polynomial time computation with k rounds of parallel queries to an NP oracle [27].
log : polynomial time computation where the number of queries to an NP oracle is at most logarithmic
in the input size [25].
log : logarithmic space computation where the number of queries to an NP oracle is at most logarithmic
in the input size [26]. 1
1 Observe that the space for the oracle tape is not bounded. Unbounded oracle space is also assumed for all other classes
using an oracle in this paper.
III FL NP
log
log
IV
II
log [log]
log [log]
QUERY
I

Figure

1: Function classes corresponding to \Theta P
.
For an overview of different characterizations and their history, consult [45, 21]. It is shown in [21, 4,
37, 40] that this picture changes when we turn to function computation. The above mentioned list gives
rise to at most three presumably different complexity classes FP NP
log , and FL NP
log , which are shown
in

Figure

1. Here, for any function class FC, we denote by FC[log] the restriction of FC to functions with
logarithmic output size. Moreover, k[k] denotes k rounds of parallel queries, where k is a constant.
The relationships between the complexity classes in Figure 1 have been attracting quite some research
efforts, which led to a number of interesting results.
ffl II=III is equivalent to
ffl I=II is equivalent to the property that SAT is O(log n) approximable. This was shown in [2],
after I)II was proved in [8]. (Here f -approximability of a set A means that there is a function
g such that for all x holds that g(x
ffl Furthermore, if I=II, then (1SAT,SAT), i.e., promise SAT, is in P [4, 40], FewP=P, NP=R [37],
n), and NP ' DTIME(2 n O(1= log log n)
To compare the complexity of functions, and to obtain a notion of completeness in function classes, we
use Krentel's notion of metric reducibility [25]:
Definition 2.2 A function f is metric reducible (- mr -reducible) to a function g (in symbols, f - mr g),
if there is a pair of polynomial-time computable functions h 1 and h 2 such that for every x,
Proviso 1. Let C be a complexity class. Unless stated otherwise, we use the following convention:
C-completeness is defined with respect to LOGSPACE reductions, if C is a class of decision problems,
and with respect to metric reductions, if C is a class of function problems.
Some complete problems for function classes are shown in Figure 1. The canonical FP NP
-complete
problem is QUERY, i.e., computing the string -(I 1
SUPREMUM is computing, given a Boolean formula F string
there is a satisfying assignment to the variables of F such that x
SIZE is computing the size of a maximum clique in a given graph. Note that this problem is also complete
for FP NP
log . All these problems, turned into proper decision problems, are \Theta P
2 -complete. In particular,
deciding whether the maximum clique size in a graph is even and deciding whether the answer string to
QUERY contains an even number of 1's are \Theta P
-complete, cf. [45].
2.3 Queries and descriptive complexity
Definition 2.3 Let - be a finite relational language, and let fRg be a language containing a single
relational symbol R. A query Q is a function which maps -structures to ffi-structures over the same
domain, s.t. Q(A) and Q(B) are isomorphic, if A and B are isomorphic. If R is nullary, then Q is a
Boolean query.
A Boolean query Q is regarded as a mapping from -structures to f0; 1g s.t. for isomorphic A; B,
Remarks. (1) If we disregard nonelementary queries, we can identify queries with higher order definable
relations. (2) Note that "query" is also used for oracle calls. (3) Since queries are functions, we shall
also write them as sets of pairs (A; Q(A)).
Definition 2.4 Let - be a finite relational language with a distinguished binary relation succ, and two
constant symbols min; max. Then SUCC - is the set of all finite structures A with at least two distinct
elements where succ A is a successor relation on jAj, and min A ; max A are the first and last element wrt
the successor relation, respectively.
Note that queries are not defined over SUCC - , but over arbitrary -structures; this is called "order
independence" of queries. Many query languages however seem to require a built-in order for capturing
complexity classes, i.e., capturing requires that the -structures are extended by a contingent ordering to
structures from SUCC - . Thus, when we write on ordered structures/databases, or on SUCC - , we mean
that the queries are computed on -structures which are extended to SUCC - structures.
The following theorems provide examples of this phenomenon.
Definition 2.5 A SNF formula (Stewart Normal Form) is a second-order formula of the form
where ff and fi are \Pi 1
1 second order formulas with equality having the free variables -
y. An SNF sentence is
a SNF formula without free variables. The Skolem functions for the variables -
x are called SNF witnesses.
Lemma 2.2 ([38, 39, 17]) Every \Theta P
2 -computable property on SUCC - is expressible as
where oe is a SNF sentence.
This result, in equivalent terms of first-order logic with NP-computable generalized quantifiers, is contained
for particular cases of generalized quantifiers in [38, 39], and was given for broad classes of generalized
quantifiers in [17].
On a structure A, a formula '(-x) with free variables -
x defines the relation ' A given by f-c j A '(-c)g.
A program - defines a relation R on A, if (-; on A. In particular, if
R is nullary, ' (resp., -) defines a property on A.
Lemma 2.3 (immediate from [13, 14]) Every \Pi 1
1 definable property ' on SUCC - is expressible by a
disjunctive datalog program - ' using input negation.
Remark: Note that Lemma 2.3 does not require inequalities in rule bodies, since inequality is definable
in the presence of order, cf. [14].
3 Data Disjunctions
Definition 3.1 Given a DDDB DB, a disjunctive ground fact R-c 1 - R-c n , n - 2, is called a data
disjunction, if
1. DB
2. for all S ae
In this case, we say that DB has a data disjunction on R.
A data disjunction can be seen as a kind of null value in a data base.
Example 3.1 The DDDB E)
has a data disjunction Pa - P b - P c.
Definition 3.2 Given a DDDB DB, the maximal disjunction on R (in symbols, md(DB;R)) is the disjunctive
ground fact
R-c:
Lemma 3.1 DB has a data disjunction on R if and only if DB
Proof. If DB has a data disjunction ffi on R, then no atom R-c of ffi is implied by DB. Therefore, ffi is a
subclause of md(DB;R), and thus DB md(DB;R). On the other hand, if DB
clearly md(DB;R) is not empty. Either md(DB;R) is a data disjunction itself, or atoms of md(DB;R)
can be removed until a minimal disjunction ffi   is reached such that DB by definition no
atomic subformula of md(DB;R) is implied by DB, ffi   must contain at least two different atoms. J
In measuring the complexity of data disjunctions, we distinguish several cases following Vardi's [41]
distinction between data complexity, expression complexity (alias program complexity), and combined
complexity.
Definition 3.3 The problems 9DD, 9!DD, -DD, and k -DD are defined as follows:
Instance: A DDDB E), and a relation symbol R.
Query: 9DD: Does DB have a data disjunction on R ?
9!DD: Does DB have a unique data disjunction on R ?
-DD: Compute the unique data disjunction on R if it exists, and # otherwise.
k -DD: Compute the unique data disjunction on R, if it exists and has at most k disjuncts,
and # otherwise.
Observe that 9DD, called ignorance test in [5], has been used in [5, 6] to discriminate the expressive
power of different query languages based on nonmonotonic logics over sets of disjunctive ground facts.
Problem 9!DD corresponds to the unique satisfiability problem. The uniqueness variant of a problem has
often different complexity.
Definition 3.4 Let \Pi be one of 9DD, 9!DD, -DD, or k -DD.
ffl The data complexity of \Pi is the complexity of \Pi with parameter - fixed.
ffl The expression complexity of \Pi is the complexity of \Pi with parameter E fixed.
ffl The propositional complexity of \Pi is the complexity of \Pi where - is ground.
ffl The (unconstrained) complexity of \Pi is also called the combined complexity of \Pi.
Problem \Pi has combined (or propositional) complexity C , if \Pi is C-complete with respect to combined
complexity. \Pi has data (or expression) complexity C , if \Pi is in C with respect to
data (resp. expression) complexity for all choices of the parameter, and \Pi is C-complete with respect to
data (resp. expression) complexity for a particular choice of the parameter.
4 Existence of Data Disjunctions
Theorem 4.1 Let Q be a fixed Boolean query. Over ordered databases, the following are equivalent:
1. Q is \Theta P
-computable.
2. Q is definable by a SNF sentence.
3. There exist a program - and a relation symbol R s.t. (-; A) has a data disjunction over R iff
A
4. Q is equivalent to a SNF sentence whose SNF witnesses are uniquely defined.
5. There exist a program - and a relation symbol R s.t. (-; A) has a unique data disjunction over R
iff A
Proof. The equivalence of 1: and 2: is stated in [17]. A close inspection of the proof in [17] shows
that in fact 1: is also equivalent to 4:
3: ! 1:: By Lemma 3.1, the following algorithm determines if DB has a data disjunction on R:
Algorithm DDExistence(DB; R)
1: M := ;;
2: for all R-c 2 HBDB
3: if not (DB
4: ' :=
5: if DB return true else return false;
Note that in line 4, ' equals md(DB;R). The algorithm DDExistence works in polynomial time and
makes two rounds of parallel queries to an NP oracle, and thus the problem is in P NP
.
5: ! 1:: The following algorithm DDUniqueness is an extension of DDExistence.
Algorithm DDUniqueness(DB; R)
02: for all R-c 2 HBDB
03: if not (DB
05: if not (DB
07: for all R-c 2 M
08: if not (DB
10: if DB
Note that lines 1 to 4 coincide with DDExistence. On line 5, the algorithm terminates if no data
disjunction exists. Otherwise, all possible data disjunctions are subclauses of
to 9 construct a subclause /; it contains all those literals R-c of md(DB;R) in N which cannot be removed
from md(DB;R) without destroying the data disjunction, i.e., it contains those literals which necessarily
appear in every data disjunction. Thus, if ' is a data disjunction, it is the unique one. On the other hand,
if a unique data disjunction exists, it is by construction equal to '.
Like the algorithm DDExistence, this algorithm also works in polynomial time making a constant
number of rounds of parallel queries to an NP oracle. Hence, the problem is in \Theta P
.
2: ! 3:: Let ' be a formula of the form
By Lemma 2.3 there exist programs -A and -B containing predicate symbols A and B such that for all
Let - be the program -A [ -B with the additional rules
Observe that P does not occur in -A [ -B , and thus, by well-known modularity properties [14, Section
5], the minimal models of - on A are obtained by extending the minimal models of -A [ -B on A.
It is easy to see that has a data disjunction on P if and only if there exists a tuple - c on A
such that A indeed computes property ' on SUCC - .
From the equivalence of 2: and 4:, it follows that the data disjunction of program - in the
proof of 2: ! 3: is unique. J
Corollary 4.2 The propositional and data complexity of 9DD and 9!DD are in \Theta P
. The expression and
combined complexity of 9DD and 9!DD are in PSpace NP .
Proof. It remains to consider expression and combined complexity. When the program is not fixed,
the size of HB DB is single exponential in the input, and thus the algorithm DDExistence takes exponentially
more steps. Thus, the problem is in EXPTIME NP
k , which coincides with PSpace NP [18]. J
Since \Theta P
2 has complete problems, we obtain from Theorem 4.1 the following.
Corollary 4.3 There is a program - for which 9DD and 9!DD are \Theta P
Hence, we obtain the announced result.
Theorem 4.4 The data complexity and propositional complexity of 9DD and 9!DD is \Theta P
.
Note that the propositional complexity of 9DD has been stated in [12]. The hardness proof there,
given by a standard reduction, is far more involved; this indicates the elegance of using the descriptional
complexity approach.
Since the data complexity of a query language is uniquely determined by its expressive power, two
languages with the same expressive power will always have the same data complexity. Hence, data
complexity is a property of semantics. Expression and combined complexity, however, depend on the
syntax of the language. Therefore, it is in general not possible to determine the expression complexity of
a query language L from its expressive power. Indeed, both the syntax and the semantics of L impact on its
expression complexity. In spite of these principal obstacles, the typical behavior of expression complexity
was often found to respect the following pattern: If L captures C , then the expression complexity of L is
hard for a complexity class exponentially harder than C .
The main result of [18] shows that all query languages satisfying simple closure properties indeed
match the above observation. Suppose that in a database, domain elements are replaced by tuples of
domain elements. This operation is natural when a database is redesigned; for instance, entries like "John
Smith" in a database A can be replaced by tuples ("John","Smith") in a database B. It is natural to
expect that a query QA over A can be easily rewritten into an equivalent query Q B over B. We call Q B a
vectorized variant of QA . This is the essence of the first closure property:
Vector Closure: A query language is uniformly vector closed, if the vectorized variants of query expressions
can be computed in LOGSPACE.
The second closure property is similar. Suppose again that a database A is replaced by a database B
in such a way that all relations of A can be defined by views which use only unions and intersections
of relations in B. Then, it is again natural to expect that a query QA over A can be translated into an
equivalent query Q B over B. In this case, we call Q B an interpretational variant of QA .
Interpretation Closure: A query language is uniformly interpretation closed, if the interpretational variants
of queries can be computed from the database schemata in LOGSPACE.
In conclusion, we have the following closure condition (see [18] for a formal definition).
Definition 4.1 A query language is uniformly closed, if it is uniformly vector closed and uniformly interpretation
closed.
Lemma 4.5 ([18]) The language of DDDBs is uniformly closed.
Combining Corollary 4.2 and the following Proposition 4.6, we obtain the expression and combined
complexity of 9DD and 9!DD.
Proposition 4.6 ([18]) If a language is uniformly closed, and expresses all \Theta P
2 properties of SUCC - ,
then its expression complexity and combined complexity are at least PSpace NP .
Theorem 4.7 The expression complexity and the combined complexity of 9DD and 9!DD is PSpace NP .
5 Computation of Data Disjunctions
5.1 Data complexity and propositional complexity
Theorem 5.1 Let Q be a fixed query. Then, over ordered databases the following are equivalent.
1. Q is FP NP
computable.
2. Q is definable by a SNF formula.
3. There exist a program - and a relation symbol R s.t. Q(A) is polynomial time computable from
the unique data disjunction of (A; -) on R.
Proof. 1: ! 2:: The problem of deciding whether a given tuple - c on A fulfills -
easily
seen to be in \Theta P
2 . Thus, Lemma 2.2 implies there is a SNF sentence oe such that A; - c
(provide -
c through a designated singleton relation R - c , and use 9-yR - c (-y) to access -
c). Hence, there is an
2: ! 3:: Similarly as in the proof of Theorem 4.1, let ' be the SNF formula
having the free variables - y. By Lemma 2.3 there exist programs -A and -B containing predicate symbols
A and B such that for all A(-c; -
d) 2 HB -A and B(-c; -
d) 2 HB -B
d) iff A
d) and (A; -B )
d) iff A
We have to construct a program - whose unique data disjunction on input A over relation R contains the
information about all tuples in ' A . To this end, consider the program in Figure 2. Let a be the arity of A
and B there. Then the new relation symbols T and S also have arity a, and R has arity a+2. The program

Figure

2: DDDB program for FP NP
queries.
requires that a successor relation over tuples is available. The lexicographical successor relation can be
easily defined using datalog rules. Lines 1 to 3 enforce that S(-c) holds for at least one - c. Consequently,
the unique data disjunction on - c is the positive clause containing all possible S(-c) on A.
Consider lines 1 to 4 now. If the program contained only these rules, then line 4 would enforce that the
unique data disjunction on R would be the clause
d
d; max; max):
Lines 5 and 6, however, remove certain literals from this clause. In particular, it holds that A
d) iff
there is a - c on A such that A
d) iff there is a - c on A such that the (unique) data disjunction
of (-; A) on R contains the clause R(-c; -
d; min; min)-R(-c; -
d; min; max) but not R(-c; -
d; max; max).
Therefore, ' A is polynomial time computable from the unique data disjunction on R.
3: ! 1:: The algorithm DDUniqueness in the proof of Theorem 4.1 computes the unique data disjunction
in its variable /, provided it exists. It is easily modified to output # in the other case. J
The data and propositional complexity of -DD is an easy corollary to this result.
Corollary 5.2 Problem -DD has data complexity and propositional complexity FP NP
Definition 5.1 A domain element query (DEQ) is a query whose answer relation is a singleton, i.e., a
query Q s.t. for all A it holds that
Theorem 5.3 Let Q be a fixed DEQ. Then, over ordered databases the following are equivalent:
1. Q is FP NP
2. Q(A) is a tuple of SNF witnesses to a SNF sentence.
3. There exist a program - and a relation symbol R s.t. Q(A) is definable as a projection of the unique
data disjunction over R, where the data disjunction contains at most two atoms.
4. There exist a program - and a relation symbol R s.t. Q(A) is polynomial time computable from the
unique data disjunction over R where the data disjunction contains at most two atoms.
Proof. 1: ! 2:: For constant -
c, the problem of deciding whether - c 2 -(A) is easily seen to be in
\Theta P
. Thus, there is a SNF formula '(-x) having the free variables -
x for the constants s.t. A; - c
-(A). By Theorem 4.1 we may w.l.o.g. suppose that the SNF witnesses in ' are unique.
2: ! 3:: Let ' be a SNF sentence
which has unique SNF witnesses. Then, the program for ' in part 2: ! 3: of the proof of Theorem 4.1
has a unique data disjunction of the form P (-c; -
d; max). From this data disjunction, the
projection on the -
d tuple yields the desired result.
3:
M be the polynomial time Turing Machine which computes the answer from the unique
data disjunction. Then, we use the algorithm DDUniqueness in the proof of Theorem 4.1 which computes
the unique data disjunction in its variable /. It remains to check if the data disjunction is small, and to
simulate M . By assumption, the result has logarithmic size.
The data and propositional complexity of k -DD is an immediate corollary to this result.
Corollary 5.4 The data complexity and propositional complexity of k -DD are FL NP
log [log].
At this point, the question arises whether we could not have surpassed the reduction in the proof of
2: ! 3: in Theorem 5.1, by exploiting the completeness result on k -DD. The next result tells us that
this is (presumably) not possible, and that disjunctions not bounded by a constant are needed in general
to have hardness for FP NP
Proposition 5.5 Problem -DD is metric reducible to k -DD with respect to data complexity, for some
only if FP NP
log .
Proof. !: Suppose -DD is metric reducible to k -DD. Then, Corollary 5.2 implies that k -DD
is metric complete for FP NP
k . Since FL NP
log [log] ' FP NP
log , this implies that FP NP
log ) where
denotes the closure of C under metric reductions. Clearly, - mr
log
log , and thus
log holds. Combined with FP NP
log ' FP NP
(cf.

Figure

1), it follows that FP NP
log .
/: Suppose that FP NP
. Let f be any function complete for FP NP
log (such an f exists). Then,
by hypothesis. We use the following fact: Every function f in FP NP
log is - mr -reducible to
some function g in FL NP
log [log]. Indeed, Krentel showed that his class OptP[O(log n)] satisfies FP NP
log '
- mr (OptP[O(log n)]), and that CLIQUE SIZE (cf. Section 2) is OptP[O(log n)]-complete [25]. Since
CLIQUE SIZE is clearly in FP NP
log [log], the claimed fact follows by transitivity of - mr . This
fact and Corollary 5.2, together with the hypothesis FP NP
k imply that -DD - mr f - mr g - mr
-DD. By transitivity of - mr , we obtain -DD - mr k -DD. J
5.2 Expression and combined complexity
Finally, we determine the expression complexity of computing the unique data disjunction.
Theorem 5.6 The expression and combined complexity of -DD is FPSpace NP , and the expression and
combined complexity of k -DD is FPSpace NP [pol].
The proof of the theorem uses succinct upgrade techniques for function problems whose inputs are
given in succinct circuit description. These techniques are described in detail in the following section.
6 Problems with Succinct Inputs
6.1 Previous work and methodology
A problem is succinct, if its input is not given by a string as usual, but by a Boolean circuit which computes
the bits of this string. For example, a graph can be represented by a circuit with 2n input gates, such that
on input of two binary numbers v; w of length n, the circuit outputs if there is an edge from vertex v to
vertex w. In this way, a circuit of size O(n) can represent a graph with 2 n vertices. Suppose that a graph
algorithm runs in time polynomial in the number of vertices. Then the natural algorithm on the succinctly
represented graph runs in exponential time. Similarly, upper bounds for other time and space measures
can be obtained.
The question of lower bounds for succinct problems has been studied in a series of papers about circuits
[35, 22, 31, 24, 3, 7, 44], and also about other forms of succinctness such as representation by Boolean
formulas or OBDDs [42, 43]. The first crucial step in these results is a so-called conversion lemma. It
states that reductions between ordinary problems can be lifted to reductions between succinct problems:
Here, s(A) denotes the succinct version of A, X and Y denote suitable notions of reducibility, where
- Y is transitive.
For the second step, an operator 'long' is introduced which is antagonistic to s in the sense that it
reduces the complexity of its arguments. For a binary language A, long(A) can be taken as the set of
strings w whose size jwj written as a binary string is in A. Contrary to s, long contains instances which
are exponentially larger than the input to A. For a complexity class C , long(C) is the set of languages
long(A) for all A 2 C . It remains to show a second lemma:
Compensation Lemma A - Y s(long(A)).
Then the following theorem can be derived:
Theorem Let C be complexity classes such that long(C 1 let A be C 2 -hard under
reductions. Suppose that the Conversion Lemma and the Compensation Lemma holds. Then s(A) is
reductions.
Proof. To show C 1 -hardness, let B be an arbitrary problem in C 1 . By assumption, long(B) 2 C 2 ,
and therefore, long(B) - X A. By the Compensation Lemma, B - Y s(long(B)), and by the Conversion
Lemma, we obtain s(long(B)) - Y s(A). Since - Y is transitive, s(A) is C 1 -hard. J
6.2 Queries on succinct inputs
For any -structure A, let enc(A) denote the encoding of A by a binary string. The standard way to
encode A is to fix an order on the domain elements, and to concatenate the characteristic sequences of all
relations in A. 2 All Turing machine based algorithms (and in particular, all reductions) in fact work on A.
Therefore, we shall usually identify A and enc(A) without further notice. We use the further notation:
ffl enc(-) denotes the binary language of all encodings of finite -structures.
ffl char(A) is the value of the binary number obtained by concatenating a leading 1 with enc(A).
Given a binary circuit C with k input gates, gen(C) denotes the binary string of size 2 k obtained by
evaluating the circuit for all possible assignments in lexicographical order.
The idea of succinct representation is to represent enc(A) in the form gen(C). To overcome the
mismatch between the fact that the size of enc(A) can be almost arbitrary, while the size of gen(C) has
always the form 2 k , we use self-delimiting encodings:
Definition 6.1 Let . The self-delimiting encoding of w is defined as
1). For a number n, denotes the binary
representation of the number n.
Thus, from a string sd(w)v, the string w can be easily retrieved by looking for the first 1 at an even
position in the string.
Definition 6.2 ([42]) For a binary language L, let sd(L) denote the language
2 The characteristic sequence of a relation is the binary string which for all tuples in lexicographical enumeration describes
membership in the relation by 1, and non-membership by 0; for graphs, this means writing down the adjacency matrix line by
line.
Thus, sd(L) is the language obtained from L by adding the length descriptor and then some dummy string
that pads its size to a power of 2.
Definition 6.3 An FPLT function f is computed by two polylogarithmic time bounded deterministic Turing
Machines N and M , such that on input x, N computes the size of the output jf(x)j, and on input x
and i, M computes the i-th bit of f(x).
A PLT reduction is a reduction computed by an FPLT function.
Modulo PLT reductions, self-delimiting encoding is equivalent to standard encoding:
Lemma 6.1 ([42]) For a nonempty binary language L, L j PLT sd(L).
In particular, this means that there exists an FPLT function extract, which extracts a word from its
self-delimiting encoding.
Definition 6.4 Let F be a query on -structures. The succinct version s(F ) of F is given by
If denote the corresponding -structure, otherwise gen - (C) denotes
some default -structure.
Using gen - , we can rephrase the definition of s(F ) as follows:
The weak reducibility needed for the antecedent of the conversion lemma is given by so-called forgetful
metric reductions; they differ from metric reductions in that the complexity of the inner function is
restricted to FPLT, and that the outer ("forgetful") function may not access the original input.
Definition 6.5 A function f is forgetfully metric reducible to a function g (in symbols, f - mr
f g),
if there is an FPLT function h 1 and a polynomial time computable function h 2 such that for every x,
It is not hard to see that - mr
f is transitive. The crucial observation needed to generalize the results
about succinct decision problems to succinct function problems is that the succinct representation affects
only the inner computation in the metric reduction (i.e., h 1 ), because the result of the succinct function
s(F ) is not succinct. Thus, if we are able to lift the inner reductions from ordinary instances to succinct
instances, then we can leave the outer computation (i.e., h 2 ) unchanged. This lifting is achieved by the
following lemma:
Lemma 6.2 (immediate from [44]) Let f be a FPLT function which maps -structures to oe-structures.
Then there exists an FPLT function F s.t. for all circuits C
With this background, the conversion lemma is easy to show:
Lemma 6.3 (Conversion Lemma) Let F be a query over -structures, and G be a query over oe-structures.
f s(G).
Proof. By assumption we have F We have to show that there exist an FPLT
function H 1 and a polynomial time function H 2 such that
By Lemma 6.2 there is an H 1 s.t. h 1 (gen -
Then we can set H and the lemma is proven. J
It remains to define a suitable long operator. Recall that it has to simplify the complexity of its argu-
ment. Following [42], we obtain the following definition for long on queries:
Definition 6.6 Let (R 1 ) be a signature with a single unary relation symbol, and let Q be a convex
query over signature - . Then the query long(Q) is defined as follows:
where char(A) is the value of the binary number obtained by concatenating a leading 1 with the characteristic
sequence of the tuples in A in lexicographical order.
Lemma 6.4 (Compensation Lemma) Let F be a query. Then F - mr
Proof. As in Lemma 6.3, it is sufficient to show that every input T of F can be translated into a
This was shown (using somewhat different terminology) in [42,
Lemma 6]. J
Theorem 6.5 Let F 1 be two classes of functions, such that long(F 1 . If a query F is hard for
f -reductions, then s(F ) is hard for F 1 under - mr
f -reductions.
6.3 Succinctness and expression complexity
Succinct problems and expression complexity are related by the following methods, which was used in
[23, 14] and generalized in [18]:
Suppose that a language L can express a C 2 -complete property A. Then its data complexity is trivially
. If the language is rich enough to simulate a Boolean circuit by a program of roughly the same size,
then it is possible to combine a program for A with a program for circuit simulation, thus obtaining a
program for s(A). Consequently, there is a reduction from s(A) to the expression complexity of L.
In [14], it was shown how a negation-free DDDB can simulate a Boolean circuit: Let
be a boolean circuit that decides a k-ary predicate R over f0; 1g, i.e., for any tuple
supplied to C as input, a designated output gate of C , which we assume is g t , has value 1 iff
We describe a program -C that simulates C using the universe f0; 1g. For each gate g i , -C uses a k-ary
predicate G i , where G i (-x) informally states that on input of tuple -
x to C , the circuit computation sets the
output of g i to 1. Moreover, it uses a propositional letter False , which is true in those models in which
the G i do not have the intended interpretation; none of these models will be minimal.
The clauses of -C are the following ones. For each gate of C , it contains the clause
Depending on the type a i , -C contains for additional clauses:
The clauses (00) ensure that if a model of ground(-C ; f0; 1g) contains False , it is the maximal interpretation
(which is trivially a model of -C ). In fact, this is the only model of -C that contains False. Let
MC denote the interpretation given by
takes value 1 on input
t to C g.
Lemma 6.6 ([14]) For any Boolean circuit C , MC is the unique minimal model of -C .
Theorem 6.7 Problem -DD is complete for FPSpace NP .
Proof. Define as usual a problem whose input contains a uniform circuit with constant input
gates which generates the instance to be solved. Then it is easy to see that FP NP
k contains a query
Q which is complete under - mr
f -reductions. (For example, QUERY is such a problem: the function
h 1 of any metric reduction g - mr QUERY can be shifted inside the oracle queries in polylog-time,
and the bits of the input string x provided through dummy oracle queries to h 2 .) It is not hard to see
that long(FLinSpace NP
, and therefore by Theorem 6.5, s(Q) is complete for FLinSpace NP .
By standard padding arguments, completeness for FLinSpace NP implies completeness for FPSpace NP .
Thus, it remains to reduce s(Q) to -DD.
By Lemma 6.6, a circuit C with k input gates can be converted into a disjunctive program -C whose
k-ary output relation R describes the string gen(C). Consider the query Q(extract(A)), where A is
an ordered input structure which describes a string by a unary relation. Since Q(extract(A)) is easily
seen to be in FP NP
k , Theorem 5.1 implies that there is a program - whose data disjunction describes the
result of Q(extract(A)). Since DDDBs are uniformly closed, - can be rewritten into a program - 0 whose
input relation R has arity k. As in the proof of Theorem 5.1 we can assume that there is a lexicographical
successor relation on k-tuples. By well-known modularity properties [14, Section 5], the program - 0 [-C
indeed computes Q on the succinctly specified input. J
It is not hard to show that also FL NP
log has - mr
f -complete queries (e.g., a variant of CLIQUE SIZE in
which circuits computing the functions h of a metric reduction to CLIQUE SIZE are part of the
problem instance). The following theorem is then shown analogously:
Theorem 6.8 Problem k -DD is complete for FPSpace NP [pol].
7 Further Results and Conclusion
7.1 Closed world reasoning
The results on data disjunctions that we have derived above have an immediate application to related
problems in the area of closed-world reasoning.
Reiter [36] has introduced the closed-world assumption (CWA) as a principle for inferring negative
information from a logical database. Formally,
For example, CWA(fP (a); (a)g. It follows from results in [11] that
computing CWA(DB) has propositional complexity FP NP
Observe that CWA(DB) may not be classically consistent (under Herbrand interpretations); for exam-
ple, CWA(fP - which has no model. As shown in [11], deciding whether
CWA(DB) is consistent is in \Theta P
2 and coNP-hard in the propositional case; the precise complexity of this
problem is open.
In a refined notion of partial CWA (cf. [16]), which is in the spirit of protected circumscription [34],
only atoms A involving a particular predicate P or, more general, a predicate P from a list of predicates
P may be negatively concluded from DB:
(b)g.
Definition 7.1 (P-minimal model) Let P be a list of predicates. The preorder -P on the models of a
DDDB DB is defined as follows: M -P M 0 , for every P (-c) 2 HB DB such that P 2 P it holds that
. A model M is P-minimal for DB, if there exists no model M 0 such that
We remark that a P-minimal model is a special case of the notion of model [28], given
by an empty list of fixed predicates in a circumscription.
Proposition 7.1 Let DB be a DDDB and P a predicate. Then, the following statements are equivalent:
1. DB has a data disjunction on P .
2. PCWA(DB;P ) is not consistent (with respect to classical Herbrand models).
3. DB does not have a global P -minimal model M , i.e., M - P M 0 for all models M 0 of DB.
Proof. 1: ! 2:: Suppose 2, is a data disjunction of DB. Then,
implies that
which means PCWA(DB;P ) is not consistent.
Suppose DB has a global P -minimal model M . Then, for each atom P (-c) 2 HB DB it
holds that DB 6j= P (-c) iff M 6j= P (-c), since M has the unique smallest P -part over all models of DB.
Hence, M is model of PCWA(DB;P ), and thus PCWA(DB;P ) is consistent.
3: ! 1:: Suppose DB has no global P -minimal model. Let M be the collection of all P -
minimal models M of DB, where w.l.o.g. M 1 6- P M 2 and M 2 6- P M 1 . Let X be the set of all atoms
in arbitrary atoms. Then,
holds for every
which means DB contains a data
disjunction on predicate P (which contains P
As for P-minimality, a list P of predicates can, by simple coding, be replaced with a single predicate
where the first argument in P codes
the predicate. This coding is compatible with P-minimality, i.e., P-minimal and P -minimal models
correspond as obvious. From Proposition 7.1 and the results of the previous sections, we thus obtain the
following result.
Theorem 7.2 Deciding consistency of PCWA(DB;P) and existence of some global P-minimal model of
DB have both \Theta P
propositional and data complexity, and PSpace NP program and expression complexity.
By the same coding technique, the result in Theorem 7.2 holds even if the language has only two
predicates and P contains a single predicate. On the other hand, if the language has a only one predicate
, then the existence of a data disjunction on p is equivalent to the consistency of CWA(DB), whose
precise complexity is open.
7.2 Restricted data disjunctions
In [15], a stronger notion of data disjunction R-c is considered, which requests in addition that
all disjuncts R-c i are identical up to one argument of the list of constants - c i ; we call such data disjunctions
restricted. Note that all data disjunction considered in Section 1 are restricted.
For the problems reformulated to restricted data disjunctions, Table 1 in Section 1 is the same except
that the expression and combined complexity of -DD is FPSpace NP [pol]. Indeed, a restricted data
disjunction C has at most m disjuncts where is the number of constants, and thus -DD has
log n) many output bits in the combined complexity case, where n is the size of DB. The number of
maximal disjunctions md(DB;R), adapted to restricted data disjunctions, is polynomial in the data size,
and thus the same upper bounds can be easily derived as for unrestricted data disjunctions. All hardness
results are immediate from the proofs except for propositional and data complexity of -DD; here, mapping
of elements to newly introduced (polynomially many) domain elements is a suitable technique
for adapting the construction in Figure 2 in the proof of Theorem 5.1.
Finally, we remark that Lemma 2.3 remains true even if all disjunctions in the program - ' describe
restricted data disjunctions. Thus, by a slight adaptation of the programs in proofs and exploiting the fact
that disjunction-free datalog with input negation is sufficient for upgrading purposes [14], the complexity
results for restricted data disjunction remain true even if all disjunctions in DB must be restricted data
disjunctions.
7.3 Conclusion
In this paper, we have considered the complexity of some problems concerning data disjunctions in deductive
databases. To this aim, we have taken an "engineering perspective" on deriving complexity results
using tools from the domain of descriptive complexity theory, and combined them with results for upgrading
complexity results on normal to succinct representations of the problem input. In particular, we
have also investigated the complexity of actually computing data disjunctions as a function, rather than
only the associated decision problem. This led us to generalize upgrading techniques developed for decision
problems to computations of functions. These upgrading results, in particular Theorem 6.5, may be
conveniently used in other contexts.
The tools as used and provided in this paper allow for a high-level analysis of the complexity of prob-
lems, in the sense that establishing certain properties and schematic reductions are sufficient in order to
derive intricate complexity results as eg. for the case of data disjunctions in a clean and transparent way,
without the need to deal with particular problems in reductions. While this relieves us from spelling
out detailed technical constructions, the understanding of what makes the problem computationally hard
may be blurred. In particular, syntactical restrictions under which the complexity remains the same or is
lowered can not be immediately inferred. We leave such considerations for further work. Another interesting
issue for future work is the consideration of computing data disjunctions viewed as a multi-valued
function, which we have not done here.

Acknowledgment

We are grateful to Iain Stewart and Georg Gottlob for discussions and remarks.



--R

Foundations of Databases.
Sparse sets
The complexity of algorithmic problems on succinct instances.

Autoepistemic logics as a unifying framework for the semantics of logic programs.
Querying disjunctive databases through nonmonotonic logics.
Succinct circuit representations and leaf languages are basically the same concept.
Six hypotheses in search of a theorem.
The complexity of propositional closed world reasoning and circumscription.
Semantics of logic programs: Their intuitions and formal properties.
Propositional circumscription and extended closed world reasoning are
The complexity class
Normal forms for second-order logic over finite structures
Disjunctive datalog.
A tractable class of disjunctive deductive databases.
Logical Foundations of Artificial Intelligence.
Relativized logspace and generalized quantifiers over ordered finite structures.
Succinctness as a source of complexity in logical formalisms.

Complexity of query processing in databases with or-objects
Computing functions with parallel queries to NP.
The computational complexity of graph problems with succinct multigraph representation.
Why not negation by fixpoint
Vector language: Simple descriptions of hard instances.
The complexity of optimization problems.
Relativization questions about logspace computability.
Comparison of polynomial-time reducibilities
Computing circumscription.
Foundations of Logic Programming.
Foundations of Disjunctive Logic Programming.
The complexity of graph problems for succinctly represented graphs.
On indefinite data bases and the closed world assumption.
Logic and databases: A 20 year retrospective.
Computing protected circumscription.
A Note on succinct representations of graphs.
On closed-world databases
A taxonomy of complexity classes of functions.
Logical characterizations of bounded query classes I: Logspace oracle machines.
Logical characterizations of bounded query classes II: Polynomial-time oracle machines
On polynomial-time truth-reducibilities of intractable sets to p-selective sets
The complexity of relational query languages.
Languages represented by Boolean formulas.
How to encode a logical structure by an obdd.
Succinct representation
Bounded query classes.
--TR
A note on succinct representations of graphs
Logical foundations of artificial intelligence
Foundations of logic programming; (2nd extended ed.)
The complexity of optimization problems
Complexity of query processing in databases with OR-objects
The complexity of graph problems for succinctly represented graphs
Vector language: simple description of hard instances
On truth-table reducibility to SAT
Bounded query classes
Why not negation by fixpoint?
Foundations of disjunctive logic programming
Propositional circumscription and extended closed-world reasoning are MYAMPERSANDPgr;<supscrpt>p</supscrpt><subscrpt>2</subscrpt>-complete
The complexity of algorithmic problems on succinct instances
A taxonomy of complexity classes of functions
Computing functions with parallel queries to NP
Querying disjunctive databases through nonmonotonic logics
Succinct circuit representations and leaf language classes are basically the same concept
Disjunctive datalog
Languages represented by Boolean formulas
Succinct representation, leaf languages, and projection reductions
Foundations of Databases
The Complexity Class Theta2p
Logic and Databases
On Indefinite Databases and the Closed World Assumption
Six Hypotheses in Search of a Theorem
How to Encode a Logical Structure by an OBDD
The complexity of relational query languages (Extended Abstract)
deductive databases;conversion lemma;complexity upgrading;computational complexity;data disjunction