# US 2021/0263898 A1 · Reducing response time for queries directed to domain-specific knowledge graph using property graph schema optimization

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

- Number: US 2021/0263898 A1
- Document ID: US20210263898A1
- Status: Published application
- Kind: A1
- Application number: 16/800,392
- Filed: 2020-02-25
- Published: 2021-08-26
- Earliest claimed: 2020-02-25
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: CHUAN LEI; ABDUL QUAMAR; VASILIS EFTHYMIOU; FATMA OZCAN; RANA ALOTAIBI
- Web page: https://patentgrep.com/patent/US20210263898A1

## CPC

- G06F 16/211: {Schema design and management}
- G06N 5/022: Knowledge engineering; Knowledge acquisition
- G06F 16/2453: Query optimisation
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06N 5/02: Knowledge representation; Symbolic representation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

According to one or more embodiments of the present invention, a computer-implemented method for providing a query response includes receiving, by a computing device, a domain-specific knowledge graph. The method further includes generating a first property graph schema, a property graph schema includes vertices, edges, and properties of the domain-specific knowledge graph, wherein the first property graph schema is generated based on an ontology of the domain-specific knowledge graph. The method further includes generating a second property graph schema from a copy of the first property graph schema that is optimized by applying one or more types of relationships in the first property graph schema. The method further includes instantiating a property graph using the second property graph schema. The method further includes receiving a query to obtain particular data from the domain-specific knowledge graph. The method further includes responding to the query using the property graph.

## Claims

### Claim 1

A computer-implemented method for providing a query response, the computer-implemented method comprising:
receiving, by a computing device, a domain-specific knowledge graph;
generating, by the computing device, a first property graph schema, a property graph schema includes vertices, edges, and properties of the domain-specific knowledge graph, wherein the first property graph schema is generated based on an ontology of the domain-specific knowledge graph;
generating, by the computing device, a second property graph schema from a copy of the first property graph schema that is optimized by applying one or more types of relationships in the first property graph schema;
instantiating, by the computing device, a property graph using the second property graph schema;
receiving, by the computing device, a query to obtain particular data from the domain-specific knowledge graph; and
responding to the query using the property graph.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1 further comprising, optimizing, by the computing device, the first property graph schema by modifying one or more inheritance relationships in the first property graph schema, wherein modifying an inheritance relationship comprises:
determining a set of child data-properties of a child node of the inheritance relationship, and a set of parent data-properties of a parent node of the inheritance relationship;
computing a similarity score for the child data-properties and the parent data-properties;
in response to the similarity score being greater than a first threshold, associating the child data-properties with the parent node, and otherwise associating the parent data-properties with the child node; and
removing the inheritance relationship from the first property graph schema.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1 further comprising, optimizing, by the computing device, the first property graph schema by modifying one or more union relationships in the first property graph schema, wherein optimizing a union relationship comprises, for a plurality of member nodes associated with the union relationship, adding an edge between each pair of member nodes from the plurality of member nodes.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1 further comprising, optimizing, by the computing device, the first property graph schema by modifying a 1:M relationship in the first property graph schema, the optimization comprising:
adding, to a list of properties of a source of the 1:M relationship, all of the properties of a destination of the 1:M relationship.

### Claim 5 (depends on 4)

The computer-implemented method of claim 4 further comprising, optimizing, by the computing device, the first property graph schema by modifying a M:N relationship in the first property graph schema, the optimization comprising addressing, by the computing device, the M:N relationship as multiple 1:M relationships.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1 further comprising, optimizing, by the computing device, the first property graph schema by modifying a 1:1 relationship in the first property graph schema, the optimization comprising:
adding, to the second property graph schema, a new node that is generated by merging a source node and a destination node of the 1:1 relationship; and
removing, from the second property graph schema, the source node, the destination node, and the 1:1 relationship.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1 further comprising, optimizing, by the computing device, the property graph schema by modifying a subset of relationships from a plurality of relationships in the first property graph schema, wherein the subset of relationships is determined based on a storage space limit.

### Claim 8 (depends on 7)

