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: hb7fbd622a90be189
Venue: PODS
Year: 1994
Pagerank: 4.9793485e-05
Overall Rank: 13,312 | 10.50%
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.00029346895
310	Optimization of Real Conjunctive Queries	1993	PODS	0.00021374145
366	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00019923978
559	A New Approach to Database Logic	1984	PODS	0.00016422254
689	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00014752546
809	FAD, a Powerful and Simple Database Language	1987	VLDB	0.00013777631
1,021	Querying and Updating the File	1993	VLDB	0.0001243944
1,718	Incomplete Objects - A Data Model for Design and Planning Applications	1991	SIGMOD	9.7987023e-05
1,919	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.3781849e-05
1,968	A Call to Order	1993	PODS	9.2967501e-05
2,154	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD	8.9474855e-05
2,169	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	8.9247938e-05
2,302	Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference	1989	SIGMOD	8.6714301e-05
2,515	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.3644485e-05
2,549	A Transformation-Based Approach to Optimizing Loops in Database Programming Languages	1992	SIGMOD	8.3124291e-05
3,046	Tractable Query Languages for Complex Object Databases	1991	PODS	7.7144804e-05
3,363	SVP - a Model Capturing Sets, Streams, and Parallelism	1992	VLDB	7.3742531e-05
4,619	Semantic Representations and Query Languages for Or-sets	1993	PODS	6.4993923e-05
6,689	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS	5.7074984e-05
7,232	A Query Language for NC	1994	PODS	5.579276e-05
7,484	Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure	1994	PODS	5.5128501e-05

Semantically Similar Papers

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