A system comprising: a relational database comprising a set of one or more tables (231, 232, 233); a stored procedure store having thereon a set of one or more stored procedures (221, 222) through which a plurality of machines perform data operations on the set of one or more tables; a service that comprises the plurality of machines that perform data operations on the relational database via the stored one or more stored procedures; and a service upgrade component that manages upgrades of the service without service downtime, the service upgrade component upgrading the relational database by performing the following: adding new one or more tables (234, 235, 236) to the relational database; after adding the new one or more tables to the relational database, an act of adding new stored procedures (223, 224) to the stored procedure store, the new stored procedures referencing the new tables; and after upgrading the relational database, upgrading each of at least some of the plurality of machines of the service so that the upgraded machines (211', 212') perform data operations on the relational database via the new stored procedures, wherein the upgrade of the relational database occurs without changing the set of one or more stored procedures, and wherein at least some of the plurality of machines (213, 214) continue to perform data operations on the relational database using the set of one or more stored procedures after the upgrade of the relational database, the at least some of the plurality of machines not performing data operations on the newly added tables using the newly added stored procedures at least not until the corresponding machine is upgraded. a relational database comprising a set of one or more tables (231, 232, 233); a stored procedure store having thereon a set of one or more stored procedures (221, 222) through which a plurality of machines perform data operations on the set of one or more tables; a service that comprises the plurality of machines that perform data operations on the relational database via the stored one or more stored procedures; and a service upgrade component that manages upgrades of the service without service downtime, the service upgrade component upgrading the relational database by performing the following: adding new one or more tables (234, 235, 236) to the relational database; after adding the new one or more tables to the relational database, an act of adding new stored procedures (223, 224) to the stored procedure store, the new stored procedures referencing the new tables; and after upgrading the relational database, upgrading each of at least some of the plurality of machines of the service so that the upgraded machines (211', 212') perform data operations on the relational database via the new stored procedures, adding new one or more tables (234, 235, 236) to the relational database; after adding the new one or more tables to the relational database, an act of adding new stored procedures (223, 224) to the stored procedure store, the new stored procedures referencing the new tables; and after upgrading the relational database, upgrading each of at least some of the plurality of machines of the service so that the upgraded machines (211', 212') perform data operations on the relational database via the new stored procedures, wherein the upgrade of the relational database occurs without changing the set of one or more stored procedures, and wherein at least some of the plurality of machines (213, 214) continue to perform data operations on the relational database using the set of one or more stored procedures after the upgrade of the relational database, the at least some of the plurality of machines not performing data operations on the newly added tables using the newly added stored procedures at least not until the corresponding machine is upgraded.