The computer-implemented method of claim 7, wherein optimizing the property graph schema comprises:
receiving the storage space limit as an input, the storage space limit indicating an amount of storage space budgeted for optimizing the property graph schema;
determining the order of all relationships in the first property graph schema based on a cost-benefit model; and
selecting a subset of relationships in the first property graph schema that maximize the total benefit until the storage space limit is exhausted.

### Claim 9 (depends on 7)

The computer-implemented method of claim 7, wherein optimizing the property graph schema comprises:
receiving the storage space limit as an input, the storage space limit indicating an amount of storage space budgeted for optimizing the property graph schema;
determining the order of all concepts in the first property graph schema based on the centrality analysis; and
iterating through the concepts from high centrality score to lower and apply relationship rules to each concept until the storage space limit is exhausted.

### Claim 10

A system comprising:
a memory; and
a processor coupled with the memory, the processor configured to perform a computer-implemented method for providing a query response, the computer-implemented method comprising:
receiving a domain-specific knowledge graph;
generating a first property graph schema, property graph schema includes vertices, edges, and properties of the domain-specific knowledge graph, wherein the first property graph schema is generated based on an ontology of the domain-specific knowledge graph;
generating a second property graph schema from a copy of the first property graph schema that is optimized by applying one or more types of relationships in the first property graph schema;
instantiating a property graph using the second property graph schema;
receiving a query to obtain particular data from the domain-specific knowledge graph; and
responding to the query using the property graph.

### Claim 11 (depends on 10)

The system of claim 10, wherein the method further comprises optimizing the first property graph schema by modifying one or more inheritance relationships in the first property graph schema, wherein modifying an inheritance relationship comprises:
determining a set of child data-properties of a child node of the inheritance relationship, and a set of parent data-properties of a parent node of the inheritance relationship;
computing a similarity score for the child data-properties and the parent data-properties;
in response to the similarity score being greater than a first threshold, associating the child data-properties with the parent node, and otherwise associating the parent data-properties with the child node; and
removing the inheritance relationship from the first property graph schema.

### Claim 12 (depends on 10)

The system of claim 10, wherein the method further comprises optimizing the first property graph schema by modifying one or more union relationships in the first property graph schema, wherein the optimizing a union relationship comprises, for a plurality of member nodes associated with the union relationship, adding an edge between each pair of member nodes from the plurality of member nodes.

### Claim 13 (depends on 10)

The system of claim 10, wherein the method further comprises optimizing, by the computing device, the first property graph schema by modifying a 1:M relationship in the first property graph schema, the optimization comprising:
adding, to a list of properties of a source of the 1:M relationship, all of the properties of a destination of the 1:M relationship.

### Claim 14 (depends on 10)

The system of claim 10, wherein the method further comprises optimizing, by the computing device, the first property graph schema by modifying a M:N relationship in the first property graph schema, the optimization comprising addressing the M:N relationship as multiple 1:M relationships, wherein optimizing a 1:M relationship in the ontology comprises:
adding, to a list of properties of a source of the 1:M relationship, all of the properties of a destination of the 1:M relationship.

### Claim 15 (depends on 10)

The system of claim 10, wherein the method further comprises optimizing the first property graph schema by modifying a 1:1 relationship in the first property graph schema, the optimization comprising:
adding, to the second property graph schema, a new node that is generated by merging a source node and a destination node of the 1:1 relationship; and
removing, from the second property graph schema, the source node, the destination node, and the 1:1 relationship.

### Claim 16 (depends on 10)

The system of claim 10, wherein optimizing the property graph schema comprises:
receiving the storage space limit as an input, the storage space limit indicating an amount of storage space budgeted for optimizing the property graph schema;
determining the order of all relationships in the first property graph schema based on a cost-benefit model; and
selecting a subset of relationships in the first property graph schema that maximize the total benefit until the storage space limit is exhausted.

### Claim 17 (depends on 10)

The system of claim 10, wherein optimizing the property graph schema comprises:
receiving the storage space limit as an input, the storage space limit indicating an amount of storage space budgeted for optimizing the property graph schema;
determining the order of all concepts in the first property graph schema based on the centrality analysis; and
iterating through the concepts from high centrality score to lower and apply relationship rules to each concept until the storage space limit is exhausted.

