Encoding semi-structured data for efficient search and browse

• US 20020120598A1
• Filed: 02/26/2001
• Published: 08/29/2002
• Est. Priority Date: 02/26/2001
• Status: Active Grant

• Current Assignee: DB Software, Inc.
• Original Assignee: Ori Software Development Ltd
• Inventors: Sample, Neal, Cooper, Brian, Franklin, Michael J., Shadmon, Moshe
• Granted Patent: US 6,804,677 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/835 Query processing
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method for encoding XML tree data that includes the step of encoding the semi-structured data into strings of arbitrary length in a way that maintains non-structural and structural information about the XML data, and enables indexing the encoded XML data in a way facilitates efficient search and browsing.

Claims

1. A method for encoding semi-structured data, comprising:

a) Providing a semi-structured data input;

b) obtaining an encoded semi-structured data by selectively encoding at least part of said semi-structured data into strings of arbitary length in a way that (i) maintains non-structural and structural information associated with the semi-structured data, and (ii) the so encoded semi-structured data can be indexed for efficient access.

2. The method according to claim 1, wherein said associated structural information includes information that is explicit in said semi-structured data.

3. The method according to claim 1, wherein said associated structural information includes information that is not explicit in said semi-structured data.

4. The method according to claim 2, wherein said associated structural information includes information that is not explicit in said semi-structured data.

5. The method according to claim 2, wherein said associated structural information includes path information explicit in said semi-structured data.

6. The method according to claim 3, wherein said associated structural information includes path information not explicit in said semi-structured data.

7. The method according to claim 5, wherein said associated non-structural information includes path information not explicit in said semi-structured data.

8. The method according to claim 5, wherein said path information includes at least two paths that lead to a same data item.

9. The method according to claim 2, wherein said associated structural information includes order information explicit in said semi-structured data.

10. The method according to claim 1, wherein said encoding step includes compressing whereby said strings of arbitrary length are compressed.

11. The method according to claim 1, wherein said semi-structured data being a Markup Language (ML) data or representation thereof.

12. The method according to claim 11, wherein said structural information being the markup of said ML and non-structural information being the content of said ML data.

13. The method according to claim 12 wherein said encoding stipulated in step (b) includes

i) assigning a token from a token dictionary to each tag or attribute from the markup of said at least part of ML data;

if the tag or attribute does not appear in the dictionary, creating a new token and assigning the so created token to said tag or attribute, so as to give rise to intermediate ML tree;

ii) scanning the intermediate ML tree data obtained in (i) and for represent paths from the root as corresponding strings.

14. The method of claim 13 wherein said step (ii) includes for each one of said paths erasing arrows from a parent to children so as to obtain a resulting string of arbitrary length.

15. The method according to claim 11, wherein said associated structural information includes path information explicit in said ML data.

16. The method according to claim 15, wherein said associated structural information includes path information not explicit in said ML data.

17. The method according to claim 15, wherein said path information includes at least two paths that lead to a same data item.

18. The method according to claim 16, wherein said path information includes at least two paths that lead to a same data item.

19. The method according to claim 11, wherein said associated structural information includes sibling order information explicit in said ML data.

20. The method according to claim 11, wherein said associated structural information includes sibling order information not explicit in said XML data.

21. The method according to claim 13, wherein step (i) further includes;

(1) creating a unique token in said dictionary for maintaining sibling order of data items and inserting said token to the intermediate ML tree data with edges thereof labeled with ordinal numbers that correspond to the ordered items.

22. The method of claim 1, further comprising the step of indexing the encoded semi-structured data, for efficient access.

23. The method according to claim 22, wherein said indexing utilizes layered index.

24. The method according to claim 5, further comprising the step of indexing said path information, for efficient access.

25. The method according to claim 6, further comprising the step of indexing said path information, for efficient access.

26. The method according to claim 7, further comprising the step of indexing said path information, for efficient access.

27. The method according to claim 8, further comprising the step of indexing said path information, for efficient access.

28. The method according to claim 24, wherein said indexing step includes compressing said path information.

29. The method according to claim 25, wherein said indexing step includes compressing said path information.

