A method, system, and computer program product for implementing backup history cleanup operations for a database management system are provided. The method includes identifying a version control base (VCB) value for a most recently stored record in a history table, the record representing a back up copy of a data set. The method includes scanning the table starting from most recently stored records to identify records that represent previous backup copies of the data set, the records assigned VCB values. Using a retention limit value assigned to each of the VCBs, the method includes selecting at least one record to determine the deletion date for use in implementing the cleanup operations. The selection includes counting the number of records, representing back up copies of the data set, for each VCB value; identifying last records for respective VCBs that do not exceed the retention limit value; selecting the oldest storage date among the last records; and deleting records that have storage dates older than the oldest storage date.