Factorisations of Query Results: Size Bounds and Readability
Jakub Zavodny
Info
|
Date |
22nd November 2011 (week 7, Michaelmas Term 2011) |
|
Time |
11:30 |
|
Place |
147 |
Abstract
We introduce a representation system for relational data based on algebraic factorisation using distributivity of product
over union and commutativity of product and union.
We give two characterisations of conjunctive queries based on
factorisations of their results defined by a certain class of hyperpath decompositions of the query hypergraph.
The
first characterisation concerns sizes of factorised representations. For any query, we derive a size bound that is asymptotically
tight within our class of factorisations.
For relations, where tuples are annotated with identifiers, we also characterise
the queries by the readability of their results, which is the minimum over all equivalent factorisations of the maximum number
of occurrences of any identifier in that factorisation. We give a dichotomy of queries based on the readability of their results
for any database and define syntactically the class of queries with bounded readability.
This is joint work with Dan Olteanu and will appear in the Int Conf on Database Theory (ICDT) 2012.
Further info
|
Related series |
|
