In the past, we proposed an incremental mining algorithm for maintenance of sequential patterns based on the concept of pre-large sequences as new records were inserted. In this paper, we attempt to apply the concept of pre-large sequences to maintain sequential patterns as records are deleted. Pre-large sequences are defined by a lower support threshold and an upper support threshold. They act as buffers to avoid the movements of sequential patterns directly from large to small and vice-versa. Our proposed algorithm does not require rescanning original databases until the accumulative amount of deleted customer sequences exceeds a safety bound, which depends on database size. As databases grow larger, the numbers of deleted customer sequences allowed before database rescanning is required also grow. The proposed approach is thus efficient for a large database.