Counting Answers to Existential Positive Queries: A Complexity Classification
Summary: Trichotomy for counting answers to bounded-arity existential positive (EP) formulas: every EP query class falls into one of three complexity regimes, subsuming known CQ/UCQ results. Novel equivalence theorem maps each EP class to a CQ class with identical counting complexity. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Hubie Chen
- 2. Stefan Mengel
Incoming Citations (Sorted by Pagerank)
Showing 5 of 5 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,992 | Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations | 2022 | PODS | 4.413099e-05 |
| 10,904 | The Weisfeiler-Leman Dimension of Conjunctive Queries | 2024 | PODS | 4.1945683e-05 |
| 10,919 | Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity | 2024 | PODS | 4.1945683e-05 |
| 11,640 | The Selfish Models Property: Bounding the Complexity of Query Containment and Entailment Problems | 2019 | PODS | 4.1945683e-05 |
| 11,644 | Compiling Existential-Positive Queries to Bounded-Variable Fragments | 2019 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 431 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023370207 |
| 2,063 | Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability | 2014 | PODS | 9.6447857e-05 |
Previous
Page 1 / 1
Next