Covers of query results

Conference item

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.

Authors: Kara, A; Olteanu, D

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl
• Host title: 21st International Conference on Database Theory (ICDT 2018)
• Journal: 21st International Conference on Database Theory
• Volume: 98
• Pages: 16:1--16:22
• Series: Leibniz International Proceedings in Informatics
• Publication date: 2018-02-28
• Acceptance date: 2017-09-11
• Event location: Vienna
• DOI: 10.4230/LIPIcs.ICDT.2018.16
• ISSN: 1868-8969
• ISBN: 9783959770637
• Keywords: query plan; functional aggregate query; factorized database; minimal edge cover; fractional hypertree decomposition