In: Proceedings of the Thirteenth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-94), pp. 267–278, 1994.

Adding Disjunction to Datalog

(Extended Abstract)

Thomas Eiter  Georg Gottlob  Heikki Mannila^{∗}

Christian Doppler Laboratory for Expert Systems, Information Systems Department

Technical University of Vienna, Paniglgasse 16, A-1040 Wien, Austria

(eiter|gottlob|mannila)@vexpert.dbai.tuwien.ac.at

Abstract

We study the expressive power and complexity of disjunctive datalog, i.e., datalog with disjunctive rule heads, under three different semantics: the minimal model semantics, the perfect models semantics, and the stable model semantics. We show that the brave variants of these semantics express the same set of queries. In fact, they precisely capture the complexity class Σ_{2}^{P}. The combined complexity of disjunctive datalog is shown to be NEXPTIME^{NP}-complete.

1 Introduction

Strong interest in enhancing logic programs by the capability of disjunction emerged in the logic programming and databases community. This interest is documented by a number of publications (cf. [LMR92]) and even workshops dedicated to this subject (cf. [IFI94]).

A disjunctive logic program (DLP) is a logic program that allows for disjunction in rule heads. Several semantics for such programs have been developed. Most of them are extensions of well-known semantics of logic programming (with and without negation). As plain logic programming corresponds to datalog, various extensions of datalog can be formulated for the different semantics of disjunctive logic programming.

In a previous paper [EG93], two of the authors analyzed the complexity of propositional disjunctive logic programming. The present paper is dedicated to the more difficult and involved task of analyzing both the complexity and the expressive power of disjunctive datalog.

The main questions we address in this paper are the following:

\begin{matrix}c \\ ◯ \end{matrix} 1994 ACM 0-89791-639-5/94/0005..$3.50

> How to define the precise semantics of disjunctive datalog based on different well-known semantics for DLPs ?

> What is the expressive power of these variants of disjunctive datalog? In particular, how is the expressive power affected by allowing disjunction in combination with other constructs like inequality ≠ and negation ¬ ?

> What is the complexity of disjunctive datalog, measured by data and expression complexity for the various formalisms ?

> Is disjunctive datalog besides its theoretical interest of practical relevance, i.e., do there exist queries arising in practice for which the power of disjunction in datalog is needed?

Our answers to these questions and the main contributions of this paper are summarized as follows:

• We give a precise definition of the syntax and the semantics of three major variants of disjunctive datalog. These semantics are: the minimal model semantics (MM) [Min82], also termed circumscription [McC80] and EGCWA [YH85]; the disjunctive stable model semantics (SM) [GL88, Prz91]; and the perfect model semantics (PM) [Prz88]. We consider both the brave and the cautious version of these semantics, for Boolean queries and for queries computing output relations.

• Plain datalog augmented with disjunction (DA-TALOG^{∨}) allows under all considered semantics (MM,SM,PM) expressing some Σ_{2}^{P} -hard queries, but not all queries in Σ_{2}^{P}. In fact, it does not allow expressing all queries computable in polynomial time. (This is shown by proving a weak form of preservation under supermodels.)

• We derive interesting new normal forms for second order Σ_{k}^{1} sentences, k ≥ 2, on finite structures. The salient feature of these normal forms is that there is no quantifier alternation in the first order part. Note that a similar normal form for Σ_{1}^{1} sentences does not exist. The normal forms are useful for simplifying our expressiveness proofs.

∗On leave from the University of Helsinki, Finland. Current address: Department of Computer Science, University of Helsinki, P.O. Box 26, SF-00014 University of Helsinki, Finland.

mannila@cs.helsinki.fi Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery.

To copy otherwise, or to republish, requires a fee and/or a specific permission.

SIGMOD/PODS 94 - 5/94 Minneapolis, Minnesota USA

• We show that disjunctive datalog with ≠ captures precisely the Σ_{2}^{P} queries under the brave version of all considered semantics. Thus, adding ≠ (inequality) to DATALOG^{∨} (giving DATALOG^{∨,≠}) suffices to gain full expressive power. The same holds for adding ¬ in case of both the SM and the PM semantics. In the more relevant cases, a symmetric result (Π_{2}^{P} -expressiveness) holds for cautious reasoning. In particular, the results show that for disjunctive datalog the SM-semantics and the PM-semantics express precisely the same set of queries; this is probably not true for DATALOG^{¬}.

• We show that disjunctive datalog queries are Σ_{2}^{P} - complete in the data size and NEXPTIME^{NP}- complete in the program size under the brave version of all considered semantics. Notice that NP ⊂ NEXPTIME; few natural NEXPTIME^{NP}-complete problems are known. In fact, there are Σ_{2}^{P} -hard resp. NEXPTIME^{NP}-hard queries defined by plain disjunctive datalog programs without ≠ and ¬.

• We demonstrate the practical relevance of disjunctive datalog by exhibiting queries (cf. the end of this section) which can be expressed in disjunctive datalog but not in standard DATALOG^{≠,¬} unless the polynomial hierarchy collapses.

Our results complement and extend previous studies of important extensions of datalog and related query languages (cf. [CH85, Van87, KV90, ASV90, AV91, KP91, HS91, VVAG92] and many others [Kan90]). Due to space limitations, we will comment on these extensions in the full paper. We only note that all major versions of DATALOG^{≠,¬} [KP91, Sch90, vRS91] express database queries in NP(resp. co-NP). Thus, disjunction adds expressive power (unless Σ_{2}^{P} = NP).

The following two examples of practical queries illustrate the need for higher expressive power than provided by DATALOG^{¬}.

Example 1.1 (Strategic companies) Suppose a holding has a relational database with information about products and companies; a relation Prod(x, y) contains a tuple (p, c) if product p is produced by company c. The holding faces a crisis and is forced to sell some companies, but still wants to produce all goods. Company c is called strategic if it belongs to some minimal set of companies (wrt inclusion) that can produce all goods. Clearly, the managers want to avoid selling strategic companies. Thus, the database query if a certain company c is strategic is highly relevant.

Now consider the slightly more complex situation that accounts for company control. Several companies c_{1}, c_{2}, …, c_{n} may together have control over a company c, i.e., the holding cannot own all c_{i}’s without holding c as well; this is stored in the relation Cont(x, y), which contains a tuple (c, c_{i}) for each i. Deciding if a company c is strategic in this realistic setting is Σ_{2}^{P} -complete (cf. [CEG94]). Hence, this query is not expressible in DATALOG^{≠,¬} under stable semantics (which captures co-NP [Sch90] resp. NP) unless the polynomial hierarchy collapses.

Example 1.2 (Maximal eigenvector) The need for doing matrix computations in databases was pointed out by David Maier in his invited talk at PODS ‘93 [MV93]. Recall that an eigenvector of an n × n boolean matrix M is a Boolean n-vector e that e = M · e. Eigenvectors have important applications in many areas such as control theory and game theory.

Impose a pre-order (reflexive, transitive binary relation) ≤ on Boolean n-vectors which can be decided in polynomial time, for all n ≥ 1, and consider computing maximal eigenvectors. Given a Boolean matrix M, deciding whether M has a maximal eigenvector with first component 0, order ≤ fixed, can be shown to be Σ_{2}^{P} - complete. Thus, if M is stored in a relational database, a query deciding this problem is not expressible in DA-TALOG^{≠,¬} under stable model semantics. However, by our results the problem can be solved with disjunctive datalog.

2 Preliminaries

For the required concepts of complexity theory, we refer to [Joh90], and for disjunctive logic programming to [LMR92]. For any disjunctive logic program (DLP) P (i.e., a logic program with negation where the head is a disjunction a_{1} ∨ ⋯ ∨ a_{n} of atoms), we denote by HB_{P} its Herbrand base, by MM (P) the set of its minimal Herbrand models, and by P^{U} the grounded version of P with respect to universe U. All considered DLPs are assumed to be function-free.

A relational scheme over a domain Dom is a (possibly empty) list R = R_{1}, …, R_{k} of relation symbols R_{i}, i = 1, …, k of arity a(R_{i}) ≥ 0. We assume that Dom is fixed and countable. An instance of R (relational database over R) is a finite structure D = (U, R_{1}, …, R_{k}) of a finite universe U ⊆ Dom and relations R_{i} ⊆ D^{a(R_{i})}. (As common, we use relation symbols also to denote relation instances.) D(R) denotes the set of all instances of R. By U(D) we denote the universe of D and by D[R′] the projection of D to R′ for any subscheme R′ of R.

