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.1945683e-05
Overall Rank: 10,343 | 28.05%
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.0007857786
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
1,259	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00012995821
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
3,371	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1696145e-05
4,405	On Preservation under Homomorphisms and Unions of Conjunctive Queries	2004	PODS	6.2156238e-05
4,937	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	5.8187108e-05
6,112	A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join	2024	PODS	5.2048658e-05
6,274	Classification of Annotation Semirings over Query Containment	2012	PODS	5.1321227e-05
6,728	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9483326e-05
7,017	Query Evaluation by Circuits	2022	PODS	4.8603097e-05
8,508	Minimally Factorizing the Provenance of Self-join Free Conjunctive Queries	2024	PODS	4.4952414e-05
9,334	Local Transformations and Conjunctive-Query Equivalence	2012	PODS	4.3556432e-05
10,899	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	4.1945683e-05
10,905	Tight Bounds of Circuits for Sum-Product Queries	2024	PODS	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,744	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	5.3441438e-05
12,031	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1945683e-05
5,638	Circuit Treewidth, Sentential Decision, and Query Compilation	2017	PODS	5.3965476e-05
10,357	Rewriting Consistent Answers on Annotated Data	2025	PODS	4.1945683e-05
3,371	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1696145e-05
11,157	Extremal Fitting Problems for Conjunctive Queries	2023	PODS	4.1945683e-05
6,728	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9483326e-05
10,898	Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization	2024	PODS	4.1945683e-05
7,017	Query Evaluation by Circuits	2022	PODS	4.8603097e-05
10,905	Tight Bounds of Circuits for Sum-Product Queries	2024	PODS	4.1945683e-05