Encoding semi-structured data for efficient search and browsing

• US 20050033733A1
• Filed: 09/01/2004
• Published: 02/10/2005
• Est. Priority Date: 02/26/2001
• Status: Active Grant

• Current Assignee: DB Software, Inc.
• Original Assignee: Ori Software Development Ltd
• Inventors: Shadmon, Moshe, Sample, Neal, Cooper, Brian, Franklin, Michael J.
• Granted Patent: US 8,489,597 B2
• Time in Patent Office: Days
• US Class Current: 1/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 that facilitates efficient search and browsing.

Claims

1. A method for encoding semistructured 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 at least (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 representing 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:

i) 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.

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 semi-structured data utilizing said layered index.

62. The method according to claim 32, further comprising the step of querying said Markup Language 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.

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.

83. The method according to claim 22, wherein said index is partitioned into blocks, the structure within blocks of said index is based on a sparse trie.

84. The method according to claim 22, wherein the size of said index does not depend on the size of the keys.

85. The method according to claim 22, wherein said indexing is a compressed key index.

86. The method of claim 83, wherein said index constitutes a balanced structure of blocks.

87. The method of claim 86, whereas said index constitutes a balanced structure of blocks.

88. The method of claim 85, wherein said index constitutes a balanced structure of blocks.

92. The method of claim 22, wherein said index is a designated index.

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.

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-structured 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.

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 at least (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 at least (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;

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

b) creating a balanced index structure over the arbitrary-length 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 computer program configured to perform the method steps of claim 52.

89. The method of claim 52, wherein said index is a compressed key index.

90. The method of claim 52, wherein the size of the said index does not depend on the size of the key.

91. The method of claim 52, wherein said index is a designated 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 internal memory per 1 million data items it is possible to locate a 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 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, 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 at least (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.

68. The system according to claim 67 wherein the processor node is configured to index said encoded semi-structured data.

69. The system according to claim 68, wherein the processor is configured to query said index.

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 at least (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 at least (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 at least (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-length keys.

78. A storage medium storing data indicative of encoded semi-structured data that includes strings of arbitrary length that at least (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.

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.

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.

82. 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.

93. A storage medium storing data indicative of an index over keys of arbitrary length encoded from semi-structured data, said index is partitioned into blocks;

said index constitutes an essentially balanced structure of blocks.

94. The storage medium of claim 93, wherein the structure within each block is based on a sparse trie.

95. The storage medium of claim 93, wherein the size of the index depends on the number of keys but no on the size of the keys.

96. The storage medium of claim 93, wherein said index is a designated index.

97. A storage medium of claim 96, wherein said index is used for browsing.