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.