Notice that evaluating a given [DATALOG.sup.[disjunction],??] query program under p, L semantics on a given database (termed combined complexity in Vardi [1982]), is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]-complete as well.
We define a family of classes [DATALOG.sup.X,Y] of query programs, based on independent syntactical restrictions X and Y concerning disjunction and negation, respectively, as follows.
For example, [DATALOG.sup.[disjunction]], which we refer to as plain disjunctive Datalog, allows disjunction in the head and negation of predicates from R;(3) [DATALOG.sup.[disjunction],??], disjunctive Datalog, is the language of all query programs.
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the query language of [DATALOG.sup.X,Y] query programs [Pi], IO([Pi]) = (R, S), with semantics [[Mu].sub.inf,??] such that [[Mu].sub.inf,??]([Pi]) is the partial query
For the sake of brevity, we omit in the examples detailed formal proofs for the correctness of query programs. Such proofs are not difficult to obtain, however.
In the examples of the previous section, we have designed query programs in a hierarchical fashion.
As a consequence of Lemma 5.1, we can indeed write query programs that use stable models in a modular fashion, such that modules [[Pi].sub.2] use the output of modules [[Pi].sub.1].