Efficient parallel algorithms for functional dependency manipulations

ABSTRACT Given a set of functional dependencies Z and a single dependency cr, we show that the algorithm to test whether Z implies ct is log-space complete in P. The functional dependencies x are represented as a directed hypergraph H, [I]. We first present a parallel algorithm which solves the above implication problem using P processors on a EREW-PRAh4 in 0 (e IP + n.logP ) time and on a CRCW-PRAM in 0 (e/P + of ) time, where e and II are the number of arcs and nodes of the graph HE For graphs Hz with fixed degree and diameter, we show that the closure Hz+ can be computed in NC. We present NC algorithms to obtain a non-redundant and a LR-Minimum cover for the set of functional dependencies Z. All our algorithms on a n-node directed hypergraph with fixed degree and diameter can be implemented to ruxi in 0 (log%) 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 [7] 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 here