Types and Persistence in Database Programming Languages.

@article{DBLP:journals/csur/AtkinsonB87,
  author    = {Malcolm P. Atkinson and
               Peter Buneman},
  title     = {Types and Persistence in Database Programming Languages},
  journal   = {ACM Comput. Surv.},
  volume    = {19},
  number    = {2},
  year      = {1987},
  pages     = {105-190},
  ee        = {db/journals/csur/AtkinsonB87.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Traditionally, the interface between a programming language and a database has either been through a set of relatively low-level subroutine calls, or it has required some form of embedding of one language in another. Recently, the necessity of integrating database and programming language techniques has received some long-overdue recognition. In response, a number of attempts have been made to construct programming languages with completely integrated database management systems. These languages, which we term database programming languages, are the subject of this review.

The design of these languages is still in its infancy, and the purpose of writing this review is to identify the areas in which further research is required. In particular, we focus on the problems of providing a uniform type system and mechanisms for data to persist. Of particular importance in solving these problems are issues of polymorphism, type inheritance, object identity, and the choice of structures to represent sets of similar values. Our conclusion is that there are areas of programming language research--modules, polymorphism, persistence, and inheritance--that must be developed and applied to achieve the goal of a useful and consistent database programming language. Other research areas of equal importance, such as implementation, transaction handling, and concurrency, are not examined here in any detail.

Copyright © 1987 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

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/An4-1 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/aDVD2 or /dvd

Online Edition: ACM Digital Library

References

[Aho and Ullman 1979]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120

[Ait-Kaci and Nasr 1985]

Hassan Aït-Kaci, Roger Nasr: LOGIN: A Logic Programming Language with Built-In Inheritance. J. Log. Program. 3(3): 185-215(1986)

[Albano et al. 1983]

...

[Albano et al. 1985a]

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

[Albano et al. 1985b]

Antonio Albano, Giorgio Ghelli, Renzo Orsini: The Implementation of Galileo's Persistent Values. Data Types and Persistence (Appin) 1985: 253-263

[Albano et al. 1985c]

...

[Albano et al. 1985]

Antonio Albano, Fosca Giannotti, Renzo Orsini, Dino Pedreschi: The Type System of Galileo. Data Types and Persistence (Appin) 1985: 101-119

[Amble et al. 1979]

...

[Astrahan et al. 1976]

Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976)

[Atkinson 1978]

Malcolm P. Atkinson: Programming Languages and Databases. VLDB 1978: 408-419

[Atkinson and Morrison 1984]

Malcolm P. Atkinson, Ronald Morrison: Persistent First Class Procedures are Enough. FSTTCS 1984: 223-240

[Atkinson and Morrison 1985a]

Malcolm P. Atkinson, Ronald Morrison: Procedures as Persistent Data Objects. ACM Trans. Program. Lang. Syst. 7(4): 539-559(1985)

[Atkinson and Morrison 1985b]

Malcolm P. Atkinson, Ronald Morrison: Types, Bindings and Parameters in a Persistent Environment. Data Types and Persistence (Appin) 1985: 3-20

[Atkinson and Morrison 1986]

...

[Atkinson et al. 1981]

...

[Atkinson et al. 1983a]

Malcolm P. Atkinson, Kenneth Chisholm, W. Paul Cockshott, Richard Marshall: Algorithms for a Persistent Heap. Softw., Pract. Exper. 13(3): 259-271(1983)

[Atkinson et al. 1983b]

Malcolm P. Atkinson, Peter J. Bailey, Kenneth Chisholm, W. Paul Cockshott, Ronald Morrison: An Approach to Persistent Programming. Comput. J. 26(4): 360-365(1983)

[Atkinson et al. 1984]

...

[Atkinson et al. 1986]

...

[Backus 1978]

John W. Backus: Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs. Commun. ACM 21(8): 613-641(1978)

[Balzer 1986]

...

[Bancilhon and Ramakrishnan 1986]

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52

[Bever and Lockemann 1985]

Martin Bever, Peter C. Lockemann: Database Hosting in Strongly-Typed Programming Languages. ACM Trans. Database Syst. 10(1): 107-126(1985)

[Borgida 1983]

...

[Borgida 1985a]

...

[Borgida 1985b]

Alexander Borgida, Keith E. Williamson: Accommodating Exceptions in Databases, and Refining the Schema by Learning from them. VLDB 1985: 72-81

[Borgida 1985c]

Alexander Borgida: Language Features for Flexible Handling of Exceptions in Information Systems. ACM Trans. Database Syst. 10(4): 565-603(1985)

[Brachman 1978]

...

[Brachman 1983]

Ronald J. Brachman: What IS-A Is and Isn't: An Analysis of Taxonomic Links in Semantic Networks. IEEE Computer 16(10): 30-36(1983)

[Bragger et al. 1983]

Richard P. Brägger, Andreas Dudler, Jürg Rebsamen, Carl August Zehnder: Gambit: An Interactive Database Design Tool for Data Structures, Integrity Constraints and Transactions. ICDE 1984: 399-407

[Brodie et al. 1983]

Michael L. Brodie, John Mylopoulos, Joachim W. Schmidt (Eds.): On Conceptual Modelling, Perspectives from Artificial Intelligence, Databases, and Programming Languages, Book resulting from the Intervale Workshop 1982. Topics in Information Systems Springer 1984, ISBN 3-540-90842-0
Contents

[Bruce and Wegner 1987]

Kim B. Bruce, Peter Wegner: An Algebraic Model of Subtype and Inheritance. DBPL 1987: 75-96

[Buneman 1985]

Peter Buneman: Data Types For Database Programming. Data Types and Persistence (Appin) 1985: 91-100

[Buneman and Atkinson 1986]

Peter Buneman, Malcolm P. Atkinson: Inheritance and Persistence in Database Programming Languages. SIGMOD Conference 1986: 4-15

[Buneman and Ohori 1986]

Peter Buneman, Atsushi Ohori: A Domain Theoretic Approach to Higher-Order Relations. ICDT 1986: 91-104

[Buneman and Ohori 1987]

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

[Buneman et al. 1982]

Peter Buneman, Robert E. Frankel, Rishiyur S. Nikhil: An Implementation Technique for Database Query Languages. ACM Trans. Database Syst. 7(2): 164-186(1982)

[Buneman et al. 1982]

...

[Burge 1977]

...

[Cardelli 1984a]

Luca Cardelli: A Semantics of Multiple Inheritance. Inf. Comput. 76(2/3): 138-164(1988)

[Cardelli 1984b]

...

[Cardelli and MacQueen 1985]

Luca Cardelli, David B. MacQueen: Persistence and Type Abstraction. Data Types and Persistence (Appin) 1985: 31-41

[Cardelli and Wegner 1985]

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

[Carey et al. 1986]

Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and File Management in the EXODUS Extensible Database System. VLDB 1986: 91-100

[Cattell 1983]

...

[Chen 1976]

Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976)

