TRANSLATION SYSTEM AND METHOD FOR SPARQL QUERIES

• US 20100250577A1
• Filed: 03/26/2010
• Published: 09/30/2010
• Est. Priority Date: 03/31/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cao, Feng, Ma, Li, Pan, Yue, Hu, Gang, Sun, Xing Zhi
• Granted Patent: US 8,275,784 B2
• Time in Patent Office: Days
• 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 system for translating a SPARQL query, comprising:

a parser/lexer for parsing said SPARQL query;

a hidden negative pattern detector for detecting a hidden negative pattern in said parsed SPARQL query;

a hidden negative pattern translator for translating said detected hidden negative pattern into an explicit negative pattern;

a separator for separating said explicit negative pattern from a positive pattern in said parsed SPARQL query;

a negative pattern translator for translating said explicit negative pattern into a negative portion of an SQL statement;

a positive pattern translator for translating said positive pattern into a positive portion of said SQL statement; and

an SQL statement combiner for combining said negative portion of said SQL statement with said positive portion of said SQL statement.

2. The system according to claim 1, wherein said hidden negative pattern detector comprises:

a normalizer for normalizing a filter condition in said SPARQL query to a disjunctive normal form;

a condition extractor for extracting, from said filter condition, a condition having a pair of unequal variables;

a connected sub-graphs extractor for extracting connected sub-graphs represented by respective triples in said SPARQL query and matching respective maximal connected similar sub-graphs; and

a hidden negative pattern matching unit for matching said hidden negative pattern in accordance with the respective maximal connected similar sub-graphs and differences between said respective maximal connected similar sub-graphs and corresponding said extracted connected sub-graphs.

3. The system according to claim 1, wherein said hidden negative pattern translator comprises:

a triplet removing unit for removing a triple in said hidden negative pattern duplicated with those in said positive pattern;

a variable replacing unit for replacing variables in an additional triple in said hidden negative pattern by corresponding variables in said positive pattern; and

an appending unit for appending a flag representing a “

NOT”

logic to said translated additional triple.

4. The system according to claim 1, wherein said negative pattern translator comprises:

a searching unit for searching SPARQL matched units to be translated;

a SELECT statement establishing unit for establishing a new SELECT statement;

a WHERE clause generating unit for generating a WHERE clause;

a SELECT clause generating unit for generating a SELECT clause;

a FROM clause generating unit for generating a FROM clause;

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

a determining unit for determining whether there exists other matched units that have not been translated.

5. The system according to claim 1, wherein said SQL statement combiner comprises:

a serial combiner for 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.

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

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

8. The system 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, 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.

10. The method according to claim 9, 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.

11. The method according to claim 9, 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.

12. The method according to claim 9, 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.

13. The method according to claim 9, 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.

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

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

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

NOT”

logic appended to a triple.

21. A computer program product for translating a SPARQL query, said computer program product comprising computer program instructions for carrying out the steps of the method according to claim 9, wherein said computer program instructions are stored on a computer readable storage medium.

17. A computer-implemented system for translating a SPARQL query, comprising:

a parser/lexer for parsing the SPARQL query;

a pattern detection separator for detecting a hidden negative pattern in said parsed SPARQL query, and separately outputting said detected hidden negative pattern and a positive pattern;

a negative pattern direct translator for translating said detected hidden negative pattern into a negative portion of an SQL statement;

a positive pattern translator for translating said positive pattern into a positive portion of said SQL statement; and

a combiner for combining said negative portion of said SQL statement with said positive portion of said SQL statement.

18. The system according to claim 17, wherein said negative pattern direct translator comprises:

a triple identifying unit for identifying an additional triple in said hidden negative pattern;

a searching unit for searching a SPARQL matched unit having said additional triple and a filter condition;

a SELECT statement establishing unit for establishing a new SELECT statement;

a WHERE clause generating unit for generating a WHERE clause;

a SELECT clause generating unit for generating a SELECT clause;

a FROM clause generating unit for generating a FROM clause;

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

a determining unit for determining whether there exists another matched unit that has not been translated.

19. 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.

20. The method according to claim 19, 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.

22. A computer program product for translating a SPARQL query, said computer program product comprising computer program instructions for carrying out the steps of the method according to claim 19, wherein said computer program instructions are stored on a computer readable storage medium.