Tutorial: Languages for Collection Types.

@inproceedings{DBLP:conf/pods/Tannen94,
  author    = {Val Tannen},
  title     = {Tutorial: Languages for Collection Types},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
               Minnesota},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {150-154},
  ee        = {http://doi.acm.org/10.1145/182591.182608, db/conf/pods/pods94-150.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Collection types such as sets, bags (multisets), lists, complex objects, nested relations, arrays, and certain kinds of trees are widely used in non-traditional database applications and must therefore be properly supported by modern database systems. The study of languages for these structures has only recently received serious attention. Can we find languages that naturally support these structures in databases? Practical database languages are based on first-order logic, and much research has been devoted to augmentations of first-order logic to produce languages of increased expressive power, but with the added demands of dealing with collection types, we must ask whether we are stretching this computational paradigm beyond its breaking point.

This tutorial will suggest that we can cope with a rich variety of collection type semantics by looking at the operations that are "naturally" (in the sense of category theory) associated with the data structures involved. Surprisingly, category theory concepts that one might dismiss as too esoteric lead to a succession of useful languages for collection types, that includes equivalents of familiar languages for relational databases, such as relational algebra, nested relational algebra and datalog. As an extra bonus, this approach provides a basis for language syntax that is closely related to that of practical database query languages such as SQL. Moreover, this approach provides equational logics which serve to study certain classes of query optimizations. Finally, there are some intriguing connections between these languages and query complexity classes, both sequential and parallel.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[AB86]

Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations: An Algebra Allowing Data Restructuring. J. Comput. Syst. Sci. 33(3): 361-393(1986) BibTeX

[AB87]

Malcolm P. Atkinson, Peter Buneman: Types and Persistence in Database Programming Languages. ACM Comput. Surv. 19(2): 105-190(1987) BibTeX

[AB88]

Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX

[ABD+90]

Malcolm P. Atkinson, François Bancilhon, David J. DeWitt, Klaus R. Dittrich, David Maier, Stanley B. Zdonik: The Object-Oriented Database System Manifesto. DOOD 1989: 223-240 BibTeX

[ABGG89]

Serge Abiteboul, Catriel Beeri, Marc Gyssens, Dirk Van Gucht: An Introduction to the Completeness of Languages for Complex Objects and Nested Relations. NF² 1987: 117-138 BibTeX

[ACM93]

Serge Abiteboul, Sophie Cluet, Tova Milo: Querying and Updating the File. VLDB 1993: 73-84 BibTeX

[ADG+89]

Antonio Albano, Alan Dearle, Giorgio Ghelli, Chris D. Marlin, Ronald Morrison, Renzo Orsini, David W. Stemple: A Framework for Comparing Type Systems for Database Programming Languages. DBPL 1989: 170-178 BibTeX

[AK89]

Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX

[AL+91]

Malcolm P. Atkinson, Christophe Lécluse, Paul Philbrow, Philippe Richard: Design Issues in a Map Language. DBPL 1991: 20-32 BibTeX

[ART90]

Malcolm P. Atkinson, Philippe Richard, Philip W. Trinder: Bulk Types for Large Scale Programming. East/West Database Workshop 1990: 228-250 BibTeX

[BBKV88]

François Bancilhon, Ted Briggs, Setrag Khoshafian, Patrick Valduriez: FAD, a Powerful and Simple Database Language. VLDB 1987: 97-105 BibTeX

[BBW92]

Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX

[BK93]

Catriel Beeri, Yoram Kornatzky: Algebraic Optimization of Object-Oriented Query Languages. Theor. Comput. Sci. 116(1&2): 59-94(1993) BibTeX

[BTBN91]

Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19 BibTeX

[BTS91]

Val Tannen, Ramesh Subrahmanyam: Logical and Computational Aspects of Programming with Sets/Bags/Lists. ICALP 1991: 60-75 BibTeX

[Bun93]

...

[Col89]

Latha S. Colby: A Recursive Algebra and Query Optimization for Nested Relations. SIGMOD Conference 1989: 273-283 BibTeX

[Col90]

Latha S. Colby: A recursive algebra for nested relations. Inf. Syst. 15(5): 567-582(1990) BibTeX

[CS93]

Surajit Chaudhuri, Kyuseok Shim: Query Optimization in the Presence of Foreign Functions. VLDB 1993: 529-542 BibTeX

[CV93]

Surajit Chaudhuri, Moshe Y. Vardi: Optimization of Real Conjunctive Queries. PODS 1993: 59-70 BibTeX

[Feg94]

Leonidas Fegaras: Efficient Optimization of Iterative Queries. DBPL 1993: 200-225 BibTeX

[FMS93]

Leonidas Fegaras, David Maier, Tim Sheard: Specifying Rule-Based Query Optimizers in a Reflective Framework. DOOD 1993: 146-168 BibTeX

[GM93]

Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58 BibTeX

[GV91]

Stéphane Grumbach, Victor Vianu: Tractable Query Languages for Complex Object Databases. PODS 1991: 315-327 BibTeX

[HK94]

Gerd G. Hillebrand, Paris C. Kanellakis: Functional Database Query Languages as Typed Lambda Calculi of Fixed Order. PODS 1994: 222-231 BibTeX

[HKM93]

Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson: Database Query Languages Embedded in the Typed Lambda Calculus. LICS 1993: 332-343 BibTeX

[HN91]

...

[HS89]

Richard Hull, Jianwen Su: On Bulk Data type Constructors and Manipulation Primitives: A Framework for Analyzing Power and Complexity. DBPL 1989: 396-410 BibTeX

[HS91]

Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. J. Comput. Syst. Sci. 43(1): 219-267(1991) BibTeX

[Hul87]

...

[INV91]

Tomasz Imielinski, Shamim A. Naqvi, Kumar V. Vadaparty: Incomplete Objects - A Data Model for Design and Planning Applications. SIGMOD Conference 1991: 288-297 BibTeX

[IPS91]

Neil Immerman, Sushant Patnaik, David W. Stemple: The Expressiveness of a Family of Finite Set Languages. PODS 1991: 37-52 BibTeX

[JS82]

Gerhard Jaeschke, Hans-Jörg Schek: Remarks on the Algebra of Non First Normal Form Relations. PODS 1982: 124-138 BibTeX

[KV84]

Gabriel M. Kuper, Moshe Y. Vardi: A New Approach to Database Logic. PODS 1984: 86-96 BibTeX

[KV93]

Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model. Theor. Comput. Sci. 116(1&2): 33-57(1993) BibTeX

[LD91]

Daniel F. Lieuwen, David J. DeWitt: Optimizing Loops in Database Programming Languages. DBPL 1991: 287-305 BibTeX

[LD92]

Daniel F. Lieuwen, David J. DeWitt: A Transformation-Based Approach to Optimizing Loops in Database Programming Languages. SIGMOD Conference 1992: 91-100 BibTeX

[LMS+94]

Theodore W. Leung, Gail Mitchell, Bharathi Subramanian, Bennet Vance, Scott L. Vandenberg, Stanley B. Zdonik: The AQUA Data Model and Algebra. DBPL 1993: 157-175 BibTeX

[LW93a]

...

[LW93b]

Leonid Libkin, Limsoon Wong: Semantic Representations and Query Languages for Or-sets. PODS 1993: 37-48 BibTeX

[LW94a]

Leonid Libkin, Limsoon Wong: Aggregate Functions, Conservative Extensions, and Linear Orders. DBPL 1993: 282-294 BibTeX

[LW94b]

Leonid Libkin, Limsoon Wong: Conservativity of Nested Relational Calculi with Internal Generic Functions. Inf. Process. Lett. 49(6): 273-280(1994) BibTeX

[LW94c]

Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114 BibTeX

[MS91]

Florian Matthes, Joachim W. Schmidt: Bulk Types: Built-In or Add-On? DBPL 1991: 33-54 BibTeX

[MV93]

David Maier, Bennet Vance: A Call to Order. PODS 1993: 1-16 BibTeX

[OBB89]

Atsushi Ohori, Peter Buneman, Val Tannen: Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference. SIGMOD Conference 1989: 46-57 BibTeX

[Osb88]

Sylvia L. Osborn: Identity, Equality and Query Optimization. OODBS 1988: 346-351 BibTeX

[PG92]

Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992) BibTeX

[PSV92]

Douglas Stott Parker Jr., Eric Simon, Patrick Valduriez: SVP: A Model Capturing Sets, Lists, Streams, and Parallelism. VLDB 1992: 115-126 BibTeX

[RKS88]

Mark A. Roth, Henry F. Korth, Abraham Silberschatz: Extended Algebra and Calculus for Nested Relational Databases. ACM Trans. Database Syst. 13(4): 389-417(1988) BibTeX

[RZ91]

Steve Rozen, Dennis Shasha: Rationale and Design of BULK. DBPL 1991: 71-85 BibTeX

[SAB+87]

Michel Scholl, Serge Abiteboul, François Bancilhon, Nicole Bidoit, Sophie Gamerman, Didier Plateau, Philippe Richard, Anne Verroust: VERSO: A Database Machine Based On Nested Relations. NF² 1987: 27-49 BibTeX

[Sar92]

...

[SBT94]

Dan Suciu, Val Tannen: A Query Language for NC. PODS 1994: 167-178 BibTeX

[Sch78]

...

[Sch86]

Marc H. Scholl: Theoretical Foundation of Algebraic Optimization Utilizing Unnormalized Relations. ICDT 1986: 380-396 BibTeX

[SP91]

Carol Small, Alexandra Poulovassilis: An Overview of PFL. DBPL 1991: 96-110 BibTeX

[SP94]

Dan Suciu, Jan Paredaens: Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure. PODS 1994: 201-209 BibTeX

[SS86]

Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX

[SS89]

Tim Sheard, David W. Stemple: Automatic Verification of Database Transaction Safety. ACM Trans. Database Syst. 14(3): 322-368(1989) BibTeX

[Suc94]

Dan Suciu: Bounded Fixpoints for Complex Objects. DBPL 1993: 263-281 BibTeX

[TF86]

...

[Tri91]

Philip W. Trinder: Comprehensions, a Query Notation for DBPLs. DBPL 1991: 55-68 BibTeX

[TW88]

...

[TW89]

...

[Wad92]

...

[Won93]

Limsoon Wong: Normal Forms and Conservative Properties for Query Languages over Collection Types. PODS 1993: 26-36 BibTeX

[WT91]

...

Referenced by

1. Michael Benedikt, H. Jerome Keisler: Expressive Power of Unary Counters. ICDT 1997: 291-305
2. Leonid Libkin: Approximation in Databases. ICDT 1995: 411-424