Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.13104 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911244904038400 |
|---|---|
| author | Chen, Hubie Schneider, Markus |
| author_facet | Chen, Hubie Schneider, Markus |
| contents | We study the problem of statically optimizing select-project-join-union (SPJU) plans where unary key constraints are allowed. A natural measure of a plan, which we call the output degree and which has been studied previously, is the minimum degree of a polynomial bounding the plan's output relation, as a function of the input database's maximum relation size. This measure is, by definition, invariant under passing from a plan to another plan that is semantically equivalent to the first. In this article, we consider a plan measure which we call the intermediate degree; this measure is defined to be the minimum degree of a polynomial bounding the size of all intermediate relations computed during a plan's execution -- again, as a function of the input database's maximum relation size. We present an algorithm that, given an SPJU plan $p$ and a set $Σ$ of unary keys, computes an SPJU plan $p'$ that is semantically equivalent to $p$ (over databases satisfying $Σ$) and that has the minimum intermediate degree over all such semantically equivalent plans. For the types of plans considered, we thus obtain a complete and effective understanding of intermediate degree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_13104 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Intermediate Relation Size Bounds for Select-Project-Join-Union Query Plans Chen, Hubie Schneider, Markus Databases We study the problem of statically optimizing select-project-join-union (SPJU) plans where unary key constraints are allowed. A natural measure of a plan, which we call the output degree and which has been studied previously, is the minimum degree of a polynomial bounding the plan's output relation, as a function of the input database's maximum relation size. This measure is, by definition, invariant under passing from a plan to another plan that is semantically equivalent to the first. In this article, we consider a plan measure which we call the intermediate degree; this measure is defined to be the minimum degree of a polynomial bounding the size of all intermediate relations computed during a plan's execution -- again, as a function of the input database's maximum relation size. We present an algorithm that, given an SPJU plan $p$ and a set $Σ$ of unary keys, computes an SPJU plan $p'$ that is semantically equivalent to $p$ (over databases satisfying $Σ$) and that has the minimum intermediate degree over all such semantically equivalent plans. For the types of plans considered, we thus obtain a complete and effective understanding of intermediate degree. |
| title | Intermediate Relation Size Bounds for Select-Project-Join-Union Query Plans |
| topic | Databases |
| url | https://arxiv.org/abs/2412.13104 |