Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries

Summary: Minimizes provenance factorization size for self-join-free conjunctive queries; NP-complete, but a PTIME class identified. ILP yields exact minimal factorization; MFMC offers fast approximations, linking factorizations to VEOs and minimal query plans. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1935
Venue: PODS
Year: 2024
Pagerank: 4.4952414e-05
Overall Rank: 8,508 | 40.82%
DOI: 10.1145/3651605

Incoming Non-self Citations Over Time

Authors

1. Neha Makhija
2. Wolfgang Gatterbauer

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,343	Circuit Bounds for Conjunctive Queries with Self-joins	2025	PODS	4.1945683e-05
10,359	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
31	Provenance Semirings	2007	PODS	0.0007857786
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018608845
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
2,764	The Semiring Framework for Database Provenance	2017	PODS	8.1574444e-05
3,218	Reverse Data Management	2011	VLDB	7.3592173e-05
4,361	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.2559141e-05
4,720	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.973811e-05
4,937	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	5.8187108e-05
6,186	On Provenance Minimization	2011	PODS	5.166082e-05
7,022	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	4.8576599e-05
8,581	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.492241e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,727	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2216778e-05
6,169	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB	5.1716068e-05
7,069	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8438319e-05
10,001	A Unifying Algorithm for Hierarchical Queries	2026	PODS	4.1945683e-05
10,899	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1945683e-05
10,359	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.1945683e-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,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
3,462	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0703696e-05
8,721	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	4.4608778e-05