Techniques related to binary encoding of hierarchical data objects to support efficient path navigation of the hierarchical data objects

Patent metadata

Field	Value
Publication number	US-10262012-B2
Application number	US-201514836680-A
Country	US
Kind code	B2
Filing date	Aug 26, 2015
Priority date	Aug 26, 2015
Publication date	Apr 16, 2019
Grant date	Apr 16, 2019

Abstract

Techniques related to binary encoding of hierarchical data objects to support efficient path navigation of the hierarchical data objects are disclosed. A hierarchical data object may include field names that are associated with field values. A method may involve generating a plurality of hash codes, each hash code corresponding to a respective field name. The method may involve generating a hash-code mapping that maps each hash code to a respective field-name identifier. The method may involve generating a field-name mapping that maps each field name to a respective field-name identifier. The method may involve generating a hierarchical tree of nodes that includes non-leaf nodes and leaf nodes. A particular non-leaf node may include a child node mapping that maps the particular non-leaf node to one or more child nodes and may include a field-name-identifier-to-child mapping that maps a respective field-name identifier to each of the one or more child nodes.

First claim

What is claimed is:

1. A method comprising:
for a hierarchical data object comprising field names that are each associated with one or more field values in said hierarchical data object, generating a plurality of hash codes, each hash code of said plurality of hash codes corresponding to a respective field name of said field names;
generating a hash-code mapping that maps each hash code of said plurality of hash codes to a respective field-name identifier of a plurality of field-name identifiers;
generating a field-name mapping that maps each field name of said field names to a respective field-name identifier of said plurality of field-name identifiers;
generating a hierarchical tree of nodes, wherein said hierarchical tree of nodes comprises non-leaf nodes and leaf nodes, wherein a particular non-leaf node of said non-leaf nodes comprises:
a child node mapping that maps said particular non-leaf node to one or more child nodes of said particular non-leaf node; and
a field-name-identifier-to-child mapping that maps a respective field-name identifier of said plurality of field-name identifiers to each of said one or more child nodes of said particular non-leaf node;

storing, in a record representing said hierarchical data object, said hash-code mapping, said field-name mapping, and for said particular non-leaf node of said non-leaf nodes, the child node mapping and the field-name-identifier-to-child mapping; and
wherein said method is performed by one or more computing devices.

2. The method of claim 1 , wherein generating said hash-code mapping comprises:
sorting said plurality of hash codes prior to storing said plurality of hash codes in said hash-code mapping.

3. The method of claim 1 , wherein, for each field-name identifier of said plurality of field-name identifiers, said field-name mapping references a respective memory location in a field-name collection, said field-name collection contiguously storing said field names and lengths of said field names within a memory address space.

4. The method of claim 3 , wherein generating said hash-code mapping comprises: resolving duplicate hash codes based on said field-name collection.

5. The method of claim 1 , wherein each leaf node of said leaf nodes references a respective memory location of a corresponding field value in a field-value collection, said field-value collection contiguously storing said field values within a memory address space.

6. The method of claim 5 , wherein said hash-code mapping, said field-name mapping, and said field-value collection are shared by a plurality of hierarchical data objects.

7. One or more non-transitory storage media storing instructions which, when processed by one or more computing devices, cause:
for a hierarchical data object comprising field names that are each associated with one or more field values in said hierarchical data object, generating a plurality of hash codes, each hash code of said plurality of hash codes corresponding to a respective field name of said field names;
generating a hash-code mapping that maps each hash code of said plurality of hash codes to a respective field-name identifier of a plurality of field-name identifiers;
generating a field-name mapping that maps each field name of said field names to a respective field-name identifier of said plurality of field-name identifiers;
generating a hierarchical tree of nodes, wherein said hierarchical tree of nodes comprises non-leaf nodes and leaf nodes, wherein a particular non-leaf node of said non-leaf nodes comprises:
a child node mapping that maps said particular non-leaf node to one or more child nodes of said particular non-leaf node; and
a field-name-identifier-to-child mapping that maps a respective field-name identifier of said plurality of field-name identifiers to each of said one or more child nodes of said particular non-leaf node; and

storing, in a record representing said hierarchical data object, said hash-code mapping, said field-name mapping, and for said particular non-leaf node of said non-leaf nodes, the child node mapping and the field-name-identifier-to-child mapping.

8. The one or more non-transitory storage media of claim 7 , wherein generating said hash-code mapping comprises:
sorting said plurality of hash codes prior to storing said plurality of hash codes in said hash-code mapping.

9. The one or more non-transitory storage media of claim 7 , wherein, for each field-name identifier of said plurality of field-name identifiers, said field-name mapping references a respective memory location in a field-name collection, said field-name collection contiguously storing said field names and lengths of said field names within a memory address space.

10. The one or more non-transitory storage media of claim 9 , wherein generating said hash-code mapping comprises:
resolving duplicate hash codes based on said field-name collection.

11. The one or more non-transitory storage media of claim 7 , wherein each leaf node of said leaf nodes references a respective memory location of a corresponding field value in a field-value collection, said field-value collection contiguously storing said field values within a memory address space.

12. The one or more non-transitory storage media of claim 11 , wherein said hash-code mapping, said field-name mapping, and said field-value collection are shared by a plurality of hierarchical data objects.

13. A method comprising:
for a hierarchical data object comprising field names that are associated with field values in said hierarchical data object, storing a representation of said hierarchical data object, wherein said representation of said hierarchical data object comprises a hash-code mapping and a hierarchical tree of nodes, wherein said hash-code mapping maps each field hash code of a plurality of field hash codes to a respective field-name identifier of a plurality of field-name identifiers, wherein said hierarchical tree of nodes comprises non-leaf nodes and leaf nodes, wherein said field values correspond to said leaf nodes, wherein a particular non-leaf node of said non-leaf nodes comprises:
a child node mapping that maps said particular non-leaf node to one or more child nodes of said particular non-leaf node; and
a field-name-identifier-to-child mapping that maps a respective field-name identifier of said plurality of field-name identifiers to each of said one or more child nodes of said particular non-leaf node;

to resolve a path expression comprising a plurality of path steps:
generating a sequence of step-hash codes, each step-hash code of said sequence corresponding to a path step of said plurality of path steps;
based on said hash-code mapping, translating said sequence of step-hash codes into a sequence of step-field-name identifiers;
navigating said hierarchical tree of nodes based on said sequence of step-field-name identifiers;

wherein said method is performed by one or more computing devices.

14. The method of claim 13 , wherein navigating said hierarchical tree of nodes based on said sequence of step-field-name identifiers comprises:
for each step-field-name identifier of said sequence of step-field-name identifiers, determining one or more corresponding non-leaf nodes based on said field-name-identifier-to-child mapping.

15. The method of claim 13 , wherein navigating said hierarchical tree of nodes based on said sequence of step-field-name identifiers comprises:
finding a particular step-field-name identifier in said field-name-identifier-to-child mapping based on performing a binary search on said field-name-identifier-to-child mapping.

Assignees

• Oracle Int Corp

Inventors

• Liu Zhen Hua
• Hammerschmidt Beda
• Mcmahon Douglas

Classifications

• G06F17/30303 Primary

  Physics · mapped topic

• G06F17/30327

  Physics · mapped topic

• G06F17/30589

  Physics · mapped topic

• G06F17/3033

  Physics · mapped topic

• G06F17/30917

  Physics · mapped topic