Back to papers
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
- 1493
- Venue
- PODS
- Year
- 2009
- Pagerank
- 4.4604187e-05
- Overall Rank
- 8,699 | 39.55%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
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 |
| 82 |
Answering Queries Using Views (Extended Abstract) |
1995 |
PODS |
0.00054430106 |
| 102 |
Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers |
1987 |
VLDB |
0.00049592627 |
| 142 |
Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) |
1982 |
PODS |
0.00041780711 |
| 218 |
Aggregate-Query Processing in Data Warehousing Environments |
1995 |
VLDB |
0.00033489004 |
| 335 |
Optimization of Real Conjunctive Queries |
1993 |
PODS |
0.00027012705 |
| 582 |
The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) |
1992 |
PODS |
0.00019753367 |
| 583 |
Answering Queries with Aggregation Using Views |
1996 |
VLDB |
0.00019705383 |
| 607 |
Extending Query Rewriting Techniques for Fine-Grained Access Control |
2004 |
SIGMOD |
0.00019248482 |
| 1,059 |
Answering Complex SQL Queries Using Automatic Summary Tables |
2000 |
SIGMOD |
0.00014370009 |
| 1,303 |
Query Optimization by Predicate Move-Around |
1994 |
VLDB |
0.00012692678 |
| 1,579 |
Constraint Checking with Partial Information |
1994 |
PODS |
0.00011273105 |
| 1,959 |
Deciding Containment for Queries with Complex Objects (Extended Abstract) |
1997 |
PODS |
9.958725e-05 |
| 2,252 |
Compiling Mappings to Bridge Applications and Databases |
2007 |
SIGMOD |
9.1887678e-05 |
| 2,475 |
Querying Aggregate Data |
1999 |
PODS |
8.6942707e-05 |
| 3,284 |
Magic Conditions |
1990 |
PODS |
7.2738706e-05 |
| 5,196 |
Equivalence of Queries Combining Set and Bag-Set Semantics |
2006 |
PODS |
5.6311982e-05 |
| 6,293 |
Containment of Nested XML Queries |
2004 |
VLDB |
5.1206121e-05 |
| 6,830 |
Stacked Indexed Views in Microsoft SQL Server |
2005 |
SIGMOD |
4.9081078e-05 |
| 7,782 |
New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions |
1994 |
PODS |
4.6479178e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 3,380 |
Query Shredding: Efficient Relational Evaluation of Queries over Nested Multisets |
2014 |
SIGMOD |
7.1565855e-05 |
| 1,781 |
Normal Forms and Conservative Properties for Query Languages over Collection Types |
1993 |
PODS |
0.00010557953 |
| 1,520 |
The Containment Problem for Real Conjunctive Queries with Inequalities |
2006 |
PODS |
0.00011524911 |
| 13,432 |
A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator |
2013 |
PODS |
- |
| 2,109 |
A Recursive Algebra and Query Optimization for Nested Relations |
1989 |
SIGMOD |
9.5283567e-05 |
| 2,105 |
Deciding Equivalences among Aggregate Queries |
1998 |
PODS |
9.5309231e-05 |
| 7,782 |
New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions |
1994 |
PODS |
4.6479178e-05 |
| 12,305 |
Equivalence of SQL Queries In Presence of Embedded Dependencies |
2009 |
PODS |
4.1905499e-05 |
| 5,196 |
Equivalence of Queries Combining Set and Bag-Set Semantics |
2006 |
PODS |
5.6311982e-05 |
| 1,959 |
Deciding Containment for Queries with Complex Objects (Extended Abstract) |
1997 |
PODS |
9.958725e-05 |