Untyped Sets, Invention, and Computable Queries
Summary: Over untyped sets, set algebra without while is equivalent to the typed complex-object algebra; with while (or COL under stratified/inflationary semantics) it captures exactly the computable queries. Exhibits a calculus beyond computable queries, characterizes it via a typed complex-object calculus with invention, and introduces a "generic Turing machine" technical tool. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Richard Hull
- 2. Jianwen Su
Incoming Citations (Sorted by Pagerank)
Showing 10 of 10 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 353 | Object Identity As A Query Language Primitive | 1989 | SIGMOD | 0.00026275228 |
| 1,833 | The Expressiveness of a Family of Finite Set Languages | 1991 | PODS | 0.00010365844 |
| 2,546 | Towards Tractable Algebras for Bags (Extended Abstract) | 1993 | PODS | 8.5606179e-05 |
| 3,043 | Tractable Query Languages for Complex Object Databases | 1991 | PODS | 7.6632326e-05 |
| 3,195 | On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions | 1989 | SIGMOD | 7.4052272e-05 |
| 4,278 | A Query Language for List-Based Complex Objects | 1994 | PODS | 6.285241e-05 |
| 6,795 | Complexity of Nonrecursive Logic Programs with Complex Values | 1998 | PODS | 4.9197522e-05 |
| 7,363 | IDLOG: Extending the Expressive Power of Deductive Database Languages | 1990 | SIGMOD | 4.7461604e-05 |
| 8,567 | Semi-determinism (extended abstract) | 1992 | PODS | 4.4893996e-05 |
| 12,920 | A Non-deterministic Deductive Database Language | 1991 | SIGMOD | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 11 of 11 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 86 | Making Smalltalk a Database System | 1984 | SIGMOD | 0.0005348843 |
| 375 | PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract) | 1988 | PODS | 0.00025262028 |
| 443 | A Calculus for Complex Objects | 1986 | PODS | 0.00023059917 |
| 485 | A New Approach to Database Logic | 1984 | PODS | 0.00022061287 |
| 552 | Why Not Negation By Fixpoint? | 1988 | PODS | 0.00020309855 |
| 722 | FAD, a Powerful and Simple Database Language | 1987 | VLDB | 0.00017505795 |
| 910 | Sets and Negation in a Logic Database Language (LDL1) | 1987 | PODS | 0.00015398775 |
| 1,920 | A Transaction Language Complete for Database Update and Specification | 1987 | PODS | 0.00010092077 |
| 2,560 | Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions | 1988 | PODS | 8.541561e-05 |
| 2,808 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 8.0939851e-05 |
| 3,392 | The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra | 1988 | SIGMOD | 7.1418515e-05 |
Previous
Page 1 / 1
Next