Given a set of functional dependencies Σ and a single dependency σ, it is shown that the algorithm to test whether Σ implies σ is log-space complete in P. The functional dependencies Σ are represented as a directed hypergraph HΣ. A parallel algorithm is presented which solves the above implication problem using P processors on an exclusive-read, exclusive-write parallel random access machine (EREW-PRAM) in O(e/P + n log P) time and on a concurrent-read, concurrent-write PRAM (CRCW-PRAM) in O(e/P + n) time, where e and n are the number of arcs and nodes of the graph HΣ. For graphs HΣ with fixed degree and diameter, it is shown that the closure HΣ+ can be computed in NC. NC algorithms are presented to obtain a nonredundant and a LR-minimum cover for the set of functional dependencies Σ. All the algorithms on an n-node directed hypergraph with fixed degree and diameter can be implemented to run in O(log2 n) time with M(n) processors on a CREW-PRAM model, where M(n) is the cost of multiplying two binary matrices. The algorithms are efficient based on the transitive closure bottleneck phenomenon - that is, any improvement in the time and processor complexity of the transitive closure algorithm will result in an improvement by the same amount for the algorithms presented.
