Efficient parallel algorithms for functional dependency manipulations Conference

Sridhar, R, Iyengar, SS. (1990). Efficient parallel algorithms for functional dependency manipulations . 126-137. 10.1145/319057.319078

cited authors

  • Sridhar, R; Iyengar, SS



  • 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.

publication date

  • January 1, 1990

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 10

International Standard Book Number (ISBN) 13

start page

  • 126

end page

  • 137