[Chung 1984]

...

[Clocksin and Mellish 1981]

W. F. Clocksin, Chris Mellish: Programming in Prolog. Springer 1981

[Codd 1970]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970)

[Codd 1979]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979)

[Cole and Morrison 1982]

...

[Copeland and Khoshafian 1987]

...

[Copeland and Maier 1984]

George P. Copeland, David Maier: Making Smalltalk a Database System. SIGMOD Conference 1984: 316-325

[Dahl and Nygaard 1966]

...

[Darlington et al. 1982]

...

[Date 1981a]

C. J. Date: Referential Integrity. VLDB 1981: 2-12

[Date 1981b]

C. J. Date: An Introduction to Database Systems, 3rd Edition. Addison-Wesley 1981

[Date 1983a]

C. J. Date: An Introduction to Database Systems, Volume II. Addison-Wesley 1983, ISBN 0-201-14474-3

[Date 1983b]

...

[Demers and Donahue 1979]

...

[Donahue et al. 1986]

...

[Eckhardt et al. 1985]

...

[Fairbairn 1982]

...

[Fairbairn 1985]

Jon Fairbairn: A New Type-Checker for a Functional Language. Data Types and Persistence (Appin) 1985: 69-87

[Gallaire and Minker 1978]

...

[Gallaire et al. 1984]

Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)

[Goguen and Meseguer 1984]

Joseph A. Goguen, José Meseguer: Equality, Types, Modules, and (Why not ?) Generics for Logic Programming. J. Log. Program. 1(2): 179-210(1984)

[Goldberg and Robson 1983]

Adele Goldberg, David Robson: Smalltalk-80: The Language and Its Implementation. Addison-Wesley 1983

[Goldstein and Bobrow 1980]

Ira P. Goldstein, Daniel G. Bobrow: Extenting Object Oriented Programming in Smalltalk. LISP Conference 1980: 75-81

[Gordon et al. 1979]

...

[Hall 1983]

Patrick A. V. Hall: Adding Database Management to Ada. SIGMOD Record 13(3): 13-17(1983)

