Virtual databases are provisioned using point-in-time copies of a source database. Transaction logs received from the source database are applied to a point-in-time copy of the source database to create recovery milestones comprising database blocks that can be used to provision virtual databases. The recovery milestones are created in advance of receiving a request to provision a virtual database. Each recovery milestone is validated to determine that a consistent database snapshot can be created using the recovery milestone. If a problem is identified that prevents creation of a consistent database snapshot, the problem is fixed before creating the next recovery milestone. In response to receiving a request to provision a virtual database corresponding to a point in time, a recovery milestone is identified and transaction logs applied to the recovery milestone to create a database snapshot corresponding to the requested point in time.