System and method of xml query processing

Abstract

A method of processing queries, e.g., XPath expressions, related to an XML document includes generating a plurality of tokens based on the contents of the XML document. At least one query expression is compiled to a first plurality of query nodes defining a tree. A plurality of lookup tables may be configured to relate each of the first plurality of query nodes by a symbol. Each token is processed by looking up the query nodes indexed by a symbol matching the token in one of the plurality of lookup tables, marking each of the related query nodes, and indicating a match if each of the first plurality of query nodes of the at least one query expression is marked. A system for performing the method includes a tokenizer, an expression compiler, and an engine module.

1 . A method of checking whether an XML document is well-formed, the method comprising:
 receiving contents of the XML document;   generating a plurality of tokens based on the contents of the XML document;   determining an element depth of each of the plurality of tokens;   calculating a maximum depth of the XML document based on the depths of each of the plurality of tokens; and   rejecting the XML document if the maximum depth exceeds a predetermined depth.   
   
   
       2 . The method of  claim 1 , wherein determining an element depth of each of the tokens comprises determining the level of nesting of an XML element associated with each of the tokens. 
   
   
       3 . The method of  claim 1 , wherein determining the level of nesting of an XML element associated with each of the tokens comprises identifying a tree structure of elements defined by the XML document and wherein the level of nesting is determined based on the depth of an element formed by the token within the tree structure. 
   
   
       4 . The method of  claim 1 , further comprising determining whether the XML document is lexicographically correct in terms of syntactic elements and selectively rejecting the XML document based on the determining. 
   
   
       5 . The method of  claim 1 , further comprising determining whether the XML document is well-formed based on an XML specification and rejecting the XML document based on the determining. 
   
   
       6 . The method of  claim 1 , further comprising determining whether at least one of the tokens is declared in an enclosing namespace and selectively rejecting the XML document based on the determining. 
   
   
       7 . The method of  claim 1 , wherein the XML document is associated with a received electronic message and wherein rejecting the XML document comprises terminating processing of the message. 
   
   
       8 . A system for processing an XML document, the system comprising:
 a tokenizer configured to:
 generate a plurality of tokens based on the contents of the XML document; 
 determine an element depth of each of the plurality of tokens; and 
 calculate a maximum depth of the XML document based on the depths of each of the plurality of tokens; and 
   a processor configured to:
 reject the XML document if the maximum depth exceeds a predetermined depth. 
   
   
   
       9 . The system of  claim 8 , wherein to determine an element depth of each of the tokens, the tokenizer is configured to determine the level of nesting of an XML element associated with each of the tokens. 
   
   
       10 . The system of  claim 9 , wherein to determine the level of nesting of an XML element associated with each of the tokens, the tokenizer is configured to identify a tree structure of elements defined by the XML document and wherein the level of nesting is determined based on the depth of an element formed by the token within the tree structure. 
   
   
       11 . The system of  claim 8 , wherein the processor is further configured to determine whether the XML document is lexicographically correct in terms of syntactic elements and selectively reject the XML document based on the determination. 
   
   
       12 . The system of  claim 8 , wherein the processor is further configured to determine whether the XML document is well-formed based on an XML specification and selectively reject the XML document based on the determination. 
   
   
       13 . The system of  claim 8 , wherein the processor is further configured to determine whether at least one of the tokens is declared in an enclosing namespace and selectively reject the XML document based on the determination. 
   
   
       14 . The system of  claim 8 , wherein the system comprises one or more of an application specific integrated circuit, a field programmable gate array, and a network interface card. 
   
   
       15 . A system for processing an XML document, the system comprising:
 means for generating a plurality of tokens based on the contents of the XML document;   means for determining an element depth of each of the plurality of tokens;   means for calculating a maximum depth of the XML document based on the depths of each of the plurality of tokens; and   means for rejecting the XML document if the maximum depth exceeds a predetermined depth.   
   
   
       16 . The system of  claim 15 , wherein said means for determining an element depth of each of the tokens comprises means for determining the level of nesting of an XML element associated with each of the tokens. 
   
   
       17 . The system of  claim 16 , wherein said means for determining the level of nesting of an XML element associated with each of the tokens comprises means for identifying a tree structure of elements defined by the XML document and wherein the level of nesting is determined based on the depth of an element formed by the token within the tree structure. 
   
   
       18 . The system of  claim 15 , further comprising means for determining whether the XML document is well-formed based on an XML specification and selectively rejecting the XML document based on the determination. 
   
   
       19 . The system of  claim 15 , further comprising means for determining whether at least one of the tokens is declared in an enclosing namespace and selectively rejecting the XML document based on the determination. 
   
   
       20 . The system of  claim 15 , wherein the said means for generating, determining, calculating, and rejecting are implemented as one or more of an application specific integrated circuit, a field programmable gate array, and a network interface card.