The notion of roll-up dependency (RUD) extends functional
dependencies with generalization hierarchies. RUDs can be applied in
OLAP and database design. The problem of discovering RUDs in large
databases is at the centre of this paper. An algorithm is provided
that relies on a number of theoretical results. The algorithm has
been implemented; results on two real-life datasets are given. The
extension of functional dependency with roll-up turns out to capture
meaningful rules that are beyond the scope of classical functional
dependencies. Performance figures show that RUDs can be discovered
in linear time in the number of tuples of the input dataset.