A Domain-theoretic Approach to Integrating Functional and Logic Database Languages

摘要

The advantages of logic languages with respect to search-based computation are well-understood, while the advantages of functional languages with respect to deterministic computation are becoming increasingly recognised. It is therefore natural to investigate the development of languages which reconcile the two paradigms. As a contribution to this effort, we extend an existing functional database language called PFL with sets as first class objects. The resulting language subsumes Datalog~(fun+neg) in the sense that any set of Datalog~(fun+neg) rules can be translated into a set of PFL equations with the same semantics. Since functional and logic database languages can be considered as proper sub-languages of PFL, well-known optimisation techniques from both can usefully be employed (for example lazy evaluation for recursive functions and bottom-up evaluation techniques for recursive predicates). We motivate our work by reviewing the respective advantages of functional and logic programming for computation, data manipulation and data modelling. An overview of the previous version of PFL is presented and the syntax of this language is then extended to incorporate sets. We show how the Plotkin powcrdomain construction can be used to assign meaning to set expressions and we give a denotational semantics for the extended language. To illustrate its expressiveness, we show how Datalog rules can be expressed as PFL functions. We discuss the optimisation of these functions. We also show how integrity constraints can be defined, and describe how a particular constraint enforcement technique developed for logic databases can be adopted by PFL.