Efficient traversals over hierarchical data and indexing semistructured data

Abstract

A method for encoding hierarchical data stored in an index, partitioned into blocks, over keys representing the data. For every key K representing a record R in the index, the key of the children records of record R are prefixed with K. The method includes traversing to a first R record represented in the index, traversing from the record R to the next sequential R such that the path in the index from the position representing R to the position representing the next sequential R does not include information relating to the children of R. Next, repeating the latter operation for 0 or more R records, and for any 0 or more particular R records, traversing from the particular R to its children. The index constitutes a balanced structure of blocks.

1 . A method for computerized traversal of hierarchical data using an index partitioned into blocks, over the keys representing the data; for every key K representing a record R in said index, the key of the children records of R are prefixed with K; the method comprising: 
 (i) traversing to a first R record represented in the index;    (ii) traversing from said R to the next sequential R such that the path in the index from the position representing R to the position representing the next sequential R does not include information relating to the children of R;    (iii) repeating step (ii) for 0 or more R records;    (iv) for any 0 or more particular R records, traversing from the particular R to its children;    said index constitutes a balanced structure of blocks.    
   
   
       2 . The method of  claim 1 , wherein the structure within each leaf block in the said index constitutes at least a sparse trie over the keys of the data elements accessible from the block.  
   
   
       3 . The method of  claim 1 , wherein said index includes at least a Patricia trie over the keys of the indexed data.  
   
   
       4 . The method of  claim 1 , wherein said index is a designated index.  
   
   
       5 . The method of  claim 1 , wherein said index is a layered index.  
   
   
       6 . The method of  claim 1 , wherein said index does not require that the complete key values are stored in the index.  
   
   
       7 . The method according to  claim 1 , wherein said index is based on a designated trie; and wherein said search in the trie is depth first post order.  
   
   
       8 . The method of  claim 1 , wherein said hierarchical data being semi-structured data.  
   
   
       9 . A method for computerized traversal of semi-structured data and/or hierarchical data, comprising a layered index partitioned into blocks over keys representing the said data; 
 the leaf layer of the said layered index includes at least a sparse trie; the method comprising performing a range search such that nodes are traversed depth first post order;    said range search process is capable to identify and ignore sub-tries that index keys not relevant to a search criterion.    said index constitutes a balanced structure of blocks.    
   
   
       10 . The method of  claim 9 , wherein said index is a designated index;  
   
   
       11 . The method of  claim 9 , wherein said index is a layered index.  
   
   
       12 . The method of  claim 9 , wherein a search by a parent key and a search by a child key are done in substantially the same efficiency.