Armstrong Relations, Functional Dependencies and Strong Dependencies

Abstract

The main purpose of this paper is to give some results related to Armstrong relations for functional dependency (FD) and strong dependency (SD). In this paper, the dependency inference problem, the FD-relation implication problem and the FD-relation equivalence problem are solved by combinatorial algorithms. We prove that the time complexity of finding a set of antikeys for a given relation scheme S is exponential in the number of attributes. Keys play important roles for the logical and structural investigation of functional dependency in the relational datamodel. We present a computational connection between relations, relation schemes, sets of antikeys and sets of minimal keys. Constructions of relation R, relation scheme S, for which KR = KS, where  KR, KS are the sets of minimal keys R, S of the FD-relation key-implication problem and the FD-relation key-equivalence problem are also presented. We show that the time complexity of finding a relation R of a given relation scheme  S such that KR = KS  is exponential in the size of S. We give a class of relations and relation schemes, for which the above problems are solved in a polynomial time. For a given relation R and a relation scheme S we introduce the following two problems:
1.    Decide whether each key of S is key of R.
2.    Decide whether all keys of R are keys of S.
We show that the first problem is solved in polynomial time, but the second problem is co-NP-complete. In the second part of the paper the concept of strong scheme is introduced. We prove that the membership problem for strong dependencies is solved by an algorithm in polynomial time. We give a necessary and sufficient condition for a relation to be Armstrong relation of a given strong scheme. We present four important problems for logical and structural investigation of strong dependencies: the construction of Armstrong relation of a given strong scheme, the construction of strong scheme SDs of which hold in a given relation, the SD-relation implication problem, the SD-relation equivalence problem.  We prove that above problems are solved by polynomial time algorithm.