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.4909322e-05
Overall Rank: 8,506 | 40.89%
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,355	Circuit Bounds for Conjunctive Queries with Self-joins	2025	PODS	4.1905499e-05
10,371	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.1905499e-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.00078516827
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018593536
1,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
2,770	The Semiring Framework for Database Provenance	2017	PODS	8.1495762e-05
3,224	Reverse Data Management	2011	VLDB	7.3523336e-05
4,358	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.2499e-05
4,722	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.9646931e-05
4,940	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	5.8131196e-05
6,187	On Provenance Minimization	2011	PODS	5.1611195e-05
7,024	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	4.8530001e-05
8,578	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	4.4879347e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,732	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2137395e-05
6,167	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB	5.1725053e-05
7,064	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8391823e-05
10,000	A Unifying Algorithm for Hierarchical Queries	2026	PODS	4.1905499e-05
10,903	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1905499e-05
10,371	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.1905499e-05
7,024	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	4.8530001e-05
7,603	Polynomial-time program transformations in deductive databases	1990	PODS	4.6959912e-05
3,505	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0304901e-05
8,718	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	4.4566012e-05