FAST IN-PLACE VERIFICATION OF DATA DEPENDENCIES

Several fast and space-optimal sequential and parallel algorithms for solving the satisfaction problem of functional and multivalued depende ncies (FD's and MVD's) are presented in this paper. We propose two fra meworks to verify an MVD for a relation, and implement them by explori ng the existing fast space-optimal sorting techniques. The space optim ality means that we need only a constant amount of extra memory space for the sequential implementations, and O(M) amount of extra memory sp ace for parallel algorithms that use M processors. This feature makes the algorithms particularly attractive whenever space is a critical re source and I/O transfers should be reduced to the minimal, as is often the case for relational database systems. With N denoting the number of tuples in a relation, we show that the FD and MVD verification can be done in-place in a time of O(N log N) for M = 1, and in a time of O ((N/M+log N) log N) for M less-than-or-equal-to N, which implies a tim e of O((N log N)/M) for M less-than-or-equal-to N/log N. We also discu ss the effect of relation modification on FD and MVD verification.