SPARQL to SQL Translation

Formula#

Number of WHERE conditions (one-table schema):

where the sum runs over all variables $v$ of the query and $m_v$ is the number of occurrences of $v$ in the query triples.

Properties#

• Each join equality is an equi-Join condition; a shared SPARQL variable is exactly a join.
• One table per predicate (lecture schema, e.g. acted_in(person, film), married_to(person1, person2)): the predicate is not stored, so each query triple uses the table of its predicate, there is no predicate condition, and only the fixed subjects/objects and the joins remain. ES7 deliberately uses the one-table schema instead, which makes the predicate an explicit WHERE condition.
• Disconnected patterns: if the triples fall into groups that share no variable, no equality links the groups, and the result is the Cartesian product of the groups’ results (in SQL and in SPARQL).
• Reverse direction (SQL → SPARQL): each alias ti with ti.predicate = 'p' becomes a triple ?s_i p ?o_i; every join equality ti.c = tj.c' means the two positions get the same variable; fixed values are written in place of the variable; the SELECT columns become the selected variables.
• An additional condition such as a1.person < a2.person (or t1.subject != t2.subject) has no triple counterpart; in SPARQL it is a FILTER.
• In full generality, SPARQL and SQL are much more complex; the lecture and ES7 cover basic queries only.

Example#

SELECT ?mother ?father WHERE {
  ?child  <has_mother> ?mother .
  ?child  <has_father> ?father .
  ?mother <married_to> ?father .
}

SELECT t1.object, t2.object
FROM triples AS t1, triples AS t2, triples AS t3
WHERE t1.predicate = "has_mother"
  AND t2.predicate = "has_father"
  AND t1.subject = t2.subject          -- ?child  (2 occurrences → 1 equality)
  AND t3.predicate = "married_to"
  AND t3.subject = t1.object           -- ?mother (2 occurrences → 1 equality)
  AND t3.object = t2.object;           -- ?father (2 occurrences → 1 equality)

Condition count: 3 fixed predicates $+ (2-1) + (2-1) + (2-1) = 6$.

With one table per predicate (lecture example, married couples who acted together):

SELECT a1.person, a2.person, a1.film
FROM acted_in AS a1, acted_in AS a2, married_to AS m
WHERE a1.film = a2.film
  AND a1.person = m.person1
  AND a2.person = m.person2;

The lecture code additionally adds AND a1.person < a2.person, which is not part of the SPARQL query and drops one of the two symmetric rows of a couple.

Sources#

• Slides 07, p. 27 (setup, table per predicate), p. 28 (example), pp. 29–30 (generic algorithm)
• DBIS_VL07 > SPARQL to SQL Translation, DBIS_VL07 > Setup, DBIS_VL07 > Generic algorithm
• Exams: DBIS Exam WS1314 (not published) (Task 6.2), DBIS Exam WS1819 (not published) (Task 6.2), DBIS Exam WS1920 (not published) (Task 5), DBIS Exam WS2324 (not published) (Task 3.1), DBIS Exam WS2324-2 (not published) (Task 3.1)
• Related: Relational Model — the triples table is a relation with columns $(\text{subject}, \text{predicate}, \text{object})$