Abstract:
A technique for converting a first version of a database to a second version is disclosed. The technique includes determining available translation steps, selecting a translation path from the first version of the database to the second version, and executing the selected translation steps in the translation path. The translation path includes selected translation steps from among the available translation steps.

Description:
CROSS REFERENCE TO OTHER APPLICATIONS 
     U.S. patent application Ser. No. 10/950,357 entitled MARKUP LANGUAGE SPECIFICATION OF A DATABASE SCHEMA is incorporated herein by reference for all purposes. 
     BRIEF SUMMARY OF THE INVENTION 
     A technique for converting a first version of a database to a second version is disclosed. The technique includes determining available translation steps, selecting a translation path from the first version of the database to the second version, and executing the selected translation steps in the translation path. The translation path includes selected translation steps from among the available translation steps. 
     FIELD OF THE INVENTION 
     The present invention relates generally to data storage. More specifically, database migration is disclosed. 
     BACKGROUND OF THE INVENTION 
     A database schema describes the organization and structure of data in a database. Typically the schema of a database is modified incrementally with each new software release.  FIG. 1  is a diagram illustrating five versions of a database, v 1  to v 5 . For example, a first version (v 1 ) of a customer database may include first name, last name, and SSN fields. In the next version (v 2 ), a date of birth field may be added. As more versions are released, a customer site may end up with multiple databases each having different versions of software. Maintaining the logic to migrate the various existing versions to newer versions becomes increasingly difficult. For example, in  FIG. 1 , specific logic must be maintained to translate from v 1  to v 2 , v 1  to v 3 , v 1  to v 4 , v 1  to v 5 , v 3  to v 5 , v 2  to v 3 , v 2  to v 4 , v 4  to v 5 , and v 2  to v 5 . In addition, it is difficult to express translations that span more than one version, such as a translation from v 1  to v 3 . It would be desirable to have a simpler method for translating databases. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Various embodiments of the invention are disclosed in the following detailed description and the accompanying drawings. 
         FIG. 1  is a diagram illustrating five versions of a database, v 1  to v 5 . 
         FIG. 2  is a diagram illustrating various versions of a database. 
         FIG. 3  is a flowchart illustrating a method of converting a database from a first version to a second version. 
         FIG. 4  is a diagram of a translation graph. 
         FIG. 5  is a flowchart illustrating a method of applying translation steps to arrive at a desired database version. 
         FIG. 6  is a flowchart illustrating a method of translating a database from one version to the next version. 
         FIG. 7  is a block diagram illustrating a system used in one embodiment to manage a database cluster having multiple database versions. 
         FIG. 8  is a flowchart illustrating a method of propagating an update from a first database to a second database with a different version. 
     
    
    
     DETAILED DESCRIPTION 
     The invention can be implemented in numerous ways, including as a process, an apparatus, a system, a composition of matter, a computer readable medium such as a computer readable storage medium or a computer network wherein program instructions are sent over optical or electronic communication links. In this specification, these implementations, or any other form that the invention may take, may be referred to as techniques. In general, the order of the steps of disclosed processes may be altered within the scope of the invention. 
     A detailed description of one or more embodiments of the invention is provided below along with accompanying figures that illustrate the principles of the invention. The invention is described in connection with such embodiments, but the invention is not limited to any embodiment. The scope of the invention is limited only by the claims and the invention encompasses numerous alternatives, modifications and equivalents. Numerous specific details are set forth in the following description in order to provide a thorough understanding of the invention. These details are provided for the purpose of example and the invention may be practiced according to the claims without some or all of these specific details. For the purpose of clarity, technical material that is known in the technical fields related to the invention has not been described in detail so that the invention is not unnecessarily obscured. 
     Converting a first version of a database to a second version is disclosed. Available translation steps are determined, a translation path from the first version of the database to the second version is selected, and translation steps in the translation path are executed. 
       FIG. 2  is a diagram illustrating various versions of a database. In this example, Version  1  of the database includes a Customer object with three members: LastName, FirstName, and SSN. Version  2  of the database includes a customer object with four members: LastName, FirstName, SSN, and DOB_US_Format (i.e., month-date-year). Version  3  of the database includes a customer object with three members: LastName.FirstName, SSN, and DOB_Euro_Format (i.e., date-month-year). Version  2 , patch  1  of the database includes a customer object with four members: LastName, FirstName, SSN, and DOB_Std_Format. Although objects are described in this example, any other appropriate data structures, such as tables or structures, may also be used. 
     r 1  represents the translation from version  1  to version  2 . r 1  includes a new member translation for the Customer object, where the new member is DOB_US_Format. r 2  represents the translation from version  1  to version  2 , patch  1 . r 2  includes a new member translation for the Customer object, where the new member is DOB_Std_Format. r 3  represents the translation from version  2  to version  3 . r 3  includes two member value transform translations for the Customer object. The first member value transform concatenates LastName and FirstName. The second member value transform reformats DOB_US_Format to DOB_Euro_Format. r 4  represents the translation from version  2 , patch  1  to version  3 . r 4  includes two member value transform translations for the Customer object. The first member value transform concatenates LastName and FirstName. The second member value transform reformats DOB_Std_Format to DOB_Euro_Format. For example, to migrate a database from version  1  to version  3 , either r 1  and r 3 , or r 2  and r 4  can be applied. The translations are lossless and any available translation path can be taken. In one embodiment, each translation r 1 -r 4  is expressed in a markup language such as XML, as more fully described below. 
     The following is an example of an XML description of a database (Example 1): 
     &lt;database version=“2.0.0R18”/&gt; 
     &lt;object&gt;
         &lt;property name=“name” value=“127.0.0.1”/&gt;   &lt;property name=“_type” value=“.com.infoblox.one.node”/&gt;   &lt;property name=“first_name” value=“John”/&gt;   &lt;property name=“last_name” value=“Doe”/&gt;       

     &lt;/object&gt; 
     &lt;object&gt;
         &lt;property name=“name” value=“com”/&gt;   &lt;property name=“_type” value=“.com.infoblox.one.zone”/&gt;       

     &lt;/object&gt;
         .   .   .
 
&lt;/database&gt;
       

     In this example, the specification describes version 2.0.0_R18 of a database. The database includes a plurality of objects. Each object includes one or more members, where a member includes a name value pair. For example, the first object has four members: name “127.0.0.1”, type “.com.infoblox.one.node”, first_name “John”, and last_name “Doe”. The first object is a node object. The second object has two members: name “com” and type “.com.infoblox.one.zone”. The second object is a zone object. Any number of objects can be specified. In one embodiment, the XML description of the database used is RTXML, a markup language described in U.S. patent application Ser. No. 10/950,357, which is incorporated herein by reference above. 
     The following is an example of a Migration Description XML (MDXML) specification of a translation (Example 2): 
     &lt;STRUCTURE-TRANSFORM STRUCT-NAME=“.com.infoblox.one.node”&gt; 
     &lt;MEMBER-NAME-CHANGE PRE-XFORM-VALUE=“name” POST-XFORM-VALUE=“node_name”/&gt; 
     &lt;MEMBER-VALUE-CHANGE MEMBER-NAME=“name” PRE-XFORM-VALUE=“127.0.0.1” POST-XFORM-VALUE=“192.168.1.2”/&gt; 
     &lt;MEMBER-VALUE-CHANGE MEMBER-NAME=“name” PRE-XFORM-VALUE=“127.0.0.2” POST-XFORM-VALUE=“192.168.1.3”/&gt; 
     &lt;NEW-MEMBER MEMBER=“DOB” DEFAULT-VALUE=“Jan. 1, 1970” 
     &lt;MEMBER-VALUE-XFORM&gt;
         &lt;concat&gt;
           &lt;first_name&gt;   &lt;last_name&gt;   
           &lt;/concat&gt;   &lt;destination full_name/&gt;       

     &lt;/MEMBER-VALUE-XFORM&gt; 
     &lt;/STRUCTURE-TRANSFORM&gt; 
     For example, MDXML may be used to describe a translation such as r 1 , r 2 , r 3 , or r 4 . In this example, the translation to be applied to structures of type “.com.infoblox.one.node” is specified. The translation may include a set of translations (or transforms), such as the following: 
     MEMBER-NAME-CHANGE changes the name of a member. For example, if the name of the structure was previously “name”, it would be changed to “node_name”. 
     MEMBER-VALUE-CHANGE changes the value of a member. For example, if the value of the name of the structure was previously “127.0.0.1”, it would be changed to “192.168.1.2”. 
     NEW-MEMBER adds a new member to the structure. For example, a new member with name “DOB” and value “Jan. 1, 1970” would be created in the structure. 
     MEMBER-VALUE-XFORM transforms the value of a member. For example, first_name and last_name values would be transformed according to the concat tag, where the concat tag could indicate a concatenation of the first_name and last_name values. 
     Other types of translations may also be specified for objects of type “.com.infoblox.one.node”. Translations for other types of objects may also be specified. 
     The following is an example of an XML description of a database after the translation shown in Example 2 is applied to the database shown in Example 1 (Example 3): 
     &lt;database version=“2.0.0R19”/&gt; 
     &lt;object&gt;
         &lt;property name=“node_name” value=“192.168.1.2”/&gt;   &lt;property name=“_type” value=“.com.infoblox.one.node”/&gt;   &lt;property name=“dob” value=“Jan. 1, 1970”/&gt;   &lt;property name=“full_name” value=“John. Doe”/&gt;       

     &lt;/object&gt; 
     &lt;object&gt;
         &lt;property name=“name” value=“com”/&gt;   &lt;property name=“_type” value=“.com.infoblox.one.zone”/&gt;       

     &lt;/object&gt;
         .   .   .
 
