In: Proceedings of the Twelth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-93), 1993, pp. 158–167.

Complexity Aspects of Various Semantics for Disjunctive Databases

Thomas Eiter and Georg Gottlob

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

Christian Doppler Laboratory for Expert Systems Information Systems Department, Vienna University of Technology

Paniglgasse 16, A-1040 Wien, Austria

Abstract

This paper addresses complexity issues for important problems arising with disjunctive databases. In particular, the complexity of inference of a literal and a formula from a propositional disjunctive database under a variety of wellknown disjunctive database semantics is investigated, as well deciding whether a disjunctive database has as model under a particular semantics. The problems are located in appropriate slots of the polynomial hierarchy.

1 Introduction

Allowing to store disjunctions in a logical database is indispensable for dealing with disjunctive information. Accordingly, the meaning of a disjunctive database is expressed by a set of models instead of a single model as in case of nondisjunctive databases. A variety of different semantics for disjunctive databases has been proposed in the literature; see [9] for a comprehensive overview. We will deal with the following ones.

• The Generalized Closed World Assumption (GCWA) by Minker [16].

• The Extended Generalized Closed World Assumption (EGCWA) by Yahya and Henschen [30].

• The Careful Closed World Assumption (CCWA) by Gelfond and Przymusinska [11].

• The Disjunctive Database Rule (DDR) by Ross and Topor [23], which is equivalent to the Weak GCWA of Rajasekar, Lobo, and Minker [21].

\begin{matrix}c \\ ◯ \end{matrix} 1993 ACM 0-89791-593-3/93/0005/0158...$1.50

• The Extended Closed World Assumption (ECWA) by Gelfond, Przymusinska, and Przymusinski [12], which is in the finite propositional case equivalent to McCarthy’s circumscription as defined by Lifschitz in [14] (CIRC).

• The Possible Worlds Semantics (PWS) by Chan [5], which turned out equivalent to the independently developed Possible Models Semantics (PMS) of Sakama [24].

• The Perfect Models Semantics (PERF) by Przymusinski [19] and the Iterated Closed World Assumption (ICWA) by Gelfond, Przymusinska, and Przymusinski [12] introduced for capturing PERF under stratified negations.

• The (Partial) Disjunctive Stable Model Semantics (DSM, PDSM) as defined by Przymusinski [20] to extend Gelfond and Lifschitz’s Stable Semantics [10] and the Well-Founded Semantics of van Gelder, Ross, and Schlipf [29].

Much work has been spent on studying the logical properties of these semantics, but less on complexity issues and tractability in the propositional case, cf. [4, 27]. Cadoli and Lenzerini present in [3] a careful complexity analysis of inference from a propositional database under several semantics from above (GCWA, EGCWA, CCWA, ECWA, CIRC) for syntactically restricted cases. Eiter and Gottlob complemented their work with results for arbitrary propositional databases [7]. Marek and Truszczyński [15] and Bidoit and Froidevaux [2] independently showed that deciding whether a nondisjunctive database has a stable model is NP-complete. Chan [5] considered the complexity of inference of a literal under GCWA, DDR and PWS. He proved that inferring a literal from a propositional database in which no integrity clauses (i.e. clauses with empty heads) occur is coNP-hard under GCWA, but polynomial under DDR and PWS. Chan proved that if integrity clauses are present, the problem becomes coNP-complete for DDR as well as PWS. In recent papers, Schaerf derived complexity results for non-Horn logic programs [25, 26]. In [25], using results in [7] he derived Σ_{2}^{P} - and Π_{2}^{P} -completeness results for positivistic models and minimally-supported models. In [26] he analyzed the complexity of weakly-stable and weaklysupported models of non-Horn programs, showing that in both cases deciding whether a formula is true in at least one such model is NP-complete and that deciding whether a formula is true in all such models is coNPcomplete. In this paper, we present complexity results for inference tasks under the above mentioned semantics for disjunctive databases. As in [5], we limit our analysis to propositional (i.e. grounded) databases. Some of the results concerning GCWA, EGCWA, CCWA, CCWA, and CIRC appear in weaker form in [7]; note that the results in the present paper constitute a substantial improvement as they are derived for databases without integrity clauses. The proofs given in [7] do not apply to the cases we consider here. In particular, we consider the following inference problem: Given a finite disjunctive propositional database DB and a propositional formula F, is F satisfied by all disjunctive models of DB ? We pay special attention to the traditionally most important subcase where F is a single literal L. Besides the inference problem, we address the problem of deciding whether the database has a model. As [5], we consider both problems also for databases without integrity clauses. The results of this paper, together with previous results and results by other authors (marked by ^{∗}), are summarized in Tables 1 and 2. They may be interpreted as follows. If the polynomial hierarchy does not collapse into some class below Π_{2}^{P}, the inference problem is for almost all semantics strictly harder than classical inference, even in case of positive databases, i.e. databases without integrity clauses and negation “¬”. An intuitive explanation for Π_{2}^{P} -hardness is that due to some minimality criterion, the problem of identifying a disjunctive model is difficult and involves an (at least) coNP-hard test. This constitutes a source of complexity “orthogonal” to the source given by the potentially exponentially many candidates for a disjunctive model of DB. As a consequence of the results, under the assumption polynomial inference algorithms using an oracle for classical inference do not exist. Inference of a formula under GCWA or CCWA is an interesting problem: the best upper bound we can provide by a nontrivial membership proof is P^{Σ_{2}^{P} [O(log n)]}, which is “mildly” harder than Π_{2}^{P} or Σ_{2}^{P}. Completeness for this class would entail Σ_{2}^{P} -hardness; however, it is not clear how to reduce a Σ_{2}^{P} -complete problem to these problems. Literal inference under GCWA is in Π_{2}^{P}, as it suffices to check a restricted set of DB models. Chan [5] shows that inference under DDR and PWS (which exclude “¬”) is tractable if integrity clauses are not allowed; this in fact constitutes the only cases of tractability for one of the considered semantics. If integrity clauses are permitted, both semantics are “merely” coNP-complete and thus still “easier” than all others. Since PWS is more intuitive than DDR, the complexity point of view supports choosing PWS. It is interesting to observe that for PERF, DSM, and PDSM semantics, deciding whether DB has a model is likely to be more complex than for the other semantics. For all of them this is equivalent to deciding if the database has a model under classical semantics, from which the respective entries in Tables 1 and 2 are easily verified. Σ_{2}^{P} -hardness of DSM and PDSM may be intuitively explained by an additional source of complexity in terms of a fixpoint condition on a model which interacts with an independent minimality criterion. PERF similarly imposes a minimality condition on models, which again leads to the lower bound of Σ_{2}^{P} -hardness. The rest of the paper is organized as follows. Section 2 provides definitions and notation. All further sections are devoted to justify the remaining entries in the tables. Following the classification in [9], we deal in Sections 3–5 with semantics for disjunctive deductive DBs, disjunctive stratified DBs, and disjunctive normal DBs. The various semantics can be alternatively characterized proof-theoretically, by fixpoints, or in terms of models, cf. [9]. We refer here only to model theoretic characterizations, which are heavily used for deriving the results. Full proofs of the results can be collected from [8], which extends on the material of this paper in the context of logic programming.

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.

ACM-PODS-5/93/Washington, D.C.

2 Preliminaries and Notation

We consider propositional databases over a finite set V of propositional variables. Denote by C the set of clauses

a_{1} ∨ ⋯ ∨ a_{n} ← b_{1} ∧ ⋯ ∧ b_{k} ∧ ¬b_{k+1} ∧ ⋯ ∧ ¬b_{m}, n, m ≥ 0,

where all a_{i} and b_{j} are from V. The set of clauses in which “¬” does not occur is denoted by C^{+}. A disjunctive database (DDB) DB is a finite set of clauses from C. According to the classification of [9], any such DB is a disjunctive normal database (DNDB) in general; it is a disjunctive deductive database (DDDB) if DB ⊆ C^{+}, and a disjunctive stratified database (DSDB)

Table 1: Complexity results for positive propositional DDBs (i.e. without integrity clauses and negation)

Semantics  Inference of literal  Inference of formula  ∃ model
GCWA  Π_{2}^{P} -complete  Π_{2}^{P} -hard, in P^{Σ_{2}^{P} [O(log n)]}
DDR (≡WGCA)  in P ^{∗}[5]  coNP-complete
PWS (≡PMS)  in P ^{∗}[5]  coNP-complete
EGCWA  Π_{2}^{P} -complete  O(1)
CCWA  Π_{2}^{P} -hard, in P^{Σ_{2}^{P} [O(log n)]}
ECWA (≡CIRC)  Π_{2}^{P} -complete
ICWA  Π_{2}^{P} -complete
PERF  Π_{2}^{P} -complete
DSM, PDSM  Π_{2}^{P} -complete

Table 2: Complexity results for propositional DDBs (with integrity clauses)

Semantics  Inference of literal  Inference of formula  ∃ model
GCWA  Π_{2}^{P} -complete  Π_{2}^{P} -hard, in P^{Σ_{2}^{P} [O(log n)]}
DDR (≡WGCA) coNP-complete ^{∗}[5]  coNP-complete
PWS (≡PMS) coNP-complete ^{∗}[5]  coNP-complete
EGCWA  Π_{2}^{P} -complete  NP-complete
CCWA  Π_{2}^{P} -hard, in P^{Σ_{2}^{P} [O(log n)]}
ECWA (≡CIRC)  Π_{2}^{P} -complete
ICWA^{⋄}  Π_{2}^{P} -complete  O(1)
PERF  Π_{2}^{P} -complete  Σ_{2}^{P} -complete
DSM, PDSM  Π_{2}^{P} -complete  Σ_{2}^{P} -complete

⋄ defined here without integrity clauses

if negation is allowed in a structured way. A clause with n = 0 is called an integrity clause. We refer to a DDB which is a DDDB and in which no integrity clauses occur as positive DDB. For any semantics C, by C(DB) we denote the set of models of DB under this semantics. M(DB) denotes the set of all Herbrand models of DB (i.e. model M is the set of propositional variables true in M). The partial order ≤ on M(DB) is defined by M ≤ M′ iff M ⊆ M′, i.e., all variables true in M are also true in M′, and for a partition ⟨P; Q; Z⟩ of V, the preorder ≤_{P;Z} by M ≤_{P;Z} M′ iff M ∩ Q = M′ ∩ Q and M ∩ P ⊆ M′ ∩ P. Note that ≤_{P;Z} coincides with ≤ if P = V. Model M ∈ M(DB) is minimal (resp. ⟨P; Z⟩-minimal) iff no M′ ∈ M(DB) satisfies M′ ≤ M and M ≰ M′, (resp. M′ ≤_{P;Z} M and M ≰_{P;Z} M′). The minimal (resp. ⟨P; Z⟩-minimal) models of DB are denoted by MM(DB) (resp. MM(DB; P; Z)).

Example 2.1 Consider the database

DB = {a ∨ b ← c, b ← ¬a ∧ ¬c},

where V = {a, b, c}. Then, M(DB) = {{b}, {a}, {a, b}, {a, c}, {b, c}, {a, b, c}}. Furthermore MM(DB) = {{a}, {b}}, and for the partition ⟨{a}, {b}, {c}⟩ of V, we have MM(P; {a}; {c}) = {{b}, {b, c}, {a}, {a, c}}.

Refer to [13] for concepts and notation of complexity theory. Recall that the classes Σ_{k}^{P}, Π_{k}^{P}, of the polynomial hierarchy are defined by Σ_{0}^{P} = Π_{0}^{P} = P, and for k ≥ 0, Σ_{k+1}^{P} = NP^{Σ_{k}^{P}}, Π_{k+1}^{P} = coΣ_{k+1}^{P}. In particular, Σ_{2}^{P} = NP^{NP} and Π_{2}^{P} = coNP^{NP}.

The class of decision problems that are polynomially solvable with ≤ f(n) calls to a Σ_{k}^{P} oracle is P^{Σ_{k}^{P} [f(n)]}, where f(n) is a function in the size n of the problem instance.

3 Disjunctive deductive databases

Prior to reviewing the different semantics defined for such databases, we present the following fundamental theorem on a lower complexity bound of inference for many DDB semantics.

Theorem 3.1 Let DB be a positive DDB and let w ∈ V. Deciding if MM(DB) ⊧ ¬w is Π_{2}^{P} -hard.

Proof. (Sketch) We show this by the following reduction of deciding the validity of a quantified Boolean formula Φ = ∀x_{1} ⋯ ∀x_{n}∃y_{1} ⋯ ∃y_{m}E, n, m ≥ 1. We may assume that E = C_{1} ∧ ⋯ ∧ C_{r} and each C_{i} = L_{i,1} ∨L_{i,2} ∨L_{i,3} is a disjunction of literals L_{i,j} over variables x_{1}, …, x_{n}, y_{1}, …, y_{m} as deciding if such a Φ is valid is still Π_{2}^{P} -hard. Let v_{1}, …, v_{n} and z_{1}, …, z_{m}, w be new propositional variables and define the following database DB:

DB = { x_{1} ∨ v_{1} ← , …, x_{n} ∨ v_{n} ← ,

y_{1} ∨ z_{1} ← , …, y_{m} ∨ z_{m} ← ,

w ← y_{1} ∧ z_{1}, …, w ← y_{m} ∧ z_{m},

y_{1} ← w, …, y_{m} ← w,

z_{1} ← w, …, z_{m} ← w,

w ← τ(L_{1,1}) ∧ τ(L_{1,2}) ∧ τ(L_{1,3}),

⋮

w ← τ(L_{r,1}) ∧ τ(L_{r,2}) ∧ τ(L_{r,3}) }

where τ maps literals from x_{1}, …, x_{n}, y_{1}, …, y_{m} to literals as follows:

τ(L) = \{ \begin{matrix}v_{i} & if L = x_{i} \\ z_{j} & if L = y_{j} \\ x_{i} & if L = ¬x_{i} \\ y_{j} & if L = ¬y_{j} \end{matrix}

Intuitively, v_{i} corresponds to ¬x_{i} and z_{j} corresponds to ¬y_{j}. It can be shown that Φ is valid iff MM(T) ⊧ ¬w. □

3.1 GCWA and CCWA

Reiter’s CWA [22] adds to DB each literal ¬x, x ∈ V, such that M(DB) |̸= x. This is not suitable for disjunctive databases since it enforces a unique model of the DB if the result is consistent. (It is interesting to note that deciding whether CWA(DB) is nonempty is coNP-hard and in P^{NP[O(log n)]}, but not in coD^{P} [18] (coD^{P} ⊇ NP ∪ coNP) unless the polynomial hierarchy collapses [7].) Minker adapted the CWA for disjunctive databases by introducing the Generalized CWA (GCWA) in [16], which adds all literals ¬x to DB such that atom x is false in all minimal models of DB. The respective models of DB can be characterized as follows.

GCWA(DB) = {M ∈ M(DB) : ∀x ∈ V.

MM(DB) ⊧ ¬x ⇒ M ⊧ ¬x}

The Careful Closed World Assumption (CCWA) of Gelfond and Przymusinska [11] generalizes the GCWA as follows. For a partition ⟨P; Q; Z⟩ of V, each literal ¬x, x ∈ P, is added to DB such that MM(DB; P; Z) ⊧ ¬x. Thus,

CCWA_{P;Z}(DB) = {M ∈ M(DB) : ∀x ∈ P. MM(DB; P; Z) ⊧ ¬x ⇒ M ⊧ ¬x}

Notice that if P = V, CCWA is identical to GCWA. It is immediate from the definition that GCWA(DB) ⊧ ¬x iff MM(DB) ⊧ ¬x for any x ∈ V. Thus from Theorem 3.1,

Theorem 3.2 Inference of a literal from a positive DDDB DB without integrity clauses is Π_{2}^{P} -hard under GCWA as well as CCWA.

For GCWA, this lower bound is also an upper bound.

Theorem 3.3 Literal inference under GCWA is in Π_{2}^{P}.

Proof. A guess for M ∈ MM(DB) such that M |̸= L for L a literal, can be verified in polynomial time with an NP oracle, since deciding M_{1} ≤ M_{2} is clearly polynomial. □

To derive an Π_{2}^{P} upper bound for literal inference under CCWA in an analogous way fails since for deciding CCW A_{P;Z}(DB) ⊧ ¬x, if x ∈ Q ∪ Z, checking only ⟨P; Z⟩-minimal models is not correct in general. (However, for x ∈ P this is possible). Formula inference can be easily done with O(|P |) calls to a Σ_{2}^{P} oracle by first deciding MM(DB) ⊧ ¬x for each x ∈ P using the oracle. This upper bound can be improved to a logarithmic number of oracle calls.

Theorem 3.4 Formula inference under CCWA (resp. GCWA) can be done with O(log |P |) (resp. O(log |V |)) calls to a Σ_{2}^{P} oracle; thus the problem is in P^{Σ_{2}^{P} [O(log n)]}.

Proof. (Sketch) We outline a polynomial-time algorithm that makes only O(log |P |) calls to a Σ_{2}^{P} oracle for CCWA (cf. [7] for this method). Notice that GCWA coincides with CCWA for Q = Z = ∅, hence P = V. The basic idea is to proceed in two steps. Given DB and F, first the number r of variables x from P such that MM(DB; P; Z) |̸= ¬x is computed. This can be done in a binary search with O(log |P |) calls to the Σ_{2}^{P} oracle: r ≥ k iff there exist M_{1}, … M_{k} ∈ MM(DB; P; Z) such that | ⋃_{i=1}^{k} M_{i}| ≥ k; since deciding M ∈ MM(DB; P; Z) is in coNP, deciding r ≥ k is in Σ_{2}^{P}. If r is known, a guess for M ∈ CCW A_{P;Z}(DB) such that M |̸= F can be witnessed by a polynomial sized structure S constituting a “proof” of M ∈ CCW A_{P;Z}(DB), which can be checked in polynomial time with an NP oracle. S is as follows:

S = ⟨{x_{1}, …, x_{r}}, (M_{1}, …, M_{r}), M⟩

where x_{1}, …, x_{r} are pairwise distinct variables, M_{1}, …, M_{r} ∈ MM(DB; P; Z) satisfying x_{i} ∈ M_{i} for 1 ≤ i ≤ r, and M ∈ M(DB) such that M ⊆ {x_{1}, …, x_{r}} and M |̸= F. Thus the second step is to query the Σ_{2}^{P} oracle whether such an M exists. □

3.2 DDR, WGCWA, PWS, and PMS Given DB and a Herbrand interpretation I of DB, define

T_{DB}(I) = {a_{i} : a_{1} ∨ ⋯ ∨ a_{n} ← b_{1} ∧ ⋯ ∧ b_{k}

andb_{j} ∈ I, for all j = 1, … k},

and

T_{DB}↑0 = ∅,
T_{DB}↑n + 1 = T_{DB}(T_{DB}↑n), and
T_{DB}↑ω = ⋃_{n=0}^{∞} T_{DB}↑n.

The Disjunctive Database Rule (DDR) of Ross and Topor [23] can be characterized as follows.

DDR(DB) = {M ∈ M(DB) :

x ∈ V − T_{DB}↑ω ⇒ M ⊧ ¬x},

i.e. the DDR adds to DB all literals ¬x where atom x does not occur in T ↑ ω. The DDR semantics is equivalent to the Weak GCWA of Rajasekar, Lobo, and Minker [21]. Since T_{DB}↑ω can be computed efficiently, the complexity results on formula inference in Tables 1 and 2 are obvious; the entries on literal inference were proven by Chan [5]. Chan improved the DDR semantics by taking care of integrity clauses in DB, which are not respected by DDR.

Example 3.1 Let

DB = {a ∨ b ← , ← a ∧ b, c ← a ∧ b}.

Then DDR(DB) |̸= ¬c. Under Chan’s Possible Worlds Semantics (PWS), however, PWS(DB) ⊧ ¬c as suggested by intuition.

Informally, PWS augments DB by all literals ¬x such that x is false in all possible worlds of DB. We use Chan’s characterization of PWS in terms of the equivalent Possible Models Semantics of Sakama [24]. A split database of DB is any database obtained if every clause

a_{1} ∨ ⋯ ∨ a_{n} ← b_{1} ∧ ⋯ ∧ b_{m}, n ≥ 2,

in DB is replaced by Horn clauses

a_{p} ← b_{1} ∧ ⋯ ∧ b_{m}, for p ∈ N,

for some nonempty N ⊆ {1, …, n}. Let SDB(DB) be the family of all split databases of DB. Then,

PWS(DB) = {M ∈ MM(DB′) : DB′ ∈ SDB(DB)}.

Theorem 3.5 Formula inference for PWS and PMS is coNP-complete.

Proof. (Sketch) Guess M ∈ PWS(DB) and DB′ ∈ SDB(DB) to verify M; as DB′ is Horn, it has in case of consistency a unique minimal model M′, which is efficiently computable. If M′ = M and M |̸= F, then PWS(DB) |̸= F. ^{1} Hardness follows from Chan’s result on literal inference [5]. □

3.3 EGCWA, ECWA, and CIRC The Extended GCWA (EGCWA) was introduced by Yahya and Henschen [30] for inferring integrity clauses. DB is augmented by each integrity clause ← a_{1}∧⋯∧a_{n} that is true in every minimal model of DB. It holds that

EGCWA(DB) = MM(DB).

The EGCWA is generalized by the Extended CWA (ECWA) of Gelfond, Przymusinska, and Przymusinski [12] in the following way. For a partition ⟨P; Q; Z⟩ of V,

ECWA_{P;Z}(DB) = MM(DB; P; Z).

1Chan follows a different proof.

EGCWA results if Q = Z = ∅. ECWA is equivalent to circumscription (CIRC) as defined by Lifschitz in [14]. For ⟨P; Q; Z⟩, let

Circ(DB; P; Z) = DB[P; Z] ∧
¬∃P′Z′(DB[P′; Z′] ∧ (P′ < P))

(cf. [14] for details). Then

CIRC_{P;Z}(DB) = M(Circ(DB; P; Z)).

It holds that CIRC_{P;Z}(DB) = MM(DB; P; Z) [14], hence CIRC_{P;Z}(DB) = ECWA_{P;Z}(DB). Notice that this holds as we have propositional databases, cf. [12].

Theorem 3.6 Literal inference from a positive DDB DB is Π_{2}^{P} -hard under EGCWA, ECWA, and CIRC.

Proof. Immediate from Theorem 3.1 □

Theorem 3.7 Formula inference under EGCWA, ECWA, and CIRC is in Π_{2}^{P}.

Proof. (Sketch) Clearly, M_{1} ≤_{P;Z} M_{2} is efficiently decidable for any models M_{1} and M_{2}. Thus a guess for M ∈ MM(DB; P; Z) such that M |̸= F can be verified in polynomial time with an NP oracle. □

4 Disjunctive stratified databases

The concept of stratification of DNDBs, which has been discussed by Chandra and Harel [6], was independently introduced for logic programs by Apt, Blair, and Walker [1] and van Gelder [28]; Przymusinski generalized it to DDB [19]. A DNDB DB without integrity clauses is stratified iff it is possible to partition V into strata ⟨S_{1}, …, S_{r}⟩, such that for every

a_{1} ∨ ⋯ ∨ a_{n} ← b_{1} ∧ ⋯ ∧ b_{k} ∧ ¬c_{1} ∧ ⋯ ∧ ¬c_{m}

in DB there exists a constant c, 1 ≤ c ≤ r, such that ∀i Stratum(a_{i}) = c , ∀j Stratum(b_{j}) ≤ c, and ∀l Stratum(c_{l}) < c, where Stratum(x) = i iff x ∈ S_{i}. Any such ⟨S_{1}, …, S_{r}⟩ is a stratification of DB.^{2} Notice that a stratification of DB can be efficiently found. Gelfond, Przymusinska, and Przymusinski [12] defined the Iterated CWA (ICWA) as iterated application of ECWA to a DSDB. Let ⟨P; Q; Z⟩ be a partition of V and S = ⟨S_{1}, …, S_{r}⟩ a stratification of DB, and let P_{i} = P ∩ S_{i}, Z_{i} = Z ∩ (S_{1} ∪ ⋯ ∪ S_{i}), 1 ≤ i ≤ r, and let DB_{i}, 1 ≤ i ≤ r, be the clauses from DB that contain only literals from S_{j}, j ≤ i, in their heads modified by moving each ¬x in the body to the head. The ICWA of DB can be characterized as follows (cf. [12]).

ICWA_{P_{1};Z_{1}}(DB_{1}) = ECWA_{P_{1};Z_{1}}(DB_{1}),
ICWA_{P_{1}>···>P_{n+1};Z_{n+1}}(DB_{n+1}) =
ECWA_{P_{n+1};Z_{n+1}}(DB_{n+1} ∪

F(ICWA_{P_{1}>···>P_{n};Z_{n}}(DB_{n}))), n > 0,

ICWA_{P_{1}>···>P_{r};Z}(DB) = ICWA_{P_{1}>···>P_{r};Z_{r}}(DB_{r}),

where F(M) is some DDDB DB′ such that M(DB′) = M. Stratifiability asserts consistency; if DB is stratified by S, then ICWA is consistent for any ⟨P; Q; Z⟩ [12]. For inference, we have the following upper bound.

Theorem 4.1 Given ⟨P; Q; Z⟩ and S, formula inference under ICWA is in Π_{2}^{P}.

Proof. By results in [12, Section 6], ICWA is given by the following intersection of ECWAs:

ICWA_{P_{1}>···>P_{r};Z}(DB) =

⋂_{i=1}^{r} ECWA_{P_{i};P_{i+1}∪···∪P_{r}∪Z}(DB_{1} ∪ ⋯ ∪ DB_{r}).

Since for each P′, Z′, and DB′ a guess for M ∈ ECWA_{P′;Z′}(DB′) can be verified in polynomial time with an NP oracle (cf. proof of Theorem 3.7), the same is possible for a guess of M ∈ ICWA_{P_{1}>···>P_{r};Z}(DB) such that M |̸= F. □

From Theorem 3.1 immediately follows (set S = ⟨V ⟩)

Theorem 4.2 Given a stratification S, literal inference from a DSDB DB under ICWA is Π_{2}^{P} -hard, even if DB is positive.

5 Disjunctive normal databases

5.1 PERF

Przymusinski introduced in [19] the Perfect Models Semantics (PERF) for DNDBs without integrity clauses.^{3} The priority relation < on atoms [19], which is similar to stratification, is defined from the structure of DB using an auxiliary relation ⪯ as follows. (Intuitively, x < y means that y has higher priority than x.) For each clause

a_{1} ∨ ⋯ ∨ a_{n} ← b_{1} ∧ ⋯ ∧ b_{k} ∧ ¬c_{1} ∧ ⋯ ∧ ¬c_{m}

from DB, it holds that (i) a_{i} < c_{j}, for all 1 ≤ i ≤ n, 1 ≤ j ≤ m,

2It is not clear how to extend stratification to programs with integrity clauses. Hence, we do not consider such an extension.

3The same definition can be readily extended to general DNDBs by ignoring integrity clauses in the definition of “<”.

The results in the general case remain unchanged [8].

(ii) a_{i} ⪯ b_{j}, for all 1 ≤ i ≤ n, 1 ≤ j ≤ k, and

(iii) a_{i} ⪯ a_{j} for all 1 ≤ i, j ≤ n.

Now < and ⪯ are the smallest extensions to (i)–(iii) which satisfy a < b ⇒ a ⪯ b and which are closed under transitivity, i.e. a ⪯ b, b ⪯ c ⇒ a ⪯ c and a ⪯ b, b < c (resp. d < a) ⇒ a < c (resp. d < b). It is not hard to see that < can be computed in polynomial time.

Definition 5.1 The preference order ≪ on M(DB) is defined by M_{1} ≪ M_{2} iff M_{1} ≠ M_{2} and for each x ∈ M_{1} − M_{2} there exists y ∈ M_{2} − M_{1} with x < y.

Notice that ≪ is efficiently decidable, as easily seen from the definition of <. The perfect models of DNDB DB are as follows.

PERF(DB) = {M ∈ M(DB) : ∀M′ ∈ M(DB).
M′ ≪̸ M}.

It holds that M_{1} < M_{2} ⇒ M_{1} ≪ M_{2}, hence PERF(DB) ⊆ MM(DB). Przymusinski showed that PERF(DB)= MM(DB) if DB is positive; thus from Theorem 3.1,

Theorem 5.1 Literal inference from a DNDB DB under PERF is Π_{2}^{P} -hard, even if DB is positive.

On the other hand, since ≪ is polynomially decidable (cf. proof of Theorem 3.7),

Theorem 5.2 Formula inference from a DNDB DB under PERF is in Π_{2}^{P}.

Unlike the semantics considered so far, PERF semantics is not necessarily consistent if M(DB) is nonempty.

Example 5.1 DB = {p ← ¬q, q ← ¬p} has two minimal models {p} and {q}, but {p} ≪ {q} and {q} ≪ {p}, hence no model of DB can be perfect.

In fact, even if it is known that DB has a model, deciding the existence of a perfect model seems difficult.

Theorem 5.3 Deciding whether a DNDB DB has a perfect model is Σ_{2}^{P} -complete.

Proof. (Sketch) Σ_{2}^{P} is an upper bound for deciding perfect model existence, since a guess for a perfect model can be verified with an NP oracle in polynomial time. Hardness is shown by a reduction from deciding the validity of a ∃∀-quantified Boolean formula

Φ = ∃x_{1} ⋯ ∃x_{n}∀y_{1} ⋯ ∀y_{m}E, n, m ≥ 1,

where E = D_{1} ∨⋯∨D_{r} and each D_{i} = L_{i,1} ∧L_{i,2} ∧L_{i,3} is a conjunction of literals L_{i,j} over atoms x_{1}, …, x_{n}, y_{1}, …, y_{m}. Let v_{1}, …, v_{n} and z_{1}, …, z_{m}, w, w′ be new propositional atoms and define the following DNDB DB:

{x_{i} ∨ v_{i} ← ,  for 1 ≤ i ≤ n
y_{j} ∨ z_{j} ← ,  for 1 ≤ j ≤ m
y_{j} ← w ∧ w′,  z_{j} ← w ∧ w′  for 1 ≤ j ≤ m
w ← y_{j} ∧ z_{j},  w′ ← y_{j} ∧ z_{j} for 1 ≤ j ≤ m

w ∨ w′ ← σ(L_{1,1}) ∧ σ(L_{1,2}) ∧ σ(L_{1,3})

⋮  ⋮

w ∨ w′ ← σ(L_{r,1}) ∧ σ(L_{r,2}) ∧ σ(L_{r,3})

w ← ¬w′,  w′ ← ¬w }

where σ maps literals from atoms x_{1}, …, x_{n}, y_{1}, …, y_{m} to atoms as follows:

σ(L) = \{ \begin{matrix}v_{i} & if L = ¬x_{i} for some i = 1, …, n \\ z_{j} & if L = ¬y_{j} for some j = 1, …, m \\ L & otherwise \end{matrix}

Notice that the interpretation where all variables are true is a model of DB. The structure of DB entails that there exists no variable p such that x_{i} < p or z_{i} < p, for any 1 ≤ i ≤ n, and that for each variable q from {w, w′, y_{1}, z_{1}, …, y_{m}, z_{m}}, it holds that q < w and q < w′. It can be shown that DB has a perfect model iff Φ is valid. □ An interesting case, which has to our best knowledge not analyzed yet, is the one where the database is not disjunctive. Call DB a normal logic program (NLP) if every clause in DB has exactly one atom in its head. We provide some evidence that deciding for the existence of a perfect model is for such programs not in NP ∪ coNP. We show this by a reduction from UMINSAT, which is the problem to decide if a collection C = {C_{1}, …, C_{n}} of propositional clauses has a unique minimal satisfying truth assignment, i.e. whether a logically equivalent DNDB DB has a unique minimal model. The following has been shown in [7].

Proposition 5.4 UMINSAT is coNP-hard and, unless the polynomial hierarchy collapses, UMINSAT does not belong to coD^{P}.

coD^{P} is a complexity class [18] that contains –most likely properly– NP ∪ coNP.

Lemma 5.5 UMINSAT is polynomially transformable to deciding whether a NLP DB has a unique minimal model.

Proof. (Sketch) Let a, b, and c be new atoms not occurring in C. Let DB be a DNDB logically equivalent to C ∪ {¬c}. Clearly, DB has a unique minimal model iff C has a unique minimal satisfying truth assignment. Let the NLP DB′ contain the following clauses:

(1) a ← ¬b ∧ c

(2) x ← c for each atom x occurring in C, and

(3) c ← ¬C_{i} for each C_{i} ∈ C,

where ¬C_{i} is the conjunction of the opposites of all literals in C_{i}. It can be shown that DB′ has a unique minimal model iff DB has a unique model; hence the lemma follows. □

Theorem 5.6 Deciding whether an NLP DB has a perfect model is coNP-hard and, unless the polynomial hierarchy collapses, not in NP ∪ coNP.

Proof. (Sketch) Let DB be an NLP as in Lemma 5.5. Let p be a new atom not occurring in DB, and let DB′ be the NLP obtained from DB by adding for each pair of atoms q, r that occur in DB the clause q ← ¬r ∧ p. This clause assures that q < r holds in DB′. Notice that no minimal model of DB′ contains p. Thus, for any distinct minimal models M and M′ of DB′, M ≪ M′ and M′ ≪ M holds. It can be thus shown that DB′ has a perfect model iff DB′ has a unique minimal model. It holds that DB′ has a unique minimal model iff DB has a unique minimal model. Consequently, DB′ has a perfect model iff DB has a unique minimal model. Thus the result follows from the preceding lemma and proposition. □

For the inference problem, we obtain the following interesting lower bound.

Theorem 5.7 Literal inference from an NLP DB under PERF is NP-hard and, unless the polynomial hierarchy collapses, not in NP ∪ coNP. Proof. (Sketch) Let DB be an NLP and p a propositional atom not occurring in DB. Then, PERF(DB∪{p ← }) ⊧ ¬p iff DB has no perfect model. The result follows from the previous theorem. □

For checking whether a model of a NLP DB is perfect, the following holds.

Theorem 5.8 Deciding whether a model M of an NLP DB is perfect is coNP-complete. Proof. (Sketch) Membership in coNP is easy as a model M′ such that M′ ≪ M can be guessed and verified in polynomial time. For the hardness part, we sketch a polynomial time reduction of deciding whether a DDDB DB′ has no model (M(DB′) = ∅), which is coNP-complete, to deciding whether a model M_{0} of a nondisjunctive database DB is perfect. Assume that DB′ is built on atoms x_{1}, …, x_{n}, and contains clauses

a_{i,1} ∨ ⋯ ∨ a_{i,n_{i}} ← b_{i,1} ∧ ⋯ ∧ b_{i,m_{i}}, 1 ≤ i ≤ r,

where n_{i}, m_{i} ≥ 0. Without loss of generality we may assume that {x_{1}, …, x_{n}} is not a model of DB′. Let a, u, v be new atoms. DB is defined as follows:

DB = {x_{1} ← a, …, x_{n} ← a,
a ← u ∧ v, u ← a, v ← a,
v ← ¬u, u ← ¬v,

a ← b_{1,1} ∧ ⋯ ∧ b_{1,m_{1}} ∧ ¬a_{1,1} ∧ ⋯ ∧ ¬a_{1,n_{1}},

⋮  ⋮

a ← b_{r,1} ∧ ⋯ ∧ b_{r,m_{r}} ∧ ¬a_{r,1} ∧ ⋯ ∧ ¬a_{r,n_{r}} }.

It is easy to see that M_{0} = {x_{1}, …, x_{n}, a, u, v} is a model of DB. Furthermore, it can be checked that for each atom z, it holds that z < u and z < v. Every model M of DB such that M ≠ M_{0} must contain exactly one of u and v and satisfy M ⊧ ¬a; thus, M satisfies DB′. On the other hand, if M is a model of DB′, then M ∪ {u}and M ∪ {v} are models of DB. Hence, it can be shown that M_{0} is a perfect model of DB if and only if DB′ has no model. □

5.2 DSM, PDSM

Generalizing the Stable Model Semantics [10], Przymusinski [20] defined the meaning of a DNDB DB by disjunctive stable models (DSM), which are a subset of the minimal models of DB as follows. For a DNDB DB and a Herbrand interpretation I, the Gelfond-Lifschitz transformation of DB is the database DB^{I}, which contains for each clause

a_{1} ∨ ⋯ ∨ a_{n} ← b_{1} ∧ ⋯ ∧ b_{k} ∧ ¬b_{k+1} ∧ ⋯ ∧ ¬b_{m}

from DB such that b_{i} ∉ I, for all k < i ≤ m, the clause

a_{1} ∨ ⋯ ∨ a_{n} ← b_{1} ∧ ⋯ ∧ b_{k}

and DB^{I} contains nothing else. Then,

DSM(DB) = {M : M ∈ MM(DB^{M})}

In fact, disjunctive stable models of DB are minimal models of DB, i.e. DSM(DB) ⊆ MM(DB) [20]. Notice that if DB ⊆ C^{+}, (i.e. “¬” does not occur in DB), then DB^{I} = DB for every I; hence DSM(DB) = MM(DB). Thus if DB is positive, deciding model existence is trivial. For the general case, Theorem 5.9 Deciding if a DNDB DB has a stable model is Σ_{2}^{P} -hard.

Proof. (Sketch) Let DB be a positive DDB and x ∈ V. Add the clause x ← ¬x to DB and let DB′ be the resulting DB. Then, it holds that DB′ has a stable model iff MM(DB) |̸= ¬x. The result follows from Theorem 3.1. □

Remark: It is not essential that a variable may occur in the head and negated in the body of the same clause to derive this result. As immediate from Theorem 3.1,

Theorem 5.10 Literal inference from a positive DNDB DB under DSM is Π_{2}^{P} -hard.

Theorem 5.11 Formula inference from a DNDB DB under DSM is in Π_{2}^{P}.

Proof. (Sketch) A guess for M ∈ DSM(DB) such that M |̸= F can be verified with an NP oracle in polynomial time (DB^{M} is efficiently computable). □

In [20] also the Partial Disjunctive Stable Model Semantics (PDSM) is introduced, which extends the Well-Founded Semantics of van Gelder, Ross, and Schlipf [29]. It is defined like DSM but using partial (i.e. 3-valued) models, in which true, false, and undefined variables have respective truth values 1, 0, and 0.5. We do not define partial stable models here, and only outline in the sequel how the results in Tables 1 and 2 are derived. The interested reader is referred to [8] for the details. Przymusinski shows that PDSM coincides with DSM if DB is positive; thus the Π_{2}^{P} lower bound on literal inference of DSM carries over to PDSM. On the other hand, under 3-valued truth valuations the generalized Gelfond-Lifschitz transformation DB^{I} is still efficiently computable, and the truth value of a formula is efficiently computable. Furthermore, deciding partial model minimality in this framework is still in coNP. Consequently, a Π_{2}^{P} upper bound on formula inference for PDSM holds, as well as a Σ_{2}^{P} upper bound on model existence in the general case. Since by adding the clause

← x ∧ ¬x

for every x ∈ V, partial stable models can be forced to be total models, the Σ_{2}^{P} lower bound on deciding model existence for DSM carries over also to PDSM. However, integrity clauses are not crucial for proving Σ_{2}^{P} -hardness of PDSM-model existence. It can be shown that this lower bound holds if no integrity clauses are present [8]. Summarizing, we obtain the same complexity results for PDSM as for DSM.

References

[1] K. Apt, H. Blair, and A. Walker. Towards a Theory of Declarative Knowledge. In Minker [17], pages 89–148.

[2] N. Bidoit and C. Froidevaux. Negation by default and unstratifiable programs. Theoretical Computer Science, 78:85–112, 1991.

[3] M. Cadoli and M. Lenzerini. The Complexity of Closed World Reasoning and Circumscription. In Proceedings AAAI-90, pages 550–555, 1990.

[4] M. Cadoli and M. Schaerf. A Survey on Complexity Results for Non-monotonic Logics. Technical report, Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, 1992. Journal of Logic Programming, to appear.

[5] E. Chan. A Possible Worlds Semantics for Disjunctive Databases. IEEE Transactions on Data and Knowledge Engineering, 1991. To appear.

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

[7] T. Eiter and G. Gottlob. Propositional Circumscription and Extended Closed World Reasoning are Π_{2}^{P} - complete. Technical Report CD-TR 91/20, Christian Doppler Laboratory for Expert Systems, Vienna University of Technology, Austria, May 1991. To appear in Theoretical Computer Science.

[8] T. Eiter and G. Gottlob. On the Computational Cost of Disjunctive Logic Programming: Propositional Case. Manuscript, March 1993.

[9] J. Fernández and J. Minker. Semantics of Disjunctive Deductive Databases. In Proceedings ICDT-92, pages 21–50, Berlin, October 1992.

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

[11] M. Gelfond and H. Przymusinska. Negation as Failure: Careful Closure Procedure. Artificial Intelligence, 30:273–287, 1986.

[12] M. Gelfond, H. Przymusinska, and T. Przymusinski. On the Relationship Between Circumscription and Negation as Failure. Artificial Intelligence, 38:75–94, 1989.

[13] D. S. Johnson. A Catalog of Complexity Classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, chapter 2. Elsevier Science Publishers B.V. (North-Holland), 1990.

[14] V. Lifschitz. Computing Circumscription. In Proceedings IJCAI-85, pages 121–127, 1985.

[15] W. Marek and M. Truszczyński. Autoepistemic Logic. Journal of the ACM, 38(3):588–619, 1991.

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

[17] J. Minker, editor. Foundations of Deductive Databases and Logic Programming. Morgan Kaufman, Washington DC, 1988.

[18] C. H. Papadimitriou and M. Yannakakis. The Complexity of Facets (And Some Facets of Complexity). Journal of Computer and System Sciences, 28:244–259, 1984.

[19] T. Przymusinski. On the Declarative and Procedural Semantics of Stratified Deductive Databases. In Minker [17], pages 193–216.

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

[21] A. Rajasekar, J. Lobo, and J. Minker. Weak Generalized Closed World Assumption. Journal of Automated Reasoning, 5:293–307, 1989.

[22] R. Reiter. On Closed-World Databases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 55–76. Plenum Press, New York, 1978.

[23] K. Ross and R. Topor. Inferring Negative Information From Disjunctive Databases. Journal of Automated Reasoning, 4(2):397–424, 1988.

[24] C. Sakama. Possible Model Semantics for Disjunctive Databases. In Proceedings 1st Intl. Conf. DOOD-89, pages 337–351, Kyoto Japan, 1989.

[25] M. Schaerf. Logic Programming and Autoepistemic Logics: New Relations and Complexity Results. Submitted, December 1992.

[26] M. Schaerf. Negation and Minimality in Non-Horn Databases. In Proceedings PODS-93, 1993.

[27] J. Schlipf. A Survey of Complexity and Undecidability Results in Logic Programming. In H. Blair, W. Marek, A. Nerode, and J. Remmel, editors, Informal Proceedings of the Workshop on Structural Complexity and Recursion-Theoretic Methods in Logic Programming, pages 93–102, Washington DC, November 13 1992. Cornell University, Mathematical Sciences Institute.

[28] A. van Gelder. Negation as Failure Using Tight Derivations for General Logic Programs. In Minker [17], pages 1149–1176.

[29] A. van Gelder, K. Ross, and J. Schlipf. The Well-Founded Semantics for General Logic Programs. Journal of the ACM, 38(3):620–650, 1991.

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