Complexity and expressive power of deterministic semantics for DATALOG

Deterministic models are (partial) stable models which are not contradicted dieted by any other stable model; i.e,, M is a deterministic no stable mod el N such that M boolean OR N is not an interpretation. For instanced the w ell-founded model, which coincides with the intersection of all partial sta ble models, is a deterministic model. As the well-founded model is determin istic and unique for each program, well-founded model semantics has been pr oposed as the canonical deterministic semantics for partial stable models. But the well-founded model is not the unique deterministic model; indeed th e family of deterministic (partial stable) models is not, in general, a sin gleton and admits a minimum (the wellfounded model) and a maximum, the max- deterministic model. The latter model is, another candidate for a determini stic semantics. The aim of this paper is to study the complexity and the ex pressive power of deterministic semantics. In coherence with the determinis tic nature of the model, the expressive power of max-deterministic semantic s is shown to be able to express problems with unique solutions, whereas th e well-founded model only captures a proper subset of the queries computabl e in polynomial time, the so-called fixpoint queries, (C) 1999 Academic Pre ss.