Polymorphism and Type Inference in Database Programming.

@article{DBLP:journals/tods/BunemanO96,
  author    = {Peter Buneman and
               Atsushi Ohori},
  title     = {Polymorphism and Type Inference in Database Programming},
  journal   = {ACM Trans. Database Syst.},
  volume    = {21},
  number    = {1},
  year      = {1996},
  pages     = {30-76},
  ee        = {http://doi.acm.org/10.1145/227604.227609, db/journals/tods/BunemanO96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In order to find a static type system that adequately supports database languages, we need to express the most general type of a program that involves database operations. This can be achieved through an extension to the type system of ML that captures the polymorphic nation of field selection, together with a techniques that generalizes relational operators to arbitrary data structures. The combination provides a statically typed language in which generalized relational databases may be cleanly represented as typed structures. As in ML types are inferred, which relieves the programmer of making the type assertions that may be required in a complex database environment.

These extensions may also be used to provide static polymorphic typechecking in object-oriented languages and databases. A problem that arises with object-oriented databases is the apparent need for dynamic typechecking when dealing queries on heterogeneous collections of objects. An extension of the type system needed for generalized relational operations can also be used for manipulating collections of dynamically typed values in a statically typed language. A prototype language based on these ideas has been implemented. While it lacks a proper treatment of persistent data, it demonstrates that a wide variety of database structures can be cleanly represented in a polymorphic programming language.

Copyright © 1996 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

[Atkinson and Buneman 1987]

Malcolm P. Atkinson, Peter Buneman: Types and Persistence in Database Programming Languages. ACM Comput. Surv. 19(2): 105-190(1987) BibTeX

[Abiteboul and Bonner 1991]

Serge Abiteboul, Anthony J. Bonner: Objects and Views. SIGMOD Conference 1991: 238-247 BibTeX

[Atkinson et al. 1983]

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) BibTeX

[Atkinson et al. 1989]

Malcolm P. Atkinson, François Bancilhon, David J. DeWitt, Klaus R. Dittrich, David Maier, Stanley B. Zdonik: The Object-Oriented Database System Manifesto. DOOD 1989: 223-240 BibTeX

[Albano et al. 1985]

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

[Abadi et al. 1991]

Martín Abadi, Luca Cardelli, Benjamin C. Pierce, Gordon D. Plotkin: Dynamic Typing in a Statically Typed Language. ACM Trans. Program. Lang. Syst. 13(2): 237-268(1991) BibTeX

[Appel and MacQueen 1991]

Andrew W. Appel, David B. MacQueen: Standard ML of New Jersey. PLILP 1991: 1-13 BibTeX

[Augustsson 1984]

...

[Bancilhon et al. 1988]

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

[Biskup 1981]

Joachim Biskup: A Formal Approach to Null Values in Database Relations. Advances in Data Base Theory 1979: 299-341 BibTeX

[Buneman et al. 1991]

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

[Buneman et al. 1994]

Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen, Limsoon Wong: Comprehension Syntax. SIGMOD Record 23(1): 87-96(1994) BibTeX

[Buneman and Ohori 1991]

Peter Buneman, Atsushi Ohori: A Type System that Reconsiles Classes and Extents. DBPL 1991: 191-202 BibTeX

[Breazu-Tannen et al. 1991]

Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19 BibTeX

[Breazu-Tannen et al. 1992]

Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX

[Breazu-Tannen and Subrahmanyam 1991]

Val Tannen, Ramesh Subrahmanyam: Logical and Computational Aspects of Programming with Sets/Bags/Lists. ICALP 1991: 60-75 BibTeX

[Cardelli 1986]

...

[Cardelli 1988]

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

[Cardelli and Mitchell 1989]

...

[Cardelli and Wegner 1985]

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

[Copeland and Maier 1984]

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

[Courcelle 1983]

Bruno Courcelle: Fundamental Properties of Infinite Trees. Theor. Comput. Sci. 25: 95-169(1983) BibTeX

[Damas and Milner 1982]

Luís Damas, Robin Milner: Principal Type-Schemes for Functional Programs. POPL 1982: 207-212 BibTeX

[Gallier and Snyder 1989]

Jean H. Gallier, Wayne Snyder: Complete Sets of Transformations for General E-Unification. Theor. Comput. Sci. 67(2&3): 203-260(1989) BibTeX

[Harper and Pierce 1991]

Robert Harper, Benjamin C. Pierce: A Record Calculus Based on Symmetric Concatenation. POPL 1991: 131-142 BibTeX

[Hart and Wong 1994]

...

[Hindley 1969]

...

[Hoang et al. 1993]

My Hoang, John C. Mitchell, Ramesh Viswanathan: Standard ML-NJ weak polymorphism and imperative constructs. LICS 1993: 15-25 BibTeX

[Hudak et al. 1992]

...

[Huet 1976]

...

[Hull and King 1987]

Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX

[Ichbiah et al. 1979]

...

[Imielinski and Lipski 1984]

Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX

[Immerman et al. 1991]

Neil Immerman, Sushant Patnaik, David W. Stemple: The Expressiveness of a Family of Finite Set Languages. PODS 1991: 37-52 BibTeX

[Jategaonkar and Mitchell 1988]

...

[Kim 1994]

Won Kim: Observations on the ODMG-93 Proposal. SIGMOD Record 23(1): 4-9(1994) BibTeX

[Leroy 1993]

Xavier Leroy: Polymorphism by Name for References and Continuations. POPL 1993: 220-231 BibTeX

[Leroy and Wies 1991]

Xavier Leroy, Pierre Weis: Polymorphic Type Inference and Assignment. POPL 1991: 291-302 BibTeX

[Lipski 1979]

Witold Lipski Jr.: On Semantic Issues Connected with Incomplete Information Databases. ACM Trans. Database Syst. 4(3): 262-296(1979) BibTeX

[MacQueen et al. 1986]

David B. MacQueen, Gordon D. Plotkin, Ravi Sethi: An Ideal Model for Recursive Polymorphic Types. Information and Control 71(1/2): 95-130(1986) BibTeX

[MacQueen 1988]

...

[Morrison et al. 1989]

...

[Milner 1978]

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

[Milner et al. 1990]

...

[Mitchell 1990]

...

[Object Design 1991]

...

[Ohori 1989a]

...

[Ohori 1989b]

...

[Ohori 1990]

Atsushi Ohori: Semantics of Types for Database Objects. Theor. Comput. Sci. 76(1): 53-91(1990) BibTeX

[Ohori 1992]

Atsushi Ohori: A Compilation Method for ML-Style Polymorphic Record Calculi. POPL 1992: 154-165 BibTeX

[Ohori and Buneman 1988]

...

[Ohori and Buneman 1994]

...

[Ohori et al. 1989]

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

[Ohori 1995]

Atsushi Ohori: A Polymorphic Record Calculus and Its Compilation. ACM Trans. Program. Lang. Syst. 17(6): 844-895(1995) BibTeX

[Plotkin 1979]

Gordon D. Plotkin: Call-by-Name, Call-by-Value and the lambda-Calculus. Theor. Comput. Sci. 1(2): 125-159(1975) BibTeX

[Rémy 1992]

Didier Rémy: Typing Record Concatenation for Free. POPL 1992: 166-176 BibTeX

[Rémy 1994]

...

[Robinson 1965]

John Alan Robinson: A Machine-Oriented Logic Based on the Resolution Principle. J. ACM 12(1): 23-41(1965) BibTeX

[Schmidt 1977]

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

[Stroustrup 1991]

Bjarne Stroustrup: The C++ Programming Language, Second Edition. Addison-Wesley 1991, ISBN 0-201-53992-6
BibTeX

[Stonebraker and Rowe 1986]

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

[Tofte 1988]

...

[Turner 1985]

...

[Wadler 1991]

...

[Wand 1987]

Mitchell Wand: Complete Type Inference for Simple Objects. LICS 1987: 37-44 BibTeX

[Wand 1988]

Mitchell Wand: Corrigendum: Complete Type Inference for Simple Objects. LICS 1988: 132 BibTeX

[Wand 1989]

Mitchell Wand: Type Inference for Record Concatenation and Multiple Inheritance. LICS 1989: 92-97 BibTeX

[Watt and Trinder 1991]

...

[Wirth 1977]

Niklaus Wirth: Modula: a Language for Modular Multiprogramming. Softw., Pract. Exper. 7(1): 3-35(1977) BibTeX

[Wong 1994]

...

[Zaniolo 1984]

Carlo Zaniolo: Database Relations with Null Values. J. Comput. Syst. Sci. 28(1): 142-166(1984) BibTeX

Referenced by

1. Suad Alagic: Type-Checking OQL Queries In the ODMG Type Systems. ACM Trans. Database Syst. 24(3): 319-360(1999)
2. Jan Van den Bussche, Emmanuel Waller: Type Inference in the Polymorphic Relational Algebra. PODS 1999: 80-90
3. Meike Albrecht, Margita Altus, Martin Steeg: Application-Oriented Design of Behavior: A Transformational Approach Using RADD. ER 1997: 323-332
4. Meike Albrecht, Margita Altus, Martin Steeg: Conceptual Data Modeling, Implementation Prototyping, Transformation, and Application Design - An Animating Approach using RADD. ADBIS 1997: 231-240
5. Atsushi Ohori, Keishi Tajima: A Polymorphic Calculus for Views and Object Sharing. PODS 1994: 255-266
6. Sunit K. Gala, Shamkant B. Navathe, Manuel E. Bermudez: Voltaire: A Database Programming Language with a Single Execution Model for Evaluating Queries, Constraints amd Functions. ICDE 1993: 283-292
7. Christian Laasch, Marc H. Scholl: A Functional Object Language. DBPL 1993: 136-156