Expressive Power and Complexity of Partial Models for Disjunctive Deductive Databases

Thomas Eiter, Nicola Leone, Domenico Saccà

Christian Doppler Labor für Expertensyteme Technische Universität Wien Paniglgasse 16, 1040 Wien

August 19, 1995

CD-TR 95/83

Expressive Power and Complexity of Partial Models for Disjunctive Deductive Databases

T. Eiter  N. Leone  D. Saccà
Christian Doppler Lab.  ISI-CNR  DEIS
Technische Universitat Wien  c/o DEIS-UNICAL,  Università della Calabria,
1040 Vienna, Austria  87030 Rende, Italy  87030 Rende, Italy

eiter@dbai.tuwien.ac.at    nik@si.deis.unical.it   sacca@si.deis.unical.it

preliminary report

Abstract

This paper investigates the expressive power and complexity of partial model semantics for disjunctive deductive databases. In particular, partial stable, regular model, maximal stable (M-stable), and least undefined stable (L-stable) semantics for function-free disjunctive logic programs are considered, for which the expressiveness of queries based on possibility and certainty inference is determined. On the complexity side, we determine the data and expression complexity of query evaluation. The analysis pays particular attention to the impact of syntactical restrictions on programs in the form of limited use of disjunction and negation.

It appears that the considered semantics capture complexity classes at the lower end of the polynomial hierarchy. In fact, each class Σ_{i}^{P}, Π_{i}^{P} 1 ≤ i ≤ 3 is captured by some semantics using appropriate syntactical restrictions. Partial stable models have exactly the same expressive power and complexity as total stable models (Σ_{2}^{P} resp. Π_{2}^{P}), while a higher degree of expressiveness is obtained by the semantics which minimize undefinedness (M-stable, regular, and L-stable semantics). In particular, L-stable semantics has the highest expressive power (Σ_{3}^{P} resp. Π_{3}^{P}). An interesting result in this course is that, in contrast with total stable models, negation is for partial stable models more expressive than disjunction.

For the data complexity of queries, we obtain completeness results for the classes Σ_{i}^{P}, Π_{i}^{P}, i ≤ 3, and, for the expression complexity, completeness results for the analogous classes at the lower end of the weak exponential hierarchy.

The results of this paper complement and extend previous results, and contribute to a more complete picture of the computational aspects of disjunctive logic programming and databases, which supports in choosing an appropriate setting that fits the needs in practice.

Keywords: Deductive Databases, Expressive Power, Complexity, Disjunctive Logic Programming, Partial Model Semantics.

Contents

1 Introduction 1

2 Partial Model Semantics 4 2.1 Disjunctive Logic Programs . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 P-stable Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Restricted Classes of P-stable Models . . . . . . . . . . . . . . . . . . . . 8 2.4 Regular Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5 Relationships between Models . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.6 Deterministic Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3 Expressive Power 12 3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 The Power of PS Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 The Power of MS Semantics . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4 The Power of LS Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.5 The Power of RS semantics . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4 Complexity 22 4.1 Data Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 Expression Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5 The Impact of Disjunction and Negation 24

6 Conclusion 32

A Appendix 34

1 Introduction

The study of integrating databases with logic programming opened in the past the research field of deductive databases. Basically, a deductive database is a logic program without function symbols, i.e., a datalog program (extended with negation) [54, 14]. A number of advanced deductive database systems have been developed that utilize logic programming and extensions thereof for querying relational databases [13, 15, 36, 43, 45].

The need for representing disjunctive (or incomplete) information led to disjunctive deductive databases [40], for which a generalization of the closed world assumption (CWA) had to be devised, whose complexity has been first analyzed in [17]. Disjunctive deductive databases can be basically seen as disjunctive logic programs without function symbols, i.e., disjunctive datalog (DATALOG^{∨,¬}) programs (simply programs in the following) [26].

Several alternative semantics for (disjunctive) programs based on total models have been proposed, e.g. [28, 40, 44, 50] (see [3, 19, 38] for comprehensive surveys). A widely accepted semantics is the extension of the stable model semantics [27] to disjunctive programs [28, 44]. This semantics coincides with the minimal model semantics [40] on negation-free (¬-free) programs and with the perfect model semantics [44] on stratified programs. Stable model semantics for disjunctive program has quite high expressive power, as it captures the complexity class Σ_{2}^{P} (i.e., it allows to express all (and only) database properties that are decidable in non-deterministic polynomial time with an oracle in NP) [29, 22].

Despite its relevance, a severe drawback of total stable semantics is that it does not assign a model to each program. In particular, meaningful programs may have no total stable model. To overcome this drawback, a number of partial model semantics have been recently proposed, which relax the notion of total stable model and assign a meaning to a wider class of programs [5, 23, 44, 49, 48, 57, 58]. In a sense, these partial models “approximate” total stable models.

The first relaxation of total stable was the notion of partial stable model (also called 3-valued stable or P-stable model) proposed by Przymusinski in [44]. Compared to total stable models, partial stable models conservatively extend the class of programs for which an acceptable model exists; in particular, every disjunction-free (∨-free) program has some partial stable model, while it may lack a total stable model. Moreover, on the class of (disjunctive) stratified programs, partial stable models coincide with total stable models.

Objections to partial stable models came from the observation that every 3-valued model theoretic approach should meet the principle of minimal undefinedness [57, 58], which prescribes that the undefined truth value should be used only when necessary (i.e., a “good” semantics should tend to minimize the set of undefined atoms). The attempt to minimize undefinedness in partial models led to three main notions of partial models: maximal stable, regular, and least undefined stable models.

The maximal stable (M-stable) models [23, 47, 48] are those partial stable models which are maximal under set inclusion (where a partial model is represented by the set of ground literals true in the model). On disjunction-free programs, M-stable models coincide with the preferred extensions of [20], the regular models of [57], the maximal stable classes of [5], and the M-stable models of [48, 47], as shown in [24, 23, 59].

The notion of regular model [57, 58] is similar in spirit to M-stable model, but is based on a weaker concept of model than partial stability, which has the advantage that every program admits a regular model. On the other hand, as discussed in [23], a drawback of regular models is that they do not obey to the CWA principle.

The least undefined stable (L-stable) models [23, 47] are the partial stable models with the minimal degree of undefinedness, i.e., no other partial stable model exists whose undefined atoms constitute a proper subset of the atoms that are undefined in an L-stable model. The relevance of L-stable models is confirmed by the fact that L-stable models differ from total stable models only if the program has no total stable model; thus, Lstable models can be considered as the best “approximation” of total stable models.

In this paper, we study the expressive power and the complexity of disjunctive (datalog) programs based on the partial model semantics mentioned above, i.e., the capability of this query language of expressing queries on relational databases (see [2] for background on the subject). In particular, we analyze the expressive power of bound (Boolean) queries resorting to the common modalities of possibility inference –a literal is true if it is in some model– and certainty inference –a literal is true if it is in every model [1]. (As in many cases, results for general database queries can be easily derived from these results.) The main points of interest are:

• The expressive powers of the different partial model semantics vs. total model semantics, and their complexity.

• The impact of minimizing undefinedness on expressive power and complexity.

• The impact of syntactical restrictions. In particular, the power of disjunction vs the power of negation; the effect of stratified negation vs arbitrary negation; and, the effect of limited disjunction (in particular, head cycle free disjunction [6]) vs unrestricted disjunction.

The main results on the expressiveness can be summarized as follows:

1. Partial stable models have the same expressive power as total stable models. Under possibility and certainty inference, they capture the complexity classes Σ_{2}^{P} and Π_{2}^{P}, i.e., they can express precisely the database collections with complexity in Σ_{2}^{P} and Π_{2}^{P}, respectively (see Section 3 for details).

2. Under certainty inference, M-stable models and regular models are more powerful than the total stable models, as the former capture the class Π_{3}^{P} while the latter capture Π_{2}^{P}; under possibility inference, both have the same power as total stable models and capture the class Σ_{2}^{P}.

3. L-stable models are always more expressive than total stable models, since, under possibility and certainty inference, they capture the classes Σ_{3}^{P} and Π_{3}^{P}, respectively.

4. For partial models that minimize undefinedness (M-stable, L-stable, and regular models), negation is more expressive than disjunction under certainty inference and for L-stable models, also under possibility inference. Indeed, ∨-free programs with negation can express all of Σ_{2}^{P} (or Π_{2}^{P}); however, only a fragment thereof can be expressed by ¬-free programs with disjunction. By contrast, under total model semantics ∨-free programs with negation can define only database collections in NP (or coNP), while ¬-free programs with disjunction can define database collections that are Σ_{2}^{P} -hard (or Π_{2}^{P} -hard) to recognize.

5. Allowing headcycle-free disjunction (on ¬-free programs) increases the expressibility to a strict fragment of NP (resp. coNP), which contrasts with the well-known fact that stratified negation (on ∨-free programs) does not increase the expressibility beyond polynomial time computability. Interestingly, the combination of headcyclefree disjunction and stratified negation captures NP (or coNP), for all variants of partial models that we consider.

On the complexity side, we determine the data and expression complexity [56] of query evaluation. The data complexities (i.e., evaluating an arbitrary but fixed query over a given database) of the various query languages we consider yield complete problems for the classes at the lower end of the polynomial hierarchy up to Σ_{3}^{P} and Π_{3}^{P}. All query languages considered are shown to have data complexity which is complete for a class C from the polynomial hierarchy (however, not every considered query language which is complete for C can also express all of C).

The expression complexity (i.e., evaluating a given query on an arbitrary but fixed database) parallels the data complexity in the weak exponential hierarchy NEXP = Σ_{1}^{E}, Σ_{2}^{E} = NEXP^{NP}, Σ_{3}^{E} = NEXP^{Σ_{2}^{P}}, … and yields complete problems for these classes.

Our study extends and complements the work in [47, 48] on partial semantics for ∨- free programs, and the work in [22] on the expressiveness and complexity of total model semantics for disjunctive programs, which has been preceded by related work on ∨-free programs in [10, 39, 51]. While plain datalog (i.e., ¬-free and ∨-free programs) can express only polynomial time database collections, with negation total stable models can express all of coNP under certainty inference [51]; interesting recent work shows that similar expressive power can be gained without negation but using fixed predicates [12].

The analysis of the impact of syntactic restrictions carried out in this paper adds new insights to previous studies on complexity and expressiveness of restricted forms of disjunction (headcycle-free programs) [6, 7, 8]. The results may support in choosing an appropriate fragment of the query language under a suitable semantics, which fits the needs in practice.

Note that for normal programs the well-founded semantics [55] is often viewed as a competing approach to the stable model semantics in [27], and is understood as an approximation thereof. In fact, the well-founded model of a normal program is a Pstable model, and, moreover, the unique minimal P-stable model [49]. Thus, well-founded semantics is intimately related to P-stable semantics on normal programs. This is not the case with disjunctive programs, however. In fact, while several attempts to extend the well-founded semantics to disjunctive programs have been made, e.g. [4, 46], there is to date no general consensus about a proper formulation. Hence, we do not address such approaches here.

The remainder of the paper is structured as follows. Section 2 gives a short review of the definition of partial model semantics for disjunctive logic programs, and points out some basic relationships between different concepts of models. In Section 3, we first describe the formal framework for the use of function-free disjunctive logic programs (i.e., DATALOG^{∨,¬} programs) for defining queries and recall the basic concepts about expressive power of a query language; after that, we determine the expressive power of the different DATALOG^{∨,¬} query languages for each of the partial model semantics in Section 2. In Section 4, we address the issue of query complexity, and determine the data and expression complexity [56] of the DATALOG^{∨,¬} query languages. Section 5 is dedicated to the effect of syntactical restrictions on query programs, and discusses the expressive power under limited use of disjunction and negation. Finally, Section 6 gives a short summary and concludes the paper.

2 Partial Model Semantics

In this section we review from [23, 44, 58], the basic definitions and characterizations of partial model semantics for disjunctive logic programs. We assume that the reader is familiar with the basic concepts of logic programming [37]. For a more detailed account of (disjunctive) logic programming and databases, see [14, 38, 41, 2]; for overviews of expressibility and complexity results for normal and disjunctive logic programming, see [29, 11, 52].

2.1 Disjunctive Logic Programs

A rule r is a clause of the form

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

a_{1}, ⋯, a_{n}, b_{1}, ⋯, b_{m} are atoms of the form p(t_{1}, ..., t_{n}), where p is a predicate of arity n and the terms t_{1}, ..., t_{n} are constants or variables. The disjunction a_{1} ∨ ⋯ ∨ a_{n} is the head of r, while the conjunction b_{1}, ..., b_{k}, ¬b_{k+1}, ..., ¬b_{m} is the body of r. We denote by H(r) the set {a_{1}, ..., a_{n}} of the head atoms, and by B(r) the set {b_{1}, ..., b_{k}, ¬b_{k+1}, ..., ¬b_{m}} of the body literals. (As usual, a literal is an atom p or a negated atom ¬p; in the former case, it is positive, and in the latter negative.) Moreover, B^{+}(r) and B^{−}(r) denote the set of positive and negative literals occurring in B(r), respectively.

A disjunctive logic program (simply program hereafter) is a finite set of rules. A ¬-free (resp. ∨-free) program is called positive (resp. normal). A term, (resp. an atom, a literal, a rule or a program) is ground if no variables occur in it.

We often use upper-case letters, say L, to denote literals. Two literals are complementary , if they are of the form p and ¬p, for some atom p. For a literal L, ¬L denotes its complementary literal, and for a set A of literals, ¬.A = {¬L | L ∈ A}.

The Herbrand Universe U_{LP} of a program LP is the set of all constants appearing in LP, and its Herbrand Base B_{LP} is the set of all ground atoms constructed from the predicates appearing in LP and the constants from U_{LP}. A rule r′ is a ground instance of a rule r, if r′ is obtained from r by replacing every variable X with σ(X), where σ is a map from the variables occurring in r into U_{LP}. We denote by ground(LP) the set of all ground instances of the rules in LP.

An interpretation of LP is a consistent set of ground literals, i.e., a subset I ⊆ B_{LP} ∪ ¬.B_{LP} such that I ∩ ¬.I = ∅. We denote by I^{+} and I^{−} the set of positive and negative literals occurring in I, respectively, and by \overline{I} the set B_{LP} − (I ∪ ¬.I). The interpretation I is total if \overline{I} is empty; otherwise, I is partial.

Following [44], we define a 3-valued logic with values T (True), F (False), and U (Undefined), ordered by F < U < T. Let LP be a program and I an interpretation. The value of a ground literal L in I, value_{I}(L), is T if L ∈ I, F if L ∈ ¬.I, and U otherwise (i.e., if L ∉ I ∪ ¬.I). For ground literals L_{1}, …, L_{n}, the value of the conjunction C of all L_{i} is the minimum over the values of the L_{i}, i.e., value_{I}(C) = min({value_{I}(L_{i}) | 1 ≤ i ≤ n}), while the value value_{I}(D) of the disjunction D of all L_{i} is their maximum, i.e., value_{I}(D) = max({value_{I}(L_{i}) | 1 ≤ i ≤ n}); if n = 0, then value_{I}(C) = T and value_{I}(D) = F. Finally, a ground rule r is satisfied by I if value_{I}(H(r)) ≥ value_{I}(B(r)).

An interpretation M for LP is a 3-valued model of LP if M satisfies each rule in ground(LP); if M is total, it is a total model. A model M_{1} ≠ M is smaller than M, denoted M_{1} ≺ M, iff M_{1}^{+} ⊆ M^{+} and M_{1}^{−} ⊇ M^{−}. A model M is minimal iff there does not exist a smaller model M_{1}. Among total models, a model M is minimal iff there exists no smaller total model M_{1}. We denote the set of the minimal total models by MM^{+}(LP).

2.2 P-stable Models

As for total stable models [27, 44], the definition of partial stable models requires that every positive literal in an interpretation must be derivable from the rules possibly using negative literals as additional axioms.

An interpretation M for LP is justified (or founded [23]) iff M^{+} = N^{+} for some N ∈ MM^{+}(LP(M)), where the program LP(M) is obtained from ground(LP) as follows:

(i) remove all rules r such that B^{−}(r) ⊈ I^{−}, and (ii) remove all negative literals from the remaining rules.

Example 1 Let LP_{1} be the following program:

\begin{aligned}a ∨ b & ← \\ d & ← ¬d, ¬b \\ a ∨ c & ← ¬d \end{aligned}

Interpretation M_{1} = {a, ¬b, ¬c} is founded. Indeed, LP_{1}(M_{1}) is the following program:

a ∨ b ←

and there exists a minimal total model N of LP_{1}(M_{1}) such that N^{+} = M_{1}^{+}, namely N = {a, ¬b}. For M_{2} = {b, c, ¬a, ¬d}, LP_{1}(M_{2}) is as follows:

\begin{aligned}a ∨ b & ← \\ a ∨ c & ← \end{aligned}

Also M_{2} is founded, since N = {b, c, ¬a} is a minimal total model of LP_{1}(M_{2}) and N^{+} = M_{2}^{+}.

For total interpretations foundedness alone is sufficient to characterize (2-valued) stable models, which are indeed defined as the total founded interpretations of the program [27, 28, 44]. However, as for normal programs [49], foundedness alone is not sufficient to single out partial stable models, as some conditions on the false literals are needed. Intuitively, what must be imposed on the false literals for a founded interpretation I to be a (partial) stable model is the consistency with the closed world assumption. In other words, every false literal in I must be definitely not derivable from the rules of the program (assuming I), and no further literal must be declarable false without violating some rule of the program. This consistency with the CWA is precisely formalized by the notion of maximal unfounded set.

Definition 1 [23] Let I be an interpretation for LP. A set X ⊆ B_{LP} of ground atoms is an unfounded set for LP w.r.t. I if, for each a ∈ X, at least one of the following conditions holds for each rule r ∈ ground(LP) such that a ∈ H(r):

1. B(r) ∩ (¬.I ∪ X) ≠ ∅, or

2. H(r) ⊈ (¬.I ∪ X).

An unfounded set X is consistent w.r.t. I if X ∩ I^{+} = ∅.

Thus, if X is a consistent unfounded set (i.e., I ∪ ¬.X is an interpretation), for every rule r having an element of X in the head, either the body of r is false w.r.t. I ∪ ¬.X (Condition 1 of Definition 1), or the head of r is not false w.r.t. I ∪ ¬.X (Condition 2 of Definition 1). Thus, if we think in terms of classical (2-valued) interpretations, it is possible to extend I by assuming that all atoms in X are false,^{1} without explicitly violating r; in fact, rule r is still satisfiable: if Condition 1 applies, then r is definitely satisfied (as the body is false), and if Condition 2 applies, r can be satisfied by assuming true some atom in H(r) − X. Since the atoms in X are “defined” only by such rules r (under the intended assignment-based reading of rules), intuitively every atom in X should be false, since the assumption that it is true is not much founded, according to a principle of closed world assumption.

Example 2 Consider the program LP = {a ∨ b ←} and the interpretation I = ∅. The set X = {a} is a (consistent) unfounded set of LP w.r.t. I. Indeed, the unique rule of ground(LP) (with a in the head) satisfies Condition 2 of Definition 1, as H(r)−(X∪¬.I) = {b}. Likewise, we can easily verify that Y = {b} is a (consistent) unfounded set for LP w.r.t. I (as H(r) − (Y ∪ ¬.I) = {a}). For the program LP = { a ∨ b ← ; a ← b ; b ← a } and the interpretation I = {a, b} the only unfounded set is ∅.

Even if Definition 1 generalizes the standard definition of unfounded set [23] for normal programs, the union of all unfounded sets is not necessarily an unfounded set in case of a disjunctive program. Thus, a notion of maximal unfounded set is given instead of that of greatest unfounded set.

A consistent unfounded set X w.r.t. I is a maximal unfounded set for LP w.r.t. I if no proper superset Y of X is a consistent unfounded set for LP w.r.t. I.

Example 3 Let LP = {a ∨ b ←}. Both X_{1} = {a} and X_{2} = {b} are maximal unfounded sets for LP w.r.t. I = ∅.

X_{1} is the only maximal unfounded set for LP w.r.t. the interpretation {b} (note that X_{2} is not a consistent unfounded set w.r.t. {b}). For program LP_{1} of Example 1, the interpretation M_{1} = {a, ¬b, ¬c} has the single maximal unfounded set X_{1} = {b, c}, and M_{2} = {b, c, ¬a, ¬d} has the single maximal unfounded X_{2} = {a, d}.

Intuitively, a maximal unfounded set X is a maximal set of atoms that can be assumed false without violating the satisfiability of the rules of the program that contain some atom from X. Consistency of the unfounded set X ensures that the assumption of the falsity of the literals in X is consistent with I (that is, I ∪ ¬.X is an interpretation). For instance, we have seen in the above examples that for the program LP = {a ∨ b ←} both {a} and {b} are (consistent) unfounded sets w.r.t. I = ∅ while {a, b} is not an unfounded set. Indeed, we can assume the falsity of either a or b without violating the satisfiability of a∨b ← (which can be satisfied by making true b or a, respectively); but we cannot assume the falsity of both a and b at the same time, as in the latter case we would have no way to satisfy rule a ∨ b ←.

We are finally ready to provide the notion of P-stable model.

1Note that assuming false a literal which is in I^{+} would cause inconsistency.

Definition 2 [23] Let LP be a program and M an interpretation of it. Then M is a P-stable (partial stable) model of LP if the following conditions hold:

(a) M is founded,

(b) ¬.M^{−} is a maximal unfounded set for LP w.r.t. M.

Note that Condition (a) characterizes the true atoms of M, imposing that they have to be “justified” [57], while Condition (b) characterizes the false atoms of M, requiring that they must be all and only the atoms that can be assumed false consistently with M and with the rules of the program (further negative assumptions would make some rule unsatisfiable).

Example 4 Consider the program LP_{1} of Example 1. Both M_{1} = {a, ¬b, ¬c} and M_{2} = {b, c, ¬a, ¬d} are P-stable models of LP_{1}. Indeed, we have seen in Example 1 that M_{1} and M_{2} are founded, and Example 3 showed that ¬.M_{1}^{−} and ¬.M_{2}^{−} are maximal unfounded sets w.r.t. M_{1} and M_{2}, respectively.

Notice that M_{1} and M_{2} are the only P-stable models of LP_{1}. For instance, the interpretation M_{3} = {a, ¬d} is not a P-stable model of LP_{1}. While M_{3} is founded (note that LP_{1}(M_{3}) = {a ∨ b ← , a ∨ c ← }), ¬.M_{3}^{−} is not a maximal unfounded set w.r.t. M_{3}; indeed, M_{3} has the single maximal unfounded set X = {b, c}.

We gave the definition of P-stable in terms classical 2-valued semantics and unfounded sets, as we use this formulation to derive complexity and expressibility results in next sections; however, as shown in [23], this definition is equivalent to the one provided by Przymusinski in terms of 3-valued logics.

Proposition 1 [23] M is a P-stable model for a program LP if and only if M is a 3-valued stable model for LP according with [44].

It is worth noting that a disjunctive program may lack P-stable models, while every normal program has some P-stable model [44].

2.3 Restricted Classes of P-stable Models

As for normal (∨-free) logic programs [47, 48], P-stable models are grouped into three main families: T-stable, M-stable, and L-stable models.

Definition 3 [23] A P-stable model M is:

(a) T-stable (Total stable) if M is a total interpretation;

(b) M-stable (Maximal stable) if there exists no P-stable model N of LP such that N ⊃ M.

(c) L-stable (Least-undefined stable) if the set of its undefined atoms is minimal, i.e., there exists no P-stable model N of LP such that \overline{N} ⊃ \overline{M}.

Note that the T-stable models coincide with the 2-valued (total disjunctive) stable models of [44].

Example 5 The M-stable models of the program LP_{1} in Example 1 are M_{1} = {a, ¬b, ¬c} and M_{2} = {b, c, ¬a, ¬d}. In particular, M_{2} is also L-stable and T-stable; while M_{1} is not L-stable (and it is not T-stable obviously).

Consider the following program LP_{2}.

\begin{aligned}a & ← ¬b \\ b & ← ¬a \\ c ∨ d & ← a \\ d & ← c \end{aligned}

The P-stable models of LP_{2} are:

\begin{aligned}M_{1} & = \{b, ¬a, ¬c, ¬d\}, \\ M_{2} & = \{a, d, ¬b, ¬c\}, \\ M_{3} & = \{¬c\} \end{aligned}

M_{1} and M_{2} are also M-stable models, while M_{3} is not (as it is a subset of the P-stable model M_{1}, as well as of M_{2}). Both M_{1} and M_{2} are also L-stable models for LP_{2}. Moreover, M_{1} and M_{2} are also T-stable models, as they are total interpretations.

It is worth noting that an L-stable is not total in general. Consider the program LP_{3}:

\begin{matrix}a ∨ b ← \\ c ← ¬c \end{matrix}

Both {a} and {b} are L-stable models; but neither the former nor the latter is T-stable.

2.4 Regular Models

Regular models are similar in spirit to M-stable models, as they are maximal elements under set inclusion in a class of models. However, they are based on a weaker concept of model than the P-stable model which underlies M-stability.

Definition 4 [58] Let LP be a logic program and M an interpretation of it. Then, M is a regular model of LP iff

(a) M is a founded 3-valued model of LP, and

(b) M is maximal w.r.t. inclusion, i.e., there exists no founded 3-valued model N of LP with N ⊃ M.

[figure: .; .; .; .; .; TS; MS; LS; RS; PS; FS]

Figure 1: Relation between partial model semantics

Notice that every program has a regular model [58]. Thus, in contrast to the semantics from above, the regular model semantics assigns a model to every program.

Example 6 [44] Let LP be the program below.

work ∨ sleep ∨ tired ←
work ← ¬tired
sleep ← ¬work
tired ← ¬sleep

It is easy to see that LP has no P-stable model (cf. [44]), and hence no M-stable, L-stable, and T-stable model. On the other hand, {work}, {sleep}, and {tired} are (all the) regular models of LP.

2.5 Relationships between Models

We briefly discuss some properties and relationships of the concepts of partial models from above; a more detailed account is given in [23]. We use XS_{LP} as generic notation for the models of LP, where XS_{LP} is one of PS_{LP}, MS_{LP}, LS_{LP}, TS_{LP}, and RS_{LP}, and denotes the sets of P-stable, M-stable, L-stable, T-stable, and regular models of LP, respectively. Whenever LP is understood from the context, we shall omit the subscript LP.

The inclusion order diagram for the different sets of models XS is displayed in Figure 1. There, FS denotes the set of founded 3-valued models of LP.

In general, all concepts of models are different. However, on the class of (even locally) stratified programs, with the exception of FS they all coincide.^{2}

2A program LP is (locally) stratified if each atom p ∈ B_{LP} can be associated a positive integer l(p)

such that, for each rule r ∈ ground(LP) with p ∈ H(r) and each ground atom q the following holds: (i)

