Functional queries in Datalog

A 'functional' query is a query whose answer is always defined and unique i.e. it is either true or false in all models. It has been shown that the expressive powers of the various types of stable models, when restricted to the class of DATALOG functional queries, do not in practice go beyond those of well-founded semantics, except for the least undefined stable models which, instead, capture the whole boolean hierarchy BH. In this paper we present a 'functional' language which, by means of a disciplined use of negation, achieves the desired level of expressiveness up to BH. Although the semantics of the new language is partial, all atoms in the source program are defined and possibly undefined atoms are introduced in a rewriting phase to increase the expressive power. We show that the language satisfies 'desirable' properties better than classical languages with (unstratified) negation and stable model semantics. We present an algorithm for the evaluation of functional queries and we show that exponential time resolution is required for hard problems only. Finally we present the architecture of a prototype of the language which has been developed.