30. The method according to claim 26, wherein said indexing step includes compressing said path information.

31. The method according to claim 27, wherein said indexing step includes compressing said path information.

32. The method of claim 11, further comprising the step of indexing the encoded ML data, for efficient access.

33. The method according to claim 32, wherein said indexing utilizes layered index.

34. The method according to claim 15, further comprising the step of indexing said path information, for efficient access.

35. The method according to claim 16, further comprising the step of indexing said path information, for efficient access.

36. The method according to claim 17, further comprising the step of indexing said path information, for efficient access.

37. The method according to claim 18, further comprising the step of indexing said path information, for efficient access.

38. The method according to claim 34, wherein said indexing step includes compressing said path information.

39. The method according to claim 35, wherein said indexing step includes compressing said path information.

40. The method according to claim 36, wherein said indexing step includes compressing said path information.

41. The method according to claim 37, wherein said indexing step includes compressing said path information.

42. The method according to claim 22, wherein said indexing step results in an index that maintains a balanced structure of blocks.

43. The method according to claim 23, wherein said indexing step results in an index that maintains a balanced structure of blocks.

44. The method according to claim 32, wherein said indexing step results in an index that maintains a balanced structure of blocks.

45. The method according to claim 33, wherein said indexing step results in an index that maintains a balanced structure of blocks.

47. The method according to claim 46, wherein the metadata dictionary further maintains semantic information that is not explicit in the semi-structured data as well as syntactic information that is explicit in the semi-structured data.

48. The method according to claim 46, wherein said semi-strctured data being a Markup Language (ML) data or representation thereof;

said Markup Language (ML) data or representation thereof includes markup and contents.

49. The method according to claim 46, wherein said metadata dictionary being a token dictionary and wherein said construction step includes:

i) assigning a token from a token dictionary to each tag or attribute from the markup of said at least part of ML data;

if the tag or attribute does not appear in the dictionary, creating a new token and assigning the so created token to said tag or attribute.

57. The method according to claim 1, wherein said access includes browse.

58. The method according to claim 11, wherein said access includes browse.

59. The method according to claim 22, wherein said access includes browse.

60. The method according to claim 22, further comprising the step of querying said semi-structured data utilizing said index.

61. The method according to claim 23, further comprising the step of querying said Markup Language data utilizing said layered index.

62. The method according to claim 32, further comprising the step of querying said semi-structured data utilizing said index.

63. The method according to claim 33, further comprising the step of querying said Markup Language data utilizing said index.

64. A method according to claim 23, wherein said encoding and indexing steps include:

mapping the semi-structured data to designated data records where each such designated record can be a subordinated record;

combining the designated records into strings that can represent structural and non-structural information that is either explicit or not explicit in the original data item; and

creating a designated index in which part or all of each string is treated as a key, thereby enabling search over this set of designated records. In a preferred embodiment such index would be a layered index.

65. For use with the method claim 22, said indexing step.

66. For use with the method claim 60, said querying step.

68. For use with a system according claim 65 a processor node configured to index said encoded semi-structured data.

69. For use with a system according to claim 66, a processor configured to query said index

a storage medium storing data indicative of a metadata dictionary for semi-structured data;

the metadata dictionary facilitates compressed encoding of at least part of said semi-structured data into strings of arbitrary length in a way that at least maintains non-structural and structural information associated with the semi-structured data.

73. A computer program product storing data indicative of computer program configured to perform the method steps of claim 1.

74. The computer program product of claim 73, wherein said computer program is further configured to perform the step of indexing the encoded semi-structured data, for efficient access.

46. A method for constructing a metadata dictionary in respect of semi-structured data, comprising:

a) providing a semi-structured data input;

b) constructing a metadata dictionary that facilitates compressed encoding of at least part of said semi-structured data into strings of arbitrary length in a way that at least maintains non-structural and structural information associated with the semi-structured data.

50. A method for encoding and indexing semi-structured data, comprising:

a) providing a semi-structured data input;

b) obtaining an encoded semi-structured data by selectively encoding at least part of said semi-structured data into strings of arbitrary length in a way that (i) maintains non-structural and structural information associated with the semi-structured data;