if q ∈ H(r), then l(p) = l(q); (ii) if ¬q ∈ B^{−}(r), then l(p) > l(q); (iii) if q ∈ B^{+}(r), then l(p) ≥ l(q).

In particular, if all ground atoms with the same predicate have the same number associated, then LP is globally stratified.

This is an immediate consequence of the fact that the P-stable models and T-stable models are the 3-valued stable and 2-valued stable models, which coincide for locally stratified DLPs [44].

Proposition 2 [23] Let LP be a program. If LP is (locally) stratified, then PS_{LP} = MS_{LP} = LS_{LP} = TS_{LP} = RS_{LP}.

Note that a (locally) stratified program has always P-stable models.

In addition to foundedness, P-stable models obey the principle of the closed world assumption (CWA), adapted to models of disjunctive logic programs [23]: “If every ground rule with an atom A in the head has a false body, or its head contains a true atom distinct from A w.r.t. an acceptable model, then A must be false in that model.”

The concept of regular model is similar to M-stable model, but yet different; this is explained by lacking obedience to the CWA principle. However, if disjunction is not present, the concepts coincide.

Proposition 3 [59] Let LP be a normal program. Then, MS = RS.

MS and LS on the one hand and RS on the other provide approximations of TS. In fact, LS is accurate for the programs that are consistent under stable semantics.

Proposition 4 [23] Let LP be a program. Then, TS ≠ ∅ implies TS = LS.

2.6 Deterministic Semantics

Each set XS of models can be considered as the intended models of a program LP. Although XS contains multiple models, a deterministic semantics can be enforced using two main approaches cf. [1, 47, 52, 22]: the possibility (or credulous, brave) semantics, and the certainty (or skeptical, cautious) semantics.

Definition 5 Let LP be a program and A be a ground literal. Then

(a) A is a ∃_{XS} (possible) inference of LP, denoted LP ⊧_{XS}^{∃} A, if ∃M ∈ XS such that A ∈ M (i.e., A is true in some model in XS);

(b) A is a ∀_{XS} (certain) inference of LP, denoted LP ⊧_{XS}^{∀} A, if ∀M ∈ XS, A ∈ M (i.e., A is true in every model in XS).

The next proposition points out some relationships among the various stable semantics.

Proposition 5 Let LP be a program and A be a ground literal. Then

(a) (A is a ∀_{PS} inference) ⇒ (A is a ∀_{MS} inference) ⇒ (A is a ∀_{LS} inference)

(b) (A is a ∃_{LS} inference) ⇒ (A is a ∃_{MS} inference) ≡ (A is a ∃_{PS} inference).

Proof. Point (a) along with the first implication of Point (b) follow from Proposition 4 of [23] where it is proven that PS ⊆ MS ⊆ LS.

Equivalence between ∃_{MS} and ∃_{PS} inference stems from the observation that the union of all M-stable models coincides with the union of all P-stable models.

Example 7 Consider program LP_{1} of Example 1.

The set {M_{1}, M_{2}} of P-stable models of LP_{1} coincides with the set of the M-stable models. Thus, we have that {a, ¬b, ¬c, b, c, ¬a, ¬d} are both ∃_{PS} and ∃_{MS} inferences; while both sets of ∀_{PS} and ∀_{MS} inferences are empty.

Model M_{2} is the only L-stable and T-stable model of LP_{1}. Therefore, b, c, ¬a, and ¬d are ∀_{LS}, ∀_{TS}, ∃_{LS} and ∃_{TS} inferences.

On program LP_{2} of Example 5 the various stable semantics coincide. Indeed, under P-stable, M-stable, L-stable and T-stable semantics, ¬c is the only certain inference, and a, ¬a, b, ¬b, ¬c, d, and ¬d are the possible inferences.

Finally, consider the program of Example 6. Since PS = MS = LS = TS = ∅, we have that: (i) the set of ∃_{PS}, ∃_{MS}, ∃_{LS} and ∃_{TS} inferences are empty, and (ii) under ∀_{LS}, ∀_{TS}, ∃_{LS} and ∃_{TS}, every literal is inferred.

Moreover, concerning regular model semantics, we have that work, sleep, and tired are ∃_{RS} inferences; while the set of ∀_{RS} inferences is empty.

3 Expressive Power

3.1 Preliminaries

In the context of deductive databases, programs as introduced above are known as disjunctive datalog (DATALOG^{∨,¬}) programs, i.e., the extension of datalog (with negation) [14, 32, 54] by disjunction [22]. Some of the predicate symbols correspond to database relations (the extensional (EDB) predicates), and are not allowed to occur in rule heads; the other predicate symbols are called intensional (IDB) predicates. Actual database relations are formed on a fixed countable domain U, from which also possible constants in a DATALOG^{∨,¬} program are taken.

More formally, a DATALOG^{∨,¬} program LP has associated a relational database scheme DB_{LP} = {r| r is an EDB predicate symbol of LP}; thus EDB predicate symbols are seen as relation symbols. A database D on DB_{LP} is a set of finite relations on U, one for each r in DB_{LP}, denoted by D(r); note that D can be seen as a first-order structure whose universe consists of the constants occurring in D (the active domain of D).^{3} The set of all databases on DB_{LP} is denoted by D_{LP}.

3We use here active domain semantics (cf. [2]), rather then a setting in which a (finite) universe of D is explicitly provided [25, 16, 56]. Note that Fagin’s Theorem and all other results to which we refer remain valid in this (narrower) context; conversely, the results of this paper can be extended to that setting.

Given a database D ∈ D_{LP}, LP_{D} denotes the following program:

LP_{D} = LP ∪ {r(t) ← |r ∈ DB_{LP} ∧ t ∈ D(r)}.

Definition 6 A (bound DATALOG^{∨,¬}) query Q is a pair ⟨LP, G⟩, where LP is a DATALOG^{∨,¬} program and G is a ground literal (the query goal). Given a database D in D_{LP} and a class of models XS, the ∃_{XS} (resp., ∀_{XS}) answer of Q on D is true if G is a ∃_{XS} (resp., ∀_{XS}) inference of LP_{D} and false otherwise.

The set of all queries is denoted by Q.

The constants occurring in LP_{D}, G define the active domain of query Q = ⟨LP, G⟩ on the database D.

Observe that, in general, two queries ⟨LP, G⟩ and ⟨LP, ¬G⟩ on the same database need not give symmetric answers. That is, if e.g. ⟨LP, G⟩ answers yes for D, it may be possible that also ⟨LP, ¬G⟩ answers yes for D.

A bound query paired with an answer (i.e., inference) mode defines a Boolean Cgeneric query of [2], i.e., a map from D_{LP} to {true, false}. As common, we focus in our analysis of the expressive power of a query language on generic queries, which are those mappings whose result is invariant under renaming the constants in D with constants from U. Genericity of a bound query ⟨LP, G⟩ is assured by excluding constants in LP and G. As discussed in [2, p. 421], this issue is not central, since constants can be provided by designated input relations; moreover, any query goal G = (¬)p(⋯) can be easily replaced by a new goal G′ = (¬)q and the rule q ← p(⋯), where q is a propositional letter. In the rest of this paper, we thus implicitly assume that constants do not occur in queries.

Definition 7 Let Q = ⟨LP, G⟩ be a (constant-free) query. Then the database collection of Q w.r.t. the set of models XS is:

(a) under the possibility (∃_{XS}) variant of semantics, the set of all databases D in D_{LP} for which the ∃_{XS}-answer of Q is true, which is denoted by EXP_{XS}^{∃}(Q);

(b) under the certainty (∀_{XS}) variant of semantics, the set of all databases D in D_{LP} for which the ∀_{XS}-answer of Q is true, which is denoted by EXP_{XS}^{∀}(Q).

The expressive power of Q under a type of semantics w.r.t XS is the family of the database collections of all queries Q, i.e., EXP_{XS}^{∃}[Q] = {EXP_{XS}^{∃}(Q)|Q ∈ Q, Q constant-free} and EXP_{XS}^{∀}[Q] = {EXP_{XS}^{∀}(Q)|Q ∈ Q, Q constant-free}.

The expressive power of each semantics will be related to database complexity classes, which are as follows. Let C be a Turing machine complexity class (e.g., P or NP), R be a relational database scheme, and D be a set of databases on R.^{4} Then, D is C-recognizable if the problem of deciding whether D ∈ D for a given database D on R is in C. The database complexity class DB-C is the family of all C-recognizable database collections. (For instance, DB-P is the family of all database collections that are recognizable in polynomial time). If the expressive power of a given semantics coincides with some class DB-C, we say that the given semantics captures C.

4As usual, adopting the data independence principle, it is assumed that D generic, i.e., it is closed under renamings of the constants in U.

Recall that the classes Σ_{k}^{P}, Π_{k}^{P} of the polynomial hierarchy [53] are defined by Σ_{0}^{P} = P, Σ_{i+1}^{P} = NP^{Σ_{i}^{P}}, and Π_{i}^{P} = co-Σ_{i}^{P}, for all i ≥ 0. In particular, Π_{0}^{P} = P, Σ_{1}^{P} = NP, and Π_{1}^{P} = coNP. By Fagin’s Theorem [25] and its generalization in [53], complexity and second-order definability are linked as follows.

Proposition 6 ([25, 53]) A database collection D over a scheme R is in DB-Σ_{k}^{P}, k ≥ 1, iff it is definable by a second-order formula (∃A_{1})(∀A_{2}) ⋯ (Q_{k}A_{k})ϕ on R, where the A_{i} are lists of predicate variables preceded by alternating quantifiers and ϕ is first-order.

3.2 The Power of PS Semantics

In [21], it was shown that ∃_{PS} and ∀_{PS} inference from propositional programs is complete for the complexity classes Σ_{2}^{P} and Π_{2}^{P}, respectively. In this section, we complement these complexity results by capturing results for Σ_{2}^{P} and Π_{2}^{P}.

Lemma 1 Let LP be a ground program, and let M be an interpretation. Deciding whether M ∈ PS is coNP-complete.

Proof. To show that M is a P-stable model, we have to show that (a) M is founded and (b) ¬.M^{−} is a maximal unfounded set. Concerning (a), deciding if M^{+} = N^{+} for some N ∈ MM^{+}(LP(M)) is in coNP, since the program LP(M) can be constructed efficiently and a guess for a total model M1 of LP(M) such that M1 ≺ M (where M1 is represented by its positive part M1^{+}) can be checked in polynomial time. Also (b) is in coNP: checking if ¬.M^{−} is an unfounded set is easy, and if all ground atoms that do not occur in LP are false in M (otherwise ¬.M^{−} is clearly not maximal) a guess for a larger consistent unfounded set has polynomial size and can be checked in polynomial time. Since coNP is closed under conjunctions, it follows that deciding P-stability of M is in coNP. For a proof of hardness where all atoms are propositional letters –which uses the equivalent definition of 3-valued stable model (Prop. 1)– cf. [21].

Lemma 2 [22] Every DB-Σ_{2}^{P} -recognizable database collection D can be defined by a (constant-free) query Q = ⟨LP, G⟩ under ∃_{TS} semantics, where LP is stratified and G is an atom.

By the coincidence of T-stable and P-stable models on stratified programs, we thus obtain the following results.

Theorem 1 EXP_{PS}^{∃}[Q] = DB-Σ_{2}^{P}.

Proof. We first prove that for any query Q = ⟨LP, G⟩ in Q, recognizing whether a database D is in EXP_{PS}^{∃}(Q) is in Σ_{2}^{P}. D is in EXP_{PS}^{∃}(Q) iff there exists a P-stable model M of LP_{D} such that G ∈ M. To check this, we may guess an interpretation M of LP_{D} and verify that: (i) M is a P-stable model of LP_{D}, and (ii) G ∈ M. By virtue of Lemma 1, (i) is done by a single call to an NP oracle (note that, since Q is fixed, ground(LP_{D}) has size polynomial in D, and can be constructed in polynomial time), and (ii) is clearly polynomial. Hence, this problem is in Σ_{2}^{P}. Consequently, recognizing whether a database D is in EXP_{PS}^{∃}(Q) is in Σ_{2}^{P}.

By Proposition 2 and Lemma 2, it follows immediately that every Σ_{2}^{P} -recognizable database collection D is in EXP_{PS}^{∃}[Q]. This proves the result.

Theorem 2 EXP_{PS}^{∀}[Q] = DB-Π_{2}^{P}.

Proof. We first prove that for any query Q = ⟨LP, G⟩ in Q, recognizing whether a database D is in EXP_{PS}^{∀}(Q) is in Π_{2}^{P}. To this end, let consider the complementary problem: is it true that D is not in EXP_{PS}^{∀}(Q) ? Now, D is not in EXP_{PS}^{∀}(Q) iff there exists a Pstable model M of LP_{D} such that G ∉ M. Following the line of the proof of Theorem 1, we can easily see that the latter problem is in Σ_{2}^{P}. Hence, recognizing whether a database D is in EXP_{PS}^{∀}(Q) is in Π_{2}^{P}.

That every Π_{2}^{P} -recognizable database collection D is in EXP_{PS}^{∀}[Q] is derived from Lemma 2 and Proposition 2. By these results, there exists a query Q = ⟨LP, G⟩ with stratified LP, whose ∃_{PS} answer is true on a database D iff D is not in D. Let Q′ = ⟨LP′, G′⟩ where G′ is a new propositional atom and LP′ = LP ∪ {G′ ← ¬G}. Note that for every D, LP′_{D} is stratified, and hence the P-stable models of LP′_{D} coincide with the T-stable models and LP′_{D} always has a P-stable model.

