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
Authors
- 1. Hangdong Zhao (University of Wisconsin)
- 2. Austen Z. Fan (University of Wisconsin)
- 3. Xiating Ouyang (University of Wisconsin)
- 4. Paraschos Koutris (University of Wisconsin)
BibTeX Citation
@inproceedings{zhao_pods24,
address = {New York, NY, USA},
series = {{PODS} '24},
title = {{Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization}},
url = {https://dl.acm.org/doi/10.1145/3651138},
doi = {10.1145/3651138},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Zhao, Hangdong and Fan, Austen Z. and Ouyang, Xiating and Koutris, Paraschos},
year = {2024}
}
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,296 | Succinct Structure Representations for Efficient Query Optimization | 2026 | SIGMOD | 5.093636e-05 |
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 |
|---|---|---|---|---|
| 358 | FAQ: Questions Asked Frequently | 2016 | PODS | 0.00020243592 |
| 1,109 | What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? | 2017 | PODS | 0.00012142685 |
| 2,266 | On Functional Aggregate Queries with Additive Inequalities | 2019 | PODS | 8.8391372e-05 |
| 2,468 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS | 8.5358494e-05 |
| 6,565 | Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation | 2021 | PODS | 5.8382688e-05 |
| 7,161 | Computing the Difference of Conjunctive Queries Efficiently | 2023 | SIGMOD | 5.6852987e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 9,009 | Efficient Approximations of Conjunctive Queries | 2012 | PODS |
| 2 | 8,700 | Aggregated Deletion Propagation for Counting Conjunctive Query Answers | 2021 | VLDB |
| 3 | 6,678 | Output-sensitive Conjunctive Query Evaluation | 2024 | PODS |
| 4 | 8,528 | Aggregate Queries on Sparse Databases | 2020 | PODS |
| 5 | 636 | Answering Conjunctive Queries under Updates | 2017 | PODS |
| 6 | 10,182 | The Space-Time Complexity of Sum-Product Queries | 2026 | PODS |
| 7 | 7,028 | Semantic Acyclicity on Graph Databases | 2013 | PODS |
| 8 | 10,154 | Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum | 2026 | PODS |
| 9 | 2,468 | On the Enumeration Complexity of Unions of Conjunctive Queries | 2019 | PODS |
| 10 | 14,015 | Equivalences Among Aggregate Queries with Negation | 2001 | PODS |