Parallel algorithms for solving the satisfaction problem of functional and multivalued data dependencies

摘要

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 M ⩾ N are both O(N), and that of Algorithm (3) or (4) for solving the FD or MVD satisfaction problem under N ⩾ M 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).