A database property over R is a predicate P on D(R) which associates with each D ∈ D(R) a truth value P(D) from {true, false} and which is closed under isomorphisms.

A database mapping or query is a (partial) recursive function q : D(R) → D(S), i.e., which maps instances D of R (intuitively, the input relations) to instances q(D) of S (the output relations), where R and S are disjoint, such that U(D) = U(q(D)) and q is invariant under isomorphisms.The pair (R, S), denoted by IO(q), is called the input/output scheme of q.

Recognizability of a query q is defined in terms of the following query output tuple (QOT) problem: Given D ∈ D(R) and a tuple t matching the format of S_{i} ∈ S, decide if q(D)[S_{i}] ⊧ S_{i}(t). Query q is C-recognizable, C a complexity class, iff the QOT-problem is in C (cf. [Gur88]). Similarly, a database property P is Crecognizable (or, in C) iff deciding P(D) = true is in C.

A query q is Boolean if S is a single 0-ary relation symbol, i.e., a propositional letter P; we say that such a P is true if P (as a relation) consists of the empty tuple (); otherwise, P is false (in that case, P = ∅). A Boolean query corresponds to a database property in the obvious way.

A query language is a set L of query expressions E and a function μ defining the semantics of L, such that for each E ∈ L, μ(E) is a query. The expressive power E(L) of L is the class of all queries definable by query expressions from L, i.e., E(L) = {q : q = μ(E), E ∈ L}.

As well-known, second order definability over finite structures is closely connected to computability within the polynomial hierarchy P H = Σ_{1}^{P} ∪ Σ_{2}^{P} ∪ ⋯ (Σ_{1}^{P} = NP) [Sto77, Lyn82]. For vocabulary σ denote by Σ_{k}^{1}(σ) the second order sentences of the form (∃S_{1})(∀S_{2}) ⋯ (QS_{k})φ(S_{1}, …, S_{k}), where the quantifiers alternate and φ is first order; we write Σ_{k}^{1} if σ is understood.

Proposition 2.1 [Fag74, Sto77, Lyn82] A database property P over R is in Σ_{k}^{P}, k ≥ 1, iff there exists a Σ_{k}^{1}(R)-sentence Ψ such that for each D ∈ D(R), D ⊧ Ψ iff P(D) = true.

3 Disjunctive datalog

3.1 Syntax A disjunctive datalog rule is a clause of the form

a_{1} ∨ ⋯ ∨ a_{n} ← t_{1}, ⋯, t_{m},  1 ≤ n, 0 ≤ m, (1)

where the a_{i}’s are atoms S(x_{1}, …, x_{l}) forming the head of the clause, and the t_{j}’s are terms of the form P (x_{1}, …, x_{l}), ¬P (x_{1}, …, x_{a}), equality atoms x_{i} = x_{j}, or inequality atoms x_{i} ≠ x_{j} that constitute the body of the clause, where S resp. P are relations and all x_{k} are variables (cf. [KP91]); we allow that literals involve 0-ary relation symbols (i.e., propositional letters). The formalism can be easily extended for constants.

A DATALOG^{∨,≠,¬} program π is a finite collection of clauses of form (1). Let RS(π) denote the relations occurring in π. We assume that π has attached an input/output schema IO(π), which is a pair (R, S) such that R are the extensional database relations (i.e., those relations which can appear only in the body), and S is a subset of the intensional relations (i.e., those relations which appear in the head of at least one rule). Intuitively, the relations in R are the input relations and the relations in S are the output relations of π. The relations in RS(π)−RS are referred to as auxiliary relations.

We define a family DATALOG^{X}, X ⊆ {∨, ≠, ¬}, of sublanguages of DATALOG^{∨,≠,¬} as follows. DATALOG (i.e. X = ∅) allows only for clauses with no disjunction (n = 1), negation ¬ only in front of input relations, and no atoms x_{i} = x_{j}, x_{i} ≠ x_{j}; ∨ ∈ X (resp. ≠, ¬ ∈ X) means that disjunction in heads (i.e. n > 1) (resp. x_{i} = x_{i} and x_{i} ≠ x_{j}, ¬P (x_{1}, …, x_{l}) for all P) is allowed, cf. [KV90]. For example, DATALOG^{∨}, which we refer to as plain disjunctive datalog, allows disjunction in the head but no form of negation except in front of input predicates.

3.2 Semantics There are several approaches in logic programming to capture the meaning of DLPs (cf. [LMR92]). We consider the minimal model semantics [Min82] (also termed circumscription [McC80] or EGCWA [YH85]), the (disjunctive) stable model semantics [GL88, Prz91], and the perfect model semantics [Prz88], which are among the most well-known disjunctive semantics. In [BF87] a semantics of disjunctive datalog (with stratified negation) was proposed using default logic; it is equivalent to the stable semantics. We formulate these semantics for full DATALOG^{∨,≠,¬} programs, which implicitly also provides definitions for the sublanguages.

With each DATALOG^{∨,≠,¬} program π and input database D, we associate a grounded DLP P_{π}^{D}. This program consists of all ground clauses C′ which can be obtained from any clause C of π^{U(D)}, i.e., the ground instantiation of π (seen as DLP) from U(D), by cancelling each literal l such that D ⊧ l and l is an atom a = b, a ≠ b, or l involves an input relation of π. Notice that in P_{π}^{D} no =, ≠ and no literal of an input relation of π occurs. We define models of π in terms of Herbrand models of P_{π}^{D}. In the sequel, by model we always mean Herbrand model.

Definition 3.1 Let π be a DATALOG^{∨,≠,¬} program and D an input database for π. The minimal (resp. stable, perfect) models of π on D, MM (π, D) (resp. SM (π, D), PM (π, D)), are the minimal models (resp. the stable models, perfect models) of the DLP P_{π}^{D}.

The stable models of a grounded DLP P are the interpretations I of P such that I is a minimal model of the Gelfond-Lifschitz transform P^{I} [GL88, Prz91]; for the definition of perfect models, cf. [Prz88].

Since a disjunctive datalog program π has multiple minimal (resp. stable, perfect) models in general, the result of the computed query can be defined as either the union or the intersection of those models. The former approach (union) is usually referred to as brave (or credulous) reasoning and the latter (intersection) as cautious (or skeptical) reasoning. More formally, let IO(π) = (R, S) and let S stand for any of MM , SM , PM : brave semantics: q_{b,S}^{π} denotes the query with I/O scheme (R,S) which maps D ∈ D(R) into the union of all S-models of π on D, i.e.,

t ∈ q_{b,S}^{π}(D)[S_{i}] iff S_{i}(t) ∈ ⋃_{M∈S(π,D)} M,

for each tuple t ∈ U(D)^{a(S_{i})} and each S_{i} from S;

cautious semantics: q_{c,S}^{π} denotes the query with input/output scheme (R,S) which maps D ∈ D(R) into the intersection of all S-models of π on D, i.e.,

t ∈ q_{c,S}^{π}(D)[S_{i}] iff S_{i}(t) ∈ ⋂_{M∈S(π,D)} M,

for each t ∈ U(D)^{a(S_{i})} and each S_{i} from S.

We denote by DATALOG_{b,S}^{∨,≠,¬} (resp. DATALOG_{c,S}^{∨,≠,¬}) the query language of DATALOG^{∨,≠,¬} programs π with meaning q_{b,S}^{π} (resp. q_{c,S}^{π}). For example, DATA-LOG_{b,SM}^{∨,≠,¬} denotes DATALOG^{∨,≠,¬} with brave stable model semantics. The notation for sublanguages is analogous.

The following relation between models of the semantics from above follows easily from the definitions and the well-known coincidence of minimal, perfect, and stable models of a ¬-free disjunctive program [Prz88].

Lemma 3.1 For every DATALOG^{∨,≠} program π and input database D, MM (π, D) = SM (π, D) = PM (π, D).

Hence, the query languages DATALOG_{b,S}^{∨,≠} (resp. DATA-LOG_{c,S}^{∨,≠}) for S = MM , SM , PM coincide.

