Posted: 28th August 2014

The FDB project led by Dr Dan Olteanu of the Computer Science Department has been awarded funding from Google to investigate how factorised databases can help reduce the communication cost in distributed database systems, such as the F1 system that supports Google's lucrative AdWords business.

Factorised databases exploit algebraic properties of relational algebra and the structure of queries to achieve lossless compression of relational data. Besides achieving much better compression than generic compression schemes for relations representing query answers, factorised data can be queried directly in the compressed domain.

F1 already factorises its input database to increase data locality for common access patterns and partitions the data across servers into factorisation fragments. The next logical step is to use factorised data for the entire processing pipeline, including temporary results that are frequently repartitioned by the servers.