Covers of Query Results
From MaRDI portal
Abstract: We introduce succinct lossless representations of query results called covers. They are subsets of the query results that correspond to minimal edge covers in the hypergraphs of these results. We first study covers whose structures are given by fractional hypertree decompositions of join queries. For any decomposition of a query, we give asymptotically tight size bounds for the covers of the query result over that decomposition 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 using query plans with a new operator called cover-join. The tuples in the query result can be enumerated from any of its covers with linearithmic pre-computation time and constant delay. We then generalize covers from joins to functional aggregate queries that express a host of computational problems such as aggregate-join queries, in-database optimization, matrix chain multiplication, and inference in probabilistic graphical models.
Recommendations
Cites work
- Approximating fractional hypertree width
- Combinatorial optimization. Networks and matroids
- Data exchange: getting to the core
- Generalized hypertree decompositions: NP-hardness and tractable variants
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- On Acyclic Conjunctive Queries and Constant Delay Enumeration
- On the Desirability of Acyclic Database Schemes
- Size bounds and query plans for relational joins
- Size bounds for factorised representations of query results
- The core of a graph
Cited in
(5)- Bounds and algorithms for joins via fractional edge covers
- Size bounds for factorised representations of query results
- Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
- Enumeration of minimal hitting sets parameterized by treewidth
- Generalized covers for conjunctive queries
This page was built for publication: Covers of Query Results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3305362)
