Lower Bounds for Conjunctive Query Evaluation
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908415957139456 |
|---|---|
| author | Mengel, Stefan |
| author_facet | Mengel, Stefan |
| contents | In this tutorial, we will survey known results on the complexity of conjunctive query evaluation in different settings, ranging from Boolean queries over counting to more complex models like enumeration and direct access. A particular focus will be on showing how different relatively recent hypotheses from complexity theory connect to query answering and allow showing that known algorithms in several cases can likely not be improved. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17702 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Conjunctive Query Evaluation Mengel, Stefan Databases Computational Complexity In this tutorial, we will survey known results on the complexity of conjunctive query evaluation in different settings, ranging from Boolean queries over counting to more complex models like enumeration and direct access. A particular focus will be on showing how different relatively recent hypotheses from complexity theory connect to query answering and allow showing that known algorithms in several cases can likely not be improved. |
| title | Lower Bounds for Conjunctive Query Evaluation |
| topic | Databases Computational Complexity |
| url | https://arxiv.org/abs/2506.17702 |