Covers of query results
We introduce succinct lossless representations of query results called covers that are subsets of these results, yet allow for constant-delay enumeration of all result tuples. We first study covers whose structures are given by hypertree decompositions of join queries. For any join query, we give a...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl
2018
|
| _version_ | 1797054069417705472 |
|---|---|
| author | Kara, A Olteanu, D |
| author_facet | Kara, A Olteanu, D |
| author_sort | Kara, A |
| collection | OXFORD |
| description | We introduce succinct lossless representations of query results called covers that are subsets of these results, yet allow for constant-delay enumeration of all result tuples. We first study covers whose structures are given by hypertree decompositions of join queries. For any join query, we give asymptotically tight size bounds for the covers of the query results and show that such covers can be computed in worst-case optimal time (up to a logarithmic factor in the database size). For acyclic join queries, we can compute covers compositionally from covers for subqueries using plans with a new operator called cover-join. We then generalise covers from join queries to functional aggregate queries, which express a host of computational problems, e.g., evaluation of queries with joins and aggregates, in-database optimization, matrix chain multiplication, and inference in probabilistic graphical models. |
| first_indexed | 2024-03-06T18:52:23Z |
| format | Conference item |
| id | oxford-uuid:10af9a13-bdfc-40fa-85af-93b84e4dc736 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:52:23Z |
| publishDate | 2018 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:10af9a13-bdfc-40fa-85af-93b84e4dc7362022-03-26T09:57:43ZCovers of query resultsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:10af9a13-bdfc-40fa-85af-93b84e4dc736Symplectic Elements at OxfordSchloss Dagstuhl2018Kara, AOlteanu, DWe introduce succinct lossless representations of query results called covers that are subsets of these results, yet allow for constant-delay enumeration of all result tuples. We first study covers whose structures are given by hypertree decompositions of join queries. For any join query, we give asymptotically tight size bounds for the covers of the query results and show that such covers can be computed in worst-case optimal time (up to a logarithmic factor in the database size). For acyclic join queries, we can compute covers compositionally from covers for subqueries using plans with a new operator called cover-join. We then generalise covers from join queries to functional aggregate queries, which express a host of computational problems, e.g., evaluation of queries with joins and aggregates, in-database optimization, matrix chain multiplication, and inference in probabilistic graphical models. |
| spellingShingle | Kara, A Olteanu, D Covers of query results |
| title | Covers of query results |
| title_full | Covers of query results |
| title_fullStr | Covers of query results |
| title_full_unstemmed | Covers of query results |
| title_short | Covers of query results |
| title_sort | covers of query results |
| work_keys_str_mv | AT karaa coversofqueryresults AT olteanud coversofqueryresults |