Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908358906216448 |
|---|---|
| author | Khamis, Mahmoud Abo Nakos, Vasileios Olteanu, Dan Suciu, Dan |
| author_facet | Khamis, Mahmoud Abo Nakos, Vasileios Olteanu, Dan Suciu, Dan |
| contents | Estimating the cardinality of the output of a query is a fundamental problem in database query processing.
In this article, we overview a recently published contribution that casts the cardinality estimation problem as linear optimization and computes guaranteed upper bounds on the cardinality of the output for any full conjunctive query. The objective of the linear program is to maximize the joint entropy of the query variables and its constraints are the Shannon information inequalities and new information inequalities involving $\ell_p$-norms of the degree sequences of the join attributes.
The bounds based on arbitrary norms can be asymptotically lower than those based on the $\ell_1$ and $\ell_\infty$ norms, which capture the cardinalities and respectively the max-degrees of the input relations. They come with a matching query evaluation algorithm, are computable in exponential time in the query size, and are provably tight when each degree sequence is on one join attribute. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_03290 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation Khamis, Mahmoud Abo Nakos, Vasileios Olteanu, Dan Suciu, Dan Databases Information Theory H.2; E.4 Estimating the cardinality of the output of a query is a fundamental problem in database query processing. In this article, we overview a recently published contribution that casts the cardinality estimation problem as linear optimization and computes guaranteed upper bounds on the cardinality of the output for any full conjunctive query. The objective of the linear program is to maximize the joint entropy of the query variables and its constraints are the Shannon information inequalities and new information inequalities involving $\ell_p$-norms of the degree sequences of the join attributes. The bounds based on arbitrary norms can be asymptotically lower than those based on the $\ell_1$ and $\ell_\infty$ norms, which capture the cardinalities and respectively the max-degrees of the input relations. They come with a matching query evaluation algorithm, are computable in exponential time in the query size, and are provably tight when each degree sequence is on one join attribute. |
| title | Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation |
| topic | Databases Information Theory H.2; E.4 |
| url | https://arxiv.org/abs/2503.03290 |