Ontology-based graph query optimization

Patent metadata

Field	Value
Publication number	US-11461318-B2
Application number	US-201715445228-A
Country	US
Kind code	B2
Filing date	Feb 28, 2017
Priority date	Feb 28, 2017
Publication date	Oct 4, 2022
Grant date	Oct 4, 2022

Abstract

Examples of the present disclosure describe systems and methods for ontology-based graph query optimization. In an example, ontology data relating to a graph or isolated collection may be collected. The ontology data may comprise uniqueness and topology information and may be used to reformulate a query in order to yield a query that is more performant than the original query when retrieving target information from a graph. In an example, reformulating a query may comprise reordering one or more parameters of the query relating to resources, relationships, and/or properties based on uniqueness information. In another example, the query may be reformulated by modifying the resource type to which the query is anchored based on the topology information. The reformulated query may then be executed to identify target information in the isolated collection, thereby identifying the same target information as the original query, but in a manner that is more performant.

First claim

What is claimed is:

1. A system comprising:
at least one processor; and
a memory storing instructions that when executed by the at least one processor perform a set of operations comprising:
receiving a query for data stored in an isolated collection, wherein the query comprises a plurality of parameters;
accessing ontology data relating to data in the isolated collection, wherein the ontology data comprises uniqueness data relating to the data in the isolated collection;
identifying, using at least the uniqueness data, a level of uniqueness for each of the parameters;
determining, for each of the parameters, a query order based on the uniqueness data identified for the parameter;
generating a revised query based on the received query, wherein the revised query is comprised of the parameters in the determined query order; and
executing the revised query to identify data in the isolated collection associated with the revised query.

2. The system of claim 1 , wherein the ontology data further comprises topology data, and the set of operations further comprises:
identifying an anchor and one or more resource types for the query, wherein the anchor relates to at least one of the one or more resource types;
identifying, using the topology data, an average number of relationships for each of the one or more resource types; and
determining, using the average number of relationships for each of the one or more resource types, whether the anchor for the query should relate to a different group of one or more of the one or more of resource types.

3. The system of claim 2 , wherein generating the revised query further comprises:
when it is determined that the anchor query should relate to a different group of one or more of the one or more resource types, generating the revised query such that the different group of one or more of the one or more resource types relates to the anchor of the more performant query.

4. The system of claim 1 , wherein the isolated collection is associated with a related isolated collection, and the ontology data was generated using the related isolated collection.

5. The system of claim 1 , wherein the ontology data is updated when data in the isolated collection is at least one of added, modified, and deleted.

6. The system of claim 1 , wherein the ontology data is updated periodically.

7. The system of claim 1 , wherein the revised query is more efficient than the received query when executed to identify data in the isolated collection.

8. A computer-implemented method for revising a query for data stored in an isolated collection, the method comprising:
receiving a query for data stored in an isolated collection;
identifying an anchor and a plurality of resource types for the query, wherein the anchor is at least one of the resource types;
accessing ontology data relating to data in the isolated collection, wherein the ontology data comprises topology data;
identifying, using the topology data, an average number of relationships for each of the resource types;
determining, using the average number of relationships for each of the resource types, whether the anchor for the query should be a different group of one or more of the resource types;
when it is determined that the anchor query should be a different group of resource types, generating a revised query such that the different group of resource types is a new anchor for the revised query; and
executing the revised query to identify data in the isolated collection associated with the revised query.

9. The computer-implemented method of claim 8 , wherein the ontology data further comprises uniqueness data, the method further comprising:
identifying one or more parameters of the query;
identifying, using the uniqueness data, a level of uniqueness for each of the one or more parameters; and
determining, for each of the one or more parameters, a query order based on the uniqueness data identified for the parameter.

10. The computer-implemented method of claim 9 , wherein generating the revised query further comprises reformulating the query such that one or more parameters of the revised query are in the determined query order.

11. The computer-implemented method of claim 8 , wherein the isolated collection is associated with a related isolated collection, and the ontology data was generated from the related isolated collection.

12. The computer-implemented method of claim 8 , wherein the ontology data is updated when data in the isolated collection is at least one of added, modified, and deleted.

13. The computer-implemented method of claim 8 , wherein the ontology data is updated periodically.

14. The computer-implemented method of claim 8 , wherein the ontology data is stored in a PATRICIA tree.

15. A method for generating a revised query for data stored in an isolated collection, the method comprising:
receiving a query for data stored in an isolated collection, wherein the query comprises a plurality of parameters;
accessing ontology data relating to data in the isolated collection, wherein the ontology data comprises uniqueness data relating to the data in the isolated collection;
identifying, using at least the uniqueness data, a level of uniqueness for each of the parameters;
determining, for each of the parameters, a query order based on the uniqueness data identified for the parameter;
generating a revised query based on the received query, wherein the revised query is comprised of the parameters in the determined query order; and
executing the revised query to identify data in the isolated collection associated with the revised query.

16. The method of claim 15 , wherein the ontology data further comprises topology data, and the method further comprises:
identifying an anchor and one or more resource types for the query, wherein the anchor relates to at least one of the one or more resource types;
identifying, using the topology data, an average number of relationships for each of the one or more resource types; and
determining, using the average number of relationships for each of the one or more resource types, whether the anchor for the query should relate to a different group of one or more of the one or more of resource types.

17. The method of claim 16 , wherein generating the revised query further comprises:
when it is determined that the anchor query should relate to a different group of one or more of the one or more resource types, generating the more performant query such that the different group of one or more of the one or more resource types relates to the anchor of the more performant query.

18. The method of claim 15 , wherein the isolated collection is associated with a related isolated collection, and the ontology data was generated using the related isolated collection.

19. The method of claim 15 , wherein the ontology data is updated when data in the isolated collection is at least one of added, modified, and deleted.

20. The method of claim 15 , wherein the revised query is more efficient than the received query when executed to identify data in the isolated collection.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Kreutzer Tor
• Johansen Amund Kronen
• Valvåg Steffen Viken
• Kvalnes Åge
• Eidesen Dag
• Heen Peter Dahle
• Karlberg Jan-Ove
• Vettorel Daniele

Classifications

• G06F16/2453 Primary

  Query optimisation · CPC title

• G06F16/367

  Ontology · CPC title

• G06F16/24534 Primary

  Query rewriting; Transformation · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title