Semantics of Knowledge Graphs

Wouter Beek (

Part I: Formal Meaning

Formal meaning

Meaning is formalized with 2 functions:

Interpretation function ($I$)
From terms (syntax) to resources and properties (semantics).
Extension function ($Ext$)
From properties (semantics) to pairs of resources (semantics).

The combination of an specific interpretation function and a specific extension function is a model ($M$).

Meaning of terms

The interpretation of a node is the resource it refers to.

The interpretation of a predicate term is the property it denotes.

The extension of a property is the collection of pairs of resources that are connected by that property.

Meaning of terms: example

Meaning of sentences: Truth-conditional Semantics

To understand what a sentence means is to know what is the case if it would be true. (One can understand a sentence, without knowing whether it is true.)
Tractatus Logico-Philosophicus, 4.024

Truth of a triple

$$\langle s,p,o \rangle \text{ is true} \iff \langle I(s),I(o) \rangle \in Ext(I(p))$$

$$\langle \text{the Louvre}, \text{owns}, \text{the Mona Lisa} \rangle \text{ is true} \iff$$ $$\langle I(\text{the Louvre}), I(\text{the Mona Lisa}) \rangle \in Ext(I(\text{owns})) \iff$$ $$\langle 🏰, πŸ–Ό \rangle \in Ext(\text{concept-of-ownership}) \iff$$ $$\langle 🏰, πŸ–Ό \rangle \in \{ \langle 🏰, πŸ–Ό \rangle \}$$ βœ“

$$\langle \text{the Mona Lisa}, \text{owns}, \text{the Louvre} \rangle \text{ is true} \iff$$ $$\langle I(\text{the Mona Lisa}), I(\text{the Louvre}) \rangle \in Ext(I(\text{owns})) \iff$$ $$\langle πŸ–Ό, 🏰 \rangle \in Ext(\text{concept-of-ownership}) \iff$$ $$\langle πŸ–Ό, 🏰 \rangle \in \{ \langle 🏰, πŸ–Ό \rangle \}$$ ❌

Meaning of a triple

The meaning of a triple is the set of models in which the triple is true.

Meaning of a graph

The meaning of a graph is the set of models in which the triples in the graph are true.

Open World Assumption (OWA) & Closed World Assumption (CWA)

Difference between OWA and CWA

β€œApples are green.”
β€œAre apples delicious?”
CWA answer
OWA answer
β€œI don't known.”

Why does the SW need OWA?

In a local database, we can assume that we always have full access to all the relevant data.

On the web, we may not always have access to all the relevant data all the time.

Example of OWA

  • I(the Louvre) = 🏰
  • I(the Mona Lisa) = πŸ–Ό
  • Ext(I(owns)) = {γ€ˆ 🏰,πŸ–Όγ€‰}
  • Ext(I(exhibits)) = {γ€ˆ 🏰,πŸ–Όγ€‰}

With CWA, owning and exhibiting would have the same meaning. With OWA, they may still be different.

  • I(owns) = concept-of-ownership
  • I(exhibits) = concept-of-exhibiting

Corner case example (1/2)

rdfs:Class a rdfs:Class.
  • I(rdfs:Class) = πŸ•
  • I(a) = 🐘
  • Ext(🐘) = {γ€ˆπŸ•,πŸ•γ€‰,…}

This statement cannot be expressed with CWA, due to the axiom of regularity: βˆ€x (xβ‰ βˆ… β†’ βˆƒy∈x(x∩y=βˆ…)

Corner case example (2/2)

owl:sameAs owl:sameAs owl:sameAs.
  • I(owl:sameAs) = ~
  • Ext(~) = {γ€ˆ~,~〉,…}

γ€ˆowl:sameAs,owl:sameAs,owl:sameAs〉is true iffγ€ˆI(owl:sameAs),I(owl:sameAs)γ€‰βˆˆ Ext(I(owl:sameAs))

Notice that an RDF graph is a special kind of graph, i.e., vertices and edges may overlap.

Instances belong to classes

pokemon:mew     a          def:Pokemon;
                def:name   "γƒŸγƒ₯ウ"@ja;
                def:weight 40.
pokemon:pikachu a          def:Pokemon;
                def:knows  pokemon:mew;
                def:name   "ピカチγƒ₯ウ"@ja;
                def:weight 60.

Domain & range

foaf:knows rdfs:domain foaf:Person.
ex:john foaf:knows ex:mary.
=> ex:john a foaf:Person.
foaf:knows rdfs:range foaf:Person.
ex:john foaf:knows ex:mary.
=> ex:mary a foaf:Person.

SPARQL Algebra

SPARQL algebra

  • Variables V
  • Solution mapping ΞΌ:V β†’ T
  • Pattern instance mapping P := ΞΌ ∘ Οƒ
  • Basic Graph Pattern (BGP) x
  • ΞΌ is a solution for x from G, if (βˆƒP)(P(x) βŠ† G and ΞΌ is the restriction of P to V(x)

Example 1


prefix rdfs: <>
rdfs:Class a rdfs:Class.


?x a ?y.

Solution ΞΌ = {(?x,rdfs:Class),(?y,rdfs:Class)}

Example 2


prefix rdfs: <>
rdfs:Class a rdfs:Class.


_:1 a _:2.
  • Solution ΞΌ = βˆ…
  • Οƒ = {(_:1,rdfs:Class), (_:2,rdfs:Class)}

Alternative semantics for owl:sameAs

Definitions of identity

Indiscernibility of identicals (Leibniz's Law)

$$a = b \rightarrow (\forall \phi \in \Psi)(\phi(a) = \phi(b))$$

Identity of indiscernibles

$$(\forall \phi \in \Psi)(\phi(a) = \phi(b)) \rightarrow a = b$$

Equivalence relation

Identity is the smallest equivalence relation

Formal Concept Analysis (FCA)

Context: instances (X), properties (Y), mapping (m)

$$X' \,:=\, \{ y \in Y \,\vert\, (\forall x \in X)(m(x,y)) \}$$

$$Y' \,:=\, \{ x \in X \,\vert\, (\forall y \in Y)(m(x,y)) \}$$

Formal concept γ€ˆX,Y〉: X'=Y and Y'=X

Thank you for your attention!