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: 1377
Venue: PODS
Year: 2006
Pagerank: 6.3799383e-05
Overall Rank: 5,062 | 65.28%
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,498	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.3629798e-05
6,358	On Provenance Minimization	2011	PODS	5.9020113e-05
8,798	GEqO: ML-Accelerated Semantic Equivalence Detection	2023	SIGMOD	5.3698781e-05
8,971	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.3420194e-05
12,492	Equivalence of SQL Queries In Presence of Embedded Dependencies	2009	PODS	5.093636e-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
97	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00034574497
134	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00030343737
309	Optimization of Real Conjunctive Queries	1993	PODS	0.00021768596
633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015560958
869	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013503594
1,269	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.000113935
2,047	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS	9.2564254e-05
2,238	Deciding Equivalences among Aggregate Queries	1998	PODS	8.8882317e-05
2,662	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.2831426e-05
2,883	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	8.0012184e-05
3,884	Inclusion Dependencies and the Universal Instance	1983	PODS	7.0480285e-05

Semantically Similar Papers

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