In this paper, we will disregard the cautious variant of the MM-semantics (c, MM ) and restrict our attention to the brave variant (b, MM ). The reason is that a well-known theorem states that a positive fact is in all minimal models iff it is in all models. Thus, the cautious MM-semantics does not provide model selection, and falls back to logical formalisms which are wellunderstood (cf. FN-queries in [CH85]). For the other semantics (SM,PM), the cautious variant is precisely symmetric to the brave variant if ¬ is allowed. For instance, the Boolean DATALOG_{b,SM}^{∨,¬} queries express the Σ_{2}^{P} database properties and the Boolean DATALOG_{c,SM}^{∨,¬} queries express the Π_{2}^{P} database properties. Therefore, we will not explicitly consider cautious SM-semantics (resp. cautious PM-semantics) here.

4 Limited capability of plain disjunctive datalog

We start with considering the effect of adding disjunction to (plain) DATALOG. The expressive power increa-

ses a lot: DATALOG_{b,MM}^{∨} (and DATALOG_{b,SM}^{∨}, DATA-

LOG_{b,PM}^{∨} as well) can express some Σ_{2}^{P} -hard queries (cf. Section 7). Notice that DATALOG_{b,MM} , which coincides with classical DATALOG plus negation of input relations, is limited to a strict subclass of the queries computable in polynomial time. However, DATALOG_{b,MM}^{∨} does not express all Σ_{2}^{P} -recognizable queries, and can in fact even not express all polynomial time computable database properties.

We show that no DATALOG^{∨,¬} program with brave minimal model semantics is able to decide if the universe of the input database is even. This can be easily derived from the following lemma, which states a weak form of monotonicity for this query language.

Lemma 4.1 Let π be a DATALOG^{∨,¬} program with IO(π) = (∅, W), where W is an arbitrary 0-ary predicate. Let D_{1}, D_{2} ∈ D(∅) (i.e., D_{1} = (U_{1}), D_{2} = (U_{2})) such that U_{1} ⊆ U_{2} and |U_{1}| ≥ 1. Then, W ∈ M_{1} for some M_{1} ∈ MM (π, D_{1}) only if W ∈ M_{2} for some M_{2} ∈ MM (π, D_{2}).

Proof. (Sketch) Note that, since π has no input relations, P_{π}^{D_{1}} = π^{U_{1}} and P_{π}^{D_{2}} = π^{U_{2}}, hence MM (π, D_{1}) = MM (π^{U_{1}}) and MM (π, D_{2}) = MM (π^{U_{2}}). In what follows, let P_{1} = π^{U_{1}} and P_{2} = π^{U_{2}}.

It is sufficient to show that the claim holds for U_{2} = U_{1} ∪ {a} where a ∉ U_{1}. The result then follows by a simple induction argument.

Let U_{2} = U_{1} ∪ {a}, a ∉ U_{1}. Assume that W ∈ M for M ∈ MM (P_{1}). Let c be an arbitrary constant from U_{1}, and denote for any formal object X (formula, rule, term, etc) by X[a/c] the object resulting from X by uniformly replacing a with c. Let M^{a/c} = {L ∈ HB_{P_{2}} : L[a/c] ∈ M}. Of course, M^{a/c} is an interpretation of P_{2}. One can show that M^{a/c} is a model of P_{2}. There must exist a minimal model M′ ⊆ M^{a/c} of P_{2}. Clearly, M′ ∩ HB_{P_{1}} is a model of P_{1}. Since M′ ∩ HB_{P_{1}} ⊆ M, but M is already minimal, it holds that M′ ∩ HB_{P_{1}} = M. Since W ∈ M, also W ∈ M′. Since M′ ∈ MM (P_{2}), we are done. □

Theorem 4.2 A query deciding if the universe of a database is even is not expressible in DATALOG_{b,MM}^{∨,¬}.

Proof. Assume that query q_{b,MM}^{π} defined by the DATALOG^{∨,¬} program π with IO(∅, W) decides if the universe of input database D is even. Let D = (U) ∈ D(∅) be such that |U| > 0 is even. Then π computes W true on D. By Lemma 4.1, π also computes W true on D′ = (U ∪{a}), where a is not in U. However, |U ∪{a}| is odd. Contradiction. □

Corollary 4.3 A query deciding if the universe of a database is even is not expressible in DATALOG_{b,SM}^{∨} and not expressible in DATALOG_{b,PM}^{∨}.

Analogous results hold for the cautious semantics. Note that for nondisjunctive datalog, nonexpressiveness results have been recently shown by using infinitary logic (cf. [KV90, KV92]). It would be interesting if similar techniques can also be applied to disjunctive datalog.

5 Useful normal forms for Σ_{2}^{1}-sentences on finite structures

In this section, we present new normal forms for Σ_{2}^{1} sentences over finite structures. In particular, (2) refines the normal form (∃S)(∀T)(∃x)(∀y)φ(x, y), where φ is quantifier-free first order, for Σ_{2}^{1} sentences (cf. [KP91]) over all structures, by taking into account that only finite structures are considered. The new normal forms appear to be helpful for deriving the result of Σ_{2}^{P} - expressiveness of DATALOG_{b,MM}^{∨,≠} in the next section.

Theorem 5.1 Let σ be a (finite) vocabulary and Φ a Σ_{2}^{1}(σ) sentence.

(i) There exists a Σ_{2}^{1}(σ) sentence of the form

(∃S)(∀TZ)[ (∀y)(Z(y))∨(∃x)(ϑ_{1}(x)∨⋯∨ϑ_{k}(x)) ] (2)

where the ϑ_{i}’s are conjunctions of literals, which is equivalent to Φ over all finite structures.

(ii) Let σ′ = σ ∪ {F, S, L}, where F and L, unary, and S, binary, are new predicate symbols. There exists a Σ_{2}^{1}(σ′) sentence Φ′ of the form

(∃S)(∀T)(∃x)(ϑ_{1}(x) ∨ ⋯ ∨ ϑ_{k}(x))  (3)

where the ϑ_{i}’s are conjunctions of literals in which F, L, and S occur only positively, such that for every finite structure D for σ, we have D ⊧ Φ iff D′ ⊧ Φ′, for any extension D′ of D to σ′ in which F, S, and L are interpreted as the relations first, successor, and last of a linear order on the universe.

Proof. (Sketch) We first show (ii). Applying the method in [KP91] one can easily show that every Σ_{2}^{1}(σ) sentence is equivalent to a Σ_{2}^{1}(σ) sentence

(∃S)(∀T)(∃x)(∀y)φ(x, y).  (4)

Assume that F (x), S(x, y), and L(x) are the predicates which describe the first element, the successor relation, and the last tuple of some linear order < on the universe. The predicates F^{n}(y), S^{n}(y, y′), and L^{n}(y) that describe the first tuple, the successor (y′ is the successor of y) and the last tuple of the lexicographic order <^{n} derived from < on all n-tuples over the universe can be easily described using F, S and L as follows: let F^{1}(x) = F (x), S^{1}(x, y) = S(x, y), L^{1}(x) = L(x) and for n > 1,

F^{n}(x) ≡ F (x_{1}) ∧ F^{n−1}(x′),
S^{n}(x, y) ≡ (x_{1} = y_{1} ∧ S^{n−1}(x′, y′)) ∨ (S(x_{1}, y_{1}) ∧
L^{n−1}(x′) ∧ F^{n−1}(y′)),
L^{n}(y) ≡ L(y_{1}) ∧ L^{n−1}(y′),

where x = (x_{1}, …, x_{n}), x′ = (x_{2}, …, x_{n}), y = (y_{1}, …, y_{n}) and y′ = (y_{2}, …, y′_{n}). Thus, F^{n}(x), S^{n}(x, y), and L^{n}(x) can be described by disjunctions of conjunctions of equality atoms x_{i} = y_{i} and atoms from F, S, and L.

Using F^{n}, S^{n} and L^{n}, the universal first order quantifier in (4) can be eliminated as follows. Define the formula Ψ as

(∀Z)(∃xy)[ F^{n}(y) ∧ φ(x, y) ∧ ¬Z(x, y) ]
∨ (∃xy)[ Z(x, y) ∧ L^{n}(y) ]
∨ (∃xyy′)[ Z(x, y) ∧ ¬Z(x, y′) ∧
S^{n}(y, y′) ∧ φ(x, y′) ],

where Z is a new predicate variable. Intuitively, the formula is false if Z consists of the union of {(a, b_{1}), …, (a, b_{la})} for all a, where b_{1}, …, b_{la} is the maximum initial segment of the order <^{n} such that φ(a, b_{i}) is true, 1 ≤ i ≤ la, and each of those segments is strict. We claim that Ψ ≡ (∃x)(∀y)φ(x, y).

Assume that for any finite structure D, D |̸= (∃x)(∀y)φ(x, y), i.e., D ⊧ (∀x)(∃y)¬φ(x, y). Let min(a) be the first b′ such that D |̸= φ(a, b′); notice that min(a) is well-defined. Define Z_{0} = {(a, b) : b is ordered before min(a)}. We check that (D, Z_{0}) |̸= A, where A is the first order part of Ψ. First

(D, Z_{0}) |̸= (∃xy)[ F^{n}(y) ∧ φ(x, y) ∧ ¬Z(x, y) ],

because if (D, Z_{0}) ⊧ φ(a, b)∧F^{n}(b), then by definition (a, b) ∈ Z_{0}. Second,

(D, Z_{0}) |̸= (∃xy)[ Z(x, y) ∧ L^{n}(y) ];

for, if (D, Z_{0}) ⊧ Z(a, b), b is ordered by definition of Z_{0} before min(a), hence (D, Z_{0}) |̸= L^{n}(b). Third,

(D, Z_{0}) |̸= (∃xyy′)[ Z(x, y) ∧ ¬Z(x, y′) ∧
S^{n}(y, y′) ∧ φ(x, y′) ];

Assume to the contrary that (D, Z_{0}) ⊧ Z(a, b) ∧ ¬Z(a, b′) ∧ S^{n}(b, b′) ∧ φ(a, b′) for a, b, and b′. By the definition of Z_{0}, it follows that b′ = min(a). Since D ⊧ ¬φ(a, min(a)), a contradiction is reached. It follows that (D, Z_{0}) |̸= A; hence, D |̸= Ψ.

Now assume that D ⊧ (∃x)(∀y)φ(x, y), i.e., D ⊧ (∀y)φ(a, y) for some a. Consider any Z, and let b_{1} be the first and the b_{l} be the last tuple in the order <^{n}. There are three cases. Case 1: (a, b_{1}) ∉ Z. Then, (D, Z) ⊧ F^{n}(b_{1}) ∧ φ(a, b_{1}) ∧ ¬Z(a, b_{1}); hence, (D, Z) ⊧ A. Case 2: (a, b_{l}) ∈ Z. Then, (D, Z) ⊧ Z(a, b_{l}) ∧ L^{n}(b_{l}); hence, (D, Z) ⊧ A. Case 3: (a, b_{1}) ∈ Z and (a, b_{l}) ∉ Z. Hence, there is a b such that (a, b) ∉ Z and (a, b′) ∈ Z for each b′ that is ordered before b. Let b′ be the predecessor of b. (Note that b′ exists.) Then,

(D, Z) ⊧ Z(a, b′) ∧ ¬Z(a, b) ∧ S^{n}(b′, b) ∧ φ(a, b);

hence, (D, Z) ⊧ A. ⋄

Consequently, (D, Z) ⊧ A. It follows that D ⊧ Ψ. The claim is proved.

Thus, if F, S, and L are provided, (4) is equivalent to

(∃S)(∀TZ)(∃z)μ(z),  (5)

where (∃z)μ(z) is the first order part of Ψ transformed into prenex normal form. Now μ(z) can be easily rewritten as a disjunction of conjunctions of literals, in which F, S, and L occur only positively. Thus, part (ii) of the theorem follows.

We continue to show (i). Clearly, F, S and L can be characterized from < by a first order sentence, which is equivalent to some second order sentence of the form

(∃Q)(∀R)[(∀x)(R(x)) ∨ (∃u)β(u)],  (6)

where β(xy) = ¬R(x)∧φ(x, y). To show this, every Σ_{1}^{1} sentence is equivalent to a Σ_{1}^{1} sentence of the form

(∃S)(∀x)(∃y)φ(x, y),  (7)

over the same vocabulary, cf. [KP91]; as easily checked, this formula is equivalent to

(∃S)(∀T)[(∀x)(T (x)) ∨ (∃xy)(¬T (x) ∧ φ(x, y))], (8)

where T is a new predicate variable.

Consequently, the sentence (4) is equivalent to the existential closure of the conjunction of (5) and (6) with respect to <, F, S, and L, which is equivalent to

(∃S<F SLQ)(∀RT)

{ [ (∀x)(R(x)) ∨ (∃u)β(u) ] ∧ (∃z)μ(z) } . (9)

This sentence is in turn equivalent to

(∃S<F SLQ)(∀RT)

{ (∀x)(R(x)) ∨ [ (∃u)β(u) ∧ (∃z)μ(z) ] } . (10)

Here (∃u)β(u) ∧ (∃z)μ(z) can be rewritten to

(∃uz) [γ_{1}(u, z) ∨ ⋯ ∨ γ_{m}(u, z)], where each γ_{i} is a conjunction of literals. Hence, for (4) there exists an equivalent formula of the form of (2). Part (ii) of the theorem follows. □

The theorem easily generalizes from Σ_{2}^{1} sentences to Σ_{k}^{1} sentences for k ≥ 2. Notice that it does not hold for k = 1, i.e., Σ_{1}^{1} sentences. We remark that neither of the disjuncts in (2) can be eliminated; one can show that if the existential (resp. universal) formula is not present, the formula is preserved under submodels (resp. supermodels; cf. [CK73] for model preservation properties). It is currently not known if the form (2) is valid over all structures. Analogous normal forms for Π_{k}^{1} sentences follow.

6 Expressive power of disjunctive datalog plus ≠

In this section, we show that adding ≠ to plain disjunctive datalog under the brave minimal model semantics suffices to gain full expressive power for Σ_{2}^{P}.

We consider first Boolean queries and address then general queries. The proof that DATALOG_{b,MM}^{∨,≠} expresses Σ_{2}^{P} utilizes the equivalent form 3 for Σ_{2}^{1} sentences in Theorem 5.1. In order to do so, we first describe a DA-TALOG^{∨,≠} program π_{<} that computes the relations F, S, and L under brave minimal semantics. A special 0ary predicate Good will indicate in each minimal model whether F, S, and L have the intended interpretation.

First, we state an easy lemma on minimal models of DLPs, which is useful for showing that a subprogram P_{1} of a DLP P behaves as desired under minimal models. Similar modularity properties of logic programs have been considered in [Sch90] and, for disjunctive logic programs, in [Dix92].

Definition 6.1 Let P_{1} and P_{2} be DLPs. We write P_{2} ▷ P_{1} iff no predicate occurring in P_{1} occurs in the head of any rule of P_{2}.

Lemma 6.1 Let P_{1} and P_{2} be ¬-free DLPs such that P_{2} ▷ P_{1}. Then,

(i) ∀M ∈ MM (P_{1} ∪ P_{2}): M ∩ HB_{P_{1}} ∈ MM (P_{1}).

(ii) MM (P_{1} ∪ P_{2}) = ⋃_{M∈MM (P_{1})} MM (M ∪ P_{2}). □

Program π_{<} is as follows; < is a binary relation, F̃, S̃, L̃ are intended to be the complements of F, S, and L respectively, in minimal models, and G is an auxiliary relation.

(1) x < y ∨ y < x ← x ≠ y.
(2) x < z ← x < y, y < z.
(3) S̃(x, z) ← z < x.
(4) S̃(x, z) ← x < y, y < z.
(5) S̃(x, x) ←.
(6) S(x, y) ∨ S̃(x, y) ←.

(7) F̃(x) ← y < x.
(8) F (x) ∨ F̃(x) ←.
(9) L̃(x) ← x < y.
(10) L(x) ∨ L̃(x) ←.
(11) G(x) ← F (x).
(12) G(y) ← G(x), S(x, y).
(13) Good ← G(x), L(x).

Lemma 6.2 Let U be any finite universe. For every linear order ≺ on U, let M_{≺}^{U} be the interpretation of π_{<}^{U} such that {Good, G(a) : a ∈ U} ⊆ M_{≺}^{U}, < is interpreted as ≺, and F, S, and L (resp. F̃, S̃, L̃) are interpreted as the relations describing the first element, the successor relation, and the last element of ≺ (resp. the complements of those relations). Then,

(i) M_{≺}^{U} ∈ MM (π_{<}^{U}), for each linear order ≺ on U;

(ii) if M ∈ MM (π_{<}^{U}) such that Good ∈ M, then M = M_{≺}^{U} for some linear order ≺ on U.

Proof. (Sketch) Let P denote π_{<}^{U}. It is easy to see that M_{≺}^{U} is a model of P, and that no atoms can be removed from M_{≺}^{U} without loosing the model property. Hence, (i) follows. To show (ii), let M ∈ MM (P) such that Good ∈ M. (Thus, U ≠ ∅.) Since M is minimal, it is easy to see that F̃, S̃ and L̃ are defined in M as the complement of F, S and L, respectively. Let P_{1} consist of all instances of (1) (2) in P and P_{2} of the remaining clauses of P. By Lemma 6.1, it follows easily that < is interpreted in M as a linear order ≺ on U. Since F and F̃ etc are complementary in M, it follows from the clauses of P that F, S and L must be interpreted in M as subsets of the relations describing the first element, the successor, and last element for ≺, respectively. Since Good ∈ M, it follows that G(a), L(a) ∈ M for some a ∈ U; it follows that M interprets L as relation describing the last element of ≺. By induction downwards the order ≺, we obtain that G(a) ∈ M for each a ∈ M and that M interprets S and F such that they describe the successor relation and the first element of ≺, respectively. It follows that M = M_{≺}^{U}. □

The following lemma collects already known results on minimal, stable, and perfect models of propositional DLPs.

Lemma 6.3 [EG93] Let P be a propositional DLP and p be a propositional atom. Deciding if p ∈ M for some M ∈ S(P) is Σ_{2}^{P} -complete for S = MM , SM , PM .

Now we are ready, using the results from Section 5, to show that DATALOG_{b,MM}^{∨,≠} can express all, and only, the Σ_{2}^{P} -recognizable queries.

Theorem 6.4 Let S be any of MM , SM , PM . The DA-TALOG_{b,S}^{∨,≠,¬} queries are Σ_{2}^{P} -recognizable.

Proof. The QOT problem (cf. Section 2) for query q_{b,S}^{π} defined by the DATALOG^{∨,≠,¬} program π trivially reduces to deciding if a grounded atom a belongs to some M ∈ S(π, D) = S(P_{π}^{D}). For fixed π, the size of π^{U(D)} is polynomial in the size of the input database D of π, hence the grounded DLP P_{π}^{D} can be constructed in polynomial time. Thus the theorem follows from Lemma 6.3. □

Let us first note the expressiveness of Boolean queries, which is useful for deriving the expressiveness of queries with output relations.

Theorem 6.5 The Boolean DATALOG_{b,MM}^{∨,≠} queries precisely capture the class of all database properties in Σ_{2}^{P}.

Proof. (Sketch) By Theorem 6.4, it remains to show that every Σ_{2}^{P} -recognizable database property P can be expressed by a Boolean DATALOG_{b,MM}^{∨,≠} query.

For that, we describe a Boolean DATALOG^{∨,≠} program π with IO = (R, W), where W is a 0-ary predicate, such that, for every D ∈ D(R), the query q_{b,MM}^{π} computes W true on D iff P(D) = true. From Proposition 2.1, we have that P is equivalent to some Σ_{2}^{1}(σ) sentence Ψ. Let Ψ′ be the Σ_{2}^{1}(σ′) sentence, σ′ = R ∪ {F, S, L}, of the form (∃S)(∀T)(∃x)(ϑ_{1}(x)∨⋯∨ϑ_{k}(x)) as described in Theorem 5.1(i). Assume that S = S_{1}, …, S_{n} and T = T_{1}, …, T_{m}. Let the DATALOG^{∨,≠} program π_{0} consist of the following clauses (arities of tuple variables are understood):

(1)  S_{i}(x) ∨ S̃_{i}(x) ← ,  for i = 1, …, n;
(2)  T_{j}(x) ∨ T̃_{j}(x) ← ,  for j = 1, …, m;
(3)  T_{j}(x) ← W,  for j = 1, …, m;
(4)  T̃_{j}(x) ← W,  for j = 1, …, m;
(5)  W ← T_{j}(x), T̃_{j}(x),  for j = 1, …, m;
(6)  W ← η_{i}(x),  for i = 1, …, k;

In this program, the S̃_{i} and T̃_{j} are new relations of the arity of S_{i} and T_{j}, respectively; W is a new 0ary relation. Further, for each i = 1, …, k, η_{i}(x) = l′_{i,1}, …, l′_{i,n_{i}}, Good, where ϑ_{i} = l_{i,1} ∧ ⋯ ∧ l_{i,n_{i}} and l′_{i,j} is the literal l_{i,j} where, in case, each ¬S_{h} (resp. ¬T_{h}) is replaced by S̃_{h} (resp. T̃_{h}).

Let R′ = R ∪ {F, S, L, Good} and let IO(π_{0}) = (R′, W). The following can be shown. For every D′ ∈ D(R′) such that Good is true and F, S, L describe the relations first, successor, and last for a linear order ≺ of the universe U(D), there exists an M ∈ MM (π_{0}, D′) with W ∈ M iff D′ ⊧ Ψ′, i.e., P(D′[R]) = true.

Now let π be the union of π_{0} and π_{<} from above. Let D ∈ D(R). Define that for each linear order ≺ on U(D), D_{≺} ∈ D(R′) is the database such that D_{≺}[R] = D, Good is true, and F, S and L describe the relations first, successor and last for ≺. Then, by Lemmas 6.1 and 6.2 it follows that

{M ∈ MM (π, D) : W ∈ M} = {M_{1} ∪ M_{2} : M_{1} ∈ MM (π_{0}, D_{≺}), W ∈ M_{1},

M_{2} = M_{≺}^{U(D)}, ≺ a linear order on U(D)} .

It follows that for every D ∈ D(R), the query q_{b,MM}^{π} computes W true on D iff P(D) = true. □

Corollary 6.6 The Boolean DATALOG_{b,SM}^{∨,≠} (resp. DA-TALOG_{b,PM}^{∨,≠} ) queries precisely capture the class of all database properties in Σ_{2}^{P}.

A similar result can be derived for DATALOG^{∨,¬} queries under the brave SM (resp. PM) -semantics. Notice that the expressive power of DATALOG^{∨,¬} queries under the MM-semantics is the same as for DATALOG^{∨} queries, since negative literals in the body can be moved to the head of a clause.

Theorem 6.7 The Boolean DATALOG_{b,SM}^{∨,¬} (resp. DA-TALOG_{b,PM}^{∨,¬}) queries precisely capture the class of all database properties in Σ_{2}^{P}.

Proof. (Sketch) This follows from Corollary 6.6 and the fact that ≠ can be easily computed using negation in stable (resp. perfect) models. Let π be a DATA-LOG^{∨,≠,¬} program and let Neq, Eq be binary relations not occurring in π. Let π′ be the program resulting after replacing in π each x_{i} = x_{j} by Eq(x_{i}, x_{j}), each x_{i} ≠ x_{j} by Neq(x_{i}, x_{j}), and by adding the clauses Neq(x, y) ← ¬Eq(x, y) and Eq(x, x) ←. It holds that for every D ∈ D(R), SM (π, D) = {M ∩ HB_{P_{π}^{D}} : M ∈ SM (π′, D)} (resp. PM (π, D) = {M ∩ HB_{P_{π}^{D}} : M ∈ PM (π′, D)}); the result follows. □

Since Σ_{2}^{P} is closed under conjunction, it is not difficult to extend our results for Boolean queries to the case of general I/O-queries. However, proofs of such generalizations are rarely found in the literature. Therefore, we will give a proof here.

Theorem 6.8 A query q is Σ_{2}^{P} -recognizable iff it is expressible in DATALOG_{b,MM}^{∨,≠} .

Proof. (Sketch) By Theorem 6.4, it remains to show the if-direction.

Let q : D(R) → D(S) be a Σ_{2}^{P} -recognizable query. Let P be the database property over R′ = RS defined as follows: for every D′ ∈ D(R′), P(D′) = true iff D′[S] ⊆ q(D′[R]), where ⊆ is understood componentwise. (P is in fact a database property.) Note that for any instance D′ of R′, P(D′) is equivalent to a conjunction of QOTproblems for q as follows:

P(D′) = ⋀_{S_{i}∈S} ⋀_{t∈D′[S_{i}]}( t ∈ q(D′[R])[S_{i}] ).

Since q is Σ_{2}^{P} -recognizable, it follows that P is in Σ_{2}^{P}. Thusreftheo:ddlneq-b,mm, there exists a DATALOG^{∨,¬} program π′ where IO(π′) = (R′, W) for some 0-ary relation W such that q_{b,MM}^{π′} computes W true over D′ ∈ D(R′) iff P(D′) = true. We may assume that π′ has exactly the form of the DATALOG^{∨,≠}-program in the proof of Theorem 6.5. Now let π be the DA-TALOG^{∨,≠} program with IO(π) = (R, S) obtained by modifying π′ as follows. For each S_{i} ∈ S, add the rules

\begin{matrix}S_{i}(x) ← & W, S′_{i}(x). \\ S′_{i}(x) ∨ S̃′_{i}(x) ← & . \end{matrix}

where S′_{i} and S̃′_{i} are new relations of the same arity as S_{i}, and replace each positive (resp. negative) occurrence of S_{i} in π with S′_{i} (resp. S̃′_{i}). Intuitively, the first rule allows derivation of S_{i} only if W is in the interpretation, and the second rule simulates all possible instances of S′_{i}.

For every D ∈ D(R), q_{b,MM}^{π} essentially computes the union of all M ∈ MM (π, D) with W ∈ M. It can be seen that those M correspond precisely to the D′ ∈ D(R′) such that D′[R] = D and P(D′) = true, i.e., D′[S] ⊆ q(D′[R]), where each M corresponds to the D′ such that M and D′ are equivalent on S. It follows that q_{b,MM}^{π} (D) = q(D). □

Corollary 6.9 A query q is Σ_{2}^{P} -recognizable iff it is expressible in DATALOG_{b,SM}^{∨,≠} iff it is expressible in DA-TALOG_{b,PM}^{∨,≠} iff it is expressible in DATALOG_{b,SM}^{∨,¬} iff it is expressible in DATALOG_{b,PM}^{∨,¬}.

Symmetric results hold for the cautious semantics.

7 Complexity of disjunctive datalog

The complexity of a query language is traditionally measured by data and expression (resp. data/ expression) complexity, cf. [Var82]. The data (resp. expression, data/expression) complexity of a query language L is defined as the complexity of the QOT-problem in Section 2 for the queries defined by expressions E ∈ L, where E is part of the input and E (resp. D, neither E nor D) is fixed.

7.1 Data complexity From Theorem 6.4, we have

Theorem 7.1 The data complexity of DATALOG_{b,S}^{∨,≠,¬} queries is in Σ_{2}^{P} for S = MM , SM , PM .

From the proof of Theorem 6.5 and Proposition 2.1, it follows that DATALOG_{b,MM}^{∨,≠} queries are Σ_{2}^{P} -hard in the data size. In fact, this can be sharpened to plain disjunctive datalog queries defined by programs without ≠ and ¬. Thus, adding disjunction to pure Horn clauses allows one to express Σ_{2}^{P} -hard queries. The proof is via a program π for deciding whether an atom a occurs in some minimal model of a DLP program of propositional clauses a_{1} ∨ a_{2} ← t_{1}, t_{2}, t_{3} ([EG93]).

Theorem 7.2 The Boolean DATALOG_{b,MM}^{∨} queries are Σ_{2}^{P} -hard in the data size, even if no negation occurs in query programs.

Proof. Let P be a DLP consisting of propositional clauses of the form

a_{1} ∨ a_{2} ← t_{1}, t_{2}, t_{3} (∗)

where all a_{1}, a_{2} and t_{1}, t_{2}, t_{3} are not necessarily distinct atoms from propositional variables x_{1}, …, x_{n} and t, which is a constant for true. By [EG93, Theorem 3.1] it follows that, given P and an atom a, deciding if a occurs in some minimal model of P is Σ_{2}^{P} -hard.

We define a fixed DATALOG^{∨} program π with IO(π) = (CAT, W), where C is 5-ary, A and T are unary, and W is 0-ary, such that π solves this problem on an input database D which is constructed from P as follows. The universe U of D is the set {x_{1}, …, x_{n}, t}.

The clauses of P are encoded in the relation C, which consists of the tuples (a_{1}, a_{2}, t_{1}, t_{2}, t_{3}) for all clauses (∗) in P; the relations A and T are used to designate the atom a and the constant t, i.e. A = {a} and T = {t}. In addition, π uses a unary auxiliary relation V which intuitively corresponds to a valuation of the atoms.

Program π consists of the following three clauses.

V (y) ← T (y).
V (y_{1}) ∨ V (y_{2}) ← C(y_{1}, y_{2}, y_{3}, y_{4}, y_{5}),

V (y_{3}), V (y_{4}), V (y_{5}).

W ← A(y), V (y).

It is easily checked that π has a minimal model on D in which W occurs (i.e., the query q_{b,MM}^{π} computes W true on D) iff P has a minimal model in which a occurs. Since D is polynomial time constructible from P, the result follows. □

Corollary 7.3 The Boolean DATALOG_{b,SM}^{∨} queries and DATALOG_{b,PM}^{∨} queries are Σ_{2}^{P} -hard in the data size, even if no negation occurs in query programs.

7.2 Expression complexity Intuitively, the expression complexity of disjunctive datalog is exponentially larger than the data complexity, since the size of the grounded DLP P_{π}^{D} for the DATA-LOG^{∨,≠,¬} program π can be exponential in the size of D and π. In fact, the expression complexity of DA-TALOG_{b,MM}^{∨,≠,¬} turns out to be NEXPTIME^{NP}-complete; even plain disjunctive datalog without ≠ and ¬ is NEXPTIME^{NP}-hard in the program size.

Theorem 7.4 The expression complexity of DATA-LOG_{b,S}^{∨,≠,¬} is in NEXPTIME^{NP} for S = MM , SM , PM .

Proof. (Sketch) P_{π}^{D} is polytime constructible from D and π^{U(D)}, whose size is clearly bounded by n^{n} = 2^{n log n}, where n is the size of π plus D. By Lemma 6.3, deciding if S_{i}(a) ∈ M for some M ∈ S(P_{π}^{D}) is nondeterministically possible with an NP oracle in time polynomial in the size P_{π}^{D}. Thus, deciding whether S_{i}(a) ∈ M for some M ∈ S(π, D) is possible by a nondeterministic Turing machine in single exponential time with respect to the size of π plus D by using an NP oracle. Thus, the QOT-problem (Section 2) is in

NEXPTIME^{NP}. □

The proof of NEXPTIME^{NP}-hardness relies on the use of new complexity upgrade techniques that extend the results in [BLT92, PY85], applied to results in [Ste91], and the simulation of Boolean circuits by a DATALOG^{∨} program without ≠ and ¬ under minimal model semantics. (Cf. [KP91] for a simulation in DA-TALOG^{¬,≠} using fixpoint semantics.)

Roughly, the proof consists in a reduction of a problem on graphs, co-CERT3COL [Ste91], in its succinct version co-CERT3COL_{S} [BLT92], i.e., the problem input consists of a Boolean circuit C_{w} by which the bits of the standard problem input w (a binary string encoding the graph) can be computed. Using the complexity upgrade techniques, we show that co-CERT3COL_{S} is NEXPTIME^{NP}-complete. This problem is reduced to evaluating Boolean queries q_{bMM}^{π} over a fixed database D_{0}, defined by DATALOG^{∨} programs π which are constructed in polynomial time

It is well-known that the input representation (e.g., numbers in unary or binary notation) can have a drastic effect on the problem complexity. Such effects were investigated for the “succinct versions” of graphtheoretic problems in [PY85], where a graph whose vertices are elements of {0, 1}^{n} is represented by a Boolean circuit with 2n input bits; the circuit outputs 1 if and only if the input represents two vertices which are connected by an edge.

