KeyFinder: An Efficient Minimal Keys Finding Algorithm For Relational Databases

Abstract

In relational databases, it is essential to know all minimal keys since the concept of database normaliza- tion is based on keys and functional dependencies of a relation schema. Existing algorithms for determining keys or computing the closure of arbitrary sets of attributes are generally time-consuming. In this paper we present an efficient algorithm, called KeyFinder, for solving the key-ï¬nding problem. We also propose a more direct method for computing the closure of a set of attributes. KeyFinder is based on a powerful proof procedure for ï¬nding keys called tableaux. Experimental results show that KeyFinder outperforms its predecessors in terms of search space and execution time.