Abstract:
A programming technique is disclosed for linking (or “mapping”) a query on the tree structure of an extensible markup language (XML) based computer-coded file to the “start” and “end” positions of the corresponding XML-coded data contained within the file, when the coded data has variable length in order to enhance the efficiency of querying an XML document (or other type of file).

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates generally to querying of an extensible markup language (XML) based data. 
       BACKGROUND OF THE INVENTION 
       [0002]    A programming technique is disclosed for linking (or “mapping”) a query expression on the tree structure of an extensible markup language (XML) based computer-coded data to the “start” and “end” positions of the corresponding XML-coded data contained when the coded data has variable length, in order to enhance the efficiency of querying an XML document (or other type of data based on tree structure). 
         [0003]    The technique is applicable to XML-coded data that does not contain “redundant whitespaces” (i.e., no new character(s) between XML “tags” and otherwise limiting non-character entries to the minimum number necessary for the XML expression to be well-formed) or otherwise utilizes appropriate correction factors to account for “whitespaces”. 
         [0004]    Previous techniques of querying an XML-coded file (involving use of programs such as XQuery and XPath) require the entire XML data file to be examined (or “read”) in order to perform a search for the desired data, resulting in more “file read” operations and potentially causing “memory overload” for the storage locations containing XML data files. In contrast, use of the present invention does not require all XML-coded data residing in a file to be loaded into memory for performance of the query search, thus providing memory use efficiency (and advantages over conventional methods). 
       SUMMARY OF THE INVENTION 
       [0005]    In accordance with at least one presently preferred embodiment of the present invention, there is broadly contemplated herein a programming technique to link (or “map”) a query expression on the tree structure of an extensible markup language (XML) based computer-coded data to the “start” and “end” positions of the corresponding XML-coded data, when the coded data has variable length. The “start” and “end” positions of the XML data can be defined by “byte positions” in which the variable code length can be specified in terms of the number of binary digits (separated into groups of eight digits, i.e., “bytes”) that it contains. Alternately, these “start” and “end” positions can be defined in terms of “character positions” in which the variable code length can be specified by the number of text characters contained in the XML-coded data. 
         [0006]    The programming technique proposed by this invention requires a single examination (or “parsing”) of the XML-coded file to determine the exact (current) lengths of data element and attribute names and values, along with the “file header length” containing “metadata” providing identifying (and other) information necessary for the data file to be processed. These lengths can be defined in terms of either “character length” or “byte length” depending on the type of XML query structure position mapping (i.e., character-based or byte-based) being used. The length of each data element or attribute can be determined by “parsing” the XML data. 
         [0007]    In summary, one aspect of the invention provides a computer system comprised of a computer processor configured for executing program instructions stored in computer memory and arranged for linking a query on the tree structure of an extensible markup language (XML) computer file to the start and end positions of coded data element(s), the system comprising: an arrangement for defining the start and end positions of a queried data element by byte positions where code length is specified by a defined number of binary digits; or an arrangement for defining the start and end positions of a queried data element by character positions where code length is specified by a defined number of text characters; wherein the coded data has variable length. 
         [0008]    Another aspect of the invention provides a method of linking a query on the tree structure of an extensible markup language (XML) computer data to the start and end positions of coded data element(s), the method comprising the steps of: defining the start and end positions of a queried data element by byte positions where code length is specified by a defined number of binary digits; or defining the start and end positions of a queried data element by character positions where code length is specified by a defined number of text characters; wherein the coded data has variable length. 
         [0009]    Furthermore, an additional aspect of the invention provides a computer program storage device readable by a computer processor machine, tangibly embodying a program of instructions executable by the machine to perform a method of linking a query on the tree structure of an extensible markup language (XML) computer file to the start and end positions of coded data element(s), the method comprising the steps of: defining the start and end positions of a queried data element by byte positions where code length is specified by a defined number of binary digits; or defining the start and end positions of a queried data element by character positions where code length is specified by a defined number of text characters; wherein the coded data has variable length. 
         [0010]    For a better understanding of the present invention, together with other and further features and advantages thereof, reference is made to the following description, taken in conjunction with the accompanying drawings, and the scope of the invention will be pointed out in the appended claims. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0011]      FIG. 1  schematically illustrates a computer system with which a preferred embodiment of the present invention can be used. 
           [0012]      FIG. 2  illustrates a code structure used for a formatted XML data file with which a preferred embodiment of the present invention can be used. 
           [0013]      FIG. 3A-3B  illustrates a formatted XML data file with which a preferred embodiment of the present invention can be used. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0014]    It will be readily understood that the components of the present invention, as generally described and illustrated in the Figures herein, may be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the apparatus, system, and method of the present invention, as represented in  FIGS. 1-3B , is not intended to limit the scope of the invention, as claimed, but is merely representative of selected embodiments of the invention. 
         [0015]    Reference throughout this specification to “one embodiment” or “an embodiment” (or the like) means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, appearances of the phrases “in one embodiment” or “in an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. 
         [0016]    Furthermore, the described features, structures, or characteristics may be combined in any suitable manner in one or more embodiments. In the following description, numerous specific details are provided, such as examples of programming, software modules, user selections, network transactions, database queries, database structures, hardware modules, hardware circuits, hardware chips, etc., to provide a thorough understanding of embodiments of the invention. One skilled in the relevant art will recognize, however, that the invention can be practiced without one or more of the specific details, or with other methods, components, materials, etc. In other instances, well-known structures, materials, or operations are not shown or described in detail to avoid obscuring aspects of the invention. 
         [0017]    The illustrated embodiments of the invention will be best understood by reference to the drawings, wherein like parts are designated by like numerals or other labels throughout. The following description is intended only by way of example, and simply illustrates certain selected embodiments of devices, systems, and processes that are consistent with the invention as claimed herein. 
         [0018]    Referring now to  FIG. 1 , there is depicted a block diagram of an illustrative embodiment of a computer system  100 . The illustrative embodiment depicted in  FIG. 1  may be a notebook computer system, such as one of the ThinkPad® series of personal computers previously sold by the International Business Machines Corporation of Armonk, N.Y., and now sold by Lenovo (US) Inc. of Morrisville, N.C.; however, as will become apparent from the following description, the present invention is applicable to any data processing system. Notebook computers, as may be generally referred to or understood herein, may also alternatively be referred to as “notebooks”, “laptops”, “laptop computers” or “mobile computers”. 
         [0019]    As shown in  FIG. 1 , computer system  100  includes at least one system processor  42 , which is coupled to a Read-Only Memory (ROM)  40  and a system memory  46  by a processor bus  44 . System processor  42 , which may comprise one of the AMD™ line of processors produced by AMD Corporation or a processor produced by Intel Corporation, is a general-purpose processor that executes boot code  41  stored within ROM  40  at power-on and thereafter processes data under the control of operating system and application software stored in system memory  46 . System processor  42  is coupled via processor bus  44  and host bridge  48  to Peripheral Component Interconnect (PCI) local bus  50 . 
         [0020]    PCI local bus  50  supports the attachment of a number of devices, including adapters and bridges. Among these devices is network adapter  66 , which interfaces computer system  100  to a local area network (LAN), and graphics adapter  68 , which interfaces computer system  100  to display  69 . Communication on PCI local bus  50  is governed by local PCI controller  52 , which is in turn coupled to non-volatile random access memory (NVRAM)  56  via memory bus  54 . Local PCI controller  52  can be coupled to additional buses and devices via a second host bridge  60 . 
         [0021]    Computer system  100  further includes Industry Standard Architecture (ISA) bus  62 , which is coupled to PCI local bus  50  by ISA bridge  64 . Coupled to ISA bus  62  is an input/output (I/O) controller  70 , which controls communication between computer system  100  and attached peripheral devices such as a keyboard and mouse. In addition, I/O controller  70  supports external communication by computer system  100  via serial and parallel ports, including communication over a wide area network (WAN) such as the Internet. A disk controller  72  is in communication with a disk drive  200  for accessing external memory. Of course, it should be appreciated that the system  100  may be built with different chip sets and a different bus structure, as well as with any other suitable substitute components, while providing comparable or analogous functions to those discussed above. 
         [0022]    The following unformatted XML data file is used as an example to illustrate the XML structure position mapping implemented by the invention: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 &lt;School&gt; 
               
               
                   
                  &lt;Student id=“S001”&gt; 
               
               
                   
                   &lt;Name&gt;Peter Blazer&lt;/Name&gt; 
               
               
                   
                   &lt;Address&gt; 
               
               
                   
                    &lt;HouseNumber&gt;12/3&lt;/HouseNumber&gt; 
               
               
                   
                    &lt;Street&gt;Green Avenue&lt;/Street&gt; 
               
               
                   
                    &lt;PostalCode&gt;120057&lt;/PostalCode&gt; 
               
               
                   
                   &lt;/Address&gt; 
               
               
                   
                   &lt;GPA&gt;6.8&lt;/GPA&gt; 
               
               
                   
                  &lt;/Student&gt; 
               
               
                   
                  &lt;Teacher id=“T001” dept=“D001”&gt; 
               
               
                   
                   &lt;Name&gt;Tarun Paul&lt;/Teacher&gt; 
               
               
                   
                   &lt;Address&gt; 
               
               
                   
                    &lt;HouseNumber&gt;22/5&lt;/HouseNumber&gt; 
               
               
                   
                    &lt;Street&gt;LakeView Road&lt;/Street&gt; 
               
               
                   
                    &lt;PostalCode&gt;320066&lt;/PostalCode&gt; 
               
               
                   
                   &lt;/Address&gt; 
               
               
                   
                  &lt;/Teacher&gt; 
               
               
                   
                 &lt;/School&gt; 
               
               
                   
                   
               
             
          
         
       
     
         [0023]    The (above) example unformatted XML data file can be encoded in the formatted manner shown in  FIG. 3A-3B  to implement XML structure position mapping using “byte positions” (such that a single text character is defined by XML code having a length of eight binary digits or a single byte) (as with ASCII coded characters) thereby allowing the same code length computations to also be used for “character position” queries. (Certain coding adjustments are required for calculation of “byte positions” when one text character encodes to more than one byte as explained below.) Using this technique, the formatted XML data file does not contain “newline characters” or “beautifying spaces” as with the unformatted file.  FIG. 3A-3B  shows the starting and ending positions of “node names” (and/or “attribute values”) with the “node names” being shown in &lt;angle brackets&gt; for clarity in computing byte (or character) starting positions which are not contained within the “node names”, and with “attribute values” being shown within “quotes” for clarity in computing starting positions which are not part of the “attribute values”.  FIG. 3A-3B  shows “metadata” consisting of the lengths of data element and attribute names and values linked (or “mapped”) to each “node ID” as determined using a parser program (such as the SAX parser which examines XML data in “depth-first” order). 
         [0024]      FIG. 2  shows the tree structure of the XML data file. 
         [0025]    The type of node (referenced in  FIG. 2  and Column  2  of  FIG. 3A-3B ) can be either of the following: 
         [0026]    1. Element Name 
         [0027]    2. Element Value 
         [0028]    3. Attribute 
         [0029]    The following computational steps are taken to determine the starting position of a node in the structure of  FIG. 2  when representing the entries in the formatted XML data file of  FIG. 3A-3B  (nodes are in depth-first order): 
         [0000]      starting position of an Element Name=sum EN +num EN* 2+sum EV +sum AN +sum AV +num AN* 4+sum LD +num LD* 3+2 
         [0000]      starting position of an Element Value=sum EN +num EN* 2+sum EV +sum AN +sum AV +num AN* 4+sum LD +num LD* 3+1 
         [0000]      starting position of an Attribute Name=sum EN +num EN* 2+sum EV +sum AN +sum AV +num AN* 4+sum LD +num LD* 3+1 
         [0000]      starting position of an Attribute Value=Starting position of an Attribute Name+length AN+ 2 
         [0000]      ending position of node=starting position of node+length of node−1 
         [0000]    where: 
         [0030]    sumEN=sum of lengths of Element Names before computed node starting position 
         [0031]    sumEV=sum of lengths of Element Values before computed node starting position 
         [0032]    sumAN=sum of lengths of Attribute Names before computed node starting position 
         [0033]    sumAV=sum of lengths of Attribute Values before computed node starting position 
         [0034]    sumLD=sum of lengths of Level Decreases before computed node start position 
         [0035]    numEN=number of Element Nodes before computed node starting position 
         [0036]    numAN=number of Attributes before computed node starting position 
         [0037]    numLD=number of Level Decreases before computed node starting position 
         [0038]    The above expressions are given with the assumption that one text character is encoded using one data byte (such as with UTF-8). The adjustments for other encodings are as follows:
       numEN*2 where the “2” in the above expression represents the characters &lt;, &gt; or &lt; or a single space (refer to  FIG. 3A-3B ) such that “2” may change in the above expression depending on the number of bytes taken to encode these characters   numAN*4 where the “4” in the above expression represents the characters=, ‘single’ or “double” start quote, ‘single’ or “double” end quote, &gt; such that “4” may change in the above expression depending on the number of bytes taken to encode these characters   numLD*3 where the “3” in the above expression represents the characters &lt;,/, &gt; such that “3” may change in the above expression depending on the number of bytes taken to encode these characters   The trailing “+2” in the starting position of an Element Name expression represents the character “&lt;”+1 such that if n bytes are used to encode “&lt;” then +2 should be changed to n+1   The trailing +2 in the starting position of an Attribute Value expression represents the characters=and ‘single’ or “double” quotes such that if n bytes are used to represent the characters mentioned above then +2 should be changed to +n       
 
         [0044]    A fragment has a “root node” which is equivalent to its “fragment ID” so the starting position of the fragment is the starting position of its “root node” as computed in the same way as described above. 
         [0000]      ending position of fragment=ending position of last node in fragment+sum LD +num LD* 3 
         [0000]    where 
         [0045]    sumLD=Sum of level decreases between last node of the fragment and next node 
         [0046]    numLD=Number of level decreases between last node of the fragment and next node 
         [0047]    If the last node of the fragment is also the last node of the tree, the next node is taken as the root node (whose level is 1) and as mentioned previously adjustment for encoding needs to be applied for this expression. For example, the ending position of fragment with node ID  6  (depth-first) is computed by considering the last node of the fragment (which is  12 ) (see  FIG. 2 ). 
       Example Computations of Starting Positions of Some Nodes 
       [0048]    Starting position of node  10  (which is an Element Value):
 