[Hammer and McLeod 1980]

...

[Hammer and McLeod 1981]

Michael Hammer, Dennis McLeod: Database Description with SDM: A Semantic Database Model. ACM Trans. Database Syst. 6(3): 351-386(1981)

[Henderson and Morris 1976]

Peter Henderson, James H. Morris Jr.: A Lazy Evaluator. POPL 1976: 95-103

[Horowitz and Kemper 1983]

...

[Ichbiah et al. 1979]

...

[Iverson 1979]

Kenneth E. Iverson: Operators. ACM Trans. Program. Lang. Syst. 1(2): 161-176(1979)

[Jarke and Koch 1982]

...

[Jarke and Koch 1983]

Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206

[Jarke and Koch 1984]

Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)

[Jarke and Vassiliou 1985]

Matthias Jarke, Yannis Vassiliou: A Framework for Choosing a Database Query Language. ACM Comput. Surv. 17(3): 313-340(1985)

[Kahn et al. 1984]

...

[Kaplan 1983]

...

[Kent 1978]

...

[Kent 1979]

William Kent: Limitations of Record-Based Information Models. ACM Trans. Database Syst. 4(1): 107-131(1979)

[Kersten and Wasserman 1981]

Martin L. Kersten, Anthony I. Wasserman: The Architecture of the PLAIN Data Base Handler. Softw., Pract. Exper. 11(2): 175-186(1981)

[Khoshafian and Copeland 1986]

Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416

[Koch et al. 1983]

...

[Krablin 1985]

G. Lawrence Krablin: Building Flexible Multilevel Transactions in a Distributed Persistent Environment. Data Types and Persistence (Appin) 1985: 213-234

[Kulkarni and Atkinson 1983]

K. G. Kulkarni, Malcolm P. Atkinson: Implementing an Extended Functional Data Model Using PS-algol. Softw., Pract. Exper. 17(3): 171-185(1987)

[Kulkarni and Atkinson 1985]

K. G. Kulkarni, Malcolm P. Atkinson: EFDM: Extended Functional Data Model. Comput. J. 29(1): 38-46(1986)

[Lampson et al. 1977]

...

[Liskov 1981]

Barbara Liskov, Russell R. Atkinson, Toby Bloom, J. Eliot B. Moss, Craig Schaffert, Robert Scheifler, Alan Snyder: CLU Reference Manual. Lecture Notes in Computer Science Vol. 114 Springer 1981, ISBN 3-540-10836-X

[Liskov et al. 1983]

...

[MacQueen 1985]

David B. MacQueen: Modules for Standard ML. LISP and Functional Programming 1984: 198-207

[Maier et al. 1986]

David Maier, Jacob Stein, Allen Otis, Alan Purdy: Development of an Object-Oriented DBMS. OOPSLA 1986: 472-482

[Mall et al. 1984]

Manuel Mall, Joachim W. Schmidt, Manuel Reimer: Data Selection, Sharing, and Access Control In a Relational Scenario. On Conceptual Modelling (Intervale) 1982: 411-440

[Matthews 1985a]

...

[Matthews 1985b]

David C. J. Matthews: An Overview of the Poly Programming Language. Data Types and Persistence (Appin) 1985: 43-50

[McCarthy 1962]

...

[Merrett 1977]

T. H. Merrett: Relations as Programming Language Elements. Inf. Process. Lett. 6(1): 29-33(1977)

[Merrett 1983]

T. H. Merrett: Extending the Relational Algebra to Capture Less Meaning. SIGMOD Record 14(3): 55-68(1984)

[Merrett 1984]

...

[Merrett 1985a]

T. H. Merrett: First Steps to Algebraic Processing of Text. ICOD-2 Workshop on New Applications of Data Bases 1983: 109-127

[Merrett 1985b]

T. H. Merrett: Persistence and Aldat. Data Types and Persistence (Appin) 1985: 173-188

[Merrett and Düchting 1984]

...

[Michie 1968]

...

[Miller 1986]

Dale Miller: A Theory of Modules for Logic Programming. SLP 1986: 106-114

[Milner 1978]

Robin Milner: A Theory of Type Polymorphism in Programming. J. Comput. Syst. Sci. 17(3): 348-375(1978)

[Milner 1979]

Robin Milner: Flowgraphs and Flow Algebras. J. ACM 26(4): 794-818(1979)

[Milner 1983]

...

[Milner 1984]

Robin Milner: A Proposal for Standard ML. LISP and Functional Programming 1984: 184-197

