VL07 Knowledge Graphs, SPARQL, SPARQL to SQL

Organisation#

Knowledge Graphs / RDF#

So the data model of RDF is triples, and a set of triples produces a knowledge graph.

IRIs#

Widely used knowledge graphs#

Most IT-heavy companies (Google, Amazon, Microsoft, Meta, Bloomberg, Walmart, Airbnb, …) maintain their own large KG (Slides 8–9).

Interoperability#

One strength of RDF + SPARQL is how easily datasets can be combined. For relational databases this is hard (different, complex schemas, different identifiers). In RDF one only needs additional triples that relate the IDs of the two datasets (Slide 11):

wd:Q183      wdtn:P402    osmrel:51477 .   # from Wikidata
osmrel:51477 osm:wikidata wd:Q183 .        # from OpenStreetMap

Here wd:Q183 is Germany in Wikidata, osmrel:51477 is Germany in OSM, wdtn:P402 is Wikidata’s predicate “OpenStreetMap IRI”, and osm:wikidata is OSM’s predicate “Wikidata IRI”. This enables federated SPARQL queries over several datasets, e.g. all power lines in the EU.

SPARQL#

Basic queries#

A basic query has the form SELECT <variables> WHERE { <triples> }, where each triple may have variables (?name) at some positions (SPARQL Query Structure).

SELECT ?person1 ?person2 ?film WHERE {
  ?person1 <acted_in>   ?film .
  ?person2 <acted_in>   ?film .
  ?person1 <married_to> ?person2 .
}
# married couples who acted together in at least one movie

• Like in SQL, the result of a SPARQL query is always a table.
• There is one row for each assignment of values to the variables such that all triples of the query body exist in the KG (Slide 13).

Queries as graph patterns#

A SPARQL query is a (small) sub-graph with variables at some nodes or edges. Solving the query means finding all matches of this sub-graph in the (large) KG; each distinct match corresponds to one assignment of values to the variables such that the corresponding sub-graph exists in the KG (Slide 14).

PREFIX, FILTER, ORDER BY, LIMIT#

PREFIX declarations abbreviate the long IRIs of real KGs. Query: all people born in Honolulu, with their English names (Slides 10 and 15):

PREFIX wd: <http://www.wikidata.org/entity/>
PREFIX wdt: <http://www.wikidata.org/prop/direct/>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
SELECT ?person ?person_name WHERE {
  ?person wdt:P19 wd:Q18094 .
  ?person rdfs:label ?person_name .
  FILTER (LANG(?person_name) = "en")
}

with wdt:P19 = <http://www.wikidata.org/prop/direct/P19> (place of birth), wd:Q18094 = Honolulu, rdfs:label = canonical name. FILTER (LANG(?x) = "en") keeps only English-language labels.

ORDER BY and LIMIT work as in SQL, except that DESC/ASC is written like a function of the sort key, not as a suffix (Slide 16):

SELECT ?person ?person_name ?date_of_birth WHERE {
  ?person wdt:P19 wd:Q18094 .
  ?person wdt:P569 ?date_of_birth .      # P569 = date of birth
  ?person rdfs:label ?person_name .
  FILTER (LANG(?person_name) = "en")
}
ORDER BY DESC(?date_of_birth) LIMIT 100

Differences between SPARQL and SQL#

(Slide 17)

The power of RDF + SPARQL: example queries on Wikidata (birth places of people with first name X, events on Dec 2, German universities with student counts), UniProt (organisms with protein sequences), PubChem (NSAID drugs with small molecular weight), OSM (all streets in X) and Wikidata + OSM (fast-food restaurants along the E 35) all run on the same system with almost zero per-dataset configuration (Slide 18).

Reification#

The problem: $n$-ary relations#

Meryl Streep won Oscars for these movies (Slides 19–20):

What is needed is an $n$-ary predicate with $n > 2$, e.g. <award> <Meryl_Streep> <BA> "2011" <The_Iron_Lady> (BA = Best Actress). In a relational database this is just a table with 4 columns; the question is how to express it with triples.

Mediator entities (statement nodes)#

@prefix wd:  <http://www.wikidata.org/entity/> .
@prefix wds: <http://www.wikidata.org/entity/statement/> .
@prefix p:   <http://www.wikidata.org/prop/> .
@prefix ps:  <http://www.wikidata.org/prop/statement/> .
@prefix pq:  <http://www.wikidata.org/prop/qualifier/> .
wd:Q873           p:P166    wds:Q873-6ad4311a .  # award statement node
wds:Q873-6ad4311a ps:P166   wd:Q103618 .         # which award
wds:Q873-6ad4311a pq:P585   "2011" .             # point in time
wds:Q873-6ad4311a pq:P1686  wd:Q269810 .         # for work

Wikidata’s naming scheme#

The Wikidata Prefix System uses different prefixes for the same predicate, depending on whether and how it relates to a statement node (Slide 22):

wdt:P166, p:P166, ps:P166, pq:P166, … are technically all different IRIs; the common suffix P166 says that they express the same relation (winning an award).

Entity ──p:Pxxx──▶ statement node ──ps:Pxxx──▶ value
                                  ──pq:Pyyy──▶ qualifier value

Finding the right query is hard#

Search request: Which Oscars did Meryl Streep win and for which movies? (Slides 23–24). ES7 Exercise 3 asks for a similar query (without language filter).

PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX wdt: <http://www.wikidata.org/prop/direct/>
PREFIX pq: <http://www.wikidata.org/prop/qualifier/>
PREFIX ps: <http://www.wikidata.org/prop/statement/>
PREFIX p: <http://www.wikidata.org/prop/>
PREFIX wd: <http://www.wikidata.org/entity/>
SELECT ?movie ?award WHERE {
  wd:Q873   p:P166    ?mediator .
  ?mediator ps:P166   ?award_id .
  ?mediator pq:P1686  ?movie_id .
  ?award_id wdt:P31   wd:Q19020 .
  ?award_id rdfs:label ?award . FILTER (LANG(?award) = "en")
  ?movie_id rdfs:label ?movie . FILTER (LANG(?movie) = "en")
}

What makes this hard (Slide 25):

• the right prefix definitions,
• the right entity names: wd:Q873 (Meryl Streep), wd:Q19020 (Academy Award),
• the right predicate names (very hard, even for experts): p:P166 “won award” (awardee → mediator), ps:P166 “won award” (mediator → award), pq:P1686 “for work” (mediator → movie), wdt:P31 “instance of” (instance → class),
• the syntax for filtering by language.

Autocompletion and QLever#

The chair develops QLever, an RDF database (https://github.com/ad-freiburg/qlever), with many thesis and project topics. The QLever UI (https://qlever.dev/wikidata) offers context-sensitive autocompletion, which helps significantly with formulating queries. Lecture 8 shows how to build a simple autocompletion mechanism; Lectures 9–10 build a web app that combines everything so far (Slide 26).

SPARQL to SQL Translation#

Setup#

Goal: translate a SPARQL query into a SQL query that gives the desired result on a given database (SPARQL to SQL Translation). The lecture uses one table per predicate; since all rows of a table belong to one predicate, the predicate name is not stored (Slide 27):

CREATE TABLE acted_in(person TEXT, film TEXT);
CREATE TABLE married_to(person1 TEXT, person2 TEXT);

Example#

(Slide 28; the SQL was written live, the version below follows the lecture code public/code/lecture-07/README.md)

SELECT ?person1 ?person2 ?film WHERE {
  ?person1 <acted_in>   ?film .
  ?person2 <acted_in>   ?film .
  ?person1 <married_to> ?person2 .
}

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;

Each query triple becomes one table alias (a1, a2, m); each variable that occurs in several triples yields join equalities (?film: a1.film = a2.film; ?person1: a1.person = m.person1; ?person2: 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.

Generic algorithm#

For arbitrary basic queries SELECT <list of variables> WHERE { <list of triples> } (designing it is ES7 Exercise 1; Slides 29–30):

1. FROM: $k$ query triples → $k$ aliases of the table: FROM wikidata AS w1, wikidata AS w2, ..., wikidata AS wk.
2. Variable occurrences: for each variable, collect the list of all its occurrences, e.g. ?x: w1.subject, w2.object, w5.object.
3. WHERE, joins: equate the occurrences, e.g. w1.subject = w2.object AND w2.object = w5.object. If ?x occurs $m$ times, $m-1$ equalities suffice.
4. WHERE, constants: every fixed (non-variable) element of a triple gives an equality wi.<column> = '<value>' (in the ES7 schema this includes the predicate).
5. SELECT: each selected variable maps to one of its occurrences wi.<column>.

Hence (one-table schema) the number of WHERE conditions is

where the sum is over all variables $v$ of the query and $m_v$ is the number of occurrences of $v$ in the query triples (SPARQL to SQL Translation). Each join equality is an equi-Join condition in the sense of SQL’s FROM/WHERE.

In full generality, SPARQL and SQL are much more complex; lecture and ES7 focus on the basics.

Python ⇿ SQLite#

(Slide 31)

import sqlite3
db = sqlite3.connect("example.db")
cursor = db.cursor()
cursor.execute("SELECT * FROM table")
for row in cursor.fetchall():
    print("\t".join(row))

Further literature#

H. Bast, J. Kalmbach, T. Klumpp, C. Korzen: Knowledge Graphs (book chapter, gentle introduction); Wikipedia on Knowledge graph and SPARQL; Wikidata and its RDF dump format (Slide 32).

Open Questions#

• Why are there two symbols for variables?
  • Not answered on the slides, which only use ?var for variables (and <…> or prefix:name for fixed IRIs).
  • Beyond the lecture: the SPARQL 1.1 standard allows a variable to be written as ?x or $x; both denote the same variable.
• Is SPARQL/RDF a competitor to SQL, or does it fill a different niche?
  • Both: in expressiveness they are essentially equivalent, and basic SPARQL translates mechanically to SQL (Slide 12). The niche of RDF + SPARQL is schema-free data that has to be combined across datasets: combining datasets needs only a few linking triples (Slide 11), and one system runs queries on very different KGs with almost no configuration (Slide 18). The price is reification for $n$-ary facts, which makes queries harder to write. Student feedback in Lecture 8 also says “it depends on the use case”.

Concepts#

• RDF Triples — data model: all data as subject predicate object triples forming a directed knowledge graph
• SPARQL Query Structure — SELECT … WHERE { triples with variables }, PREFIX, FILTER, ORDER BY/LIMIT; queries as graph patterns
• Wikidata Prefix System — wd:, wdt:, p:, ps:, pq: and statement nodes for reified facts
• SPARQL to SQL Translation — one alias per triple, equalities for constants, $m-1$ equalities per variable
• Join — shared variables in SPARQL correspond to join conditions in SQL
• SQL Query Structure — target of the translation (SELECT/FROM/WHERE with aliases)
• Knowledge Graph — set of RDF triples viewed as a directed labelled graph
• IRI — globally unique, URL-like identifier for entities and predicates
• Reification — modelling $n$-ary facts with mediator entities (statement nodes)
• Federated query — SPARQL query over several linked datasets (e.g. Wikidata + OSM)