# US 2017/0286566 A1 · Optimizing sparse schema-less data in data stores

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0286566 A1
- Document ID: US20170286566A1
- Status: Published application
- Kind: A1
- Application number: 15/631,550
- Filed: 2017-06-23
- Published: 2017-10-05
- Earliest claimed: 2012-04-24
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Mihaela Ancuta BORNEA; Julian DOLBY; Achille Belly FOKOUE-NKOUTCHE; Anastasios KEMENTSIETSIDIS; Kavitha SRINIVAS
- Web page: https://patentgrep.com/patent/US20170286566A1

## CPC

- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/211: {Schema design and management}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Various embodiments of the invention relate to optimizing storage of schema-less data. At least one of a schema-less dataset including a plurality of resources one or more query workloads associated with the plurality of resources is received. Each resource is associated with at least a plurality of properties. At least one set of co-occurring properties from the plurality of properties is identified. A graph including a plurality of nodes is generated. Each of the nodes represents a unique property in the set of co-occurring properties. The graph further includes an edge connecting each node representing a pair of co-occurring properties. A schema is generated based on the graph that assigns a column identifier from a table to each unique property represented by one of the nodes in the graph.

## Claims

### Claim 1

A method for optimizing storage of schema-less data in a data storage system, the method comprising:
receiving at least one of
a schema-less dataset comprising a plurality of resources, and
at least one query workload associated with the plurality of resources,
wherein each resource in the plurality of resources is associated with at least a plurality of properties;
identifying, for one or more of the plurality of resources, at least one set of co-occurring properties from the plurality of properties;
generating a graph comprising a plurality of nodes, wherein each of the plurality of nodes represents a unique property in the at least one set of co-occurring properties, and wherein the graph further comprises an edge connecting each of the plurality of nodes representing a pair of co-occurring properties in the at least one set of co-occurring properties; and
generating, based on the graph, a storage schema, wherein the storage schema assigns a column identifier from a table to each unique property represented by one of the plurality of nodes in the graph, where each of the plurality of nodes connected by an edge is assigned the same column identifier.

### Claim 2 (depends on 1)

The method of claim 1, wherein generating the storage schema further comprises:
generating an inverse of the graph; and
performing a graph coloring operation on the inverse of the graph, wherein the graph coloring operation comprises assigning each of the plurality of nodes to a color, wherein nodes connected by an edge are assigned the same colors, and wherein a color represents a column identifier from the table.

### Claim 3 (depends on 2)

The method of claim 2, further comprising:
determining a total number of colors assigned to the plurality of nodes in the graph;
comparing the total number of colors to a first threshold identifying a maximum number of columns associated with the table;
determining if the total number of colors is greater than the first threshold; and
removing, based on the total number of colors being greater than the first threshold, nodes associated with at least one set of co-occurring properties from the graph until a percentage of the dataset represented by all nodes in the graph at least one of
reaches or becomes less than a second threshold identifying a minimum percentage of the schema-less dataset to be conflict free, and
reaches the first threshold.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
generating, based on the total number of colors being equal to the first threshold, at least one additional graph comprising nodes representing unique properties in at least one additional set of co-occurring properties.

### Claim 5 (depends on 1)

The method of claim 1, wherein generating the storage schema further comprises:
partitioning the graph into a set of partitions, wherein each of the set of partitions comprises a set of the plurality of nodes; and
performing a graph coloring operation on each of the set of partitions, wherein the graph coloring operation comprises assigning each node in the set of plurality of nodes in one of the set of partitions the same color, and wherein a color represents a column identifier from the table.

### Claim 6 (depends on 1)

The method of claim 1, wherein the table resides within a column store.

### Claim 7 (depends on 1)

The method of claim 1, wherein the table resides within a property table store.

### Claim 8 (depends on 1)

The method of claim 1, wherein the schema-less dataset is in a Resource Description Framework triple format, and wherein the plurality of resources is represented as a plurality of subjects and the plurality of properties is represented as a plurality of predicates.

### Claim 9 (depends on 1)

The method of claim 1, wherein generating the graph further comprises:
identifying a first property in the at least one set of co-occurring properties that is associated with a higher priority than a second property in the at least one set of co-occurring properties; and
adding a node to the graph representing the first property prior to adding a node to the graph representing the second property.

### Claim 10

An information processing system for optimizing storage of schema-less data in a data storage system, the information processing system comprising:
a memory;
a processor communicatively coupled to the memory; and
a data optimizer communicatively coupled to the memory and the processor, wherein the data optimizer is configured to perform a method comprising:
receiving at least one of
a schema-less dataset comprising a plurality of resources, and
at least one query workload associated with the plurality of resources,
wherein each resource in the plurality of resources is associated with at least a plurality of properties;
identifying, for one or more of the plurality of resources, at least one set of co-occurring properties from the plurality of properties;
generating a graph comprising a plurality of nodes, wherein each of the plurality of nodes represents a unique property in the at least one set of co-occurring properties, and wherein the graph further comprises an edge connecting each of the plurality of nodes representing a pair of co-occurring properties in the at least one set of co-occurring properties; and
generating, based on the graph, a storage schema, wherein the storage schema assigns a column identifier from a table to each unique property represented by one of the plurality of nodes in the graph, where each of the plurality of nodes connected by an edge is assigned the same column identifier.

### Claim 11 (depends on 10)