### Claim 18

A computer program product comprising a memory storage device having computer executable instructions stored thereon, the computer executable instructions when executed by a processing unit cause the processing unit to perform a method comprising:
receiving a domain-specific knowledge graph;
generating a first property graph schema, a property graph schema includes vertices, edges, and properties of the domain-specific knowledge graph, wherein the first property graph schema is generated based on an ontology of the domain-specific knowledge graph;
generating a second property graph schema from a copy of the first property graph schema that is by applying one or more types of relationships in the first property graph schema;
instantiating a property graph using the second property graph schema;
receiving a query to obtain particular data from the domain-specific knowledge graph; and
responding to the query using the property graph.

### Claim 19 (depends on 18)

The computer program product of claim 18, wherein the method further comprises, optimizing the first property graph schema by modifying one or more inheritance relationships in the first property graph schema, wherein modifying an inheritance relationship in the ontology comprises:
determining a set of child data-properties of a child node of the inheritance relationship, and a set of parent data-properties of a parent node of the inheritance relationship;
computing a similarity score for the child data-properties and the parent data-properties;
in response to the similarity score being greater than a first threshold, associating the child data-properties with the parent node, and otherwise associating the parent data-properties with the child node; and
removing the inheritance relationship from the first property graph schema.

### Claim 20 (depends on 18)

The computer program product of claim 18, wherein the method further comprises, optimizing the first property graph schema by modifying one or more union relationships, wherein the optimizing a union relationship comprises, for a plurality of member nodes associated with the union relationship, adding an edge between each pair of member nodes from the plurality of member nodes.

### Claim 21 (depends on 18)

The computer program product of claim 18, wherein the method further comprises, optimizing the first property graph schema by modifying a 1:1 relationship in the first property graph schema, the optimization comprising:
adding, to the second property graph schema, a new node that is generated by merging a source node and a destination node of the 1:1 relationship; and
removing, from the second property graph schema, the source node, the destination node, and the 1:1 relationship.

### Claim 22 (depends on 21)

The computer program product of claim 21, wherein the method further comprises, optimizing, by the computing device, the first property graph schema by modifying a 1:M relationship in the first property graph schema by addressing the M:N relationship as multiple 1:M relationships, wherein optimizing a 1:M relationship comprises:
adding, to a list of properties of a source of the 1:M relationship, all of the properties of a destination of the 1:M relationship.

### Claim 23

A computer-implemented method for providing a query response, the computer-implemented method comprising:
receiving, by a computing device, a domain-specific knowledge graph;
generating, by the computing device, a first property graph schema, a property graph schema includes vertices, edges, and properties of the domain-specific knowledge graph, wherein the first property graph schema is generated based on an ontology of the domain-specific knowledge graph; and
generating, by the computing device, a second property graph schema, which is a replica of the first property graph schema, and optimizing the second property graph schema by applying one or more types of relationships in the first property graph schema, wherein optimizing the second property graph schema comprises:
receiving a storage space limit as an input, the storage space limit indicating an amount of storage space budgeted for optimizing the second property graph schema;
determining the order of all relationships in the first property graph schema based on a cost-benefit model; and
selecting a subset of relationships in the first property graph schema that maximize the total benefit until the storage space limit is exhausted.

### Claim 24

A computer-implemented method for providing a query response, the computer-implemented method comprising:
receiving, by a computing device, a domain-specific knowledge graph;
generating, by the computing device, a first property graph schema, a property graph schema includes vertices, edges, and properties of the domain-specific knowledge graph, wherein the first property graph schema is generated based on an ontology of the domain-specific knowledge graph; and
generating, by the computing device, a second property graph schema, which is a replica of the first property graph schema, and optimizing the second property graph schema by applying one or more types of relationships in the first property graph schema, wherein optimizing the second property graph schema comprises:
receiving the storage space limit as an input, the storage space limit indicating an amount of storage space budgeted for optimizing the property graph schema;
determining the order of all concepts in the first property graph schema based on the centrality analysis; and
iterating through the concepts from high centrality score to lower and apply relationship rules to each concept until the storage space limit is exhausted.
