Data in tables with foreign key relationship is synchronized in batches employing a two-pass process during playback based on whether the foreign key constraint is a linear dependency, self-referencing, or cyclic. A separate table containing a primary key of records and database timestamp columns for change operations may also be used for batch synchronization in addition to or instead of adding database timestamp columns to existing tables.