The information processing system of claim 10, wherein generating the storage schema further comprises:
generating an inverse of the graph; and
performing a graph coloring operation on the inverse of the graph, wherein the graph coloring operation comprises assigning each of the plurality of nodes to a color, wherein nodes connected by an edge are assigned the same colors, and wherein a color represents a column identifier from the table.

### Claim 12 (depends on 11)

The information processing system of claim 11, wherein the method further comprises:
determining a total number of colors assigned to the plurality of nodes in the graph;
comparing the total number of colors to a first threshold identifying a maximum number of columns associated with the table;
determining if the total number of colors is greater than the first threshold; and
removing, based on the total number of colors being greater than the first threshold, nodes associated with at least one set of co-occurring properties from the graph until a percentage of the dataset represented by all nodes in the graph at least one of
reaches or becomes less than a second threshold identifying a minimum percentage of the schema-less dataset to be conflict free, and
reaches the first threshold.

### Claim 13 (depends on 12)

The information processing system of claim 12, wherein the method further comprises:
generating, based on the total number of colors being equal to the first threshold, at least one additional graph comprising nodes representing unique properties in at least one additional set of co-occurring properties.

### Claim 14 (depends on 10)

The information processing system of claim 10, wherein generating the storage schema further comprises:
partitioning the graph into a set of partitions, wherein each of the set of partitions comprises a set of the plurality of nodes;
performing a graph coloring operation on each of the set of partitions, wherein the graph coloring operation comprises assigning each node in the set of plurality of nodes in one of the set of partitions the same color, and wherein a color represents a column identifier from the table.

### Claim 15 (depends on 10)

The information processing system of claim 10, wherein the schema-less dataset is in a Resource Description Framework triple format, and wherein the plurality of resources is represented as a plurality of subjects and the plurality of properties is represented as a plurality of predicates.

### Claim 16 (depends on 10)

The information processing system of claim 10, wherein generating the graph further comprises:
identifying a first property in the at least one set of co-occurring properties that is associated with a higher priority than a second property in the at least one set of co-occurring properties; and
adding a node to the graph representing the first property prior to adding a node to the graph representing the second property.

### Claim 17

A computer program product for optimizing storage of schema-less data in a data storage system, the computer program product comprising:
a storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:
receiving at least one of
a schema-less dataset comprising a plurality of resources, and
at least one query workload associated with the plurality of resources,
wherein each resource in the plurality of resources is associated with at least a plurality of properties;
identifying, for one or more of the plurality of resources, at least one set of co-occurring properties from the plurality of properties;
generating a graph comprising a plurality of nodes, wherein each of the plurality of nodes represents a unique property in the at least one set of co-occurring properties, and wherein the graph further comprises an edge connecting each of the plurality of nodes representing a pair of co-occurring properties in the at least one set of co-occurring properties; and
generating, based on the graph, a storage schema, wherein the storage schema assigns a column identifier from a table to each unique property represented by one of the plurality of nodes in the graph, where each of the plurality of nodes connected by an edge is assigned the same column identifier.

### Claim 18 (depends on 17)

The computer program product of claim 17, wherein generating the storage schema further comprises:
generating an inverse of the graph; and
performing a graph coloring operation on the inverse of the graph, wherein the graph coloring operation comprises assigning each of the plurality of nodes to a color, wherein nodes connected by an edge are assigned the same colors, and wherein a color represents a column identifier from the table.

### Claim 19 (depends on 18)

The computer program product of claim 18, wherein the method further comprises
determining a total number of colors assigned to the plurality of nodes in the graph;
comparing the total number of colors to a first threshold identifying a maximum number of columns associated with the table;
determining if the total number of colors is greater than the first threshold; and
removing, based on the total number of colors being greater than the first threshold, nodes associated with at least one set of co-occurring properties from the graph until a percentage of the dataset represented by all nodes in the graph at least one of
reaches or becomes less than a second threshold identifying a minimum percentage of the schema-less dataset to be conflict free, and
reaches the first threshold.

### Claim 20 (depends on 19)

The computer program product of claim 19, wherein the method further comprises
generating, based on the total number of colors being equal to the first threshold, at least one additional graph comprising nodes representing unique properties in at least one additional set of co-occurring properties.

### Claim 21 (depends on 17)

The computer program product of claim 17, wherein generating the storage schema further comprises:
partitioning the graph into a set of partitions, wherein each of the set of partitions comprises a set of the plurality of nodes; and
performing a graph coloring operation on each of the set of partitions, wherein the graph coloring operation comprises assigning each node in the set of plurality of nodes in one of the set of partitions the same color, and wherein a color represents a column identifier from the table.

### Claim 22 (depends on 17)

The computer program product of claim 17, wherein the table resides within a column store.

### Claim 23 (depends on 17)

The computer program product of claim 17, wherein the table resides within a property table store.

### Claim 24 (depends on 17)

The computer program product of claim 17, wherein the schema-less dataset is in one of a Resource Description Framework triple format, and wherein the plurality of resources is represented as a plurality of subjects and the plurality of properties is represented as a plurality of predicates.

### Claim 25 (depends on 17)

The computer program product of claim 17, wherein generating the graph further comprises:
identifying a first property in the at least one set of co-occurring properties that is associated with a higher priority than a second property in the at least one set of co-occurring properties; and
adding a node to the graph representing the first property prior to adding a node to the graph representing the second property.
