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 (University of Southern California)
- 2. Jianwen Su (University of Southern California)
BibTeX Citation
@inproceedings{hull_pods89,
address = {New York, NY, USA},
series = {{PODS} '89},
title = {{Untyped Sets, Invention, and Computable Queries}},
url = {https://dl.acm.org/doi/10.1145/73721.73755},
doi = {10.1145/73721.73755},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Hull, Richard and Su, Jianwen},
year = {1989}
}Incoming Citations (Sorted by Pagerank)
Showing 10 of 10 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 366 | Object Identity As A Query Language Primitive | 1989 | SIGMOD | 0.00019914615 |
| 1,921 | The Expressiveness of a Family of Finite Set Languages | 1991 | PODS | 9.3737469e-05 |
| 2,515 | Towards Tractable Algebras for Bags (Extended Abstract) | 1993 | PODS | 8.3605462e-05 |
| 3,047 | Tractable Query Languages for Complex Object Databases | 1991 | PODS | 7.7108309e-05 |
| 3,184 | On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions | 1989 | SIGMOD | 7.5543186e-05 |
| 4,561 | A Query Language for List-Based Complex Objects | 1994 | PODS | 6.5313973e-05 |
| 6,804 | Complexity of Nonrecursive Logic Programs with Complex Values | 1998 | PODS | 5.6771104e-05 |
| 8,057 | IDLOG: Extending the Expressive Power of Deductive Database Languages | 1990 | SIGMOD | 5.3966955e-05 |
| 8,943 | Semi-determinism (extended abstract) | 1992 | PODS | 5.2534908e-05 |
| 13,401 | A Non-deterministic Deductive Database Language | 1991 | SIGMOD | 4.9769913e-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 |
|---|---|---|---|---|
| 150 | Making Smalltalk a Database System | 1984 | SIGMOD | 0.00028917874 |
| 486 | A Calculus for Complex Objects | 1986 | PODS | 0.00017463801 |
| 559 | A New Approach to Database Logic | 1984 | PODS | 0.00016414522 |
| 719 | PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract) | 1988 | PODS | 0.0001452391 |
| 809 | FAD, a Powerful and Simple Database Language | 1987 | VLDB | 0.00013771533 |
| 1,012 | Why Not Negation By Fixpoint? | 1988 | PODS | 0.00012514931 |
| 1,049 | Sets and Negation in a Logic Database Language (LDL1) | 1987 | PODS | 0.00012293092 |
| 1,768 | A Transaction Language Complete for Database Update and Specification | 1987 | PODS | 9.6894e-05 |
| 2,751 | Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions | 1988 | PODS | 8.0523904e-05 |
| 2,970 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 7.7976956e-05 |
| 3,630 | The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra | 1988 | SIGMOD | 7.1471847e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 13,393 | On the power of Rule-Based Languages with Sets | 1991 | PODS |
| 2 | 7,340 | Typed Query Languages for Databases Containing Queries | 1998 | PODS |
| 3 | 13,336 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB |
| 4 | 1,952 | Relational Expressive Power of Constraint Query Languages | 1996 | PODS |
| 5 | 6,693 | Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract) | 1994 | PODS |
| 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 | 3,184 | On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions | 1989 | SIGMOD |
| 9 | 8,307 | Formal Semantics and Analysis of Object Queries | 2003 | SIGMOD |
| 10 | 2,970 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS |