Attribute reduction algorithms based on binary discernibility matrix are disadvantageous to the larger database
sets. To overcome above shortcoming, firstly, the two definitions of attribute reduction based on binary discernibility matrix
are proposed. It is proved that attribute reductions acquired from the definitions are all equivalent to the attribute reduction
based on positive region. Then the method of attribute reduction is present, which is based on the vertically partitioned
binary discernibility matrix. In order to decrease the express of space, the partitioned binary attribute columns are all stored
on the external space. In the process of reduction, essential part is transferred into the memory merely. Based above, a
heuristic attribute reduction algorithm is designed, in which upper bounds of the time and space complexity are O(∣C∣∣U∣2)
and O(∣U∣2) respectively. Finally, both of theoretical analysis and experimental results show that the algorithms are correct
and efficient.