TRANSLATION OF A SPARQL QUERY TO A SQL QUERY

• US 20160103931A1
• Filed: 10/09/2014
• Published: 04/14/2016
• Est. Priority Date: 10/09/2014
• Status: Active Grant

• Current Assignee: Maplebear Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: APPAVU, Rajendran
• Granted Patent: US 9,703,830 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/24526 Internal representations for queries

Abstract

In the processing of a query while being translated from the SPARQL language to the SQL language, a manner of navigation through the one or more graphs is provided. The plurality of the nodes in the one or more graphs generated from the query is identified. The plurality of the nodes are assigned a priority and arranged in the priority queue based on the assigned priorities. The node with a highest assigned priority is selected each time for execution of the query from the selected node. The one or more graphs are navigated from the selected node to traverse to the one or more nodes connected with the selected node. An access plan element is generated corresponding to the selected nodes and the one or more traversed nodes.

Claims

1. A method of translating a Simple Protocol and RDF Query Language (SPARQL) query into a Structured Query Language (SQL) query, the method comprising:

generating one or more graphs from the SPARQL query, wherein the one or more graphs comprise a plurality of nodes;

assigning a priority to the plurality of nodes and generating a priority queue based on the assigned priority;

selecting the node having a highest assigned priority from the priority queue;

navigating the one or more graphs to traverse to one or more nodes of the plurality of nodes connected to the selected node; and

generating an access plan element of the SQL query for the one or more nodes traversed and the selected node.

2. The method of claim 1, further comprising:

updating the priority of the plurality of nodes in the priority queue, wherein the updating of the priority of the plurality of nodes comprises reassigning the priority to the one or more nodes of the plurality of the nodes having a variable identified during navigation.

3. The method of claim 1, wherein at least two of the plurality of nodes are connected with one another through an edge.

4. The method of claim 3, wherein navigating the one or more graphs to traverse to the one or more nodes connected to the selected node comprises:

identifying the one or more edges associated with the selected node in the one or more graphs; and

navigating the one or more graphs to reach the one or more nodes connected to the selected node through the one or more associated edges.

5. The method of claim 4, wherein the one or more graphs are navigated simultaneously through the one or more associated edges to reach the one or more nodes connected to the selected node.

6. The method of claim 1, wherein the priority is assigned to the plurality of nodes based on a criteria, the criteria comprising one or more of the following:

a high priority to the node being a constant and a low priority to the node being the variable;

priority being assigned to the node being constant and appearing across the one or more graphs is assessed based on scope; and

statistics are used to assign priority among the one or more nodes being the constant.

7. The method of claim 6, wherein whether the node is one of the constant and the variable is determined based on the query.

8. A computer program product for translating a Simple Protocol and RDF Query Language (SPARQL) query into a Structured Query Language (SQL) query, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal per se, the program instructions executable by a processor to cause the processor to perform a method comprising:

generating one or more graphs from the SPARQL query, wherein the one or more graphs comprise a plurality of nodes;

assigning a priority to the plurality of nodes and generate a priority queue based on the assigned priority;

selecting the node having a highest assigned priority from the priority queue;

navigating the one or more graphs to traverse to one or more nodes of the plurality of nodes connected to the selected node; and

generating an access plan element of the SQL query for the one or more nodes traversed and the selected node.

9. The computer program product of claim 8, wherein the method further comprises updating the priority of the plurality of nodes in the priority queue, wherein the updating of the priority of the plurality of nodes comprises reassigning the priority to one or more said nodes of the plurality of the nodes having a variable identified during navigation.

10. The computer program product of claim 8, wherein at least two of the plurality of nodes are connected with one another through an edge.

11. The computer program product of claim 10, wherein navigating the one or more graphs to traverse to the one or more nodes connected to the selected node comprises:

identifying the one or more edges associated with the selected node in the one or more graphs; and

navigating the one or more graphs to reach the one or more nodes connected to the selected node through the one or more associated edges.

12. The computer program product of claim 11, wherein the one or more graphs are navigated simultaneously through the one or more associated edges to reach the one or more nodes connected to the selected node.

13. The computer program product of claim 8, wherein the priority is assigned to the plurality of nodes based on a criteria, the criteria comprising one or more of the following:

a high priority to the node being a constant and a low priority to the node being the variable;

priority being assigned to the node being constant and appearing across the one or more graphs is assessed based on scope; and

statistics are used to assign priority among the one or more nodes being the constant.

14. A system for translating a Simple Protocol and RDF Query Language (SPARQL) query into a Structured Query Language (SQL) query, the system comprising:

a processor; and

a computer readable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal per se, the program instructions executable by a processor to cause the processor to perform a method comprising;

generating one or more graphs from the SPARQL query, wherein the one or more graphs comprise a plurality of nodes;

assigning a priority to the plurality of nodes and generate a priority queue based on the assigned priority;

selecting the node having a highest assigned priority from the priority queue;

navigating the one or more graphs to traverse to one or more nodes of the plurality of nodes connected to the selected node; and

generating an access plan element of the SQL query for the one or more nodes traversed and the selected node.

15. The system of claim 14, wherein the method further comprise updating the priority of the plurality of nodes in the priority queue, wherein the updating of the priority of the plurality of nodes comprises reassigning the priority to the one or more nodes of the plurality of the nodes having a variable identified during navigation.

16. The system of claim 14, wherein at least two of the plurality of nodes are connected with one another through an edge.

17. The system of claim 16, wherein navigating the one or more graphs to traverse to the one or more nodes connected to the selected node comprises:

identifying the one or more edges associated with the selected node in the one or more graphs; and

navigating the one or more graphs to reach the one or more nodes connected to the selected node through the one or more associated edges.

18. The system of claim 17, wherein the one or more graphs are navigated simultaneously through the one or more associated edges to reach the one or more nodes connected to the selected node.

19. The system of claim 14, wherein the priority is assigned to the plurality of nodes based on a criteria, the criteria comprising one or more of the following:

a high priority to the node being a constant and a low priority to the node being the variable;

priority being assigned to the node being constant and appearing across the one or more graphs is assessed based on scope; and

statistics are used to assign priority among the one or more nodes being the constant.

20. The system of claim 14, wherein whether the node is one of the constant and the variable is determined based on the query.