Polymorphic type inference for the named nested relational calculus

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Polymorphic type inference for the named nested relational calculus

Full text

Pdf (239 KB)

Source

ACM Transactions on Computational Logic (TOCL) archive
Volume 9 , Issue 1 (December 2007) table of contents

Article No. 3

Year of Publication: 2007

ISSN:1529-3785

Authors

Jan Van den Bussche	Hasselt University and Transnational University of Limburg, Diepenbeck, Belgium
Stijn Vansummeren	Hasselt University and Transnational University of Limburg, Diepenbeck, Belgium

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 77, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1297658.1297661 What is a DOI?

ABSTRACT

The named nested relational calculus is the canonical query language for the complex object database model and is equipped with a natural static type system. Given an expression in the language, without type declarations for the input variables, there is the problem of whether there are any input type declarations under which the expression is well-typed. Moreover, if there are, then which are they, and what is the corresponding output type for each of these? This problem is solved by a logic-based approach, and the decision problem is shown to be NP-complete.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	2	Suad Alagíc, Type-checking OQL queries in the ODMG type systems, ACM Transactions on Database Systems (TODS), v.24 n.3, p.319-360, Sept. 1999 [doi>10.1145/328939.328943]
	3	Baader, F. and Snyder, W. 2001. Unification theory. In Handbook of Automated Reasoning. Elsevier and MIT Press, 445--532.
	4	Herman Balsters , Rolf A. de By , Roberto Zicari, Typed Sets as a Basis for Object-Oriented Database Schemas, Proceedings of the 7th European Conference on Object-Oriented Programming, p.161-184, July 26-30, 1993
	5	Catriel Beeri , Tova Milo, Subtyping in OODBs, Journal of Computer and System Sciences, v.51 n.2, p.223-243, Oct. 1995 [doi>10.1006/jcss.1995.1063 ]
	6	Val Tannen , Peter Buneman , Limsoon Wong, Naturally Embedded Query Languages, Proceedings of the 4th International Conference on Database Theory, p.140-154, October 14-16, 1992
	7	Peter Buneman , Susan Davidson , Gerd Hillebrand , Dan Suciu, A query language and optimization techniques for unstructured data, ACM SIGMOD Record, v.25 n.2, p.505-516, June 1996
	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	Cynthia Dwork , Paris C. Kanellakis , John C. Mitchell, On the sequential nature of unification, Journal of Logic Programming, v.1 n.1, p.35-50, June 1984 [doi>10.1016/0743-1066(84)90022-0 ]
	12	Enderton, H. B. 2001. A Mathematical Introduction to Logic. Academic Press. 2nd Ed.
	13	Mary F. Fernandez , Jérôme Siméon , Philip Wadler, A Semi-monad for Semi-structured Data, Proceedings of the 8th International Conference on Database Theory, p.263-300, January 04-06, 2001
	14	Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey Ullman , Vasilis Vassalos , Jennifer Widom, The TSIMMIS Approach to Mediation: Data Models and Languages, Journal of Intelligent Information Systems, v.8 n.2, p.117-132, March/April 1997 [doi>10.1023/A:1008683107812 ]
	15	Jones, S. P. 2003. Haskell 98 Language and Libraries. Cambridge University Press.
	16	Kanellakis, P. C., Mairson, H. G., and Mitchell, J. C. 1991. Unification and ML-type reconstruction. In Computational Logic---Essays in Honor of Alan Robinson. MIT Press, 444--478.
	17	Harry G. Mairson, Deciding ML typability is complete for deterministic exponential time, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.382-401, December 1989, San Francisco, California, United States [doi>10.1145/96709.96748]
	18	Alberto Martelli , Ugo Montanari, An Efficient Unification Algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.258-282, April 1982 [doi>10.1145/357162.357169]
	19	McAllester, D. A. 2003. Joint RTA-TLCA invited talk: A logical algorithm for ML type inference. In Proceedings of the Rewriting Techniques and Applications, 14th International Conference (RTA'03). Lecture Notes in Computer Science, vol. 2706. Springer, 436--451.
	20	Jim Melton, Understanding SQL's stored procedures: a complete guide to SQL/PSM, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
	21	John C. Mitchell, Foundations of programming languages, MIT Press, Cambridge, MA, 1996
	22	Martin Odersky , Martin Sulzmann , Martin Wehr, Type inference with constrained types, Theory and Practice of Object Systems, v.5 n.1, p.35-55, Jan. 1999 [doi>10.1002/(SICI)1096-9942(199901/03)5:1<35::AID-TAPO4>3.0.CO;2-4 ]
	23	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]
	24	Paterson, M. S. and Wegman., M. N. 1978. Linear unification. J. Comput. Syst. Sci. 16, 158--167.
	25	Benjamin C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, 2002
	26	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
	27	Martin Franz Sulzmann , Paul Hudak, A general framework for hindley/milner type systems with constraints, Yale University, New Haven, CT, 2000
	28	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
	29	Jeffrey D. Ullman, Elements of ML programming (ML97 ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
	30	Van den Bussche, J., Van Gucht, D., and Vansummeren, S. 2005. Well-definedness and semantic type-checking in the nested relational calculus and XQuery (extended abstract). In Proceedings of the International Conference on Database Theory (ICDT'05). Lecture Notes in Computer Science, vol. 3363. Springer, 99--113.
	31	Van den Bussche, J. and Waller, E. 2002. Polymorphic type inference for the relational algebra. J. Comput. Syst. Sci. 64, 694--718.
	32	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]
	33	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]
	34	Limsoon Wong , Peter Buneman, Querying nested collections, University of Pennsylvania, Philadelphia, PA, 1994