Formally, a Boolean circuit is a finite set of triples (gates) {g_{i} = (a_{i}, j, k) : 1 ≤ i ≤ t}, where a_{i} ∈ {in, and, or, not} is the kind of the gate, and g_{j}, g_{k}, j, k < i are the inputs of the gate, unless g_{i} is an in-gate, in which case, say, j = k = 0. For not-gates, j = k (cf. [KP91]). As shown in [PY85] showed that the succinct problem setting often leads to an exponential complexity increase.

The results and techniques of [PY85] were generalized in [BLT92] to the succinct version of any decisional problem A encoded as a language over {0, 1}. The succinct representation of a binary word w is a Boolean circuit that on input of a number i (in binary), outputs whether i ≤ |w| and in that case, the i-th bit of w (|w| denotes the length of w). The succinct version A_{S} of A is as follows: Given a Boolean circuit C_{w} describing a word w, decide whether w ∈ A.

The following theorem shows how to obtain hardness results under polynomial time transformability (≤_{m}^{p}) for the succinct problem version from hardness of the standard problem under polylogtime transformability (≤_{m}^{P LT}). This theorem is a generalization of [BLT92, Theorem 5], where the theorem is formulated for logtime transformability (≤_{m}^{LT}). Roughly, a ≤_{m}^{P LT} - transformation is a problem mapping f such that, given w and an integer i, the i-th bit of f(w) is computable in polylogarithmic time; note that every such mapping defines a polynomial-time transformation. For problem A, let long(A) be defined as follows: w ∈ long(A) iff the binary expression of the length of w is in {1w : w ∈ A}.

Theorem 7.5 Let C1 and C2 be arbitrary complexity classes such that for every A ∈ C1, long(A) ∈ C2. Then, for every B, if B is hard for C2 under ≤_{m}^{P LT} - transformation, then B_{S} is hard for C1 under ≤_{m}^{p}- transformation.

Proof. (Sketch) The theorem can be easily shown along the lines of the proof of Theorem 5 in [BLT92] by using a generalization of the following Conversion Lemma in [BLT92]: If A ≤_{m}^{LT} B then A_{S} ≤_{m}^{p} B_{S}. It can be seen, by carefully looking at the proof in [BLT92], that the Conversion Lemma remains valid if A ≤_{m}^{LT} B is replaced by A ≤_{m}^{P LT} B.

To show the theorem, assume that B is hard for C2 under ≤_{m}^{P LT} -transformation, and let A ∈ C1 be arbitrary. By hypothesis, long(A) ∈ C2 and therefore long(A) ≤_{m}^{P LT} B. By the generalized Conversion Lemma, long(A)_{S} ≤_{m}^{p} B_{S}. Furthermore, A ≤_{m}^{p} long(A)_{S} ([BLT92, Lemma 4]); by transitivity, A ≤_{m}^{p} B_{S}, and thus B_{S} is ≤_{m}^{p}-hard for C1. □

The proof of Theorem 7.9 uses this complexity upgrade technique. It gives a polynomial time transformation of the succinct version co-CERT3COL_{S} of the graph problem co-CERT3COL, to evaluating Boolean DATA-LOG_{b,MM}^{∨} queries over a fixed database. The query program involves a subprogram which simulates Boolean circuits by which the relations in the input structure encoding the graph can be computed.

Problem co-CERT3COL is as follows (cf. [Ste91]):

Instance of size n: a graph G on the vertices {0, 1, …, n − 1} such that every edge is labeled with a disjunction of two literals, where each literal is over the Boolean variables {X_{i,j} : i, j = 0, …, n − 1}. Yes-instance of size n: an instance G of size n such that for some truth value assignment t on the Boolean variables, the graph t(G) obtained from G by including only those edges set true under t is not 3-colorable.

Stewart showed that the complementary problem CERT3COL (i.e., negated condition for Yes-instances) is complete for Π_{2}^{P} under projection translations. It can be easily seen that projection translatability implies ≤_{m}^{P LT} -transformability. Thus, co-CERT3COL is clearly complete for Σ_{2}^{P} under ≤_{m}^{P LT} -transformation. Applying the complexity upgrade theorem, we thus obtain

Theorem 7.6 co-CERT3COL_{S} is complete for NEXP-

TIME^{NP}under ≤_{m}^{p}-transformation.

We next describe disjunctive dalaog programs for deciding co-CERT3COL and for simulating a Boolean circuit. The programs are used in the proof of Theorem 7.9.

labeled graph coloring program

Problem co-CERT3COL can be decided by a Boolean DATALOG^{∨} program π_{Col} in which no negation occurs using brave stable model semantics. For an instance of co-CERT3COL of size n, the input database of π_{Col} consists in a structure with universe {0, …, n − 1} and certain relations encoding the labeled graph.

We may assume that co-CERT3COL is encoded using a binary relation E and 4-ary relations P and N, such that E(x, y) ∨ E(y, x) (resp. P (x, y, u, v) ∨ P (y, x, u, v), N(x, y, u, v) ∨ N(y, x, u, v)) encodes that an edge between x and y exists (resp. the edge between x and y is labeled by X_{u,v}, ¬X_{u,v}).

Thus, the input relations of π_{Col} are E, N and P; the output relation of π_{Col} is the 0-ary predicate W. The program π_{Col} uses in addition binary relations V and Ṽ, where V (u, v) means that X_{u,v} has value true; Ṽ is intended to be the complement of V. Furthermore, π_{Col} uses unary relations R, B, and G, which encode the color of a node. π_{Col} consists of the following clauses:

\begin{matrix}(1) & V (x, y) ∨ Ṽ (x, y) ← . \\ (2) & W ← R(x), G(x). \\ (3) & W ← R(x), B(x). \\ (4) & W ← G(x), B(x). \\ (5) & R(x) ∨ G(x) ∨ B(x) ← . \\ (6) & C(x) ← W. \\ (7) & W ← P (x, y, u, v), V (u, v), C(x), C(y). C = R, \\ (8) & W ← N(x, y, u, v), Ṽ (u, v), C(x), C(y). G, B. \end{matrix}

Intuitively, clause (1) chooses a truth value for X_{u,v}. Dependent on that choice, W is computed true if the resulting graph t(G) is not 3-colorable.

Lemma 7.7 Let D be the input database for π_{Col} for an instance I of co-CERT3COL. Then, π_{Col} has a minimal model on D that contains W iff I is a Yesinstance.

Boolean circuit program Let C = {g_{i} : g_{i} = (a_{i}, j, l), 1 ≤ i ≤ t} constitute a Boolean circuit that computes a k-ary relation R over {0, 1}.

We outline a DATALOG^{∨} program π_{C} that simulates C using the fixed input database D_{0} = ({0, 1}, {1}, {0}). (A similar DATALOG^{∨,¬}-program using fixpoint semantics can be found in [KP91].)

The following relations occur in π_{C}: A 0-ary output relation W, unary input relations One and Zero to emulate constants 1 and 0, and for each gate g_{i} a kary auxiliary relation G_{i}.

Informally, G_{i}(x) states that on input of tuple x to C, the circuit computation sets the output of g_{i} to 1.

The program π_{C} consists of the following clauses. For each gate g_{i} = (a_{i}, j, l), it contains the clause

(0) G_{i}(x) ← W;

Depending on the type a_{i} of gate g_{i}, it contains additional clauses as follows.

a_{i} = in: (1) G_{i}(x) ← One(x_{j}) .
(2) W ← G_{i}(x), Zero(x_{j}).
a_{i} = not: (3) G_{i}(x) ∨ G_{j}(x) ← .
(4) W ← G_{j}(x), G_{i}(x).
a_{i} = and: (5) G_{i}(x) ← G_{j}(x), G_{l}(x).
(6) G_{j}(x) ← G_{i}(x).
(7) G_{l}(x) ← G_{i}(x).
a_{i} = or: (8) G_{i}(x) ← G_{j}(x).
(9) G_{i}(x) ← G_{l}(x).
(10) G_{j}(x) ∨ G_{l}(x) ← G_{i}(x).

Assume that g_{t} is the output gate of C. The following can be shown.

Lemma 7.8 π_{C} has a unique minimal model M on D_{0} = ({0, 1}, {1}, {0}), which has the properties that W ∉ M and that G_{t}(t) ∈ M iff C computes 1 on input vector t, for each t ∈ {0, 1}^{k}.

