A crash course on database queries

ABSTRACT

Complex database queries, like programs in general, can "crash", i.e., can raise runtime errors. We want to avoid crashes without losing expressive power, or we want to correctly predict the absence of crashes. We show how concepts and techniques from programming language theory, notably type systems and reflection, can be adaptedto this end. Of course, the specific nature of database queries (asopposed to general programs), also requires some new methods, andraises new questions.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Serge Abiteboul , Rakesh Agrawal , Phil Bernstein , Mike Carey , Stefano Ceri , Bruce Croft , David DeWitt , Mike Franklin , Hector Garcia Molina , Dieter Gawlick , Jim Gray , Laura Haas , Alon Halevy , Joe Hellerstein , Yannis Ioannidis , Martin Kersten , Michael Pazzani , Mike Lesk , David Maier , Jeff Naughton , Hans Schek , Timos Sellis , Avi Silberschatz , Mike Stonebraker , Rick Snodgrass , Jeff Ullman , Gerhard Weikum , Jennifer Widom , Stan Zdonik, The Lowell database research self-assessment, Communications of the ACM, v.48 n.5, p.111-118, May 2005 [doi>10.1145/1060710.1060718]
• 3: Noga Alon , Tova Milo , Frank Neven , Dan Suciu , Victor Vianu, Typechecking XML views of relational databases, ACM Transactions on Computational Logic (TOCL), v.4 n.3, p.315-354, July 2003 [doi>10.1145/772062.772065]
• 4: Noga Alon , Tova Milo , Frank Neven , Dan Suciu , Victor Vianu, XML with data values: typechecking revisited, Journal of Computer and System Sciences, v.66 n.4, p.688-727, 1 June 2003 [doi>10.1016/S0022-0000(03)00032-1]
• 5: Henk P. Barendregt. The Lambda Calculus: its Syntax and Semantics. North-Holland, 1984.
• 6: Scott Boag, Don Chamberlin, Mary F. Fernández, Daniela Florescu, Jonathan Robie, and Jérôme Siméon. XQuery 1.0: An XML Query Language. W3C Working Draft, February 2005.
• 7: Don Box and Anders Hejlsberg. The LINQ Project: .NET Language Integrated Query. http://msdn.microsoft.com/netframework/future/linq/, March 2006.
• 8: Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu, Adding Structure to Unstructured Data, Proceedings of the 6th International Conference on Database Theory, p.336-350, January 08-10, 1997
• 9: Peter Buneman , Shamim Naqvi , Val Tannen , Limsoon Wong, Principles of programming with complex objects and collection types, Theoretical Computer Science, v.149 n.1, p.3-48, Sept. 18, 1995
• 10: 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]
• 11: C. Calcagno , E. Moggi , T. Sheard, Closed types for a safe imperative MetaML, Journal of Functional Programming, v.13 n.3, p.545-571, May 2003 [doi>10.1017/S0956796802004598]
• 12: Luca Cardelli. Type systems. In The Computer Science and Engineering Handbook, pages 2208--2236. CRC Press, 1997.
• 13: R. G. G. Cattell , Douglas K. Barry , Mark Berler , Jeff Eastman , David Jordan , Craig Russell , Olaf Schadow , Torsten Stanienda , Fernando Velez, The object data standard: ODMG 3.0, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 14: Weidong Chen , Michael Kifer , David S. Warren, HILOG: a foundation for higher-order logic programming, Journal of Logic Programming, v.15 n.3, p.187-230, Feb. 1993 [doi>10.1016/0743-1066(93)90039-J]
• 15: Luis Damas , Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-212, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582176]
• 16: Denise Draper, Peter Fankhauser, Mary F. Fernández, Ashok Malhotra, Kristoffer Rose, Michael Rys, Jérôme Siméon, and Philip Wadler. XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Working Draft, February 2005.
• 17: Mary F. Fernández, Ashok Malhotra, Jonathan Marsh, Marton Nagy, and Norman Walsh. XQuery 1.0 and XPath 2.0 Data Model. W3C Working Draft, February 2005.
• 18: Véronique Benzaken , Giuseppe Castagna , Alain Frisch, CDuce: an XML-centric general-purpose language, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.51-63, August 25-29, 2003, Uppsala, Sweden
• 19: Dieter Gawlick , Dmitry Lenkov , Aravind Yalamanchi , Lucy Chernobrod, Applications for Expression Data in Relational Database Systems, Proceedings of the 20th International Conference on Data Engineering, p.609, March 30-April 02, 2004
• 20: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 21: Marc Gyssens , Laks V. S. Lakshmanan, A Foundation for Multi-dimensional Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.106-115, August 25-29, 1997
• 22: Roger Hindley. The principal type-scheme of an object in combinatory logic. Transactions of the American Mathematical Society, 146:29--60, December 1969.
• 23: Haruo Hosoya , Benjamin C. Pierce, XDuce: A statically typed XML processing language, ACM Transactions on Internet Technology (TOIT), v.3 n.2, p.117-148, May 2003 [doi>10.1145/767193.767195]
• 24: Haruo Hosoya , Jérôme Vouillon , Benjamin C. Pierce, Regular expression types for XML, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.1, p.46-90, January 2005 [doi>10.1145/1053468.1053470]
• 25: M. Jain, A. Mendhekar, and D. Van Gucht. A uniform data model for relational data and meta-data query processing. In Advances in Data Management '95, pages 146--165. Tata McGraw-Hill, 1995.
• 26: Christoph Koch, On the complexity of nonrecursive XQuery and functional query languages on complex values, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1215-1256, December 2006 [doi>10.1145/1189769.1189771]
• 27: Laks V. S. Lakshmanan , Fereidoon Sadri , Subbu N. Subramanian, SchemaSQL: An extension to SQL for multidatabase interoperability, ACM Transactions on Database Systems (TODS), v.26 n.4, p.476-519, December 2001 [doi>10.1145/503099.503102]
• 28: Zi Lin, Bingsheng He, and Byron Choi. A quantitative summary of XML structures. In ER 2006 - 25th International Conference on Conceptual Modeling, volume 4215 of Lecture Notes in Computer Science, pages 228--240. Springer, 2006.
• 29: S. Maneth , A. Berlea , T. Perst , H. Seidl, XML type checking with macro tree transducers, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065203]
• 30: Sebastian Maneth, Thomas Perst, and Helmut Seidl. Exact XML type checking in polynomial time. In Schwentick and Suciu {41}, pages 254--268.
• 31: Wim Martens , Frank Neven, Frontiers of tractability for typechecking simple XML transformations, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055563]
• 32: Wim Martens , Frank Neven, On the complexity of typechecking top-down XML transformations, Theoretical Computer Science, v.336 n.1, p.153-180, 25 May 2005 [doi>10.1016/j.tcs.2004.10.035]
• 33: Jim Melton, Understanding SQL's stored procedures: a complete guide to SQL/PSM, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 34: Robin Milner. A theory of type polymorphism in programming. J. Comput. Syst. Sci., 17(3):348--375, 1978.
• 35: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.11-22, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335171]
• 36: Frank Neven , Jan Van den Bussche , Dirk Van Gucht , Gottfried Vossen, Typed query languages for databases containing queries, Information Systems, v.24 n.7, p.569-595, Nov. 1999 [doi>10.1016/S0306-4379(99)00033-2]
• 37: Atsushi Ohori, A polymorphic record calculus and its compilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.6, p.844-895, Nov. 1995 [doi>10.1145/218570.218572]
• 38: Benjamin C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, 2002
• 39: Didier Rémy, Type inference for records in natural extension of ML, Theoretical aspects of object-oriented programming: types, semantics, and language design, MIT Press, Cambridge, MA, 1994
• 40: Kenneth A. Ross, Relations with relation names as arguments: algebra and calculus, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.346-353, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137905]
• 41: Thomas Schwentick , Dan Suciu, Database Theory ICDT 2007: 11th International Conference, Barcelona, Spain, January 10-12, 2007, Proceedings (Lecture Notes in Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, 2007
• 42: H. Schwichtenberg. Definierbare funktionen in λ-kalkül mit typen. Archiv für mathematische Logik und Grundlagenforschung, 174:113--114, 1976.
• 43: Michael Stonebraker , Erika Anderson , Eric Hanson , Brad Rubenstein, QUEL as a data type, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 44: Michael Stonebraker , Jeff Anton , Eric Hanson, Extending a database system with procedures, ACM Transactions on Database Systems (TODS), v.12 n.3, p.350-376, Sept. 1987 [doi>10.1145/27629.27631]
• 45: Dan Suciu, Typechecking for Semistructured Data, Revised Papers from the 8th International Workshop on Database Programming Languages, p.1-20, September 08-10, 2001
• 46: Martin Franz Sulzmann , Paul Hudak, A general framework for hindley/milner type systems with constraints, Yale University, New Haven, CT, 2000
• 47: Martin Sulzmann, A General Type Inference Framework for Hindley/Milner Style Systems, Proceedings of the 5th International Symposium on Functional and Logic Programming, p.248-263, March 07-09, 2001
• 48: Walid Taha , Tim Sheard, MetaML and multi-stage programming with explicit annotations, Theoretical Computer Science, v.248 n.1-2, p.211-242, October 2000 [doi>10.1016/S0304-3975(00)00053-0]
• 49: Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• 50: Henry S. Thompson, David Beech, Murray Maloney, and Noah Mendelsohn. XML Schema Part 1: Structures. W3C Recommendation, May 2001.
• 51: Jan Van den Bussche , Dirk van Gucht , Gottfried Vossen, Reflective programming in the relational algebra, Journal of Computer and System Sciences, v.52 n.3, p.537-549, June 1996 [doi>10.1006/jcss.1996.0040]
• 52: J. Van den Bussche, S. Vansummeren, and G. Vossen. Meta-SQL: Towards practical meta-querying. In Advances in Database Technology--EDBT 2004, volume 2992 of Lecture Notes in Computer Science, pages 823--825. Springer, 2004.
• 53: Jan Van den Bussche , Stijn Vansummeren , Gottfried Vossen, Towards practical meta-querying, Information Systems, v.30 n.4, p.317-332, June 2005 [doi>10.1016/j.is.2004.04.001]
• 54: J. Van den Bussche and E. Waller. Polymorphic type inference for the relational algebra. Journal of Computer and System Sciences, 64:694--718, 2002.
• 55: Jan Van den Bussche , Dirk Van Gucht , Stijn Vansummeren, Well-definedness and semantic type-checking for the nested relational calculus, Theoretical Computer Science, v.371 n.3, p.183-199, March, 2007 [doi>10.1016/j.tcs.2006.11.007]
• 56: Jan Van den Bussche and Stijn Vansummeren. Polymorphic type inference for the named nested relational calculus. ACM Transactions on Computational Logic, To appear.
• 57: Stijn Vansummeren, Deciding well-definedness of XQuery fragments, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065173]
• 58: Stijn Vansummeren. On deciding well-definedness for query languages on trees. Technical report, Hasselt University, 2005.
• 59: Stijn Vansummeren, On the complexity of deciding typability in the relational algebra, Acta Informatica, v.41 n.6, p.367-381, May 2005 [doi>10.1007/s00236-005-0162-6]
• 60: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• 61: Mitchell Wand, Type inference for record concatenation and multiple inheritance, Information and Computation, v.93 n.1, p.1-15, July 1991 [doi>10.1016/0890-5401(91)90050-C]
• 62: Piotr Wieczorek. Complexity of typechecking XML views of relational databases. In Schwentick and Suciu {41}, pages 239--253.
• 63: Limsoon Wong, Kleisli, a functional query system, Journal of Functional Programming, v.10 n.1, p.19-56, January 2000 [doi>10.1017/S0956796899003585]
• 64: Catharine M. Wyss , Edward L. Robertson, Relational languages for metadata integration, ACM Transactions on Database Systems (TODS), v.30 n.2, p.624-660, June 2005 [doi>10.1145/1071610.1071618]
• 65: XML syntax for XQuery 1.0 (XQueryX). W3C Working Draft 19 December 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Specification techniques

General Terms:
Languages, Theory, Verification

Keywords:
XQuery, nested relational calculus, reflection, relational algebra, runtime error, typability, type inference, type system, well-definedness