Computing the Difference of Conjunctive Queries Efficiently

Summary: Push-down the difference operator via structure-aware rewriting to near-linear time in input+output size for a broad class of conjunctive-query differences. Hardness for remaining cases; heuristics; speedups vs SQL on graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6656
Venue: SIGMOD
Year: 2023
Pagerank: 4.8132423e-05
Overall Rank: 7,162 | 50.18%
DOI: 10.1145/3589298

Incoming Non-self Citations Over Time

Authors

1. Xiao Hu
2. Qichen Wang

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,467	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7218691e-05
8,589	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4897014e-05
10,551	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	4.1945683e-05
10,898	Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization	2024	PODS	4.1945683e-05
10,970	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1945683e-05
11,132	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	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
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
626	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018973823
2,169	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3845975e-05
3,371	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1696145e-05
3,885	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.6674822e-05
5,718	Conjunctive Queries with Comparisons	2022	SIGMOD	5.3552123e-05
6,626	Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation	2021	PODS	4.9889109e-05
6,647	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	4.9772122e-05
7,332	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	4.7606012e-05
8,159	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5729025e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,437	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	4.5138778e-05
6,728	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9483326e-05
8,159	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5729025e-05
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
1,754	Querying Multiple Features of Groups in Relational Databases	1996	VLDB	0.00010670609
14,281	EFFICIENT PROCESSING OF RELATIONAL CALCULUS EXPRESSIONS USING RANGE QUERY THEORY (Extended Abstract)	1984	SIGMOD	-
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
7,824	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	4.6418459e-05
6,090	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD	5.2148332e-05