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)

Paper ID: 879
Venue: PODS
Year: 1989
Pagerank: 8.6128871e-05
Overall Rank: 2,515 | 82.51%
DOI: -

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
352	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00026299604
1,835	The Expressiveness of a Family of Finite Set Languages	1991	PODS	0.00010375854
2,546	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.5701687e-05
3,040	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6707607e-05
3,189	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD	7.4116834e-05
4,285	A Query Language for List-Based Complex Objects	1994	PODS	6.2913523e-05
6,794	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	4.9244886e-05
7,368	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	4.7507411e-05
8,570	Semi-determinism (extended abstract)	1992	PODS	4.4937074e-05
12,910	A Non-deterministic Deductive Database Language	1991	SIGMOD	4.1945683e-05

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
85	Making Smalltalk a Database System	1984	SIGMOD	0.00053428612
374	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00025286717
440	A Calculus for Complex Objects	1986	PODS	0.00023084404
485	A New Approach to Database Logic	1984	PODS	0.00022085103
551	Why Not Negation By Fixpoint?	1988	PODS	0.00020329959
724	FAD, a Powerful and Simple Database Language	1987	VLDB	0.00017536758
912	Sets and Negation in a Logic Database Language (LDL1)	1987	PODS	0.00015414126
1,916	A Transaction Language Complete for Database Update and Specification	1987	PODS	0.00010101977
2,553	Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions	1988	PODS	8.5500139e-05
2,800	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	8.1019352e-05
3,392	The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra	1988	SIGMOD	7.1485699e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,454	On the power of Rule-Based Languages with Sets	1991	PODS	4.5082358e-05
6,664	Typed Query Languages for Databases Containing Queries	1998	PODS	4.9699875e-05
12,847	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB	4.1945683e-05
1,741	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010714223
6,551	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS	5.0171671e-05
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05
3,040	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6707607e-05
3,189	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD	7.4116834e-05
7,773	Formal Semantics and Analysis of Object Queries	2003	SIGMOD	4.655071e-05
2,800	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	8.1019352e-05