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!
|
Table of 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.