Tutorial: Languages for Collection Types

Summary: Synthesizes category-theoretic operations to derive natural query languages for diverse collection types (sets, bags, lists, nested relations, arrays, trees), recovering relational algebra, nested algebra and datalog. Provides equational logics for optimization and links these languages to sequential and parallel query complexity while aligning with SQL-style syntax. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1025
Venue: PODS
Year: 1994
Pagerank: 5.093636e-05
Overall Rank: 13,022 | 10.66%
DOI: 10.1145/182591.182608

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Val Tannen (University of Pennsylvania)

BibTeX Citation

@inproceedings{tannen_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{Tutorial: Languages for Collection Types}},
        url = {https://dl.acm.org/doi/10.1145/182591.182608},
        doi = {10.1145/182591.182608},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Tannen, Val},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
140	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.00029686538
309	Optimization of Real Conjunctive Queries	1993	PODS	0.00021768596
355	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00020351749
544	A New Approach to Database Logic	1984	PODS	0.00016792556
677	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00015065909
782	FAD, a Powerful and Simple Database Language	1987	VLDB	0.00014080876
1,001	Querying and Updating the File	1993	VLDB	0.00012714843
1,690	Incomplete Objects - A Data Model for Design and Planning Applications	1991	SIGMOD	0.00010001011
1,864	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.5928463e-05
1,909	A Call to Order	1993	PODS	9.4991504e-05
2,130	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	9.1244275e-05
2,198	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD	8.9680897e-05
2,248	Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference	1989	SIGMOD	8.8703718e-05
2,461	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.550394e-05
2,505	A Transformation-Based Approach to Optimizing Loops in Database Programming Languages	1992	SIGMOD	8.4960641e-05
2,986	Tractable Query Languages for Complex Object Databases	1991	PODS	7.8912631e-05
3,299	SVP - a Model Capturing Sets, Streams, and Parallelism	1992	VLDB	7.5418401e-05
4,522	Semantic Representations and Query Languages for Or-sets	1993	PODS	6.6466406e-05
6,563	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS	5.8384765e-05
7,086	A Query Language for NC	1994	PODS	5.7073076e-05
7,339	Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure	1994	PODS	5.6393827e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,467	A Query Language for List-Based Complex Objects	1994	PODS
2	6,184	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS
3	6,563	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS
4	8,971	Equivalence of Nested Queries with Mixed Semantics	2009	PODS
5	1,864	The Expressiveness of a Family of Finite Set Languages	1991	PODS
6	2,897	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS
7	2,986	Tractable Query Languages for Complex Object Databases	1991	PODS
8	13,040	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
9	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS
10	7,849	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS