The Space-Time Complexity of Sum-Product Queries
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912607543230464 |
|---|---|
| author | Deeds, Kyle Merkl, Timo Camillo Pichler, Reinhard Suciu, Dan |
| author_facet | Deeds, Kyle Merkl, Timo Camillo Pichler, Reinhard Suciu, Dan |
| contents | While extensive research on query evaluation has achieved consistent improvements in the time complexity of algorithms, the space complexity of query evaluation has been largely ignored. This is a particular challenge in settings with strict pre-defined space constraints. In this paper, we examine the combined space-time complexity of conjunctive queries (CQs) and, more generally, of sum-product queries (SPQs). We propose several classes of space-efficient algorithms for evaluating SPQs, and we show that the optimal time complexity is almost always achievable with asymptotically lower space complexity than traditional approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_11920 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Space-Time Complexity of Sum-Product Queries Deeds, Kyle Merkl, Timo Camillo Pichler, Reinhard Suciu, Dan Databases While extensive research on query evaluation has achieved consistent improvements in the time complexity of algorithms, the space complexity of query evaluation has been largely ignored. This is a particular challenge in settings with strict pre-defined space constraints. In this paper, we examine the combined space-time complexity of conjunctive queries (CQs) and, more generally, of sum-product queries (SPQs). We propose several classes of space-efficient algorithms for evaluating SPQs, and we show that the optimal time complexity is almost always achievable with asymptotically lower space complexity than traditional approaches. |
| title | The Space-Time Complexity of Sum-Product Queries |
| topic | Databases |
| url | https://arxiv.org/abs/2509.11920 |