Title of Invention

IN-PLACE EVOLUTION OF XML SCHEMAS IN DATABASES

Abstract

1A method and system for the in-place evolution of XML schemas is disclosed. To automatically evolve an existing XML schema, a schema evolver receives both an existing XML schema and an XML document as input. The XML document indicates changes to be made to the existing XML schema. Based on the existing XML schema and the XML document, the schema evolver evolves the existing XML schema into a new XML schema that incorporates the changes indicated in the XML document. According to one aspect, the schema evolver generates one or more SQL statements based on the new XML schema. The SQL statements, when executed by a database server, cause the database server to evolve database structures that were based on the formerly existing XML schema so that the database structures conform to the new XML schema. This is accomplished "in place," without copying the data in the database structures.

Full Text

IN-PLACE EVOLUTION OF XML SCHEMAS IN DATABASES RELATED APPLICATIONS [0001] The present application is related to the following U.S. Patent Applications, the entire contents of which are incorporated herein by reference for all purposes: [0002] U.S. Patent Application Serial No. 10/260,138, filed on September 27,2002, entitled OPERATORS FOR ACCESSING HIERARCHICAL DATA IN A RELATIONAL SYSTEM, by Nipun Agarwal, Ravi Murthy, Eric Sedlar, Sivasankaran Chandrasekar and Fei Ge; [0003] U.S. Patent Application Serial No. 10/260,384, filed on September 27,2002, entitled PROVIDING A CONSISTENT HIERARCHICAL ABSTRACTION OF RELATIONAL DATA, by Nipun Agarwal, Eric Sedlar, Ravi Murthy and Namit Jain; [0004] U.S. Patent Application Serial No. 10/259,278, filed on September 27,2002, entitled MECHANISM FOR MAPPING XML SCHEMAS TO OBJECT-RELATIONAL DATABASE SYSTEMS, by Ravi Murthy, Muralidhar Krishnaprasad, Sivasankaran Chandrasekar, Eric Sedlar, Vishu Krishnamurthy and Nipun Agarwal; [0005] U.S. Patent Application Serial No. 10/260,161, filed on September 27,2002, entitled INDEXING TO EFFICIENTLY MANAGE VERSIONED DATA IN A DATABASE SYSTEM, by Nipun Agarwal, Eric Sedlar and Ravi Murthy; [0006] U.S. Patent Application Serial No. 10/256,524, filed on September 27,2002, entitled MECHANISMS FOR STORING CONTENT AND PROPERTIES OF HIERARCHICALLY ORGANIZED RESOURCES, by Ravi Murthy, Eric Sedlar, Nipun Agarwal, and Neema Jalali; [0007] U.S. Patent Application Serial No. 10/259,176, filed on September 27, 2002, entitled MECHANISM FOR UNIFORM ACCESS CONTROL IN A DATABASE SYSTEM, by Ravi Murthy, Eric Sedlar, Nipun Agarwal, Sam Idicula, and Nicolas Montoya; [0008] U.S. Patent Application Serial No. 10/256,777, filed on September 27,2002, entitled LOADABLE UNITS FOR LAZY MANIFESTATION OF XML DOCUMENTS by Syam Pannala, Eric Sedlar, Bhushan Khaladkar, Ravi Murthy, Sivasankaran Chandrasekar, and Nipun Agarwal; [0009] U.S. Patent Application Serial No. 10/260,381, filed on September 27, 2002, entitled MECHANISM TO EFFICIENTLY INDEX STRUCTURED DATA THAT PROVIDES HIERARCHICAL ACCESS IN A RELATIONAL DATABASE SYSTEM, by Neema Jalali, Eric Sedlar, Nipun Agarwal, and Ravi Murthy; [0010] U.S. Patent Application Serial No. 10/648,600, filed on August 25,2003, entitled DIRECT LOADING OF SEMISTRUCTURED DATA, by Namit Jain, Nipun Agarwal, and Ravi Murthy; [0011] U.S. Patent Application Serial No. 10/648,577, filed on August 25, 2003, entitled DIRECT LOADING OF OPAQUE TYPES, by Namit Jain, Ellen Batbouta, Ravi Murthy, Nipun Agarwal, Paul Reilly, and James; and [0012] U.S. Patent Application Serial No. 10/648,497, filed on August 25, 2003, entitled MECHANISM TO ENABLE EVOLVING XML SCHEMA, by Sam Idicula, Nipun Agarwal, Ravi Murthy, Eric Sedlar, and Sivasankaran Chandrasekar. FIELD OF THE INVENTION [0013] The present invention relates to data management systems, and in particular, to techniques for updating an XML schema, and for updating XML-schema-based instance documents and database structures to conform to an updated XML schema. BACKGROUND OF THE INVENTION [0014] Using Extensible Markup Language (XML), information may be represented in conformity with a specified hierarchical structure. An XML schema defines such a structure. An XML schema comprises a root XML element. One or more other XML elements may be nested within the root XML element as content of the root XML element. Such nested XML elements are called child XML elements of the root XML element. Conversely, the root XML element is called the parent XML element of the child XML elements. Each child XML element may, in turn, be a parent XML element of one or more additional child XML elements nested within the parent XML element. The parent-child relationships of XML elements within an XML schema define a hierarchical structure according to which information may be stored in a hierarchically structured manner. For each XML element in an XML schema, the XML schema defines the type of that XML element’s content value. [0015] Information stored in conformity with an XML schema does not need to indicate the XML tags of the XML elements in the XML schema. Specifically, as long as it is known to which XML schema such information conforms, content values that correspond to XML elements in an XML schema may be stored without the XML tags that would enclose the content values. For example, content values may be stored according to a format in which the content values are separated by delimiters such as comma characters,. Reference may be made to the corresponding XML schema in order to align the content values with their corresponding XML elements in the XML schema. [0016] For another example, database structures, such as database tables and database views, may be generated based on an XML schema. The names and data types associated with columns in such database tables may correspond to names and data types indicated by attributes of XML elements in the XML schema. A content value that corresponds to a particular XML element in the XML schema may be stored in a database table’s column that corresponds to the particular XML element [0017] Multiple different sets of content values, each based on the same XML schema, may be stored distinctly from each other. Each set is a separate “instance document.” For example, an XML schema may define an XML element such as ““. One instance document may contain a r content value of “1” that corresponds to the XML element. Another instance document may contain a content value of “2” that corresponds to the same XML element. When content values are stored in database tables, content values from different instance documents may be stored in different rows of the database tables. Content values that correspond to the same XML element may be stored in the same column of a database table. [0018] Often, even after many instance documents have been generated in conformity with a particular XML schema, it may be desirable to evolve the XML schema. For example, it may be desirable to add a new XML element to the XML schema, sometimes by inserting the new XML element between existing XML elements in the XML schema. For another example, if a particular XML element represents an enumerated data type, it may be desirable to insert a new XML element into a set of child XML elements of the particular XML element, where each child XML element represents a different enumerated value. [0019] An XML schema may be modified manually using, for example, a text editing tool. Unfortunately, as a consequence of the modification of the XML schema, existing instance documents that formerly conformed to the XML schema might cease to conform to the XML schema. Instance documents interpreted according to the modified XML schema might be interpreted incorrectly, causing content values in the instance documents to be aligned with the wrong XML elements in the modified XML schema. [0020] Additionally, database structures, such as database tables and database views, whose structures were based on the XML schema prior to the modification of the XML schema, might also cease to conform to the XML schema. As a result, it might be impossible to store correctly, in such database structures, content values in instance documents generated in conformity with the modified XML schema. For example, a database table might lack a column that corresponds to a new XML element that was inserted into the XML schema. Furthermore, existing instance documents may be interpreted incorrectly if the mapping of a specific column to a specific XML element has changed, [0021] There is no established approach for ensuring that XML-schema-based instance documents and database structures will continue to conform to the XML schema upon which they are based after the XML schema has been modified. A technique is needed for evolving an XML schema while ensuring that XML-schema-based instance documents and database structures will continue to conform to the XML schema even after the XML schema has been evolved. [0022] The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section. BRIEF DESCRIPTION OF THE DRAWINGS [0023] The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which: [0024] Figure 1 is a block diagram that illustrates the interaction between structures involved in in-place XML schema evolution, according to an embodiment of the present invention; [0025] Figure 2 is a flow diagram that illustrates a technique, according to an embodiment of the present invention, for evolving an XML schema and XML-schema- based database structures in place; and [0026] Figure 3 is a block diagram that illustrates a computer system upon which an embodiment of the invention may be implemented, DETAILED DESCRIPTION OF THE INVENTION [0027] A method and system are provided for in-place evolution of (1) an XML schema, (2) database object types and tables that are based on the XML schema, and (3) database object instances that are based on the database object types. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention. FUNCTIONAL OVERVIEW [0028] It is desirable that instance documents and database structures that conform to an XML schema evolve with the XML schema so that the instance documents and database structures continue conform to the XML schema after the XML schema has been evolved. According to one embodiment of the present invention, such continued conformity is achieved with a schema evolver that executes in a computer system. [0029] The schema evolver receives both an existing XML schema and an XML document as input. The XML document indicates one. or more changes to be made to the existing XML schema. Based on the existing XML schema and the XML document, the schema evolver first generates a new XML schema that incorporates the changes indicated in the XML document. [0030] Additionally, according to one embodiment, the schema evolver generates one or more Structured Query Language (SQL) statements based on the new XML schema. The SQL statements, when executed by a database server, cause the database server to evolve database structures that were based on the formerly existing XML schema so that the database structures conform to the new XML schema. Such database structures may define, for example, database object types and database object instances. DATABASE OBJECT TYPES, DATABASE OBJECT TABLES, AND DATABASE OBJECT INSTANCES [0031] A database object type specifies the structure and attributes of all database object instances that are based on the database object type. For example, an “address” object type might specify a sequence of three primitive “VARCHAR” object types: one to store a person’s name, one to store a street identifier, and one to store a city identifier. A database object table is a database table that is based on a database object type. For example, an “address” object table based on the “address” object type would comprise at least three separate columns; one for a person’s name, one for a street identifier, and one for a city identifier. When a database object type is altered, database object tables based on that database object type are altered correspondingly. [0032] Based on the “address” object type, multiple different “address” object instances may be created. Each of the “address” object instances conforms to the structure and attributes specified by the “address” object type. Each different “address” object instance may specify a different value for a particular attribute specified by the “address” object. For example, one “address” object instance may specify “Joe Smith” as the value of the name attribute, while another “address” object instance may specify “John Taylor” as the value of the name attribute. [0033] When an XML schema is evolved, XML elements may be added to or deleted from the XML schema. The addition of a new XML element may cause the schema evolver to generate an SQL statement that, when executed by a database server, causes the database server to add a corresponding attribute to a database object type. The SQL statement, when executed by the database server, may also cause the database server to add a corresponding column to a database table that stores database object instances that are based on the database object type. [0034] Similarly, the deletion of an XML element may cause the schema evolver to generate an SQL statement that, when executed by the database server, causes the database server to remove a corresponding attribute from a database object type. The SQL statement, when executed by the database server, may also cause the database server to drop a corresponding column from a database table that stores database object instances that are based on the database object type. [0035] Thus, the SQL statements generated by the schema evolver may cause both database object types and database object instances to be evolved to conform to a new XML schema. Such SQL statements may cause database object types and database object instances to be created, deleted, and/or altered. IN-PLACE EVOLUTION [0036] Techniques described herein allow for “in-place” evolution of XML schemas, as well as database object types and database object instances that are based on such XML schemas. Through “in-place” evolution, additional copies of information represented in such structures do not need to be made. Instead, the information represented by such structures may be updated without making additional copies of the information. Changes to an existing XML schema may be made automatically by modifying the XML schema according to changes indicated by an XML document. A database server may execute automatically generated SQL statements that cause the database server to alter existing database object types and database object instances to conform to the modified XML schema. [0037] “In-place” evolution differs from “data copy” evolution. “Data copy” evolution involves making a copy of the information represented by the structures to be evolved, then the deleting the structures, then creating new structures, and then inserting the information from the copy back into corresponding components of the new structures. “In-place” evolution typically exhibits performance superior to “data copy” evolution and does not require the disk space that data copy evolution requires. INTERACTION BETWEEN STRUCTURES INVOLVED IN IN-PLACE XML SCHEMA EVOLUTION [0038] Figure 1 is a block diagram that illustrates the interaction between structures involved in in-place XML schema evolution, according to an embodiment of the present invention. A schema evolver 102 is a component of a database server 104. Database server 104 executes in a computer system. The schema evolver 102 receives, as input, an existing XML schema 106 and an XML document 108. Existing XML schema 106 is an XML schema that is currently registered in database 110. XML document 108 indicates, in XML, changes to be made to existing XML schema 106. [0039] Schema evolver 102 automatically alters existing XML schema 106 so that the changes indicated by XML document 108 are incorporated into existing XML schema 106. As a result, existing XML schema 106 evolves into evolved XML schema 112. Evolved XML schema 112 incorporates all of the changes indicated by XML document 108. [0040] According to one embodiment, schema evolver 102 receives, as input, evolved XML schema 112, existing database object types 114, and existing database object instances 116. Existing database object types 114 conform to the structure indicated by existing XML schema 106. Existing database object instances 116 conform to the type definitions indicated by database object types 114. [0041] Schema evolver 102 determines which aspects of existing database object types 114 do not conform to evolved XML schema 112. Based on these non-conforming aspects, schema evolver 102 automatically generates SQL statements 118 that, when executed by database server 104, cause database server 104 to alter existing database object types 114 to conform to evolved XML schema 112. Additionally, when executed by database server 104, SQL statements 118 also cause the database server to make existing database object instances 116 conform to the changes to existing type definitions 114 that will result from database server 104 executing the SQL statements. [0042] Database server 104 executes SQL statements 118. As a result, database server 104 evolves existing database object types 114 into evolved database object types 120. As another result, database server 104 also evolves existing database object instances 116 into evolved database object instances 122. Evolved database object types 120 conform to the structure indicated by evolved XML schema 112. Evolved database object instances 122 conform to the structures indicated by evolved database object types 120. ROLLBACK STATEMENTS [0043] SQL statements 118 maybe called “evolve” statements because, when executed, the SQL statements cause database server 104 to evolve existing database object types 114 and existing database object instances 116. In order to make the evolution an atomic transaction, schema evolver 102 also generates SQL statements 124 that, if executed by database server 104, will cause the database server to undo, or “roll back” all of the effects of SQL statements 118 that have been executed when the error occurs. Therefore, SQL statements 124 may be called “rollback statements.” [0044] If, during execution of SQL statements 118, an error occurs, then database server 104 executes those of SQL statements 124 that will reverse the effects of those of SQL statements 118 that the database server has executed. Therefore, unless the entire evolution completes successfully, no part of the evolution is made permanent. [0045] Changes to XML schema 106 are also reversed when an error occurs during XML schema evolution. For example, schema evolver 102 may track changes that schema evolver 102 makes to XML schema 106 and then undo those changes if an error occurs before the entire evolution transaction is complete. EXAMPLE TECHNIQUE FOR EVOLVING AN XML SCHEMA AND XML-SCHEMA-BASED DATABASE STRUCTURES IN PLACE [0046] Figure 2 is a flow diagram that illustrates a technique 200, according to an embodiment of the present invention, for evolving an XML schema and XML-schema-based database structures in place. In block 202, a schema evolver receives an XML document. The XML document indicates one or more changes to be made to an existing XML schema. [0047] In block 204, the schema evolver generates, based on the existing XML schema and the XML document, an evolved XML schema. The evolved XML schema incorporates all of the changes indicated by the XML document. The schema evolver may track the changes that were made to the existing XML schema in order to produce the evolved XML schema. [0048] In block 206, the schema evolver generates, based on the evolved XML schema, “evolve” SQL statements. The “evolve” SQL statements, when executed by a database server, cause the database server to do one or more of the following: create a new database structure, delete an existing database structure, and/or alter an existing database structure. Database structures that may be created, deleted, and/or altered may include structures that define database object types and structures that define database object instances. [0049] The “evolve” SQL statements, when executed by a database server, cause the database server to make database object types that are based on the pre-evolved XML schema conform to the structure indicated by the evolved XML schema. Thus, the database object types are evolved. Also, when a database server executes the “evolve” SQL statements, the “evolve” SQL statements cause the database server to make database object instances that are based on the pre-evolved database object types conform to the evolved database object types. Thus, the database object instances are evolved. [0050] For example, the schema evolver may generate, based on an evolved XML schema that incorporates a new XML element, an SQL statement that causes a database server to add a new column to a database table. The new column may have the same name as the name indicated by the attributes of the new XML element, and may be populated with default values based on the type indicated by the attributes of the new XML element. SQL statements that the schema evolver may generate may include actions such as “CREATE,” “ALTER,” “ADD,” “MODIFY,” and “DROP.” Such SQL statements may indicate whether the target of the SQL statement is a “TYPE,” a “TABLE,” etc. [0051] In block 208, the schema evolver generates one or more “rollback” SQL statements. The schema evolver may generate the “rollback” SQL statements as the schema evolver generates the “evolve” SQL statements. The Rollback” SQL statements, when executed by a database server, cause the database server to reverse the effects of the “evolve” SQL statements on the targets of the “evolve” SQL statements. [0052] In block 210, the database server executes the “evolve” SQL statements. As a result, database object types and database object instances may be created, deleted, or altered. If no error occurs, then the resulting database object types and database object instances conform to the evolved XML schema. [0053] While the database server executes the “evolve” SQL statements, it is determined, in block 212, whether an error has occurred with regard to the execution of the “evolve” SQL statements. If the “evolve” SQL statements execute entirely without an error, then control passes to block 214. Otherwise, control passes to block 216 as soon as the error occurs. [0054] If no error occurs, then, in block 214, the evolution is finished. However, if an error occurs during the execution of the “evolve” SQL statements, then, in block 216, the database server executes as many of the “rollback” SQL statements as are necessary to reverse the effects of the already executed “evolve” SQL statements on the targets of the “evolve” SQL statements. The schema evolver may also undo the changes made to the XML schema based on the changes the schema evolver tracked while evolving the XML schema. As a result, the XML schema and database structures based on the XML schema are rolled back to their pre-evolutionary state. Thus, the evolution is guaranteed to be an atomic operation. THE XDIFF SCHEMA [0055] As described above, a schema evolver may evolve an existing XML schema into an evolved XML schema based on an XML document that indicates changes to be made to the existing XML schema. The XML document may express the changes in terms of XML elements defined by an “xdiff XML schema of which the XML document is an instance document. [0056] The xdiff schema defines, in XML, primitive elements through which a user may express evolution commands. Such commands may express operations relative to “nodes.” As used herein, a “node” is some aspect of an XML structure such as an XML element. For example, one element of the xdiff schema may define the structure of a command to append a specified node to the end of a specified list of nodes. Another element of the xdiff schema may define the structure of a command to insert a specified node immediately before another specified node. Yet another element of the xdiff schema may define the structure of a command to delete a specified node and the child nodes of the specified node. [0057] An exemplary xdiff schema is shown below: [0058] In the above xdiff schema, three elements are defined: “append-node,” “insert-node-before,” and “delete-node.” The “append-node” element expresses syntax for indicating that the schema evolver should add, as the last child node of the node specified by the “parent-xpath” attribute, the node specified by the “content” element. The node specified by the “content” element is indicated to be of a node type specified by the “node-type” element [0059] For example, an XML document provided to the schema evolver might contain an element such as: Based on this, the schema evolver would add “Enumeration value=‘FL7>“ to the below XML schema, as shown after the addition: [0060] The “insert-node-before” element expresses syntax for indicating that the schema evolver should insert the node specified by the “content” element immediately before the node specified by the “xpath” attribute. Again, the node specified by the “content” element is indicated to be of a node type specified by the “node-type” element. [0061] For example, an XML document provided to the schema evolver might contain an element such as: Based on this, the schema evolver would insert ““ in the below XML schema, as shown after the insertion:

