A system and methods to provide updates of an oblivious database that is based on an original database without compromising privacy guarantees, and without requiring a periodic downtime to re-initialize the database. According to embodiments of the present invention, update caches are provided at the random servers that are not emptied or sent to the oblivious database after every update in a predictable fashion. Instead, updates are made incrementally to the oblivious database in an order that is independent of how the original database is updated. Hence there is no way for the server to learn which record of the oblivious database corresponds to an updated block from the original database.