Encoding of hierarchically organized data for efficient storage and processing

• US 20060212467A1
• Filed: 07/14/2005
• Published: 09/21/2006
• Est. Priority Date: 03/21/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Manian, Anjana, Peschansky, Olga, Sedlar, Eric, Chandrasekar, Sivasankaran, Murthy, Ravi, Karun, K., Yiu, Kwok Lun Alex, Lenkov, Dmitry
• Granted Patent: US 8,346,737 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/123 Storage facilities
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/146 Coding or compression of tree-structured data

Abstract

A compact binary encoding technique for information that is logically hierarchically structured, such as XML data, maintains all of the features of XML data in a useable form, such as the hierarchical structure underlying the data. Hence, data encoded in this format can undergo XML-based processing on-the-fly as it is being received or fetched, as if the data was being processed linearly in its textual character-based format. Processing of data encoded in this format can begin without having to wait for and decode the entire data set. The overhead due to XML tags is significantly minimized. The encoded data can be processed more efficiently because the data is pre-parsed. Values may be stored in their native type formats and, therefore, processing of the encoded data avoids costly type conversions. Further, any available structural constraint information can be effectively exploited.

Claims

1. A machine-implemented method for processing information that is logically hierarchically structured as one or more hierarchies, the method comprising:

receiving the information encoded in a compact format, wherein the encoded information requires less memory for storing than the information in its original form and maintains characteristics of the one or more hierarchies; and

beginning processing a portion of the encoded information, based on the characteristics of the one or more hierarchies, before receiving all of the encoded information.

2. The method of claim 1, wherein the information that is hierarchically structured is within an XML document, and wherein processing the portion of the encoded information includes processing XML elements and values.

3. The method of claim 2, wherein receiving the encoded information includes receiving token identifiers to substitute for and identify XML tags contained in the information, and wherein the token identifiers require fewer bits to encode than corresponding character representations of the tags require.

4. The method of claim 3, wherein processing a portion of the encoded information includes accessing a mapping of token identifiers to corresponding definitions, and wherein the mapping is separate from the XML document.

5. A machine-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

6. A machine-implemented method for processing information that is logically hierarchically structured as one or more hierarchies, the method comprising:

encoding the information in a compact format, wherein the encoded information requires less memory for storing than the information in its original form and maintains characteristics of the one or more hierarchies; and

transmitting the encoded information to a receiver, wherein processing a portion of the encoded information by the receiver begins, based on the characteristics of the one or more hierarchies, before receiving all of the encoded information.

7. The method of claim 6, wherein the information that is hierarchically structured is within an XML document.

8. The method of claim 6, wherein encoding the information and transmitting the encoded information include alternately encoding a subset of the information and transmitting the encoded subset of information.

9. The method of claim 6, wherein at least one of the one or more hierarchies is a single-level hierarchy.

10. A machine-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

11. A machine-implemented method for encoding XML data, the method comprising:

encoding the information using token identifiers to substitute for and identify XML tags contained in the information, wherein the token identifiers require fewer bits to encode than corresponding character representations of the tags require.

12. The method of claim 11,

wherein encoding the information includes using an operation code-operand(s) pair to substitute for respective (a) corresponding XML tags and (b) corresponding values associated with the XML tags, and wherein the operation codes and associated operands require fewer bits to encode than corresponding character representations of the tags and values require.

13. The method of claim 12, wherein the XML document is associated with a corresponding schema that specifies a particular hierarchical order and particular cardinalities for two or more tags within the document, and

wherein encoding the information includes encoding, for each of the two or more tags other than the first tag, an operation code for only the corresponding values.

14. The method of claim 13, further comprising:

in response to the original schema being modified, adding annotations to the modified schema;

wherein the annotations map each of the two or more tags to the corresponding hierarchical order of the tag from the original schema.

15. The method of claim 11,

wherein encoding the information includes using an operation code-operand(s) pair to substitute for respective (a) corresponding XML tags and (b) corresponding values associated with the XML tags,

the method further comprising:

if the information includes two or more consecutive instances of a particular XML tag, then using an array mode operation code without an operand, to substitute for each consecutive instance other than the first instance; and

wherein the array mode operation code indicates that the tag that corresponds to the instance is the same tag that corresponds to a particular previous instance.

16. The method of claim 11,

wherein encoding the information includes using an operation code-operand pair to substitute for respective corresponding XML elements, and wherein the token identifiers are used as the operands for associated operation codes.

17. The method of claim 11, wherein the XML data is associated with a corresponding schema that specifies a particular data type for corresponding variable values,

wherein encoding the information includes encoding a corresponding variable value in a data type-based machine-representation of the value, and wherein the machine-representation of the value requires fewer bits to encode than a corresponding character representation of the value requires.

18. The method of claim 17,

wherein encoding the information includes encoding, in association with the variable value, the data type of the variable value.

19. The method of claim 11, wherein the XML data is a sectioned XML document,

wherein encoding the information includes encoding a series of nodal section references with a collection section operation code;

wherein the operands corresponding to the collection section operation code include order keys corresponding to the first and last sections referenced in the series; and

wherein each order key indicates where a corresponding root node of the corresponding section is positioned within a hierarchical structure of the XML data.

20. A machine-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

21. A machine-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

22. A machine-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

23. A machine-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

24. A machine-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15.

25. A machine-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16.

26. A machine-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 17.

27. A machine-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 18.

28. A machine-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 19.