c) indexing the encoded semi-structured data using layered index;

the layered index includes basic partitioned index structure;

said layered index maintains a balanced structure of blocks.

75. A computer program product storing data indicative of computer program configured to perform the method steps of claim 50.

51. A method for encoding and indexing Markup Language (ML) data, comprising:

a) providing an ML data input;

b) obtaining an encoded ML data by selectively encoding at least part of said ML data into strings of arbitrary length in a way that (i) maintains non-structural and structural information associated with the semi-structured data;

c) indexing the encoded semi-structured data using layered index;

the layered index includes basic partitioned index structure;

said layered index maintains a balanced structure of blocks.

76. A computer program product storing data indicative of computer program configured to perform the method steps of claim 51.

52. A method for encoding and indexing semi-structured data, comprising:

(a) Providing a semi-structured data input;

b) selectively encoding at least part of said semi-structured data into keys of arbitrary length in a way that (i) maintains non-structural and structural information associated with the semi-structured data;

c) creating a balanced index structure over the arbitrary-lengthed keys.

53. The method of claim 52, wherein said index structure being a layered index.

54. The method according to claim 52, wherein said semi-structured data being an ML.

77. A computer program product storing data indicative of compact program configured to perform the method steps of claim 52.

79. The storage medium of claim 78, wherein said data further contain an index of said encoded semi-structured data.

80. The storage medium of claim 79, wherein said index being layered index.

55. A method for indexing semi-structured data, comprising:

(a) providing a semi-structured data input that include data items;

(b) indexing keys of the data items of the said semi-structured data such that with about no more than 25,000 bytes of interned memory per 1 million data items it is possible to locate an address of any such said data item with no more than 2 I/Os, irrespective of the size of the key.

56. A method for indexing metadata language (ML) data, comprising:

(a) providing an ML data input that include data items;

(b) indexing keys of the data items of the said ML data such that with about no more tan 25,000 bytes of internal memory per 1 million data items it is possible to locate an address of any such said data item with no more than 2 I/Os, irrespective of the size of the key.

67. A system for encoding semi-structured data, comprising:

storage for storing a semi-structured data input;

processor node configured to construct an encoded semi-structured data by selectively encoding at least part of said semi-structured data into strings of arbitrary length in a way that (i) maintains non-structural and structural information associated with the semi-structured data, and (ii) the so encoded semi-structured data can be indexed for efficient access.

70. A system for encoding and indexing semi-structured data, comprising:

storage for storing a semi-structured data input;

processor node configured to construct an encoded semi-structured data by selectively encoding at least part of said semi-structured data into strings of arbitrary length in a way that (i) maintains non-structural and structural information associated with the semi-structured data;

processor node configured to construct an indexing o the encoded semi-structured data using layered index;

the layered index includes basic partitioned index structure;

said layered index maintains a balanced structure of blocks.

71. A system for encoding and indexing Markup Language (ML) data, comprising:

storage for storing an ML data input;

processor node configured to construct an encoded ML data by selectively encoding at least part of said ML data into strings of arbitrary length in a way that (i) maintains non-structural and structural information associated with the semi-structured data;

processor node configured to construct an indexing of the encoded semi-structured data using layered index;

the layered index includes basic partitioned index structure;

said layered index maintains a balanced structure of blocks.

72. A system for encoding and indexing semi-structured data, comprising:

storage for storing a semi-structured data input;

processor node configured to selectively encoding at least part of said semi-structured data into keys of arbitrary length in a way that (i) maintains non-structural and structural information associated with the semi-structured data;

processor node configured to creating a balanced index structure over the arbitrary-lengthed keys.

78. A storage medium storing data indicative of encoded semi-structured data that includes strings of arbitrary length that (i) maintains non-structural and structural information associated with the semi-structured data, and (ii) the so encoded semi-structured data can be indexed for efficient access.

81. In a computer system having a storage medium of at least an internal memory and an external memory;

a data structure that includes an index over the keys of the data items;

the index is arranged in blocks, such that with about no more than 25,000 bytes of internal memory per 1 million data items it is possible to locate an address of any such said data item with no more than 2 I/Os access to the external memory, irrespective of the size of the key.