[Morrison 1979]

...

[Morrison et al. 1985a]

Ronald Morrison, Alan Dearle, Peter J. Bailey, Alfred L. Brown, Malcolm P. Atkinson: The Persistent Store as an Enabling Technology for Integrated Project Support. ICSE 1985: 166-173

[Morrison et al. 1985b]

Ronald Morrison, Alfred L. Brown, Peter J. Bailey, Antony J. T. Davie, Alan Dearle: A Persistent Graphics Facility for the ICL PERQ. Softw., Pract. Exper. 16(4): 351-367(1986)

[Mycroft 1984]

...

[Mylopoulos and Wong 1980]

John Mylopoulos, Harry K. T. Wong: Some Features of the TAXIS Data Model. VLDB 1980: 399-410

[Mylopoulos et al. 1980]

John Mylopoulos, Philip A. Bernstein, Harry K. T. Wong: A Language Facility for Designing Database-Intensive Applications. ACM Trans. Database Syst. 5(2): 185-207(1980)

[Nikhil 1982]

...

[Nikhil 1984]

...

[Nixon 1983]

...

[Nixon 1984]

...

[OBrien 1983]

...

[OBrien et al. 1986]

Patrick O'Brien, Bruce Bullis, Craig Schaffert: Persistent and Shared Objects in Trellis/Owl. OODBS 1986: 113-123

[Ohori 1987]

Atsushi Ohori: Orderings and Types in Databases. DBPL 1987: 97-116

[Olle 1978]

...

[Ontologic Inc. 1986]

...

[Owoso 1984]

...

[Owoso 1985]

...

[Persistent Programming Research Group 1985]

...

[Pirotte and Lacroix 1980]

...

[Richard and Velez 1987]

...

[Rosenthal et al. 1986]

Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176

[Rowe 1985]

...

[Rowe and Shoens 1979]

Lawrence A. Rowe, Kurt A. Shoens: Data Abstractions, Views and Updates in RIGEL. SIGMOD Conference 1979: 71-81

[Samet 1981]

...

[Schmidt 1977]

Joachim W. Schmidt: Some High Level Language Constructs for Data of Type Relation. ACM Trans. Database Syst. 2(3): 247-261(1977)

[Schmidt and Brodie 1983]

...

[Schmidt and Mall 1983]

...

[Shipman 1981]

David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981)

[Shopiro 1979]

Jonathan E. Shopiro: Theseus - A Programming Language for Relational Databases. ACM Trans. Database Syst. 4(4): 493-517(1979)

[Skarra and Zdonik 1986]

Andrea H. Skarra, Stanley B. Zdonik: The Management of Changing Types in an Object-Oriented Database. OOPSLA 1986: 483-495

[Smith and Smith 1977]

John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation and Generalization. ACM Trans. Database Syst. 2(2): 105-133(1977)

[Smith et al. 1983]

...

[Stonebraker and Rowe 1986]

Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355

[Stonebraker et al. 1976]

Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976)

[Stroustroup 1986]

Bjarne Stroustrup: The C++ Programming Language, First Edition. Addison-Wesley 1986, ISBN 0-201-12078-X

[Swinehart et al. 1986]

Daniel C. Swinehart, Polle Zellweger, Richard J. Beach, Robert Hagemann: A Structural View of the Cedar Programming Environment. ACM Trans. Program. Lang. Syst. 8(4): 419-490(1986)

[Teitelman 1975]

...

[Tsichritzis and Lochovsky 1977]

...

[Turner 1981]

...

[Turner 1985]

D. A. Turner: Miranda: A Non-Strict Functional language with Polymorphic Types. FPCA 1985: 1-16

[Turner 1986]

...

[Ullman 1982]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6

[van Wijngaarden et al. 1969]

...

[Wasserman 1978]

...

[Wasserman and Booster 1981]

...

[Wasserman et al. 1981]

...

[Weihl and Liskov 1985a]

William E. Weihl, Barbara Liskov: Implementation of Resilient, Atomic Data Types. ACM Trans. Program. Lang. Syst. 7(2): 244-269(1985)

[Weihl 1985b]

William E. Weihl: Linguistic Support for Atomic Data Types. Data Types and Persistence (Appin) 1985: 191-212

[Wirth 1971]

Niklaus Wirth: The Programming Language Pascal. Acta Inf. 1: 35-63(1971)

[Wirth 1983]

Niklaus Wirth: Programming in Modula 2. Springer 1982, ISBN 3-540-11674-5

[Zdonik and Wegner 1985]

...