Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis
Summary: Initiates a fine-grained enumeration complexity study of conjunctive queries with self-joins, extending dichotomies for linear delay and constant delay after linear preprocessing and identifying new tractable cases that arise only with self-joins. Develops tagging-based hardness proofs, provides sufficient and necessary tractability conditions, and settles low-arity and cyclic-core cases while leaving many instances open. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Nofar Carmeli
- 2. Luc Segoufin
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,707 | Towards Update-Dependent Analysis of Query Maintenance | 2025 | PODS | 4.299267e-05 |
| 10,010 | Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries | 2026 | PODS | 4.1945683e-05 |
| 10,343 | Circuit Bounds for Conjunctive Queries with Self-joins | 2025 | PODS | 4.1945683e-05 |
| 10,905 | Tight Bounds of Circuits for Sum-Product Queries | 2024 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 1 of 1 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,371 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS | 7.1696145e-05 |
Previous
Page 1 / 1
Next