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: 1967
Venue: PODS
Year: 2024
Pagerank: 5.4049137e-05
Overall Rank: 8,599 | 41.01%
DOI: 10.1145/3651605

Incoming Non-self Citations Over Time

Authors

1. Neha Makhija (Northeastern University)
2. Wolfgang Gatterbauer (Northeastern University)

BibTeX Citation

@inproceedings{makhija_pods24,
        address = {New York, NY, USA},
        series = {{PODS} '24},
        title = {{Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries}},
        url = {https://dl.acm.org/doi/10.1145/3651605},
        doi = {10.1145/3651605},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Makhija, Neha and Gatterbauer, Wolfgang},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,639	Circuit Bounds for Conjunctive Queries with Self-joins	2025	PODS	5.093636e-05
10,652	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	5.093636e-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
17	Provenance Semirings	2007	PODS	0.00059843817
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
620	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00015703409
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
2,503	The Semiring Framework for Database Provenance	2017	PODS	8.4964654e-05
2,914	Reverse Data Management	2011	VLDB	7.9667467e-05
3,991	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.9695922e-05
4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	6.7737212e-05
4,670	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	6.5734205e-05
6,358	On Provenance Minimization	2011	PODS	5.9020113e-05
7,269	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD	5.6595955e-05
8,476	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD	5.4170414e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,225	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB
2	7,558	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS
3	11,121	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS
4	10,174	A Unifying Algorithm for Hierarchical Queries	2026	PODS
5	10,652	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS
6	7,269	A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations	2023	SIGMOD
7	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
8	3,268	Efficient and Provable Multi-Query Optimization	2017	PODS
9	10,154	Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum	2026	PODS
10	8,700	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB