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)
Incoming Non-self Citations Over Time
Authors
- 1. Neil Immerman
- 2. Sushant Patnaik
- 3. David Stemple
Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,427 | Towards an Effective Calculus for Object Query Languages | 1995 | SIGMOD | 8.8307261e-05 |
| 4,278 | A Query Language for List-Based Complex Objects | 1994 | PODS | 6.285241e-05 |
| 4,378 | Functional and Predicative programming in OODB's | 1992 | PODS | 6.2329359e-05 |
| 4,710 | Verifiable Properties of Database Transactions | 1996 | PODS | 5.9737802e-05 |
| 5,980 | A Query Language for NC | 1994 | PODS | 5.241279e-05 |
| 6,132 | Sequences, Datalog and Transducers | 1995 | PODS | 5.192386e-05 |
| 6,537 | On the Power of Algebras with Recursion | 1993 | SIGMOD | 5.0180143e-05 |
| 6,548 | Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract) | 1994 | PODS | 5.0123519e-05 |
| 7,782 | New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions | 1994 | PODS | 4.6479178e-05 |
| 8,324 | New Data Models and Languages - the Challenge | 1992 | PODS | 4.5392079e-05 |
| 12,837 | Tutorial: Languages for Collection Types | 1994 | PODS | 4.1905499e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 353 | Object Identity As A Query Language Primitive | 1989 | SIGMOD | 0.00026275228 |
| 375 | PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract) | 1988 | PODS | 0.00025262028 |
| 490 | Horn Clauses and the Fixpoint Query Hierarchy | 1982 | PODS | 0.00021979489 |
| 541 | Parallel Evaluation of Recursive Rule Queries | 1986 | PODS | 0.00020586706 |
| 2,323 | Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference | 1989 | SIGMOD | 9.0322199e-05 |
| 2,520 | Untyped Sets, Invention, and Computable Queries | 1989 | PODS | 8.6044305e-05 |
| 2,808 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 8.0939851e-05 |
Previous
Page 1 / 1
Next