Distributed relational or more recently object-oriented databases usually employdata fragmentation techniques during the design phase in order to split and allocate thedatabase entities across the nodes of the system. Most of the design algorithms are usuallystatic and do not take into account the system evolution: data updates and addition of newapplications. As this is an important issue in modern databases, we propose in this paper anincremental method for dynamically re-fragmenting an existing database as it evolves overtime. We prove that by incrementally changing the database schema and allocation over timewe improve database availability. This is a direct result of the reduced amount of time neededfor incremental fragmentation as compared to a full fragmentation.