Although there is a strong focus on NoSQL databases for cloud computing environments, traditional relational data bases are still an integral part of many computing services in the cloud. Two significant issues in managing a relational database in a cloud environment are handling the inevitable evolution of the database schema and managing changes to system configuration and other data stored in the database as the system evolves over time. Techniques for handling these issues in on-premise databases are much less feasible in cloud computing environments, which demand efficiency, elasticity, and scalability. We propose a versioning system that can be used in relational databases to allow new versions of the database schema and data to be maintained within the same database as the production data. Past research on versioning either handles data versioning but not schema changes, or handles both but is focused on OLAP or XML databases. In this paper, we describe a mechanism for storing concurrent versions of data in an OLTP database. We explore two different implementation alternatives for versioned data storage and evaluate their relative merits given different workloads. We provide a concrete description of how this can be implemented within the InnoDB storage engine, which is the default data store for MySQL databases, and we present a quantitative comparison of the two implementations in InnoDB.