Efficient traversals over hierarchical data and indexing semistructured data

• US 20030204515A1
• Filed: 03/05/2003
• Published: 10/30/2003
• Est. Priority Date: 03/06/2002
• Status: Active Grant

• Current Assignee: DB Software, Inc.
• Original Assignee: Ori Software Development Ltd
• Inventors: Sample, Neal, Shadmon, Moshe
• Granted Patent: US 7,287,033 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

Claims

1. In a storage medium used by a database file management system executed on data processing system, a data structure comprising:

an index, partitioned into blocks, over keys representing hierarchical data;

leaf blocks of said index are associated with data records;

said hierarchical data is represented by keys of type K(i) as a parent and for each parent 0 or more children of the type K(i)+J(1) . . . K(i)+J(n);

in order to satisfy a query for parents data, it is possible to traverse from a link of a parent K(i) to a link of the sequentially next parent K(i+1), skipping over links to the children K(i)+J(1) . . . K(i)+J(n);

to satisfy a query for a parent and his children, the index further supports a traversal from K(i) to the children J(1) . . . J(n) of said K(i);

said index maintains the key order;

said index constitutes an essentially balanced structure of blocks.

2. The data structure of claim 1 where each leaf block of said index maintains at least a sparse trie over data records addressed from the block.

3. The data structure of claim 1 where said index includes at least a Patricia trie over the keys of the data records.

4. The data structure of claim 1 where said index is a designated index.

5. The data structure of claim 1 where said index is a layered index.

6. The data structure of claim 4 where said index is a layered index.

7. The data structure of claim 1 where said index does not require that the complete key values are stored in the index.

8. The data structure of claim 1 wherein

each block of said index contains at least compressed information identifying the keys accessible from such block and links such that data records can be found according to their key;

the index facilitates the process of searching for a data record according to its key by reading a series of blocks composed of a root block and additional 0 or more blocks and a data record addressed by the leaf block of the said series of blocks such that the link to each additional block in the series or to the data record is found by applying a formula based on the compressed information in each previously read block and the key of the searched data record;

if a wrong data record is accessed, it is possible to decide that the searched data record does not exist or to initiate a new search by adding the information found in the accessed data record to the search formula;

the process is repeated until the data record is found or being able to decide that the searched data record does not exist.

9. The data structure of claim 1 further comprising:

for each parent, links to its children appear in a sub-tree in a leaf layer, the index facilitates a search to a root of the sub-tree by the key of the parent.

10. The data structure of claim 1, wherein said hierarchical data being semi-structured data.

30. The index of claim 1 where more than one type of key exists in a particular level of the hierarchy.

31. The data structure of claim 1 wherein the search for a parent by the key of the parent and a search of a child by the key of the child are done in similar efficiency.

32. The index of claim 31 whereas said index is a designated index.

33. The index of claim 32 whereas said index is a layered index.

34. The data structure of claim 1, wherein the index is further characterized in that for every 2 consecutive keys (K(i),K(i+1)) where the first K(i) key has children such that the size in the index to represent K(i) and his children is equal or larger than a block, it is possible to partition the index such that K(i) and the consecutive K(i+1) reside in the same block.

11. In a storage medium used by a database file management system executed on data processing system, that includes:

a tree based index, partitioned into blocks, over keys representing hierarchical data;

said keys include keys of parent records;

one or more parent records have children such that a key of each child record is prefixed by the key of its parent;

said index includes a sub-index such that the sub-index is an index over the keys of the children of a parent;

said index maintains an essentially balanced structure of blocks;

a method for searching in the index by a key;

said key is the prefix of the key of one or more parents including;

retrieving a first parent;

said method is further capable, if the first parent has children, to retrieve the children of said first parent;

said method is further capable, if a next parent is available, to retrieve the next parent skipping over the children of the first parent.

12. The method of claim 11 whereas said index is a designated index.

13. The method of claim 11 whereas said index is a layered index.

14. The method of claim 11 wherein:

said index allows clustering of links to data records according to the type of the data records.

15. The method of claim 14 such that:

said index further allows alternative clustering of links to a parent together with links to its children.

16. The method of claim 11 wherein:

said index is a designated index;

the keys of the children include at least 2 keys in the same hierarchy;

the said 2 keys have different designators.

17. The method of claim 11, wherein said hierarchical data being semi-structured data.

18. A method for encoding 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.

19. The method of claim 18 where 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.

20. The method of claim 18 where said index includes at least a Patricia trie over the keys of the indexed data.

21. The method of claim 18 where said index is a designated index.

22. The method of claim 18 where said index is a layered index.

23. The method of claim 18 where said index does not require that the complete key values are stored in the index.

24. The method according to claim 18 wherein said index is based on a designated trie;

and wherein said search in the trie is depth first post order.

25. The method of claim 18, wherein said hierarchical data being semi-structured data.

26. A method for encoding 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 an essentially balanced structure of blocks.

27. The method of claim 26 where said index is a designated index;

28. The method of claim 26 where said index is a layered index.

29. The index of claim 26 where a search by a parent key and a search by a child key are done in substantially the same efficiency.