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: 922
Venue: PODS
Year: 1991
Pagerank: 9.5928463e-05
Overall Rank: 1,864 | 87.22%
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,825	Towards an Effective Calculus for Object Query Languages	1995	SIGMOD	8.0869692e-05
4,422	Functional and Predicative programming in OODB's	1992	PODS	6.7128479e-05
4,467	A Query Language for List-Based Complex Objects	1994	PODS	6.6843364e-05
5,475	Verifiable Properties of Database Transactions	1996	PODS	6.205309e-05
6,563	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS	5.8384765e-05
6,802	Sequences, Datalog and Transducers	1995	PODS	5.7686659e-05
7,086	A Query Language for NC	1994	PODS	5.7073076e-05
7,260	On the Power of Algebras with Recursion	1993	SIGMOD	5.6612789e-05
7,849	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	5.5324391e-05
8,562	New Data Models and Languages - the Challenge	1992	PODS	5.4119882e-05
13,022	Tutorial: Languages for Collection Types	1994	PODS	5.093636e-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
355	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00020351749
616	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015712636
702	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00014855299
888	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS	0.00013402577
2,248	Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference	1989	SIGMOD	8.8703718e-05
2,400	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.6299917e-05
2,897	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.9790527e-05

Semantically Similar Papers

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