Normal Forms and Conservative Properties for Query Languages over Collection Types

Summary: Proves strong normalization and normal forms for collection-type query languages: for any input/output nesting heights i,o, definability (without the powerset operator) is independent of intermediate nesting height. Uniform for sets, bags, lists and variant types; generalizes Paredaens–Van Gucht and complements Grumbach–Vianu’s powerset negative results, with implications for query optimization. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 985
Venue: PODS
Year: 1993
Pagerank: 0.00010568101
Overall Rank: 1,783 | 87.60%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Limsoon Wong

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,741	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010714223
1,952	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.9677831e-05
2,426	Towards an Effective Calculus for Object Query Languages	1995	SIGMOD	8.8375297e-05
5,662	Query Unnesting in Object-Oriented Databases	1998	SIGMOD	5.3838456e-05
5,974	A Query Language for NC	1994	PODS	5.246329e-05
6,551	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS	5.0171671e-05
7,146	Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure	1994	PODS	4.8177747e-05
7,782	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	4.6523963e-05
8,034	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB	4.6010599e-05
12,010	An Approach towards the Study of Symmetric Queries	2014	VLDB	4.1945683e-05
12,828	Tutorial: Languages for Collection Types	1994	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
97	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.0005080702
309	The Format Model: A Theory of Database Organization (extended abstract)	1982	PODS	0.00028136165
2,553	Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions	1988	PODS	8.5500139e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,773	Formal Semantics and Analysis of Object Queries	2003	SIGMOD	4.655071e-05
12,828	Tutorial: Languages for Collection Types	1994	PODS	4.1945683e-05
2,800	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	8.1019352e-05
7,248	Positive Higher-Order Queries	2010	PODS	4.7902631e-05
8,454	On the power of Rule-Based Languages with Sets	1991	PODS	4.5082358e-05
1,741	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010714223
13,419	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS	-
8,704	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	4.4647149e-05
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05
7,782	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	4.6523963e-05