Parallel algorithms for solving the satisfaction problem of functional and multivalued data dependencies |
| |
Authors: | Chao-Chih Yang Weicong Shen |
| |
Affiliation: | 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 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). |
| |
Keywords: | Complexity Functional dependency Multivalued dependency Parallel processing Relational database Systolic array |
本文献已被 ScienceDirect 等数据库收录! |