XML schema evolution

[0001] 1. Technical Field

[0002] The invention relates generally to XML schema evolution technique. More particularly, the invention relates to an apparatus and a method for providing schema manipulation operations and validating schema changes.

[0003] 2. Description of the Prior Art

[0004] XML (Extensible Markup Language), developed by the World Wide Web Consortium (W3C), is a system for organizing and tagging elements of a document. It allows designers to create their own customized tags, enabling the definition, transmission, validation, and interpretation of data between applications and between organizations. It is a flexible way to create common information formats and share both the format and the data on the World Wide Web, intranets, and other networks. For example, computer makers might agree on a standard way to describe information, such as processor speed, memory size, and so forth, about a computer product and then describe the product information format with XML. Such a standard way of describing data enables a user to send an intelligent agent to each computer maker's Web site, gather data, and then make a valid comparison. XML can be used by any individual or group of individuals or company that wants to share information in a consistent way.

[0005] XML elements and attributes can be identified and accessed with XPath expressions. XPath is a language that describes a way to locate and process items in XML documents by using an addressing syntax based on a path through the document's logical structure or hierarchy. This makes writing programming expressions easier than if each expression had to understand typical XML markup and its sequence in a document. XPath also allows the programmer to deal with the document at a higher level of abstraction. It uses the information abstraction defined in the XML Information Set.

[0006] XPath uses the concepts of node, i.e. the point from which the path address begins), the logical tree that is inherent in any XML document, and the concepts expressing logical relationships that are defined in the XML Information Set, such as ancestor, attribute, child, parent, and self. XPath includes a small set of expressions for specifying mathematics functions and the ability to be extended with other functions.

[0007] The XML language itself does not limit set of tags for element and attribute names. Due to lack of a definite set of element and attribute names and lack of structure definition, confusion may arise when two different party communicate via XML documents. This has lead to the provision of many schema definition languages, one of which is the XML Schema that specifies how to describe the elements in XML document formally. This description can be used to verify that each item of content in a document adheres to the description of the element in which the content is to be placed.

[0008] In general, a schema is an abstract representation of an object's characteristics and relationship to other objects. An XML schema represents the interrelationship between the attributes and elements of an XML object, for example, a document or a portion of a document. To create a schema for a document, its structure must be analyzed and each structural element must be defined. XML Schema has several advantages over earlier XML schema languages, such as Document Type Definition (DTD). For example, it is more direct: XML Schema, in contrast to the earlier languages, is written in XML, which means that it does not require intermediary processing by a parser. Other benefits include self-documentation, automatic schema creation, and the ability to be queried through XML Transformations (XSLT).

[0009] For an XML schema to endure over time it must be capable of evolving to reflect the changing information requirements. A set of operations, such as, Insert, Delete, Update, Query has been proposed for manipulating XML documents. However, no mechanisms have been defined for manipulating XML schemas.

[0010] To allow XML document to contain extended data, XML schemas could have various data types with <xsd:any> as its subcomponents. <xsd:any> are served as place holders for any extended data because an any type does not constrain its content in any way. An extremely extensive XML schema is illustrated as follows:

[0011]

	<xs:element name=“myData”>
	<xs:complexType><xs:sequence>
	<xs:any processContents=“skip” minOccurs=“0”
	maxOccurs=“unbounded”/>
	</xs:sequence></xs:complexType>
	</xs:element>

[0012] Although this approach does allow extended data to be contained in XML documents of the schema, it does not provide any control of the extended data.

[0013] What is desired is a technique for performing schema manipulation operations so that an XML schema can be evolved in a controlled, pragmatic way. Because there might be lots of XML documents, e.g. thousands under an existing XML Schema, XML Schema must evolve in such a way that ensures all existing XML documents remain valid under the new XML schema that results from such schema manipulations.

[0014] What is further desired is a technique to determine whether all XML documents are still valid after schema manipulation without individually examining these XML documents. It is time consuming to examine thousands XML documents. In certain applications, for example Web Services that use XML to represent user data logically in a distributed set of computers, it is substantially impossible to examine XML documents individually.

