A Method for Extracting Knowledge from Decision Tables in Terms of Functional Dependencies

The problem of extracting knowledge from decision tables in terms of functional dependencies is one of the important problems in knowledge discovery and data mining. Based on some results in relational database, in this paper we propose two algorithms. The first one is to find all reducts of a consistent decision table. The second is to infer functional dependencies from a consistent decision table. The second algorithm is based on the result of the first. We show that the time complexity of the two algorithms proposed is exponential in the number of attributes in the worst case.