The Expressiveness of a Family of Finite Set Languages

Summary: Exactly characterizes SRL, a set-based queries+updates language, showing simple syntactic restrictions capture precisely P and LOGSPACE. Investigates ordering, proving Machiavelli's hom operator fails for some order-independent properties and advocating tractable finite-set reasoning. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hd38cd97600103dfd
Venue: PODS
Year: 1991
Pagerank: 9.3737469e-05
Overall Rank: 1,921 | 87.10%
DOI: 10.1145/113413.113417

Incoming Non-self Citations Over Time

Authors

1. Neil Immerman (University of Massachusetts Amherst)
2. Sushant Patnaik (University of Massachusetts Amherst)
3. David Stemple (University of Massachusetts Amherst)

BibTeX Citation

@inproceedings{immerman_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{The Expressiveness of a Family of Finite Set Languages}},
        url = {https://dl.acm.org/doi/10.1145/113413.113417},
        doi = {10.1145/113413.113417},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Immerman, Neil and Patnaik, Sushant and Stemple, David},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,888	Towards an Effective Calculus for Object Query Languages	1995	SIGMOD	7.9039272e-05
4,524	Functional and Predicative programming in OODB's	1992	PODS	6.5591235e-05
4,561	A Query Language for List-Based Complex Objects	1994	PODS	6.5313973e-05
5,603	Verifiable Properties of Database Transactions	1996	PODS	6.0674379e-05
6,693	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS	5.7047967e-05
6,941	Sequences, Datalog and Transducers	1995	PODS	5.6368097e-05
7,234	A Query Language for NC	1994	PODS	5.576635e-05
7,414	On the Power of Algebras with Recursion	1993	SIGMOD	5.5316562e-05
8,010	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	5.4060276e-05
8,737	New Data Models and Languages - the Challenge	1992	PODS	5.2880532e-05
13,318	Tutorial: Languages for Collection Types	1994	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
366	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00019914615
633	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015373336
719	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.0001452391
914	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS	0.00013109036
2,306	Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference	1989	SIGMOD	8.6673254e-05
2,457	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.4335382e-05
2,970	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.7976956e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,341	On the Expressive Power of Logic Programming Languages with Sets	1988	PODS
2	8,010	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS
3	4,293	An Expressive Language for Linear Spatial Database Queries (extended abstract)	1998	PODS
4	1,952	Relational Expressive Power of Constraint Query Languages	1996	PODS
5	13,336	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
6	4,428	Languages for Relational Databases over Interpreted Structures	1997	PODS
7	3,047	Tractable Query Languages for Complex Object Databases	1991	PODS
8	13,153	String Operations in Query Languages	2001	PODS
9	6,693	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS
10	13,393	On the power of Rule-Based Languages with Sets	1991	PODS