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.00019923978 |
| 1,919 | The Expressiveness of a Family of Finite Set Languages | 1991 | PODS | 9.3781849e-05 |
| 2,515 | Towards Tractable Algebras for Bags (Extended Abstract) | 1993 | PODS | 8.3644485e-05 |
| 3,046 | Tractable Query Languages for Complex Object Databases | 1991 | PODS | 7.7144804e-05 |
| 3,183 | On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions | 1989 | SIGMOD | 7.5578905e-05 |
| 4,559 | A Query Language for List-Based Complex Objects | 1994 | PODS | 6.5344897e-05 |
| 6,798 | Complexity of Nonrecursive Logic Programs with Complex Values | 1998 | PODS | 5.6797989e-05 |
| 8,051 | IDLOG: Extending the Expressive Power of Deductive Database Languages | 1990 | SIGMOD | 5.3992494e-05 |
| 8,935 | Semi-determinism (extended abstract) | 1992 | PODS | 5.2559789e-05 |
| 13,395 | A Non-deterministic Deductive Database Language | 1991 | SIGMOD | 4.9793485e-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.00028930192 |
| 486 | A Calculus for Complex Objects | 1986 | PODS | 0.00017471997 |
| 559 | A New Approach to Database Logic | 1984 | PODS | 0.00016422254 |
| 718 | PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract) | 1988 | PODS | 0.00014530776 |
| 809 | FAD, a Powerful and Simple Database Language | 1987 | VLDB | 0.00013777631 |
| 1,012 | Why Not Negation By Fixpoint? | 1988 | PODS | 0.00012520852 |
| 1,049 | Sets and Negation in a Logic Database Language (LDL1) | 1987 | PODS | 0.0001229888 |
| 1,767 | A Transaction Language Complete for Database Update and Specification | 1987 | PODS | 9.6939822e-05 |
| 2,751 | Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions | 1988 | PODS | 8.0562002e-05 |
| 2,968 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 7.8013847e-05 |
| 3,629 | The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra | 1988 | SIGMOD | 7.1505568e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 13,387 | On the power of Rule-Based Languages with Sets | 1991 | PODS |
| 2 | 7,337 | Typed Query Languages for Databases Containing Queries | 1998 | PODS |
| 3 | 13,330 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB |
| 4 | 1,950 | Relational Expressive Power of Constraint Query Languages | 1996 | PODS |
| 5 | 6,689 | Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract) | 1994 | PODS |
| 6 | 4,426 | Languages for Relational Databases over Interpreted Structures | 1997 | PODS |
| 7 | 3,046 | Tractable Query Languages for Complex Object Databases | 1991 | PODS |
| 8 | 3,183 | On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions | 1989 | SIGMOD |
| 9 | 8,300 | Formal Semantics and Analysis of Object Queries | 2003 | SIGMOD |
| 10 | 2,968 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS |