Like any other database application, object database applications are subject to evolution. Evolution, however, is a critical requirement in object-oriented databases as it is a fundamental characteristic of complex applications such as computer-aided design and manufacturing (CAD/CAM) and office information systems. Object-oriented databases are inherently suited to supporting such applications. In this paper we present a database evolution taxonomy for object-oriented databases. We describe a conceptual database model and use it to define the taxonomy. We also present the various invariants and rules governing the various evolution operations. The execution sequence of rules is described. An implementation of the database model and the evolution taxonomy in the Semi-Autonomous Database Evolution System (SADES), is discussed. The implementation employs aspect-oriented programming techniques to provide a flexible means of transforming objects upon evolution, and implementing some application-specific evolution primitives. A case study compares the evolution taxonomy with existing evolution approaches. The comparison demonstrates that the taxonomy and its corresponding implementation in SADES provide improved coverage of the fundamental evolution operations to which an object database might be subjected. At the same time, erosion of the database structure is avoided by maintaining a coherent and comprehensible view of historical changes.