It is now easy to see that G′ is a ∀_{PS} inference of LP′_{D} iff G is not a ∃_{PS} inference of LP_{D}, i.e., D ∈ D. Consequently, EXP_{PS}^{∀}(Q′) = D. This proves the result.

It is worth noting that, under certainty semantics, the addition of disjunction increases the power of P-stable models of two levels in the polynomial hierarchy. Indeed, on normal programs ∀_{PS} semantics coincides with well-founded semantics, which expresses only a strict subset of the polynomial queries (cf. [2]).

3.3 The Power of MS Semantics

We next determine the expressive power of M-stable models, and start with the possibility semantics. As for normal programs [47, 48], under the possibility semantics, the expressive power of M-stable models coincides with the expressive power of T-stable models.

Theorem 3 EXP_{MS}^{∃}[Q] = DB-Σ_{2}^{P}.

Proof. By Proposition 5.(b), we have that for any query Q = ⟨LP, G⟩ and any given database D, G is an ∃_{MS} inference of LP_{D} iff G is a ∃_{PS} inference of LP_{D}. Thus, by Theorem 1 the result is immediate.

In order to determine the expressive power of M-stable models under certainty semantics, we need to establish the complexity of recognizing M-stable models.

Theorem 4 Let LP be a fixed program. Given a database D on DB_{LP} and an interpretation M for LP_{D}, deciding whether M is an M-stable model for LP_{D} is Π_{2}^{P} -complete.

Proof. Membership in Π_{2}^{P}. Notice that, since LP is fixed, ground(LP_{D}) can be constructed from D in polynomial time. Let M be an interpretation and consider the complementary problem: is it true that M is not an M-stable model? This can be decided as follows. Guess an interpretation N and verify that (i) either M is not P-stable or (ii) N is P-stable and M is a proper subset of N. By Lemma 1, both (i) and (ii) can be decided by a single call to an NP oracle. Thus, this problem is in Σ_{2}^{P}. Consequently, deciding whether M is an M-stable model for LP_{D} lies in Π_{2}^{P}. Hardness for Π_{2}^{P}. Let LP be stratified and ¬q be a ground literal where q is an atom. Lemma 2 implies that deciding, given D, whether ¬q is true in every T-stable model of LP_{D} is Π_{2}^{P} -hard (cf. also [22]). We reduce this problem in polynomial time to our problem. Let LP′ be the program obtained from LP by the following steps:

(i) insert ¬p in the body of each rule in LP, where p is a new propositional letter;

(ii) add the rules p ← ¬q, ¬p and q ← p;

(iii) for each IDB predicate s of LP, add the rules s(X_{1}, ..., X_{n}) ← ¬s(X_{1}, ..., X_{n}), ¬q and s(X_{1}, ..., X_{n}) ← p.

Fix a database D over DB_{LP}. Program LP′_{D} has a P-stable model on D, which is obtained if all ground atoms over IDB predicates are undefined. More precisely, let A = {r(t) | r ∈ DB_{LP}, t ∈ D(r)} be the set of facts stored in the extensional database and B the Herbrand Base B_{LP}′_{D} of LP′_{D} restricted to the database predicates (i.e., the predicates in DB_{LP}). Intuitively (and as easy to prove), M = A ∪ ¬.(B − A) is contained in every P-stable model of LP′_{D}. In fact, M itself is a P-stable model of LP′_{D}. To show this, we have to prove that (a) M is founded and (b) ¬.M^{−} is a maximal unfounded set w.r.t. M.

(a) M is founded because (1) there is a fact in LP′_{D}(M) for every atom in M^{+} = A, and (2) no other atom is derivable from LP′_{D}(M): all rules in (i)–(iii) that contain a negative literal are discarded in LP′_{D}(M), and the remaining rules q ← p, s(⋯) ← p can not fire because p is not derivable (no rule with p in the head exists in LP′_{D}(M)).

(b) ¬.M^{−} = (B − A) is an unfounded set for LP′_{D} w.r.t. M, as in LP′_{D} there is no rule with an atom from (B − A) in the head. Finally, ¬.M^{−} can not be extended to a larger consistent unfounded set (that is, no other undefined atom can be declared false): p does not belong to any unfounded set of M, since its unfoundness would require the truth of q because of rule p ← ¬q, ¬p; consequently, due to the rules q ← p and s(⋯) ← p, also q and all atoms s(⋯) does not belong to any unfounded set of M (Condition 3 of Definition 1 is not applicable to these rules since the they are non-disjunctive, Condition 1 and 2 do not apply as the body p is neither false nor unfounded).

Therefore, M is a P-stable model of LP′_{D}. On the other hand, it is immediate that M is included in every P-stable model. It thus follows that M is M-stable iff there exists no other P-stable model of LP′_{D}. We claim that this is the case iff ¬q is true in every T-stable model of LP_{D}. This implies that, given M and D, deciding whether M is an M-stable model of LP′_{D} is Π_{2}^{P} -hard.

We first show the following: In every P-stable model M′ of LP′_{D} such that M′ ≠ M, atom p must be false.

Indeed, p can not be true in M′, as then no rule with p in the head occurs in LP′_{D}(M′) (if p is true rule p ← ¬q, ¬p is not in LP′_{D}(M′), as its negative body literal ¬p is false). If p is undefined in M′, then q must not be true due to the rule p ← ¬q, ¬p (otherwise, ¬.M^{′−} is not maximal unfounded), and q must not be false due to q ← p. Thus q must be undefined, as must be every s(⋯) due to the rules in (iii). This would imply M′ = M, a contradiction. Thus, p must be false in M′.

To prove the claim, it suffices to show now that a P-stable model M′ ≠ M of LP′_{D} exists iff LP_{D} has a P-stable model in which q is true, since PS_{LP_{D}} = TS_{LP_{D}} and LP_{D} has some P-stable model as it is stratified.

Assume that an M′ as described exists. Since p is false in M′, q must be true due to the rule p ← ¬q, ¬p. It is easy to verify that M′ − {¬p} is a P-stable model of LP_{D} in which q is true. Conversely, let N be a P-stable model of LP_{D} such that q is true. Then, it is straightforward to check that M′ = N ∪ {¬p} is a P-stable model of LP′_{D}. Since M′ ≠ M, this proves our claim. We are done.

Thus, while recognizing P-stable models is in coNP, recognizing M-stable models is one level higher up in the polynomial hierarchy.

From this result, it is intuitive that the expressive power of certainty semantics using M-stable models is precisely one level higher up in the polynomial hierarchy than certainty semantics using P-stable models. This is actually the case.

Theorem 5 EXP_{MS}^{∀}[Q] = DB-Π_{3}^{P}.

Proof. Let us first prove that, for any fixed query Q = ⟨LP, G⟩ in Q, recognizing whether a given database D is in EXP_{MS}^{∀}(Q) lies in Π_{3}^{P}. Consider the complementary problem: is there any M-stable model M of LP_{D} such that G ∉ LP_{D}? To solve this problem, we guess an interpretation M and use a Σ_{2}^{P} oracle to check whether M is not M-stable (cf. Theorem 4); if not (i.e., M is M-stable), we check in polynomial time whether G ∈ M. Therefore, this problem is in Σ_{3}^{P}; hence, recognizing whether a database D is in EXP_{MS}^{∀}(Q) is in Π_{3}^{P}.

Let us now prove that every Π_{3}^{P} recognizable database collection D on a database scheme DB is in EXP_{MS}^{∀}[Q]. By Proposition 6, D is definable by a second-order formula (∀A)Ψ, where Ψ is a Σ_{2}^{1} formula over DB and A = a_{1}, …, a_{k} is a list of predicate variables.

Let DB′ be DB extended with A, and let D′ be the collection of all databases D′ = (D, A) over DB′ such that D is from D and D′ ⊧ Ψ.^{5} Clearly, a database D on DB belongs to D iff every database D′ = (D, A) over DB′ whose the relations A are drawn from the active domain of D belongs to D′. Note that by the results in [53], D′ is Σ_{2}^{P} -recognizable. We use this to exhibit a query Q1 such that EXP_{MS}^{∀}(Q1) defines D.

We proceed in two steps. First, we show that there is a query Q0 = ⟨LP0, G0⟩ such that, given a database D′ on DB′, the ∃_{MS} answer of Q0 is yes iff D′ belongs to D′. The program LP0 is the program LP′ constructed from the stratified program LP in the proof of Theorem 4. Indeed, since D′ is Σ_{2}^{P} -recognizable, by Lemma 2 there exists a (generic) query Q = ⟨LP, G⟩, where LP is stratified and G is an atom, such that for every database D′ on DB′, the program LP_{D′} has some T-stable model containing G iff D′ belongs to D′.

For the program LP′ constructed from LP where q = G, the interpretation M = A ∪ ¬.(B − A) defined analogously for D′ is a P-stable model of LP′_{D′}, and it is M-stable iff ¬q is true in every T-stable model of LP_{D′}. Thus, M is not M-stable iff q is true in some T-stable model of LP_{D′}. As argued in the proof of Theorem 4, M is contained in every P-stable model M′ of LP′_{D′}, and every such M′ with M′ ≠ M must contain ¬p. Thus, it follows that by choosing LP0 = LP′ and G0 = ¬p, the query Q0 = ⟨LP0, G0⟩ under ∀_{MS} semantics defines D′.

The second step in the proof uses the query Q0 to construct a query Q1 = ⟨LP1, G1⟩ which defines D. Recall that D belongs to D iff every D′ = (D, A) such that the relations in A are drawn from the active domain of D is in D′. Now, construct the program LP1 from LP0 by adding the clause

a(X_{1}, …, X_{n}) ∨ â(X_{1}, …, X_{n}) ←

for each predicate a from A, where â is a new predicate of the same arity. These clauses simulate all possible choices for the predicates in A, and generate all possible extensions D′ = (D, A) of D.

It is easy to see that every P-stable model of LP1_{D} contains either {a(t), ¬â(t)} or {¬a(t), â(t)}, for each ground atom a(t). Moreover, for each possible choice, some Pstable (and hence M-stable) model of LP1_{D} exists; notice that P-stable models M1 and M2 corresponding to different choices are incomparable, i.e., M1 ⊈ M2 ⊈ M1. It holds that ¬p is true in every M-stable model iff for each possible extension D′ = (D, A) of D, the ∀_{MS} answer of Q0 for D′ is yes. Thus, by choosing G1 = ¬p, the ∀_{MS} answer of Q1 = ⟨LP1, G1⟩ is yes for database D on DB iff D belongs to D. In other words, EXP_{MS}^{∀}(Q1) = D. This proves the theorem.

Therefore, while the certainty variant of P-stable semantics has dual complexity compared to the possibility semantics, the certainty semantics based on M-stable models has higher complexity than the possibility semantics. Remark. The use of disjunctive clauses a(X_{1}, …, X_{n}) ∨ â(X_{1}, …, X_{n}) ← in the program LP1 is not essential for the expressiveness of the formalism. In fact, these clauses could be replaced by the clauses

5Here, the universe of D′ as a structure consists of the constants occurring in its relations.

\begin{matrix}a(X_{1}, …, X_{n}) ← & ¬â(X_{1}, …, X_{n}) \\ â(X_{1}, …, X_{n}) ← & ¬a(X_{1}, …, X_{n}) \\ p ← & a(X_{1}, …, X_{n}), â(X_{1}, …, X_{n}) \end{matrix}

which also serve well for the purpose.

3.4 The Power of LS Semantics

We first consider certainty inference. The expressiveness of the ∀_{LS} semantics coincides with the expressiveness of the ∀_{MS} semantics. This is intuitive, since recognizing L-stable models has the same complexity as recognizing L-stable models.

Theorem 6 Let LP be a fixed program. Give a database D on DB_{LP} and an interpretation M for LP_{D}, deciding whether M is an L-stable model for LP_{D} is Π_{2}^{P} -complete.

Proof. The proof of membership in Π_{2}^{P} follows the membership part in Theorem 4, with the only difference that the check M ⊂ N is changed to \overline{N} ⊂ \overline{M}. Hardness for Π_{2}^{P} follows from the construction in the hardness part of Theorem 4: M is an L-stable model iff M is an M-stable model.

However, the query Q1 constructed in the proof of Theorem 5 does not serve to show that L-stable models can express all of DB-Π_{3}^{P} under the certainty semantics. The reason is that M-stable models M_{1} and M_{2} corresponding to different choices for the predicates A, i.e., M1 ⊈ M2 ⊈ M1 may be comparable with respect to L-stability, e.g. \overline{M_{1}} ⊆ \overline{M_{2}} is possible. A slight extension of the construction is sufficient to prove the expected result.

Theorem 7 EXP_{LS}^{∀}[Q] = DB-Π_{3}^{P}.

Proof. The proof that, for any fixed query Q = ⟨LP, G⟩ in Q, deciding whether a given database D is in EXP_{LS}^{∀}(Q) lies in Π_{3}^{P} is analogous to the proof that deciding if D is in EXP_{MS}^{∀}(Q) lies in Π_{3}^{P} (cf. proof of Theorem 5).

To prove that every Π_{3}^{P} -recognizable database collection D on a database scheme DB is in EXP_{MS}^{∀}[Q], consider the query Q1 = ⟨LP1, G1⟩ constructed for D in the proof of Theorem 5. Construct LP2 from LP1 by adding for each of the clauses a(X_{1}, …, X_{n}) ∨ â(X_{1}, …, X_{n}) ← implementing the possible choices for A, the following clauses:

