An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database
Zvi Galil · Journal of the ACM · 1982
All algonthm that constructs, for a given set of (functional and multwalued) dependen-cJes X and a set of attributes X, the dependency basis of X as described.The algorithm runs in time O(( 1+ min(E, logp))llZl[), where p is the number of sets m the dependency basas of X,/~ Js the number of multivalued dependencies in X, and IlXll as the length of ~. a A variant of the algorithm tests whether a dependency a is unplied by X m time O((1 + mm(/~, log p-))ll~.ll),where ff is the number of sets m the dependency basas of the left-hand side of o that intersect the right-hand sade of o Whenever all the dependencies in X are functaonal dependenoes, these algorithms are linear Ume Categories and Subject Descriptors.F.