A method, apparatus, and computer instructions for synchronizing a database used by a client device with at least one server. A locally unique identifier is associated with each record in the database at the client. The locally unique identifier for a deleted record is changed to a selected value. This value is selected in a manner to indicate that a record has been deleted. This locally unique identifier may be a negative value and may be selected by multiplying the locally unique identifier by a negative one. The selected value is used in synchronizing the database and is used to track records deleted since a last synchronization of the database. In the depicted examples, this selected value is unique and allows for mapping back to the locally unique identifier for the record.