Here sumEN=sum of the first part (before the + sign) of column ( 5 ) for Element Names up to node  9 . Therefore sumEN=6+7+4+7+11+6=41
 
numEN=number of Element Names up to node  9 =6 (nodes  1 / 2 / 4 / 6 / 7 / 9 )
 
sumEV=sum of the first part (before the + sign) of column ( 5 ) for Element Values up to node  9 . Therefore sumEV=12+4=16
 
sumAN=sum of the first part (before the + sign) of column ( 5 ) for Attribute Names up to node  9 . Therefore sumAN=2
 
sumAV=sum of the first part (before the + sign) of column ( 5 ) for Attribute Values up to node  9 . Therefore sumAV=4
 
numAN=number of Attribute Names up to node  9 =1 (node  3 )
 
sumLD=sum of the first part (before the + sign) of column ( 5 ) for Level Decreases up to node  9 . Therefore sumLD=4+11=15
 
numLD=number of Level Decreases up to node  9 =2 (between nodes  5 / 6  and nodes  8 / 9 ).
 
Starting position of node  10 =sumEN+numEN*2+sumEV+sumAN+sumAV+numAN*4+sumLD+numLD*3+1=41+6*2+16+2+4+1*4+15+2*3+1=101
 
Ending Position of node  10 =Starting Position of node  10 +length of node  10 +1=101+12−1=112
 
         [0049]    If the header length of the XML file is h bytes (i.e. the body of the file starts immediately after the header length without space) then the (actual) starting position of node  10 =h+101 and the (actual) ending position of node  10 =h+112. From the starting and ending positions the value of node  10  is directly read from the XML data (for the example in  FIGS. 2 &amp; 3  it is Green Avenue). 
         [0000]    Starting position of node  6  (which is an Element Name)=17+3*2+12+2+4+1*4+4+1*3+2=54
 
Starting position of node  17  (which is an Attribute Name)=61+9*2+37+4+8+2*4+48+7*3+1=206
 
Starting position (of value) of node  17 =Starting position of node  17 +length of Attribute Name of node  17 +2=206+4+2=212
 
Ending Position of fragment  6  (depth-first)=Ending Position of node  12  (depth-first)+sumLD+numLD*3
 
Starting Position of node  12  (depth-first node ID):
 
sumEN=6+7+4+7+11+6+10=51
 
numEN=7
 
sumEV=12+4+12=28
 
sumAN=2
 
sumAV=4
 
numAN=1
 
sumLD=4+11+6=21
 
numLD=3
 
Starting Position of node  12 =sumEN+numEN*2+sumEV+sumAN+sumAV+numAN*4+sumLD+numLD*3+1=51+7*2+28+2+4+1*4+21+3*3+1=134
 
Ending Position of node  12 =Starting Position+length of node−1=134+6−1=139
 
Level of node  12 =5
 
Level of node  13 =3
 
Number of level decrease (numLD)=5−3=2
 
Sum of level decrease (sumLD)=10+7=17
 
sumLD+numLD*3=17+2*3=23
 
Ending Position of fragment  6  (depth-first)=Ending Position of node  12 +sumLD+numLD*3=139+17+2*3=162
 
         [0050]    Input of node IDs is not required if proper tooling is available and an XML template file is used. A node can be graphically selected and the “tooling program” can generate the corresponding node ID along with the code of the XML file. Retrieval of a fragment is similar to retrieval of a node where tooling is used to generate the fragment ID of a fragment. An “update” operation is similar to a “retrieve” operation where the starting and ending positions are determined and the new value is replaced between the starting and ending positions (inclusive). 
         [0051]    It is to be understood that the present invention, in accordance with at least one presently preferred embodiment, includes elements that may be implemented on at least one general-purpose computer running suitable software programs. These may also be implemented on at least one Integrated Circuit or part of at least one Integrated Circuit. Thus, it is to be understood that the invention may be implemented in hardware, software, or a combination of both. 
         [0052]    If not otherwise stated herein, it is to be assumed that all patents, patent applications, patent publications and other publications (including web-based publications) mentioned and cited herein are hereby fully incorporated by reference herein as if set forth in their entirety herein. 
         [0053]    Although illustrative embodiments of the present invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various other changes and modifications may be affected therein by one skilled in the art without departing from the scope or spirit of the invention.