ALGORITHMS FOR GENERATING AN ARMSTRONG RELATION AND INFERRING FUNCTIONAL-DEPENDENCIES IN THE RELATIONAL DATAMODEL

The main purpose of this paper is to give some new combinatorial algor ithms for generating an Armstrong relation from a given relation schem e S and inferring functional dependencies (FDs) which hold in a relati on R. We estimate the time complexities of them. It is known that wors t-case time complexities of generating an Armstrong relation and infer ring the FDs are exponential. However, we show that our algorithms are effective in many cases, i.e., in these cases, they require polynomia l 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 rela tions and relation schemes we also present two effective algorithms co nstructing an Armstrong relation and finding a set of FDs. We give a c lass of relations and relation schemes for which generating an Armstro ng relation and inferring the FDs are solved in polynomial time. In th is paper, we prove that if relations and relation schemes satisfy cert ain additional properties then the FD-relation equivalence problem is solved in polynomial time. The keys play important roles in logical an d structural investigations for FD in the relational datamodel. This p aper gives some results concerning keys of relation and relation schem e.