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: 6657
Venue: SIGMOD
Year: 2023
Pagerank: 4.8086254e-05
Overall Rank: 7,161 | 50.24%
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,465	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7186055e-05
8,587	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4853975e-05
10,560	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	4.1905499e-05
10,902	Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization	2024	PODS	4.1905499e-05
10,973	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1905499e-05
11,135	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	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
401	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024281448
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
623	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018976192
2,173	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3767985e-05
3,374	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1631303e-05
3,886	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.6610704e-05
5,728	Conjunctive Queries with Comparisons	2022	SIGMOD	5.350072e-05
6,625	Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation	2021	PODS	4.9841228e-05
6,647	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	4.9729424e-05
7,328	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	4.7560344e-05
8,163	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5685178e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,732	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9435849e-05
8,428	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	4.5095504e-05
8,163	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5685178e-05
912	The Complexity of Evaluating Relational Queries	1983	PODS	0.00015374685
1,754	Querying Multiple Features of Groups in Relational Databases	1996	VLDB	0.00010663123
14,295	EFFICIENT PROCESSING OF RELATIONAL CALCULUS EXPRESSIONS USING RANGE QUERY THEORY (Extended Abstract)	1984	SIGMOD	-
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
770	Answering Conjunctive Queries under Updates	2017	PODS	0.0001686092
7,829	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	4.6373918e-05
6,094	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD	5.2099705e-05