Graph database query handling method and apparatus

• US 9,454,567 B2
• Filed: 03/28/2014
• Issued: 09/27/2016
• Est. Priority Date: 03/28/2013
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Hu, Bo, Carvalho, Nuno
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): Nguyen, Cindy
• Application Number:
  US14/229,158
• Publication Number:
  US 20140297621A1
• Time in Patent Office: 914 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

A querying method for a database of graph data encoded as triples being stored on storage servers. The method including dividing a query into a plurality of result criteria triple patterns which query results match, each triple pattern element being either: a single value triple pattern element; or a variable value triple pattern element specifying an ID of a variable. The method includes forming one or more sub-queries each having triple patterns having the same single value triple pattern element or specifying the same ID of a variable as a variable value triple pattern element, issuing each formed sub-query to each of the servers, and receiving triples satisfying a sub-query as results from the servers and using the sub-query results in as a response to the query.

Claims

1. A querying method for a database of graph data encoded as triples, the triples each comprising values of three triple elements and being stored on a plurality of storage servers, the method comprising:

at a centralized database controller, a dividing step comprising dividing a query into a plurality of result criteria, the result criteria being a triple pattern which some or all query results must match, each triple pattern is composed of three triple pattern elements each corresponding to a different one of the three triple elements;

each triple pattern element being either one of;

a single value triple pattern element specifying a single value of the corresponding triple element which triples must have to match the triple pattern;

or

a variable value triple pattern element specifying an ID of a variable, the ID being attributed to values of the corresponding triple elements of triples matching the triple pattern;

at the centralized database controller, a sub-query forming step comprising, forming one or more sub-queries each comprising two or more triple patterns having the same single value triple pattern element or specifying the same ID of a variable as a variable value triple pattern element;

at the centralized database controller, a sub-query issuing step comprising issuing each formed sub-query to each of the plurality of storage servers;

at each storage server;

receiving the formed sub-queries,

scanning the triples stored on the storage server for triples satisfying the result criteria of each of the received sub-queries, and,

for each received sub-query, transferring a copy of any triple satisfying the result criteria of the sub-query to the other storage servers and/or the centralized database controller as a sub-query result of the sub-query, wherein the scanning comprises;

identifying each different triple pattern from among the received formed sub queries;

prioritizing the identified different triple patterns with triple patterns having more variable value triple pattern elements being prioritized below triple patterns having fewer variable value triple pattern elements;

in order of priority, for each of the triple patterns, scanning the triples stored on the storage server for triples matching the triple pattern to obtain an intermediate result set of triples; and

obtaining sub-query results by combining the intermediate result set of triples for

each of the triple patterns in sub-queries having more than one triple pattern, and by applying filtering conditions to the intermediate result set of triples for each of the triple patterns in sub-queries having filtering conditions;

the method further comprising;

at the centralized database controller, a query result preparing step comprising

receiving the sub-query results from the plurality of storage servers and using the sub-query results to prepare query results as a response to the query.

2. A method according to claim 1, wherein result criteria further comprise one or more filtering conditions each of which define, for one or more particular IDs from among the IDs of variables, a range within which values of the triple element attributed the ID must fall for a triple to be included in the query results;

and

the sub-query forming step further comprises forming one or more sub-queries each comprising a triple pattern specifying an ID of a variable as a variable value triple pattern element and a filtering condition defining a range for the specified ID.

3. A method according to claim 2, the sub-query forming step further comprising, when one of the filtering conditions defines the range within which values of the triple element attributed the ID must fall for a triple to be included in the query results with reference to another ID of a variable, joining the sub-queries for the ID and the another ID into a single sub-query.

4. A method according to claim 1, wherein the sub-query forming step comprises, for each single value triple pattern element or ID of a variable appearing in more than one result criterion, forming a sub-query comprising a copy of every result criterion having that single value triple pattern element or ID of a variable.

5. A method according to claim 1, wherein the query result preparing step further comprises, for each of the formed sub-queries which comprise two or more triple patterns having the same ID of a variable as a variable value triple pattern element:

receiving from each of the storage servers individual triple pattern results comprising a copy of every triple satisfying at least one of the two or more triple patterns;

removing from the received individual triple pattern results the copies of the triples stored as sub-query results for that sub-query; and

searching the remaining received individual triple pattern results for triples satisfying the result criteria of the sub-query, and storing those triples as sub-query results.

6. A method according to claim 1, further comprising at each of the storage servers, for a sub-query comprising two or more triple patterns specifying the same ID of a variable as a variable value triple pattern element, assigning one of the two or more triple patterns as a first triple pattern and obtaining the intermediate result set of triples for each of the one or more other triple patterns in the sub-query from each of the other storage servers, and, for each of triples found to match the first triple pattern on the storage server, scanning the obtained intermediate result sets of triples to identify pairs or groups of triples satisfying the sub-query.

7. A method according to claim 1, wherein:

the query result preparing step includes obtaining the query results by combining the sub-query results of each of the sub-queries according to the query.

8. A method according to claim 1, wherein the query is a SPARQL query (SPARQL Protocol and RDF Query Language).

9. A non-transitory computer readable storage medium storing a computer program which, when executed by one or more computing apparatuses, causes the one or more computing apparatuses to perform the method according to any of claim 1.

10. A system comprising a database controller for a database of graph data encoded as triples, and a plurality of storage servers for storing the database, the triples each comprising values of three triple elements and being stored on the plurality of storage servers, the database controller comprising:

a processor; and

a memory which stores a plurality of instructions, which when executed by the processor, cause the processor to execute,

dividing a query into a plurality of result criteria, the result criteria comprising a plurality of triple patterns which query results must match, each triple pattern being composed of three triple pattern elements each corresponding to a different one of the three triple elements;

each triple pattern element being either one of;

a single value triple pattern element specifying a single value of the corresponding triple element which triples must have to match the triple pattern; and

a variable value triple pattern element specifying an ID of a variable, the ID being attributed to values of the corresponding triple elements of triples matching the triple pattern

forming one or more sub-queries each comprising two or more triple patterns having the same single value triple pattern element or specifying the same ID of a variable as a variable value triple pattern element; and

issuing each formed sub-query to each of the plurality of storage servers;

each of the storage servers being configured to;

receive the formed sub-queries, scan the triples stored on the storage server for triples satisfying the result criteria of each of the received sub-queries, and, for each received sub-query, transfer a copy of any triple satisfying the result criteria of the sub-query to the other storage servers and/or the centralized database controller as a sub-query result of the sub-query, wherein the scanning comprises;

identifying each different triple pattern from among the received formed sub-queries;

prioritizing the identified different triple patterns with triple patterns having more variable value triple pattern elements being prioritized below triple patterns having fewer variable value triple pattern elements;

in order of priority, for each of the triple patterns, scanning the triples stored on the storage server for triples matching the triple pattern to obtain an intermediate result set of triples; and

obtaining sub-query results by combining the intermediate result set of triples for each of the triple patterns in sub-queries having more than one triple pattern, and by applying filtering conditions to the intermediate result set of triples for each of the triple patterns in sub-queries having filtering conditions;

the processor triples satisfying at least one formed sub-query as sub-query results from the plurality of storage servers and use the sub-query results to prepare query results as a response to the query.

11. A computer program which, when executed by one or more computing apparatuses, causes the one or more computing apparatuses to function as the database controller according to claim 10.