Strong types for relational databases

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: Catriel Beeri , Ronald Fagin , John H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509414]
• 3: Björn Bringert , Anders Höckersten , Conny Andersson , Martin Andersson , Mary Bergman , Victor Blomqvist , Torbjörn Martin, Student paper: HaskellDB improved, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, p.108-115, September 22-22, 2004, Snowbird, Utah, USA [doi>10.1145/1017472.1017473]
• 4: Peter Buneman , Atsushi Ohori, Polymorphism and type inference in database programming, ACM Transactions on Database Systems (TODS), v.21 n.1, p.30-76, March 1996 [doi>10.1145/227604.227609]
• 5: Paulo Carreira , Helena Galhardas, Efficient development of data migration transformations, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007692]
• 6: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 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 (7th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 9: Ramez Elmasri , Shamkant B. Navathe, Fundamentals of database systems (2nd ed.), Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 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: Ralf Hinze, Formatting: a class act, Journal of Functional Programming, v.13 n.5, p.935-944, September 2003 [doi>10.1017/S0956796802004367]
• 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: Oleg Kiselyov , Ralf Lämmel , Keean Schupke, Strongly typed heterogeneous collections, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA [doi>10.1145/1017472.1017488]
• 15: Oleg Kiselyov , Chung-chieh Shan, Functional pearl: implicit configurations--or, type classes reflect the values of types, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA [doi>10.1145/1017472.1017481]
• 16: Daan Leijen , Erik Meijer, Domain specific embedded compilers, ACM SIGPLAN Notices, v.35 n.1, p.109-122, Jan. 2000
• 17: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 18: Conor McBride, Faking it Simulating dependent types in Haskell, Journal of Functional Programming, v.12 n.5, p.375-392, July 2002 [doi>10.1017/S0956796802004355]
• 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: Atsushi Ohori , Peter Buneman, Type inference in a database programming language, Proceedings of the 1988 ACM conference on LISP and functional programming, p.174-183, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62700]
• 22: Atsushi Ohori , Peter Buneman , Val Breazu-Tannen, Database programming in Machiavelli—a polymorphic language with static type inference, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.46-57, June 1989, Portland, Oregon, United States
• 23: S. L. Peyton Jones. Haskell 98: Language and libraries. J. Funct. Program., 13(1):1--255, 2003.
• 24: Peter J. Stuckey , Martin Sulzmann, A theory of overloading, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1216-1269, November 2005 [doi>10.1145/1108970.1108974]
• 25: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Records

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms; Schema and subschema; Data models
      H.2.3 Languages
          Subjects: Query languages; Data manipulation languages (DML)

General Terms:
Algorithms, Design, Languages, Theory

Keywords:
Haskell, SQL, functional dependency theory, relational databases, type-level programming