On the Expressive Power of Database Queries with Intermediate Types

Summary: Defines CALC_k,s to quantify set-height of input/output and intermediate types in the complex-object calculus and studies semantics with arbitrarily many or bounded invented values. Shows invented-value semantics leaves relational calculus unchanged and CALC0,∞=CALC0,1; proves CALC0,s has ≥EXPSPACE complexity, the CALC0,s hierarchy is strict (CALC0,s < CALC0,s+2), and ⋃_s CALC0,s is strictly weaker than the class of computable database queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h843b8b9961105b4b
Venue: PODS
Year: 1988
Pagerank: 7.7976956e-05
Overall Rank: 2,970 | 80.04%
DOI: 10.1145/308386.308409

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_pods88,
        address = {New York, NY, USA},
        series = {{PODS} '88},
        title = {{On the Expressive Power of Database Queries with Intermediate Types}},
        url = {https://dl.acm.org/doi/10.1145/308386.308409},
        doi = {10.1145/308386.308409},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hull, Richard and Su, Jianwen},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,921	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.3737469e-05
2,152	Theory of Database Queries (Extended Abstract)	1988	PODS	8.9497631e-05
2,457	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.4335382e-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
3,630	The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra	1988	SIGMOD	7.1471847e-05
13,346	Database Method Schemas and Object Creation	1993	PODS	4.9769913e-05
13,393	On the power of Rule-Based Languages with Sets	1991	PODS	4.9769913e-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
16	The Functional Data Model and the Data Language DAPLEX	1979	SIGMOD	0.00059968627
140	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.00029333191
426	Relative Information Capacity of Simple Relational Database Schemata	1984	PODS	0.00018477356
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
828	Logic Programming With Sets	1987	PODS	0.00013608891
914	Horn Clauses and the Fixpoint Query Hierarchy	1982	PODS	0.00013109036
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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,952	Relational Expressive Power of Constraint Query Languages	1996	PODS
2	1,921	The Expressiveness of a Family of Finite Set Languages	1991	PODS
3	7,812	Positive Higher-Order Queries	2010	PODS
4	4,428	Languages for Relational Databases over Interpreted Structures	1997	PODS
5	2,457	Untyped Sets, Invention, and Computable Queries	1989	PODS
6	8,307	Formal Semantics and Analysis of Object Queries	2003	SIGMOD
7	3,184	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD
8	13,938	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS
9	3,047	Tractable Query Languages for Complex Object Databases	1991	PODS
10	421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS