Algorithms for Generating an Armstrong Relation and Inferring Functional Dependencies in the Relational Datamodel

AbstractThe main purpose of this paper is to give some new combinatorial algorithms for generating an Armstrong relation from a given relation scheme S and inferring functional dependencies (FDs) which hold in a relation R. We estimate the time complexities of them. It is known that worst-case time complexities of generating an Armstrong relation and inferring the FDs are exponential. However, we show that our algorithms are effective in many cases, i.e., in these cases, they require polynomial time in the size of S (in a case generating an Armstrong relation), in the size of R (in a case inferring the FDs). For BCNF class of relations and relation schemes we also present two effective algorithms constructing an Armstrong relation and finding a set of FDs. We give a class of relations and relation schemes for which generating an Armstrong relation and inferring the FDs are solved in polynomial time. In this paper, we prove that if relations and relation schemes satisfy certain additional properties then the FD-relation equivalence problem is solved in polynomial time. The keys play important roles in logical and structural investigations for FD in the relational datamodel. This paper gives some results concerning keys of relation and relation scheme