\begin{matrix}ã(X_{1}, …, X_{n}) ← & a(X_{1}, …, X_{n}) \\ â(X_{1}, …, X_{n}) ← & u \\ ã(X_{1}, …, X_{n}) ← & u \\ u ← & ¬u \end{matrix}

These additional clauses serve to destroy the symmetry between the two possible choices for satisfying a(X_{1}, …, X_{n})∨â(X_{1}, …, X_{n}) ← in a P-stable model, namely {a(t), ¬â(t)} and {¬a(t), â(t)}, which both define a(t) and â(t). After the addition of the above clauses, there are two P-stable models for the choice: {a(t), ã(t)} and {¬a(t), â(t)}. These models, which are not symmetric, are not comparable with respect to L-stability. It is easy to see that by choosing G2 = G1, for any database D the ∀_{LS} answer of the query Q2 = ⟨LP2, G2⟩ coincides with the ∀_{MS} answer of Q1. Consequently, D ∈ EXP_{LS}^{∀}(Q2). This proves the result.

Now let us consider possibility semantics. The expressiveness of ∃_{MS} semantics does not carry over to ∃_{LS} semantics. In fact, ∃_{LS} is more expressive than ∃_{MS}. The reason is that it is not always possible to reach from an arbitrary P-stable model an L-stable model by successively adding literals. Thus, while in the case of M-stable models, possibility semantics only needs to inspect P-stability of a model, in the case of L-stable models the property of L-stability of P-stable models has to be taken into account.

Theorem 8 EXP_{LS}^{∃}[Q] = DB-Σ_{3}^{P}.

Proof. We first verify that deciding whether a database D is in EXP_{LS}^{∃}(Q) is in Σ_{3}^{P}. D is in EXP_{LS}^{∃}(Q) iff there exists some L-stable model M of LP_{D} such that G belongs to M. A guess for M can be verified in polynomial time with a single call to an Σ_{2}^{P} oracle by Theorem 6. Thus, deciding whether D ∈ EXP_{LS}^{∃}(Q) is in Σ_{3}^{P}. It remains to show that every Σ_{3}^{P} -recognizable database collection D on a database scheme DB is in EXP_{LS}^{∃}[Q].

Let D′ = \overline{D} be the complementary database collection on DB, and consider the query Q2 = ⟨LP2, G2⟩ from the proof of Theorem 7, constructed for D′ (which is in Π_{3}^{P}). Then, for any database D on DB, D ∉ \overline{D} (i.e., D ∈ D) iff D ∉ EXP_{LS}^{∀}(Q2) iff G2 does not belong to some L-stable model M of LP2_{D}.

Recall that G2 = ¬p. Notice that, as easy to see, no P-stable (and hence also no L-stable) model of LP2_{D} contains p. Indeed, p occurs only in the head of a single rule, namely p ← ¬G, ¬p, which can however not be used to derive p.

Now construct LP3 by adding the following clauses to LP2:

\begin{matrix}a ∨ b ← & ¬p \\ b ← & p \\ c ← & ¬a, d \\ d ← & ¬d \end{matrix}

Here, a, b, c and d are new propositional atoms.^{6}

Assuming that p is undefined, the clauses from above have a single P-stable model: M = {¬a}; on the other hand, assuming that p is false, there are two P-stable models: M1 = {¬a, b} and M2 = {a, ¬b, ¬c}. Notice that M1 defines only a and b, while M2 defines a, b and also c. Thus, only M2 is L-stable.

6One could also drop the rule d ← ¬d and use the atom u from LP2 instead of d in the rule bodies.

Now let M be an L-stable model of LP2_{D}. It is easy to see that, if ¬p ∉ M, the set M ∪ {¬a} is an L-stable model of LP3; otherwise, the set M ∪ {a, ¬b, ¬c} is an L-stable model of LP3.

On the other hand, every L-stable model M′ of LP3 must be of the form M ∪ {¬a} or M ∪ {a, ¬b, ¬c}, where M is an L-stable model of LP2_{D}.

It holds that LP3_{D} has an L-stable model containing ¬a iff LP2_{D} has some L-stable model not containing ¬p.

It follows that for G3 = ¬a, the query Q3 = ⟨LP3, G3⟩ satisfies EXP_{LS}^{∃}(Q3) = D. Consequently, every Σ_{3}^{P} -recognizable database collection D is in EXP_{LS}^{∃}[Q].

3.5 The Power of RS semantics

The definition of regular model is in the spirit of the definition of M-stable model (select the maximal models from a collection of models w.r.t. inclusion), but is based on a weaker notion of model. However, the expressive power of regular models is the same as of Mstable models.

Theorem 9 EXP_{RS}^{∃}[Q] = DB-Σ_{2}^{P}.

Proof. We first have to show that for every query Q = ⟨LP, G⟩, given a database D, deciding whether D ∈ EXP_{RS}^{∃}(Q) is in Σ_{2}^{P}. From the definition of regular model, it is easy to see that G is a ∃_{RS} inference of LP_{D} iff there exists a 3-valued model M of LP_{D} such that M^{+} is founded and G ∈ M. A guess for M can be verified with an NP oracle in polynomial time: (i) check that M is a 3-valued model, and (ii) check using the NP oracle, that there exists no total minimal model N of LP(M) such that N^{+} ⊂ M^{+}. Since LP_{D} is polynomial in D, this shows that deciding whether D ∈ EXP_{RS}^{∃}(Q) is in Σ_{2}^{P}.

On the other hand, by Proposition 2 and Theorem 1, it follows immediately that every Σ_{2}^{P} -recognizable database collection D is in EXP_{RS}^{∀}[Q].

Prior to the result on certainty expressibility, we note the complexity of recognizing regular models.

Theorem 10 Let LP be a fixed program. Given a database D on DB_{LP}, and an interpretation M for LP_{D}, deciding whether M is a regular model for LP_{D} is Π_{2}^{P} -complete.

Proof. Membership in Π_{2}^{P}. An interpretation M is not a regular model of LP iff one of the following three conditions holds: (i) M is not a 3-valued model of LP; (ii) M^{+} is not a minimal model of LP(M); or (iii) there is some interpretation N ⊃ M such that N is a 3-valued model of LP and N^{+} is a minimal model of LP (N).

Condition (i) can be efficiently checked, and (ii) can be easily checked with a call to an NP oracle. Finally, (iii) can be checked with a call to a Σ_{2}^{P} oracle, since a guess for N can be verified with an NP oracle in polynomial time. Thus, deciding whether M is not regular is in Σ_{2}^{P}, which implies that deciding if M is regular is in Π_{2}^{P}.

Hardness for Π_{2}^{P}. This part is shown by a reduction from deciding whether a ground literal is true in every T-stable model of a stratified program LP_{D}. The reduction is identical to the one in the proof of Theorem 4: The interpretation M = A ∪ ¬.(B − A) is contained in every regular model of LP′_{D}, and is in fact a regular model iff ¬q is true in every T-stable model of LP_{D}. Note that M is founded and a 3-valued model, because M is a P-stable model. Along the lines in the proof of Theorem 4, one can show that p must be false and q true in every founded 3-valued model M′ such that M′ ≠ M; the maximal such M′ correspond to the T-stable models of LP_{D} in which q is true. The result follows.

Theorem 11 EXP_{RS}^{∀}[Q] = DB-Π_{3}^{P}.

Proof. For any query in Q = ⟨LP, G⟩, recognizing whether a database D belongs to EXP_{RS}^{∀}(Q) is in Π_{3}^{P}. In fact, D ∉ EXP_{RS}^{∀}(Q) iff LP_{D} has some regular model M such that G ∉ M. By the preceding Theorem 10, a guess for M can be verified in polynomial time with an oracle for Σ_{2}^{P}. Thus, it follows that EXP_{RS}^{∀}(Q) is a Π_{3}^{P} -recognizable database collection.

The proof the every Π_{3}^{P} -recognizable database collection D is in EXP_{RS}^{∀}(Q) is analogous to the respective part in the proof of Theorem 5. In fact, for the query Q1 = ⟨LP1, G1⟩ constructed there the ∀_{MS} answer is identical to the ∀_{RS} answer.

4 Complexity

The complexity of a query language is usually measured according with two criteria, namely data complexity and expression complexity [16, 56].

For the language Q, data and expression complexity amount to the following. Let Q = ⟨LP, G⟩ be a query and D be a database in DB_{LP}.

• Data complexity: measure the complexity of evaluating Q as a function of the size of the database D, while Q is fixed.

• Expression complexity: measure the complexity of evaluating Q as a function of the size of Q, while D is fixed.

Observe that, while measuring data complexity, since LP is fixed, the arity of the predicates is bounded by a constant and ground(LP_{D}) is polynomial in the size of the input D.

On the contrary, while measuring expression complexity, the size of ground(LP_{D}) is in general exponential in the size of the input Q.

4.1 Data Complexity

The results on the data complexity of queries defined by partial model semantics are immediate consequences from the expressiveness results in the previous section.

Theorem 12 (Possibility inference) Let Q be a fixed query. Deciding, given a database D, whether Q is true on D under ∃_{XS} semantics is (a) Σ_{2}^{P} -complete for XS from PS, MS, RS, and (b) Σ_{3}^{P} -complete for LS.

Theorem 13 (Certainty inference) Let Q be a fixed query. Deciding, given a database D, whether Q is true on D under ∀_{XS} semantics is (a) Π_{2}^{P} -complete for XS = PS, and (b) Π_{3}^{P} -complete for XS from MS, LS, and RS.

We complement these results with the complexity of deciding whether a P-stable model of LP_{D} exists. Recall that LP_{D} always has a regular model, and hence the same problem for regular semantics has trivial complexity.

Theorem 14 Let Q = ⟨LP, G⟩ be a fixed query. Deciding, given database D, whether LP_{D} has a P-stable model, is Σ_{2}^{P} -complete.

Proof. Membership in Σ_{2}^{P} is already implicit from the membership part of the proof of Theorem 3.

Hardness for Σ_{2}^{P} follows by a simple reduction of evaluating a fixed Σ_{2}^{P} -hard query Q = ⟨LP, G⟩ under ∃_{TS} semantics, where LP is stratified and G is an atom. The existence of such Q follows from Lemma 2. Notice that for every D, by Proposition 2, PS_{LP_{D}} = TS_{LP_{D}}, and thus each P-stable model of LP_{D} is total. Let LP′ be the program obtained by adding to LP the following clauses, where a, b and c are new propositional atoms:

\begin{matrix}a ∨ b ∨ c ← & ¬G \\ b ← & ¬a, ¬G \\ c ← & ¬b, ¬G \\ a ← & ¬c, ¬G \end{matrix}

These clauses do not have a P-stable model. Asserting that G is true, however, {¬a, ¬b, ¬c} is a P-stable model. Since every P-stable model of LP_{D} contains either G or ¬G, it is thus easy to see that LP′_{D} has a P-stable model iff LP_{D} has a P-stable model containing G. This shows Σ_{2}^{P} -hardness.

Corollary 1 Let Q = ⟨LP, G⟩ be a fixed query. Deciding, given database D, whether LP_{D} has an M-stable model, is Σ_{2}^{P} -complete. The same holds for L-stable models.

Proof. From Definition 3, M-stable and L-stable models exist for a program iff it admits some P-stable model. The statement therefore follows from Theorem 14.

Notice that in [21] it was shown that deciding whether a given propositional program has a P-stable (equivalently, a 3-valued stable) model is Σ_{2}^{P} -complete. This result, which is on expression complexity of propositional DATALOG^{∨,¬} programs, is an immediate consequence of the preceding theorem (which is on data complexity), while it needs a little extrawork to derive the latter result from the former.

4.2 Expression Complexity

Intuitively, the expression complexity is exponentially higher than the data complexity, since the size of LP_{D} is exponential in the the size of D. Thus, we expect that the program complexity of partial model semantics parallels the data complexity in the exponential analog of the polynomial hierarchy NP = Σ_{1}^{P}, Σ_{2}^{P} = NP^{NP}, Σ_{3}^{P} = NP^{Σ_{2}^{P}}…; the proper analog is the weak exponential hierarchy, which consists of the classes NEXP = Σ_{1}^{E}, Σ_{2}^{E} = NEXP^{NP}, Σ_{3}^{E} = NEXP^{Σ_{2}^{P}}, …. It turns out that this intuition is correct.

Theorem 15 (Possibility inference) Let D be a fixed database. Deciding, given a query Q, whether Q is true on D under ∃_{XS} semantics is (a) Σ_{2}^{E}-complete for XS from PS, MS, RS, and (b) Σ_{3}^{E}-complete for LS.

Theorem 16 (Certainty inference) Let D be a fixed database. Deciding, given a query Q, whether Q is true on D under ∀_{XS} semantics is (a) Π_{2}^{E}-complete for XS = PS, and (b) Π_{3}^{E}-complete for XS from MS, LS, and RS, where Π_{k}^{E} = coΣ_{k}^{E}, k ≥ 0.

Proof. The membership parts of the theorems are easy to see from the proofs that for a fixed query Q, EXP_{XS}^{∀}(Q) (resp. EXP_{XS}^{∃}(Q)) define database collections in corresponding classes of the polynomial hierarchy.

The hardness parts follow from the facts that evaluating a given second order formula Φ from the Σ_{k}^{1} (resp. Π_{k}^{1} ) fragment on a fixed database D is complete for Σ_{k}^{E} (resp. Π_{k}^{E}) [30], and that the proofs of all expressiveness results in the previous section implicitly provide polynomial time transformations of evaluating a formula Φ on D into evaluating an equivalent query Q = ⟨LP, G⟩ on D. Indeed, the proof of Lemma 2 in [22] constructs a query Q = ⟨LP, G⟩ equivalent to a Σ_{2}^{1} formula Ψ; tracing the proof, it is easy to see that Q can be effectively computed in polynomial time. Thus, each of the queries Qi = ⟨LPi, Gi⟩ in the expressibility proofs from above can be clearly constructed in polynomial time from the given formulas Φ. This gives polynomial time transformations of evaluating formulas Φ on D into evaluating queries Q on D, and proves the hardness parts.

5 The Impact of Disjunction and Negation

The previous section gave a complete description of the expressive power and complexity of evaluating queries Q = ⟨LP, G⟩ based on DATALOG^{∨,¬} programs LP that resort to partial model semantics. An interesting issue is the impact of syntactical restrictions on the query programs LP. In particular, comparing the power of disjunction with the power of negation is intriguing [22].

In an account of this issue, we focus here on the most powerful concepts of partial models, which are those that minimize undefinedness, and discuss queries whose programs make limited use of disjunction and negation. Starting from normal positive programs (i.e., pure datalog programs), we consider the effect of allowing the (combined) use of the following constructs:

• stratified negation (¬_{s})

• arbitrary negation (¬)

• headcycle-free disjunction [6, 7] (∨_{h})

• arbitrary disjunction (∨)

Headcycle-free disjunction is a syntactical property of programs that gives no account to negation. A program LP is headcycle-free iff there are no two distinct atoms a, b ∈ B_{LP} such that a and b are on a negation-free cycle of the dependency graph of ground(LP) (i.e., a and b mutually depend on each other without negation) and a, b occur together in the head of some clause of ground(LP). It is known that admitting headcycle-free disjunction besides full negation does not increase the complexity of T-stable models. The following proposition, which is implicit in [6], is straightforward from the fact that checking whether a total model of a positive headcycle-free program is minimal is polynomial [8].

Proposition 7 (cf. [6, 8]) Let LP be a ground (i.e., propositional) headcycle-free program and let M be an interpretation of it. Then, deciding if M is a T-stable model of LP is polynomial.

We say that a query Q = ⟨LP, G⟩ uses headcycle-free disjunction iff LP is disjunctive and LP_{D} is headcycle-free for each D, and similarly that Q is (locally) stratified iff LP_{D} is (locally) stratified for each D.

The expressive power of headcycle-free, stratified queries (that we denote by Q_{∨_{h},¬_{s}}) has been investigated in [8] in a different setting. There, it is shown that every polynomial time computable output-query (a query that computes an output relation) can be “weakly expressed” in Q_{∨_{h},¬_{s}} using T-stable models, i.e., the query result is given by some T-stable model; if the input databases are ordered, it can be expressed in a stronger sense, i.e., the result is given by every T-stable model. Notice that such a notion of semantics is in general different from the usual notion of certainty or possibility inference. For bound (i.e., boolean) queries, weak expressibility coincides with possibility inference. Notice that the expressive power of headcycle-free stratified bound queries is higher than DB-P, and in fact DB-NP (see Figure 2).

By Q_{np} we denote the set of queries Q = ⟨LP, G⟩ such that LP is a normal positive program; for any combination X of constructs from above, we denote by Q_{X} the extension of Q_{np} in Q where the constructs in X may be used in query programs. Note that the programs in Q_{∨} and Q_{∨_{h}} are ¬-free, while the programs in Q_{¬} and Q_{¬_{s}} are ∨-free.

The inclusion order diagrams of the resulting different fragments of Q, together with their expressive powers under ∃_{XS} and ∀_{XS} inference, where XS is from LS, MS, RS, are displayed in Figure 2. Notice that different combinations X may give rise to the same fragment (e.g., X = ∨, ∨_{h}, ¬, ¬_{s} and X′ = ∨, ¬); we have chosen for each fragment the smallest X as a representative.

There are two main observations on the diagrams. First, the diagrams for ∃_{LS} inference differs from the diagram for ∃_{MS} and ∃_{RS} inference only on the three points along the right upper part of the outline (that is, on Q_{∨,¬}, Q_{∨_{h},¬}, and Q_{¬}). Coincidence on the remaining part is an immediate consequence of the coincidence of L-stable, M-stable and regular models on locally stratified programs (see Proposition 2), since in the respective fragments of Q at most locally stratified negation can be used. Second, the diagram for ∀_{LS}, ∀_{MS}, and ∀_{RS} inference is the same and just symmetric to the diagram for ∃_{LS} inference. For the fragments that allow at most locally stratified negation, this is an easy consequence of the facts that the concepts of models coincide to T-stable models, that always a T-stable model exists and that on any database D, the ∃_{TS} answer of ⟨LP, L⟩ is opposite to the ∀_{TS} answer of ⟨LP, ¬L⟩.

Observe also that each of DB-Σ_{i}^{P} and DB-Π_{i}^{P} for i = 1, 2, 3 is expressed by at least one fragment. On the other hand, some fragments, namely Q_{¬_{s}}, Q_{∨} and the more restrictive fragments, allow to express only a strict subclass of the respective classes DB-C; however, as shown below, they include queries that are hard for C (see below).

An example of a nonexpressible query for all these fragments is the Even-Constants query, which tells whether a given database D on a fixed scheme DB contains an even number of constants.

Proposition 8 The Even-Constants query can not be expressed in Q_{∨} ∪ Q_{¬_{s}} using ∃_{XS} or ∀_{XS} inference, for any XS from PS, TS, MS, LS, and RS.

Proof. Notice that each query in Q_{∨} ∪ Q_{¬_{s}} is stratified, and thus it suffices to consider XS = TS by Proposition 2.

By the results in [16, 33], it is immediate that the Even-Constants query can not be expressed in Q_{¬_{s}} using ∃_{TS} inference: locally stratified queries are no more expressive than stratified queries [9], and stratified queries can only express fixpoint-queries [33], by which the Even-Constants query can not be defined [16]; notice that ∃_{TS} inference coincides with ∀_{TS} inference in Q_{¬_{s}}.

It was reported in [22] that for a minor variant of the Even-Constants query, there is in Q_{∨} no query Q = ⟨LP, G⟩ where G is a propositional atom, such that Q coincides under ∃_{TS} inference (or ∀_{TS} variant as well) with this variant. That result immediately implies the same for the Even-Constants query.

Since all queries in Q_{∨} are ¬-free (and hence stratified), it remains by Proposition 2 to show that no query Q = ⟨LP, ¬a⟩ from Q_{∨}, where a is a propositional atom, can define

[figure: DB-Σ_{2}^{P}; Q_{¬}; Q_{¬_{s}}; DB-Σ_{3}^{P}; DB-Σ_{2}^{P}; ⊂DB-P; ⊂DB-NP; ⊂DB-P; ⊂DB-Σ_{2}^{P}; Q_{np}; ∃_{LS} inference; Q_{∨}; Q_{∨,¬} (=Q); Q_{∨_{h}}; Q_{∨,¬_{s}}; Q_{∨_{h},¬}; DB-Σ_{2}^{P}; Q_{∨_{h},¬_{s}}; DB-NP; ⊂DB-P; Q_{∨_{h},¬_{s}}; ⊂DB-Σ_{2}^{P}; ⊂DB-NP; Q_{∨}; Q_{∨,¬_{s}}; Q_{∨_{h}}; Q_{∨,¬} (=Q); DB-Σ_{2}^{P}; Q_{∨_{h},¬}; Q_{np}; ⊂DB-P; DB-Σ_{2}^{P}; DB-NP; Q_{¬_{s}}; DB-NP; Q_{¬}; ∃_{MS}, ∃_{RS} inference; DB-NP]

[figure: ⊂DB-P; Q_{∨_{h},¬_{s}}; ⊂DB-Π_{2}^{P}; ⊂DB-coNP; Q_{∨}; Q_{∨,¬_{s}}; Q_{∨_{h}}; Q_{∨,¬} (=Q); DB-Π_{2}^{P}; Q_{∨_{h},¬}; Q_{np}; ⊂DB-P; DB-Π_{3}^{P}; DB-Π_{2}^{P}; Q_{¬_{s}}; DB-Π_{2}^{P}; Q_{¬}; ∀_{LS}, ∀_{MS}, ∀_{RS} inference; DB-coNP]

Figure 2: Expressive power of queries based on partial models minimizing undefinedness the Even-Constants query using ∃_{TS} (resp. ∀_{TS}) inference.

Assume such a Q using ∃_{TS} inference exists. Define Q′ = ⟨LP ∪ {a ∨ b ←}, b⟩, where b is a new propositional atom. Then, for any D the ∃_{TS} answer for Q′ coincides with the ∃_{TS} answer for Q. Hence, Q′ would embody the Even-Constants query, and we reached a contradiction.

Now assume such a Q under ∀_{TS} inference exists. Then, for any D the ∃_{TS} answer of Q′ = ⟨LP, a⟩ is opposite to the ∀_{TS} answer of Q. Hence, Q′ defines the complement of the Even-Constants query under ∃_{TS} inference. Since the Even-Constants query is not in Q_{∨}, it is easy to verify that also its complement is not in Q_{∨}; hence, the existence of Q leads to a contradiction.

Let us verify the upper bounds for the expressive powers of the fragments. We first consider the fragments in which no negation or only stratified negation ¬_{s} is allowed. Note that T-stable, L-stable, M-stable, and regular models coincide on the programs of such queries. Since each of these fragment expresses under ∃_{TS} inference just the complement of the queries under ∀_{TS} inference, we consider only ∃ inference in the sequel.

From Lemma 2, on Σ_{2}^{P} -recognizability of ∃_{TS} inference, and Proposition 8, we have the following.

Theorem 17 EXP_{XS}^{∃}[Q_{∨,¬_{s}}] = DB-Σ_{2}^{P} and

EXP_{XS}^{∃}[Q_{∨}] ⊂ DB-Σ_{2}^{P}, for XS = TS, LS, MS, RS.

Restricting ∨ to ∨_{h} besides restricting ¬ to ¬_{s} leads to a decrease in expressive power. In fact, only queries in DB-NP can be expressed in Q_{∨_{h}} using ∃_{TS} inference. On the other hand, if ¬_{s} is allowed, then all of DB-NP can be expressed.

Theorem 18 EXP_{XS}^{∃}[Q_{∨_{h},¬_{s}}] = DB-NP and

EXP_{XS}^{∃}[Q_{∨_{h}}] ⊂ DB-NP, for XS from TS, LS, MS, RS.

Proof. By Proposition 2, it suffices to consider ∃_{TS} inference.

It is straightforward to derive from Proposition 7 that, for any query Q ∈ Q_{∨_{h},¬_{s}}, deciding whether a given database D belongs to EXP_{TS}^{∃}(Q) is in NP. Thus, it follows from Proposition 8 that EXP_{XS}^{∃}[Q_{∨_{h}}] ⊂ DB-NP.

It remains to show that every NP-recognizable database collection D is in EXP_{TS}^{∃}[Q_{∨_{h},¬_{s}}]. We use Fagin’s Theorem [25] and construct for any existential second order formula Φ a headcycle-free stratified query Q = ⟨LP, G⟩ such that Q is true on D under ∃_{TS} inference iff Φ is true on D. We assume that Φ is in second-order Skolem normal form [35], i.e.

Φ = (∃A)(∀X)(∃Y)(θ_{1}(X, Y) ∨ ⋯ ∨ θ_{k}(X, Y))

where A is a list of predicate variables, X, Y are lists of individual variables, and the θ_{i} are conjunctions of literals.

LP consists of the following clauses (cf. [51, 35] for similar programs that are nondisjunctive but use unstratified negation):

(i) a(X_{1}, …, X_{n}) ∨ â(X_{1}, …, X_{n}) ← , for every a occurring in A, where â is a new predicate;

(ii) q(X) ← θ′_{i}(X, Y), for i = 1, …, k, where θ′_{i} denotes the literals of θ_{i}, among which equality (resp. inequality) atoms X = Y (resp. X ≠ Y) are replaced with eq(X, Y) and ¬eq(X, Y), respectively, where q and eq are new predicates;

(iii) f ← ¬q(X) , where f is a new propositional atom; and

(iv) eq(X, X) ←

Now let Q = ⟨LP, ¬f⟩. Clearly, Q is headcycle-free and stratified. It is easily seen that Q answers true for D under ∃_{TS} inference iff Φ is true on D. This proves the theorem.

The expressive power of Q_{np} and Q_{¬_{s}} has been studied extensively (see [32, 2]). Notice that on these fragments, ∃_{TS} coincides with ∀_{TS}, since TS contains a single model. It is well-known that Q_{¬_{s}} expresses a strict subset of DB-P (in fact, even a strict subset of the fixpoint-queries [33]), and that Q_{np} can express only monotonic queries (see [2] for monotonic queries). Thus, Q_{∨_{h}} and Q_{¬_{s}} allow for queries of different complexity.^{7}

It remains to consider the fragments in which full negation ¬ is allowed. The results for the top elements in the diagrams (Q_{∨,¬}) have been established in Section 3, while the results on the expressive power of Q_{¬} for LS, MS have been derived in [47, 48]; by Proposition 3, they carry over to RS.

In order to justify the results for the last fragment Q_{∨_{h},¬} that we have to consider, it suffices to show that for each mode of inference, query-recognizability has the same upper bound as on Q_{¬}. The key result is that recognizing P-stable models of a program does not become harder if besides negation also headcycle-free disjunction is allowed.

To show this, we provide a helpful characterization of P-stable models, which is proven in the appendix. For any program LP and interpretation I of it, denote by red(LP, I) the program obtained from ground(LP) as follows: (1) Remove every rule r such that H(r) ∩ M^{+} ≠ ∅ or B^{−}(r) is false in M; (2) Remove from the remaining rules all negative literals and all atoms from M^{+}.

Lemma 3 Let LP be a program and M be a founded model of P. Then, M is a P-stable model of LP iff \overline{M} = N^{+} for some N ∈ MM^{+}(red(LP, M)).

7In fact the expressive powers of Q_{∨_{h}} and Q_{¬_{s}} are incomparable: the collection of 3-colorable graphs can be defined in Q_{∨_{h}} using ∃-inference (as demonstrated below), but not in Q_{¬_{s}} (since Q_{¬_{s}} resorts to a fragment of L_{∞,ω}^{ω}, in which 3-colorability can not be defined [18]). On the other hand, e.g. a query whether two relations R_{1}, R_{2} contain the same tuples is simple in Q_{¬_{s}}, while it is impossible in Q_{∨_{h}} (the proof is easy with a weak monotonicity property of DATALOG^{∨} query programs derived in [22]).

Proof. See appendix.

Using this lemma, it is straightforward to derive a generalization of Proposition 7 from T-stable to P-stable models. The lower complexity of recognizing T-stable and P-stable models entails also lower complexity for recognizing M-stable and L-stable models, as well as for recognizing regular models (due to lower complexity of recognizing minimal models for headcycle-free, positive programs).

Proposition 9 Let LP be a ground (i.e., propositional) headcycle-free program and let M be an interpretation of it. Then, deciding if (i) M ∈ PS is polynomial; and (ii) M ∈ XS is in coNP, for XS from LS, MS, and RS.

Proof. (i): By Lemma 3, M is P-stable iff (1) M is a model of LP, (2) M is founded (i.e., M^{+} = N_{1}^{+} for some N_{1} ∈ MM^{+}(LP(M))), and (3) \overline{M}^{+} = N_{2}^{+} for some N_{2} ∈ MM^{+}(red(LP, M)).

Notice that the programs LP(M) and red(LP, M) are headcycle-free, positive, and polynomial-time constructible. Since MM^{+}(LP′) = TS_{LP}′ for any positive program LP′ (this is a simple consequence of Proposition 2 and the definition of P-stable model), it follows from Proposition 7 that the tests (2) and (3) can be performed in polynomial time. (ii): For MS and LS, this follows easily from (i), and for RS, from Proposition 7 and the fact that LP(M) is positive (thus minimal total models coincide with T-stable models) and headcycle-free.

Using this properties, we derive the expressibility results for Q_{∨_{h},¬}.

Theorem 19 EXP_{LS}^{∃}[Q_{∨_{h},¬}] = DB-Σ_{2}^{P},

EXP_{MS}^{∃}[Q_{∨_{h},¬}] = EXP_{RS}^{∃}[Q_{∨_{h},¬}] = DB-NP, and
EXP_{XS}^{∀}[Q_{∨_{h},¬}] = DB-Π_{2}^{P}, for XS from LS, MS, RS.

Proof. By the expressiveness results for Q_{¬} in [47, 48] and Proposition 3, it remains to prove the upper bounds on expressiveness. For EXP_{LS}^{∃}[Q_{∨_{h},¬}] and EXP_{XS}^{∀}[Q_{∨_{h},¬}], where XS is from LS, MS, RS, they are easily derived from Proposition 9.

From Proposition 9 it is straightforward that the database collections in EXP_{PS}^{∃}[Q_{∨_{h},¬}] are NP-recognizable; since ∃_{MS} inference coincides with ∃_{PS} inference, the upper bound of DB-NP for EXP_{MS}^{∃}[Q_{∨_{h},¬}] is justified.

Finally, note that a literal L is a ∃_{RS} inference of a program LP iff there is some founded 3-valued model of LP such that L ∈ M. Since LP(M) is positive (which means that minimal total models and T-stable models coincide) and headcycle-free, it follows from Proposition 7 that deciding if L is a ∃_{RS} inference of a given ground program LP is in NP; the DB-NP upper bound for EXP_{RS}^{∃}[Q_{∨_{h},¬}] follows immediately. This proves the theorem.

Thus, we have verified all expressiveness results in Figure 2. As mentioned above, some fragments fail to express even simple queries (in particular, the Even-Constants query), but they include queries whose complexity matches with the upper bound on recognizability for the whole fragment.

To verify this, note that it is well-known that P-time hard queries can be expressed in Q_{np} (i.e., in standard datalog), e.g. the path systems query (cf. kola-vard-90); a Σ_{2}^{P} -hard query that uses only disjunction but no negation has been presented in [22]. Finally, 3colorability of a finite graph G = (V, E), which is well-known to be NP-complete, is easily expressed by a headcycle-free query under ∃-inference without the use of negation:

red(x) ∨ green(x) ∨ blue(x) ←
f ← e(x, y), red(x), red(y)
f ← e(x, y), green(x), green(y)
f ← e(x, y), blue(x), blue(y)

Here e is the the edge predicate, respectively. It holds that for a given graph G, the ∃_{XS} answer of Q = ⟨LP, ¬f⟩ is true iff G is 3-colorable, where XS is from TS, LS, MS, RS.

Since the fragments of Q that express a database collection DB-C contain database collections that are hard for C, it follows that the data complexity of each fragment of Q under any considered inference mode is complete for the complexity class C, where DB-C is the upper bound on the query complexity (in case of C = P, completeness is via logspace-reductions). We formulate this here as a result for ∃_{LS} inference; for the other modes of inference, the results are analogous according with Figure 2.

Theorem 20 Let Q be a fixed query from Q_{X}. Deciding, given a database D, whether Q is true on D under ∃_{LS} semantics is (a) P-time complete for X = np and X = ¬_{s};

(b) NP-complete for X = ∨_{h} and X = ∨_{h}, ¬_{s}; (c) Σ_{2}^{P} -complete for X = ∨, X = ∨, ¬_{s}, X = ¬ and X = ∨_{h}, ¬; and (d) Σ_{3}^{P} -complete for X = ∨, ¬.

The expression complexity of each fragment parallels the data complexity in the exponential analogues (EXPTIME, NEXP = Σ_{1}^{E}, NEXP^{NP} = Σ_{2}^{E},…) of the classes for the data complexity (P, NP = Σ_{1}^{P}, NP^{NP} = Σ_{2}^{P},…).

The hardness results for the fragments capturing a class Σ_{i}^{P} are immediate from the expressibility proofs above and [47] and the results in [30] (cf. Section 4.2 for a discussion). It remains to justify the hardness results for the other, noncapturing fragments.

It is known that inference of a ground atom from a given datalog program over a fixed database is EXPTIME-complete;^{8} hence, the expression complexity of Q_{np} and Q_{¬_{s}} is EXPTIME-hard. Σ_{2}^{E}-hardness of the expression complexity of Q_{∨} queries using ∃_{TS} inference was shown in [22]. The proof gave a reduction of solving a generalized 3-coloring problem on graphs (coCERT3COL), given in its succinct representation, to evaluating a Q_{∨} query using ∃_{TS} inference over a fixed database. The succinct problem representation consists of a boolean circuit, by which the bits of the normal representation can be uniformly computed [35, 42]; this boolean circuit is simulated by a positive disjunctive program.

8This is folklore and implicit in the work of [56, 16]; it can be also derived using results on relational data dependencies (G. Gottlob, personal communication).

A straightforward simplification and minor modification of the reduction in [22] yields a polynomial-time reduction of deciding 3-colorability of a graph G (which is a subproblem of coCERT3COL), given in succinct representation, to evaluating a query Q from Q_{∨_{h}} over a fixed database. In particular, the boolean circuit is simulated by a headcyclefree positive program. Since succinct graph 3-colorability is NEXP-hard [35], it follows that the expression complexity of Q_{∨_{h}} is NEXP-hard. This shows the results on the expression complexity. For ∃_{LS} inference, they are summarized as follows. (Again, for the other inference modes, they are analogous according with Figure 2).

Theorem 21 Let D be a fixed database. Deciding, given a query Q from Q_{X}, whether Q is true on D under ∃_{LS} semantics is (a) EXPTIME-complete for X = np and X = ¬_{s};

(b) NEXP-complete for X = ∨_{h} and X = ∨_{h}, ¬_{s}; (c) Σ_{2}^{E}-complete for X = ∨, X = ∨, ¬_{s}, X = ¬ and X = ∨_{h}, ¬; and (d) Σ_{3}^{E}-complete for X = ∨, ¬.

6 Conclusion

The results on the expressibility and complexity of partial model semantics in the general case, complemented by previously known results for total stable (T-stable) models [22, 21], are compactly represented in Table 1. There, each entry of a complexity class C symbolizes C-completeness, and each entry DB-C that C is captured (i.e., precisely the database collections in DB-C are expressible).

The results in (a) have been actually derived for the data complexity of bound queries, except for T-stable models and recognition of P-stable models. (Using the results in [21, 22], they can be easily extended to data complexity in these cases, too.)

It appears that using P-stable models as a substitute for T-stable models has no impact on the expressive power and the complexity of query evaluation. In fact, the full expressive power of P-stable models is available already with stratified disjunctive programs, on which all concepts of models in Table 1 coincide. Minimization of undefinedness imposes another level of data complexity in the polynomial hierarchy (except for possibility inference with M-stable or regular models), but also increases the expressive power in a balanced way, such that all queries within this complexity can be expressed.

From the point of complexity, there is no difference between M-stable, L-stable and regular models under certainty inference, while under possibility inference, L-stable models are more complex than M-stable and regular models. However, L-stable models coincide with T-stable models if some T-stable model exists, while this is not guaranteed for M-stable or regular models. In particular, the complexity of certainty inference under M-stable or regular models is not diminished by the assertion that the query program has T-stable models on every input database; this can be easily derived from the proofs of Therorems 5 and 11, which we leave to the interested reader. (Hint: use the observa-

P-Stable T-Stable M-Stable L-stable  Regular

(a) Recognition and Existence for propositional (ground) programs

Recognition  coNP  coNP  Π_{2}^{P}  Π_{2}^{P}  Π_{2}^{P}
Existence  Σ_{2}^{P}  Σ_{2}^{P}  Σ_{2}^{P}  Σ_{2}^{P}  guaranteed

(b) Expressive Power

Possibility  DB-Σ_{2}^{P}  DB-Σ_{2}^{P}  DB-Σ_{2}^{P}  DB-Σ_{3}^{P}  DB-Σ_{2}^{P}
Certainty  DB-Π_{2}^{P}  DB-Π_{2}^{P}  DB-Π_{3}^{P}  DB-Π_{3}^{P}  DB-Π_{3}^{P}

(c) Data Complexity

Possibility  Σ_{2}^{P}  Σ_{2}^{P}  Σ_{2}^{P}  Σ_{3}^{P}  Σ_{2}^{P}
Certainty  Π_{2}^{P}  Π_{2}^{P}  Π_{3}^{P}  Π_{3}^{P}  Π_{3}^{P}

(d) Program Complexity

Possibility  NEXP^{NP}  NEXP^{NP}  NEXP^{NP}  NEXP^{Σ_{2}^{P}}  NEXP^{NP}
Certainty  coNEXP^{NP} coNEXP^{NP} coNEXP^{Σ_{2}^{P}} coNEXP^{Σ_{2}^{P}} coNEXP^{Σ_{2}^{P}}

Table 1: Expressibility and complexity results on partial models

tion that each P-stable (resp. regular) model M′ of the program LP′_{D} from the proof of Theorem 4 such that M′ ≠ M is total, and hence T-stable.)

These observations candidate L-stable models as an attractive, natural candidate among L-stable, M-stable and regular models for approximating T-stable models.

The high complexity of inference using L-stable models (Σ_{3}^{P} resp. Π_{3}^{P}) is intuitively due to three sources of complexity that interact, in a sense, orthogonally: (1) the (possibly exponential) number of L-stable models; (2) the P-stability condition for a model (foundedness and maximal unfounded set condition); and, (3) the condition of minimal undefinedness. Similar intuitions underly the other kinds of models.

We have also investigated the impact of limited disjunction and negation on expressive power and complexity of partial models that minimize undefinedness. We found that fragments of the languages capture the classes Σ_{i}^{P}, Π_{i}^{P}, 1 ≤ i ≤ 3 of the polynomial hierarchy. An interesting result in this course is that negation is more powerful than disjunction (except for ∃_{MS}, ∃_{RS}) inference, which is not the case for T-stable models. Moreover, we found that the combination of headcycle-free disjunction and stratified negation allows to capture NP (or coNP) for every considered kind of model.

The results complement and extend previous results on disjunctive datalog and partial models for normal programs. They show that syntactic restrictions on query programs result in a broad spectrum of complexity classes that can be captured. In this context, interesting research issues remain to be addressed. One such issue are further syntactic restrictions and their effect on expressiveness and complexity. Another issue is to identify fragments of the language on which concepts of models coincide; in particular, fragments that extend locally stratified programs are interesting.

A Appendix

Lemma 3 Let LP be a program and M be a founded model of P. Then, M is a P-stable model of LP iff \overline{M} = N^{+} for some N ∈ MM^{+}(red(LP, M)).

Proof. From Definition 2, we have to prove that (a) ¬.M^{−} is a maximal unfounded set for LP w.r.t. M iff (b) \overline{M} = N^{+} for some N ∈ MM^{+}(red(LP, M)).

For convenience, let LP′ = red(LP, M). We first observe that the total interpretation I_{M} of LP′ such that I_{M}^{+} = \overline{M} is a model of LP′. Indeed, consider a rule r from LP′ such that H(r) is false in I_{M}. Then, by the definition of LP′, H(r) is false in M. Hence, there exists a rule r′ in ground(LP) such that B(r) = B^{+}(r′) − M^{+} ≠ ∅ and B^{−}(r′) is not false in M; since r′ is satisfied in M, it follows that B^{+}(r′) is false in M. Consequently, B(r) is false in M, and thus also false in I_{M}. Hence, r is satisfied in I_{M}. Observe also that, since M is a model, ¬.M^{−} is an unfounded set for LP w.r.t. M.

(a) ⟹ (b): Assume then that (b) is false. Then, some total model N of LP′ exists such that N ≺ I_{M}. We show that X = ¬.M^{−} ∪ (I_{M}^{+} − N^{+}) is a consistent unfounded set for LP′ w.r.t. M demonstrating that ¬.M^{−} is not a maximal unfounded set. (This intuitively means that the undefined atoms in \overline{M} − N^{+} can be switched to false without violating any rule of LP.)

Let r be a rule in ground(LP) with an atom from X in the head. If r has been discarded by the red(·, ·) tranformation, then it necessarily satisfies either Condition 1 or Condition 2 of Definition 1. Otherwise, let r′ be the rule corresponding to r in LP′. Then, by definition of red(·, ·) tranformation, we have: (i) H(r) ∩ M^{+} = ∅, (ii) H(r) = H(r′), (iii) B(r′) = B^{+}(r) − M^{+}, (iv) B(r′) ⊆ \overline{M}. Since N is a total model of LP′, either (1) B(r′) ⊈ N^{+} or (2) H(r′) ∩ N^{+} ≠ ∅. If (1) is the case, then (by (iii) and (iv) above) the body of r′, and consequently also the body of r, contains an atom in \overline{M} − N^{+}; thus, r satisfies Condition 1 of Definition 1, as B(r) ∩ X ≠ ∅. If (2) is the case, then r satisfies Condition 2 of Definition 1, as H(r) (which coincides with H(r′)) contains some element which is not in ¬.M^{−} ∪ X, since N^{+} is disjoint from both X and ¬.M^{−}. X is therefore a consistent unfounded set which contains properly ¬.M^{−} ( (a) ⟹ (b) is proven).

(a) ⟸ (b). Let N ∈ MM^{+}(red(LP, M)) such that N^{+} = \overline{M}. By contradiction, assume that the unfounded set ¬.M^{−} is not maximal (i.e., (a) does not hold). Let X be a consistent unfounded set for LP w.r.t. M containing ¬.M^{−} properly. We prove that the total interpretation J such that J^{+} = N^{+} − X is a total model for LP′ (note that this contradicts the minimality of N, as J ≺ N).

Let r be a rule in LP′ whose body is true w.r.t. J. Then, the body of r is true also w.r.t. N and, as N is a model for LP′, the head of r contains some atom in N^{+}, say a.

Now, if a is in N^{+}−X, then r is satisfied in J. Otherwise, a is necessarily in X. To see that r is satisfied also in the latter case, consider the rule r′ ∈ ground(LP) whose image (under red(·, ·) tranformation) is r. Since H(r′) contains some element of the unfounded set X, r′ must verify either Condition 1 or Condition 2 of Definition 1 for LP w.r.t. M. Condition 1 can not be verified, however: B(r′) ∩ ¬.M ≠ ∅ is not possible, since B^{−}(r′) ∩ ¬.M ≠ ∅ would mean that r is not in red(LP, M), and B^{+}(r′) ∩ ¬.M ≠ ∅ would imply that B(r) is false in J. Further, B(r′) ∩ X ≠ ∅ is not possible, since B^{+}(r′) ⊆ B(r) ∪ M^{+}, X ∩ M^{+} = ∅, and B(r) ⊆ J^{+} = N^{+} − X. Therefore, r′ must satisfy Condition 2, that is, H(r′) ⊈ (¬.M^{−} ∪ X). The head of r′ must hence contain some atom, say b, in (M^{+} ∪ \overline{M}) − X. b cannot be in M^{+}, otherwise r would not be in red(LP, M). Therefore b is in \overline{M} − X; consequently, b ∈ J. Thus, r′ (whose head concides with H(r)) is satisfied w.r.t. J. We arrived hence at the desired contradiction that a total interpretation J ≺ N is a model for LP′. We are done.

References

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

[2] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.

[3] K.R. Apt, R.N. Bol. Logic Programming and Negation: a Survey. Journal of Logic Programming, Vol. 19/20, May/July 1994, pp. 9–71.

[4] C. Baral, J. Lobo and J. Minker. Generalized Disjunctive Well-Founded Semantics for Logic Programs: Declarative Semantics. In Z. Ras, M. Zemenkova and M.L. Emrich, ed., Proc. Fourth International Symposium on Methods for Intelligent Systems (ISMIS-90), pp. 465–473, North Holland, 1990.

[5] C. Baral and V. Subrahmanian. Stable and Extension Class Theory for Logic Programs and Default Logic. Journal of Automated Reasoning, 8:345–366, 1992.

[6] R. Ben-Eliyahu and R. Dechter. Propositional Semantics for Disjunctive Logic Programs. In Proc. Joint International Conference and Symposium on Logic Programming (JICSLP-92), pp. 813–827, Washington DC, November 1992.

[7] R. Ben-Eliyahu and R. Dechter. Propositional Semantics for Disjunctive Logic Programs. Annals of Mathematics and Artificial Intelligence, 12:53–87, 1994.

[8] R. Ben-Eliyahu and L. Palopoli. Reasoning with Minimal Models: Efficient Algorithms and Applications. In Proc. Fourth International Conference on Principles of Knowledge Representation and Reasoning (KR-94), pp. 39–50, 1994.

[9] N. Bidoit. Negation in Rule-Based Database Systems: A Survey. Theoretical Computer Science, 78:3–83, 1991.

[10] N. Bidoit and C. Froidevaux. General Logic Databases and Programs: Default Semantics and Stratification. Information and Computation, 19:15–54, 1991.

[11] M. Cadoli and M. Schaerf. A Survey of Complexity Results for Non-monotonic Logics. Journal of Logic Programming, 17:127–160, 1993.

[12] M. Cadoli, L. Palopoli. Circumscribing Datalog: Expressive Power and Complexity. Manuscript, 1995.

[13] F. Cacace, S. Ceri, S. Crespi-Reghizzi, L. Tanca, R. Zicari. Integrating Object-Oriented Data Modeling with a Rule-Based Programming Paradigm. Proc. of 1990 ACM-SIGMOD Intern. Conf., Atlantic City, NJ, May, 23-25, 1990, pp. 225-236.

[14] S. Ceri, G. Gottlob, and L. Tanca. Logical Programming and Databases. Springer, 1990.

[15] D. Chimenti, R. Gamboa, R. Krishnamurthy, S. Naqvi, S. Tsur, C. Zaniolo. The LDL System Prototype. IEEE TKDE, Vol. 2, no. 1, 1990.

[16] A. Chandra and D. Harel. Structure and Complexity of Relational Queries. Journal of Computer and System Sciences, 25:99–128, 1982.

[17] Jan Chomicki and V.S. Subrahmanian. Generalized Closed World Assumption is Π_{2}^{0}- Complete. Information Processing Letters, 34:289–291, 1990.

[18] A. Dawar. A Restricted Second Order Logic for Finite Structures. In Proc. Workshop on Logic and Computational Complexity, D. Leivant (ed), Springer LNCS, 1995. To appear.

[19] J. Dix. Semantics of Logic Programs: Their Intuitions and Formal Properties. An Overview. Logic, Action and Information. Proc. of the Konstanz Colloquium in Logic and Information (LogIn’92), pp. 241-329, DeGruyter, 1995.

[20] P. Dung. Negation as Hypotheses: An Abductive Foundation for Logic Programming. In Proc. ICLP-91. MIT Press, 1991.

[21] T. Eiter and G. Gottlob. On the Computational Cost of Disjunctive Logic Programming: Propositional Case. Annals of Mathematics and Artificial Intelligence, 1995, to appear. (Abstract under different title in Proc. PODS 93)

[22] T. Eiter, G. Gottlob, and H. Mannila. Adding Disjunction to Datalog. In Proc. PODS-94, pp. 267–278, 1994.

[23] T. Eiter, N. Leone, and D. Saccà. On the Partial Semantics for Disjunctive Deductive Databases. Technical Report ISI-CNR, 1995. Invited submission to a special issue of Annals of Mathematics and Artificial Intelligence on advances in logic-based database languages.

[24] A. Kakas, P. Mancarella. Preferred Extensions are Partial Stable Models. Journal of Logic Programming, 14, pp. 341-348, 1992.

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

[26] J.A. Fernández and J. Minker. Semantics of Disjunctive Deductive Databases. Proc. 4th Intl. Conference on Database Theory (ICDT-92), pp. 21–50, Berlin, October, 1992.

[27] M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In Proc. Fifth Logic Programming Symposium (ILPS ‘88) , pp. 1070–1080, 1988. MIT Press.

[28] M. Gelfond and V. Lifschitz. Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing, 9:365-385, 1991.

[29] G. Gottlob. Complexity and Expressive Power of Disjunctive Logic Programming. In M. Bruynooghe, editor, Proc. of the International Logic Programming Symposium (ILPS), pp. 23–42, Ithaca NY, 1994. MIT Press.

[30] G. Gottlob, N. Leone, and H. Veith. Second-Order Logic and the Weak Exponential Hierarchies. In Proc. Conference on Mathematical Foundations of Computer Science (MFCS-95), Prague, 1995. Forthcoming. Full paper available as CD/TR 95/80, Christian Doppler Lab for Expert Systems, Information Systems Department, TU Wien.

[31] S. Greco, N. Leone, P. Rullo. COMPLEX: An Object-Oriented Logic Programming System. IEEE TKDE, vol. 4, no. 4, August 1992.

[32] P. Kanellakis. Elements of Relational Database Theory. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science B, 1990.

[33] Ph. Kolaitis. The Expressive Power of Stratified Logic Programs. Information and Computation, 90:50–66, 1991.

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

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

[36] N. Leone, P. Rullo. BQM: A System Integrating Logic, Objects, and Non-Monotonic Reasoning. Proc. 7th IEEE International Conference on Tools with Artificial Intelligence, Washington, November 5-8, 1995, (Forthcoming).

[37] J. LLoyd. Foundations of Logic Programming. Springer, Berlin, 1984.

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

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

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

[41] J. Minker. Overview of Disjunctive Logic Programming. Annals of Mathematics and Artificial Intelligence, 12:1–24, 1994.

[42] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

[43] G. Phipps, M. A. Derr, and K. A. Ross. Glue-NAIL!: A Deductive Database System. Proc. ACM-SIGMOD Conf. on Management of Data, pp. 308-317, 1991.

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

[45] R. Ramakrishnan, D. Srivastava, S. Sudarshan. CORAL - Control, Relations and Logic. Proc. of the 18th VLDB Conf., Vancouver, British Columbia, Canada, 1992.

[46] K.A. Ross. The Well Founded Semantics for Disjunctive Logic Programs. In W. Kim, J.–M. Nicolas and S. Nishio, ed., Proc. First International Conference on Deductive and Object-Oriented Databases (DOOD-89), pp. 385–402, Elsevier Science Pub., 1990.

[47] D. Saccà. The Expressive Powers of Stable Models for Bound and Unbound DATALOG Queries. Journal of Computer and System Sciences, to appear.

[48] D. Saccà. Deterministic and Nondeterministic Stable Model Semantics for Unbound DATA-LOG Queries. In Proc. 5th Intl. Conference on Database Theory (ICDT-95), LNCS 893, pp. 353–367, January 1995.

[49] D. Saccà and C. Zaniolo. Stable Models and Non-Determinism in Logic Programs with Negation. In Proc. PODS-90, pp. 205–218, 1990.

[50] C. Sakama. Possible Model Semantics for Disjunctive Databases. In W. Kim, J.–M. Nicolas and S. Nishio, ed., Proc. First International Conference on Deductive and Object-Oriented Databases (DOOD-89), pp. 1055–1060, 1990.

[51] J. Schlipf. The Expressive Powers of Logic Programming Semantics. Technical Report CIS-TR-90-3, CS Dept, Univ. Cincinnati, 1990. To appear in Journal of Computer and System Sciences. (Preliminary version in Proc. PODS-90, pp. 196–204.)

[52] J. Schlipf. A Survey of Complexity and Undecidability Results in Logic Programming. In H. Blair, W. Marek, A. Nerode, and J. Remmel, editors, Proc. of the Workshop on Structural Complexity and Recursion-Theoretic Methods in Logic Programming, pp. 93–102, Washington DC, November 1992. MSI, Cornell University.

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

[54] J. D. Ullman. Principles of Database and Knowledge Base Systems. Computer Science Press, 1989.

[55] 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.

[56] M. Vardi. Complexity of relational query languages. In Proc. 14th ACM-STOC, pp. 137–146, 1982.

[57] J.-H. You and L. Yuan. Three-Valued Formalization of Logic Programming: Is it Needed? In Proc. PODS-90, pp. 172–182, 1990.

[58] J.-H. You and L. Yuan. A Three-Valued Semantics for Deductive Databases and Logic Programs. Journal of Computer and System Sciences, 49:334–361, 1994.

[59] J.-H. You and L. Yuan. On the Equivalence of Semantics for Normal Logic Programming. Journal of Logic Programming, pp. 211–222, 1995.