Equivalence of Nested Queries with Mixed Semantics

Summary: Deciding equivalence of conjunctive nested queries mixing sets, bags, and normalized bags (arbitrary nesting) is NP-complete, via reduction to an “encoding equivalence” problem by encoding nested objects as flat relations. Introduces a normal form using query-implied multivalued dependencies that characterizes interactions between collection types, unifies prior semantics results, and clarifies nested-aggregation behavior. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h6914ba5d1615940d
Venue: PODS
Year: 2009
Pagerank: 5.2224867e-05
Overall Rank: 9,135 | 38.59%
DOI: 10.1145/1559795.1559828

Incoming Non-self Citations Over Time

Authors

1. David DeHaan (University of Waterloo)

BibTeX Citation

@inproceedings{dehaan_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Equivalence of Nested Queries with Mixed Semantics}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559828},
        doi = {10.1145/1559795.1559828},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {DeHaan, David},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,447	Complete Yet Practical Search for Minimal Query Reformulations Under Constraints	2014	SIGMOD	7.2941472e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037549176
97	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034124569
136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00029740459
202	Aggregate-Query Processing in Data Warehousing Environments	1995	VLDB	0.00025244649
310	Optimization of Real Conjunctive Queries	1993	PODS	0.00021374145
567	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016272161
568	Extending Query Rewriting Techniques for Fine-Grained Access Control	2004	SIGMOD	0.00016262553
642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015243164
1,054	Answering Complex SQL Queries Using Automatic Summary Tables	2000	SIGMOD	0.00012269068
1,119	Query Optimization by Predicate Move-Around	1994	VLDB	0.00011950395
1,521	Constraint Checking with Partial Information	1994	PODS	0.00010379636
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5718481e-05
2,289	Querying Aggregate Data	1999	PODS	8.6891266e-05
2,498	Compiling Mappings to Bridge Applications and Databases	2007	SIGMOD	8.3830999e-05
3,364	Magic Conditions	1990	PODS	7.3731362e-05
5,187	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.2371772e-05
6,319	Containment of Nested XML Queries	2004	VLDB	5.8153622e-05
6,804	Stacked Indexed Views in Microsoft SQL Server	2005	SIGMOD	5.6782614e-05
8,005	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS	5.4085878e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,212	Query Shredding: Efficient Relational Evaluation of Queries over Nested Multisets	2014	SIGMOD
2	2,169	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS
3	1,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
4	13,933	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS
5	2,154	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD
6	2,269	Deciding Equivalences among Aggregate Queries	1998	PODS
7	8,005	New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions	1994	PODS
8	12,782	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS
9	5,187	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS
10	1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS