Method for representing and storing hierarchical data in a columnar format

• US 9,087,138 B2
• Filed: 01/15/2013
• Issued: 07/21/2015
• Est. Priority Date: 01/15/2013
• Status: Active Grant

• Current Assignee: Xiaofan Zhou
• Original Assignee: Xiaofan Zhou
• Inventors: Zhou, Xiaofan
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Santos, Pedro J
• Application Number:
  US13/741,478
• Publication Number:
  US 20140201244A1
• Time in Patent Office: 917 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/86 Mapping to a database

Abstract

A computer implemented system, program product, and method that organizes hierarchical data into a plurality of columns is disclosed. A schema interface is defined for the data and two types of columns, value columns and occurrence columns, are used. Each value column stores the values for a field. Each occurrence column stores the occurrence numbers for a node that is repeatable, or optional, or in a choice group. The hierarchical relationship of the data is jointly preserved by the schema interface and the occurrence numbers in the occurrence columns. A database management system built upon the method is capable of operating at higher efficiency by combining some of the best aspects of relational database and hierarchical database management systems. The computer implemented method also provides a new and efficient method of exchanging data over networks.

Claims

1. A method of organizing hierarchical data in a columnar form to be stored in a computer database or transmitted over networks, said method comprising:

using a computer processor to create a fully expanded tree-like metadata schema for a type of hierarchical data;

wherein said schema is a fully expanded tree-like structure comprising record nodes and field nodes with one root node, wherein;

a;

a record node or a field node is defined and used only once in said tree structure;

b;

each node is defined by at least a name, a unique ID, and a type identifier;

c;

said unique ID is unique among all the nodes in said fully expanded tree-like structure, and said unique ID uniquely identifies the full path from the said root node to the said node in said fully expanded tree-like structure;

d;

said type identifier for a record node defines the content model of said record as either “

sequence”

or “

choice”

, wherein the default value is “

sequence”

, and said type identifier for a field node specifies the data type of the scalar value of said field node;

e;

each node has two optional attributes;

maxOccurs and minOccurs, wherein the default value for both attributes is “

1”

, wherein a value greater than “

1”

for maxOccurs indicates that the node is repeatable, and a value of “

0”

for minOccurs indicates that the node is optional;

f;

each field node has optional attributes to specify the value constraints; and

g;

each node further has an optional attribute pseudo to indicate said node is for content grouping or content presentation purposes;

using a computer processor to receive a plurality of instance data of said type of hierarchical data;

said instance data comprising a plurality of data entries organized in a hierarchical relationship;

matching each instance data against said schema and producing a plurality of columns of data, wherein there exists two types of columns, value columns and occurrence columns;

wherein each said instance data is matched against said schema in a chosen tree traversal order;

for each field node in said schema, allocating a value column in said columnar form and storing the scalar values for all matched data entries in said value column, and identifying said value column by the unique ID of said field node;

for each repeatable, optional or choosable field and record node in said schema, additionally allocating an occurrence column in said columnar form, storing occurrences in said occurrence column, and identifying said occurrence column by the unique ID of said respective field and record node;

discarding other matched data entries; and

each value column comprises an array of scalar values of same data type for a field in said schema;

each occurrence column comprises an array of occurrence numbers for a node in said schema, wherein said node is repeatable, optional or choosable;

wherein each occurrence number in an occurrence column indicates the total number of occurrences of the node under a single occurrence of the node'"'"'s parent node; and

said hierarchical relationship among said data entries is jointly preserved by said schema and said occurrence numbers in said occurrence columns;

storing said columns of data in a computer database;

or

serializing said columns of data into a stream of bytes of data;

or

performing at least one of a query, update, insertion, or deletion on said hierarchical data as stored in said columnar form.

2. The method of claim 1, further performing a query operation on said hierarchical data organized in said columnar form by:

constructing a query statement directed to one or more nodes in a fully expanded tree structure determined by said schema, wherein said query statement uses full paths in said fully expanded tree structure, wherein a plurality of sub-queries may be included;

optimizing said query statement, wherein each said unique ID replaces each said full path for each referenced node, and wherein said unique ID points to the column of data it identifies; and

executing the optimized query statement and retrieving data in a columnar form.

3. The method of claim 1, further performing an update operation on said hierarchical data organized in said columnar form by:

constructing an update statement with expressed conditions directed to one or more field nodes in a fully expanded tree structure determined by said schema, wherein said update statement uses full paths in said fully expanded tree structure;

optimizing said update statement, wherein each said unique ID replaces each said full path for each referenced node, wherein each said unique ID points to each column of data it identifies; and

executing the optimized update statement and replacing value entries in the columnar form with supplied values at the position that satisfies the update statement expressed conditions.

4. The method of claim 1, further performing an insert operation on said hierarchical data organized in said columnar form by:

organizing the data to be inserted in said columnar form, wherein said data comprises at least one instance of a repeatable or optional node in a fully expanded tree structure determined by said schema;

constructing an insert statement with expressed conditions directed to said repeatable or optional node in said fully expanded tree structure, wherein said insert statement uses full paths in said fully expanded tree structure;

optimizing said insert statement, wherein each said unique ID replaces each said full path for said referenced nodes; and

executing the optimized insert statement, and inserting said data into corresponding columns in the existing data at the position that satisfies said insert statement expressed conditions.

5. The method of claim 1, further performing a delete operation on said hierarchical data organized in said columnar form by:

constructing a delete statement with expressed conditions directed to one repeatable or optional node in a fully expanded tree structure determined by said schema, wherein said delete statement uses full paths in said fully expanded tree structure;

optimizing said delete statement, wherein each said unique ID replaces each said full path for said referenced nodes; and

executing the optimized delete statement, and deleting the instance data of said repeatable or optional node in the existing data according to said delete statement expressed conditions.

6. The method of claim 1, wherein a repeatable, optional or choosable field is also allocated an additional occurrence column;

wherein said additional occurrence column and said value column are both identified by the same said unique ID, further assigning an additional column identifier to differentiate the two types of columns;

or alternatively

assigning an additional unique ID to said repeatable, optional, or choosable field in a fully expanded tree structure determined by said schema and identifying the additional occurrence column by said additional unique ID;

or

alternatively performing the steps of;

h;

defining a content grouping node as the parent node of said field node, inserting it into the current position of said field node, and identifying said occurrence column by the unique ID of said content grouping node;

i;

assigning said content grouping node the attributes “

maxOccurs” and

“

minOccurs”

with desired value; and

j;

assigning said content grouping node the attribute “

pseudo”

.

7. The method of claim 1, wherein an occurrence column in said computer database is allocated for a repeatable, optional, or choosable node, wherein an occurrence number in said occurrence column in said computer database is used to indicate the total number of occurrences of said node in a single occurrence of said node'"'"'s parent node;

wherein if an ancestor node of said node is also allocated an occurrence column, and no other nodes between said ancestor node and said node is allocated an occurrence column, then for each occurrence number in said ancestor node'"'"'s occurrence column, assigning a same number of occurrence number entries in said node'"'"'s occurrence column.

8. The method of claim 1, further storing a plurality of said value columns and occurrence columns as columns of data in a computer database, said columns of data representing said instance data of said type of hierarchical data, wherein each column comprises an array of value entries of same data type and is identified by said unique ID, wherein:

for each fixed length field, storing the entries of the value column consecutively in allocated disk or memory space, wherein each entry occupies pre-defined number of bytes or characters;

for each variable length field, storing the entries of the value column consecutively in allocated disk or memory space, wherein each value is preceded by the length of the value;

or storing the lengths of the value entries consecutively, and then storing the values consecutively;

for each occurrence column, storing the occurrences consecutively in allocated disk or memory space;

wherein said allocated disk or memory space for each said column may contain one or more chunks of unit space from one or more storage devices, wherein said entries from different columns may be stored either consecutively or separately, in either a grouped or partitioned manner.

9. The method of claim 1, further serializing and transmitting a plurality of columns of data as a message comprising a stream of bytes of data to be transmitted over at least one computer network;

said method comprising;

for each column, concatenating said unique ID, the total number of entries, and the entry values to form bytes of data, wherein;

said unique ID and the total number of entries each comprise a fixed number of bytes in said message;

if said column is allocated for a fixed length field, each value entry comprises a fixed number of bytes or characters in said message;

if said column is allocated for a variable length field each value entry comprises a variable number of bytes or characters in said message, each said value being preceded by a length value in said message;

if said column has a maximum one value as may be determined by said schema, discarding the total number of entries after said unique ID;

concatenating said bytes of data from different columns together; and

transmitting said message with or without an attached copy of said schema.

