A characterization of finite fd-acyclicity

摘要

Database schemes with functional dependencies are considered. A satisfying state of a database scheme consists of relations whose representative instance satisfies the functional dependencies. All states are assumed to be finite. A database scheme is defined to be fd-acyclic if all its pairwise consistent and satisfying states are also join consistent. The fd-acyclic database schemes are characterized, and it is shown that testing fd-acyclicity can be done in polynomial time. An interesting special case is when the relation schemes are closed under the functional dependencies of the database scheme. In this case, a database scheme is fd-acyclic if and only if it is acyclic (i.e., its corresponding hypergraph is acyclic).