A Unifying Perspective on Succinct Data Representations
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916510299062272 |
|---|---|
| author | Kimelfeld, Benny Martens, Wim Niewerth, Matthias |
| author_facet | Kimelfeld, Benny Martens, Wim Niewerth, Matthias |
| contents | Factorized representations (FRs) are a well-known tool to succinctly represent results of join queries and have been originally defined using the named database perspective. We define FRs in the unnamed database perspective and use them to establish several new connections. First, unnamed FRs can be exponentially more succinct than named FRs, but this difference can be alleviated by imposing a disjointness condition on columns. Conversely, named FRs can also be exponentially more succinct than unnamed FRs. Second, unnamed FRs are the same as (i.e., isomorphic to) context-free grammars for languages in which each word has the same length. This tight connection allows us to transfer a wide range of results on context-free grammars to database factorization; of which we offer a selection in the paper. Third, when we generalize unnamed FRs to arbitrary sets of tuples, they become a generalization of \emph{path multiset representations}, a formalism that was recently introduced to succinctly represent sets of paths in the context of graph database query evaluation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_11663 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Unifying Perspective on Succinct Data Representations Kimelfeld, Benny Martens, Wim Niewerth, Matthias Databases Formal Languages and Automata Theory Factorized representations (FRs) are a well-known tool to succinctly represent results of join queries and have been originally defined using the named database perspective. We define FRs in the unnamed database perspective and use them to establish several new connections. First, unnamed FRs can be exponentially more succinct than named FRs, but this difference can be alleviated by imposing a disjointness condition on columns. Conversely, named FRs can also be exponentially more succinct than unnamed FRs. Second, unnamed FRs are the same as (i.e., isomorphic to) context-free grammars for languages in which each word has the same length. This tight connection allows us to transfer a wide range of results on context-free grammars to database factorization; of which we offer a selection in the paper. Third, when we generalize unnamed FRs to arbitrary sets of tuples, they become a generalization of \emph{path multiset representations}, a formalism that was recently introduced to succinctly represent sets of paths in the context of graph database query evaluation. |
| title | A Unifying Perspective on Succinct Data Representations |
| topic | Databases Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2309.11663 |