Abstract: As a useful tool for Data Mining, the Rough Set Theory is widely used in the description of the correlation between attributes of relational database, the reduction of the attribute set, the counting of an attribute importance compared to other attribute importance, the discovery of rules, and so on. First, on the basis of analyzing the Rough Set Theory based on relational database, a more detailed description of attribute set reduction algorithm based on the core is given. Next, in order to reduce the computational complexity of the algorithm, the relationship conception, which describes the contribution of one of condition attributes to decision attribute, is put forward. It is applied to the algorithm above and the speed of the improved algorithm is raised. A brief comparison of the computation complexity of the old algorithm with the improved one is made. Finally, we test the improved algorithm with practical data. The result shows that the improved algorithm can not only reduce the computational complexity, but also gain the solution inferior to the best attribute reduction in most cases.

Key words: rough set theory, approximation space, reduction algorithm, relationship