10. A computer program product in a non-transitory computer readable storage medium, the product comprising computer code for instructing a computer processor to organize hierarchical data in a columnar form to be stored in a computer database or transmitted over networks, said computer code further comprising instructions for:

using a computer processor to create a fully expanded tree-like metadata schema for a type of hierarchical data;

wherein said schema is a fully expanded tree-like structure comprising record nodes and field nodes with one root node, wherein;

a;

a record node or a field node is defined and used only once in said tree structure;

b;

each node is defined by at least a name, a unique ID, and a type identifier;

c;

said unique ID is unique among all the nodes in said fully expanded tree structure, and said unique ID uniquely identifies the full path from the said root node to the said node in said fully expanded tree-like structure;

d;

said type identifier for a record node defines the content model of said record as either “

sequence”

or “

choice”

, wherein the default value is “

sequence”

, and said type identifier for a field node specifies the data type of the scalar value of said field node;

e;

each node has two optional attributes;

maxOccurs and minOccurs, wherein the default value for both attributes is “

1”

, wherein a value greater than “

1”

for maxOccurs indicates that the node is repeatable, and a value of “

0”

for minOccurs indicates that the node is optional;

f;

each field node has optional attributes to specify the value constraints; and

g;

each node further has an optional attribute pseudo to indicate said node is for content grouping or content presentation purposes;

using a computer processor to receive a plurality of instance data of said type of hierarchical data;

said instance data comprising a plurality of data entries organized in a hierarchical relationship;

matching each instance data against said schema and producing a plurality of columns of data, wherein there exists two types of columns, value columns and occurrence columns;

wherein each said instance data is matched against said schema in a chosen tree traversal order;

for each field node in said schema, allocating a value column in said columnar form and storing the scalar values for all matched data entries in said value column, and identifying said value column by the unique ID of said field node;

for each repeatable, optional or choosable field and record node in said schema, additionally allocating an occurrence column in said columnar form, storing occurrences in said occurrence column, and identifying said occurrence column by the unique ID of said respective field and record node;

discarding other matched data entries; and

each value column comprises an array of scalar values of same data type for a field in said schema;

each occurrence column comprises an array of occurrence numbers for a node in said schema, wherein said node is repeatable, optional or choosable;

wherein each occurrence number in an occurrence column indicates the total number of occurrences of the node under a single occurrence of the node'"'"'s parent node; and

said hierarchical relationship among said data entries is jointly preserved by said schema and said occurrence numbers in said occurrence columns;

storing said columns of data in a computer database;

or

serializing said columns of data into a stream of bytes of data;

or

performing at least one of a query, update, insertion, or deletion on said hierarchical data as stored in said columnar form.

11. The computer program product of claim 10, wherein a repeatable, optional or choosable field is also allocated an additional occurrence column, wherein said additional occurrence column and said value column are both identified by the same said unique ID, wherein said computer program further instructs a computer processor to perform the steps of:

further assigning an additional column identifier to differentiate the two types of columns;

or alternatively

assigning an additional unique ID to said repeatable, optional, or choosable field in a fully expanded tree structure determined by said schema and identifying the additional occurrence column by said additional unique ID;

or

alternatively performing the steps of;

h;

defining a content grouping node as the parent node of said field node, inserting it into the current position of said field node, and identifying said occurrence column by the unique ID of said content grouping node;

i;

assigning said content grouping node the attributes “

maxOccurs” and

“

minOccurs”

with desired value; and

j;

assigning said content grouping node the attribute “

pseudo”

.

12. The computer program product of claim 10, wherein said computer program further comprises instructions to direct a computer processor to serialize and transmit a plurality of columns of data as a message comprising a stream of bytes of data to be transmitted over at least one computer network;

said computer program further comprising instructions to direct a computer processor to;

for each column, concatenating said unique ID, the total number of entries, and the entry values to form bytes of data, wherein;

said unique ID and the total number of entries each comprise a fixed number of bytes in said message;

if said column is allocated for a fixed length field, each value entry comprises a fixed number of bytes or characters in said message;

if said column is allocated for a variable length field each value entry comprises a variable number of bytes or characters in said message, each said value being preceded by a length value in said message;

if said column has a maximum one value as may be determined by said schema, discarding the total number of entries after said unique ID;

concatenating said bytes of data from different columns together; and

transmitting said message with or without an attached copy of said schema.