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

@inproceedings{DBLP:conf/vldb/PoulovassilisS93,
  author    = {Alexandra Poulovassilis and
               Carol Small},
  editor    = {Rakesh Agrawal and
               Se{\'a}n Baker and
               David A. Bell},
  title     = {A Domain-theoretic Approach to Integrating Functional and Logic
               Database Languages},
  booktitle = {19th International Conference on Very Large Data Bases, August
               24-27, 1993, Dublin, Ireland, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1993},
  isbn      = {1-55860-152-X},
  pages     = {416-428},
  ee        = {db/conf/vldb/PoulovassilisS93.html},
  crossref  = {DBLP:conf/vldb/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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 anyset 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 respcective 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 powerdomain 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 asPFL 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.

Copyright © 1993 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

Serge Abiteboul, Stéphane Grumbach: A Rule-Based Language with Functions and Sets. ACM Trans. Database Syst. 16(1): 1-30(1991)

[2]

Antonio Albano, Luca Cardelli, Renzo Orsini: Galileo: A Strongly-Typed, Interactive Conceptual Language. ACM Trans. Database Syst. 10(2): 230-260(1985)

[3]

Jurgen Annevelink: Database Programming Languages: A Functional Approach. SIGMOD Conference 1991: 318-327

[4]

François Bancilhon, Ted Briggs, Setrag Khoshafian, Patrick Valduriez: FAD, a Powerful and Simple Database Language. VLDB 1987: 97-105

[5]

Don S. Batory, T. Y. Leung, T. E. Wise: Implementation Concepts for an Extensible Data Model and Data Language. ACM Trans. Database Syst. 13(3): 231-262(1988)

[6]

Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284

[7]

David Beech: A Foundation for Evolution from Relational to Object Databases. EDBT 1988: 251-270

[8]

Peter Buneman, Achim Jung, Atsushi Ohori: Using Powerdomains to Generalize Relational Databases. Theor. Comput. Sci. 91(1): 23-55(1991)

[9]

...

[10]

Luca Cardelli, Peter Wegner: On Understanding Types, Data Abstraction, and Polymorphism. ACM Comput. Surv. 17(4): 471-522(1985)

[11]

Luca Cardelli: Types for Data-Oriented Languages. EDBT 1988: 1-15

[12]

Stefano Ceri, Georg Gottlob, Letizia Tanca: Logic Programming and Databases. Springer 1990, ISBN 3-540-51728-6

[13]

Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy, Shamim A. Naqvi, Shalom Tsur, Carlo Zaniolo: The LDL System Prototype. IEEE Trans. Knowl. Data Eng. 2(1): 76-90(1990)

[14]

Keith L. Clark: Negation as Failure. Logic and Data Bases 1977: 293-322

[15]

...

[16]

Umeshwar Dayal, Frank Manola, Alejandro P. Buchmann, Upen S. Chakravarthy, David Goldhirsch, Sandra Heiler, Jack A. Orenstein, Arnon Rosenthal: Simplifying Complex Objects: The PROBE Approach to Modelling and Querying Them. BTW 1987: 17-37

[17]

Stéphane Grumbach: Integration of Functions Defined with Rewriting Rules in Datalog. DOOD 1989: 349-368

[18]

Sandra Heiler, Stanley B. Zdonik: Views, Data Abstraction, and Inheritance in the FUGUE Data Model. OODBS 1988: 225-241

[19]

J. Roger Hindley, Jonathan P. Seldin: Introduction to Combinators and Lambda-Calculus. Cambridge University Press 1986

[20]

Gabriel M. Kuper: On the Expressive Power of Logic Programming Languages with Sets. PODS 1988: 10-14

[21]

John W. Lloyd, Rodney W. Topor: A Basis for Deductive Database Systems. J. Log. Program. 2(2): 93-109(1985)

[22]

John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7

[23]

Michael V. Mannino, Injun Choi, Don S. Batory: The Object-Oriented Functional Data Language. IEEE Trans. Software Eng. 16(11): 1258-1272(1990)

[24]

Florian Matthes, Joachim W. Schmidt: The Type System of DBPL. DBPL 1989: 219-225

[25]

Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568

[26]

Atsushi Ohori, Peter Buneman, Val Tannen: Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference. SIGMOD Conference 1989: 46-57

[27]

Simon L. Peyton Jones: The Implementation of Functional Programming Languages. Prentice-Hall 1987

[28]

Alexandra Poulovassilis, Peter J. H. King: Extending the Functional Data Model to Computational Completeness. EDBT 1990: 75-91

[29]

Alexandra Poulovassilis, Carol Small: A Functional Programming Approach to Deductive Databases. VLDB 1991: 491-500

[30]

Swarup Reddi: Integrity Constraint Enforcement in the Functional Database Language PFL. BNCOD 1993: 238-257

[31]

...

[32]

Frank S. K. Silbermann, Bharat Jayaraman: A Domain-Theoretic Approach to Functional and Logic Programming. J. Funct. Program. 2(3): 273-321(1992)

[33]

Carol Small, Alexandra Poulovassilis: An Overview of PFL. DBPL 1991: 96-110

[34]

Harald Søndergaard, Peter Sestoft: Non-Determinism in Functional Languages. Comput. J. 35(5): 514-523(1992)

[35]

...

[36]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents