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.2371772e-05
Overall Rank: 5,187 | 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,570	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.1977783e-05
6,457	On Provenance Minimization	2011	PODS	5.7779266e-05
8,962	GEqO: ML-Accelerated Semantic Equivalence Detection	2023	SIGMOD	5.2493925e-05
9,135	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.2224867e-05
12,782	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	4.9793485e-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.00033914384
136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00029740459
310	Optimization of Real Conjunctive Queries	1993	PODS	0.00021374145
642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015243164
880	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013280642
1,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.00011242154
2,098	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS	9.0521246e-05
2,269	Deciding Equivalences among Aggregate Queries	1998	PODS	8.7196256e-05
2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.1006747e-05
2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8518874e-05
3,968	Inclusion Dependencies and the Universal Instance	1983	PODS	6.8901775e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,266	Query Evaluation using Overlapping Views: Completeness and Efficiency	2006	SIGMOD
2	1,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
3	10,130	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS
4	10,392	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,718	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,135	Equivalence of Nested Queries with Mixed Semantics	2009	PODS
9	2,269	Deciding Equivalences among Aggregate Queries	1998	PODS
10	12,782	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS