Efficient parallel algorithms for functional dependency manipulations

Abstract

Given a set of functional dependencies Sigma and a single dependency sigma , it is shown that the algorithm to test whether Sigma implies sigma is log-space complete in P. The functional dependencies Sigma are represented as a directed hypergraph H/sub Sigma /. 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/sub Sigma /. For graphs H/sub Sigma / with fixed degree and diameter, it is shown that the closure H/sub Sigma //sup +/ can be computed in NC. NC algorithms are presented to obtain a nonredundant and a LR-minimum cover for the set of functional dependencies Sigma . All the algorithms on an n-node directed hypergraph with fixed degree and diameter can be implemented to run in O(log/sup 2/ 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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>