efficient parallel algorithms for functional dependency manipulations
Given a set of functional dependencies &Sgr; and a single dependency &sgr;, we show that the algorithm to test whether &Sgr; implies &sgr; is log-space complete in P . The functional dependencies &Sgr; are represented as a directed hypergraph H &Sgr; [1]. We first present a parallel algorithm which solves the above implication problem using P processors on a EREW-PRAM in &Ogr; ( e/P + n.logP ) time and on a CRCW-PRAM in &Ogr; ( e/P + n ) time, where e and n are the number of arcs and nodes of the graph H &Sgr; . For graphs H &Sgr; with fixed degree and diameter, we show that the closure H &Sgr; + 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 &Sgr;. All our algorithms on a n -node directed hypergraph with fixed degree and diameter can be implemented to run in &Ogr; (log 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 [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.
parallel algorithm functional dependency nc algorithm processor complexity non-redundant cover log-space reduction directed hyper-graph relational databases minimum cover minimal cover time complexity