Searching for dependencies at multiple abstraction levels Toon Calders, Raymond T. Ng, and Jef Wijsen   View Paper (PDF)   Return to Number 3, September 2002 Abstract 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 center 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 (FD) with roll-ups turns out to capture meaningful rules that are outside the scope of classical FD mining. Performance figures show that RUDs can be discovered in linear time in the number of tuples of the input dataset. DiSC'03 © 2003 Association for Computing Machinery