&lt;/database&gt;
       

     As shown, “node” has become “node_name”. The member with name “_type” is unchanged. “dob” is a new member. “full_name” is a new member whose value is the concatenation of the first_name and last_name values. The zone object is the same, since there were no translations described for the zone object in the MDXML translation shown in Example 2. 
       FIG. 3  is a flowchart illustrating a method of converting a database from a first version to a second version. In this example, a graph is built based on a map list and MDXML files ( 402 ). The following is an example of a map list (Example 4): 
     &lt;rtxml-version-map-list&gt; 
     &lt;RTXML-VERSION-MAP version=“2.0.0-R18” 
     md5=“2bf689e0aa69ab0663147908250cacc0”/&gt; 
     &lt;RTXML-VERSION-MAP version=“2.0.0-R19” 
     md5=“79fcd96045cb43147845d8336892a835”/&gt; 
     &lt;/rtxml-version-map-list&gt; 
     The map list uniquely maps a content based key to a database version. In one embodiment, the content based key is a hash value, such as an MD5 sum, of the database schema. In the example shown, the first mapping is from version “2.0.0-R18” to key “2bf689e0aa69ab0663147908250cacc0”. The key was obtained by taking a hash of the version “2.0.0-R18” database schema. Using the map list, the database version can be determined and the appropriate translation graph can be constructed.  FIG. 4  is a diagram of a translation graph. A translation graph describes the available paths that may be used to translate a database from one version to another version. In this example, the translation graph shows the available paths that may be used to translate a database from version “2.0.0_R18” to version “2.0.0_R24”. (“2.0.0_Roff” might be a special release created for a particular customer.) For example, translations t 1 , t 2 , t 3 , t 9 , translations t 4 , t 5 , or translations t 6 , t 7 , t 8 , t 9  may be applied to translate the database from version 2.0.0_R18 to version 2.0.0_R24. In one embodiment, for each translation step t 1 -t 9 , there is an MDXML file that describes the translation. Thus, if there is an MDXML file available for a particular translation, that translation is available for use as a step in a translation path. 
     Returning to  FIG. 3 , a translation path is selected ( 404 ). For example, the shortest path (e.g., t 4 , t 5 ) or the first path found (e.g., t 1 , t 2 , t 3 , t 9 ) may be selected. The appropriate translation steps in the path are applied to the database ( 406 ). For example, if the shortest path was selected in step  404 , the MDXML file for t 4  and the MDXML file for t 5  would be used to translate the database, as more fully described below. 
       FIG. 5  is a flowchart illustrating a method of applying translation steps to arrive at a desired database version. In one embodiment, this method is used to perform step  406  of  FIG. 3 . In this example, an XML dump of the database is performed ( 702 ). For example, the database could be a relational, object-oriented, or any other type of database. That database would be dumped into an XML file, e.g., formatted similarly to the file shown in Example 1. In one embodiment, the database is already described in XML. The database is translated from the current version to the next version ( 704 ) using the appropriate MDXML file. In one embodiment, the MDXML file is parsed into in memory structures based on the type of structure, e.g., there is one in memory structure describing the translations for each type of structure. It is determined whether the database version is the desired version ( 706 ). If the database version is the desired version, the process ends ( 708 ). If the database version is not the desired database version, the process returns to step  704  in which the database is translated from the current version to the next version using the appropriate MDXML file. For example, if the next step is to perform translation t 2  in  FIG. 4 , “t 2 .mdxml” is used. In this example, the database is translated from one version to another incrementally, i.e., the database is translated one version at a time until the desired version is reached. In one embodiment, each time a new database version is released, an MDXML file is released to describe the incremental translation from the previous version. 
       FIG. 6  is a flowchart illustrating a method of translating a database from one version to the next version. In one embodiment, this process is used to perform step  704  of  FIG. 5 . In this example, the first object is read ( 802 ). In one embodiment, the first object in an XML file representing a database is read. For example, returning to Example 1, the first object read would be the node object with name “127.0.0.1” and type “.com.infoblox.one.node”. It is determined whether there are any translations for that object type. For example, if the object is a node object, it is determined whether there are any translations for the node object. In some embodiments, the in memory structures of the MDXML file parsed in step  704  are consulted for translations corresponding to the object. For example, if the MDXML file looked like Example 2, it would be determined that there are translations for the node object, as the structure transform shown is for an object (or structure) of type node (“.com.infoblox.one.node”). If it is determined that there are translation(s) for that object type, the translation is applied to the object ( 806 ). 
     For example, if the structure transform for objects of type node shown in Example 2 is applied to the node object shown in Example 1, the resulting object would look like the node structure shown in Example 3. The resulting object is written to a file ( 808 ), e.g., tmp.xml. It is determined whether the object is the last object in the database XML file ( 810 ). If the object is the last object, the process ends ( 812 ). If the object is not the last object, the process returns to step  802  and the next object is read. Returning to step  804 , if there are no translations for that object type, the object is written to the file ( 808 ) and the process continues as described above. The resulting file (e.g., tmp.xml) is the XML file associated with the translated database. The resulting file may be used to generate the new database, such as an object oriented or relational database. In some embodiments, rather than translating one object at a time, objects are translated in groups. 
     In addition to database migration, the system and methods described herein may also be used for other purposes. For example, in one embodiment the techniques described above are used to manage a database cluster having multiple versions of a database. 
       FIG. 7  is a block diagram illustrating a system used in one embodiment to manage a database cluster having multiple database versions. In this example, the system includes five databases  902 - 910 . Databases  902  and  904  have version  1  software. Databases  906  and  908  have version  2  software, and database  910  has version  3  software. Such a scenario, in which multiple database versions exist within a cluster, can occur during a system upgrade process. For example, rather than upgrading all the databases to the latest version at once, the databases may be migrated one at a time. In one embodiment, databases  902 - 910  serve as backups of each other. If one database fails, there are four remaining backup databases that are available. All the databases would need to fail before the cluster failed. If any one of databases  902 - 910  is updated, the other databases would also need to be updated. 
     x 1  represents the translation from version  1  to version  2 . x 1 ′ represents the translation from version  2  to version  1 . x 3  represents the translation from version  2  to version  3 . x 3 ′ represents the translation from version  3  to version  2 . For example, an update sent from database  902  to database  906  would be translated using x 1 . An update from sent from database  906  to database  904  would be translated using x 1 ′. An update sent from database  904  to database  908  would be translated using x 1 . An update sent from database  904  to database  910  would be translated using x 1  and x 3 . Each of translations x 1 , x 1 ′, x 3 , and x 3 ′ may be described by an XML file, such as an MDXML file. 
       FIG. 8  is a flowchart illustrating a method of propagating an update from a first database to a second database with a different version. In this example, an update is received ( 1002 ). For example, an update is received at database  902  in  FIG. 7 . The update could be any write request, such as update, delete, or insert. The version of the database is determined ( 1004 ). For example, a content based key, such as a hash value, is generated based on the first database schema. A map list can be consulted to determine the version of the database from the content based key, as described above. A translation path is determined ( 1006 ). In one embodiment, a translation graph is consulted to determine the translation path. For example, to propagate an update from database  904  (version  1 ) to database  910  (version  3 ), there may be two available translation paths: x 1 , x 3  or x 2 , x 4 . The translation path may be determined based on any appropriate criteria, such as the shortest path or the first path found. The translation path may be predetermined. For example, translation path x 1 , x 3  ma be the predetermined path; that is, when an update is received at database  910 , translation path x 1 , x 3  is automatically used to translate the update. In some embodiments, the translation occurs at database  904 . For example, a translation from v 2  to v 1  may occur at database  904 . The updates are sequentially applied ( 1008 ). For example, x 1  is applied followed by x 3  if translation path x 1 , x 3  is selected. Similarly, the update could be propagated to the other databases in the cluster. 
     Although the foregoing embodiments have been described in some detail for purposes of clarity of understanding, the invention is not limited to the details provided. There are many alternative ways of implementing the invention. The disclosed embodiments are illustrative and not restrictive.