Smallest Synthetic Witnesses for Conjunctive Queries

Summary: Defines synthetic witnesses D for a self-join-free CQ Q and S; ESW in P, SSW in P when Q is head-dominant. Dichotomy: SSW poly-time for head-dominant Berge-acyclic Q; NP-hard without head-domination and for some cyclic queries; applications to test-data generation and compression. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1984
Venue: PODS
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,359 | 27.94%
DOI: 10.1145/3725250

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
31	Provenance Semirings	2007	PODS	0.0007857786
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018608845
888	QAGen: Generating Query-Aware Test Databases	2007	SIGMOD	0.00015578618
1,106	Provenance for Aggregate Queries	2011	PODS	0.0001398766
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
2,562	Explaining Missing Answers to SPJUA Queries	2010	VLDB	8.5386194e-05
4,260	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.3124474e-05
4,361	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.2559141e-05
4,432	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1938383e-05
4,937	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	5.8187108e-05
4,971	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	5.7938195e-05
5,733	Explaining Wrong Queries Using Small Examples	2019	SIGMOD	5.3483446e-05
6,740	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.944395e-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,076	Mining Approximate Acyclic Schemes from Relations	2020	SIGMOD	4.8426354e-05
8,508	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	4.4952414e-05
8,721	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	4.4608778e-05
9,486	Quantifying the Loss of Acyclic Join Dependencies	2023	PODS	4.3341665e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2721228e-05
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
7,069	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8438319e-05
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
8,508	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	4.4952414e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
6,728	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9483326e-05
8,721	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	4.4608778e-05
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
9,259	Materializing Views with Minimal Size To Answer Queries	2003	PODS	4.3690661e-05