SQL-based discovery of exact and approximate functional dependencies

Abstract

Students in a typical database course are introduced to theoretical design from a functional dependency standpoint. Functional dependencies are rules of the form X→Y, where X and Y are attributes of a relation r(R). Those rules express the potential one-to-one, and many-to-one relationships among the atributes of R. Unfortunately finding the non-trivial rules X→Y from an existing arbitrary relation is a hard problem. We present an extension of the SQL-based algorithm of Bell and Brockhausen [1] to explore a relation and find its exact and approximate functional dependencies. We use the g3 measure of Kivinen and Mannila to express the degree of approximation of a dependency. This application could be used either as an example or a project in an advanced database course.