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, lieves 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.
Functional Queries in Datalog
Basta Stefano;
2002
Abstract
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, lieves 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
