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,426 | Towards an Effective Calculus for Object Query Languages | 1995 | SIGMOD | 8.8375297e-05 |
| 4,285 | A Query Language for List-Based Complex Objects | 1994 | PODS | 6.2913523e-05 |
| 4,381 | Functional and Predicative programming in OODB's | 1992 | PODS | 6.2389434e-05 |
| 4,709 | Verifiable Properties of Database Transactions | 1996 | PODS | 5.9795558e-05 |
| 5,974 | A Query Language for NC | 1994 | PODS | 5.246329e-05 |
| 6,129 | Sequences, Datalog and Transducers | 1995 | PODS | 5.1974539e-05 |
| 6,539 | On the Power of Algebras with Recursion | 1993 | SIGMOD | 5.02287e-05 |
| 6,551 | Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract) | 1994 | PODS | 5.0171671e-05 |
| 7,782 | New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions | 1994 | PODS | 4.6523963e-05 |
| 8,331 | New Data Models and Languages - the Challenge | 1992 | PODS | 4.5435639e-05 |
| 12,828 | Tutorial: Languages for Collection Types | 1994 | PODS | 4.1945683e-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 |
|---|---|---|---|---|
| 352 | Object Identity As A Query Language Primitive | 1989 | SIGMOD | 0.00026299604 |
| 374 | PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract) | 1988 | PODS | 0.00025286717 |
| 490 | Horn Clauses and the Fixpoint Query Hierarchy | 1982 | PODS | 0.00022016773 |
| 537 | Parallel Evaluation of Recursive Rule Queries | 1986 | PODS | 0.0002068591 |
| 2,317 | Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference | 1989 | SIGMOD | 9.0409573e-05 |
| 2,515 | Untyped Sets, Invention, and Computable Queries | 1989 | PODS | 8.6128871e-05 |
| 2,800 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 8.1019352e-05 |
Previous
Page 1 / 1
Next