[0015] A technique to evolve XML schemas is disclosed. The technique involves methods of performing schema manipulation operations and validating the schema changes so that the current XML documents remain valid against the new schema. A method to compare two XML document sets, each containing all valid XML documents of one schema, is disclosed that avoids the need to validate all current XML documents with the new XML schema.

[0016] According to one aspect of the invention, a method for evolving a first XML schema to a second XML schema in an application involving a plurality XML documents which are valid against the first XML schema comprises the steps of: (1) performing a plurality of schema manipulation operations to generate the second XML schema; and (2) validating the plurality of schema manipulation operations so that all existing XML documents are still valid.

[0017] Another aspect of the invention provides a method for determining whether a first set of XML documents contains a second set of XML documents. The first set of XML documents is the set of all valid XML documents of a first XML schema and the second set of XML documents is the set of all valid XML documents of a second XML schema. This method comprises the steps of: (1) locating a first root element for the first XML schema and a second root node for the second schema; (2) constructing a first element set which contains elements that could be reached from the first root node and a second element set which contains elements that could be reached from the second root node; (3) returning false if the first element set does not contain the second element set; and (4) performing element comparison for each of the elements in the second element set with the corresponding elements in the first element set.

[0018] In yet another aspect of the invention, an apparatus for evolving XML schemas in an application handling XML documents comprises a schema manipulation means, and a schema validation means, wherein the schema manipulation means performs a plurality of schema manipulation operations to evolve a current XML schema into a new XML schema, and wherein the schema validation means validates the new XML schema to make sure all current XML documents are still valid against the new XML schema.

[0024] In the following detailed description of the invention, some specific details are set forth to provide a thorough understanding of the presently preferred embodiment of the invention. However, it will be apparent to those skilled in the art that the invention may be practiced in embodiments that do not use the specific details set forth herein. Well known methods, procedures, components, and circuitry have not been described in detail.

[0025] In one preferred embodiment of the invention, a method is disclosed for evolving a first XML schema to a second XML schema in an application involving a plurality XML documents which are valid against the first XML schema. The method comprises the following steps:

• • [0026] performing a plurality of schema manipulation operations to generate the second XML schema; and
  • [0027] validating the plurality of schema manipulation operations so that all existing XML documents are still valid.

[0028] FIG. 1 is a schematic diagram illustrating a list of schema manipulation operations 100. The schema manipulation operations, which may be invoked on the current XML schema 101 to obtain a new XML schema 102, include an insert schema operation 111, a replace schema operation 112, a delete schema operation 113, a compact schema operation 114, and an evolve schema 115.

[0029] The insert schema operation 111 inserts a schema segment into an XML schema.

[0030] The syntax for the insert schema operation is as the following:

• • [0031] InsertSchema <schema ID> <XPath to locate a component> <relative position> <new XML segment to be added>

[0032] The detail descriptions of parameters are listed in Table 1 below.

[0033]

TABLE 1
Parameters	Description	Example
schema ID	A unique string that	<schemaID>Address.xsd</schemaID>
	identifies a schema
XPath to	an XPath	<xpath>/element [@name=“address”]</xpath>
locate a	expression that
component	identify a node in
	an XML schema.
	Examples of such a
	node include
	<schema>,
	<element>,
	<complexType>,
	<attribute>, and
	<sequence> etc . . .
relative	The relative	<position>after</position>
position	position w.r.t. a
	selected XML
	schema node. It
	could take one of
	four values:
	before . . . as
	the
	immediately
	left sibling
	(before) the
	selected
	node
	after . . . as
	immediately
	right sibling
	(after) the
	selected
	node
	first_child . . .
	as the first
	child of the
	selected
	node
	last_child . . .
	as the last
	child of the
	selected
	child
new XML	One or several	<newSegment>
segment to	XML schema	<xs:complexType
be added	nodes	name=“simpleAddressType”>
		<xs:sequence>
		<xs:element name=“street”
		type=“xs:string” maxOccurs=“3”/>
		<xs:element name=“city”
		type=“xs:string”/>
		</xs:sequence>
		<xs:attribute name=“country”
		type=“xs:string”/>
		</xs:complexType>
		</newSegment>

[0034] This operation can also be represented in XML. The following is an XML sample which represents an insert schema operation:

[0035]

	<InsertSchema>
	<schemaID>Address.xsd</schemaID>
	<xpath>/element[@name=“address”]</xpath>
	<position>after</position>
	<newSegment>
	<xs:complexType name=“simpleAddressType”>
	<xs:sequence>
	<xs:element name=“street” type=
	“xs:string” maxOccurs=“3”/>
	<xs:element name=“city” type=
	“xs:string”/>
	</xs:sequence>
	<xs:attribute name=“country” type=
	“xs:string”/>
	</xs:complexType>
	</newSegment>
	</InsertSchema>

[0036] The replace schema operation 112 replaces a schema segment of an XML schema. The syntax for the replace schema operation is as the following:

• • [0037] ReplaceSchema <schema ID> <XPath to locate a component> <new XML segments used for replacement>

[0038] The detail descriptions of parameters are listed in Table 2.

[0039]

TABLE 2
Parameters	Description	Example
schema ID	A unique string	<schemaID>Address.xsd</schemaID>
	that identifies a
	schema
XPath to locate	an XPath	<xpath>/complexType [@name=“addressType”]</
a component	expression that	xpath>
	identify a node in
	an XML schema.
	Examples of
	such a node
	include
	<schema>,
	<element>,
	<complexType>,
	<attribute>, and
	<sequence>
	etc . . .
new XML	One or several	<newSegment>
segments used	XML schema	<xs:complexType name=“addressType”>
for replacement	nodes	<xs:complexContent>
		<xs:extension
		base=“simpleAddressType”>
		<xs:sequence>
		<xs:element name=“state”
		type=“xs:string”/>
		<xs:element name=“zipcode”
		type=“xs:string”/>
		</xs:sequence>
		</xs:extension>
		</xs:complexContent>
		</xs:complexType>
		</newSegment>

[0040] This operation can also be represented in XML. The following is an XML sample which represents a replace schema operation:

[0041]

	<ReplaceSchema>
	<schemaID>Address.xsd</schemaID>
	<xpath>/complexType[@name=“addressType”]</xpath>
	<newSegment>
	<xs:complexType name=“addressType”>
	<xs:complexContent>
	<xs:extension base=“simpleAddressType”>
	<xs:sequence>
	<xs:element name=“state” type=“xs:string”/>
	<xs:element name=“zipcode” type=“xs:string”/>
	</xs:sequence>
	</xs:extension>
	</xs:complexContent>
	</xs:complexType>
	</newSegment>
	</ReplaceSchema>

[0042] The delete schema operation 113 deletes a schema segment from an XML schema.

[0043] The syntax for the delete schema operation is as the following:

• • [0044] DeleteSchema <schema ID> <Xpath to locate a component>

[0045] The detail descriptions of parameters are listed in the following Table 3.

[0046]

TABLE 3
Parameters	Description	Example
schema ID	A unique string that	<schemaID>Address.xsd</schemaID>
	identifies a schema
XPath to	an XPath	<xpath>/element [@name=“address”]</xpath>
locate a	expression that
component	identify a node in an
	XML schema.
	Examples of such a
	node include
	<schema>,
	<element>,
	<complexType>,
	<attribute>, and
	<sequence> etc . . .

[0047] This operation can also be represented in XML. The following is an XML sample which represents a delete schema operation. The sample operation eliminates an element “country.”

[0048]

	<DeleteSchema>
	<schemaID>Address.xsd</schemaID>
	<xpath>/complexType/sequence/element[@name=
	“country”]/</xpath>
	</DeleteSchema>

[0049] The compact schema operation 114 makes an XML schema compact by eliminating unnecessary segments. The syntax for a compact schema operation is as the following:

• • [0050] CompactSchema <schema ID> <XPath to locate a component>

[0051] The detail descriptions of parameters are listed in the following Table 4.

[0052]

TABLE 4
Parameters	Description	Example
schema ID	A unique string that	<schemaID>Address.xsd</schemaID>
	identifies a schema
XPath to	an XPath	<xpath>/element [@name=“address”]</xpath>
locate a	expression that
component	identify a node in an
	XML schema.
	Examples of such a
	node include
	<schema>,
	<element>,
	<complexType>,
	<attribute>, and
	<sequence> etc . . .

[0053] This operation can also be represented in XML. The following is an XML sample which represents an insert schema operation. This operation sample makes the type definition of “addressType” more compact.

[0054]

<CompactSchema>
	<schemaID>Address.xsd</schemaID>
	<xpath>/complexType[@name=“addressType”]/sequence</xpath>
</CompactSchema>

[0055] The evolve schema 115 operation commits the schema changes since a previous version. The syntax for the evolve schema operation is as the following:

• • [0056] EvoloveSchema <schema ID> <new_version>

[0057] The detail descriptions of parameters are listed in the following Table 5.

[0058]

TABLE 5
Param-
eters	Description	Example
schema	A unique string that	<schemaID>Address.xsd</schemaID>
ID	identifies a schema
new	New version assigned	<newVersion>2.0</newVersion>
version	to the evolved schema

[0059] This operation can also be represented in XML. The following is an XML sample which represents an evolve schema operation:

[0060]

	<EvoloveSchema>
	<schemaID>Address.xsd</schemaID>
	<newVersion>2.0</newVersion>
	</EvoloveSchema>

[0061] When an evolve schema operation is performed, the result new schema is validated.

[0062] To validate a schema evolution from the current XML schema to new XML schema, a first set of all valid XML documents of the current XML schema is compared with a second set of all valid XML documents of the new XML schema. If the second set of XML documents contains the first set of XML documents, all current XML documents remain valid against the new XML schema, and the schema evolution is valid.

[0063] FIG. 2 is a flow diagram illustrating a method 200 for determining whether a first set of XML documents contains a second set of XML documents in another equally preferred embodiment of the invention. Here, the first set of XML documents is the set of all valid XML documents of a first XML schema and the second set of XML documents is the set of all valid XML documents of a second XML schema. The method 200 comprises the following steps:

[0064] Step 201: Locate a first root element (RT1) for the first XML schema and a second root node (RT2) for the second schema;

[0065] Step 201A: Remove all elements and attributes from the first XML schemas that are not reachable from the first root element RT1 and from the second XML schema that are not reachable from the second root element RT2;

[0066] Step 202: Construct a first total element list (EL1) in the first XML schema and a second total element list (EL2) in the second XML schema;

[0067] Step 203: Return false if the first element list (EL1) does not contain the second element list (EL2); and

[0068] Step 204: Perform detailed element comparison for each of the elements in the second element list (EL2) with the corresponding elements in the first element list (EL1).

[0069] FIG. 3 is a flow diagram illustrating the sub-steps of the element comparison step 204 of the method 200:

[0070] Step 301: Find a first type definition (T1) of a first element in the first XML schema and a second type definition (T2) of a second element in the second XML schema;

[0071] Step 302: Perform comparison of a first language set, L(T1), which represents all possible values covered by the first type definition and a second language set, L(T2), which represents all possible values covered by the second document type;

[0072] Note that data type definitions may need to be flattened to obtain these regular expressions. For example, the regular expression of the following “address” are “(street street? street? city state zipcode)”.

[0073]

<element name=“address” type=“USAddressType”>
<complexType name=“simpleAddressType”>
	<sequence>
	<element name=“street” type=“string” maxOccurs=“3”>
	<element name=“city” type=“string”>
	</sequence>
	<attribute name=“country” type=“string”>
</complexType>
<complexType name=“addressType”>
	<complexContent>
	<extension base=“USAddressType”>
	<sequence>
	<element name=“state” type=“xs:string”/>
	<element name=“zipcode” type=“xs:string”/>
	</sequence>
	<attribute name=“version” type= “integer”>
	</extension>
	</complexContent>
</complexType>

[0074] Step 302A: Return false if the first language set L(T1) does not contain the second language set L(T2);

[0075] Step 303: Construct a first attribute set (AT1) associated with the first element and a second attribute set (AT2) associated with the second element;

[0076] Note that data type definitions may need to be flattened to obtain these lists. For the above example, the attribute set for “address” is {“country”, “version”}.

[0077] Step 304A: Return false if the first attribute set (AT1) does not contain the second attribute set (AT2);

[0078] Step 304B: Return false if any attribute in the first attribute set (AT1) but not in the second attribute set (AT2) is required;

[0079] Step 305: Perform detailed attribute comparison for each of the attributes in the second attribute set (AT2) with the corresponding attributes in the first attribute set (AT1).

[0080] FIG. 4 is a flow diagram illustrating the sub-steps of the language set comparison step 302:

[0081] Step 401: Check if the first type definition T1 and the second type definition T2 are both complex data type;

[0082] Step 402: Construct a first regular expression EXP1 for the first type definition T1 and a second regular expression EXP2 for the second type definition T2 if both T1 and T2 are complex data types;

[0083] Step 403: Apply standard regular expression comparison algorithms to decide whether the language represented by EXP1 is equal to or larger than the language represented by EXP2;

[0084] Step 404: Check if the first type definition T1 and the second type definition T2 are both simple data type;

[0085] Step 405: Return false if the first type definition T1 and the second type definition T2 are not both simple data type; and

[0086] Step 406: Perform direct comparison for simple data types T1 and T2 to decide whether the language represented by T1 is equal to or larger than the language represented by T2.

[0087] FIG. 5 is a flow diagram illustrating the sub-steps of the attribute comparison step 305:

[0088] Step 501: Find a third data type (T3) for a first attribute and a fourth data type (T4) of same attribute in the second XML schema;

[0089] Step 502: Perform comparison of a third language set, L(T3), which represents all possible values covered by the third type definition and a fourth language set, L(T4), which represents all possible values covered by the fourth document type;

[0090] Step 503: Return false if the third language set L(T3) does not contain the fourth language set L(T4); and

[0091] Step 504: Return true if the third language set L(T3) contains the fourth language set L(T4).

[0092] Another aspect of the invention is a system for evolving XML schemas in an application handling XML documents. The system includes a first sub-system for schema manipulation and a second sub-system for schema validation. The first sub-system for schema manipulation performs a plurality of schema manipulation operations to evolve a current XML schema into a new XML schema. The second sub-system for schema validation validates the new XML schema to make sure all current XML documents are still valid against the new XML schema.

[0093] The schema manipulation operations can be any of the following:

• • [0094] a query schema operation that retrieves a segment of an XML schema;
  • [0095] an insert schema operation that inserts a segment to an XML schema;
  • [0096] a replace schema operation that replaces a schema segment of an XML schema;
  • [0097] a delete schema operation that deletes a schema segment of an XML schema;
  • [0098] a compact schema operation that eliminates unnecessary segments to make an XML schema compact; and
  • [0099] an evolve schema operation that commits pending schema changes.

[0100] The second sub-system for schema validation may further comprise a comparison module for determining whether a second set containing all valid XML documents of the second XML schema contains a first set containing all valid XML documents of the first XML schema.

[0101] In one typical implementation, the application is a Web service that maps data containing in XML documents into a relational database. The system for evolving XML schemas may further comprise a module used to provide gatekeeper control for better data and schema quality, and a module used to trigger underlying database storage change for handling extended data corresponding to the new XML schema.

[0102] Although the invention is described herein with reference to the preferred embodiment, one skilled in the art will readily appreciate that other applications may be substituted for those set forth herein without departing from the spirit and scope of the present invention.

[0103] Accordingly, the invention should only be limited by the Claims included below.