Translation system and method for SPARQL queries

• US 8,275,784 B2
• Filed: 03/26/2010
• Issued: 09/25/2012
• Est. Priority Date: 03/31/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cao, Feng, Hu, Gang, Ma, Li, Pan, Yue, Sun, Xing Zhi
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US12/732,240
• Publication Number:
  US 20100250577A1
• Time in Patent Office: 914 Days
• Field of Search: 707/759, 707/760, 707/764, 707/771, 707999003-999005
• US Class Current: 707/760
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation

Abstract

A computer-implemented system and method for translating a SPARQL query. The system includes: a parser/lexer for parsing the SPARQL query; a hidden negative pattern detector for detecting a hidden negative pattern in the parsed SPARQL query; a hidden negative pattern translator for translating the detected hidden negative pattern into an explicit negative pattern; a separator for separating the explicit negative pattern from a positive pattern in the parsed SPARQL query; a negative pattern translator for translating the explicit negative pattern into a negative portion of an SQL statement; a positive pattern translator for translating the positive pattern into a positive portion of the SQL statement; and an SQL statement combiner for combining the negative portion of the SQL statement with the positive portion of the SQL statement.

Claims

1. A computer-implemented method for translating a SPARQL query, comprising the steps of:

parsing said SPARQL query, wherein said parsing step is performed using a parser/lexer;

detecting a hidden negative pattern in said parsed SPARQL query, wherein said detecting step is performed using a hidden negative pattern detector;

translating said detected hidden negative pattern into an explicit negative pattern, wherein said translating step is performed using a hidden negative pattern translator;

separating said explicit negative pattern from a positive pattern in said parsed SPARQL query, wherein said separating step is performed using a separator;

translating said explicit negative pattern into a negative portion of an SQL statement, wherein said step of translating said explicit negative pattern is performed using a negative pattern translator;

translating said positive pattern into a positive portion of said SQL statement, wherein said step of translating said positive pattern is performed using a positive pattern translator; and

combining said negative portion of said SQL statement with said positive portion of said SQL statement, wherein said combining step is performed using a combiner.

2. The method according to claim 1, wherein said hidden negative pattern detection step further comprises the steps of:

normalizing a filter condition in said SPARQL query to a disjunctive normal form, wherein said normalizing step is performed using a normalizer;

extracting, from said filter condition, a condition having a pair of unequal variables, wherein said extracting step is performed using a condition extractor;

extracting connected sub-graphs represented by respective triples in said SPARQL query and matching respective maximal connected similar sub-graphs, wherein said step of extracting connected sub-graphs is performed by using a connected sub-graphs extractor; and

matching hidden negative patterns in accordance with said respective maximal connected similar sub-graphs and differences between said respective maximal connected similar sub-graphs and corresponding connected sub-graphs, wherein said matching step is performed using a hidden negative pattern matching unit.

3. The method according to claim 1, wherein said hidden negative pattern translation step further comprises the steps of:

removing a triple in said hidden negative pattern duplicated with those in said positive pattern, wherein said removing step is performed using a triplet removing unit;

replacing variables in an additional triple in said hidden negative pattern by corresponding variables in said positive pattern, wherein said replacing step is performed using a variable replacing unit; and

appending a flag representing a “

NOT”

logic to said translated additional triple, wherein said appending step is performed using an appending unit.

4. The method according to claim 1, wherein said negative pattern translation step further comprises the steps of:

searching SPARQL matched units to be translated, wherein said searching step is performed by a searching unit;

establishing a new SELECT statement using a SELECT statement establishing unit;

generating a WHERE clause using a WHERE clause generating unit;

generating a SELECT clause using a SELECT clause generating unit;

generating a FROM clause using a FROM clause generating unit;

maintaining a variable mapping table using a table maintaining unit; and

determining whether there exists other matched units that have not been translated, wherein said determining step is performed using a determining unit.

5. The method according to claim 1, wherein said combining step further comprises:

combining, one by one, said negative portion of said SQL statement and said combined positive portion of said SQL statement into a resulting SQL statement, wherein said step of combining one by one is performed using a serial combiner.

6. The method according to claim 5, wherein said resulting SQL statement comprises an EXIST command.

7. The method according to claim 5, wherein said resulting SQL statement comprises a LEFT-OUTER-JOIN command.

8. The method according to claim 1, wherein said explicit negative pattern is in the form of a flag representing a “

NOT”

logic appended to a triple.

9. A computer-implemented method for translating a SPARQL query, comprising the steps of:

parsing said SPARQL query, wherein said parsing step is performed using a parser/lexer;

detecting a hidden negative pattern in said parsed SPARQL query, and separately outputting said detected hidden negative pattern and a positive pattern, wherein said detecting step is performed using a hidden negative pattern detector;

translating said detected hidden negative pattern into a negative portion of an SQL statement, wherein said translating step is performed using a hidden negative pattern translator;

translating said positive pattern into a positive portion of said SQL statement, wherein said step of translating said positive pattern is performed using a positive pattern translator; and

combining said negative portion of said SQL statement with said positive portion of said SQL statement, wherein said combining step is performed using a combiner.

10. The method according to claim 9, wherein said negative pattern direct translation step further comprises the steps of:

identifying an additional triple in said hidden negative pattern, wherein said identifying step is performed using a triple identifying unit;

searching a SPARQL matched unit having said additional triple and a filter condition, wherein said searching step is performed using a searching unit;

establishing a new SELECT statement using a SELECT statement establishing unit;

generating a WHERE clause using a WHERE clause generating unit;

generating a SELECT clause using a SELECT clause generating unit;

generating a FROM clause using a FROM clause generating unit;

maintaining a variable mapping table using a table maintaining unit; and

determining whether there exists another matched unit that has not been translated, wherein said determining step is performed using a determining unit.