Bag Query Containment and Information Theory

Summary: Establishes a tight link between information inequalities and bag-semantic conjunctive-query containment: many-one equivalence between validity of generalized information inequalities and containment when the containing CQ is acyclic. Also isolates a decidable case: an EXPTIME algorithm for containment when the containing CQ is chordal and admits a simple junction tree. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1776
Venue: PODS
Year: 2020
Pagerank: 6.775636e-05
Overall Rank: 3,775 | 73.74%
DOI: 10.1145/3375395.3387645

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,275	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.1319495e-05
6,995	Structure and Complexity of Bag Consistency	2021	PODS	4.8683245e-05
7,022	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	4.8576599e-05
7,344	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS	4.7565607e-05
7,761	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS	4.658708e-05
9,791	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS	4.2818172e-05
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2721228e-05
10,002	Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories	2026	PODS	4.1945683e-05
10,649	STsCache: An Efficient Semantic Caching Scheme for Time-series Data Workloads Based on Hybrid Storage	2025	VLDB	4.1945683e-05
10,905	Tight Bounds of Circuits for Sum-Product Queries	2024	PODS	4.1945683e-05
11,232	Collective Grounding: Applying Database Techniques to Grounding Templated Models	2023	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
335	Optimization of Real Conjunctive Queries	1993	PODS	0.00027036073
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
1,522	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.0001153051
3,307	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.2431594e-05
3,420	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.1154446e-05
6,824	Computing Join Queries with Functional Dependencies	2016	PODS	4.9144789e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
335	Optimization of Real Conjunctive Queries	1993	PODS	0.00027036073
10,001	A Unifying Algorithm for Hierarchical Queries	2026	PODS	4.1945683e-05
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
3,168	Query Containment for Data Integration Systems	2000	PODS	7.4508875e-05
3,307	Attacking Diophantus: Solving a Special Case of Bag Containment	2019	PODS	7.2431594e-05
6,275	Determinacy of Real Conjunctive Queries. The Boolean Case	2022	PODS	5.1319495e-05
10,002	Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories	2026	PODS	4.1945683e-05
9,791	Bag Semantics Conjunctive Query Containment. Four Small Steps Towards Undecidability.	2024	PODS	4.2818172e-05
1,522	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.0001153051