From spreadsheets to relational databases and back

ABSTRACT

This paper presents techniques and tools to transform spreadsheets into relational databases and back. A set of data refinement rules is introduced to map a tabular datatype into a relational database schema. Having expressed the transformation of the two data models as data refinements, we obtain for free the functions that migrate the data. We use well-known relational database techniques to optimize and query the data. Because data refinements define bi-directional transformations we can map such database back to an optimized spreadsheet. We have implemented the data refinement rules and we constructed Haskell-based tools to manipulate, optimize and refactor Excel-like spreadsheets.

REFERENCES

• 1: Robin Abraham , Martin Erwig, GoalDebug: A Spreadsheet Debugger for End Users, Proceedings of the 29th international conference on Software Engineering, p.251-260, May 20-26, 2007 [doi>10.1109/ICSE.2007.39]
• 2: Robin Abraham , Martin Erwig, UCheck: A spreadsheet type checker for end users, Journal of Visual Languages and Computing, v.18 n.1, p.71-95, February, 2007 [doi>10.1016/j.jvlc.2006.06.001]
• 3: T.L. Alves, P.F. Silva, and J. Visser. Constraint-aware Schema Transformation. In The Ninth International Workshop on Rule-Based Programming, 2008.
• 4: 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]
• 5: Aaron Bohannon , Benjamin C. Pierce , Jeffrey A. Vaughan, Relational lenses: a language for updatable views, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142399]
• 6: 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]
• 7: Thomas M. Connolly , Carolyn Begg, Database Systems: A Practical Approach to Design, Implementation, and Management, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 8: Alcino Cunha , Joost Visser, Strongly Typed Rewriting For Coupled Software Transformation, Electronic Notes in Theoretical Computer Science (ENTCS), v.174 n.1, p.17-34, April, 2007 [doi>10.1016/j.entcs.2006.10.019]
• 9: A. Cunha, J.N. Oliveira, and J. Visser. Type-safe Two-level Data Transformation. In J. Misra et al., editors, Proc. Formal Methods, 14th Int. Symp. Formal Methods Europe, volume 4085 of LNCS, pages 284--299. Springer, 2006.
• 10: C. J. Date. An Introduction to Database Systems. Addison-Wesley, 1995. ISBN 0-201-82458-2.
• 11: FAST. UMinho Haskell Software -- http://haskell.di.uminho.pt/UMHS.
• 12: Marc Fisher , Gregg Rothermel, The EUSES spreadsheet corpus: a shared resource for supporting experimentation with spreadsheet dependability mechanisms, Proceedings of the first workshop on End-user software engineering, p.1-5, May 21-21, 2005, St. Louis, Missouri
• 13: J. Nathan Foster , Michael B. Greenwald , Jonathan T. Moore , Benjamin C. Pierce , Alan Schmitt, Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.3, p.17-es, May 2007 [doi>10.1145/1232420.1232424]
• 14: B.H. Frost and S.D. Stanton. Spreadsheet-based relational database interface, January 2008. URL http://www.freepatentsonline.com/20080016041.html. US Patent 20080016041.
• 15: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 16: Carroll Morgan , P. H. B. Gardiner, Data refinement by calculation, Acta Informatica, v.27 n.6, p.481-503, 1990
• 17: Noel Novelli , Rosine Cicchetti, FUN: An Efficient Algorithm for Mining Functional and Embedded Dependencies, Proceedings of the 8th International Conference on Database Theory, p.189-203, January 04-06, 2001
• 18: J.N. Oliveira. 'Fractal' Types: an Attempt to Generalize Hash Table Calculation. In Workshop on Generic Programming (WGP'98), Marstrand, Sweden, June 1998.
• 19: J.N. Oliveira. A reification calculus for model-oriented software specification. Formal Asp. Comput., 2(1):1--23, 1990.
• 20: José N. Oliveira, Transforming Data by Calculation, Generative and Transformational Techniques in Software Engineering II: International Summer School, GTTSE 2007, Braga, Portugal, July 2-7, 2007. Revised Papers, Springer-Verlag, Berlin, Heidelberg, 2007 [doi>10.1007/978-3-540-88643-3_4]
• 21: J.N. Oliveira. Pointfree foundations for (generic) lossless decomposition. 2007b. Submitted.
• 22: J.N. Oliveira. Functional dependency theory made 'simpler'. Technical Report PURe-05.01.01, DI-Research, January 2005.
• 23: S. Peyton Jones. Haskell 98: Language and libraries. J. Funct. Program., 13(1):1--255, 2003.
• 24: S. Peyton Jones, G. Washburn, and S. Weirich. Wobbly types: type inference for generalised algebraic data types. Technical Report MS-CIS-05-26, Univ. of Pennsylvania, July 2004.
• 25: Christopher Scaffidi , Mary Shaw , Brad Myers, Estimating the Numbers of End Users and End User Programmers, Proceedings of the 2005 IEEE Symposium on Visual Languages and Human-Centric Computing, p.207-214, September 20-24, 2005 [doi>10.1109/VLHCC.2005.34]
• 26: Jeffrey D. Ullman , Jennifer Widom, A first course in database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 27: Joost Visser, Coupled Transformation of Schemas, Documents, Queries, and Constraints, Electronic Notes in Theoretical Computer Science (ENTCS), v.200 n.3, p.3-23, May, 2008 [doi>10.1016/j.entcs.2008.04.090]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming
  D.2 SOFTWARE ENGINEERING
        D.2.12 Interoperability
            Subjects: Data mapping

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models; Normal forms; Schema and subschema

General Terms:
Algorithms, Design, Languages, Theory

Keywords:
bi-directional transformations, functional programming, spreadsheets, type-safe data migration