engleski

A Combined Algorithm for Testing Implications of Functional and Multi Valued Dependencies

In this paper a combined algorithm for testing implication problem, F I= f, where F is a set of functional or multi valued dependencies, and f is a functional or multi valued dependency, is presented. The algorithm combines two well known algorithms. The first algorithm solves the implication problem F |= f, where F is a set of functional dependencies and f is a functional dependency (the algorithm is based on the closure of a set of attributes [Maier 83]). The other algorithm solves the problem F |= f, where F is a set of functional or multi valued dependencies and f is a functional or multi valued dependency (the algorithm is based on the dependency basis [Beeri 80]). The time complexity of the new algorithm is the same as one of the algorithm in [Beeri 80]. In addition, the new algorithm is more informative than the algorithms in [Maier 83] and [Beeri 80] in so far as the new algorithm includes the result explanations RE1 and RE2 that indicate how the implication problem F |= f is solved ; the algorithms in [Maier 83] and [Beeri 80] produce only the answer 'Yes' or the answer 'No'. Also, RE1 and RE2 contain the proof of the correctness of the new algorithm.

algorithms; correctness; dependency theory; functional and multi valued dependencies; implication problem; informativeness; time complexity

nije evidentirano