[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Extending functional database languages to update completeness

  • Conference paper
  • First Online:
Advances in Databases (BNCOD 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 940))

Included in the following conference series:

Abstract

This paper discusses the update operators currently implemented in the functional database programming language PFL and the linear type system which regulates their use.

Updates in functional database programming languages pose a problem because if update operations are expressed as functions from an original database relation to a new updated relation then they are potentially inefficient. However destructive updates may compromise the confluence of the language, with the result that the meaning of an expression is ambiguous.

The update operators discussed here allow relations to be updated destructively but their use is constrained by a linear type system. The purpose of the linearity constraints is to ensure that at all stages in the evaluation of an expression intended to effect an update there is exactly one reference to each relation being updated. This means that the order in which updates are applied to each relation is always clear, and consequently that the meaning of every expression is unambiguous.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Abiteboul, S. and Vianu, V. Procedural languages for database queries and update, Journal of Computer and System Sciences, 41, 1990.

    Google Scholar 

  2. Bancilhon, F. et al. FAD, a powerful and simple database language, Proc. 13th VLDB Conference, 1991.

    Google Scholar 

  3. Barja, M.L. et al. An effective deductive object-oriented database through language integration, Proc. 20th VLDB, 1994.

    Google Scholar 

  4. Erwig, M. and Lipeck, U. A functional DBPL revealing high level optimizations, Proc. 3rd DBPL, Morgan-Kaufman, 1991.

    Google Scholar 

  5. Girard, J-Y. Linear logic, Theoretical Computer Science, 50, 1987.

    Google Scholar 

  6. Girard, J-Y., Lafont, Y. and Taylor, P. Proofs and types, Cambridge University Press, 1989.

    Google Scholar 

  7. Hughes, J. Why functional programming matters, The Computer Journal, 32(2), 1989.

    Google Scholar 

  8. Manchanda, S. Declarative expression of deductive database updates, Proc. ACM PODS, 1989.

    Google Scholar 

  9. Manino, M.V. Choi, I.J. and Batory, D.S. The Object-Oriented Functional Data Language, IEEE Trans. on Software Engineering, 16(11), 1990.

    Google Scholar 

  10. Milner, R. A theory of type polymorphism in programming, Journal of Computer and System Sciences, 17, 1978.

    Google Scholar 

  11. Morrison, R., Brown, F., Connor, R. and Dearle, A. The Napier-88 reference manual, Universities of Glasgow and St Andrews, PPRR-77-89, 1989.

    Google Scholar 

  12. Ohori, A., Buneman, P. and Breazu-Tannen, V. Database programming in Machiavelli — a polymorphic language with static type inference, Proc. ACM SIGMOD, 1989.

    Google Scholar 

  13. Peyton-Jones, S.L. The Implementation of Functional Programming Languages, Prentice Hall, 1987.

    Google Scholar 

  14. Peyton-Jones, S.L. and Wadler, P. Imperative functional programming, Proc. 20th ACM Symposium on Principles of Programming Languages, 1993.

    Google Scholar 

  15. Phipps, G., Derr, M.A. and Ross, K.A. Glue-Nail: A deductive database system, Proc. ACM SIGMOD Conference, 1991.

    Google Scholar 

  16. Poulovassilis, A. and Small, C. A functional programming approach to deductive databases, Proc. 17th VLDB Conference, 1991.

    Google Scholar 

  17. Poulovassilis, A. and Small, C. A domain-theoretic approach to integrating functional and logic databases, Proc. 19th VLDB, 1993.

    Google Scholar 

  18. Poulovassilis, A. and Small, C. Investigation of algebraic query optimisation techniques for database programming languages, Proc. 20th VLDB Conference, 1994.

    Google Scholar 

  19. Small, C. and Poulovassilis, A. An overview of PFL, Proc. 3rd DBPL, Morgan-Kaufman, 1991.

    Google Scholar 

  20. Small, C. A functional approach to database updates, Information Systems, 18(8), 1993.

    Google Scholar 

  21. Søndergaard, H. and Sestoft, P. Referential Transparency, Definiteness and Unfoldability, Acta Informatica, 27, 1990.

    Google Scholar 

  22. Trinder, P. Referentially transparent database languages, Proc. 1989 Glasgow Workshop on Functional Programming, 1989.

    Google Scholar 

  23. Wadler, P. Linear types can change the world ! In M. Broy and C. Jones (eds.) Programming Concepts and Methods, North Holland, 1990.

    Google Scholar 

  24. Wadler, P. Is there a use for linear logic ? In Conference on partial evaluation and Semantics Based Program Manipulation (PEPM), ACM Press, June 1991.

    Google Scholar 

  25. Wakeling, D. Linearity and laziness, PhD dissertation, University of York, November 1990.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Carole Goble John Keane

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Sutton, D., Small, C. (1995). Extending functional database languages to update completeness. In: Goble, C., Keane, J. (eds) Advances in Databases. BNCOD 1995. Lecture Notes in Computer Science, vol 940. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0000540

Download citation

  • DOI: https://doi.org/10.1007/BFb0000540

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60100-5

  • Online ISBN: 978-3-540-49427-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics