-
Notifications
You must be signed in to change notification settings - Fork 4
Query transformation through rules
ericprud edited this page Sep 8, 2012
·
1 revision
SWObjects was designed as a query transformation and execution engine. In many cases, we wish to query a virtual graph, created by some rules applied to some other (potentially virtual) graph. Some of these graphs may be the direct graph implied by a relational database; in this case, the final query is transformed to SQL and performed against a database like mysql or postgresql.
The following example is taken from the first example in A Direct Mapping of Relational Data to RDF. The following mapping rule expresses this data as FOAF:
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX empP: <http://hr.example/DB/Employee#>
PREFIX task: <http://hr.example/DB/Task#>
SHAREDVARS DRACONIAN
INTERSECTION {<Emp_TaskToFoaf>}?emp {<Emp_TaskToFoaf>}?man
<Emp_TaskToFoaf>
CONSTRUCT { ?emp foaf:last_name ?wname .
?emp foaf:knows ?man .
?man foaf:last_name ?mname }
WHERE { ?emp empP:lastName ?wname .
?pair task:drone ?emp .
?pair task:manager ?man .
?man empP:lastName ?mname }
Given a user query
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>
SELECT ?lname {
?who foaf:last_name ?lname .
?who foaf:knows ?whom .
?whom foaf:knows ?whom2 .
?whom2 foaf:last_name 'Smith'^^xsd:string }
The mapping algorithms can be invoked from the command line tool sparql:
sparql -8 --debug 1 -npm Emp_TaskToFoaf.map two.rq
- -8 : unicode box characters
- --debug 1 : set debug level to 1 (currently any non-zero value is the same)
- -n : no execute -- don't run the query.
- -p : print the final query.
- Emp_TaskToFoaf.map : SPIN rules file (above) to create the virtual graph with FOAF arcs.
- two.rq : a query (above) which is satisfied by two invokations of Emp_TaskToFoaf.map.
Debug level: 1. Queued reading default map from Emp_TaskToFoaf.map. Query resource: two.rq. Switching to utf-8. Execution suppressed. + Stream constructed to read file Emp_TaskToFoaf.map.
Emp_TaskToFoaf.map has one rule in it, labeled .
adding rule: <Emp_TaskToFoaf> {
?emp <http://hr.example/DB/Employee#lastName> ?wname .
?pair <http://hr.example/DB/Task#drone> ?emp .
?pair <http://hr.example/DB/Task#manager> ?man .
?man <http://hr.example/DB/Employee#lastName> ?mname .
}
=> {
?emp <http://xmlns.com/foaf/0.1/last_name> ?wname .
?emp <http://xmlns.com/foaf/0.1/knows> ?man .
?man <http://xmlns.com/foaf/0.1/last_name> ?mname .
}
+ Stream constructed to read file two.rq.
Transforming user query by applying 1 rule maps.
The query mapper visits each graph pattern in the user's query. In this case, there is only one graph pattern, a basic graph pattern with four triple patterns.
transforming bgp: {
?who <http://xmlns.com/foaf/0.1/last_name> ?lname .
?who <http://xmlns.com/foaf/0.1/knows> ?whom .
?whom <http://xmlns.com/foaf/0.1/knows> ?whom2 .
?whom2 <http://xmlns.com/foaf/0.1/last_name> "Smith"^^<http://www.w3.org/2001/XMLSchema#string> .
}
There are four possible ways that the mapping rule can be instantiated to produce the graph pattern in the user's query.
-> [[
alternative: <Emp_TaskToFoaf>
┌────────┬────────┬────────┬───────┬────────────────────────────────────────────────────┐
│ ?emp │ ?man │ ?mname │ ?pair │ ?wname │
│ ?who │ ?whom │ -- │ -- │ ?lname │
│ ?whom │ ?whom2 │ -- │ -- │ -- │
│ ?whom2 │ -- │ -- │ -- │ "Smith"^^<http://www.w3.org/2001/XMLSchema#string> │
└────────┴────────┴────────┴───────┴────────────────────────────────────────────────────┘
bindings: {?emp=?who, ?man=?whom, ?wname=?lname} instantiate as:
?who <http://hr.example/DB/Employee#lastName> ?lname .
?_Emp_TaskToFoaf_0_pair <http://hr.example/DB/Task#drone> ?who .
?_Emp_TaskToFoaf_0_pair <http://hr.example/DB/Task#manager> ?whom .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_0_mname .
bindings: {?emp=?whom, ?man=?whom2} instantiate as:
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_1_wname .
?_Emp_TaskToFoaf_1_pair <http://hr.example/DB/Task#drone> ?whom .
?_Emp_TaskToFoaf_1_pair <http://hr.example/DB/Task#manager> ?whom2 .
?whom2 <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_1_mname .
bindings: {?emp=?whom2, ?wname="Smith"^^<http://www.w3.org/2001/XMLSchema#string>} instantiate as:
?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string> .
?_Emp_TaskToFoaf_2_pair <http://hr.example/DB/Task#drone> ?whom2 .
?_Emp_TaskToFoaf_2_pair <http://hr.example/DB/Task#manager> ?_Emp_TaskToFoaf_2_man .
?_Emp_TaskToFoaf_2_man <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_2_mname .
The possible invocations of rules produce a set of ways the query could be mapped to the antecedent to the rules. The query solution is the union of these mappings. Below is one example mapping:
UNION
alternative: <Emp_TaskToFoaf>
┌───────┬────────┬────────────────────────────────────────────────────┬───────┬────────┐
│ ?emp │ ?man │ ?mname │ ?pair │ ?wname │
│ ?who │ ?whom │ -- │ -- │ ?lname │
│ ?whom │ ?whom2 │ "Smith"^^<http://www.w3.org/2001/XMLSchema#string> │ -- │ -- │
└───────┴────────┴────────────────────────────────────────────────────┴───────┴────────┘
bindings: {?emp=?who, ?man=?whom, ?wname=?lname} instantiate as:
?who <http://hr.example/DB/Employee#lastName> ?lname .
?_Emp_TaskToFoaf_3_pair <http://hr.example/DB/Task#drone> ?who .
?_Emp_TaskToFoaf_3_pair <http://hr.example/DB/Task#manager> ?whom .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_3_mname .
bindings: {?mname="Smith"^^<http://www.w3.org/2001/XMLSchema#string>, ?emp=?whom, ?man=?whom2} instantiate as:
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_4_wname .
?_Emp_TaskToFoaf_4_pair <http://hr.example/DB/Task#drone> ?whom .
?_Emp_TaskToFoaf_4_pair <http://hr.example/DB/Task#manager> ?whom2 .
?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string> .
In the above mapping, two invocations the UNION
alternative: <Emp_TaskToFoaf>
┌────────┬────────┬────────┬───────┬────────────────────────────────────────────────────┐
│ ?emp │ ?man │ ?mname │ ?pair │ ?wname │
│ ?whom2 │ ?who │ ?lname │ -- │ "Smith"^^<http://www.w3.org/2001/XMLSchema#string> │
│ ?who │ ?whom │ -- │ -- │ -- │
│ ?whom │ ?whom2 │ -- │ -- │ -- │
└────────┴────────┴────────┴───────┴────────────────────────────────────────────────────┘
bindings: {?mname=?lname, ?emp=?whom2, ?man=?who, ?wname="Smith"^^<http://www.w3.org/2001/XMLSchema#string>} instantiate as:
?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string> .
?_Emp_TaskToFoaf_5_pair <http://hr.example/DB/Task#drone> ?whom2 .
?_Emp_TaskToFoaf_5_pair <http://hr.example/DB/Task#manager> ?who .
?who <http://hr.example/DB/Employee#lastName> ?lname .
bindings: {?emp=?who, ?man=?whom} instantiate as:
?who <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_6_wname .
?_Emp_TaskToFoaf_6_pair <http://hr.example/DB/Task#drone> ?who .
?_Emp_TaskToFoaf_6_pair <http://hr.example/DB/Task#manager> ?whom .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_6_mname .
bindings: {?emp=?whom, ?man=?whom2} instantiate as:
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_7_wname .
?_Emp_TaskToFoaf_7_pair <http://hr.example/DB/Task#drone> ?whom .
?_Emp_TaskToFoaf_7_pair <http://hr.example/DB/Task#manager> ?whom2 .
?whom2 <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_7_mname .
UNION
alternative: <Emp_TaskToFoaf>
┌───────┬────────┬────────────────────────────────────────────────────┬───────┬────────┐
│ ?emp │ ?man │ ?mname │ ?pair │ ?wname │
│ -- │ ?who │ ?lname │ -- │ -- │
│ ?who │ ?whom │ -- │ -- │ -- │
│ ?whom │ ?whom2 │ "Smith"^^<http://www.w3.org/2001/XMLSchema#string> │ -- │ -- │
└───────┴────────┴────────────────────────────────────────────────────┴───────┴────────┘
bindings: {?mname=?lname, ?man=?who} instantiate as:
?_Emp_TaskToFoaf_8_emp <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_8_wname .
?_Emp_TaskToFoaf_8_pair <http://hr.example/DB/Task#drone> ?_Emp_TaskToFoaf_8_emp .
?_Emp_TaskToFoaf_8_pair <http://hr.example/DB/Task#manager> ?who .
?who <http://hr.example/DB/Employee#lastName> ?lname .
bindings: {?emp=?who, ?man=?whom} instantiate as:
?who <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_9_wname .
?_Emp_TaskToFoaf_9_pair <http://hr.example/DB/Task#drone> ?who .
?_Emp_TaskToFoaf_9_pair <http://hr.example/DB/Task#manager> ?whom .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_9_mname .
bindings: {?mname="Smith"^^<http://www.w3.org/2001/XMLSchema#string>, ?emp=?whom, ?man=?whom2} instantiate as:
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_10_wname .
?_Emp_TaskToFoaf_10_pair <http://hr.example/DB/Task#drone> ?whom .
?_Emp_TaskToFoaf_10_pair <http://hr.example/DB/Task#manager> ?whom2 .
?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string> .
]]
=== As SPARQL Algebra ===
The debugging output includes a view of the final query expressed in the SPARQL Algebra.
<Query_algebra>
SELECT ?lname
(union
(bgp
(triple ?who <http://hr.example/DB/Employee#lastName> ?lname)
(triple ?_Emp_TaskToFoaf_0_pair <http://hr.example/DB/Task#drone> ?who)
(triple ?_Emp_TaskToFoaf_0_pair <http://hr.example/DB/Task#manager> ?whom)
(triple ?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_0_mname)
(triple ?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_1_wname)
(triple ?_Emp_TaskToFoaf_1_pair <http://hr.example/DB/Task#drone> ?whom)
(triple ?_Emp_TaskToFoaf_1_pair <http://hr.example/DB/Task#manager> ?whom2)
(triple ?whom2 <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_1_mname)
(triple ?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string>)
(triple ?_Emp_TaskToFoaf_2_pair <http://hr.example/DB/Task#drone> ?whom2)
(triple ?_Emp_TaskToFoaf_2_pair <http://hr.example/DB/Task#manager> ?_Emp_TaskToFoaf_2_man)
(triple ?_Emp_TaskToFoaf_2_man <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_2_mname)
)
(bgp
(triple ?who <http://hr.example/DB/Employee#lastName> ?lname)
(triple ?_Emp_TaskToFoaf_3_pair <http://hr.example/DB/Task#drone> ?who)
(triple ?_Emp_TaskToFoaf_3_pair <http://hr.example/DB/Task#manager> ?whom)
(triple ?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_3_mname)
(triple ?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_4_wname)
(triple ?_Emp_TaskToFoaf_4_pair <http://hr.example/DB/Task#drone> ?whom)
(triple ?_Emp_TaskToFoaf_4_pair <http://hr.example/DB/Task#manager> ?whom2)
(triple ?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string>)
)
(bgp
(triple ?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string>)
(triple ?_Emp_TaskToFoaf_5_pair <http://hr.example/DB/Task#drone> ?whom2)
(triple ?_Emp_TaskToFoaf_5_pair <http://hr.example/DB/Task#manager> ?who)
(triple ?who <http://hr.example/DB/Employee#lastName> ?lname)
(triple ?who <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_6_wname)
(triple ?_Emp_TaskToFoaf_6_pair <http://hr.example/DB/Task#drone> ?who)
(triple ?_Emp_TaskToFoaf_6_pair <http://hr.example/DB/Task#manager> ?whom)
(triple ?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_6_mname)
(triple ?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_7_wname)
(triple ?_Emp_TaskToFoaf_7_pair <http://hr.example/DB/Task#drone> ?whom)
(triple ?_Emp_TaskToFoaf_7_pair <http://hr.example/DB/Task#manager> ?whom2)
(triple ?whom2 <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_7_mname)
)
(bgp
(triple ?_Emp_TaskToFoaf_8_emp <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_8_wname)
(triple ?_Emp_TaskToFoaf_8_pair <http://hr.example/DB/Task#drone> ?_Emp_TaskToFoaf_8_emp)
(triple ?_Emp_TaskToFoaf_8_pair <http://hr.example/DB/Task#manager> ?who)
(triple ?who <http://hr.example/DB/Employee#lastName> ?lname)
(triple ?who <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_9_wname)
(triple ?_Emp_TaskToFoaf_9_pair <http://hr.example/DB/Task#drone> ?who)
(triple ?_Emp_TaskToFoaf_9_pair <http://hr.example/DB/Task#manager> ?whom)
(triple ?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_9_mname)
(triple ?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_10_wname)
(triple ?_Emp_TaskToFoaf_10_pair <http://hr.example/DB/Task#drone> ?whom)
(triple ?_Emp_TaskToFoaf_10_pair <http://hr.example/DB/Task#manager> ?whom2)
(triple ?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string>)
)
)
</query_algebra>
=== Output ===
The output is a SPARQL query which, when performed over the input RDF graph, which give the same solutions as would the user query performed over the inferred graph.
Final query: .
SELECT ?lname
WHERE
{
{
?who <http://hr.example/DB/Employee#lastName> ?lname .
?_Emp_TaskToFoaf_0_pair <http://hr.example/DB/Task#drone> ?who .
?_Emp_TaskToFoaf_0_pair <http://hr.example/DB/Task#manager> ?whom .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_0_mname .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_1_wname .
?_Emp_TaskToFoaf_1_pair <http://hr.example/DB/Task#drone> ?whom .
?_Emp_TaskToFoaf_1_pair <http://hr.example/DB/Task#manager> ?whom2 .
?whom2 <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_1_mname .
?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string> .
?_Emp_TaskToFoaf_2_pair <http://hr.example/DB/Task#drone> ?whom2 .
?_Emp_TaskToFoaf_2_pair <http://hr.example/DB/Task#manager> ?_Emp_TaskToFoaf_2_man .
?_Emp_TaskToFoaf_2_man <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_2_mname .
}
UNION
{
?who <http://hr.example/DB/Employee#lastName> ?lname .
?_Emp_TaskToFoaf_3_pair <http://hr.example/DB/Task#drone> ?who .
?_Emp_TaskToFoaf_3_pair <http://hr.example/DB/Task#manager> ?whom .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_3_mname .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_4_wname .
?_Emp_TaskToFoaf_4_pair <http://hr.example/DB/Task#drone> ?whom .
?_Emp_TaskToFoaf_4_pair <http://hr.example/DB/Task#manager> ?whom2 .
?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string> .
}
UNION
{
?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string> .
?_Emp_TaskToFoaf_5_pair <http://hr.example/DB/Task#drone> ?whom2 .
?_Emp_TaskToFoaf_5_pair <http://hr.example/DB/Task#manager> ?who .
?who <http://hr.example/DB/Employee#lastName> ?lname .
?who <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_6_wname .
?_Emp_TaskToFoaf_6_pair <http://hr.example/DB/Task#drone> ?who .
?_Emp_TaskToFoaf_6_pair <http://hr.example/DB/Task#manager> ?whom .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_6_mname .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_7_wname .
?_Emp_TaskToFoaf_7_pair <http://hr.example/DB/Task#drone> ?whom .
?_Emp_TaskToFoaf_7_pair <http://hr.example/DB/Task#manager> ?whom2 .
?whom2 <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_7_mname .
}
UNION
{
?_Emp_TaskToFoaf_8_emp <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_8_wname .
?_Emp_TaskToFoaf_8_pair <http://hr.example/DB/Task#drone> ?_Emp_TaskToFoaf_8_emp .
?_Emp_TaskToFoaf_8_pair <http://hr.example/DB/Task#manager> ?who .
?who <http://hr.example/DB/Employee#lastName> ?lname .
?who <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_9_wname .
?_Emp_TaskToFoaf_9_pair <http://hr.example/DB/Task#drone> ?who .
?_Emp_TaskToFoaf_9_pair <http://hr.example/DB/Task#manager> ?whom .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_9_mname .
?whom <http://hr.example/DB/Employee#lastName> ?_Emp_TaskToFoaf_10_wname .
?_Emp_TaskToFoaf_10_pair <http://hr.example/DB/Task#drone> ?whom .
?_Emp_TaskToFoaf_10_pair <http://hr.example/DB/Task#manager> ?whom2 .
?whom2 <http://hr.example/DB/Employee#lastName> "Smith"^^<http://www.w3.org/2001/XMLSchema#string> .
} }