From Theorem 7.6 and Lemmas 7.7 and 7.8, the main theorem of this section can be derived.

Theorem 7.9 The Boolean DATALOG_{b,MM}^{∨} queries are NEXPTIME^{NP}-hard in the program size (resp. combined data and program size).

Proof. (Sketch) Let C_{I} be the Boolean circuit of an instance I of co-CERT3COL of size n. From C_{I}, Boolean circuits C_{P} and C_{N} are constructible in polynomial time that compute P and N, respectively, where each argument x, y, u, and v is encoded by a string of ⌈log n⌉ bits. The circuits output 1 if a tuple is contained in P resp. N and 0 otherwise; for any string representing m with n ≤ m < 2^{⌈log n⌉}, the output is 0. C_{P} and C_{N} can be simulated by DATALOG^{∨} programs π_{C_{P}} and π_{C_{N}} constructible in polynomial time over input database D_{0} as shown above. Let G_{t}^{P} and G_{t}^{N} be the relations corresponding to the output gates g_{t}^{P} and g_{t}^{N} of C_{P} and C_{N}, respectively.

Program π_{Col} can be easily adapted to a variant π_{Col}^{n} where the elements from {0, …, n − 1} are represented by binary strings of length ⌈log n⌉ and all occurrences of P, N are replaced by G_{t}^{P} and G_{t}^{N}, respectively, in time polynomial in log n.

Let the program π_{I} with IO(π_{I}) = (One, Zero; W) consist of the union of π_{Col}^{n}, π_{C_{N}} and π_{C_{P}}. It can be shown that π_{I} has on D_{0} a minimal model that contains W, i.e., query q_{b,MM}^{π_{I}} computes W true on D_{0} iff the considered instance of co-CERT3COL is a Yes-instance. Since π_{I} can be constructed from C_{I} in polynomial time, the result follows. □

Corollary 7.10 The Boolean DATALOG_{b,SM}^{∨} queries and DATALOG_{b,PM}^{∨} queries are NEXPTIME^{NP}-hard in the program size (resp. combined data and program size).

Symmetric results (membership and hardness for Π_{2}^{P} in the data size and for co-NEXPTIME^{NP} in the program size resp. the combined data and program size) hold for the cautious variants of SM and PM, with hardness for Boolean DATALOG^{∨,¬} queries.

Acknowledgment We are indebted to P.A. Bonatti, Ph. Kolaitis, and J.S. Schlipf for several important hints and comments.

References

[ASV90] A. Abiteboul, E. Simon, and V. Vianu. Non-Deterministic Languages to Express Deterministic Transformations. In Proceedings PODS-90, pp. 218–229, 1990.

[AV91] S. Abiteboul and V. Vianu. Datalog Extensions for Database Updates and Queries. Journal of Computer and System Sciences, 43:62–124, 1991.

[BLT92] J.L. Balcázar, A. Lozano, and J. Torán. The Complexity of Algorithmic Problems on Succinct Instances. In R. Baeta-Yates and U. Manber, editors, Computer Science, pp. 351–377. Plenum Press, New York, 1992.

[BF87] N. Bidoit and C. Froidevaux. Minimalism Subsumes Default Logic and Circumscription in Stratified Logic Programming. In Proceedings LICS-87, pp. 89–97. IEEE Press, 1987.

[CEG94] M. Cadoli, T. Eiter, and G. Gottlob. Using Default Logic as a Query Language. In Proceedings KR-94, 1994. Forthcoming.

[CH85] A. Chandra and D. Harel. Horn Clause Queries and Generalizations. Journal of Logic Programming, 2:1–15, 1985.

[CK73] C. C. Chang and H. J. Keisler. Model Theory. North-Holland, 2nd edition, 1973.

[Dix92] Jürgen Dix. Classifying Semantics of Disjunctive Logic Programs. In Proceedings JICSLP-92, pp. 798–812, Washington DC, November 1992.

[EG93] T. Eiter and G. Gottlob. Complexity Aspects of Various Semantics for Disjunctive Databases. In Proceedings PODS-93, pp. 158–167, June 1993.

[Fag74] R. Fagin. Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. In R. M. Karp, editor, Complexity of Computation, pp. 43–74. AMS, 1974.

[GL88] M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In Proc. Fifth Logic Programming Symposium, pp. 1070–1080, Cambridge Mass., 1988. MIT Press.

[Gur88] Y. Gurevich. Logic and the Challenge of Computer Science. In E. Börger, editor, Trends in Theoretical Computer Science, chapter 1. Computer Science Press, 1988.

[HS91] R. Hull and J. Su. On the Expressive Power of Database Queries with Intermediate Types. Journal of Computer and System Sciences, 43:219–267, 1991.

[IFI94] IFIP-GI. Workshop: Disjunctive Logic Programming and Disjunctive Databases. To be held at 13^{th} IFIP World Computer Congress, Hamburg, August 1994.

[Joh90] David S. Johnson. A Catalog of Complexity Classes. In van Leeuwen [van90], chapter 2.

[Kan90] P. Kanellakis. Elements of Relational Database Theory. In van Leeuwen [van90], chapter 17.

[KP91] Ph.G. Kolaitis and Ch. H. Papadimitriou. Why Not Negation By Fixpoint ? Journal of Computer and System Sciences, 43:125–144, 1991.

[KV90] Ph.G. Kolaitis and M. Vardi. On the Expressive Power of Datalog: Tools and a Case Study. In Proceedings PODS-90, pp. 61–71, 1990.

[KV92] Ph.G. Kolaitis and M. Vardi. Fixpoint Logic vs. Infinitary Logic in Finite-Model Theory. In Proceedings LICS-92, pages 61–71. IEEE Computer Science Press, 1992.

[LMR92] J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming. MIT Press, Cambridge, MA, 1992.

[Lyn82] J.F. Lynch. Complexity Classes and Theories of Finite Models. Mathematical Systems Theory, 15:127–144, 1982.

[McC80] J. McCarthy. Circumscription – A Form of Non-Monotonic Reasoning. Artificial Intelligence, 13:27–39, 1980.

[Min82] J. Minker. On Indefinite Data Bases and the Closed World Assumption. In Proceedings of the 6^{th} Conference on Automated Deduction (CADE), pp. 292–308, 1982.

[MV93] D. Maier and B. Vance. A Call to Order. In Proceedings PODS-93, pp. 1–16, 1993.

[Prz88] T. Przymusinski. On the Declarative and Procedural Semantics of Stratified Deductive Databases. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 193–216. Morgan Kaufman, 1988.

[Prz91] T. Przymusinski. Stable Semantics for Disjunctive Programs. New Generation Computing, 9:401–424, 1991.

[PY85] C.H. Papadimitriou and M. Yannakakis. A Note on Succinct Representations of Graphs. Information and Computation, 71:181–185, 1985.

[Sch90] J.S. Schlipf. The Expressive Powers of Logic Programming Semantics. Technical Report CIS-TR-90-3, Computer Science Department, University of Cincinnati, 1990. Proceedings PODS-90, pp. 196–204. Full paper in JCSS, to appear.

[Ste91] I. Stewart. Complete Problems Involving Boolean Labelled Structures and Projection Transactions. Journal of Logic and Computation, 1(6):861–882, 1991.

[Sto77] L. J. Stockmeyer. The Polynomial-Time Hierarchy. Theoretical Computer Science, 3:1–22, 1977.

[Van87] D. Van Gucht. On the Expressive Power of the Extended Relational Algebra for the Unnormalized Relational Model. In Proceedings PODS-87, pp. 302–312, 1987.

[van90] J. van Leeuwen, editor. Handbook of Theoretical Computer Science. Elsevier Science Pub, 1990.

[Var82] M. Vardi. Complexity of relational query languages. In Proceedings STOC-82, pp. 137–146, 1982.

[vRS91] A. van Gelder, K.A. Ross, and J.S. Schlipf. The Well-Founded Semantics for General Logic Programs. JACM, 38(3):620–650, 1991.

[VVAG92] J. Van den Bussche, D. Van Gucht, M. Andries, and M. Gyssens. On the Completeness of Object Creating Query Languages. In Proceedings FOCS-92, pp. 372–379, 1992.

[YH85] A. Yahya and L. Henschen. Deduction in Non-Horn Databases. Journal of Automated Reasoning, 1(2):141–160, 1985.