Documents:

648-CHENP-2006 AMENDED PAGES OF SPECIFICATION 13-12-2011.pdf

648-CHENP-2006 AMENDED CLAIMS 01-05-2012.pdf

648-CHENP-2006 AMENDED CLAIMS 13-12-2011.pdf

648-CHENP-2006 CORRESPONDENCE OTHERS 18-08-2011.pdf

648-CHENP-2006 CORRESPONDENCE OTHERS 27-05-2011.pdf

648-CHENP-2006 CORRESPONDENCE OTHERS 13-12-2011.pdf

648-CHENP-2006 EXAMINATION REPORT REPLY RECEIVED 01-05-2012.pdf

648-CHENP-2006 FORM-13 13-12-2011.pdf

648-CHENP-2006 FORM-3 13-12-2011.pdf

648-chenp-2006 form-3 16-08-2011.pdf

648-CHENP-2006 FORM-5 13-12-2011.pdf

648-CHENP-2006 POWER OF ATTORNEY 13-12-2011.pdf

648-chenp-2006 correspondence others 07-12-2010.pdf

648-chenp-2006 correspondence others 16-08-2011.pdf

648-chenp-2006 form-1 10-05-2010.pdf

648-chenp-2006 form-13 07-12-2010.pdf

648-CHENP-2006 FORM-13 10-05-2010.pdf

648-CHENP-2006 POWER OF ATTORNEY 10-05-2010.pdf

648-chenp-2006-abstract.pdf

648-chenp-2006-assignment.pdf

648-chenp-2006-claims.pdf

648-chenp-2006-correspondence-others.pdf

648-chenp-2006-description(complete).pdf

648-chenp-2006-drawings.pdf

648-chenp-2006-form 1.pdf

648-chenp-2006-form 3.pdf

648-chenp-2006-form 5.pdf

648-chenp-2006-pct.pdf