skip to main content
10.1145/1159842.1159846acmconferencesArticle/Chapter ViewAbstractPublication PagesicfpConference Proceedingsconference-collections
Article

Strong types for relational databases

Published: 17 September 2006 Publication History

Abstract

Haskell's type system with multi-parameter constructor classes and functional dependencies allows static (compile-time) computations to be expressed by logic programming on the level of types. This emergent capability has been exploited for instance to model arbitrary-length tuples (heterogeneous lists), extensible records, functions with variable length argument lists, and (homogenous) lists of statically fixed length (vectors).We explain how type-level programming can be exploited to define a strongly-typed model of relational databases and operations on them. In particular, we present a strongly typed embedding of a significant subset of SQL in Haskell. In this model, meta-data is represented by type-level entities that guard the semantic correctness of database operations at compile time.Apart from the standard relational database operations, such as selection and join, we model functional dependencies (among table attributes), normal forms, and operations for database transformation. We show how functional dependency information can be represented at the type level, and can be transported through operations. This means that type inference statically computes functional dependencies on the result from those on the arguments.Our model shows that Haskell can be used to design and prototype typed languages for designing, programming, and transforming relational databases.

References

[1]
American National Standards Institute. ANSI X3.135-1992: Database Language SQL. 1992.
[2]
C. Beeri, R. Fagin, and J. H. Howard. A complete axiomatization for functional and multivalued dependencies in database relations. In Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pages 47--61, 1977.
[3]
B. Bringert and A. Höckersten. Student paper: HaskellDB improved. In Proc. of 2004 ACM SIGPLAN workshop on Haskell, pages 108--115. ACM Press, 2004.
[4]
P. Buneman and A. Ohori. Polymorphism and type inference in database programming. ACM Trans. Database Syst., 21(1):30--76, 1996.
[5]
P. Carreira and H. Galhardas. Efficient development of data migration transformations. In G. Weikum et al., editors, Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pages 915--916. ACM, 2004.
[6]
E. F. Codd. A relational model of data for large shared data banks. Commun. ACM, 13(6):377--387, 1970.
[7]
A. Cunha, J. N. Oliveira, and J. Visser. Type-safe two-level data transformation. In Proc. Int. Symp. Formal Methods, volume 4085 of Lecture Notes in Computer Science, pages 284--299. Springer, 2006.
[8]
C. J. Date. An Introduction to Database Systems, 6th Edition. Addison-Wesley, 1995.
[9]
R. Elmasri and S. B. Navathe. Fundamentals of Database Systems, 2nd Edition. Benjamin/Cummings, 1994.
[10]
T. Hallgren. Fun with functional dependencies. In Proc. of the Joint CS/CE Winter Meeting, pages 135--145, 2001. Dep.t of Computing Science, Chalmers, Göteborg, Sweden.
[11]
R. Hinze. Formatting: a class act. J. Funct. Program., 13(5):935--944, 2003.
[12]
A. Jaoua et al. Discovering Regularities in Databases Using Canonical Decomposition of Binary Relations. JoRMiCS, 1:217--234, 2004.
[13]
O. Kiselyov and R. Lämmel. Haskell's overlooked object system. Draft of 10 September 2005, 2005.
[14]
O. Kiselyov, R. Lämmel, and K. Schupke. Strongly typed heterogeneous collections. In Proc. of the ACM SIGPLAN workshop on Haskell, pages 96--107. ACM Press, 2004.
[15]
O. Kiselyov and C. Shan. Functional pearl: implicit configurations-or, type classes reflect the values of types. In Haskell '04: Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, pages 33--44, New York, NY, USA, 2004. ACM Press.
[16]
D. Leijen and E. Meijer. Domain specific embedded compilers. SIGPLAN Not., 35(1):109--122, 2000.
[17]
D. Maier. The Theory of Relational Databases. Computer Science Press, 1983.
[18]
C. McBride. Faking it - simulating dependent types in haskell. J. Funct. Program., 12(5):375--392, 2002.
[19]
C. Necco. Procesamiento de datos politípicos (polytypic data processing). Master's thesis, Universidad Nacional de San Luis, Departamento de Informática, Argentina, 2004.
[20]
C. Necco and J. N. Oliveira. Toward generic data processing. In Proc. WISBD'05, 2005.
[21]
A. Ohori and P. Buneman. Type inference in a database programming language. In LFP '88: Proc. of the 1988 ACM conference on LISP and functional programming, pages 174--183, New York, NY, USA, 1988. ACM Press.
[22]
A. Ohori, P. Buneman, and V. Tannen. Database programming in Machiavelli - a polymorphic language with static type inference. In J. Clifford et al., editors, Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pages 46--57. ACM Press, 1989.
[23]
S. L. Peyton Jones. Haskell 98: Language and libraries. J. Funct. Program., 13(1):1--255, 2003.
[24]
P. Stuckey and M. Sulzmann. A theory of overloading. ACM Trans. Program. Lang. Syst., 27(6):1216--1269, 2005.
[25]
J. D. Ullman. Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press, 1988.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
Haskell '06: Proceedings of the 2006 ACM SIGPLAN workshop on Haskell
September 2006
131 pages
ISBN:1595934898
DOI:10.1145/1159842
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 September 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Haskell
  2. SQL
  3. functional dependency theory
  4. relational databases
  5. type-level programming

Qualifiers

  • Article

Conference

ICFP06
Sponsor:

Acceptance Rates

Overall Acceptance Rate 57 of 143 submissions, 40%

Upcoming Conference

ICFP '25
ACM SIGPLAN International Conference on Functional Programming
October 12 - 18, 2025
Singapore , Singapore

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)14
  • Downloads (Last 6 weeks)1
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Scoping monadic relational database queriesProceedings of the 12th ACM SIGPLAN International Symposium on Haskell10.1145/3331545.3342598(114-124)Online publication date: 8-Aug-2019
  • (2016)Ambiguity and constrained polymorphismScience of Computer Programming10.1016/j.scico.2016.03.007124:C(1-19)Online publication date: 1-Aug-2016
  • (2013)Just do it while compiling!Proceedings of the ACM SIGPLAN 2013 workshop on Partial evaluation and program manipulation10.1145/2426890.2426908(77-86)Online publication date: 21-Jan-2013
  • (2012)An abstract domain to infer types over zones in spreadsheetsProceedings of the 19th international conference on Static Analysis10.1007/978-3-642-33125-1_9(94-110)Online publication date: 11-Sep-2012
  • (2010)UrACM SIGPLAN Notices10.1145/1809028.180661245:6(122-133)Online publication date: 5-Jun-2010
  • (2010)UrProceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/1806596.1806612(122-133)Online publication date: 5-Jun-2010
  • (2009)Attribute grammars fly first-classACM SIGPLAN Notices10.1145/1631687.159658644:9(245-256)Online publication date: 31-Aug-2009
  • (2009)Attribute grammars fly first-classProceedings of the 14th ACM SIGPLAN international conference on Functional programming10.1145/1596550.1596586(245-256)Online publication date: 31-Aug-2009
  • (2007)A type-level approach to component prototypingInternational workshop on Synthesis and analysis of component connectors: in conjunction with the 6th ESEC/FSE joint meeting10.1145/1294917.1294920(23-36)Online publication date: 3-Sep-2007
  • (2007)Transformation of structure-shy programsProceedings of the 2007 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation10.1145/1244381.1244385(11-20)Online publication date: 15-Jan-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media