Integrity constraints are conditions that a database is enforced to obey at any time so that it is guaranteed to be in a legal state. In this paper, a new approach for integrity constraint checking in deductive databases is proposed based on the new inference tool of normal deduction graphs. In this method, the constraint checking graph associated with a database is constructed based on the given rules and integrity constraints when the database is defined. Four sets of literals derived from the above graph are then used to detect whether an update affects any integrity constraints in order to avoiding unnecessary checkings. If it does, the proposed checking algorithm is then applied, depending on different update type: the insertion or the deletion of a fact, a rule, or an integrity constraint. The checking method has the advantages that only the implicit updates relevant to the affected integrity constraints are efficiently computed, substitutions obtained before can be reused, and it does not have the inefficiencies of linear proof procedures.