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.4647149e-05
- Overall Rank
- 8,704 | 39.45%
- 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.00054402763 |
| 100 |
Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers |
1987 |
VLDB |
0.00049624696 |
| 144 |
Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) |
1982 |
PODS |
0.00041462501 |
| 218 |
Aggregate-Query Processing in Data Warehousing Environments |
1995 |
VLDB |
0.00033503922 |
| 335 |
Optimization of Real Conjunctive Queries |
1993 |
PODS |
0.00027036073 |
| 581 |
The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) |
1992 |
PODS |
0.00019767772 |
| 584 |
Answering Queries with Aggregation Using Views |
1996 |
VLDB |
0.0001971526 |
| 607 |
Extending Query Rewriting Techniques for Fine-Grained Access Control |
2004 |
SIGMOD |
0.00019266724 |
| 1,059 |
Answering Complex SQL Queries Using Automatic Summary Tables |
2000 |
SIGMOD |
0.00014382575 |
| 1,302 |
Query Optimization by Predicate Move-Around |
1994 |
VLDB |
0.00012705525 |
| 1,578 |
Constraint Checking with Partial Information |
1994 |
PODS |
0.00011284233 |
| 1,952 |
Deciding Containment for Queries with Complex Objects (Extended Abstract) |
1997 |
PODS |
9.9677831e-05 |
| 2,252 |
Compiling Mappings to Bridge Applications and Databases |
2007 |
SIGMOD |
9.1976999e-05 |
| 2,475 |
Querying Aggregate Data |
1999 |
PODS |
8.7017602e-05 |
| 3,283 |
Magic Conditions |
1990 |
PODS |
7.280826e-05 |
| 5,195 |
Equivalence of Queries Combining Set and Bag-Set Semantics |
2006 |
PODS |
5.6366303e-05 |
| 6,294 |
Containment of Nested XML Queries |
2004 |
VLDB |
5.1255418e-05 |
| 6,832 |
Stacked Indexed Views in Microsoft SQL Server |
2005 |
SIGMOD |
4.9128255e-05 |
| 7,782 |
New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions |
1994 |
PODS |
4.6523963e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 3,375 |
Query Shredding: Efficient Relational Evaluation of Queries over Nested Multisets |
2014 |
SIGMOD |
7.1633324e-05 |
| 1,783 |
Normal Forms and Conservative Properties for Query Languages over Collection Types |
1993 |
PODS |
0.00010568101 |
| 1,522 |
The Containment Problem for Real Conjunctive Queries with Inequalities |
2006 |
PODS |
0.0001153051 |
| 13,419 |
A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator |
2013 |
PODS |
- |
| 2,110 |
A Recursive Algebra and Query Optimization for Nested Relations |
1989 |
SIGMOD |
9.5315487e-05 |
| 2,103 |
Deciding Equivalences among Aggregate Queries |
1998 |
PODS |
9.5385023e-05 |
| 7,782 |
New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions |
1994 |
PODS |
4.6523963e-05 |
| 12,297 |
Equivalence of SQL Queries In Presence of Embedded Dependencies |
2009 |
PODS |
4.1945683e-05 |
| 5,195 |
Equivalence of Queries Combining Set and Bag-Set Semantics |
2006 |
PODS |
5.6366303e-05 |
| 1,952 |
Deciding Containment for Queries with Complex Objects (Extended Abstract) |
1997 |
PODS |
9.9677831e-05 |