  Acyclic schemes have numerous applications in databases and in machine
learning, such as improved design, more efficient storage, and increased
performance for queries and machine learning algorithms. Multivalued
dependencies (MVDs) are the building blocks of acyclic schemes. The discovery
from data of both MVDs and acyclic schemes is more challenging than other forms
of data dependencies, such as Functional Dependencies, because these
dependencies do not hold on subsets of data, and because they are very
sensitive to noise in the data; for example a single wrong or missing tuple may
invalidate the schema. In this paper we present Maimon, a system for
discovering approximate acyclic schemes and MVDs from data. We give a
principled definition of approximation, by using notions from information
theory, then describe the two components of Maimon: mining for approximate
MVDs, then reconstructing acyclic schemes from approximate MVDs. We conduct an
experimental evaluation of Maimon on 20 real-world datasets, and show that it
can scale up to 1M rows, and up to 30 columns.
