Abstract: Attribute reduction based on tolerance relation is proposed for incomplete decision table. Tolerance relation is used to define normal form for constructing consistent block, and the most complete description system of maximal consistent block is obtained by translating all maximal consistent blocks to their most complete description, which provides an efficient way for transforming information description. Furthermore, this description system is used to define discernibility matrix, which gives a solution for searching attribution reduction in incomplete decision table. The theoretical derivation and simulation instance shows that this method is feasible and effective in practice.