Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
Summary: Shows CQs with negation admit linear preprocessing + constant-delay enumeration exactly when they are free‑connex signed‑acyclic, with conditional lower bounds excluding other cases. Extends to FAQ with negation over semirings (adds inverse‑Ackermann preprocessing term) and applies to query difference. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Hangdong Zhao
- 2. Austen Z. Fan
- 3. Xiating Ouyang
- 4. Paraschos Koutris
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 583 | FAQ: Questions Asked Frequently | 2016 | PODS | 0.00019717214 |
| 1,442 | What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? | 2017 | PODS | 0.00011956109 |
| 3,006 | On Functional Aggregate Queries with Additive Inequalities | 2019 | PODS | 7.7299363e-05 |
| 3,371 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS | 7.1696145e-05 |
| 6,626 | Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation | 2021 | PODS | 4.9889109e-05 |
| 7,162 | Computing the Difference of Conjunctive Queries Efficiently | 2023 | SIGMOD | 4.8132423e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,162 | Computing the Difference of Conjunctive Queries Efficiently | 2023 | SIGMOD | 4.8132423e-05 |
| 8,851 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4363908e-05 |
| 8,721 | Aggregated Deletion Propagation for Counting Conjunctive Query Answers | 2021 | VLDB | 4.4608778e-05 |
| 8,966 | Output-sensitive Conjunctive Query Evaluation | 2024 | PODS | 4.4193184e-05 |
| 11,557 | Aggregate Queries on Sparse Databases | 2020 | PODS | 4.1945683e-05 |
| 772 | Answering Conjunctive Queries under Updates | 2017 | PODS | 0.00016876498 |
| 10,009 | The Space-Time Complexity of Sum-Product Queries | 2026 | PODS | 4.1945683e-05 |
| 6,948 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8898337e-05 |
| 3,371 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS | 7.1696145e-05 |
| 13,814 | Equivalences Among Aggregate Queries with Negation | 2001 | PODS | - |