Some problems on the functional dependency related to armstrong relations in the relational datamodel.

Abstract

In the paper, we give some results to combinatorial algorithms for functional dependency (FD for short) connecting the construction of Armstrong relations, relation schemes, the FD-relation implication problem, and the FD-relation equivalence problem. These algorithms play important roles in logical and structural investigations of the relational data model. Now, they are know to have exponential complexity. However, in this paper we show that if relations and relations schemes satisfy certain additional properties, then above problems are solved in polynomial time.

Key Words and Phrases: relation, relational datamodel, functional dependency, relation scheme, generating Armstrong relation, dependency inference, FD-relation implication scheme problem, FD-relation equivalence problem, minimal Armstrong relation, closed set, minimal generator, key, minimal key, antikey.