Describing candidate keys by hypergraphs

Abstract

In the paper algorithms are given that find a minimal transversal and all minimal transversals, respectively, of a hypergraph. Some other computational problems related to the hypergraphs are also studied. As applications, new characterizations of candidate keys of a relational datamodel are given, and new algorithms that find all candidate keys of a relation and a relation scheme, respectively, are presented.