  Relational datasets are being generated at an alarmingly rapid rate across
organizations and industries. Compressing these datasets could significantly
reduce storage and archival costs. Traditional compression algorithms, e.g.,
gzip, are suboptimal for compressing relational datasets since they ignore the
table structure and relationships between attributes.
  We study compression algorithms that leverage the relational structure to
compress datasets to a much greater extent. We develop Squish, a system that
uses a combination of Bayesian Networks and Arithmetic Coding to capture
multiple kinds of dependencies among attributes and achieve near-entropy
compression rate. Squish also supports user-defined attributes: users can
instantiate new data types by simply implementing five functions for a new
class interface. We prove the asymptotic optimality of our compression
algorithm and conduct experiments to show the effectiveness of our system:
Squish achieves a reduction of over 50\% in storage size relative to systems
developed in prior work on a variety of real datasets.
