For incomplete food safety information system, this paper proposes a direct method of attribute relative reduction based on rough set theory. This reduction method gives the concept of tolerance relationship similar matrix via using an extension of equivalence relationship of rough set theory, which is called tolerance relationship. It solves the problem of inconsistency in the incomplete information system through the introduction of restrictions of the generalized decision function. It calculates the core attributes of incomplete information systems via the tolerance relationship similar matrix. It applies attribute significance, which this paper puts forward based on attribute frequency in the tolerance relationship similar matrix, as the heuristic konwledge. It makes use of binsearch heuristic algorithm to calculate the candidate attribute expansion so that it can reduce the expansion times to speed up reduction. Experiment results show that this method is simple and effective.