Abstract: In order to update the attribute reduction of dynamic decision tables, an incremental algorithm of Pawlak reduction with a given attribute order was proposed based on a discernibility matrix element set. To different newly added objects this algorithm updates the discernibility matrix element set quickly. Thus, from the change of its elements the original Pawlak reduction can be updated effectively based on the given attribute order. An illustrative example and simulation experiment show that compared with the non-incremental algorithm, the proposed algorithm is efficient and feasible and has a 91.4% improvement in average efficiency.