A Domain-theoretic Approach to Integrating Functional and Logic Database Languages
Alexandra Poulovassilis, Carol Small · Very Large Data Bases · 1993
The advantages of logic languages with respect to search-based computation are well-understood, while the advantages of functional languages with respect to dcterministic computation are becoming increasingly rccognised. It is therefore natural to investigate the dcvelopment 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’““+ncs in the sense that any set of Datalogs’“+* 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 rcspcctive 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 fof 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 dclined, and describe how a particular constraint enforcement technique developed for logic databases can be adopted by PFL. Permission to copy witho~l fee all or prt of thir matrrial i.r granted provided that rhe copies are not madt ar d&r&ted for direct commercial ad-p, the VulB copyi& ~&CC and !he title of the publicadon and its dare pppcor, and noiice is given th copying ir by permission of the Very Large Data Base Endowment. To copy otherwise. or to repzk4isk reqnires a free andlor special pemtissionf lhe Endowment. I%vccdnp dibe 19th VLDD Cunfercncq Dublin, Ireland, 1993. Carol Small Dcpartmenl of Computer Scicncc, Birkbeck College, Malct St., London WClE 7HX