Abstract:
In one embodiment, the invention may include receiving an XML schema and document with first, second, third, and fourth nodes. The second and third nodes may descend from the first node. The fourth node may descend from the second node. The third and fourth nodes may be simultaneously validated.

Description:
BACKGROUND 
     One method for validating extensible markup language (XML) documents against an XML schema includes breadth-first validation. Breadth-first validation may include a traversal of an XML schema using a finite state machine (FSM). A FSM may be thought of as a model of behavior composed of a finite number of states, transitions between those states, and actions. Regarding breadth-first validation, there may be a parent node with child nodes A and B. Child node A may have child nodes C and D. In breadth-first validation, child nodes A and B of a parsed XML document must both be validated before child nodes C and D (i.e., descendants) are traversed using a FSM. In other words, the document must be verified to conform to a certain standard (e.g., XML schema). In this scenario, each top-level compositor represents a FSM, and new FSMs are instantiated upon traversal of child nodes (e.g., child nodes A and B). Unfortunately, this non-parallel, breadth-first methodology fails to properly leverage the core capacity available with parallel processing in multicore processors and/or multithread software processing. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The accompanying drawings, incorporated in and constituting a part of this specification, illustrate one or more implementations consistent with the principles of the invention and, together with the description of the invention, explain such implementations. The drawings are not necessarily to scale, the emphasis instead being placed upon illustrating the principles of the invention. In the drawings: 
         FIG. 1  is a state diagram for a finite state machine for a breadth first validation. 
         FIG. 2  is a state diagram concerning one embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     The following description refers to the accompanying drawings. Among the various drawings the same reference numbers may be used to identify the same or similar elements. While the following description provides a thorough understanding of the various aspects of the claimed invention by setting forth specific details such as particular structures, architectures, interfaces, and techniques, such details are provided for purposes of explanation and should not be viewed as limiting. Moreover, those of skill in the art will, in light of the present disclosure, appreciate that various aspects of the invention claimed may be practiced in other examples or implementations that depart from these specific details. At certain junctures in the following disclosure descriptions of well known devices, circuits, and methods have been omitted to avoid clouding the description of the present invention with unnecessary detail. 
     As will be explained more fully below, after an XML schema has been received and an XML document parsed and available as a tree structure, each node may have access to its immediate (i.e., direct descendent) children and can easily traverse a single compositor FSM. A compositor may describe the composition of a type&#39;s content. An XML schema may define multiple compositors that can be used in complex type definitions. Compositors may contain particles, which may include things like other compositors, element declarations, wildcards, and model groups. Once a single node has been locally validated (i.e., one node among many nodes is individually validated), the target schema type for each child node may be available, and new FSM validation traversals can be instantiated. For example, an XML Schema is defined in the following table. 
     
       
         
               
             
           
               
                 TABLE 1 
               
               
                   
               
             
             
               
                 &lt;xsd:schema xmlns:xsd=“http://www.w3.org/2001/XMLSchema”&gt; 
               
               
                  &lt;xsd:element name=“root”&gt; 
               
               
                   &lt;xsd:complexType&gt; 
               
               
                    &lt;xsd:sequence&gt; 
               
               
                     &lt;xsd:element name=“a”&gt; 
               
               
                      &lt;xsd:complexType&gt; 
               
               
                       &lt;xsd:sequence&gt; 
               
               
                         &lt;xsd:element name=“aChild” type=“xsd:string”/&gt; 
               
               
                       &lt;/xsd:sequence&gt; 
               
               
                      &lt;/xsd:complexType&gt; 
               
               
                     &lt;/xsd:element&gt; 
               
               
                     &lt;xsd:element name=“b”&gt; 
               
               
                      &lt;xsd:complexType&gt; 
               
               
                       &lt;xsd:choice&gt; 
               
               
                        &lt;xsd:element name=“bChoice1” type=“xsd:integer”/&gt; 
               
               
                        &lt;xsd:element name=“bChoice2” type=“xsd:integer”/&gt; 
               
               
                       &lt;/xsd:choice&gt; 
               
               
                      &lt;/xsd:complexType&gt; 
               
               
                     &lt;/xsd:element&gt; 
               
               
                    &lt;/xsd:sequence&gt; 
               
               
                   &lt;/xsd:complexType&gt; 
               
               
                 &lt;/xsd:element&gt; 
               
               
                 &lt;/xsd:schema&gt; 
               
               
                   
               
             
          
         
       
     
     The pseudocode in the above table may build a self contained FSM for the total complex type, along with a FSM for each new complex type. Each FSM may be linked into a host FSM at the state where validation for the child FSM becomes legal. In the above pseudocode, the complex type FSM associated with element “a” may be linked into the complex type FSM associated with “root” at the state immediately following a transition on element “a”. 
     Through FSM chaining, a single master FSM may consist of smaller local FSMs, each of which may contain a start state and one or more accept states. The master FSM for the XML schema in the above table may be seen in  FIG. 1 , with machine instantiations shown as thicker arrows. The XML Schema has been translated into a FSM, where each complex element node links into a child FSM. Node  105  indicates a start state (represented by a double-ring non-bolded symbol). Using the above table, node  105  assumes the root element has been located. Consequently, validity of a structure with child node element a followed by child node element b is now determined. Node  110  represents an intermediate state after child node element a has been located. Node  115  represents an accepted state (represented by a double-ring bolded symbol) and that child node element b has been located. Node  120  represents a start state. Node  125  is an accepted state and represents that child node element aChild has been located and validated. Node  130  represents a start state. Node  135  represents an accepted state and that child node element bChoice 1  has been located and validated. Node  140  represents an accepted state and that child node element bChoice 2  has been located and validated. Using a traditional breadth-first validation, the nodes would be validated in the following sequence:  105 ,  110 ,  115 ,  120 ,  125 ,  130 , and then  135  or  140 . 
     In contrast in the traditional breadth-first analysis described above, “eager” breadth-first validation may take place concurrently with respect to any other breadth-first FSM validation. Therefore, any node being eagerly validated may validate each of its children eagerly. In other words, eager validation allows for parallel processing of XML schema validation. 
       FIG. 2  is a depiction of one embodiment of the invention. The pipe-lined result of eager breadth-first validation is illustrated using sequential time slices time slices  145 ,  150 ,  155 ,  160 . There may or may not be intervening time slices among time slices  145 ,  150 ,  155 ,  160 . As a state is entered, any FSM associated with that target node can be instantiated in parallel. More specifically, node  105  indicates a start state in time slice  145 . Again, using Table 1, node  105  assumes the root element has been located. In time slice  150 , node  110  again represents an intermediate state after child node element A (which descends from a parent node) has been located. However, still in time slice  150 , node  120  represents a start state. In time slice  155 , nodes  115 ,  125  and  130  are addressed in parallel. In other words, child node element B (which descends from the parent node) is validated concurrently (i.e., eagerly) with child node element aChild (i.e., a grandchild node that descends from child node element A). Node  130  again represents a start state. In time slice  160 , node  135  again represents an accepted state and that child node element bChoice 1  has been located and validated. Furthermore, node  140  represents an accepted state and that child node element bChoice 2  has been located and validated. Thus, taking the XML Schema found in Table 1, a child state machine may validate against the XML Schema concerning the content of element “a” (e.g., &lt;xsd:element name=“aChild” type=“xsd:string”/&gt;) in parallel to another child state machine validating against the XML Schema concerning, for example, the sibling of element “a” such as element “b” (e.g., &lt;xsd:element name=“b” type=“ . . . ”). Furthermore, concurrent or parallel validation (i.e., eager validation) does not necessarily require that two validations begin and end simultaneously, although that is possible and included within the scope of the invention. 
     Thus, at each intermediate state in the FSM, the child element being processed can be “eagerly” validated against the associated follow-up FSM. This is legal because of the deterministic nature of XML Schema, as defined by Unique Particle Attribution in the W3C XML Schema specification. With no look-ahead requirement, once a state is entered, that state may become part of the master traversal, and no back-tracking may be necessary. 
     Accordingly, eager breadth-first validation may effectively support parallel operations. In one embodiment of the invention, such parallel operations may be conducted in a software multithreading environment. In one embodiment of the invention, such parallel operations may be conducted using a set of independent, interconnected processing elements (e.g., multicore processor). As a result, eager breadth-first validation may allow for job latency to scale downward as processing element count increases, thereby increasing utilization and throughput, even in workloads with a small number of tasks. This may allow higher core utilization looking forward, where intra-document parallelism may be a requirement. In one embodiment of the invention, any node eligible for validation can be processed on any available computing resource, such as a processor core. Through deterministic processing of the state machine, and the node-availability present in DOM models, a node may become eligible for validation one computation time slice after both the node&#39;s previous sibling and the node&#39;s parent have been validated. As the breadth-first walk proceeds, opportunities for parallelism increase as no structural limitations derived from the shape of the document tree apply. For example, if a parent node has a childA node, a grandchildA node descending from childA, a childB node, and a grandchildB node descending from childB, a processor core may process childA and grandchildB while another processor core processes childB and grandchildA. 
     Embodiments may be implemented in code that can be executed in many different system types. For example, embodiments may be implemented in computer systems such as server computers, personal computers, mobile devices such as cellular telephones and so forth. In such processor-based systems, an algorithm in accordance with an embodiment may be performed in a general-purpose processor such as a microprocessor, a graphics processing unit (GPU) or other such processing unit. 
     Embodiments may be implemented in code and may be stored on a storage medium having stored thereon instructions which can be used to program a system to perform the instructions. The storage medium may include, but is not limited to, any type of disk including floppy disks, optical disks, compact disk read-only memories (CD-ROMs), compact disk rewritables (CD-RWs), and magneto-optical disks, semiconductor devices such as read-only memories (ROMs), random access memories (RAMs) such as dynamic random access memories (DRAMs), static random access memories (SRAMs), erasable programmable read-only memories (EPROMs), flash memories, electrically erasable programmable read-only memories (EEPROMs), magnetic or optical cards, or any other type of media suitable for storing electronic instructions. 
     While the present invention has been described with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of this present invention.