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.1905499e-05
Overall Rank: 10,371 | 27.93%
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.00092569117
31	Provenance Semirings	2007	PODS	0.00078516827
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018593536
882	QAGen: Generating Query-Aware Test Databases	2007	SIGMOD	0.00015634206
1,106	Provenance for Aggregate Queries	2011	PODS	0.00013976386
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
2,565	Explaining Missing Answers to SPJUA Queries	2010	VLDB	8.5307653e-05
4,256	Multi-Tuple Deletion Propagation: Approximations and Complexity	2013	VLDB	6.3063725e-05
4,358	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.2499e-05
4,430	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1879319e-05
4,940	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	5.8131196e-05
4,973	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	5.7882537e-05
5,743	Explaining Wrong Queries Using Small Examples	2019	SIGMOD	5.3432106e-05
6,724	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.9449472e-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,073	Mining Approximate Acyclic Schemes from Relations	2020	SIGMOD	4.8378353e-05
8,506	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	4.4909322e-05
8,718	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	4.4566012e-05
9,488	Quantifying the Loss of Acyclic Join Dependencies	2023	PODS	4.3300131e-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.2680295e-05
7,064	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	4.8391823e-05
770	Answering Conjunctive Queries under Updates	2017	PODS	0.0001686092
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
8,506	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	4.4909322e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
6,732	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9435849e-05
8,718	Aggregated Deletion Propagation for Counting Conjunctive Query Answers	2021	VLDB	4.4566012e-05
2,246	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2039096e-05
9,263	Materializing Views with Minimal Size To Answer Queries	2003	PODS	4.3648789e-05