Circuit Bounds for Conjunctive Queries with Self-joins

Summary: Circuit size bounds for CQs under semiring semantics; extends Boolean self-join-free k-clique lower bounds. Relates self-join CQ complexity to self-join-free cases via semiring-specific correspondences and introduces endomorphism-based analysis. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1963
Venue: PODS
Year: 2025
Pagerank: 4.1905499e-05
Overall Rank: 10,355 | 28.04%
DOI: 10.1145/3725229

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 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
31	Provenance Semirings	2007	PODS	0.00078516827
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
1,255	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00013011216
1,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
3,374	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1631303e-05
4,401	On Preservation under Homomorphisms and Unions of Conjunctive Queries	2004	PODS	6.2096576e-05
4,940	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	5.8131196e-05
6,114	A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join	2024	PODS	5.1998701e-05
6,272	Classification of Annotation Semirings over Query Containment	2012	PODS	5.1271971e-05
6,732	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9435849e-05
7,017	Query Evaluation by Circuits	2022	PODS	4.8556471e-05
8,506	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	4.4909322e-05
9,339	Local Transformations and Conjunctive-Query Equivalence	2012	PODS	4.351469e-05
10,903	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1905499e-05
10,909	Tight Bounds of Circuits for Sum-Product Queries	2024	PODS	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,752	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	5.3393414e-05
12,039	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1905499e-05
5,647	Circuit Treewidth, Sentential Decision, and Query Compilation	2017	PODS	5.3913624e-05
10,369	Rewriting Consistent Answers on Annotated Data	2025	PODS	4.1905499e-05
3,374	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1631303e-05
11,160	Extremal Fitting Problems for Conjunctive Queries	2023	PODS	4.1905499e-05
6,732	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9435849e-05
10,902	Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization	2024	PODS	4.1905499e-05
7,017	Query Evaluation by Circuits	2022	PODS	4.8556471e-05
10,909	Tight Bounds of Circuits for Sum-Product Queries	2024	PODS	4.1905499e-05