Department of Computer Sciences, University of North Texas, Denton, Texas 76203-3886, U.S.A.
Abstract:
Parallel algorithms for solving the satisfaction problem of non-trivial functional and multivalued data dependencies (FDs and MVDs) in a relation of N tuples by M processors are developed in this paper. Algorithms performing, in a parallel manner, batch or interactive checking of these data dependencies are also discussed. The M processors are organized as a linear systolic array. The time complexities of the first two algorithms for solving the FD satisfaction problem under MN are both O(N), and that of Algorithm (3) or (4) for solving the FD or MVD satisfaction problem under NM is O(N2/M). The latter complexity reduced to O(N) if N = M and is at least not worse than O(N log N) if N = M (N/log N).