Functional queries in Datalog

Authors: Stefano Basta Sergio Flesca Sergio Greco

Publish Date: 2002/12/01

Volume: 20, Issue: 4, Pages: 339-371

PDF Link

Abstract

A ‘functional’ query is a query whose answer is always defined and unique ie 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 wellfounded semantics except for the least undefined stable models which instead capture the whole boolean hierarchyBHIn this paper we present a ‘functional’ language which by means of a disciplined use of negation achieves the desired level of expressiveness up toBH 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 developedStefano Basta PhD He received his PhD in “Ingegneria dei Sistemi e Informatica” from University of Calabria Italy in 2000 Since December 2000 he is Researcher for Institute of Systems Analysis and Information Technology of National Research Council ISICNR His research interests include logic programming deductive databases knowledge representation information integration data mining and data warehousingSergio Flesca PhD He received his PhD in computer science engineering at the university of Calabria Italy Currently he is a researcher in the Engineering Faculty at the University of Calabria He was a visiting researcher at the Computer Science Department of Vienna University of Technology His research interests include deductive and active database semistructured data XML query languages and XML wrapper inductionSergio Greco PhD He received his laurea degree in electrical engineering from University of Calabria Italy Currently he is a full professor at the faculty of Enginering at the University of Calabria Prior of this he was researcher at CRAI a research consortium in Informatics and assistant professor at the University of Calabria He was a visiting researcher at the research center of Microelectronics and Computer Center MCC of Austin Texas and at the Computer Science Department of University of California at Los Angeles His area of research includes database theory deductive database logic programming and query languages

Keywords: