Equivalence of Queries Combining Set and Bag-Set Semantics

Summary: Defines combined semantics to model SQL queries mixing set and bag-set evaluation (e.g., set-returning subqueries inside multiset contexts and multiset-unions of set queries). Presents the equivalence problem, a general sufficient condition, and exact characterizations for key query classes. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hd766073869945e0e
Venue: PODS
Year: 2006
Pagerank: 6.2342247e-05
Overall Rank: 5,189 | 65.13%
DOI: 10.1145/1142351.1142362

Incoming Non-self Citations Over Time

Authors

1. Sara Cohen (Technion 7 Israel Institute of Technology)

BibTeX Citation

@inproceedings{cohen_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Equivalence of Queries Combining Set and Bag-Set Semantics}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142362},
        doi = {10.1145/1142351.1142362},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cohen, Sara},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,572	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.194371e-05
6,459	On Provenance Minimization	2011	PODS	5.7751941e-05
8,972	GEqO: ML-Accelerated Semantic Equivalence Detection	2023	SIGMOD	5.2469075e-05
9,145	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.2200167e-05
12,788	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	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
102	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00033899077
136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.0002972645
310	Optimization of Real Conjunctive Queries	1993	PODS	0.00021364898
642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015236058
880	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013274554
1,276	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.0001123733
2,099	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS	9.0478598e-05
2,271	Deciding Equivalences among Aggregate Queries	1998	PODS	8.7155798e-05
2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.0968483e-05
2,924	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8481787e-05
3,970	Inclusion Dependencies and the Universal Instance	1983	PODS	6.8869179e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,269	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD
2	1,276	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
3	10,134	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS
4	10,404	Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories	2026	PODS
5	310	Optimization of Real Conjunctive Queries	1993	PODS
6	3,719	A Formal Semantics of SQL Queries, Its Validation, and Applications	2018	VLDB
7	1,680	Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries	2018	VLDB
8	9,145	Equivalence of Nested Queries with Mixed Semantics	2009	PODS
9	2,271	Deciding Equivalences among Aggregate Queries	1998	PODS
10	12,788	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS