Digital Symposium Collection 2000

Type Inference in the Polymorphic Relational Algebra Jan Van den Bussche and Emmanuel Waller   View Paper (PDF)   Return to Semantics Abstract We give a polymorphic account of the relational algebra. We introduce a formalism of "type formulas" specifically tuned for relational algebra expressions, and present an algorithm that computes the "principal" type for a given expression. The principal type ojF an expression is a formula that specifies, in a clear and concise manner, all assignments of types (sets of attributes) tO relation names, under which a given relational algebra expression is well-typed, as well as the output type that expression will have under each of these assignments. Topics discussed include complexity, the relationship with monadic logic, and polymorphic expressive power. References Note: References link to DBLP on the Web. [1] Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman : Compilers: Princiles, Techniques, and Tools. Addison-Wesley 1986, ISBN 0-201-10088-6 [2] Alexander Aiken , Edward L. Wimmers : Type Inclusion Constraints and Type Inference. FPCA 1993 : 31-41 [3] Alexander Aiken , Edward L. Wimmers , T. K. Lakshman : Soft Typing with Conditional Types. POPL 1994 : 163-173 [4] Leo Bachmair , Harald Ganzinger , Uwe Waldmann : Set Constraints are the Monadic Class. LICS 1993 : 75-83 [5] ... [6] Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu : Adding Structure to Unstructured Data. ICDT 1997 : 336-350 [7] Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516 [8] Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman , Vasilis Vassalos , Jennifer Widom : The TSIMMIS Approach to Mediation: Data Models and Languages. JIIS 8(2) : 117-132(1997) [9] Paola Giannini , Furio Honsell , Simona Ronchi Della Rocca : Type Inference: Some Results, Some Problems. Fundamenta Informaticae 19(1/2) : 87-125(1993) [10] ... [11] ... [12] ... [13] ... [14] Peter Buneman , Atsushi Ohori : Polymorphism and Type Inference in Database Programming. TODS 21(1) : 30-76(1996) [15] Atsushi Ohori , Peter Buneman , Val Tannen : Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference. SIGMOD Conference 1989 : 46-57 [16] ... [17] ... [18] David W. Stemple , Leonidas Fegaras , Tim Sheard , Adolfa Socorro : Exceeding the Limits of Polymorphism in Database Programming Languages. EDBT 1990 : 269-285 [19] Jerzy Tiuryn : Type Inference Problems: A Survey. MFCS 1990 : 105-120 [20] ... [21] ... BIBTEX @inproceedings{DBLP:conf/pods/BusscheW99,   author    = {Jan Van den Bussche and                 Emmanuel Waller},    title     = {Type Inference in the Polymorphic Relational Algebra},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {80-90},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM