\documentclass[times]{acm-book}

\usepackage{amsmath}    % Package for AMS math extensions.
\usepackage{graphicx}   % Package for importing EPS files.
\usepackage[hidelinks]{hyperref}   % clickable links.
\RequirePackage{fontawesome}

%\usepackage[T2A,T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian,english]{babel}
\usepackage{anyfontsize}
% Needed for defining and using custom colors.
\usepackage{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows.meta, fit, arrows, positioning}
\usepackage{array}
\usepackage{tabularx}
\usepackage{soul}  % For consistency with underlining (\ul)
\setuldepth{x}

\usepackage{enumerate}
% Needed to be able to set margins in an enumeration.
\usepackage{enumitem}
\usepackage{comment}


% LuaLaTeX stuff (needed for Arabic and Hindi script)
\ifluatex
  \usepackage{fontspec}
  \setmainfont{Times New Roman}
  %\setmainfont{TeX Gyre Termes}
  \usepackage{microtype}
  % \usepackage[protrusion=false]{microtype}
	%\usepackage{lmodern}
	\usepackage{polyglossia}
	\setmainlanguage{english}
	\setotherlanguages{ukrainian,hindi,arabic}
	\newfontfamily{\devanagarifont}{Noto Sans Devanagari}
	\newfontfamily{\arabicfont}{Noto Sans Arabic}
\else
\fi

% This was needed with pdflatex
% For Cyrillic in italics (does not work with Times)
%\DeclareRobustCommand{\cyrins}[1]{%
%\begingroup\fontfamily{erewhon-TLF}%
%\foreignlanguage{russian}{#1}%
%\endgroup
%}

% Custom colors.
\definecolor{darkblue}{rgb}{0.0, 0.0, 0.7}
\definecolor{darkred}{rgb}{0.7, 0.0, 0.0}
\definecolor{darkgreen}{rgb}{0.0, 0.6, 0.0}
\definecolor{todored}{rgb}{0.8, 0.0, 0.0}

% Custom commands.
\def\TODO#1{\noindent{\bf\color{todored}#1}}
\newcommand{\para}[1]{\vspace{5pt}\noindent\textbf{#1}}
\def\cursor{\hspace{0.3mm}\underline{\hspace{1.8mm}}}
\def\K{\hspace{0.1em}\mathrm{K}}
\def\M{\hspace{0.1em}\mathrm{M}}
\def\B{\hspace{0.1em}\mathrm{B}}
\def\ms{\hspace{0.1em}\mathrm{ms}}

\def\u{\raisebox{0.4mm}{\underline{\hspace{1.5mm}}\hspace{0.2mm}}}
\def\iri#1{$<$#1$>$}
\def\sparqlemph#1{#1}
\def\SELECT{\sparqlemph{SELECT}}
\def\DISTINCT{\sparqlemph{DISTINCT}}
\def\WHERE{\sparqlemph{WHERE}}
\def\ORDERBY{\sparqlemph{ORDER BY}}
\def\GROUPBY{\sparqlemph{GROUP BY}}
\def\DESC{\sparqlemph{DESC}}
\def\FILTER{\sparqlemph{FILTER}}
\def\LANG{\sparqlemph{LANG}}
\def\REGEX{\sparqlemph{REGEX}}
\def\SAMPLE{\sparqlemph{SAMPLE}}
\def\COUNT{\sparqlemph{COUNT}}
\def\AS{\sparqlemph{AS}}
\def\BIND{\sparqlemph{BIND}}
\def\STR{\sparqlemph{STR}}
\def\PREFIX{\sparqlemph{PREFIX}}
\def\OPTIONAL{\sparqlemph{OPTIONAL}}
\def\UNDEF{\sparqlemph{UNDEF}}
\def\COALESCE{\sparqlemph{COALESCE}}
\def\VALUES{\sparqlemph{VALUES}}
\def\MATCHKEYWORDS{\sparqlemph{ql:match-keywords}}
\def\MATCHKEYWORDS{\sparqlemph{MATCH{\u}KEYWORDS}}
\def\GROUPCONCAT{\sparqlemph{GROUP{\u}CONCAT}}
\def\SERVICE{\sparqlemph{SERVICE}}

% Macros for SPARQL entities for consistency
\def\isa{is\u a}
\def\birthday{birth\u date}
\def\wonaward{won\u award}
\def\wonawardinyear{won\u award\u in\u year}
\def\wonawardforfilm{won\u award\u for\u film}
\def\gender{gender}
\def\aka{also\u known\u as}
\def\filmperf{film\u performance}
\def\merylstreep{Meryl\u Streep}
\def\margaretthatcher{Margaret\u Thatcher}
\def\carter{Ruth\u E\u Carter}
\def\kramervskramer{Kramer\u vs\u Kramer}
\def\sophieschoice{Sophie's\u Choice}
\def\ironlady{The\u Iron\u Lady}
\def\bestactress{Best\u Actress}
\def\bestsupportingactress{Best\u Supporting\u Actress}
\def\bestdesign{Best\u Costume\u Design}

\newcommand{\examplequery}[1]{\\[-4mm]{\small\faExternalLink\hspace{1mm}\href{https://qlever.cs.uni-freiburg.de/ir-book/#1}{\raisebox{0.3mm}{\underline{\smash{Click to run query on QLever}}}}}}
\newcommand{\examplequeryhref}[2]{\href{https://qlever.cs.uni-freiburg.de/ir-book/#1}{#2}}


%% Hannah prefers no indent and a little space between paragraphs.
%\parindent0mm
%\parskip2mm

% Custom environments.
\newenvironment{kb}
  {\it\vspace{-1mm}\parindent0mm\begin{tabbing}\hspace*{36mm}\=\hspace*{26mm}\=\kill}
  {\end{tabbing}\vspace{-1mm}\noindent\ignorespacesafterend}
\newenvironment{kb2}
  {\it\vspace{1mm}\parindent0mm}
  {\vspace{1mm}\noindent\ignorespacesafterend}
\newenvironment{sparql}
  {\it\vspace{-1mm}\begin{tabbing}\hspace*{3mm}\=\hspace*{14mm}\=\hspace*{24mm}\=\hspace*{18mm}\=\kill}
  {\end{tabbing}\vspace{-1mm}\noindent\ignorespacesafterend}

% =============================================================================

\begin{document}

%\title{Knowledge Graphs}
%\author{Hannah Bast}
%%\email{bast@cs.uni-freiburg.de}
%\author{Theresa Klumpp}
%%\email{klumppt@cs.uni-freiburg.de}
%\author{Claudius Korzen}
%%\email{korzen@cs.uni-freiburg.de}
%\thanks{University of Freiburg, Germany}
%
%\maketitle

\tableofcontents

% =============================================================================

\chapter{Knowledge Graphs}
\chapterauthor{Hannah Bast, Johannes Kalmbach, Theresa Klumpp, Claudius Korzen\\[1mm]University of Freiburg, Germany}


\section{Introduction}\label{sec:intro}

Knowledge graphs have become an essential ingredient of information retrieval systems.
There is a plethora of specialized research papers as well as surveys on the topic.
We here focus on an aspect that has received little attention in existing overview papers so far:
efficient indexing of and search on knowledge graphs.
We explain the key ideas with many examples, which you can also try out live on a variety of (small and large) knowledge graphs;
see \url{https://qlever.cs.uni-freiburg.de/ir-book/}.
This should make the chapter easy to follow also for non-experts.
Where there is more to know, we provide links to relevant surveys.

We also provide a gentle introduction into the basics and an insightful overview
of existing knowledge graphs and their main features, strengths, and weaknesses.
We have structured this chapter into sections that can be read largely independently from each other,
provided that the basics (explained in Section \ref{sec:basics}) are understood.
Wherever there is a dependency on a previous section, we point it out.
Here is a quick overview over what each section is about.

\para{What is a knowledge graph}
Knowledge graphs are directed graphs with labeled edges
that represent structured knowledge about the world.
Each vertex stands for an \emph{entity}, for example \emph{Sanna Marin}
(former prime minister of Finland) or \emph{Helsinki} (the capital of Finland).
Each directed edge stands for a relation between two entities and the label says what the relation is.
For example, there could be an edge from \emph{Sanna Marin} to \emph{Helsinki}, labeled \emph{place of birth}.
Equivalently, the information captured by this edge could be formulated as a subject-predicate-object \emph{triple},
namely \emph{Sanna Marin - place of birth - Helsinki}.
Much of the beauty of knowledge graphs comes from this simple and universal data model.
% which has been standardized as the so-called \emph{Resource Description Framework} (RDF).
However, this simple model also implies a number of challenges.
For example, how to cast more complex information into this framework
(like Sanna Marin being elected prime minister of Finland at a certain time in a certain place)
and how to query such information?
We answer this and other questions in Section \ref{sec:basics}.

\para{What knowledge graphs are out there}
The idea behind knowledge graphs is old, but early attempts like CYC have not been widely successful
because they were too complex and too ambitious in the kind of knowledge they tried to capture,
yet lacked the human power and the data \citep{DBLP:journals/cacm/Lenat95}.
The World Wide Web has brought us vast amounts of data in electronic form and the possibility of crowdsourcing.
As a consequence, the field has been reborn and many large knowledge graphs have been developed over the past fifteen years.
Some contain general-purpose knowledge, like Freebase, Yago, DBpedia, or Wikidata.
Others contain domain-specific knowledge, like UniProt (proteins), PubChem (chemistry), OpenStreetMap (geodata),
or DBLP (bibliographic data).
Many big companies maintain their own knowledge graphs, for example: Google, Microsoft, Amazon, Facebook, or Wolfram Alpha.
In Section \ref{sec:examples}, we introduce eight popular knowledge graphs and briefly discuss their characteristics,
and their strengths and weaknesses.

\para{How to search a knowledge graph}
The standard query language for knowledge graphs is SPARQL,
which is conceptually similar to SQL (the standard query language for databases)
but adapted to the simple subject-predicate-object data model.
In principle, each knowledge graph can be stored in a standard database
and each SPARQL query can be translated into an equivalent SQL query on that database \cite{DBLP:journals/dke/ChebotkoLF09}.
But SPARQL is more natural for data modeled as triples.
Like SQL, SPARQL allows semantically precise queries, for example:
find all the current prime ministers of all countries in the world and when they were elected.
In Section \ref{sec:query_languages}, we discuss the basics of SPARQL and two other popular query languages:
\emph{Cypher}, which is strongly related to SPARQL,
and \emph{GraphQL}, which is often mistaken as related, but actually is not.%
\footnote{We include GraphQL because
we did not find a lucid explanation anywhere of what GraphQL is and what it is not.}
SPARQL is conceptually simple, but finding the right entity names and
how the sought for information is represented can be extremely hard, even for experts.%
\footnote{This is not specific for SPARQL: related languages like SQL or CYPHER have the same problem.}
There are various techniques to alleviate this, notably autocompletion and
automatically translating queries written in natural language to SPARQL queries.
We discuss these two techniques in Section \ref{sec:advanced_queries}.

\para{Engines and indexing}
The largest knowledge graphs with a coherent schema%
\footnote{Note that generating enormous amounts of triples without a meaningful schema is trivial.
For example, one could crawl the web and for every word on every web page,
add a triple stating that this word occurs on this web page.
That would give a very large knowledge graph, but not a very useful one.}
have tens of billions of triples; see Section \ref{sec:examples}.
When combining several such knowledge graphs, we obtain hundreds of billions of triples.
Finding information in such vast datasets efficiently is a major challenge,
similar to finding information in the around 50 billion pages indexed by today's web search engines.
SPARQL engines either build on existing database engines (recall the equivalence of SPARQL and SQL mentioned above),
or they precompute index data structures specifically designed for knowledge graphs.
In Section \ref{sec:indexing}, we describe the key techniques behind building a high-performance SPARQL engine.
A popular open-source SPARQL engine built on these techniques is \emph{QLever} \cite{DBLP:conf/cikm/BastKKKS22}.
We also discuss three other popular SPARQL engines and their strengths and weaknesses (\emph{Virtuoso}, \emph{Blazegraph}, \emph{Neo4j}).

%{\bf How to combine a knowledge graph with text?}
%Some information is inherently structured and perfectly suited for a knowledge graph.
%However, even more information is inherently unstructured and best expressed in natural language text.
%Knowledge graphs allow the incorporation of text in the sense that an entity can also be linked to a piece of text.
%For example, the title of a book or a short abstract describing an entity.
%SPARQL allows regular expression matching on these texts,
%and all major SPARQL engines provide extensions that also allow more advanced querying such as keyword search.
%And all major web search engines consider both the documents they crawled and their knowledge graph when processing queries.
%Section \ref{sec:text} discusses the various ways how knowledge graphs can be combined with text.
%For the most powerful of these combinations, we explain the basics of how this can be realized.

\para{Combination with text search and federated search}
One of the great strengths of RDF and SPARQL is the easy interoperability of different datasets.
In Section \ref{sec:text}, we provide a brief overview of the various ways to combine a knowledge graph with text data.
The easiest way is to have text as objects of selected triples (for example, the name or description of an entity).
A more powerful way is to recognize and link entities from a knowledge graph in a separate text corpus.
We also provide a brief overview over the benefits and challenges of federated search.
In principle, federated search allows queries that gather data from multiple knowledge graphs.
For example, we may be interested in the geometric shape (such data is contained in the OpenStreetMap data) of all countries, where a given language is officially spoken (such information is contained in Wikidata).
All that is needed for this are triples that relate entity ids from one dataset to entity ids from the other dataset.
The challenge is to execute such queries efficiently, exchanging as little data as possible.

\para{What else is there to know about knowledge graphs}
There are many more uses of and challenges associated with knowledge graphs.
In their recent survey, \citet{OTHER:HoganBCDDGGKNPNNRRSSSZ21} give a much broader overview
and cover topics such as:
graph models, schema representation, reasoning, knowledge graph construction and completion and correction.
That survey also lists (in its Table 1) many recent surveys on particular aspects of knowledge graphs.
None of these cover the aspects of indexing and search from the ground up like this chapter
(which therefore nicely fills a gap in the literature).
We here also provide other nuggets of information not found elsewhere,
for example, our characterization and critical discussion
of several popular knowledge graphs (Table \ref{table:kg-overview})
and our succinct description of the aforementioned \emph{GraphQL} query language (Section \ref{sec:query_languages:graphql}).
%which due to its name is often mistaken as a technology for knowledge graphs, but actually is not.

\para{The future of knowledge graphs}
We conclude this chapter with a short glimpse into the future (Section \ref{sec:outlook}).
In particular, we ponder the question which role knowledge graphs will play given the dramatic progress made in the fields of deep learning and language models.
We believe that the two will co-exist for a long time to come, complementing each others weaknesses.

%For example: How to construct a knowledge graph?
%How to merge different knowledge graphs?
%How to add logic to knowledge graphs in order to do complex reasoning?
%How to combine search in a knowledge graph with text search?
%The aspects of graph models, schemata, reasoning, construction.

\section{What is a knowledge graph}\label{sec:basics}

In this section, we explain some basic concepts and terminology and introduce a toy knowledge graph,
which we will refer back to throughout the chapter.

\subsection{Our toy knowledge graph, first version}\label{sec:basics:example_1}

Let us start by giving the toy knowledge graph as a set of triples,
which make some statements about a well-known actress and a well-known costume designer and their respective Oscars.

\begin{kb}
  \iri{\merylstreep}\hspace{20mm}   \= \iri{\isa}\hspace{20mm}   \= \iri{Person} . \\
  \iri{\merylstreep}   \> \iri{\gender}      \> \iri{Female} . \\
  \iri{\merylstreep}   \> \iri{\aka}         \> "Mary Louise Streep" . \\
  \iri{\merylstreep}   \> \iri{\birthday}    \> "1949-06-22" . \\
  \iri{\merylstreep}   \> \iri{\wonaward}    \> \iri{\bestactress} . \\
  \iri{\carter}        \> \iri{\isa}         \> \iri{Person} . \\
  \iri{\carter}        \> \iri{\gender}      \> \iri{Female} . \\
  \iri{\carter}        \> \iri{\wonaward}    \> \iri{\bestdesign} . \\
  % \iri{\merylstreep}   \> \iri{\wonaward}   \> \iri{\bestsupportingactress} \\
  \iri{\bestactress} \> \iri{\isa} \> \iri{Oscar} . \\
  \iri{\bestdesign}  \> \iri{\isa} \> \iri{Oscar} .
  % \iri{\bestsupportingactress} \> \iri{\isa} \> \iri{Oscar}
\end{kb}

\noindent
Such a set of triples is called a \emph{knowledge graph}.
We already noted that we can equivalently view a set of triples as a graph with directed labeled edges.
Sometimes the term \emph{knowledge base} is used as a synonym for the term knowledge graph.
In this chapter we exclusively use the term knowledge graph, as it has become much more common.
A graph representation of the triples above (and a few additional triples, explained later)
is shown in the upper part of Figure \ref{fig:example_graph} on page \pageref{fig:example_graph}.

%The beauty of this representation is that it is easy to read
%and the semantics (that is, what it is supposed to mean) is intuitive to understand.
%Nevertheless, there are many subtleties and challenges, as we explain next.

\subsection{RDF}\label{sec:basics:rdf}

Modeling data as a set of subject-predicate-object triples
is at the heart of the \emph{Resource Description Framework (RDF)}.
Each component of a triple is denoted by a so-called \emph{International Resource Identifier (IRI)};
these are the identifiers in \emph{$<$...$>$} brackets in the example above.
An IRI is like a URI (used to give a web page a universally unambiguous name),
but with an extended character set (unlike for URIs, most Unicode characters are allowed in an IRI).
Objects can alternatively also be strings, called \emph{literals} in RDF.
In the example above, the third and fourth triple have a literal object.
RDF also has basic support for modeling data types.
For example, we could specify that the object of the fourth triple is a date
and we will indeed do that in our second (more elaborate) example below.
Note that we can also use RDF to specify logical relationships between predicates;
for example, that the predicate \emph{\iri{has\u author}} is the inverse of the predicate \emph{\iri{is\u authored\u by}}.
For a formal definition of the RDF standard, see \url{https://www.w3.org/TR/rdf11-concepts}.

RDF is often called a data \emph{format}, which is not correct.
Instead, RDF is a data \emph{model}, and there are various standardized ways to format
-- or as one often says \emph{serialize} -- data that fits that model.
Our toy knowledge graph above is given in the very simple and intuitive \emph{N-Triples} format:
one triple per line, with a \emph{dot} after each triple (to be read like a full stop terminating a sentence).
A related, but more compact format is \emph{Turtle}; we will see an example of that below.
The historically first serialization was \emph{RDF/XML}, which is falling out of fashion
because it is harder to parse than N-Triples or Turtle.
%Each IRI is enclosed in \iri{$\ldots$} \TODO{this was already mentioned at the beginning of the section} and literals are written in quotes \TODO{Say this when literals are introduced for the first time}.
%Datatypes are specified by appending \^{}\^{} to a literal followed by an IRI specifying the type;
%see the next section for an example \TODO{dito}.

\subsection{Our toy knowledge graph, second version}\label{sec:basics:example_2}

The toy knowledge graph above is simpler than is typical in two important ways.
First, typical IRIs are much longer, so that they are universally unambiguous
(not just for the particular knowledge graph, but among all knowledge graphs on the planet, just like an URI).
Second, in most modern knowledge graphs, IRIs have abstract IDs
and the human-readable names and aliases are specified via dedicated predicates.
This makes sense because there is typically more than one name for an entity (just think of different languages) and there are different entities that have the same name.
Additionally, names can change, while identifiers should be persistent.
%
In Section \ref{sec:examples}, we will introduce \emph{Wikidata},
the largest (and de-facto standard) general-purpose knowledge graph of our time.
In Wikidata, Meryl Streep (identified by the URI \emph{\iri{http://www.wikidata.org/entity/Q873}}) has 152 name triples as of this writing, including the following three in English, Latvian, and Ukrainian :
% \emph{\iri{http://www.wikidata.org/entity/Q873}}

\begin{kb2}
  \iri{http://www.wikidata.org/entity/Q873} \iri{http://schema.org/name} "Meryl Streep"@en  . \\
  \iri{http://www.wikidata.org/entity/Q873} \iri{http://schema.org/name} "Merila Strīpa"@lv . \\
	\iri{http://www.wikidata.org/entity/Q873} \iri{http://schema.org/name} "\textukrainian{Меріл Стріп}"@uk .
  %\iri{http://www.wikidata.org/entity/Q873} \iri{http://schema.org/name} "\cyrins{\fontsize{9.3}{11.3}\selectfont\textit{Меріл Стріп}}"@uk .
	%\iri{http://www.wikidata.org/entity/Q873} \iri{http://schema.org/name} "\foreignlanguage{russian}{\textit{Мерил Стрип}}"@ru
  %\iri{http://www.wikidata.org/entity/Q873} $\:$ \iri{http://schema.org/name} $\:$ "\foreignlanguage{japanese}{メリル・ストリープ}"@ja . \\
  %<http://www.wikidata.org/entity/Q873> \> <http://schema.org/name> \> "\foreignlanguage{...}{梅麗·史翠普}"@zh . \\
\end{kb2}


\noindent
Here, \emph{@en}, \emph{@lv}, and \emph{@uk} are \emph{language tags} that explicitly state the language of a string literal.
Full IRIs are long, which makes input files in the N-Triples format large and cumbersome to read.
The so-called \emph{Turtle} format alleviates this in several ways.
In particular, it allows for the definition of \emph{prefixes} as well as for
various useful shortcuts such as specifying multiple triples for the same subject without repeating the subject every time.
In Turtle, and using prefixes and IRIs from Wikidata,
the four triples about Meryl Streep from Section \ref{sec:basics:example_1} (name and alias triples omitted) can be compactly specified as follows.
%Note that the \iri{$\ldots$} are part of the prefixes, so that we do not need them anymore around the prefixed names.

\def\ha{\hspace{1mm}}
\def\hb{\hspace{4mm}}
\def\hc{\hspace{35mm}}
\def\c#1{{\color{gray}#1}}
\begin{kb}
  @prefix wd:  \iri{http://www.wikidata.org/entity/}       \\
  @prefix wdt: \iri{http://www.wikidata.org/prop/direct/} \\
  @prefix xsd: \iri{http://www.w3.org/2001/XMLSchema\#}   \\[2mm]
  wd:Q873 \ha \= wdt:P31 \hb \= wd:Q5 ;        \hc                 \= \c{\# instance of human}    \\
              \> wdt:P21     \> wd:Q6581072 ;                      \> \c{\# gender female}        \\
              \> wdt:P569    \> "1949-06-22"\^{}\^{}xsd:dateTime ; \> \c{\# date of birth}        \\
              \> wdt:P166    \> wd:Q103618 .                       \> \c{\# won award Oscar for Best Actress}
  %wd:Q495980              \> wdt:P166         \> wd:Q103360 . \\
  %...
\end{kb}

\noindent
Note that the prefixed names are just a shorthand for the full IRIs:
for example, \emph{wd:Q873} is exactly equivalent to \emph{\iri{http://www.wikidata.org/entity/Q873}}.
Also note the use of the \emph{semicolon} to specify that the following triple uses the same subject as the previous triple.%
\footnote{There is also the \emph{comma} to specify that the following triple uses the same subject \emph{and predicate} as the previous.}
The comments on the right are not part of the data, but serve to clarify what the IRIs stand for in Wikidata.

\subsection{Reification}\label{sec:basics:reification}

% \TODO{Own subsection about RDF/SPARQL vs.\ DB/SQL?}
Knowledge graphs are strongly related to databases.
In fact, we could quite naturally use a standard relational database to store the triples from a knowledge graph.
The distinguishing feature of the RDF data model is that we do not need
different tables with different schemas%
\footnote{A \emph{schema} for a table specifies a name and a datatype for each column.}.
There is just one big table with the universal subject-predicate-object schema.
This is indeed simple, but gives rise to the question whether all information fits into this simple schema.

%Many pieces of information cannot be trivially expressed as RDF triples.
For example, consider the information about the three Oscars of Meryl Streep,
for her roles in the films ``Kramer vs.\ Kramer'' (1980),
``Sophie's Choice'' (1983), and ``The Iron Lady'' (2012).
A naive but {\bf wrong} way to cast this information into triples would be as follows (temporarily using the simpler N-Triples format with short IRIs again):

\def\ha{\hspace{4mm}}
\def\hb{\hspace{18mm}}
\begin{kb}
  \iri{\merylstreep} \ha \= \iri{\wonaward}    \hb  \= \iri{\bestsupportingactress} . \\
  \iri{\merylstreep}     \> \iri{\wonaward}         \> \iri{\bestactress} . \\
  \iri{\merylstreep}     \> \iri{\wonawardinyear}   \> "1980" . \\
  \iri{\merylstreep}     \> \iri{\wonawardinyear}   \> "1983" . \\
  \iri{\merylstreep}     \> \iri{\wonawardinyear}   \> "2012" . \\
  \iri{\merylstreep}     \> \iri{\wonawardforfilm}  \> \iri{\kramervskramer} . \\
  \iri{\merylstreep}     \> \iri{\wonawardforfilm}  \> \iri{\sophieschoice} . \\
  \iri{\merylstreep}     \> \iri{\wonawardforfilm}  \> \iri{\ironlady} .
\end{kb}

\noindent
The problem with this representation is that we lose information:
from these triples, we can tell which awards Meryl Streep has won,
and for which films, and in which years.
But we cannot tell which award belongs to which film and to which year.

This kind of information seems to require an $n$-ary predicate, where $n > 2$,
instead of the binary predicates represented by triples.%
\footnote{Note that a triple also states the predicate name, hence we need triples, and not only pairs for binary predicates.}
The corresponding graph would then become a \emph{hypergraph}.
For the example above, we could have a $4$-ary predicate called \emph{\iri{award}},
expressed in $5$-tuples (the fifth component is the predicate name) like these:

\def\ha{\hspace{2mm}}
\begin{kb}
\iri{award} \ha \iri{\merylstreep} \ha \iri{\bestsupportingactress} \ha "1980" \ha \iri{\kramervskramer}\\
\iri{award} \ha \iri{\merylstreep} \ha \iri{\bestactress} \ha "1983" \ha \iri{\sophieschoice}\\
\iri{award} \ha \iri{\merylstreep} \ha \iri{\bestactress} \ha "2012" \ha \iri{\ironlady}
\end{kb}

\noindent
We can represent $n$-ary predicates as triples through a simple technique called \emph{reification}.
For each tuple from the $n$-ary predicate, we simply introduce a \emph{mediator entity},
which connects to each component of the tuple through a suitably chosen binary predicate.
In Wikidata, these mediator entities are called \emph{statement nodes} and they have long alphanumerical IDs.
For example, the information about Meryl Streep's 2012 Oscar is represented as follows (including the relevant prefix definitions).
For compactness, we have abbreviated the IRI of the statement node, the full IRI is \emph{wds:Q873-6ad4311a-47f9-8d9b-7c91-d387e71529ac}.
%
\def\ha{\hspace{21mm}}
\def\hb{\hspace{10mm}}
\def\hc{\hspace{2mm}}
\def\hd{\hspace{4mm}}
\begin{kb}
  @prefix wd: $\:\:$ \= \iri{http://www.wikidata.org/entity/} \\
  @prefix wds:       \> \iri{http://www.wikidata.org/entity/statement/} \\
  @prefix p:         \> \iri{http://www.wikidata.org/prop/} \\
  @prefix ps:        \> \iri{http://www.wikidata.org/prop/statement/} \\
  @prefix pq:        \> \iri{http://www.wikidata.org/prop/qualifier/} \\[2mm]
  wd:Q873  \ha      \= p:P166 \hb \= wds:Q873-6ad4311a \hc \= . \hd \= \c{\# award statement node} \\
  wds:Q873-6ad4311a \> ps:P166   \> wd:Q103618            \> ;     \> \c{\# which award} \\
   \> pq:P585   \> "2012"                \> ;     \> \c{\# point in time} \\
   \> pq:P1686  \> wd:Q269810            \> .     \> \c{\# for work}
\end{kb}
%
This representation in Wikidata contains several clever ideas.
First, the statement nodes have a distinct prefix (\emph{wds:}),
and their alphanumerical IDs start with the ID of the entity to which the statement node belongs (\emph{Q873} in this case).
Second, the two predicates to and from the statement node have a similar (but not identical) IRI,
compared to their ``direct'' counterpart that connects two entities without a statement node.
Namely, the suffix is the same, only the prefix differs (\emph{p:} and \emph{ps:} and \emph{pq:} instead of \emph{wdt:}).
Third, the prefix depends on the ``role'' of the predicate for this particular statement node;
predicates with prefix \emph{p:} lead from an entity to a statement node,
predicates with prefix \emph{ps:} lead from the statement node to the information
that could also have been obtained directly via \emph{wdt:},
and predicates with prefix \emph{pq:} lead to additional information.

Technically, \emph{wdt:P166} and \emph{p:P166} and \emph{ps:P166}
(and there is also \emph{pq:P166} and even more variants) are different IRIs.
But they all ``mean'' the same predicate, just in different roles.
In the RDF dataset, this is expressed by a ``meta'' entity  \emph{wd:P166},
which is connected to all these variants and to which the name predicate is connected.
This elegantly solves the problem of having consistent names for a set of predicates with the same general ``meaning''.%
\footnote{Freebase (a knowledge graph introduced in Section \ref{sec:Freebase}) also has statement nodes, called \emph{mediators},
but there is no mechanism to identify the corresponding different variants of a predicate
(like the \emph{P166} variants in the example above) as belonging to the same ``meaning''.}

\def\ha{\hspace{3mm}}
\def\hb{\hspace{30mm}}
\begin{kb}
  wd:P166 \ha \= rdfs:label              \hb \= "award received" . \\
  wd:P166     \> wikibase:directClaim         \> wdt:P166 . \\
  wd:P166     \> wikibase:claim               \> p:P166   . \\
  wd:P166     \> wikibase:statementProperty   \> ps:P166  . \\
  wd:P166     \> wikibase:qualifier           \> pq:P166  .
\end{kb}

\noindent
These tricks and subtleties are elegant and the result of a long collective experience in designing knowledge graphs.
However, they also make querying a knowledge graph hard, even for expert users.
For example, it is asking a lot from a user to understand \emph{and} know that at a certain point in a query,
the variant of the predicate with prefix \emph{pq:} is needed.
We come back to this important issue when we discuss formal query languages (Section \ref{sec:query_languages})
and when we discuss how to assist the user in formulating queries in such a language (Section \ref{sec:advanced_queries}).

\subsection{Other kinds of information}\label{sec:basics:text}

We have seen that complex $n$-ary information can be represented via triples without information loss.
But what about more fuzzy information?
For example, consider the following sentence about a well-known astronaut:\\[1mm]
%
\emph{As Armstrong, whose great-grandfather Friedrich Wilhelm Kötter emigrated from Ladbergen to the United States in 1864, was the first man to walk on the moon in 1969, many citizens of Ladbergen became interested in their American relatives.}\\[1mm]
%
This sentence contains various pieces of information about entities that are found in a knowledge graph such as Wikidata
(the astronaut Neil Armstrong, the municipality of Ladbergen, the Moon, etc.).
But the information is rather complex and not easily cast into triples.
For example, which predicate should we use to express that a person set foot on a celestial body
or to express that a certain group of people became interested in a certain other group due to certain circumstances?
It's not impossible, but a knowledge graph with too many predicates or entities with subtle semantics is impractical.
Indeed, early attempts at constructing knowledge graphs (like the aforementioned CYC)
aimed at such a comprehensive modeling of knowledge and failed.

It is one of the beauties of natural language that it allows the expression of even complex and fuzzy information in an effortless and flexible manner.
Much information is therefore best kept in the form of natural language text.
This makes the combination of knowledge graphs and text
(which makes statements about entities from a knowledge graph in a looser manner) all the more important.
We come back to this in Section \ref{sec:text}.

\section{What knowledge graphs are out there} \label{sec:examples}

%Over the years, many large knowledge graphs have been developed.
%A look into the \emph{Linked Open Data (LOD) Cloud}\TODO{(J) Der Link tut nicht, es gibt \url{cas.lod-cloud.net}, aber nur ohne HTTPS}\footnote{\url{https://lod-cloud.net}}, which provides links to 1500 existing knowledge graphs,
%should be evidence enough.
In this section, we introduce and compare prominent knowledge graphs that are publicly available.
Note that there are also a lot of \emph{enterprise} knowlegde graphs,
that is, knowledge graphs which are used by companies for internal purposes
or which are the basis of their business model.
However, such knowledge graphs are not publicly available and thus out of scope for this section.

Table \ref{table:kg-overview} gives an overview of four \emph{general-purpose} and four \emph{domain-specific} knowledge graphs which are widely used in research and beyond.
Each knowledge graph is given together with metrics describing its \emph{size} (in the columns 2-4) and its \emph{content} (in the columns 5-10).
The precise definitions can be found under \url{https://qlever.cs.uni-freiburg.de/ir-book}.

\begin{tabbing}\hspace*{2mm}\=\hspace*{16mm}\=\kill
\> \#\,Tr. \> the number of all triples in the knowledge graph \\
\> \#\,S   \> the number of distinct subjects \\
\> \#\,P   \> the number of distinct predicates \\[1mm]
\> Direct  \> triples that do not fall into any of the following categories \\
\> Reified \> triples that contain a mediator node; see Section \ref{sec:basics:reification} \\
\> Type    \> triples that specify a type (e.g., via the \emph{rdf:type} predicate) \\
\> Label   \> triples that specify a label, name or title (e.g., via the \emph{rdfs:label} predicate) \\
\> Desc.   \> triples that specify a description (e.g., via the \emph{schema:description} predicate) \\
\> Meta    \> triples that specify meta information (e.g., modification dates)
\end{tabbing}

\noindent
In the following, we give further details to the listed knowledge graphs, each together with a concise summary of its historical background and some general remarks.
A publicly accessible SPARQL endpoint for each of these knowledge graphs is available at \url{https://qlever.cs.uni-freiburg.de}.

\vspace{3mm}
\begin{table}[h]
  \def\arraystretch{1.2}
  \renewcommand{\th}[2]{\makebox[#1][c]{{\small #2}}}
  \newcommand{\thh}[1]{{\small #1}}
  \newcommand{\td}[1]{{\small #1}}
  % \newcommand{\tdd}[2]{{\small\makebox[19pt][r]{#1}} \hfill {\footnotesize (#2\%)}}
  \newcommand{\tdd}[2]{\small #2\,\%}
  \renewcommand{\M}{\small\,\makebox[6pt][l]{M}}
  \renewcommand{\B}{\small\,\makebox[6pt][l]{B}}
  \renewcommand{\K}{\small\,\makebox[6pt][l]{K}}

\begin{tabular}{|l||r|r|r||r|r|r|r|r|r|} \hline
	\thh{Name}     & \textbf{\th{15pt}{\# Tr.}} & \th{15pt}{\# S} & \th{15pt}{\# P} & \th{20pt}{Direct} & \th{20pt}{Reified}  & \th{20pt}{Type}& \th{20pt}{Label} & \th{20pt}{Desc.} & \th{20pt}{Meta}  \\ \hline \hline
	\td{\examplequeryhref{statistics-wikidata}{Wikidata}} & \textbf{\td{18B}} & \td{1.9B} & \td{51K} & \td{7.8\%} & \td{23.4\%} & \td{19.2\%} & \td{14.7\%} & \td{15.7\%} & \td{19.1\%}
	\\ \hline
	\td{\examplequeryhref{statistics-freebase}{Freebase}} & \textbf{\td{3.1B}} & \td{125M} & \td{785K} & \td{3.3\%} & \td{10.3\%} & \td{31.6\%} & \td{41.8\%} & \td{0.8\%} & \td{12.2\%}
	\\ \hline
	\td{\examplequeryhref{statistics-dbpedia}{DBpedia}} & \textbf{\td{839M}} & \td{43M} & \td{55K} & \td{43.1\%} & \td{{\small\,\makebox[6pt][l]{--}}} & \td{20.2\%} & \td{7.5\%} & \td{11.0\%} & \td{18.2\%}
	\\ \hline
	\td{\examplequeryhref{statistics-yago-3}{YAGO 3}} & \textbf{\td{121M}} & \td{15M} & \td{100} & \td{32.2\%} & \td{{\small\,\makebox[6pt][l]{--}}} & \td{20.7\%} & \td{44.0\%} & \td{{\small\,\makebox[6pt][l]{--}}} & \td{3.1\%}
	\\ \hline \hline
	\td{\examplequeryhref{statistics-uniprot}{Uniprot}} & \textbf{\td{112B}} & \td{23B} & \td{237} & \td{31.9\%} & \td{11.7\%} & \td{16.8\%} & \td{10.6\%} & \td{0.8\%} & \td{28.0\%}
	\\ \hline
	\td{\examplequeryhref{statistics-pubchem}{PubChem}} & \textbf{\td{14B}} & \td{3.8B} & \td{395} & \td{10.3\%} & \td{39.6\%} & \td{22.6\%} & \td{22.4\%} & \td{{\small\,\makebox[6pt][l]{--}}} & \td{4.3\%}
	\\ \hline
	\td{\examplequeryhref{statistics-dblp}{DBLP}} & \textbf{\td{374M}} & \td{48M} & \td{68} & \td{29.6\%} & \td{47.4\%} & \td{15.4\%} & \td{4.4\%} & \td{{\small\,\makebox[6pt][l]{--}}} & \td{3.1\%}
	\\ \hline
	\td{\examplequeryhref{statistics-osm-planet}{OSM}} & \textbf{\td{13B}} & \td{1.2B} & \td{92K} & \td{68.7\%} & \td{21.6\%} & \td{8.9\%} & \td{0.7\%} & \td{{\small\,\makebox[6pt][l]{--}}} & \td{{\small\,\makebox[6pt][l]{--}}}
	\\ \hline
\end{tabular}
  \vspace{3mm}
  \caption{An overview of four \emph{general-purpose} knowledge graphs (in the upper half of the table) and four \emph{domain-specific} knowledge graphs (in the lower half of the table).
  %The columns 2-4 provide metrics describing the size of a KG; the columns 5-10 provide metrics describing the contents.
  %The meaning of the columns are as follows:
  An ``--'' entry means that the respective knowledge graph contains no triples of that category.
  All of these statistics have been computed using SPARQL queries. To inspect and run those queries, click on the name of the knowledge graph in the first column of the table or visit \url{https://qlever.cs.uni-freiburg.de/ir-book}.
  }
  \label{table:kg-overview}

  %  \begin{flushleft}

  %   \textbf{Types:} All triples providing the type of an entity, for example: all triples with predicates \emph{wdt:P31/P279*} \newline
  %   \textbf{Labels:} All triples providing a label (or an alias) of an entity, for example all triples with one of the predicates \emph{rdfs:label}; \emph{schema:name}; \emph{schema:alternateName}; \emph{skos:prefLabel}; \emph{skos:altLabel}; \emph{dbo:alias} \newline
  %   \textbf{Desc.:} All triples providing a description of an entity, for example: all triples with one of the predicates \emph{schema:description}; \emph{rdfs:comment} \newline
  %   \textbf{Mediators:} All nodes which are used to express n-ary relations and which themselves do not carry any valueable information. \newline
  %   \textbf{Meta:} All triples providing metadata, for example: all triples with one of the predicates \emph{owl:sameAs}; \emph{prov:wasDerivedFrom} or all triples corresponding to Wikipedia articles, or all triples corresponding to structural information (e.g., the length of a Wikipedia article or the template used in a Wikidedia article) and many more.\newline

  %   * YAGO contains the start/end date of certain events, in RDF* format.
  %   \end{flushleft}
\end{table}

% A general-purpose knowledge graph is a knowledge graph that contains general knowledge about, in principle, all entities of the world.
% In contrast, a domain-specific knowledge graph is a knowledge graph that contains knowledge about entities from a special domain, for example:
% biology, chemistry, geography or bibliographies.\footnote{The definitions are a bit verbose. Are they necessary at all? Should we maybe move them to a previous section?}

\subsection{Wikidata}

Wikidata \cite{DBLP:journals/cacm/VrandecicK14} was released by the \emph{Wikimedia Foundation} in 2012.
It is currently the largest, most comprehensive, and also most popular general-purpose knowledge graph.
Similarly to Wikipedia, Wikidata will probably keep this status for decades to come.
Wikidata uses alphanumerical IRIs following a carefully crafted schema,
in particular for its large portion of reified $n$-ary information;
see the examples in Section \ref{sec:basics}.
In case of disputed, uncertain, contradictory, or historical statements,
Wikidata also provides information as to the \emph{preferred} piece of information.
For example, Wikidata contains 34 statements on the population of New York City at different times,
with the most current one being marked as preferred via a dedicated triple.
On the other hand, Wikidata is still far from complete,
even for ``popular'' information that is available (even in tabular form) in Wikipedia articles.
For example, Wikidata has information about only 9 of the 23 Olympic gold medals won by Michael Phelps.

Wikidata is multilingual and provides labels for entities and predicates in more than 400 languages.
%Each entity and each predicate is identified by an IRI with an alphanumerical ID.
%The subjects IDs are numbers prefixed by \emph{Q} (e.g., the IRI of Meryl Streep is \emph{wd:Q873}); the predicate IDs are numbers prefixed by \emph{P} (e.g., the IRI of predicate \emph{date of birth} is \emph{wdt:P569}).
It is heavily used by different Wikimedia pages;
for example Wikipedia, which uses Wikidata for automatically assembling the interlanguage links (that is, the links of a Wikipedia article to equivalent articles in other languages) or some of the infoboxes (that is, the tables that can be found in the upper right of many articles).
While many older knowledge graphs (see the following sections) are based on the information
from Wikipedia's infoboxes, Wikimedia's long-term goal is the other way round:
to automatically assemble \emph{all} infoboxes from Wikidata.%
\footnote{A list of Wikipedia articles that already use a Wikidata-based infobox can be found at \url{https://w.wiki/_2Rq}.}

To acquire new data, Wikidata uses a semi-crowdsourced approach.
In principle, even unregistered users are allowed to add and update information via the Wikidata website.
However, \emph{high-traffic entities} (that is, entities that are used by $\geq$ 500 Wikimedia pages) can only be changed by privileged users.\footnote{\url{https://www.wikidata.org/wiki/Wikidata:Protection_policy}}
Changes are instantly visible to the public.
Wikidata regularly integrates other datasets as well, for example, open government data or the bibliographies of national libraries.
Integrating the retired knowledge graph Freebase, which we introduce next, is an on-going process \cite{DBLP:conf/www/TanonVSSP16}.

\subsection{Freebase} \label{sec:Freebase}
Freebase \cite{DBLP:conf/sigmod/BollackerEPST08} was started by a company called Metaweb in 2007.
It featured a web interface that allowed (registered) users to add and edit entities in a single click.
In July 2010, Freebase was acquired by Google and became Google's knowledge graph \cite{google-kw}.
In 2016, Freebase was closed to the public.
Around that time, it was the largest general-purpose knowledge graph.
% and to easily browse the data via fast autocompletion search.
Freebase allowed users to add their own predicates, which resulted in an inflated number of predicates of very limited use.
Freebase contains $785\K$ predicates, compared to only $32\K$ predicates in the current version of Wikidata.
However, more than $700\K$ of these predicates are only used in one or two triples.

Freebase provides labels and descriptions in more than 240 languages.
Like Wikidata, Freebase provides a large amount of $n$-ary information, reified via so-called \emph{mediator} nodes.
However, while Wikidata has encoded in its schema which predicates represent the same meaning
and which carry the ``main'' piece of information from an $n$-ary piece of information
(see Section \ref{sec:basics:reification}), Freebase does not contain this information.
Freebase uses IRIs with alphanumerical IDs for entities,
while the IRIs for predicates are human-readable, with a hierarchical structure.%
\footnote{For example, the IRI of Meryl Streep is \emph{fb:m.0h0wc}, while the predicates related to $n$-ary award information
are called \emph{fb:award.award\u winner.awards\u won}, \emph{fb:award.award\u honor.award}, \emph{fb:award.award\u honor.year}, etc. The prefix \emph{fb:} stands for \emph{\iri{http://rdf.freebase.com/ns/}}.}

% Reference for the number of languages in Freebase:
% https://www.uni-trier.de/fileadmin/fb2/LDV/Rettinger/publications/KG-Comparison-SWJ-Article.pdf

% Freebase integrated Wikipedia, NNDB\footnote{\url{https://www.nndb.com/}} or MusicBrainz\footnote{\url{https://musicbrainz.org/}}.

\subsection{DBpedia}
DBpedia \cite{DBLP:journals/semweb/LehmannIJJKMHMK15} was released by researchers at the universities of Leipzig and Berlin in 2007.
In contrast to Wikidata and Freebase, the content of DBpedia is not created manually but automatically extracted from (semi-)structured data of Wikipedia articles, for example, the infoboxes or the categories.
The extracted data are then matched to the DBpedia schema using a rule-based approach.
The rules and the schema can be defined and extended by (privileged) users.
Since 2018, a similar approach is used to also match statements from Wikidata to the DBpedia schema \cite{DBLP:journals/semweb/IsmayilovKALH18}.
In Table \ref{table:kg-overview}, we analyze the \emph{core release} of DBpedia, which only contains statements extracted from Wikipedia.

DBpedia contains many cross-references that connect the entities to equivalent entries in other knowledge graphs and is therefore seen as a \emph{hub} in the LOD cloud.
In the core release, the IDs in the IRIs of the entities are the human-readable Wikipedia page IDs (e.g., \emph{Meryl\u Streep}).
The IDs in the IRIs of the predicates are also human-readable (e.g., \emph{birthDate}).
DBpedia contains many different predicates with a similar or even the same meaning,
which complicates the formulation of meaningful queries considerably.
For example, there are predicates \emph{dbr:birthDate}, \emph{dbo:birthDate}, \emph{dbp:dateOfBirth} and \emph{dbp:datebirth}.
This is due to the use of different identifiers in the Wikipedia infoboxes and due to ambiguous rules created by the DBpedia users.
Even the union of such predicates is usually far from complete, because the Wikipedia infoboxes are far from complete.
DBpedia provides labels for entities and predicates in 125 languages.
In principle, it also provides $n$-ary information,
but the coverage and quality of that information is far below that of Wikidata or Freebase,
again because of the limited information in Wikipedia's infoboxes.
%For example, the information about when and for which movie Meryl Streep won an Oscar is not provided (because the infobox of the Wikipedia article about Meryl Streep does not contain this piece of information).

\subsection{YAGO}
YAGO \cite{DBLP:journals/ws/SuchanekKW08} was released by researchers at the Max Planck Institute for Informatics in 2006.
Like DBpedia, it extracts (semi-)structured data from the infoboxes and categories of Wikipedia articles.
In contrast to DBpedia, the extraction process is not crowd-sourced
but combined with the the concept hierarchy of \emph{WordNet}.%
\footnote{WordNet, \url{https://wordnet.princeton.edu}, is a lexicon for the English language that provides sets of words and concepts with the same meaning (so-called \emph{synsets}) and their hierarchical relations.}
YAGO matches the categories of the Wikipedia articles to the concepts of WordNet and thereby establishes a huge\footnote{YAGO 3 has five times more classes than Wikidata, but is over a 100 times smaller.} hierarchy of classes, but of questionable usefulness.
In particular, there are many overly specific classes (for example, \emph{Plant pathogens and diseases by causal agent}),
many classes with unclear semantics (for example, there is a concept \emph{entry} which contains a subset of songs),
and many canonical classes are missing (for example, there is no category \emph{person}).
With respect to its predicates, YAGO's schema is very compact and much clearer than that of DBpedia, but YAGO also contains less information.

Over time, YAGO was extended by (1) temporal facts extracted from Wikipedia and spatial facts extracted from GeoNames\footnote{\url{https://www.geonames.org/}} (YAGO 2, released in 2010) and (2) multilinguality (YAGO 3, released in 2015).
In 2020, YAGO 4 was released, which, however, does not follow the original idea behind YAGO anymore, as it matches the facts of Wikidata to a schema derived from \emph{schema.org} \cite{DBLP:conf/esws/TanonWS20}.
For that reason, we do not analyze YAGO 4 in Table \ref{table:kg-overview}, but YAGO 3.
Like in DBpedia, the IRIs of the entities and predicates are human-readable:
for example, \emph{yago:Meryl\u Streep} (like the Wikipedia article) or \emph{yago:wasBornOnDate}.
Labels for entities and predicates are provided in more than 300 languages.
%$N$-ary information is not provided.

% In version 4, YAGO started to match the facts of Wikidata to a scheme manually derived from \emph{schema.org}\footnote{\url{https://schema.org/}}.
% The motivation behind is to replace the complex scheme of Wikidata by a simpler and cleaner scheme.
% YAGO uses a mix of human-readable and alphanumerical entity ids: if in Wikidata the entity is linked to an Wikipedia article, the identifier is the title of the Wikipedia article; otherwise the identifier is composed of the English label and the Wikidata identifier. If Wikidata does not provide such a label, the identifier is equal to the Wikidata identifier. \TODO{Give an example.}
% Similarily to Wikidata, YAGO 4 provides labels and descriptions in more than 400 languages.
% In terms of reification, YAGO only provides temporal context information for certain events, but no further context information.


% =================================================================================================

% \subsection{Bio2RDF}
% Bio2RDF \cite{DBLP:journals/jbi/BelleauNTRM08} is an open source project that merges 35 existing diverse and heterogeneously formatted biological datasets (e.g., \emph{ClinicalTrials}\footnote{\url{https://clinicaltrials.gov/}} or \emph{DailyMed}\footnote{\url{https://dailymed.nlm.nih.gov/dailymed/}}) into one large knowledge graph.
% The project was started in October 2008 at the universities of Maastricht and Laval (Qu\'ebec).
% The resulting graph contains different healthcare data, for example: the results of clinical trials, bioactive compounds or the structure of proteins and drugs.
% The labels and descriptions are unilingual and are given in English language.
% The identifiers of the subjects are alphanumerical (e.g., \emph{NCT00233324}) and the identifiers of the predicates are human-readable strings (e.g., \emph{subjects-affected}).
% Unfortunately, each integrated dataset uses its own vocabulary in the graph, which makes querying data across triples originating from different datasets very difficult.

\subsection{UniProt}
UniProt \cite{DBLP:journals/nar/Consortium17a} is the world's largest protein knowledge graph and was released by the \emph{UniProt consortium} in 2002.
%(consisting of the European Bioinformatics Institute (\emph{EMBL-EBI}), the Swiss Institute of Bioinformatics (\emph{SIB}) and the Protein Information Resource (\emph{PIR})).
The knowledge graph is subdivided into the following parts:
the UniProt Archive (\emph{UniParc}), the UniProt knowledge graph (\emph{UniProtKB}) and the UniProt Reference Clusters (\emph{UniRef}).
UniParc contains protein sequences in form of strings, together with some basic information like the protein names.
UniProtKB contains (1) manually and automatically created annotations for the protein sequences in UniParc, for example: descriptions, classifications, or cross-references to other datasets, and (2) references to (scientific) publications that discuss the protein sequences.
UniRef contains clusters of similar protein sequences.
There is a lot of $n$-ary information, for example, the provenance of the annotations or metrics describing the quality of the annotations.
The names, descriptions and all annotations are given in one language (English).
The IDs in the IRIs of the entities are numerical (e.g., the IRI of \emph{SARS-CoV-2} is \emph{uniprot:2697049}), while the IDs in the IRIs of the predicates are human-readable (e.g., \emph{core:scientificName}).
%The schema is clean, simple and easy to understand.

\subsection{PubChem}
PubChem \cite{DBLP:journals/jcheminf/FuBDHWB15} is the world's largest chemistry database and was released by the National Institutes of Health (NIH) in 2004.
It particularly provides comprehensive information about (1) compounds, substances, proteins, genes, and their interrelations, (2) cross references to equivalent entries in other datasets (e.g., UniProt or Wikidata), and (3) references to (scientific) publications which discuss a given topic or concept.
PubChemRDF \cite{DBLP:journals/jcheminf/FuBDHWB15}, an official part of PubChem, provides the data as an RDF knowledge graph.

The IDs of entity IRIs are alphanumerical; for example, the IRI of Aspirin is \emph{pubchem:CID2244}.
Most predicate IRIs are based on alphanumerical IDs (for example, \emph{cheminf:CHEMINF\_000477} connects a molecule to its normalized counterpart).
% but some are also human-readable (for example, \emph{cito:isDiscussedBy}).
Labels and descriptions are only provided in English.
%
PubChem makes heavy use of reification, but in an unusual way.
For example, there is a single huge predicate \emph{has-attribute} (with billions of triples)
that links to mediator objects with IRIs that are the concatenation of subject and relation name
(for example, \emph{descriptor:CID2244{\u}Exact{\u}Mass} or \emph{descriptor:CID2244{\u}Molecular{\u}Formula}).
It would be more natural (and also easier for query engines, see Section \ref{sec:indexing})
to have a separate predicate for each relation
(for example, one predicate for \emph{exact mass} and one for \emph{molecular formula}).

\subsection{DBLP}
DBLP \cite{DBLP:journals/pvldb/Ley09} is a bibliography database focused on topics from computer science which was started at the University of Trier in 1993.
DBLP contains metadata of more than 5 million publications (e.g., their titles, authors, and publication dates) and of more than 2 million authors (e.g., their full names, affiliations, and links to their homepages).
For many years, the dataset was distributed in form of a large single XML file.
Since 2021, an RDF dump of the data is available as well.

DBLP provides entity labels like the publication titles or the author names only in one language (i.e., in the language in which the entities appear in the literature) and is therefore, from a technical point of view, unilingual.
The IDs of the entity IRIs are sometimes alphanumerical and sometimes human-readable.
For example, some authors are identified by IRIs with numerical IDs (e.g., \emph{dblp\u pid:6304} or \emph{dblp\u pid:10012-1}), other authors by IRIs containing their full names (e.g., \emph{dblp\u pid:PeterStone}).
The IRIs belonging to predicates contain human-readable IDs (e.g., \emph{dblp:authoredBy}).
There are also reified statements that provide the authors of a publication in the same order in which they appear on the publication.

\subsection{OpenStreetMap (OSM)}
OSM \cite{osm} is an open source project that was started by Steve Coast in 2004.
Its goal is to provide freely accessible map data for the world in a crowd-sourced manner.
Each OSM object has a geometric shape (a point, line, or multi-polygon, depending on the nature of the object)%
\footnote{Typical examples are: a park bench (point), a road or river (line), or a country border (multi-polygon).},
as well as structured information in the form of key-value pairs
(for example the name of a river or the type of a street).
%OSM principally provides the following kinds of information:
%(1) the coordinates of standalone \emph{points}, like a park bench or a street lamp,
%(2) the coordinates of linear \emph{ways} like roads, rivers or territorial borders,
%(3) relations between points and/or ways, for example, the streets that form a bus route,
%(4) descriptive tags for points, ways and relations, for example, street names or the opening hours of a shop.
For Table \ref{table:kg-overview} above, we have used the OSM2RDF project (\url{https://osm2rdf.cs.uni-freiburg.de/}) which converts the OSM data to RDF in a straightforward way,
with one triple per shape (using WKT literals)\footnote{See \url{https://en.wikipedia.org/wiki/Well-known_text_representation_of_geometry}}, and one triple per key-value pair.
We have only included OSM objects with at least one key-value pair.
A related project, which provides only a smaller portion of the OSM data, is described on
\url{https://wiki.openstreetmap.org/wiki/Sophox}.
%Originally, the data is not distributed in form of RDF, but in the custom OSM format (which is actually an XML derivative).
%However, there is a project at the University of Freiburg that translates OSM to RDF.
%\TODO{Not true: OSM is unilingual and does not contain $n$-ary information.}
%The IRIs belonging to the nodes, ways and relations contain numerical IDs; e.g., the IRI of the entity \emph{Freiburg im Breisgau} is \emph{osmnode:240092010}.
%The IRIs belonging to the predicates contain human-readable IDs; e.g., the IRI of the predicate providing the capital of a country is \emph{osmkey:capital\_city}.

% =================================================================================================

% \vspace{3mm}\noindent\textbf{Size.}
% The first aspect concerns the size of a KG.
% Most generally, the size is specified by e.g., the number of unique entities (resp. vertices), the number of unique properties (resp. edges), or the number of triples.
% Even these numbers give some kind of insights into the dimension of a KG, they can be deceptive, because they usually do not say anything about the degree of information density of the KG.
% Let us illustrate this on a simple example:

% \begin{kb}
%   \iri{Angela Merkel} $\:$ \= $<$has-father$>$ $\:$ \= \iri{Horst Kasner} . \\
%   \iri{Horst Kasner} \> $<$has-child$>$ \> \iri{Angela Merkel} . \\
% \end{kb}
% Above triples are so called \emph{bidirectional} triples.
% They represent the exact same fact (\emph{Angela Merkel is a child of Horst Kasner}) but model this fact in opposite directions.
% One of the two triples is redundant, because it does not add any new information compared to the other triple.
% So a KG with bidirectional triples consists of up to twice as many triples as the same KG with unidirectional triples but without containing more information.

% Further, KGs can include different \emph{intermediate nodes} and \emph{meta triples} that are necessary to, for example, implement reification or document the provenance of facts.
% Consider the following example triples:

% \begin{kb}
%   \iri{Angela Merkel} \qquad \= \iri{spouse} \qquad \= $<$AM-spouse-\#1$>$ . \\
%   $<$AM-spouse-\#1$>$ \> \iri{spouse} \> \iri{Joachim Sauer} . \\
%   $<$AM-spouse-\#1$>$ \> \iri{start time} \> 1998-12-30 . \\
%   $<$AM-spouse-\#1$>$ \> \iri{reference} \> $<$AM-spouse-\#1-ref$>$ . \\
%   $<$AM-spouse-\#1-ref$>$ \> $<$stated-in$>$ \> \iri{Integrated Authority File} . \\
%   $<$AM-spouse-\#1-ref$>$ \> \iri{retrieved} \>  2020-08-21 . \\
% \end{kb}
% The first three triples express the fact that \emph{Angela Merkel} is married with \emph{Joachim Sauer} since 1998.
% Note the intermediate node \emph{AM-spouse-\#1} required to add the start time of the marriage.
% The last three triples are used to document where this information comes from and when it was retrieved; they should be seen more as comments rather than as real facts.
% Obviously, intermediate nodes and meta triples increases the size of a KG but don't add any real facts.
% \TODO{Find good metrics which we want to use to assess the "real" size of KGs and describe them here.}
% \TODO{Should we consider statements with predicates like "sameAs", "label" ("alternateName"),  }

% \vspace{3mm}\noindent\textbf{Content.}

% This aspect concerns the actual content of a KG.
% In case of a \emph{domain-specific} KG, we examine the domain(s) covered by the KG.
% In case of a \emph{general-purpose} KG, we analyze if there are certain domains that are more represented than others.
% We then analyze the actual facts, including:
% (1) the provenance of the data behind the facts;
% (2) how the facts are generated from the data, in particular: how the data is matched to the existing ontology;
% (3) whether this process happens automatically or manually; and
% (4) whether there is some kind of effort to ensure the correctness of the  generated facts, and if so, how does it work; and
% (5) in how many languages the facts are provided.
% We finally discuss how up-to-date a KG is and whether it is updated regularly, and if so, in which intervals.

% \vspace{3mm}\noindent\textbf{Format / Structure.}
% This aspect concerns the internal format and structure of a KB.
% We particularly analyze the concrete format of the facts, for example whether they are stored as triples or quadruples and whether the entities and properties are identified by human-readable or numerical ids.
% We further investigate the structure of the used ontology, in particular whether it supports reification and if so, how it is implemented.
% We finally discuss to which extent a KG fulfills the Semantic Web Standards proposed by the \emph{W3C}, for example: whether the ontology complies the \emph{RDF} and/or \emph{OWL} specifications or whether the data can be queried with \emph{SPARQL}.

% \vspace{3mm}\noindent\textbf{Relevance.}
% The last aspect is dedicated to the relevance of a KG, both in the past and the present.
% To assess the relevance of a KG, we consider
% (1) the quality, up-to-dateness and exclusivity of the contained data;
% (2) the impact of the KG on research;
% (3) the amount of usage in different communities; and
% (4) the degree of linkage with other knowledge graphs.
% We conclude by trying to predict the future of each KG, that is: how the KG will grow over the next decade and how relevant it will remain.

% \begin{table}
%   \def\arraystretch{1.2}
%   \renewcommand{\th}[1]{{\small #1}}
%   \newcommand{\td}[1]{{\small #1}}
%   \newcommand{\tdd}[2]{{\small\makebox[19pt][r]{#1}} \hfill {\footnotesize (#2\%)}}
%   \caption{The dimensions of some knowledge graphs commonly used in practice. The percentages are relative to the total number of triples in a KB.}
%   \label{table:kbs}
%   \begin{tabular}{|l|c|c|c||c|c|c|c|c|} \hline
%     \th{Name}     & \th{Entities} & \th{Props.}   & \th{Triples} & \th{Types}       & \th{Labels}      & \th{Desc.}       & \th{Mediators} & \th{Meta}        \\ \hline \hline
%     \th{Wikidata} & \td{1.7B}     & \td{42,352}   & \td{15.1B}   & \tdd{1.5B}{9.9}  & \tdd{1.3B}{8.6}  & \tdd{2.1B}{13.9} & 978M           & \tdd{6.2B}{41.1} \\ \hline
%     \th{Freebase} & \td{164M}     & \td{786,350}  & \td{2.1B}    & \tdd{799M}{38}   & \tdd{128M}{6.1}  & \tdd{7.5M}{0.4}  & ?              & \tdd{501M}{23.9} \\ \hline
%     \th{DBpedia}  & \TODO{\td{75M}} & \TODO{87,469} & \TODO{596M}  & \TODO{\tdd{67M}{11.2}} & \TODO{\tdd{32.5M}{5.4}} & \TODO{\tdd{12.5M}{2.1}} & \TODO{2.6M} & \TODO{\tdd{225M}{37.6}}       \\ \hline
%     \th{YAGO 4}   & 533M          & \td{1,436}    & \td{4.7B}    & \tdd{247M}{5.3}  & \tdd{372M}{7.9}  & \tdd{1.4B}{29.8} & 0*             & \tdd{116M}{2.5}  \\ \hline \hline
%     \th{Bio2RDF}  & ?             & ?             & ?            & ?                & ?                & ?                & ?              & ?                \\ \hline
%     \th{UniProt}  & ?             & ?             & ?            & ?                & ?                & ?                & ?              & ?                \\ \hline
%     \th{PubChem}  & ?             & ?             & ?            & ?                & ?                & ?                & ?              & ?                \\ \hline
%     \th{DBLP}     & ?             & ?             & ?            & ?                & ?                & ?                & ?              & ?                \\ \hline
%   \end{tabular} \\[10pt]
%  \begin{flushleft}

%   \textbf{Types:} All triples providing the type of an entity, for example: all triples with predicates \emph{wdt:P31/P279*} \newline
%   \textbf{Labels:} All triples providing a label (or an alias) of an entity, for example all triples with one of the predicates \emph{rdfs:label}; \emph{schema:name}; \emph{schema:alternateName}; \emph{skos:prefLabel}; \emph{skos:altLabel}; \emph{dbo:alias} \newline
%   \textbf{Desc.:} All triples providing a description of an entity, for example: all triples with one of the predicates \emph{schema:description}; \emph{rdfs:comment} \newline
%   \textbf{Mediators:} All nodes which are used to express n-ary relations and which themselves do not carry any valueable information. \newline
%   \textbf{Meta:} All triples providing metadata, for example: all triples with one of the predicates \emph{owl:sameAs}; \emph{prov:wasDerivedFrom} or all triples corresponding to Wikipedia articles, or all triples corresponding to structural information (e.g., the length of a Wikipedia article or the template used in a Wikidedia article) and many more.\newline

%   * YAGO contains the start/end date of certain events, in RDF* format.
%   \end{flushleft}
% \end{table}

% \begin{table}
%   \def\arraystretch{1.3}
%   \caption{The dimensions of the knowledge graphs commonly used in practice. The percentages are relative to the total number of triples in a KB.}
%   \renewcommand{\th}[1]{{\small #1}}
%   \newcommand{\td}[2]{{\normalsize\makebox[24pt][r]{#1}} \hfill {\small (#2\%)}}
%   \label{table:kbs}
%   \begin{tabular}{|l|c|c|c|c||c|c|c|c|} \hline
%                              & \th{Wikidata [a]} & \th{Freebase [b]} & \th{DBpedia [c]}       & \th{YAGO 4 [d]} & \th{Bio2RDF} & \th{UniProt} & \th{PubChem} & \th{DBLP}  \\ \hline \hline
%   \th{\# entities}          & 1.7B               & 164M              & \TODO{75M}             & 533M            & ?            & ?            & ?            & ?          \\ \hline
%   \th{\# predicates}        & 42,352             & 786,350           & \TODO{87,469}          & 1,436           & ?            & ?            & ?            & ?          \\ \hline
%   \th{\# triples}           & 15.1B              & 2.1B              & \TODO{596M}            & 4.7B            & ?            & ?            & ?            & ?          \\ \hline \hline
%   \th{\# type triples [1]}  & \td{2.2B}{14.6}    & \td{799M}{38}     & \TODO{\td{65M}{10.9}}  & \td{247M}{5.3}  & ?            & ?            & ?            & ?          \\ \hline
%   \th{\# label triples [2]} & \td{1.2B}{7.9}     & \td{125M}{5.9}    & \TODO{\td{23.8M}{4}}   & \td{304M}{6.5}  & ?            & ?            & ?            & ?          \\ \hline
%   \th{\# desc. triples [3]} & \td{2B}{13.2}      & \td{7.5M}{0.4}    & \TODO{\td{43.2M}{7.2}} & \td{1.4B}{29.8} & ?            & ?            & ?            & ?          \\ \hline
%   \th{\# alias triples [4]} & \td{70M}{0.5}      & \td{3.6M}{0.2}    & \TODO{\td{64K}{0.01}}  & \td{68M}{1.4}   & ?            & ?            & ?            & ?          \\ \hline
%   \th{\# sameAs triples [5]} & \td{2.6M}{0.02}   & \td{60.3M}{2.9}   & \TODO{\td{10.5M}{1.8}}  & \td{116M}{2.5}   & ?            & ?            & ?            & ?          \\ \hline
%   \th{\# qualifier triples [6]} & \td{139M}{0.9} & \td{?}{?}         & \TODO{\td{19.8M}{3.3}}       & \td{2.5M}{0.05}  & ?            & ?            & ?            & ?          \\ \hline
%   \th{\# proven. triples [7]} & \td{1B}{7.6}     & \td{4.6M}{0.2}    & \TODO{\td{19M}{3.2}}   & \td{0}{0}       & ?            & ?            & ?            & ?          \\ \hline
%   \th{\# citations [8]}     & \td{174M}{1.2}     & \td{628}{0}       & \TODO{\td{0}{0}}       & \td{174M}{3.7}  & ?            & ?            & ?            & ?          \\ \hline
%   \th{\# bidir. facts [9]}  & \td{?}{?}          & \td{?}{?}         & \TODO{\td{?}{?}}       & \td{?}{?}       & ?            & ?            & ?            & ?          \\ \hline
%   \th{\# meta facts [10]}    & \td{950M}{6.3}     & \td{984K}{0.05}   & \TODO{\td{160M}{26.8}} & \td{0}{0}      & ?            & ?            & ?            & ?          \\ \hline

%   \end{tabular} \\[10pt]
%   \begin{flushleft}
%   [a] \url{https://qlever.cs.uni-freiburg.de/Wikidata} \newline
%   [b] \url{https://qlever.cs.uni-freiburg.de/Freebase} \newline
%   [c] \url{http://alicudi:7001/} (core, see \url{https://databus.dbpedia.org/dbpedia/collections/latest-core}) \newline
%   [d] \url{http://alicudi:7002/} \newline

%   [1] All triples with one of the predicates: \emph{rdf:type}; \emph{wdt:P31} (instance of); \emph{fb:type.object.type}; \emph{fb:type.type.instance}\newline % http://www.w3.org/1999/xhtml/class
%   [2] All triples with one of the predicates: \emph{rdfs:label}; \emph{schema:name}; \emph{skos:prefLabel}; \emph{wdt:P2093} (author name string); \emph{fb:type.object.name}; \emph{fb:common.notable\_for.display\_name}; \emph{foaf:name}; \emph{dbo:title};  \newline
%   [3] All triples with one of the predicates: \emph{schema:description}; \emph{rdfs:comment}; \emph{fb:common.topic.description}; \emph{dbo:abstract}; \emph{dbp:abstract}; \emph{dbo:description}; \emph{dct:subject}; \emph{dct:description} \newline
%   [4] All triples with one of the predicates: \emph{skos:altLabel}; \emph{schema:alternateName}; \emph{fb:common.topic.alias}; \emph{dbo:alias}; \newline
%   [5] All triples with one of the predicates: \emph{owl:sameAs}; \emph{fb:common.topic.topic\_equivalent\_webpage}; \newline
%   [6a] All triples with a predicate in namespace \emph{pq:} and \emph{pqv:}. \TODO{pqv: points to a \emph{full} value node, should we also consider the outgoing edges of this node?}\newline
%   % [6c] % All triples with a subject or object ending with "\_\_1" (?);
%   [6d] from \url{https://suchanek.name/work/publications/eswc-2020-yago.pdf}; \newline
%   [7a] All triples with a predicate \emph{prov:wasDerivedFrom}, and all triples with a subject of type \emph{wikibase:Reference}. \TODO{Predicates in namespace \emph{prv:} points to a \emph{full} value node, should we also consider the outgoing edges of this node?} \newline
%   [7b] All triples with a predicate \emph{fb:common.document.source\_uri} (?) \newline
%   [7c] All triples with a predicate \emph{prov:wasDerivedFrom}\newline
%   [8] All triples with one of the predicates: \emph{wdt:P2860} (cites work); \emph{fb:book.cited\_work.cited\_in}; \emph{fb:book.scholarly\_work.works\_cited}; \emph{dbp:isCitedBy}; \emph{schema:citation} \newline
%   [9] All triple pairs with the subject of the first triple being the object of the second triple; and the object of the first triple being the subject of the second triple. \newline
%   [10a] All triples with a subject or object of type \emph{schema:Article} or \emph{schema:Dataset}; \newline
%   % [13] all triples with predicates starting with \emph{fb:wikipedia.*} (specifiying e.g., the id of the relating Wikipedia article)\newline
%   % [14] all triples with predicates \emph{dbp:wikiPageUsesTemplate}, \emph{dbo:wikiPageId}, \emph{dbo:wikiPageRevisionId}, \emph{dbo:wikiPageRedirects}, \emph{dbo:wikiPageLength}, \emph{dbo:wikiPageExternalLink}, \emph{dbo:wikiPageDisambiguates}, \emph{dbo:wikiPageInterLanguageLink}, \emph{dct:subject} \newline
%   % [15] \newline

%   \end{flushleft}
% \end{table}

% ==================================================================================================

\section{How to search a knowledge graph: structured query languages}\label{sec:query_languages}

Knowledge graphs allow semantically precise queries to retrieve information.
%In this section, we discuss the basics of SPARQL and one popular related query language (Cypher).
%We present GraphQL, another query language which sounds related but actually is not.
In this section, we discuss three formal query languages: SPARQL, Cypher, and GraphQL.
As it turns out, GraphQL is actually \emph{not} a query language for knowledge graphs,
but often mistaken for one because of its name; hence we briefly discuss it here as well.
\citet{DBLP:journals/csur/AnglesABHRV17} give a more detailed account,
and they also discuss \emph{Gremlin}, a close relative of Cypher.
In Section \ref{sec:advanced_queries}, we discuss the important topic of how to make formal query languages
accessible to non-expert users (via SPARQL autocompletion and question answering).


\subsection{SPARQL}\label{sec:query_languages:sparql}

SPARQL (\emph{SPARQL Protocol And RDF Query Language}) is the de-facto standard query language for RDF knowledge graphs,
as described in Section \ref{sec:basics}.
We will explain the most important concepts of SPARQL's {\SELECT} queries by example.
For the full specification, see \url{https://www.w3.org/TR/sparql11-overview};
be warned though that it's not an easy read.

\para{Example 1.}
\def\sparqlentity{?x}
The following SPARQL query asks for all female Oscar winners.

\begin{sparql}
  {\SELECT} {\sparqlentity} ?award {\WHERE} \{ \\
  \> \sparqlentity  \> \iri{\isa}    \>  \iri{Person}   \> . \\
  \> \sparqlentity  \> \iri{\gender}	\> \iri{Female} \> . \\
  \> \sparqlentity  \> \iri{\wonaward}    \>  ?award   \> . \\
  \> ?award   \> \iri{\isa}  \>  \iri{Oscar}  \> \\
  \}
\end{sparql}

\noindent
Using the toy knowledge graph from Section \ref{sec:basics:example_1},
the result is the following table with two columns and two rows:

\begin{kb}
  \emph{\textbf{?x}} \hspace{60mm} \= \emph{\textbf{?award}} \\
  \iri{\merylstreep}   \> \iri{\bestactress} \\
  \iri{\carter}        \> \iri{\bestdesign}
\end{kb}

\noindent
The query consists of a {\SELECT} clause and a {\WHERE} clause.
The {\SELECT} clause specifies a sequence of variables, separated by spaces (in the example: \emph{\sparqlentity} \emph{?award}).
In SPARQL, variables start with a question mark.
%Each variable in the {\SELECT} clause produces one column in the result table.
In our example, the {\WHERE} clause consists of a sequence of four triples.
Each element of a triple can be an IRI (like \iri{\isa} or \iri{Female}),
a variable (like \emph{?x} or \emph{?award}) or a literal (there is none in the query above).
The result of the query is a table with $k$ columns, where $k$ is the number of variables in the {\SELECT} clause ($k = 2$ in our example).
A row of the result table corresponds to an assignment of each variable of the {\WHERE} clause to an IRI or literal.
Each assignment must \emph{match} in the sense that each triple of the {\WHERE} clause exists in the knowledge graph, when plugging in the entity or literal for each variable.
For the query above on our toy knowledge graph, there are two such assignments.
%For example, one row assigns \emph{\iri{\merylstreep}} to \emph{\sparqlentity}
%and \emph{\iri{\bestactress}} to \emph{?award}.
%Comparing the triples in the query with the knowledge graph in Section \ref{sec:basics:example_1}, we see that this is in fact the only assignment that \emph{matches}.

\para{Example 2.}
Let us next look at a query with prefixed names, as explained in Section \ref{sec:basics:example_2},
and reified triples, as explained in Section \ref{sec:basics:reification}.
The knowledge graph is Wikidata, and we have omitted the definition of the prefixes to save space.%
\footnote{See \url{https://en.wikibooks.org/wiki/SPARQL/Prefixes} for the definitions of all the Wikidata prefixes.}
Since Wikidata uses IRIs with alphanumerical IDs,
we added comments with the canonical names to make it easier to understand the query.
The query asks for all Oscars of Meryl Streep and the movies she won them for.

\def\ha{\hspace{3mm}}
\def\hb{\hspace{5mm}}
\def\hc{\hspace{7mm}}
\def\hd{\hspace{22mm}}
\def\c#1{{\color{gray}#1}}
\begin{sparql}
  %{\PREFIX} rdfs: <http://www.w3.org/2000/01/rdf-schema\#> \\
  %{\PREFIX} wdt: <http://www.wikidata.org/prop/direct/> \\
  %{\PREFIX} ps: <http://www.wikidata.org/prop/statement/> \\
  %{\PREFIX} pq: <http://www.wikidata.org/prop/qualifier/> \\
  %{\PREFIX} p: <http://www.wikidata.org/prop/> \\
  %{\PREFIX} wd: <http://www.wikidata.org/entity/> \\ [2mm]
  {\SELECT} ?award\u name ?film\u name {\WHERE} \{ \\
    \ha\= wd:Q873 \hb\= p:P166    \hc\= ?m .       \hd\=\c{\# Meryl Streep award received} \\
       \> ?m           \> pq:P1686     \> ?film\u id .     \>\c{\# for work} \\
       \> ?m           \> ps:P166      \> ?award\u id .    \>\c{\# award received} \\
       \> ?award\u id  \> wdt:P31      \> wd:Q19020 .   \>\c{\# instance of Academy Awards} \\
       \> ?film\u id   \> rdfs:label   \> ?film\u name .  \>\c{\# canonical name} \\
       \> ?award\u id  \> rdfs:label   \> ?award\u name . \>\c{\# canonical name} \\
       \> {\FILTER}({\LANG}(?film\u name)=``en'') . \\
       \> {\FILTER}({\LANG}(?award\u name)=``en'') . \\
  \}
	%\\ [2mm]
  %{\ORDERBY} ?entityLabel
  \\ \examplequery{oscars-meryl-streep}
\end{sparql}

\noindent
The result on the complete Wikidata is the following table with two columns,
one for each variable in the {\SELECT} clause, and three rows,
one for each of Meryl Streep's Oscars.

\begin{kb}
  \emph{\textbf{?award\u name}} \hspace{60mm} \= \emph{\textbf{?film\u name}} \\
  ``Academy Award for Best Supporting Actress''@en \> ``Kramer vs. Kramer''@en \\
  ``Academy Award for Best Actress''@en \> ``Sophie's Choice''@en \\
  ``Academy Award for Best Actress''@en \> ``The Iron Lady''@en
\end{kb}

\noindent
The keyword {\FILTER} restricts the result table to rows that fulfill the specified expression.
For the query above, we filter the names by language.
Otherwise, for each row in the result above, we would have obtained $k_1 \cdot k_2$ rows,
where $k_1$ is the number of names for the award
and $k_2$ is the number of names for the film (one name per language).
On the current version of Wikidata, the result would then have
$79 \cdot 42 + 76 \cdot 60 + 79 \cdot 52 = 11,986$ rows.
This cross-product phenomenon is typical for SPARQL queries,
and we come back to it in Section \ref{sec:indexing}.
% QLever results:
% best actress:		76 languages
% best supp. actr.:	70 languages
% Sophies choice:	41 languages ... 41 * 76 = 3116
% K. vs. K.:		57 languages ... 57 * 70 = 3990
% Iron Lady:		50 languages ... 50 * 76 = 3800
% (I've used the results from WDQS in the text.)
% HB: Total = 10,906
% current results:
% best actress:		79 languages
% best supp. actr.:	76 languages
% Sophies choice:	42 languages ... 42 * 79 = 3318
% K. vs. K.:		60 languages ... 60 * 76 = 4560
% Iron Lady:		52 languages ... 52 * 79 = 4108
% Total = 11,986
%Note that there are currently labels in $79$ languages for the Academy Award for Best Actress and labels in $42$ languages for Sophie's Choice.
%Without the filters, we would get $79 \cdot 42 = 3318$ rows for this Oscar instead of a single row.
%Altogether, the filters reduce
%%This reduces the number of rows in the result from over $10\K$ to $3$.
% \TODO{It's not 100\% clear why the table contains 10K rows without FILTERs}
Another expression commonly used with filters is \emph{\REGEX(?literal, r)}, where \emph{?literal} is a variable that represents a literal.
It evaluates to true if \emph{?literal} matches the regular expression $r$;
see Section \ref{sec:autocompletion} for examples.

\para{Example 3.}
Our third query introduces yet more concepts that are explained below.
The query asks for all human Oscar winners, sorted by the number of Oscars they won.
Again, we have omitted the prefix definitions and added comments.

\def\hb{\hspace{5mm}}
\def\hc{\hspace{14mm}}
\def\hd{\hspace{20mm}}
\begin{kb}
  %{\PREFIX} rdfs: <http://www.w3.org/2000/01/rdf-schema\#> \\
  %{\PREFIX} wd: <http://www.wikidata.org/entity/> \\
  %{\PREFIX} wdt: <http://www.wikidata.org/prop/direct/> \\
  %{\PREFIX} ps: <http://www.wikidata.org/prop/statement/> \\
  %{\PREFIX} p: <http://www.wikidata.org/prop/> \\ [2mm]
  {\SELECT} \= ?winner\u id \\
            \> ({\SAMPLE}(?winner\u name) {\AS} ?winner) \\
            \> ({\COUNT}(?award\u id) {\AS} ?count) \\
  {\WHERE} \{ \\
    \ha\= ?winner\u id \hb \= wdt:P31       \hc\= wd:Q5 .       \hd\= \c{\# instance of human} \\
    \>    ?winner\u id    \> p:P166/ps:P166    \> ?award\u id .    \> \c{\# award received} \\
    \>    ?award\u id     \> wdt:P31           \> wd:Q19020 .      \> \c{\# instance of Academy Awards} \\
    \>    ?winner\u id    \> rdfs:label        \> ?winner\u name . \> \c{\# label} \\
    \> {\FILTER} ({\LANG}(?winner\u name) = ``en'') . \\
\} \\
{\GROUPBY} ?winner\u id \\
{\ORDERBY} {\DESC}(?count) ?winner
\\ \examplequery{oscar-winners}
\end{kb}

\noindent
At the end of the query, we used so-called \emph{solution modifiers}, with the following semantics.
%The keyword {\GROUPBY} indicates that we want to aggregate (or \emph{group}) all rows with the same \emph{?winnerID},
The \emph{{\GROUPBY}} aggregates all rows with the same value for the specified variables
(multiple variables are possible).
In the result, there will hence be exactly one row for each \emph{winner\u id}.
For the other variables, we then have to state how we want their values to be aggregated.
The \emph{{\SAMPLE}(?winner\u name)} means that we want to pick the value of \emph{winner\u name} from any of the rows.
Note that for the query above, there is only one (English) name per winner,
and so all the rows of one winner (with the different Oscars) contain the same name anyway.
The \emph{{\COUNT}(?award\u id)} counts the number of entries in the specified column.
Note that this is exactly the number of rows in the group, independent of the variable.
We could have also written \emph{{\COUNT}({\DISTINCT} ?award\u id)},
asking for the number of \emph{distinct} entries in the specified column.
%
The keyword \emph{{\ORDERBY}} asks for an ordering of the result rows,
the keyword \emph{{\DESC}} asks for descending order (the default is ascending order),
and the two arguments specify the primary and secondary sort key (any number of keys is possible).
Counts are sorted numerically, string literals and IRIs are sorted lexicographically.

The \emph{p:P166/ps:P166} in the {\WHERE} clause is called a \emph{predicate path}.
It is equivalent to having the two triples \emph{?winner\u id p:P166 ?x} and \emph{?x ps:P166 ?award\u id},
but it avoids the intermediate variable \emph{?x}.
Note that using \emph{wdt:P166} instead of \emph{p:P166/ps:166}
would ask for the \emph{distinct} categories of Academy Awards a person won.
This is because the predicate \emph{wdt:P166} only knows that Meryl Streep won, for example,
an \emph{``Academy Award for Best Actress''}, but not how often.
%
The following is an excerpt from the result table.
The full result has over $2000$ rows (one per Oscar winner).
Understand that it is no coincidence that the winner names in the last entries starts with \emph{Z}.

\begin{kb}
  \emph{\textbf{?winner\u id}} \hspace{30mm} \= \emph{\textbf{?winner}} \hspace{30mm} \= \emph{\textbf{?count}} \\
  wdt:Q8704      \> ``Walt Disney''      \> 24  \\
  wdt:Q727904    \> ``Cedric Gibbons''   \> 11  \\
  wdt:Q367032    \> ``Alfred Newman''    \> 9   \\
  \dots                                         \\
  wdt:Q350704    \> ``Max Steiner''      \> 3   \\
  wdt:Q873       \> ``Meryl Streep''     \> 3   \\
  wdt:Q692550    \> ``Michael Kahn''     \> 3   \\
  \dots                                         \\
	wdt:Q16210211  \> ``Zoltan Elek''      \> 1   \\
  wdt:Q220548    \> ``Zoran Perisic''    \> 1   \\
  wdt:Q111342771 \> ``Zsuzsanna Sipos''  \> 1   \\
\end{kb}

\para{Example 4.}
With our fourth query, we introduce the {\OPTIONAL} keyword and explain its subtle semantics.
The query asks for all Canadian astronauts and their Hindi name, if they have one, and if not their Arabic name.

\def\hb{\hspace{5mm}}
\def\hc{\hspace{5mm}}
\def\hd{\hspace{10mm}}
\begin{sparql}
{\SELECT} ?astronaut ?name {\WHERE} \{ \\
    \ha\= ?astronaut \hb\= wdt:P106 \hc\= wdt:Q11631 .    \hd\=\c{\# occupation astronaut} \\
       \> ?astronaut    \> wdt:P27     \> wd:Q16 .           \>\c{\# nationality Canadian} \\
       \> OPTIONAL \{ ?astronaut rdfs:label ?name . {\FILTER}({\LANG}(?name)=``hi'') \} \\
       \> OPTIONAL \{ ?astronaut rdfs:label ?name . {\FILTER}({\LANG}(?name)=``ar'') \} \\
  \} %\\ [2mm]
  \\ \examplequery{canadian-astronauts}
\end{sparql}

\noindent
In the previous three example queries, all results were tables with an entry in every cell.
More generally, a table entry can also be {\UNDEF}.%
\footnote{In the SPARQL standard, a result is more formally defined
as a sequence of \emph{bindings} of the variables in the {\SELECT} clause.
Each binding corresponds to a table row, with an {\UNDEF} value in each columns where the respective variable is unbound.}
To understand the result of the query above,
it will be crucial to understand how {\UNDEF} values originate
and what their semantics is when joining tables.

According to the SPARQL standard, the two {\OPTIONAL} clauses in the query are processed one after the other, top to bottom. The first {\OPTIONAL} computes a so-called \emph{optional join} between the following two tables. The table on the left is the result of the first two lines of the query. The table on the right is the result of the \emph{\{ $\ldots$ \}} after the first {\OPTIONAL} in the query. We only show three lines of each table; the number in parentheses gives the total number of rows.

\def\ha{\hspace{7mm}}
\def\hb{\hspace{30mm}}
\vspace{2mm}
\begin{minipage}[t]{0.45\textwidth}
All Canadian astronauts (15)
\begin{kb}
  ?astronaut \ha\=  \\[1mm]
  wd:Q16297    \>\c{\# William Shatner} \\
  wd:Q1687593  \>\c{\# Jeremy Hansen}   \\
	wd:Q240769   \>\c{\# Julie Payette}   \\
	$\ldots$
\end{kb}
\end{minipage}
%
\begin{minipage}[t]{0.5\textwidth}
All entities with their Hindi name (700,475)
\begin{kb}
  ?astronaut  \ha\=?name                  \\[1mm]
  wd:Q10002   \> "\texthindi{इंसकेडी}"@hi   \\
  wd:Q17601   \> "\texthindi{घर्डै प्रांत}"@hi   \\
	wd:Q240769  \> "\texthindi{जूली पयेटे}"@hi   \\
	$\ldots$
	% "\foreignlanguage{hindi}{जूली पयेटे}" . \\
\end{kb}
\end{minipage}
\vspace{2mm}

\noindent
The tables are joined on the columns with equal variable names, which in this case is only \emph{?astronaut}.
If an astronaut from the left is found in the table on the right (that is, has a name in Hindi),
a row with that astronaut and name will be in the result.
If an astronaut on the left is not found in the table on the right,
we still have a row with that astronaut in the result, but the entry in the column \emph{?name} (which only exists in the right table) will be {\UNDEF}.
For readers familiar with SQL, this corresponds to the semantics of a \emph{left outer join} there.
% The result is a table with exactly 15 rows, two of which with their name in Hindi, and the rest with an {\UNDEF} name.

The second {\OPTIONAL} computes an optional join between the following two tables.
The table on the left is the result of the first optional join we just described.
The table on the right is the result of the \emph{\{ $\ldots$ \}} after the second {\OPTIONAL} from our query above.
Note that it has mere presentational reasons that the neighboring rows below pertain to the same astronaut
(the table on the right has many more rows than the table on the left, but we only show three that belong to an astronaut).

\def\ha{\hspace{10mm}}
\def\hb{\hspace{30mm}}
\vspace{2mm}
\begin{minipage}[t]{0.48\textwidth}
Canadian astronauts + Hindi name (15)
\begin{kb}
  ?astronaut  \ha\=?name                    \\[1mm]
	wd:Q16297      \> {\UNDEF}                \\
  wd:Q1687593    \> {\UNDEF}                \\
	wd:Q240769     \> "\texthindi{जूली पयेटे}"@hi  \\
	$\ldots$
\end{kb}
\end{minipage}
%
\begin{minipage}[t]{0.5\textwidth}
All entities + their Arabic name (5,900,123)
\begin{kb}
  ?astronaut \ha\=?name                             \\[1mm]
  wd:Q16297    \> {\UNDEF}                          \\
  wd:Q1687593  \> "\textarabic{\small جيريمي هانسن}"@ar  \\
	wd:Q240769   \> "\textarabic{\small جولي باييت}"@ar    \\
	$\ldots$
	% "\foreignlanguage{hindi}{जूली पयेटे}" . \\
\end{kb}
\end{minipage}
\vspace{2mm}

\noindent
These two tables have the same two column names and are hence joined on both columns.
The respective first rows match because they are the same, and that row hence appears in the result as well.
The respective second rows match because the entities in the first column match (both \emph{wd:Q1687593})
and by definition {\UNDEF} matches any value.%
\footnote{Indeed, if the table on the right would contain $k$ different rows which all have
\emph{wd:Q1687593} in the first column, they would all match the \emph{wd:Q1687593 {\UNDEF}} row from the table on the left.}
The respective third rows do not match, but the row on the left still appears in the result because it is an optional join.%
\footnote{Without the second {\OPTIONAL}, this row would only appear in the result if the Hindi and Arabic name happen to be identical.}
The result of this second optional join, which is also the final result of the query, hence contains the following three rows:

\begin{kb}
  ?astronaut \ha\=?name                             \\[1mm]
  wd:Q16297     \> {\UNDEF}                         \\
  wd:Q1687593   \> "\textarabic{\small جيريمي هانسن}"@ar \\
	wd:Q240769    \> "\texthindi{जूली पयेटे}"@hi           \\
	$\ldots$
	% "\foreignlanguage{hindi}{जूली पयेटे}" . \\
\end{kb}

\noindent
In total, the final result has 15 rows, one for each Canadian astronaut, with the Hindi name for two of them, the Arabic name for nine of them, and an {\UNDEF} name for four of them.

The query above is a typical use case for {\OPTIONAL} and easy to understand: add Hindi names, with Arabic names as backup (and we could also have English names as further backup).
In general, however, joins (optional or not) of tables with {\UNDEF} values are complicated and hard to understand,
in particular, when there are multiple join columns with {\UNDEF} values in all of them.
Note that {\OPTIONAL} is related to {\UNDEF} only in so far, that optional joins are a typical source of {\UNDEF} values,
but there are other sources as well.%
\footnote{For example, we can specify an arbitrary sequence of bindings explicity using a {\VALUES} clause.}

\subsection{Cypher (Neo4j)}\label{sec:query_languages:cypher}

Cypher is a data representation and query language for a so-called \emph{labeled property graph (LPG)},
defined in the following and often just called property graph.
Cypher was developed by Neo4j, Inc. in 2011 and was originally a proprietary language,
intended for use with the graph database Neo4j (discussed in Section \ref{sec:indexing}).
It became an open standard in 2015.

A property graph is very similar to a knowledge graph, with the following differences.
In a property graph, each node and each edge can have one or more \emph{properties}.
A property is a key-value pair, where the key is an IRI and the value is a literal.
%\TODO{We should put them in IRI-brackets \iri{ } in our examples, shouldn't we?}
Properties correspond to triples that have a literal object.
For example, the triple \emph{\iri{\merylstreep} \iri{\birthday} ``1949-06-22''} can be represented
by a property for \emph{\iri{\merylstreep}} with key \emph{\birthday} and value \emph{``1949-06-22''}.
Each node can also have zero or more labels.
Node labels correspond to triples from type-like predicates.
For example, the triple \emph{\iri{\merylstreep} \iri{\isa} \iri{Person}}
can be represented by assigning the label \emph{Person} to the node that represents Meryl Streep in the LPG.
All other triples are expressed using relationships.
Each relationship is annotated with exactly one \emph{label}
that corresponds to the name of the predicate.

\begin{figure}
\centering
\tikzstyle{vertex}=[font=\footnotesize, draw, rounded corners, minimum height=15, align=center, on grid, node distance=2 and 3]
\tikzstyle{edge}=[font=\footnotesize, above, sloped]
\resizebox{\textwidth}{!}{
\begin{tikzpicture}[>=triangle 60]
	\node[vertex](ms) {\iri{\merylstreep}};
	\node[vertex, below left =  of ms]  (fem)  {\iri{Female}};
	\node[vertex, below right=  of ms]  (per)  {\iri{Person}};
	\node[vertex, above right=  of ms]  (sn)   {\phantom{xx}\iri{$\ldots$}\phantom{xx}};
	\node[vertex, above right=  of sn]  (y)    {"1983"};
	\node[vertex, below right=  of fem] (rc)   {\iri{\carter}};
	\node[vertex, above left =  of ms]  (dob)  {"1949-06-22"};
	\node[vertex, above      =4 of ms]  (mary) {"Mary Louise Streep"};
	\node[vertex, right      =4 of sn]  (sc)   {"Sophie's Choice"};
	\node[vertex, right      =6 of rc]  (o2)   {\iri{\bestdesign}};
	\node[vertex, above      =  of o2]  (o)    {\iri{Oscar}};
	\node[vertex, below right=  of sn]   (o1)   {\iri{\bestactress}};
	% Arrows
	\draw[->] (ms) -- node[edge, below] {\iri{\wonaward}} (sn);
	\draw[->] (ms) -- node[edge] {\iri{\isa}} (per);
	\draw[->] (ms) -- node[edge, below] {\iri{\aka}} (mary);
	\draw[->] (ms) -- node[edge, pos=0.45] {\iri{\birthday}} (dob);
	\draw[->] (ms) -- node[edge] {\iri{\gender}} (fem);
	\draw[->] (sn) -- node[edge] {\iri{award}} (o1);
	\draw[->] (sn) -- node[edge] {\iri{year}} (y);
	\draw[->] (sn) -- node[edge] {\iri{film}} (sc);
	\draw[->] (rc) -- node[edge] {\iri{\gender}} (fem);
	\draw[->] (rc) -- node[edge] {\iri{\wonaward}} (o2);
	\draw[->] (rc) -- node[edge] {\iri{\isa}} (per);
	\draw[->] (o1) -- node[edge] {\iri{\isa}} (o);
	\draw[->] (o2) -- node[edge] {\iri{\isa}} (o);
	%\draw[help lines] (-3,-4) grid (6,4);
\end{tikzpicture}
}
\\
\vspace{1cm}
\def\edgelabel#1{\textbf{\MakeUppercase{#1}}}
\tikzstyle{vertex}=[font=\footnotesize, draw, rounded corners, minimum height=15, align=center]
\tikzstyle{big}=[minimum width=4.7cm, minimum height=1cm]
\resizebox{\textwidth}{!}{
\begin{tikzpicture}[>=triangle 60]
	\node[vertex, big](ms) at (0, 0) {\textbf{Person} \\ name: "Meryl Streep" \\ \aka : "Mary Louise Streep" \\ \birthday: "1949-06-02"};
	\node[vertex, big](rc) at (0, -4) {\textbf{Person} \\ name: "Ruth E. Carter"};
	\node[vertex, big](o1) at (8, 0) {\textbf{Oscar} \\ name: "Best Actress"};
	\node[vertex, big](o2) at (8, -4) {\textbf{Oscar} \\ name: "Best Costume Design"};
	\node[vertex](fem) at (0, -2) {name: "Female"};
	\draw[->] (ms) -- node[vertex, above=1mm] {\edgelabel{\wonaward} \\ year: "1983" \\ film: "Sophie's Choice"} (o1);
	\draw[->] (rc) -- node[vertex, above=1mm] {\edgelabel{\wonaward}} (o2);
	\draw[->] (ms) -- node[vertex, left=1mm]  {\edgelabel{\gender}} (fem);
	\draw[->] (rc) -- node[vertex, left=1mm]  {\edgelabel{\gender}} (fem);
\end{tikzpicture}
}
\caption{Two different representations of the knowledge graph from Section \ref{sec:basics:example_1} plus some additional triples including reification: a regular knowledge graph (top) and a property graph (bottom). With their additional features, property graphs are able to represent the same data more densely than a regular graph. However, property graphs are not more powerful with respect to the information they can represent. The empty node in the knowledge graph is a statement node (see Section \ref{sec:basics:reification}). Its IRI is omitted here; it is often a variation of the IRI of the subject.}
 %\TODO{Move the first graph to Section \ref{sec:basics:example_1} and explain it there. In this figure, only explain the property graph and the differences to a "regular" graph.}}
\label{fig:example_graph}
\end{figure}

The following lines specify a property graph
that is a slightly extended version of our toy knowledge graph from Section \ref{sec:basics:example_1}.
Figure \ref{fig:example_graph} shows the corresponding property graph and the equivalent knowledge graph.

\begin{sparql}
  ( P1: Person \= \{ \= name: ``Meryl Streep'', \\
  \>\> \aka: ``Meryl Louise Streep'', \\
  \>\> \birthday: ``1949-06-22'' \} ), \\
  ( P2: Person \> \{ name: ``Ruth E. Carter'' \}), \\
  ( O1: Oscar \> \{ name: ``Best Actress'' \} ), \\
  ( O2: Oscar \> \{ name: ``Best Costume Design'' \} ), \\
  ( F: \> \{ name: ``Female'' \}), \\
  (P1) $-$ [:\MakeUppercase{\gender}] ${-}{>}$ (F), \\
  (P2) $-$ [:\MakeUppercase{\gender}] ${-}{>}$ (F), \\
  (P1) $-$ [:\MakeUppercase{\wonaward} \{year: ``1983'', film: ``Sophie's Choice''\}] ${-}{>}$ (O1), \\
  (P2) $-$ [:\MakeUppercase{\wonaward}] ${-}{>}$ (O2)
\end{sparql}

\noindent
Note the pictorial character of the syntax.
Entities are written in parentheses, resembling a labeled node in the graph.
Relationships are written as arrows with the relationship label in square brackets, resembling a labeled box.
%Both nodes and relationships start with the (optional) variable name followed by a colon and the labels.
%%Each label is separated by a colon.
%Properties are written as comma-separated lists in curly brackets.
%\TODO{(C) Die Beschreibung finde ich verwirrend. Im Beispiel-Property-Graph haben die Zeilen 1-7 eine andere Syntax als die Zeilen 8-11. Mir ist nicht klar, ob hier beide Syntaxen erklärt werden, oder nur die Syntax der Zeilen 8-11. Insbesondere: Bezieht sich das ``Entities are written in parentheses'' auf die Syntax der Zeilen 1-7 (z.B. auf \emph{( F: \{ name: ``Female'' \})} oder auf die der Zeilen 8-11 (z.B. auf das \emph{(P1)} und \emph{(F)} in Zeile 8)?}

Property graphs can be seen as an alternative way to realize \emph{reification}, namely via properties and labels.
In knowledge graphs, reification is realized via intermediate nodes.
There is an important difference, however: one cannot specify a link between two properties or a property and a node.
For example, in Figure \ref{fig:example_graph}, we cannot link the property value \emph{Sophie's Choice}
to a node representing that film.
If needed, one could also introduce intermediate nodes in property graphs.
However, typical queries would then be processed very inefficiently.
This is explained in Section \ref{sec:indexing}, where we discuss a typical query engine for property graphs (Neo4j).
% For example, the ``film''-property of the ``{\wonaward}''-relationship should be linked to the entity of the corresponding movie.

Similar to SPARQL, Cypher contains different keywords for formulating queries.
The \emph{MATCH} keyword is used to describe the search pattern, and \emph{WHERE} is used to further filter or constrain the pattern.
These two correspond to what is written in the \emph{WHERE} clause of a SPARQL query.
Indeed, it makes no difference for the semantics of a Cypher query,
whether a constraint is specified in the \emph{MATCH} clause or in the \emph{WHERE} clause.
The \emph{RETURN} clause specifies the desired output and corresponds to the \emph{SELECT} clause of a SPARQL query.
The following example shows two equivalent Cypher queries to find all Oscar winners in $1983$ and the movies they won them for.
%
\begin{sparql}
  MATCH (x:Person) $-$ [rel:\MakeUppercase{\wonaward}] ${-}{>}$ (:Oscar) \\
  WHERE rel.year=``1983'' \\
  RETURN x.name rel.film \\[3mm]
  MATCH (x:Person) $-$ [rel:\MakeUppercase{\wonaward} \{ year: ``1983''\}] ${-}{>}$ (:Oscar) \\
  RETURN x.name rel.film
\end{sparql}
% \TODO{(C) Die eckigen Klammern in den Beispielen oben kann man schwer also solche erkennen}


\medskip\noindent
Another query language for property graphs is \emph{Gremlin}.
%It was developed by Apache TinkerPop and first appeared in 2009.
Similar to Cypher, it organizes data in nodes and directed edges and distinguishes between ``relationships'', ``properties'' and ``labels''.
However, the syntax of how to create and query a graph differs from Cypher;
see the aforementioned survey by \citet{DBLP:journals/csur/AnglesABHRV17}.
%\TODO{(C) Ich würde den Abschnitt über Gremlin weglassen, zumal wir in Section 1.1 schon schreiben, dass Gremlin in \citet{DBLP:journals/csur/AnglesABHRV17} beschrieben wird.}

\subsection{GraphQL (Facebook)}\label{sec:query_languages:graphql}
GraphQL (``Graph Query Language'') is an application query language which was developed for building and querying APIs.
However, due to its name, it is often mistaken as a query language for knowledge graphs.
GraphQL was created by Facebook in 2012 for internal use and released as an open project in 2015.
\begin{figure}[ht]
	\begin{tabularx}{\textwidth}{@{}XXXl@{}}
		type Actor \{ & type Oscar \{ & type Movie \{ & type Query \{ \\
		\hspace{3mm}id: ID! & \hspace{3mm}id: ID! & \hspace{3mm}id: ID! & \hspace{3mm}actor(id: ID!): Actor \\
		\hspace{3mm}name: String! & \hspace{3mm}category: String! & \hspace{3mm}name: String! & \} \\
		\hspace{3mm}movies: [Movie]! & \hspace{3mm}forWork: Movie! & \hspace{3mm}year: Int \\
		\hspace{3mm}oscars: [Oscar] & \hspace{3mm}year: Int & \} \\
		\} & \}
	\end{tabularx}
	\caption{An example of a GraphQL schema.
		The first three items are regular \emph{Object Types}.
		Each object type has so-called \emph{fields}, here for example ``id'' or ``name''.
		These fields specify what can appear in a part of a GraphQL query that operates on our Object Type.
		The last item is a special type that every schema needs, the \emph{Query Type}.
		It defines the \emph{entry point} of a GraphQL query (see Figure \ref{fig:graphQLQuery}).
		``ID'', ``String'' and ``Int'' are built-in \emph{scalar} types.
		An exclamation point indicates that this is a required field.
		Squared brackets represent an array.}
	\label{fig:schemaGraphQL}
\end{figure}

\begin{figure}
	\newlength{\myLength}
	\settowidth{\myLength}{ \{}
	\begin{tabular}{l@{\hspace{15mm}}l}
		\begin{tabular}[t]{l}
			query \{ \\
			\hspace{3mm} actor(id: "873") \{ \\
			\hspace{6mm} name \\
			\hspace{6mm} oscars \{ \\
			\hspace{9mm} category \\
			\hspace{9mm} year \\
			\hspace{6mm} \} \\
			\hspace{3mm} \} \\
			\} \\
		\end{tabular} &
		\begin{tabular}[t]{l}
			\{ \\
			\hspace{3mm} "data": \{ \\
			\hspace{6mm} "actor": \{ \\
			\hspace{9mm} "name": "Meryl Streep" \\
			\hspace{9mm} "oscars": [ \\
			\hspace{12mm} \{ "category": "Best Supporting Actress" \\
			\hspace{12mm}\hspace{\myLength} "year": 1980 \} \\
			\hspace{12mm} \{ "category": "Best Actress" \\
			\hspace{12mm}\hspace{\myLength} "year": 1983 \} \\
			\hspace{12mm} \{ "category": "Best Actress" \\
			\hspace{12mm}\hspace{\myLength} "year": 2012 \} \\
			\hspace{9mm} ] \\
			\hspace{6mm} \} \\
			\hspace{3mm} \} \\
			\} \\
		\end{tabular}
	\end{tabular}
	\caption{An example of a GraphQL query (left) and the response (right). Note that the schema in Figure \ref{fig:schemaGraphQL} knows what value type each field returns. For example, ``name'' returns a String, ``year'' an Int, and ``oscars'' returns an array of \emph{Oscar} objects.}
	\label{fig:graphQLQuery}
\end{figure}


GraphQL has a \emph{schema}, like a knowledge graph, but with an important difference.
In a knowledge graph, the schema is a property of the data and the syntax of a SPARQL query is independent of that schema
(and the same is true for property graphs and Cypher).
In GraphQL, the schema is defined by the user (in accordance with the underlying data),
and it determines the semantics and the structure of the queries that are allowed.
Figure \ref{fig:schemaGraphQL} provides an example.
The schema can be implemented in any language even though it is most widely used with JavaScript.
You can find a list of tools and libraries for various programming languages on GraphQL's website.%
\footnote{\url{https://graphql.org/code/}}

A GraphQL query looks like a nested JSON map, where the values are either nested JSON maps or omitted.
Using the example query in Figure \ref{fig:graphQLQuery}, we will now explain how the response is produced.
For each \emph{field} in the query (for example ``actor'' or ``name''), there has to be a function in the schema, called a \emph{resolver (function)}.
%
Most implementations provide simple default resolvers; other (more complicated) resolvers have to be implemented by the user.
Each field produces either a scalar value (like \emph{String} or \emph{Int}) or an object value (like \emph{Movie} or \emph{Oscar}).
If it produces an object value, the query has to contain a sub-selection of fields which apply to that object.
This is indicated by a new set of curly brackets in the query, for example after ``oscars''.
Each query starts with a Query type field or \emph{entry point} (here: ``actor'').
Usually, the corresponding resolver function accesses a database and constructs objects from it.
For example, the resolver function \emph{actor(id: ID!)} finds the actor with the correct ID in the database and returns an \emph{Actor} object.
This object is then passed to the resolver function(s) of the next field(s) (here: ``name'' and ``oscars'').
This continues until scalar values are reached.
The answer is a JSON in the same format as the query with the values filled out with the scalar values returned by the resolver functions.
%Some resolvers need an argument, e.g. ``actor'' needs an ID.
%When the query is being executed, these resolvers are called to produce the result.



%The GraphQL foundation also provides \emph{GraphiQL}, a graphical interactive in-browser GraphQL IDE for editing and testing queries.
%GraphiQL offers syntax highlighting, autocompletion, a documentation explorer, query history and other features. \TODO{C: Is this relevant? T: I wasn't sure and I thought about deleting it. I think it's very useful, if somebody wants to try out GraphQL, but certainly not relevant to the section.}

Despite the name, GraphQL's purpose and scope is quite different from query languages like SPARQL or Cypher.
First, due to the application-specific schema and the lack of global IRIs, GraphQL is not intended to combine data from different sources.
Second, typical GraphQL queries are less expressive.
In particular, only tree queries are possible and functions like filtering, sorting and grouping are not supported by default.
In principle, users can implement any additional feature using a suitable resolver function.

%In summary, GraphQL is light-weight compared to query languages like SPARQL.
%However, it is more expressive than previous APIs.
%In our example, previous APIs would typically fetch the entire \emph{Actor} object containing lots of information we do not need.
%The object would contain IDs of the oscars.
%Using these IDs, the API would query another backend to get the \emph{Oscar} objects (again, with lots of additional information not used), which are then used to obtain the category and year.
%GraphQL thus minimizes the amount of data transferred, which is particularly useful for mobile apps and websites.
%Moreover, GraphQL's nested fields allow clients to ask for multiple resources in one request.


\section{Engines and indexing} \label{sec:indexing}

% \TODO{Brief overview of SOTA engines: Virtuoso, Blazegraph, Amazon Neptune, Neo4J, RDF-3X, QLever and maybe: Apache Marmotta, Jena, Rdf4J (formerly known as Sesame), Rasqal, AllegroGraph, 4store, GraphDB, Stardog, } \\
% \TODO{Mention NoSQL databases and their relation to true triple stores -> not the focus here} \\
% \TODO{Maybe also briefly mention XML databases and their relation -> not the focus an no longer used} \\
% \TODO{Performance comparison wrt: indexing- and query times, querying capabilities, focus on SPARQL} \\
% \TODO{The importance of keeping IDs and names (possibly in many languages) separate} \\
% \TODO{Explain basic permutation idea (like in the KB summer school slides)} \\
% \TODO{Explain the importance of multiplicities (dito)} \\
% \TODO{Explain the importance of join ordernung (dito)} \\
% \TODO{Refer to QLever code and make examples reproducible in QLever} \\

Knowledge graphs contain up to tens of billions of triples (Section \ref{sec:examples} gave several examples),
and they continue to grow.
In this section, we explain how data of such scale can be processed and queried efficiently.
We focus on three techniques: representation via monotonic \emph{object identifiers},
indexing via \emph{triple permutations}, and query planning via \emph{cost estimation}.
Several SPARQL engines have been built based on these core ideas, in particular the QLever SPARQL engine
(\url{https://qlever.cs.uni-freiburg.de}),
which provides the SPARQL endpoints for the knowledge graphs discussed in Section \ref{sec:examples}.
% We also briefly comment on several implementation challenges involved in building a practical SPARQL engine.
We also discuss three other popular SPARQL engines (\emph{Virtuoso}, \emph{Blazegraph}, and \emph{Neo4j})
and their respective strengths and weaknesses.
%\TODO{We should maybe clarify that these three engines support the full SPARQL standard, but QLever does not}.
\citet{OTHER:AliSYHN21} provide a much broader overview of techniques
and list more than a hundred SPARQL engines together with their feature sets.
However, in that survey each particular technique is described only briefly and rather formally,
whereas our explanations here are more elaborate and also suitable for newcomers to the field.
% including a comparison of their feature sets.

%\subsection{QLever}
%
%QLever \cite{DBLP:conf/cikm/BastB17} is an open-source SPARQL query engine from the University of Freiburg written in C++.
%The source code of QLever is available under \url{https://github.com/ad-freiburg/qlever}.
%% It can handle even very large knowledge graphs with tens of billions of triples on a standard PC or server.
%% For example, QLever can index the complete Wikidata (\TODO{18} billion triples) in less than 24 hours and execute typical SPARQL queries in less than a second, using no more than 40 GB of memory.
%% QLever provides SPARQL endpoints for many prominent knowledge graphs (e.g., Wikidata, Freebase, DBpedia, etc.) which are publicly accessible at \url{https://qlever.cs.uni-freiburg.de/}.
%In the following, we give insights into the techniques behind QLever, with a focus on indexing and query planning (which is particularly important for executing complex queries).
%At the end, we will list some further implementation details which are out of scope for this survey but nevertheless critical for the performance of the system.

\def\oid{\mathrm{oid}}
\def\OID{\mathrm{OID}}
\subsection{Object identifiers}\label{sec:object-identifiers}
%
Call the set of distinct IRIs and literals of a knowledge graph its \emph{vocabulary}.
Many query engines work with \emph{object identifiers (OIDs)}, which map each IRI or literal from the vocabulary to a unique integer ID.
Each $\OID$ is stored in a fixed number of bytes, typically either 6 bytes (enough for 281 trillion $\OID$s)
or 8 bytes (corresponding to a \emph{word} on a 64-bit machine).
The input data is then stored using OIDs, and for a given SPARQL query, the (relatively few) IRIs and literals are also mapped to OIDs.
Most of the query processing can then be carried out efficiently with tables of fixed-size integers, instead of with tables of strings.
To produce the final result, the OIDs are mapped back to the corresponding strings.

\smallskip\noindent
To illustrate this, consider the following toy knowledge graph and the subsequent mapping of its IRIs and literals to OIDs:

\def\armstrong{Neil\u Armstrong}
\def\yang{Liu\u Yang}
\def\dob{Date\u of\u birth}
\begin{kb}
  \iri{\armstrong} \quad \= \iri{Profession} \qquad \= \iri{Astronaut} \\
  \iri{\armstrong}       \> \iri{Nationality}       \> \iri{USA} \\
  \iri{\armstrong}       \> \iri{\dob}              \> ``1930-08-05'' \\
  \iri{\yang}            \> \iri{Profession}        \> \iri{Astronaut} \\
  \iri{\yang}            \> \iri{Nationality}       \> \iri{China}
\end{kb}
\vspace{-6mm}

\begin{kb}
  \iri{Astronaut} \hspace{6mm} \= \#0 \hspace{9mm} \= \iri{\yang} \hspace{9mm} \= \#3 \hspace{9mm} \= \iri{Profession} \hspace{7mm} \= \#6 \\
  \iri{China}                  \> \#1              \> \iri{Nationality}        \> \#4              \> \iri{USA}                     \> \#7 \\
  $<$\dob$>$                   \> \#2              \> \iri{\armstrong}         \> \#5              \> ``1930-08-05''                \> \#8
\end{kb}

\noindent
These $\OID$s have an additional important property, namely, that they are \emph{monotonic}.
Informally, this means that the ``natural'' order of the IRIs and literals is preserved.
Formally, there must be a total and easy-to-compute order $<_{\OID}$ on the $\OID$s,
such that for arbitrary strings $s_1, s_2$ from the vocabulary,
it holds that $\oid(s_1) <_\OID \oid(s_2)$ if and only if $s_1 < s_2$,
where $<$ is the order of IRIs and literals as defined by the SPARQL standard.
In the example above, $<_\OID$ is simply the natural integer order of the $\OID$s.%
\footnote{\href{https://www.w3.org/TR/sparql11-query/\#solutionModifiers}{Section 15.1 of the SPARQL standard}
does not define a total order on all possible RDF terms.
However, it does specify that IRIs come before literals, hence \emph{``1930-08-05''}
correctly gets the largest $\OID$ in the example.}

%For example, $\iri{Astronaut}\:<\:\iri{\armstrong}$ and indeed
%$\oid{\iri{Astronaut}}\:=\:\#0\:<_\OID = \#5 = \oid{\iri{\armstrong}}$.
%The natural order of the IRIs is lexicographic. For example, the OID of \emph{\iri{Astronaut}} is smaller than the OID of \emph{\iri{China}}.
%The natural order of non-string literals, called \emph{values}, is the order of the values represented by the literals.
%For example, \emph{``10''\^{}\^{}xsd:int} is larger than \emph{``9''\^{}\^{}xsd:int},
%although lexicographically \emph{``10''} is smaller than \emph{``9''}.

Monotonic OIDs allow a particularly efficient implementation of operations
that need to consider the order of IRIs and literals according to the SPARQL standard.
This includes: {\ORDERBY} (sorting the result using one or several variables as sort key),
{\FILTER} with relational expressions like $\le$ or $\ge$,
and {\REGEX} expressions that check whether a given entity or literal starts with a given prefix.
It should be noted that {\ORDERBY} clauses are very frequent in SPARQL queries,
and as we will see in Section \ref{sec:autocompletion},
an efficient processing of prefix {\REGEX} expressions is crucial for efficient autocompletion for SPARQL queries.

Using monotonic OIDs, these operations can be computed using only the $\OID$s,
which is much cheaper than working with the underlying IRIs or literals, provided that $<_\OID$ is easy to compute.
This is trivial for the example above, where $<_\OID$ is just the normal integer order,
but in practice, matters are a bit more complicated.
For example, QLever encodes integers, floating point numbers and dates directly in its 8-byte $\OID$s,
using $4$ bits to specify the datatype and $60$ bits for the actual value.
It then looks like already the trivial integer order on such $\OID$s fulfills the monotonicity property, but that is not true.
For example, when encoding (signed) integers in the standard way using two's complement,
the negative numbers come \emph{after} the positive numbers in the trivial $\OID$ order.
For floating point numbers and dates, the situation is even more complicated.
Still, with clever bit fiddling, it is possible to implement a $<_\OID$ order
that can be computed very efficiently and has the monotonicity property.

When the knowledge graph is static and given in advance, monotonic $\OID$s are straightforward to compute.
When the knowledge graph is updated, or when new entities or literals are introduced as part of a query,%
\footnote{For example, this can happen when using {\VALUES} or {\SERVICE}; see Section \ref{sec:federated}.}
maintaining monotonic IDs becomes more challenging.
% The approach of monotonic OIDs can be generalized to also work in this scenario, but this is out of scope for this chapter.
Of the four SPARQL engines discussed in detail below, only QLever implements monotonic OIDs,
while Virtuoso, Blazegraph, and Neo4j do not.

%Another typical optimization for storing the vocabulary is to directly encode small values like integers, floating point numbers, and short literals in the OID, together with their datatype. For example, QLever uses 8-byte OIDs that consist of 4 bits that specify the type (IRI, integer, floating point number, etc.) and 60 bits that encode the actual value or OID. Note that it is possible, but not trivial to also make these directly encoding OIDs monotonic. Assume for example that integers are encoded using 4 leading zero bits to encode the datatype and then 60 bits to encode a two's complement integer. Then all the positive integer OIDs start with $00000$ and all the negative integer OIDs start with $00001$. When using a trivial bitwise comparison for the OIDs as the $compare_{OID}$ function, the negative integers would be considered larger than the positive integers, which violates the monotonicity. QLever therefore uses two different comparison functions for OIDs. When the monotonicity is not important, the very cheap bitwise comparison is used. This happens for examples in join operations, see the following section. When the monotonicity is important, a more complex comparison is used that takes the datatypes of the OIDs into account. This is more expensive than the simple comparison, but still orders of magnitude cheaper than looking up the corresponding strings from the vocabulary and comparing them.


%\noindent There are many ways to map numerical values are mapped to an intermediate mantissa-exponent representation, to bring them in the correct order and to assign them the respective IDs, for example:
%
%\begin{kb}
  %Value \hspace{30mm} \= Intermediate representation \qquad \= ID \\[5pt]
  %``3.14159''@xsd:double   \> ``00E3.14159000''                  \> \#9 \\
  %``42''@xsd:integer       \> ``01E4.20000000''                  \> \#10 \\
  %``1000000''@xsd:integer  \> ``06E1.00000000''                  \> \#11
%\end{kb}

%\noindent The IDs are later used to, for example, implement the \emph{ORDER BY} clause of SPARQL more efficiently (i.e., by sorting integers instead of strings).
%Note that the IDs are specific to the indexing and do not relate to any identifiers used by the knowledge graphs (e.g., \emph{Q30} for \emph{\iri{USA}} in Wikidata).
%The mapping from each ID to its token is stored in one large array, with the token assigned to ID $i$ being stored at position $i$.

\subsection{Triple permutations}\label{sec:triple-permutations}

A key idea used in most high-performance SPARQL engines is to store the set of given triples multiple times,
but in different permutations. The six possible permutations are \emph{SPO}, \emph{SOP}, \emph{PSO}, \emph{OSP}, \emph{POS}, and \emph{OPS},
where \emph{S} stands for subject, \emph{P} stands for predicate, and \emph{O} stands for object.
For example, the \emph{SPO} index and \emph{PSO} index relating to the knowledge graph from Section \ref{sec:object-identifiers} stores the triples as follows:

\noindent\begin{minipage}[t]{0.5\textwidth}
  \begin{kb}
    SPO index \\[5pt]
    S=\#3 \quad \= P=\#4 \quad \= O=\#1 \\
    S=\#3       \> P=\#6       \> O=\#0 \\
    S=\#5       \> P=\#2       \> O=\#8 \\
    S=\#5       \> P=\#4       \> O=\#7 \\
    S=\#5       \> P=\#6       \> O=\#0 \\
  \end{kb}
\end{minipage}
\hspace{15mm}
\begin{minipage}[t]{0.5\textwidth}
  \begin{kb}
    PSO index \\[5pt]
    P=\#2 \quad \= S=\#5 \quad \= O=\#8 \\
    P=\#4       \> S=\#3       \> O=\#1 \\
    P=\#4       \> S=\#5       \> O=\#7 \\
    P=\#6       \> S=\#3       \> O=\#0 \\
    P=\#6       \> S=\#5       \> O=\#0 \\
  \end{kb}
\end{minipage}
\vspace{-3mm}

\noindent In the \emph{SPO} index, the triples are sorted by subject, then predicate, then object.
In the \emph{PSO} index, the triples are sorted by predicate, then subject, then object.
Note that in the examples above (and also in the following examples), the IDs are prefixed by ``\#'' and ``\emph{S=}'', ``\emph{P=}'' or ``\emph{O=}'', depending on their position in a triple.
This is just for the sake of explanation; in reality, only the integer IDs are stored.
In fact, the first column is not stored explicitly, because it consists of long sequences of the same ID.
Instead, we store only the second and third column (row-wise),
and have a separate map that for each ID of the first column,
stores the index of the first row pertaining to that ID.
For the $SPO$ index above, the map for $S$ would be $\{3: 0; \; 5: 2\}$,
and the table would be $[(4, 1), (6, 0), (2, 8), (4, 7), (6, 0)]$.

To understand how these indexes can be used for efficient query processing, consider the following SPARQL query:

\begin{sparql}
{\SELECT} ?person ?nationality {\WHERE} \{ \\
\;\; ?person \iri{Nationality} ?nationality . \\
\} {\ORDERBY} ?person
\end{sparql}

\noindent To get all matches for the triple in the \emph{\WHERE} clause, we could use either the \emph{PSO} or the \emph{POS} index.
In both of them, the matches for \emph{?person ?nationality} form a contiguous segment, marked blue in the following example (recall from the OID table in Section \ref{sec:object-identifiers} that $\#4$ stands for \emph{\iri{Nationality}}).
Since the SPARQL query asks for the results ordered by \emph{?person}, we take the \emph{PSO} index,
because in it the matching rows are already ordered by \emph{S}, which stands for \emph{?person} in this case. Note that this only works when using monotonic OIDs, otherwise we would still have to sort the result afterwards. Retrieving a segment from one of the precomputed indexes is called a \emph{SCAN} operation.

%The triples in blue correspond to the triples with predicate \emph{\iri{Nationality}} (or ID \#4).
%Because these triples are stored in a continuous range in the \emph{PSO} index, they can be read efficiently by one so called \emph{SCAN} operation.
%The result is a table with two columns, where the subjects of the respective triples form the first column and the objects the second column.


\noindent
\begin{minipage}[t]{0.5\textwidth}
\begin{kb}
  PSO index \\[5pt]
  P=\#2 \;                             \= S=\#5 \;                          \= O=\#8 \\
  \textcolor{darkblue}{\textbf{P=\#4}} \> \textcolor{darkblue}{\textbf{S=\#3}} \> \textcolor{darkblue}{\textbf{O=\#1}} \\
  \textcolor{darkblue}{\textbf{P=\#4}} \> \textcolor{darkblue}{\textbf{S=\#5}} \> \textcolor{darkblue}{\textbf{O=\#7}} \\
  P=\#6                                \> S=\#3                                \> O=\#0 \\
  P=\#6                                \> S=\#5                                \> O=\#0 \\
\end{kb}
\end{minipage}
\hspace{7mm}
\begin{minipage}[t]{20em}
  \begin{kb}
    Result Table with OIDs \\[3pt]
    \#3 \quad \= \#1 \\
    \#5       \> \#7 \\
  \end{kb}
\end{minipage}
\hspace{7mm}
\begin{minipage}[t]{20em}
  \begin{kb}
    Result Table with IRIs \\[3pt]
    \iri{\yang} \hspace{12mm} \= \iri{China} \\
    \iri{\armstrong}         \> \iri{USA} \\
  \end{kb}
\end{minipage}
\vspace{-3mm}

\noindent Things get more interesting when SPARQL queries contain two or more triples.
For an illustration, consider the following SPARQL query:
\begin{sparql}
  {\SELECT} ?person ?nationality ?profession {\WHERE} \{ \\
  \;\; ?person \iri{Nationality} ?nationality . \hspace{10mm}\= \textcolor{darkblue}{\textbf T$\mathbf{_1}$}\\
  \;\; ?person \iri{Profession} ?profession .                \> \textcolor{darkgreen}{\textbf T$\mathbf{_2}$}\\
  \}
\end{sparql}

\noindent For each individual triple, the result is a table with two columns:
\emph{?person ?nationality} for $T_1$ and \emph{?person ?profession} for $T_2$.
Just like for the previous query, each of these tables can be obtained with a
SCAN operation on either the \emph{PSO} index or the \emph{POS} index.
Since the two triples have the same subject variable \emph{?person},
we need to join these two tables on their respective first columns.
We therefore perform the SCAN on the \emph{PSO} index,
so that both columns are already sorted by their respective join columns,
and we can perform an efficient linear-time merge JOIN. This works with any order of the OIDs, in particular also for non-monotonic OIDs.
%In this query, the query pattern $P_1$ corresponds to the set of triples with predicate \emph{\iri{Nationality}} (or ID \#4) and the query pattern $P_2$ to the set of triples with predicate \emph{\iri{Profession}} (or ID \#6).
%Both query pattern share the variable \emph{?person} as the subject, so the two triple sets relating to $P_1$ and $P_2$ need to be joined on \emph{?person} to get the query result.
%In general, \emph{JOIN} operations are faster if the respective join columns are sorted.
%For that reason, QLever uses the \emph{PSO} index to answer the above query, because this index provides the set of triples corresponding to $P_1$ and $P_2$ already ordered by subjects.
Here is an illustration, where the triples in blue correspond to $T_1$ and the triples in green to $T_2$.
%Because both sets of triples are already sorted by subjects, they can be efficiently joined on the subject column.
%The result table consists of three columns, where the mutual subjects form the first column, the objects of the blue triples the second column, and the objects of the green triples the third column.

\noindent\begin{minipage}[t]{0.5\textwidth}
  \begin{kb}
    PSO index \\[5pt]
    P=\#2 \;                          \= S=\#5 \;                          \= O=\#8 \\
    \textcolor{darkblue}{\textbf{P=\#4}} \> \textcolor{darkblue}{\textbf{S=\#3}} \> \textcolor{darkblue}{\textbf{O=\#1}} \\
    \textcolor{darkblue}{\textbf{P=\#4}} \> \textcolor{darkblue}{\textbf{S=\#5}} \> \textcolor{darkblue}{\textbf{O=\#7}} \\
    \textcolor{darkgreen}{\textbf{P=\#6}}  \> \textcolor{darkgreen}{\textbf{S=\#3}}  \> \textcolor{darkgreen}{\textbf{O=\#0}} \\
    \textcolor{darkgreen}{\textbf{P=\#6}}  \> \textcolor{darkgreen}{\textbf{S=\#5}}  \> \textcolor{darkgreen}{\textbf{O=\#0}} \\
  \end{kb}
\end{minipage}
\hspace{7mm}
\begin{minipage}[t]{20em}
    \begin{kb}
      Result Table \\[5pt]
      \#3 \; \= \#1 \; \= \#0 \\
      \#5    \> \#7    \> \#0 \\
    \end{kb}
\end{minipage}
\hspace{7mm}
\begin{minipage}[t]{20em}
    \begin{kb}
      Result Table with IRIs \\[5pt]
      \iri{Liu Yang} \hspace{8mm} \= \iri{China} \hspace{1mm} \= \iri{Astronaut} \\
      \iri{Neil Armstrong} \> \iri{USA} \> \iri{Astronaut} \\
    \end{kb}
\end{minipage}
\vspace{-5mm}

\subsection{Query planning}\label{sec:query-planning}

In the examples above, we picked the index such that the necessary JOIN operations could be carried out as efficiently as possible.
In complex SPARQL queries, there are many such choices to be made,
not only the choice of index for each SCAN operation, but also the order of the JOIN operations.
Consider the following SPARQL query,
which asks for all married couples in the knowledge graph who were born on the same date.

\begin{sparql}
  {\SELECT} ?person\u 1 ?person\u 2 ?birth\u date {\WHERE} \{ \\
  \;\; ?person\u 1 \iri{\dob} ?birth\u date . \hspace{10mm}\= \textcolor{blue}{T$_1$} \\
  \;\; ?person\u 2 \iri{\dob} ?birth\u date .              \> \textcolor{blue}{T$_2$} \\
  \;\; ?person\u 1 \iri{Spouse} ?person\u 2 .              \> \textcolor{blue}{T$_3$} \\
  \}
\end{sparql}

\noindent
Let us look at two possible query plans to compute the result of this query.
We assume that we always \emph{materialize} (fully compute) the intermediate result tables.%
\footnote{This can be avoided in special cases, for example when a SPARQL query has a \emph{LIMIT k} clause,
and $k$ rows of the result can be obtained without exploring all matches for the various parts of the query.}
The first query plan is as follows.

\begin{enumerate}[label=(\arabic*),topsep=0pt,itemsep=-3pt,leftmargin=20pt]
\item Scan the \emph{POS} index for the sets of triples relating to $T_1$ and $T_2$ (in any order).
\item Join both sets of triples on \emph{?birth\u date}.
\item Sort the result from step 2 by \emph{?person\u 1} and \emph{?person\u 2}.
\item Scan the \emph{PSO} index for the set of triples relating to $T_3$.
\item Join the results from steps 3 and 4 on two columns: \emph{?person\u 1} and \emph{?person\u 2}.
\end{enumerate}

\noindent This query plan is expensive, because the intermediate result from the JOIN operation in step 2 is huge
and therefore expensive to compute (if we have $n$ different days, and $k$ people are born on each of these,
the result has $n \cdot k^2$ rows).
%
Here is an alternative query plan:

\begin{enumerate}[label=(\arabic*),topsep=0pt,itemsep=-3pt,leftmargin=20pt]
\item Scan the \emph{PSO} index for the sets of triples relating to $T_1$ and $T_3$ (in any order).
\item Join both sets of triples on \emph{?person\u 1}.
\item Sort the result from step 2 by \emph{?person\u 2} and \emph{?birth\u date}.
\item Scan the \emph{PSO} index for the set of triples relating to $T_2$.
\item Join the results from steps 3 and 4 on two columns: \emph{?person\u 2} and \emph{?birth\u date}.
\end{enumerate}

\noindent This query plan is cheaper because any fixed person has only a single date of birth and only few spouses (if any),
and thus the result from step 2 is much smaller than for the first query plan.

But how to determine the cheapest query plan, without executing all possible query plans in advance?
The typical approach is to \emph{estimate} the cost of some or all query plans.%
\footnote{The standard approach is via dynamic programming, which we do not described in detail here.
That way, we can discard a subset of the query plans before we have fully estimated their cost,
in case the estimate for a partial plan is already more expensive
than the estimate for a full plan we have already found.}
In the following, we describe an approach that estimates the following statistics for each intermediate result table:

\begin{enumerate}[label=(\arabic*),topsep=0pt,itemsep=-3pt,leftmargin=20pt]
\item The size $s$ of the table, that is, the number of rows.
\item For each column $i$, the number $d_i$ of distinct elements in that column.
\item For each column $i$, the average multiplicity $m_i$ of an element in that column.
\end{enumerate}

\noindent Trivially, $d_i \cdot m_i = s$ for each column $i$, so that one of these three quantities is redundant.
It's still good to have all three defined because it makes the following formulas easier to understand.

The basic operations of each query plan are the index SCANs.
We assume that we have the exact values of $s$, $d_i$, and $m_i$ for the results of these SCANs
(they can be easily precomputed during the indexing).
We next describe how we estimate these values for the results of a JOIN operation,
given the estimates for the input tables.
Note that for full SPARQL support, there are also many other kinds of operations for which we would need such estimates,
like sorting a table by a particular column or filtering a table by a particular criterion. We omit them here for brevity.

\input{formulas}

\begin{comment}
Let $T'$ and $T''$ be the two input tables, and let $s'$ and $s''$ be their sizes,
and let $d'$, $d''$, $m'$, and $m''$ be the distinctness and multiplicity
of their respective join columns.

Then we can estimate the size of the result table as follows,
where $\alpha$ is a correction factor in the range $[0,1]$ explained below
%\begin{equation} \label{eqn:join_cost}
$$s = \alpha \cdot m' \cdot m'' \cdot \min(d', \; d'') \: .$$ %\tag{$*$}
%\end{equation}
Let us explain the intuition behind this formula by the examples of two border cases. % (\ref{eqn:join_cost})

\para{Case 1} Assume that the join columns of $T'$ and $T''$ do not contain duplicate values,
that is: $s' = d'$, $s'' = d''$ and $m' = m'' = 1$.
When all values of the join column in the smaller table occur in the join column of the larger table,
the size of the result table $T$ is equal to the size of the smaller table,
that is, $s = \min(d', d'')$, which matches the formula with $\alpha = 1$.

%Figure \ref{fig:join-scenario-1} provides an illustration of this case.
%This case is reflected by (\ref{eqn:join_cost}), as $\alpha \cdot m_1\cdot m_2\cdot \min(d_1, d_2) = \alpha \cdot 1 \cdot 1 \cdot \min(s_1, s_2) = \alpha \cdot \min(s_1, s_2)$.


%\begin{figure}[!t]
  %\centering
  %{
    %\itshape
\newcommand{\eqal}{\hspace{-2pt}=}
\vspace{3mm}
    \begin{tabular}{p{75pt}p{75pt}p{75pt}}
      \begin{tabular}[t]{ll}
        \multicolumn{2}{c}{$T'$ \; \footnotesize{$s' = 3$}} \\[5pt]
        \textcolor{darkblue}{\textbf{\#14}} & \#15 \\
        \textcolor{darkblue}{\textbf{\#38}} & \#42 \\
        \textcolor{darkblue}{\textbf{\#57}} & \#13 \\ \hline
        \scriptsize{$d'_1\eqal3$}           & \scriptsize{$d'_2\eqal3$} \\[-2pt]
        \scriptsize{$m'_1\eqal1$}           & \scriptsize{$m'_2\eqal1$} \\
      \end{tabular}
      &
      \begin{tabular}[t]{ll}
        \multicolumn{2}{c}{$T''$ \; \footnotesize{$s'' = 2$}} \\[5pt]
        \textcolor{darkblue}{\textbf{\#14}} & \#97 \\
        \textcolor{darkblue}{\textbf{\#57}} & \#55 \\ \hline
        \scriptsize{$d''_1\eqal2$}          & \scriptsize{$d''_2\eqal2$} \\[-2pt]
        \scriptsize{$m''_1\eqal1$}          & \scriptsize{$m''_2\eqal1$} \\
      \end{tabular}
      &
      \begin{tabular}[t]{lll}
        \multicolumn{3}{c}{$T$ \; \footnotesize{$s = 2$}} \\[5pt]
        \textbf{\#14}            & \#15                     & \#97 \\
        \textbf{\#57}            & \#13                     & \#55 \\ \hline
        \scriptsize{$d_1\eqal2$} & \scriptsize{$d_2\eqal2$} & \scriptsize{$d_3\eqal2$} \\[-2pt]
        \scriptsize{$m_1\eqal1$} & \scriptsize{$m_2\eqal1$} & \scriptsize{$m_3\eqal1$} \\
      \end{tabular}
    \end{tabular}
  \vspace{3mm}
  %}
  %\vspace{5pt}
  %\caption{An example of joining two tables. The blue columns are the join columns.
  %%The $d_i^j$ values below the columns specify the number of distinct IDs in the $j$-th column of $T_i$.
  %%Likewise, the $m_i^j$ values specify the multiplicities of the columns.
  %Because all IDs in the join column of the smaller input table ($T''$)
	%also occur in the join column of the larger input table ($T'$),
	%the number of rows in the result table $T$ is $s = s'' = 2$.}
  %\label{fig:join-scenario-1}
%\end{figure}

\para{Case 2}
Assume that each value in the join column of $T'$ has multiplicity $m'$
and each value in the join column of $T''$ has multiplicity $m''$.
Then, the number of rows in $T$ for each value contained in both tables in the join column is $m' \cdot m''$.
In the following example, $d' = d'' = 1$, in which case the number of rows in $T$ is $s = m' \cdot m''$,
which again matches our formula with $\alpha = 1$.
%In particular, when all values in the join column of $T_1$ and all values in the join column of $T_2$ are equal (that is: $m_1=s_1$ and $m_2=s_2$ and $d_1 = d_2 = 1$) \TODO{This doesn't specifically say that this value must be the same value for $T_1$ and $T_2$, does it?}, the size of $T$ is $s = m_1 \cdot m_2 = s_1 \cdot s_2$.
%Figure \ref{fig:join-scenario-2} provides an illustration of this case.
%This case is reflected by (\ref{eqn:join_cost}), as $\alpha \cdot m_1\cdot m_2\cdot \min(d_1, d_2) = \alpha \cdot m_1 \cdot m_2 \cdot \min(1, 1) = \alpha \cdot m_1 \cdot m_2$.

%\begin{figure}[!t]
  %\centering
  %\newcommand{\eqal}{\hspace{-2pt}=}
  %{
    %\itshape
		\vspace{3mm}
    \begin{tabular}{p{75pt}p{75pt}p{75pt}}
      \begin{tabular}[t]{ll}
        \multicolumn{2}{c}{$T'$ \; \footnotesize{$s' = 3$}} \\[5pt]
        \textcolor{darkblue}{\textbf{\#57}} & \#15 \\
        \textcolor{darkblue}{\textbf{\#57}} & \#42 \\
        \textcolor{darkblue}{\textbf{\#57}} & \#13 \\ \hline
        \scriptsize{$d'_1\eqal1$}          & \scriptsize{$d'_2\eqal3$} \\[-2pt]
        \scriptsize{$m'_1\eqal3$}          & \scriptsize{$m'_2\eqal1$} \\
      \end{tabular}
      &
      \begin{tabular}[t]{ll}
        \multicolumn{2}{c}{$T''$ \; \footnotesize{$s'' = 2$}} \\[5pt]
        \textcolor{darkblue}{\textbf{\#57}} & \#97 \\
        \textcolor{darkblue}{\textbf{\#57}} & \#55 \\ \hline
        \scriptsize{$d''_1\eqal1$}          & \scriptsize{$d''_2\eqal2$} \\[-2pt]
        \scriptsize{$m''_1\eqal2$}          & \scriptsize{$m''_2\eqal1$} \\
      \end{tabular}
      &
      \begin{tabular}[t]{lll}
        \multicolumn{3}{c}{$T$ \; \footnotesize{$s = 6$}} \\[5pt]
        \textbf{\#57}            & \#15                     & \#97 \\
        \textbf{\#57}            & \#15                     & \#55 \\
        \textbf{\#57}            & \#42                     & \#97 \\
        \textbf{\#57}            & \#42                     & \#55 \\
        \textbf{\#57}            & \#13                     & \#97 \\
        \textbf{\#57}            & \#13                     & \#55 \\ \hline
        \scriptsize{$d_1\eqal1$} & \scriptsize{$d_2\eqal3$} & \scriptsize{$d_3\eqal2$} \\[-2pt]
        \scriptsize{$m_1\eqal6$} & \scriptsize{$m_2\eqal2$} & \scriptsize{$m_3\eqal3$} \\
      \end{tabular}
    \end{tabular}
  \vspace{3mm}
  %}
  %\vspace{5pt}
  %\caption{Another example of joining two tables.
  %Like in Figure \ref{fig:join-scenario-1}, the blue columns are the join columns, the $d_i^j$ specify the number of distinct IDs in the columns and $m_i^j$ the multiplicities.
  %Because all IDs in the join columns are equal, the number of rows in the result table $T$ is $s=s_1 \cdot s_2 = 3 \cdot 2 = 6$.}
  %\label{fig:join-scenario-2}
%\end{figure}

\noindent In both cases, the result table might be smaller when the join column of the smaller table contains values that do not occur in the larger table.
This is reflected by the tuning constant $\alpha$.
QLever uses $\alpha = 0.7$.

% where QLever uses $\alpha=0.7$.

Since $T$ itself can be the input to another JOIN operation on any column,
we also need to estimate the distinctness $d_j$ and multiplicity $m_j$ for each column $j$ (not just of the join column).
Again assume, without loss of generality that the join column is the first column in both tables and in the result table.
For a fixed column $j > 1$ of $T$,
let $T'$ be the table from which the column originated and let $T''$ be the other table,
and let $d'_j$, $d''_j$, $m'$, and $m''$ be accordingly.
%Let $d_{orig}^{join}$ be the number of distinct elements in the join column of $T_{orig}$,
%and $d_{other}^{join}$ the number of distinct elements in the join column of $T_{other}$,
%and $d_{orig}^j$ be the number of distinct elements in the column of $T_{orig}$
%from which column $j$ in $T$ originated.
Then we estimate the distinctness in column $j$ of the result table as
$$d_j = \min(d'_j, \; \alpha \cdot m'_1 \cdot \min(d'_1, \; d''_1))\:.$$
Let us also understand the intuition behind this formula.
First, $d_j$ cannot be larger than the distinctness $d'_j$ of the original column,
because only two things can happen when column $j$ from $T'$ gets copied to $T$:
values get lost (because not all values in the join column of $T'$ may be contained in the join column of $T''$)
and values get duplicated (because of the ``cross-product effect'', like in the second example above).
This is the first term in the formula above.
Second, we can estimate the number of distinct elements from the join column of $T'$
that make it to $T$ as $\alpha \cdot \min(d'_1, \; d''_1)$, just like for our first formula above.
Each of these can ``bring'' at most $m'_1$ distinct values from column $j$, on average.
This is the second term in the formula above.
To estimate the distinctness $d_1$ of the join column in $T$, we can just drop the $m'_1$.

%To illustrate this, consider the second column of $T$ in the second example above. %in Figure \ref{fig:join-scenario-2}.
%This column originated from the second column of $T_2$.
%Thus, $T_{orig} = T_2$, $T_{other} = T_1$, $s_{orig} = s_2 = 2$, $d_{orig}^{join} = d_2^1 = 1$, $d_{other}^{join} = d_1^1= 1$, and $d_{orig}^j = d_2^2=2$.
%Consequently, $s'_{orig} = 2 \cdot \alpha \cdot \min(1, 1) / 1 = 2\cdot \alpha$ and $d^j = min(2, 2 \cdot \alpha) = 2 \cdot \alpha$.

%This column originated from the second column of $T_2$.
%Thus, $T_{orig} = T_2$, $T_{other} = T_1$, $s_{orig} = s_2 = 2$, $d_{orig}^{join} = d_2^1 = 1$, $d_{other}^{join} = d_1^1= 1$, and $d_{orig}^j = d_2^2=2$.
%Consequently, $s'_{orig} = 2 \cdot \alpha \cdot \min(1, 1) / 1 = 2\cdot \alpha$ and $d^j = min(2, 2 \cdot \alpha) = 2 \cdot \alpha$.
\end{comment}

\subsection{Further improvements}\label{sec:improvements}

We have described three key techniques: object IDs, triple permutations, and cost estimation for query planning.
These three already form a solid basis for building a high-performance SPARQL engine,
but there are still a lot of challenges to address.
Here is an incomplete list:

\begin{enumerate}[label=(\arabic*),topsep=0pt,itemsep=-3pt,leftmargin=20pt]
\item Monotonic object identifiers for dynamic knowledge graphs, in particular, new values.
\item SPARQL queries with a \emph{LIMIT} that don't require full materialization of the result.
\item Compression of the indexes and of the vocabulary.
\item Caching of intermediate results and making the query planner aware of cached results.
\item Efficient support of other SPARQL features like \emph{OPTIONAL}, \emph{UNION}, \emph{MINUS}, \ldots
\item Efficient support of predicate paths (explained in Example 3 of Section \ref{sec:query_languages:sparql}).
\end{enumerate}

\noindent For an overview of techniques, we again refer the reader to the survey by \citet{OTHER:AliSYHN21}.
For an open-source query engine implementing all of these, see \url{https://github.com/ad-freiburg/qlever},
the basic architecture of which is described in \citet{DBLP:conf/cikm/BastB17} and \cite{DBLP:conf/cikm/BastKKKS22}.

\subsection{Virtuoso}

\emph{Virtuoso} \cite{DBLP:books/sp/virgilio09/ErlingM09}, released by \emph{OpenLink Software} in 1999,
is the most widely used SPARQL engine in research.%
\footnote{There is a commercial version and an open-source version; the latter is usually used in research.}
It is written in C, and based on a database system (SPARQL queries are translated to SQL), but provides full RDF and SPARQL support.
In particular, it provides the official SPARQL endpoint for knowledge graphs as large as UniProt (80B triples);
see Section \ref{sec:examples}.
Virtuoso uses 8-byte OIDs for IRIs and long literals, while literals with $\le 12$ characters are stored without indirection.
The OIDs do not have the monotonicity property described above.
The following triple permutations are stored: \emph{PSOG}, \emph{POGS}, \emph{SP}, \emph{OP}, and \emph{GS}.
Here, $G$ denotes the knowledge graph (SPARQL has support for multiple graphs,
which can be addressed separately or altogether in a query).
The index can be partitioned and distributed over several machines.
Query planning is limited to the determination of the join order, where cost estimates are obtained via sampling the data.
Query plans can be analyzed only for the translated SQL query.
Intermediate results are materialized only if necessary; see the discussion above.

% \subsubsection{General Information}
% Virtuoso \cite{DBLP:books/sp/virgilio09/ErlingM09} is a commercial, multi-protocol server providing access to (relational) data stored in any combination of (external) databases (data can be also stored in Virtuoso itself).
% It is written in \emph{C} and implements \emph{RDF/SPARQL} (among others) on top of its own full-featured relation database (or any external relation database system).
% It is used to manage and browse the data exposed by \emph{dbpedia.org}.
% Virtuoso also supports full-text search via a custom \emph{bif:contains} predicate.

% \subsubsection{Architecture}
% Virtuoso stores the RDF triples (resp. quads) in a relational database table of four columns: \emph{G} (Graph), \emph{S} (subject), \emph{P} (predicate), \emph{O} (object).
% \emph{P}, \emph{G} and \emph{S} are internally fixed length identifiers, i.e. of custom SQL type \emph{IRI\_ID} (a numerical representation of an URI), \emph{O} is of SQL type ANY (any serializable SQL object, for example: a scalar or array).
% For long \emph{O}'s (with lengths > 12 characters), a unique id is stored instead of the actual value (and the actual value is stored in another table). Short \emph{O}'s are stored inline (and no ID is produced).
% Per default, Virtuoso introduces two indexes over the columns, which corresponds to the SPO and OPS permutation, more indices (permutations) can be built on demand.

% \subsubsection{Query processing}
% Virtuoso rewrites SPARQL queries to SQL queries.
% A SPARQL union becomes a SQL union and an OPTIONAL becomes a left outer join.
% Query optimization is made based on estimating the cardinality of given S,P,O combinations.

\subsection{Blazegraph}

\emph{Blazegraph} (formerly known as \emph{Bigdata}) \cite{blazegraph} is an open source database engine released by \emph{Systap} in 2006.
It is the query engine behind the official Wikidata query service\footnote{\url{https://query.wikidata.org/}};
it was selected at the time due to Wikimedia's open-source requirements.
However, they are currently looking for a replacement because of Blazegraph's inactivity. % This extra line messes up the format of the file...
Blazegraph also uses object IDs with 8 bytes and indexes the triples in three permutations
(\emph{SPO}, \emph{POS}, \emph{OSP}), using a B+ Tree for each.
A fourth dimension (like the graph name \emph{G} above) is supported optionally, in which case there are six indices.
Blazegraph also supports the full SPARQL standard and can be distributed over multiple machines.
Blazegraph is written in \emph{Java} and clearly lags behind in performance compared to Virtuoso for many typical queries.
A recent performance comparison against Virtuoso and QLever on a large set of queries can be found in \cite{DBLP:conf/cikm/BastKKKS22}.
%\TODO{(J) This recent evaluation also includes Virtuoso and QLever and mostly relies on monotonic OIDs, where to best but this reference?}
%SPARQL queries are translated to Abstract Syntax Trees (ASTs) and then applied to a series of (heuristic) optimization steps, for example: (1) removing expressions that evaluate to a constant,
%(2) reordering joins,
%(3) attaching FILTER clauses in the most advantageous location,
%(4) reordering of joins.
%The joins are reordered based on estimating the cardinality of a key range from the number of tuples spanned by a separator key in the B+Tree.
%Once the AST has been rewritten, it is translated into a physical query plan.

\subsection{Neo4j}\label{sec:indexing-neo4j}

\emph{Neo4j} was started by \emph{Neo4j, Inc.} in 2007,
and is the most widely used graph database for labeled property graphs in industry.
Neo4j is written in Java and supports Cypher, a variant of SPARQL, described in Section \ref{sec:query_languages:cypher}.
In principle, Neo4j can be used to index and query knowledge graphs, but not generally efficiently so.
In a nutshell, Neo4j has a record for each node (entity),
and for each record, stores pointers to the properties and relationships of that node; see Figure \ref{fig:example_graph}.
This design is efficient for retrieving information for a small set of entities and their neighborhood,
or for traversing the graph starting from such a set of entities.
It is extremely inefficient for queries that involve joins of large result sets.
%
For example, consider a query that asks for all persons of female gender.
A typical SPARQL engine processes this query by fetching precomputed lists for all entities of type \emph{Person}
and for all entities with gender \emph{Female},%
\footnote{These would both be segments of the \emph{POS} or \emph{OPS} index, assuming that the corresponding triples are
stored via predicates that stand for ``type'' and ``gender'', and object that stands for ``Person'' and ``Female'', respectively.}
and then joining these two lists.
Neo4j processes this query by iterating over all nodes with label \emph{Person}%
\footnote{Assuming that the types are represented via labels, which would be the natural thing to do in a property graph.}
and for each node follow pointers to the relationship \emph{gender} and check whether the adjacent node says \emph{Female}.


%\section{knowledge graph Construction}
%
%\TODO{Explain the crowd-sourcing nature of Freebase and Wikidata} \\
%\TODO{Clarify that the most succesful KBs to date are human made and not automatic} \\
%\TODO{Basics of automatic KB construction: entity linking, information extraction, slot filling} \\
%\TODO{Find SOTA KB construction engine and describe its architecture} \\
%\TODO{Refer to appropriate survey - clarif that it's a huge topic on its own} \\

%\section{Combination with text search}
%
%\TODO{Intro: structured core naturally in KBs, unstructured information in text -> combine the two} \\
%\TODO{Level 1: regular expression matching in literals -> part of the SPARQL standard} \\
%\TODO{Level 2: keyword search in literals -> most SPARQL engines have an extension like this} \\
%\TODO{Level 3: combined search in a text with entities linked to a KB -> QLever} \\
%\TODO{Explain how the big commercial engines combine KB and text search} \\
%\TODO{Refer to Section 9 for future developments}

\section{How to search a knowledge graph: assisting the user}\label{sec:advanced_queries}

In Section \ref{sec:query_languages:sparql} we have seen how to write formal SPARQL queries.
SPARQL is conceptually easy, because queries can be formulated as lists of triples, just like the data.
However, formulating the right query is often very hard in practice,
because it requires knowing the schema of the underlying knowledge graph
as well as knowing the IRIs and literals relevant for the query.
There are literally hundreds of user interfaces to help users to explore RDF data or formulate SPARQL queries.
In this section, we focus on the two most natural and most widely used forms of assistance:
SPARQL Autocompletion (Section \ref{sec:autocompletion}) and Question Answering, that is,
translating a natural language question into the corresponding SPARQL query (Section \ref{sec:question_answering}).

\subsection{SPARQL Autocompletion}\label{sec:autocompletion}

\def\sparqls{s} %{\mathit sparql}}
\def\token{t} % {\mathit token}}
\def\prefixvar{p} % {\mathit prefix}}

%In Section \ref{sec:query_languages:sparql} we have seen how to write SPARQL queries.
Autocompletion is a natural way to address the two problems mentioned above
(having to know the schema and the right IRIs and literals).
In this subsection, we describe how to aid a user in incrementally constructing a SPARQL query
by providing suggestions after every keystroke.
The suggestions have the following two important properties:

\begin{enumerate}[label=(\arabic*),topsep=0pt,itemsep=-3pt,leftmargin=20pt]
\item The suggestions are \emph{context-sensitive} in the sense that they continue the part of the query
already typed in a meaningful way.
\item The suggestions are \emph{ranked} by some measure of relevance, so that the continuation sought by the user
is as high up in the list of suggestions as possible.
\end{enumerate}

\noindent These properties will become very clear in the examples below.
\citet{DBLP:conf/cikm/BastKKKS22} provide a formal definition, together with an extensive quality and performance evaluation
and an account of related work on the topic.
A demo of an autocompletion system based on these ideas, for many of the knowledge graphs from Section \ref{sec:examples},
is available at \url{https://qlever.cs.uni-freiburg.de}.
Figure \ref{fig:qlever-ui} provides four screenshots.

%We first provide a formal problem definition and then explain it at length via three examples.
%
%\para{Problem Definition.}
%Imagine a valid SPARQL query typed until a certain point, called the \emph{cursor position}.
%Let $\sparqls$ be the part of the body of the \underline{S}PARQL query until that point.
%Let $\token$ be the \underline{t}oken (subject, predicate, or object) at the cursor position, i.e. the token that we want to complete.
%Let $\prefixvar$ be a \underline{p}refix of a name or alias of $t$, possibly empty.
%
%%The \emph{SPARQL Autocompletion via SPARQL} problem is:
%Given $\sparqls$ and $\prefixvar$, we would like to construct and process a SPARQL query,
%called \emph{autocompletion query} or \emph{AC query}, with the following properties:\\[2mm]
%1. The AC query returns a table with each row corresponding to a suggestion and the following three columns:\\[1mm]
%%
%\emph{?entity} (an entity from the knowledge graph),\\
%\emph{?name} (a name or alias of that entity, starting with $\prefixvar$),\\
%\emph{?score} (an estimate of how likely that entity is at the cursor position).\\[1mm]
%%
%2. The rows of the table are sorted in descending order of \emph{?score}.\\[1mm]
%3. One of the rows contains $\token$ in the \emph{?entity} column.\\
%\TODO{Use the enumerate-environment to format the enumeration more nicely}
%%, with an entry in the \emph{?name} column that starts with $\prefixvar$.\\[1mm]
%%There are two objectives:\\[.5mm]
%
%
%%We want each suggestion to be \emph{context-sensitive},
%Each suggestion should be \emph{context-sensitive}
%%\footnote{In the following, we often just call such suggestions \emph{sensitive}.}
%in the sense that it continues the SPARQL query in a meaningful way, that is,
%such that there exists a continuation with a non-empty result.
%%Moreover, suggestions should be \emph{relevant}, meaning that
%The row with the desired $\token$ should be as high up in the table as possible.

\begin{figure}
%The following four pictures are extracted from odp-files (LibreOffice). There is one file for each of the four images. Each pdf is obtained by simply exporting it from LibreOffice ("Als PDF exportieren").
\hspace{3mm}
\includegraphics[width=0.45\textwidth]{screenshot-fbe1.pdf}
\hspace{3mm}
\includegraphics[width=0.45\textwidth]{screenshot-fbe2.pdf}
\par\vspace{2mm}
\hspace{3mm}
\includegraphics[width=0.45\textwidth]{screenshot-wikidata1.pdf}
\hspace{3mm}
\includegraphics[width=0.45\textwidth]{screenshot-wikidata2.pdf}
\vspace{1mm}
\caption{Four screenshots of the SPARQL autocompletion in action, with three suggestions each.
Top-left and top-right: Examples 1 and 2 on a knowledge graph like that of Section \ref{sec:basics:example_1},
where the IRIs are directly understandable for a human.
Bottom-left and bottom-right: Example 3 and a continuation not described in the text,
for a query on Wikidata, where IRIs are alphanumeric and names are obtained
via dedicated predicates.
Note that the grey names in square brackets are not part of the formal SPARQL query,
but just there to help the user understand the query better.}
%The assignments below each screenshot show the values of the variables from our problem definition:
%$\sparqls$ (the part of the SPARQL query already typed), $\token$ (the desired token), and $\prefixvar$ (a prefix of a name or alias of that token).}
\label{fig:qlever-ui}
\vspace{-1mm}
\end{figure}

Since the suggestions should come from the knowledge graph, for which the user is trying to formulate their query,
it turns out that the suggestions can themselves be formulated as SPARQL queries,
called \emph{autocompletion (AC) queries} in the following.
This is a very elegant idea, because it allows the realization of autocompletion without additional software,%
\footnote{Except of course the code for the actual user interface. But there is no need for a separate program
that reads or preprocesses the knowledge graph in any way.}
using only the SPARQL engine that is already there.

In the following we explain this via three examples.
To understand these queries, you should be familiar with the SPARQL concepts presented in Section \ref{sec:query_languages:sparql}.
For an interactive experience, it is crucial that the AC queries are processed fast,
which is a major challenge when the knowledge graph is large.
We disregard the aspect of efficiency here and only mention that a SPARQL engine along the lines of
Section \ref{sec:indexing} can be extended to process AC queries fast.
Such an extension is described by \citet{DBLP:conf/cikm/BastKKKS22}.

\para{Example 1.}
%\TODO{Sollten wir nicht lieber \textbf{alle} Beispiele durchlaufend von 1 bis n durchnummerieren? Wenn mehrere Sections ein Example 1 haben, ist das eher verwirrend. Und wir müssten nicht sowas wie ``see Example 1 in Section 1.4.1'' schreiben, sondern nur ``see Example x''.}
Assume that we have typed the body of the SPARQL query in Example 1 in Section \ref{sec:query_languages:sparql} until before the first object; see below.
The $\cursor$ symbol marks the cursor position and the user has typed the prefix \emph{"P"}.
The desired object at this position is \emph{\iri{Person}}.

\begin{sparql}
{\sparqlentity} \iri{\isa} P\cursor
\end{sparql}

\noindent
The following AC query computes a table containing all objects \emph{?entity} (these are IRIs)
and their name \emph{?name} (these are literal strings),
such that the name starts with \emph{P}
and the triple \emph{{\sparqlentity} \iri{\isa} ?entity} exists.
The table is sorted in descending order of the number of such triples
for each \emph{?entity}.

\begin{sparql}
{\SELECT} ?entity ?name (\COUNT({\sparqlentity}) {\AS} ?score) {\WHERE} \{\\
\> {\sparqlentity} \iri{\isa} ?entity . \\
\> BIND (STR(?entity) AS ?name) . \\
\> {\FILTER} {\REGEX}(?name, "\verb|^|P")  \\
\} {\GROUPBY} ?entity ?name {\ORDERBY} DESC(?score)
\\ \examplequery{autocompletion-example-1}
\end{sparql}


\noindent
%\TODO{This probably needs some more explanation. GROUP BY, COUNT, STR and REGEX have not been introduced yet.}
The keyword {\BIND} assigns a value, in this case \emph{{\STR}(?entity)}, to a new variable, in this case \emph{?name}.
The first three result rows for that query look as follows.
The numbers are from a simplified version of Freebase, called \emph{Freebase Easy} \cite{DBLP:conf/www/BastBBH14}.%
\footnote{A SPARQL endpoint for Freebase Easy, with which the results for our
examples here can be reproduced, can also be found under the aforementioned \url{https://qlever.cs.uni-freiburg.de}.}

\begin{kb}
\iri{Person} \hspace{10mm}	\= "Person" \hspace{10mm}	\= 3970825   \\
\iri{Politician}			      \> "Politician"				    \> 127809    \\
\iri{Plant}					        \> "Plant"					      \> 60459
\end{kb}

\noindent
Note that for this knowledge graph, each name is simply the corresponding IRI converted to a string.
This is not generally the case, as we can see in Figure \ref{fig:qlever-ui} and Example 3 below.
Also note that the desired entity appears in the first row of the table,
and that, by construction, all suggested entities lead to a non-empty result.

\para{Example 2.}
Now assume that we have typed the SPARQL query a little bit further.
The desired predicate at the cursor position is \emph{\iri{\gender}}
and the user has typed no prefix yet to narrow down the search.

\begin{sparql}
	{\sparqlentity} \iri{\isa} \iri{Person} . \\
	{\sparqlentity} {\cursor}
\end{sparql}

\noindent
The following AC query gives us a ranked list of \emph{predicates} that lead to a non-empty result.
The score for each predicate is the number of persons (that is, entities matching the first triple) that have a triple with that predicate. If a person has several triples with the same predicate, we only count the predicate once, hence the {\DISTINCT}.

\begin{sparql}
{\SELECT} ?entity ?name ({\COUNT}({\DISTINCT} ?x) {\AS} ?score) {\WHERE} \{\\
\> ?x \iri{\isa} \iri{Person} . \\
\> ?x ?entity []~.	\\
\> BIND (STR(?entity) AS ?name) . \\
\} {\GROUPBY} ?entity ?name {\ORDERBY} DESC(?score)
\\ \examplequery{autocompletion-example-2}
\end{sparql}

\noindent
The square brackets \emph{``[]''} are used instead of introducing a new variable that remains unused in the rest of the query.
The first three result rows for this AC query are as follows:

\begin{kb}
\iri{\isa} \hspace{15mm}	\= "\isa"	\hspace{15mm}	\= 3970825 \\
\iri{\gender}				\> "\gender"					\> 2276146 \\
\iri{\birthday}			\> "\birthday"			\> 1915167
\end{kb}

\noindent
The desired predicate comes second in this table
and, again by construction, the AC query only returns predicates that lead to a hit.
The suggestions are ranked by how often each of them occurs with the set of entities
defined by the part of the query already typed.
Because of this, we did not have to type a single letter here to get very good suggestions.
%An \textit{agnostic} AC query computes a list of \emph{all} predicates, ordered by frequency,
%but independent of the rest of the query.
%Such a query would have bad relevance here:
%\emph{\iri{gender}} would not be among the top suggestions,
%and there would be many suggestions that are not meaningful for a person,
%for example \emph{\iri{release}} (of a musical recording).
% or \emph{\iri{author}} (of a book or article).\\[1mm]

\para{Example 3.}
Our last example is based on Wikidata, where entities have alphanumerical IRIs,
and the name is obtained via a dedicated predicate \emph{rdfs:label}. % and \emph{skos:altLabel}.
Assume that we have typed the body of the SPARQL query in Example 2 in Section \ref{sec:query_languages:sparql} this far:

\begin{sparql}
	wd:Q873 p:P166 ?m . \\
	?m \cursor
\end{sparql}%

\noindent
Again, the cursor is at the position of the predicate and the user has not yet typed a prefix at this position.
Recall that \emph{wd:Q873} stands for \emph{Meryl Streep} and \emph{p:P166} connects this entity to
all statement nodes \emph{?m} pertaining to one of her awards.
The desired token is \emph{pq:P1686}, which leads us to the awarded films. % (for example, \emph{The Iron Lady}).

%We could also consider \emph{ps:P166} as our desired token,
%since the order of the second and third triple in the original query is interchangeable.
%That would lead us to the awards (for example, \emph{Academy Award for Best Actress}).
The following AC query gives us a list of predicates, along with their English\footnote{Note that we could easily have names in another language here.} names, that lead to results at this point.
The score is analogous to that of the previous example.
%The predicate path {\it \verb|^|(<>|!<>)/rdfs:label} gives us the label of a predicate in Wikidata.

\begin{sparql}
{\SELECT} ?entity ?name ({\COUNT}({\DISTINCT} ?m) {\AS} ?score) {\WHERE} \{\\
\> wd:Q873 p:P166 ?m .                                    \\
\> ?m ?entity [] . \\
\> ?entity{\u}normalized ?tmp ?entity .   		                                  \\
\> ?entity{\u}normalized rdfs:label ?name FILTER (LANG(?name) = "en") \\
\}                                                        \\
{\GROUPBY} ?entity ?name                                  \\
{\ORDERBY} DESC(?score)                                   \\
\examplequery{autocompletion-example-3}
\end{sparql}
\noindent
The third and fourth triple connect a predicate to its label on Wikidata, see Section \ref{sec:basics:reification} for details. The first three result rows for this AC query look as follows:

\begin{kb}
ps:P166 \hspace{10mm}	\= "award received"@en  \hspace{5mm}	\= 33 \\
pq:P585					      \> "point in time"@en		\> 23 \\
pq:P1686				      \>  "for work"@en				\> 10
\end{kb}

\noindent
These rows tell us that Wikidata knows about $33$ awards of Meryl Streep,
$23$ points in time for these awards, and $10$ works awarded.
Our desired predicate comes third, and again all suggestions are context-sensitive by construction.
Without these suggestions it would require extremely intimate knowledge of Wikidata to know that
we need the predicate suffixes \emph{P166} and \emph{P1686}
and the prefixes \emph{ps:} (which stands for the main entity of a statement node)
and \emph{pq:} (which stands for additional properties of a statement node).
%Agnostic suggestions, as briefly mentioned in Example 2
%and defined in Section \ref{sec:ac_queries:agnostic}, would not be of much help here.

%For an interactive system, it is crucial that the AC queries are implemented efficiently.
%Especially when dealing with a huge knowledge graph like Wikidata,
%it is a very difficult task to achieve instant (i.e. less than $200\ms$) or at least sub-second response times for most of these AC queries.
%We omitted the details about efficiency here; for details see \TODO{AC paper}.
%

\def\result{?target}
\subsection{Question Answering}\label{sec:question_answering}
%
Context-sensitive autocompletion is great, but it still requires basic knowledge of the SPARQL syntax.
Ideally, the user can ask questions in natural language
(just as they would ask a human, without any constraints on the formulation),
which is then either translated automatically to a SPARQL query with the corresponding semantics,
or it is decided that no such SPARQL query exists (because the data is not in the knowledge graph).

Our running example in this section is the following question and corresponding SPARQL query
(referring to a simplified knowledge graph like the one from
Sections \ref{sec:basics:example_1} and \ref{sec:query_languages:sparql}, not Wikidata):\\[3mm]
%
\emph{What role does Meryl Streep play in The Iron Lady?} \\[-3mm]
\begin{sparql}
  {\SELECT} {\result} {\WHERE} \{\\
  \> \iri{\merylstreep} \iri{\filmperf} ?m . \\
  \> ?m \iri{film} \iri{\ironlady} . \\
  \> \iri{character} {\result} \\
  \}
\end{sparql}

\noindent
In this subsection, we explain the basic principles behind
a typical system that solves this problem.
The system is called \emph{Aqqu} \cite{DBLP:conf/cikm/BastH15},
and a demo is available at \url{https://aqqu.cs.uni-freiburg.de}.
\citet{DBLP:journals/kais/DiefenbachLSM18} provide a broader overview of techniques and systems
for question answering on knowledge graphs.
%
We divide this task into the following four steps, which we will explain in detail below:
\begin{enumerate}[label=(\arabic*),topsep=0pt,itemsep=-3pt,leftmargin=20pt]
\item Find entities from the knowledge graph that are mentioned in the question.
\item Generate candidate SPARQL queries that contain these entities.
\item Compute a \emph{feature vector} for each candidate.
\item Find the best candidate(s) by ranking the feature vectors.
\end{enumerate}


\subsubsection*{Step 1: Find entities from the knowledge graph mentioned in the question} %\label{sec:question_answering:findingEntities}
The input question typically refers to one or several entities from the knowledge graph
(assuming that it can be answered from the knowledge graph at all).
%The goal of the first step is to identify these entities.
Since we don't have an interpretation of the question at this point,
we identify \emph{all} possible entity mentions (or at least so many,
that we can be reasonably sure that the desired entities are among them)
and the respective entity in the knowledge graph.
This task is known as \emph{entity linking}; more about this in Section \ref{sec:text:entities}.
We assume that our entity linker does not only provide us with a single entity for each mention,
but with a probability distribution over several entities; this will be used in Step 3.

Entity linking is hard because the same entity can be referred to by many different names,
and the same piece of text can mean many different entities, depending on the context.
For example, there are many persons called \emph{Meryl},
and depending on the context, \emph{Iron Lady} could refer to the movie or to Margaret Thatcher personally.
%The system will consider all of the interpretations, in order to make sure the correct entities are not missed.
%Hence, the result of this step is a (very large) set of entity mentions.
If we assume that the question is well-formed, we can use a \emph{part-of-speech (POS) tagger}
to identify those parts of the question that could be entity mentions.
For our example, a perfect POS tagger would identify ``role'', ``Meryl Streep'' and ``Iron Lady''.
Without a POS tagger, any subsequence of words could be a potential entity match.
%we would have to check for entities matching any combination of consecutive words in the question, for example ``does Meryl'' or ``in the iron''.

Unfortunately, this method does not work well enough with predicates.
There is just much more variation in language in expressing predicates than in referring to entities,
and the match between the verb(s) in the question and the predicate in the query can be extremely fuzzy.
In our example, the words ``role does ... play'' (not even consecutive in the question)
correspond to the predicates \emph{\iri{\filmperf}} and \emph{\iri{character}} in the SPARQL query.
But the question could also be formulated differently, for example, ``Who is Meryl Streep in The Iron Lady?''.
We deal with the quality of the predicate matches in Step 3.
%Another example is the question ``Who is the CEO of Apple?''.
%The corresponding SPARQL query is
%\begin{sparql}
%  {\SELECT} ?x {\WHERE} \{\\
%  \> ?x \iri{tenure} ?m . \\
%  \> ?m $<$job-title$>$ "Managing Director" . \\
%  \> ?m \iri{company} "Apple Inc." \\
%  \}
%\end{sparql}
%Note that none of these predicates nor synonyms of them appear in the question.
%As these examples show,
%Predicate names depend on the structure of a language more than entity names do.
%The structure of knowledge graphs is often quite different from the structure of natural language.
%Besides, even in natural language, there are many ways to ask the above question, for example: , or ``What is Meryl Streep's character in The Iron Lady?'', or ``Who does Meryl Streep play in The Iron Lady?''.
%Note how the entities are always the same.

\subsubsection*{Step 2: Generating candidates}%\label{sec:question_answering:candidates}
We generate SPARQL queries, in which at least one entity from Step 1 appears as a subject or object.
Since there is a huge number of such queries, we only consider SPARQL queries
of a particular form, called \emph{template}.
Aqqu uses three templates, which are shown in Figure \ref{fig:candidates}.
They correspond to relatively simple SPARQL queries and they are sufficient to answer most simple questions.
Let us explain how to generate query candidates from the third template.
First, take any pair of entities $e_1$ and $e_2$ that were found in step (1) and whose mention text in the question does not overlap.
For each pair, find all predicates $r_1$, $r_2$, $r_3$ and mediator entities $m$ such that the triples ($e_1$ $r_1$ $m$), ($m$ $r_2$ $e_2$) and ($m$ $r_3$ $x$) exist in the knowledge graph, where $x$ represents an arbitrary entity.
Each assignment to $e_1$, $e_2$, $r_1$, $r_2$ and $r_3$ yields a query candidate.
For example, in the third row in Figure \ref{fig:candidates}, \iri{\merylstreep} was assigned to $e_1$, \iri{Margaret\u Thatcher} to $e_2$ and \iri{film\u performance}, \iri{character} and \iri{film} were assigned to $r_1$, $r_2$ and $r_3$, respectively.
This step generates many \emph{bad} query candidates, in the sense that their result is not the correct answer to the question (the first three examples in Figure \ref{fig:candidates}). % ~1000 candidates
However, the correct query should be among the candidates as well (last example in Figure \ref{fig:candidates}).
The next two steps address the problem of finding the correct query among the candidates.
%Some query candidates are better, in a sense that they are more similar to the question, for example (example 2 in Table).
%This connects Meryl Streep to a \emph{film performance} statement node and from there to all characters she has played.
%The correct query is similar, but has one more triple, restricting the result to the character she played in \emph{The Iron Lady}.
%Other candidates use wrong entities.
%For example, Margaret Thatcher might be identified as an entity in the last step, since she is often called the ``Iron Lady''.
%This can lead to a query candidate like: (Example 3 in Table)
%This yields the (wrong) answer ``The Iron Lady'' (the movie), since it confused the film and the person.
%The correct query should be among the query candidates as well:

\def\catOne{Ent}
\def\catTwo{Pred}
\def\catThree{Cov}
\begin{figure}
  \hspace*{-3mm}
  \begin{tabular}{@{\hspace{0.6cm}}lll@{}}
    {\bf Example Candidate} & {\bf Template} & {\bf Features} \\[3mm]
    \small
    \begin{tabular}[t]{@{}l@{}}
      \iri{\merylstreep} \iri{\wonaward} {\result}
    \end{tabular} &
    \begin{tikzpicture}[baseline=0]
      \node[draw, circle, minimum size=0.7cm](e1) at (0, 0) {$e_1$};
      \node[draw, circle, minimum size=0.7cm](t) at (1.5, 0) {$t$};
      \draw (e1) -- node[above] {$r_1$} (t);
    \end{tikzpicture} &
    \begin{tabular}[t]{@{}lr@{}}
	  \catOne: & $0.98$ \\
	  \catTwo: & $0$ \\
	  \catThree: & $0.2$
	\end{tabular}
    \\ [1.2cm]

	\small
    \begin{tabular}[t]{@{}l@{}}
	  \iri{\merylstreep} \iri{\filmperf} ?m . \\
	  ?m \iri{character} {\result}
	\end{tabular} &
	\begin{tikzpicture}[baseline=0]
	  \node[draw, circle, minimum size=0.7cm](e1) at (0, 0) {$e_1$};
	  \node[draw, circle, minimum size=0.7cm](m) at (1.5, 0) {$m$};
	  \node[draw, circle, minimum size=0.7cm](t) at (3, 0) {$t$};
	  \draw (e1) -- node[above] {$r_1$} (m);
	  \draw (m) -- node[above] {$r_2$} (t);
    \end{tikzpicture} &
    \begin{tabular}[t]{@{}lr@{}}
	  \catOne: & $0.98$ \\
	  \catTwo: & $1.3$ \\
	  \catThree: & $0.4$
	\end{tabular}
    \\ [1.2cm]

	\small
    \begin{tabular}[t]{@{}l@{}}
	  \iri{\merylstreep} \iri{\filmperf} ?m . \\
  	  ?m \iri{character} \iri{\margaretthatcher} . \\
  	  ?m \iri{film} {\result}
	\end{tabular} &
	\begin{tikzpicture}[baseline=0]
	  \node[draw, circle, minimum size=0.7cm](e1) at (0, 0) {$e_1$};
	  \node[draw, circle, minimum size=0.7cm](m) at (1.5, 0) {$m$};
	  \node[draw, circle, minimum size=0.7cm](e2) at (3, 0) {$e_2$};
	  \node[draw, circle, minimum size=0.7cm](t) at (1.5, -1) {$t$};
	  \draw (e1) -- node[above] {$r_1$} (m);
	  \draw (m) -- node[above] {$r_2$} (e2);
	  \draw (m) -- node[right] {$r_3$} (t);
	\end{tikzpicture} &
	\begin{tabular}[t]{@{}lr@{}}
	  \catOne: & $1.15$ \\
	  \catTwo: & $1.3$ \\
	  \catThree: & $0.7$
	\end{tabular}
	\\ [1.5cm]

	\small
	\begin{tabular}[t]{@{}l@{}}
	  \iri{\merylstreep} \iri{\filmperf} ?m . \\
  	  ?m \iri{film} \iri{\ironlady\u(film)} . \\
  	  ?m \iri{character} {\result}
	\end{tabular} &
	\begin{tikzpicture}[baseline=0]
	  \node[draw, circle, minimum size=0.7cm](e1) at (0, 0) {$e_1$};
	  \node[draw, circle, minimum size=0.7cm](m) at (1.5, 0) {$m$};
	  \node[draw, circle, minimum size=0.7cm](e2) at (3, 0) {$e_2$};
	  \node[draw, circle, minimum size=0.7cm](t) at (1.5, -1) {$t$};
	  \draw (e1) -- node[above] {$r_1$} (m);
	  \draw (m) -- node[above] {$r_2$} (e2);
	  \draw (m) -- node[right] {$r_3$} (t);
    \end{tikzpicture} &
    \begin{tabular}[t]{@{}lr@{}}
	  \catOne: & $1.72$ \\
	  \catTwo: & $1.3$ \\
	  \catThree: & $0.7$
	\end{tabular}
  \end{tabular}
  \caption{Four examples of query candidates generated for the question in Figure \ref{fig:qa_example}.
  The last row contains the query that correctly answers the question.
  Each template represents queries with a particular kind of structure.
  The nodes $e_i$ represent entities found in Step 1 and $r_i$ represent predicates that are connected with the entities as illustrated.
  The nodes $m$ are intermediate nodes, representing a variable in the query candidates.
  The nodes $t$ represent the $?target$ variable, which contains the answer that this candidate gives to the question.
  The last column shows the feature vectors, which give some indication for how good the match between the candidate and the question is;
  see Step 3 for more information.}
  \label{fig:candidates}
\end{figure}

\subsubsection*{Step 3: Computing feature vectors}%\label{sec:question_answering:features}
%\TODO{(C) Ich finde, wir springen zu sehr zwischen verschiedenen Erzählstilen hin und her. Im vorherigen Schritt erzählen wir anfangs aus der ``wir''-Perspektive (``We generate...'').
%In diesem Schritt aber anfangs eher aus einer formellen Perspektive, später wieder aus der wir-Perspektive.}
For each of the query candidates from the last step, we generate a feature vector.
Each of these features gives some indication about how likely this query candidate is to correctly answer the question.
As an example, we will discuss three different features.
A real system has more features; Aqqu for example has 23.

\para{Entities (\catOne):}
How well do the entities match the question?
We make use of the probabilities that the named-entity linker from Step 1 provides.
For each entity $e$ that matched a part of the question $s$,
compute the probability $\text{p}\left( e | s \right)$ that $s$ actually referred to the entity $e$, for example:
%This probability distribution can be obtained by counting how often $s$ was the anchor text for a link on Wikipedia and how often it linked to the entity $e$, for example:
\begin{alignat*}{2}
	\text{Prob}(\text{\iri{\ironlady\u(film)}} \:|&\: \text{``The Iron Lady''}) &\:=\: 0.74 \\
	\text{Prob}(\text{\iri{\margaretthatcher}} \:|&\: \text{``The Iron Lady''}) &\:=\: 0.17 \\
	\text{Prob}(\text{\iri{\merylstreep}} \:|&\: \text{``Meryl Streep''}) &\:=\: 0.98
\end{alignat*}
For the final score, aggregate these probabilities for all entities that appear in a query.
For our example in Figure \ref{fig:candidates} we added them up.

\para{Predicates (\catTwo):}
How well do the predicates match?
In a first approach, we would like to measure how similar the words in the question are to the words of the predicates in the query.
We can do this by either considering literal matches or derivations, for example lemmatization (e.g., ``played'' $\rightarrow$ ``play'') or synonyms (e.g., ``role'' and ``character'').
We compute a score, for example, by counting the number of matches or determining the percentage of predicate words covered in the query.
However, as discussed in Step 1, this often does not work with predicates.
%To address this problem, Aqqu has more elaborate features for predicate matching, besides the ones mentioned above.
We will now explain a more elaborate strategy for fuzzy predicate matching in more detail.
%The goal is to find \emph{indicator words} for a predicate or a concatenation of two predicates.
Assume we want to find words that describe the relationship \iri{\merylstreep} has to \emph{?target} in the second example in Figure \ref{fig:candidates}.
In order to find such \emph{indicator words}, we replace \iri{\merylstreep} with a variable and run the following query

\begin{sparql}
  {\SELECT} ?x ?target {\WHERE} \{ \\
  \> ?x \iri{\filmperf} ?m . \\
  \> ?m \iri{character} ?target \\
  \}
\end{sparql}

\noindent
Among others, we get a result row where \emph{?x} is \iri{Leonardo\u DiCaprio} and \emph{?target} is \iri{Billy\u Costigan}.
For each row in the result, look for all sentences (e.g., on Wikipedia) that contain both entities:

\begin{kb}
	In Scorsese's The Departed, \ul{DiCaprio} played the role of \ul{Billy Costigan}.
\end{kb}

\noindent
Now, consider %the lemmatization\footnote{the dictionary form; for example played $\rightarrow$ play} of
each verb or noun between the entity occurrences as an indicator word.
In other words, we have learned that ``play'' or ``role'' are indicator words for the relationship \iri{\filmperf} plus \iri{character}.
This is an instance of \emph{distant supervision},
i.e. using external data to learn something useful for our task.
Compute a score for how good an indicator word describes the relation, depending on how often it was found.
Then, for each query candidate sum up the scores for all words from the question that match a relation.
As a result, the last three examples in Figure \ref{fig:candidates} get a higher score for this feature than the first one (since no indicator words of \iri{\wonaward} appear in the question).

\para{Coverage (\catThree):}
How much of the question is covered by the query?
Generally, the more parts of the question are matched to entities or predicates in a query candidate, the better the candidate is.
Hence, we compute the percentage of words covered
by dividing the number of words that are matched by the total number of words in the question.
For example, the third candidate in Figure \ref{fig:candidates} covers $7$ out of $10$ words:

\begin{kb}
  What \ul{role} does \ul{Meryl} \ul{Streep} \ul{play} in \ul{The} \ul{Iron} \ul{Lady}?
\end{kb}

\noindent
Note that we could also give weights to different words, if we are able to identify important parts of a question.
In our example, the words not covered (``what'', ``does'' and ``in'') are not very important since they do not carry a lot of meaning.
It is therefore not important to cover them and we could assign lower weights to them. \\[5pt]
The scores in the feature vectors can be \emph{misleading} in the sense that the correct query does not get the best score.
For example, questions can contain additional information that should not be matched in the query.
Consider the question ``What role does Meryl Streep play in the British drama film The Iron Lady?''.
The part ``British drama film'' is irrelevant and queries that match this part are probably wrong.

\subsubsection*{Step 4: Ranking}%\label{sec:question_answering:ranking}

There is usually no candidate with a feature vector that is better than all other feature vectors
in all components.
Therefore, we need an algorithm to determine the ``best'' feature vector.

A simple approach would be to turn each feature vector into a real-values score
by taking a linear combination of its components.
For example:
$$s(c) = 5 \cdot c_{\text{\catOne}} + 3 \cdot c_{\text{\catTwo}} + 4.5 \cdot c_{\text{\catThree}},$$
where $c$ is a query candidate and $c_x$ is the score that $c$ got for feature $x$.
With good weights, this approach can work reasonably well, but finding good weights manually is hard,
especially when there are many features.

More sophisticated approaches try to \emph{learn} to determine the best feature vector among a given set.
To learn scores, we need training samples of the kind \emph{feature vector $\rightarrow$ score}.
Note that we can generate them from training samples of the kind \emph{question $\rightarrow$ answer} in the following way.
Using the previous steps, for each question in the ground truth, we generate query candidates and the feature vector for each candidate.
Mark a feature vector as positive sample, if the corresponding query candidate returns the correct answer according to the ground truth
and mark all other feature vectors as negative samples.
The problem with this approach is that the same feature vector can be good for one (hard) question and bad for another (easy) question.
To address this issue, we transform the problem into a binary classification problem and \emph{learn to compare} two feature vectors.
We generate pairs of one ``positive'' and one ``negative'' feature vector and we mark which one is better.
In the QA system, for all pairs of feature vectors, we let our trained classifier decide, which one is better and pick the candidate that \emph{wins} most of these comparisons.
There are two variants of Aqqu with respect to this classifier: one uses random forests and one uses a neural network.
For details, see \citet{DBLP:conf/cikm/BastH15}.

%\TODO{Keyword search: differences to QA + brief overview of systems} \\
%\TODO{Other query paradigms -> of minor relevance in practice} \\

%\section{Advanced Topics}
%
%\TODO{Huge topics by themselves, but more advanced and currently not needed/used in many apps.} \\
%\TODO{Ontology matching + merging -> condense the corresponding FNTIR chapter + bring it up to date} \\
%\TODO{Reasoning and inference -> condense the corresponding FNTIR chapter and bring it up to date} \\
%\TODO{Semantic Web: describe the general idea of not having a common schema} \\
%\TODO{Nice idea, which works on a basic level, for example, schema.org} \\
%\TODO{But little impact beyond becaue the data is just to heterogenuous to make sense of} \\

\section{Combination with text search and federated search}\label{sec:text}

There are several scenarios, where we want to extend a SPARQL query by a text-search component.
We briefly explore these in Sections \ref{sec:text:literals} (text search in literals) and \ref{sec:text:entities} (text search in an an external text corpus). Another frequent scenario is that we want to query multiple RDF datasets simultaneously with
a single query. We briefly explore this in Section \ref{sec:federated}.

\subsection{Keyword search in literals}\label{sec:text:literals}

As we have seen in Section \ref{sec:basics}, the object of a triple can also be a string containing arbitrary text.
A typical use is for the name, alias or description of an entity; see Section \ref{sec:basics:example_2}.
The SPARQL query language supports a function \emph{REGEX} that determines whether a given string matches a given regular expression.
For example, the following query finds all people on Wikidata, whose name ends with \emph{Einstein}:
%
\def\ha{\hspace{3mm}}
\def\hb{\hspace{5mm}}
\def\hc{\hspace{7mm}}
\def\hd{\hspace{22mm}}
\def\c#1{{\color{gray}#1}}
\begin{sparql}
  {\SELECT} ?person{\u}name {\WHERE} \{ \\
    \ha\= ?person \hb\= wdt:P31     \hc\= wd:Q5 .             \hd\=\c{\# instance of human} \\
       \> ?person    \> rdfs:label     \> ?person{\u}name .      \>\c{\# name} \\
       \> {\FILTER} ({\LANG}(?person{\u}name) = "en")        \>\>\>\c{\# English} \\
       \> {\FILTER} {\REGEX}(?person{\u}name, " Einstein\$")    \>\>\>\c{\# ends with " Einstein"} \\
  \}
  \\ \examplequery{persons-name-einstein}
\end{sparql}

\def\b{{\backslash}b}
\def\bb{{\backslash\backslash}b}
\noindent
Literals can contain arbitrarily long text.
For example, Wikidata contains an entity for each Wikipedia article, and we might use the predicate \emph{schema:description}
to associate each article with its abstract.%
\footnote{The abstract of a Wikipedia article is the part before the table of contents. We might also take the whole text,
but \emph{schema:description} is commonly used for short descriptions.}
%
For a text search in such literals, keyword search is often the method of choice.
That is, we specify a number of keywords, and we expect the engine to match all literals containing these keywords (in any order).
In principle, keyword search can be simulated in SPARQL by introducing one \emph{FILTER REGEX} clause per keyword.
For example, the following query finds all astronauts, where the Wikipedia abstract mentions the word \emph{moon} and a word starting with \emph{walk}.%
\footnote{The \emph{$\b$} in a regular expression matches a word boundary. For example, \emph{$\b$moon$\b$} matches a string that contains the word \emph{moon}, but does not match a string that contains the words \emph{honeymoon} or \emph{moons}, but not \emph{moon}. We would therefore expect the query to match all astronauts who actually walked on the moon. Backslashes have to be escaped in SPARQL, so we need to use \emph{$\bb$} in the query. The argument \emph{"i"} stands for case-insensitive search.}

\def\ha{\hspace{3mm}}
\def\hb{\hspace{3.5mm}}
\def\hc{\hspace{14.2mm}}
\def\hd{\hspace{10mm}}
\def\c#1{{\color{gray}#1}}

\begin{sparql}
  {\SELECT} ?astronaut{\u}label ?abstract {\WHERE} \{ \\
    \ha\= ?astronaut \hb\= wdt:P106     \hc\= wd:Q11631 .            \hd\=\c{\# occupation astronaut} \\
       \> ?astronaut    \> rdfs:label      \> ?astronaut{\u}label .      \>\c{\# name} \\
       \> ?wikipedia   \> schema:about 	\> ?astronaut . 				\>\c{\# Wikipedia article} \\
       % \> ?wikipedia  \> schema:isPartOf \> \iri{https://en.wikipedia.org/} . \\
			 \> ?wikipedia    \> schema:description \> ?abstract .            \>\c{\# Wikipedia abstract} \\
       \> {\FILTER} ({\LANG}(?astronaut{\u}label) = "en")               \>\>\>\c{\# English name} \\
       \> {\FILTER} {\REGEX}(?abstract, "$\bb$moon$\bb$", "i")       \>\>\>\c{\# contains word "moon"} \\
       \> {\FILTER} {\REGEX}(?abstract, "$\bb$walk", "i")                 \>\>\>\c{\# contains word starting with "walk"} \\
  \} \\
	\examplequery{astronauts-walk-moon-with-regex-filter}
\end{sparql}
%

\noindent
The query above is not only cumbersome to write down, but also not processed efficiently in most SPARQL engines.
The reason is that the two {\REGEX}es will be checked for every \emph{?abstract} that matches the rest of the query.
In particular, this requires the materialization of the respective strings.
A more efficient approach would be to build a dedicated data structure that supports keyword search in literals,
like an inverted index.
Engines like QLever and Virtuoso indeed provide this functionality.
For example, to process the query above more efficiently (with exactly the same result)
in QLever, one can replace the last two {\FILTER} lines as follows.%
\footnote{Virtuoso achieves the same functionality using the special \emph{bif:contains} predicate.}

\begin{sparql}
  {\SELECT} ?astronaut{\u}label ?abstract {\WHERE} \{ \\
    \ha\= $\ldots$ \phantom{tronaut} \hb\= \phantom{wdt:P106} \hc\= \phantom{wd:Q11631} \hd\=\c{\# first five lines like above} \\
    \> ?abstract ql:match-keywords "moon walk*" \>\>\>\c{\# match given keywords} \\
	\} \\
	\examplequery{astronauts-walk-moon-with-keyword-matching}
\end{sparql}
%\TODO{(C) Die Query auf QLever nutzt nicht \emph{ql:match-keywords}, sondern \emph{ql:contains-entity} und \emph{ql:contains-word}. Und der Suchstring ist nicht \emph{moon walk*} sondern \emph{walk* moon}}

\subsection{Search in an external text corpus linked to a knowledge graph}\label{sec:text:entities}

\def\ul#1{\underline{\smash{#1}}}
\def\wid#1{\href{https://www.wikidata.org/wiki/#1}{#1}}
The example query above constrained a certain set of entities (astronauts) by information contained in text (the Wikipedia abstracts).
This worked because the relevant texts were connected to the relevant entities via a predicate (\emph{schema:description}).

But this is the exception: entity descriptions are typically very short and contain only the most notable information.
In a more general scenario, we are given an abitrary text corpus that mentions entities from the knowledge graph.
To identify these entity mentions, we need to perform a task called \emph{entity linking}
(which we have already used for question answering in Section \ref{sec:question_answering}).%
\footnote{For a recent overview paper with a list of the top-performing tools, see \cite{DBLP:conf/emnlp/BastHP22}.}
For example, assume that our text corpus contains the following sentence from Section \ref{sec:basics:text}.\\[1mm]
%
\emph{As \ul{Armstrong} [\wid{Q1615}], whose great-grandfather Friedrich Wilhelm Kötter emigrated from \ul{Ladbergen} [\wid{Q181877}] to the \ul{United States} [\wid{Q30}] in 1864, was the first man to walk on \ul{the moon} [\wid{Q405}] in 1969, many citizens of \ul{Ladbergen} [\wid{Q181877}] became interested in their \ul{American} [\wid{Q846570}] relatives.}\\[1mm]
%
In such a scenario, we want to formulate queries that specify the co-occurrence of a certain kind of entity with certain words.
For example, the following query asks the same questions as in the previous subsection (astronauts who walked on the moon),
but this time without assuming that the information is contained in the description of the respective entities.
As an additional asset, the astronauts can now be ranked by how often they occur with the specified words.%
\footnote{We could also specify a more complex ranking function if we wanted to.}

\def\ha{\hspace{3mm}}
\def\hb{\hspace{5mm}}
\def\hc{\hspace{15mm}}
\def\hd{\hspace{15mm}}
\def\c#1{{\color{gray}#1}}
\begin{sparql}
  {\SELECT} ?astronaut{\u}name ({\COUNT}(?text) {\AS} ?count) {\WHERE} \{ \\
    \ha\= ?astronaut \hb\= wdt:P106     \hc\= wd:Q11631 .            \hd\=\c{\# occupation astronaut} \\
       \> ?astronaut    \> rdfs:label      \> ?astronaut{\u}name .      \>\c{\# name} \\
       \> {\FILTER} ({\LANG}(?astronaut{\u}name) = "en")               \>\>\>\c{\# English name} \\
       \> ?astronaut \> ql:mentioned-in   \> ?text .                    \>\c{\# entity mention in text ...} \\
       \> ?text      \> ql:match-keywords \> "moon walk*" .             \>\c{\#	... that matches keywords} \\
  \} \\
	{\GROUPBY} ?astronaut{\u}name
	{\ORDERBY} {\DESC}(?count) \\
	\examplequery{astronauts-walk-moon-with-entity-linking}
\end{sparql}

\noindent
The predicate \emph{ql:mentioned-in} is a so-called \emph{magic predicate}.
It links each entity to all texts mentioning that entity.
Note that this predicate represents a many-to-many relation: a single entity may be (any typically is) mentioned in multiple texts and a single text may contain multiple entities.
A simple realization of a magic predicate is to explictly add it to the RDF dataset.
The performance of this approach depends on the ability of the query engine to perform join operations with this (typically huge) predicate.
For example, the English Wikipedia (which is a text corpus of moderate size compared to, say, a web corpus), contains around one billion mentions of entities from Wikidata.
QLever provides a more efficient realization that avoids this explicit materialization but requires that the usage of \emph{ql:mentioned-in} is always combined with a keyword filter.%
\footnote{Especially when the texts are sentences, a single text typically mentions only few (often only one) entity.
This information can then be stored in the inverted index lists.}
For more information on this, see \citet{DBLP:conf/cikm/BastB17}.

Note that in the query above, as well as in the query from the previous subsection, it is implicitly assumed that entities or words that occur together in a text, also ``belong together semantically''.
But that is not necessarily the case, especially for longer texts or complex sentences.
For example, in the sentence above, it is Neil Armstrong who walked on the moon and his great-grandfather who emigrated from Germany, and not vice versa.
This problem can be addressed by splitting the text into its semantic constituents; see \cite{DBLP:conf/semco/BastH13}.

\subsection{Federated search}\label{sec:federated}

\emph{Interoperability} is at the heart of the RDF framework.
Because each dataset is simply a set of triples and entities have globally unique identifiers,
we can simply combine two datasets by combining the sets of triples.
Alternatively, SPARQL allows the querying of multiple datasets via the {\SERVICE} keyword (for a discussion of scenarios where this approach is useful see the following section).
For example, the following query asks for all movies directed by the Coen brothers (information contained in Wikidata),
ranked by the number of votes in IMDb (information contained in the IMDb dataset).

\def\ha{\hspace{3mm}}
\def\hb{\hspace{5mm}}
\def\hc{\hspace{12mm}}
\def\hd{\hspace{15mm}}
\def\hh{\hspace{2mm}}
\def\c#1{{\color{gray}#1}}
\begin{sparql}
  {\SELECT} ?movie ?imdb{\u}votes {\WHERE} \{ \\
		\ha\= ?movie \hb\= wdt:P31      \hc\= wd:Q11424 .     \hd\=\c{\# instance of film} \\
		\> ?movie       \> wdt:P345        \> ?imdb{\u}id .      \>\c{\# IMDb ID} \\
		\> ?movie       \> wdt:P57         \> wd:Q13595311 .     \>\c{\# directed by Joel Coen} \\
    \> {\SERVICE} $<$https://qlever.cs.uni-freiburg.de/api/imdb$>$ \{ \\
		\>\ha ?movie{\u}imdb \hh imdb:id \hh ?imdb{\u}id .           \>\>\>\c{\# IMDb entity with ?imdb{\u}id} \\
		\>\ha ?movie{\u}imdb \hh imdb:numVotes \hh ?imdb{\u}votes .  \>\>\>\c{\# number of votes} \\
    \>\} \\
	\}\\
	{\ORDERBY} {\DESC}(?imdb{\u}votes)
	\\ \examplequery{movies-joel-coen}
\end{sparql}
%\TODO{(C) Query auf QLever hat andere SELECT-clause und nutzt zusätzliches Tripel mit \emph{rdfs:label}}

\noindent
The semantics of the {\SERVICE} clause is easy to understand and fits very naturally into the RDF framework.
In the query above, the body of the {\SERVICE} clause is turned to a SPARQL query by adding a
\emph{{\SELECT} * {\WHERE} \{ $\ldots$ \}} around it.
That query is then sent to the SPARQL endpoint defined right after the {\SERVICE} keyword.
The result from that query is a table (or binding), just like the result of any graph pattern in a SPARQL query is a table (or binding).

A conceptually trivial implementation of {\SERVICE} is to send the query to the remote endpoint,
receive the fully materialized result (in a typical serialization format like JSON),
and let the issuing SPARQL engine parse that result for further processing.
This is correct, but can be inefficient when that materialized result is moderately large
and becomes infeasible when the result is huge.

We briefly describe two possible optimizations.
One optimization\footnote{This optimization is so obvious that it is already mentioned in the standard: \url{https://www.w3.org/TR/sparql11-federated-query\#values}.} is to send the remote endpoint additional information that helps it to reduce the results size.
For example, in the query above, the set of movies is restricted to those by a particular director.
The SPARQL engine could therefore send the remote endpoint the respective bindings for \emph{?imdb{\u}id} (19 movies by Joel Coen),
which would result in a much smaller result of the {\SERVICE} query.
Another optimization is to both send and receive bindings not in materialized form, but in binary form,
for example, using the internal IDs mentioned in Section \ref{sec:indexing}.
This is challenging to implement, however, because internal IDs from different SPARQL engines are not naturally compatible
so that we need an efficient translation scheme.

\subsection{Use cases of federated search}\label{sec:federated:use-cases}

We briefly discuss three use cases of federated search, which demonstrate the power of this paradigm.

The first and most typical use case is to query multiple RDF datasets in a single query.
The query above gives an example for that.
Note that a SPARQL query may issue {\SERVICE} queries to an arbitrary number of remote endpoints,
and these queries may even be nested (that is, a {\SERVICE} query may itself contain another {\SERVICE} query).
Also note that the remote endpoint may be a variable.
That way, we can select the appropriate endpoint via a SPARQL query or part of SPARQL query.

A second use case is to split a large datasets into multiple datasets.
One reason for this could be that smaller datasets can be queried more efficiently.
Another reason could be that we may have one large part of the dataset that is static
(building an index for a large RDF dataset is expensive, see Section \ref{sec:indexing}),
and one or several smaller parts that are dynamic (so that new indexes can be built for them fast).

A third use case is that a remote endpoint must obey the SPARQL API,
but depending on the service provided it must not necessarily be a full-featured SPARQL engine,
but may use a special-purpose implementation.
For example, the \emph{Wikidata Query Service (WDQS)}\footnote{\url{https://query.wikidata.org/}} has a {\SERVICE} that provides
labels for entities from a SPARQL query.
Using this {\SERVICE} is more efficient than explicitly using the \emph{rdfs:label} predicate on the
Blazegraph query engine (which was the WDQS backend at the time of this writing), especially when many labels have to be retrieved.%
\footnote{At the time of this writing, the \emph{rdfs:label} predicate contained 810M triples in Wikidata.}
% Computing a join with such a predicate is very expensive and beyond the capacities of the current WDQS backend.}
It is, however, relatively straightforward using a special-purpose data structure.

\section{The future of knowledge graphs}\label{sec:outlook}

In this chapter, we have gently introduced the basics of RDF and SPARQL,
we got acquainted with some of the most important publicly available knowledge graphs and their characteristics,
we have learned how to index and search a knowledge graph efficiently,
and we have seen some basic techniques for how to assist users in formulating their SPARQL queries.

%A closely related topic is how to combine search in a knowledge graph with \emph{text search};
%see the discussion in Section \ref{sec:basics:text}.
%SPARQL allows searching for literals that match or do not match a particular regular expression.
%In principle, this mechanism can be used for keyword search in literals, but not efficiently so.%
%\footnote{For example, a typical SPARQL engine processes \emph{?entity rdfs:label ?name . FILTER REGEX(?name, "Obama")}
%by computing all matches for \emph{?name} and then check for each match whether it contains the string \emph{Obama}.}
%The index data structure described in Section \ref{sec:indexing} can be naturally extended
%to support keyword search in literals efficiently,
%as well as search in an external text corpus with entity mentions from the knowledge graph.

There are many other important questions around knowledge graphs that we haven't even touched upon:
How to construct a knowledge graph automatically or semi-automatically?
How to fill gaps in an existing knowledge graph or fix mistakes or resolve inconsistencies?
How to resolve conflicts and fuse results when querying multiple knowledge graphs?
How to reason on knowledge graphs?
These aspects are discussed in the recent and very extensive survey by \citet{OTHER:HoganBCDDGGKNPNNRRSSSZ21}.
That survey also lists (in its Table 1) many surveys on more specialized subtopics.
% However, none of these surveys cover indexing and search and is hence nicely complementary to our article.

Before we close, let us dare take a short glimpse into the future.
The last decade has seen tremendous advances in the field of \emph{deep learning},
with revolutionary results across a wide variety of application domains.
Notably, \emph{large language models (LLMs)} have recently achieved state-of-the-art results and better
on a wide variety of tasks with little (\emph{few-shot}) or no (\emph{zero-shot}) task-specific learning
 \cite{DBLP:journals/corr/abs-2303-08774}.
In particular, such LLMs can automatically translate natural language questions
to SPARQL queries, as explained in Section \ref{sec:question_answering} using an explicit approach.
%It should be noted in this context that task-specific models can have an edge over universal models
%for two reasons: first, they might be more precise and second (and more importantly),
%inference with the task-specific models is usually more efficient.
%
A central question in this context is how classical frameworks like knowledge graphs (or, more generally, databases)
will co-exist with such universal models in the future.
We see three possible scenarios.

\medskip\noindent
1. Knowledge graphs and universal models will co-evolve, but remain separate ``species''.
The models will learn better and better how to formulate even complex queries,
but they will resort to an external query engine (like the ones described in Section \ref{sec:indexing})
for executing these queries.
The result can then be fed back into the ``thinking process'' of the model
and this interaction may already be part of the training.
As this mode of operation becomes more prevalent,
query engines will adapt to suit the needs of these models better.%
\footnote{For example, embeddings of entities and predicates might become first-class citizens in the query engine.}
We consider this the most likely scenario in the near and mid future.

\medskip\noindent
2. In a more dim scenario, knowledge graphs will become mere food (training data) for universal models.
Given enough data, the models might learn by themselves how to answer even complex queries
without having to resort to an external query engine.
We consider this scenario unlikely for two reasons.
First, it looks hard for a learned model to answer complex queries involving large datasets with 100\% accuracy
(a task that for a classical query engine is merely a matter of a correct implementation).
Second, resourcefulness is a major factor for large datasets.
For example, consider a business application that needs to store billions or trillions of data records.
Why let a model figure out how to store and query this data precisely and compactly
instead of using standard compression and indexing techniques directly?
We therefore don't consider this scenario very likely.

\medskip\noindent
3. The third scenario is that of hybrid systems that somehow combine universal models
and classical storage and indexing techniques.
At the time of this writing, there is no noteworthy development in this direction.
We consider such development unlikely because of the following high-level argument:
The evolution of all complex organizations we know of (including nature and human societies)
has brought forth different kind of subsystems with specialized capabilities.
Interaction between these subsystems is extremely important (and may range from slim interfaces to symbiotic relationships),
but the subsystems remain separately identifiable species.
The universe we live in does not seem to favor hybrid monsters.
Then again, there is the Borg\footnote{"Your biological and technological distinctiveness will be added to our own. Resistance is futile. You will be assimilated."} and we are still at a very early stage in our evolution.

\medskip\noindent
Whatever will happen, we will soon be able to discuss these fascinating topics in depth
and in person with a universal model of our choice $\ldots$ if they are still talking to us then.

%\bibliographystyle{ACM-Reference-Format}


\nocite{DBLP:journals/sigmod/SakrA09}
\nocite{DBLP:conf/otm/SvobodaM11}
\nocite{DBLP:journals/arima/FayeCB12}
\nocite{DBLP:books/sp/12/LuoPFHV12}
\nocite{DBLP:journals/vldb/KaoudiM15}
\nocite{DBLP:journals/ker/MaCY16}
\nocite{DBLP:journals/fcsc/Ozsu16}
\nocite{DBLP:journals/pvldb/AbdelazizHKK17}
\nocite{DBLP:conf/rweb/JankeS18}
\nocite{DBLP:journals/jaihc/PanZ0N18}
\nocite{DBLP:journals/csur/WylotHCS18}
\nocite{DBLP:conf/dasfaa/YasinZHFY18}
\nocite{DBLP:conf/sca2/Alaoui19}
\nocite{DBLP:journals/csr/ChawlaSPG20}
\nocite{DBLP:conf/sac/SantanaM20}



\bibliography{ACM-publications,kb-survey}

\end{document}

\newpage
\section{Meeting minutes}

\subsection{Meeting 02.12.2020: Hannah, Claudius, Theresa}

In this section, we introduce the most popular knowledge graphs which have been developed
over the last years -> really?

enterprise knowledge graphs -> better name

Order: most important first, not chronologically

@DBpedia: more compact + say something about reification

@YAGO: a bit too abstract, explanation by example would be good

@Domain-specific: more concrete would be better

@Enterprise knowledge graph: can something be said about the contents of these KBs?


\subsection{Meeting 26.11.2020: Hannah, Claudius, Theresa}

{\bf GraphQL vs.\ SPARQL}\\
Pro GraphQL: no need to convert to triples (reification)\\
Pro GraphQL: typical queries in familiar JSON stlye (though SPARQL is not really harder)\\
Con GraphQL: need to write code to create data and schema (TODO: how comfortable or not?)\\
Con GraphQL: limited query capabilities (fixed type of queries)\\
Typical use: API for datasets with a few typical patterns

{\bf Size of knowledge graphs}
What is a \emph{statement} in Wikidata?\\
Similar measure in other knowledge graph?\\
Number of triples is a misleading measure because it can be artificially high due to modeling.\\

{\bf Cypher and Gremlin}
Query language for property graphs\\
Node: has a label (= type) and any number of optional values (= literals)\\
Edge: has a label (= type) and any number of optional values (= literals)\\
TODO: can the values also be nodes? If not, how to model an $n$-ary edge? Also via intermediate nodes?\\

{\bf Property Graphs vs.\ RDF Graphs}
Star-shaped queries are (of course) faster, because the properties are stored with each node.\\
The downside is that if you really have to connect different nodes (big sets of them), it is very slow.

TODO: Ask Johannes, whether we still need entities ordered in a certain way.


\newpage
\section{Meeting minutes}

\subsection{Meeting 26.11.2020: Hannah, Claudius, Theresa}

{\bf GraphQL vs.\ SPARQL}\\
Pro GraphQL: no need to convert to triples (reification)\\
Pro GraphQL: typical queries in familiar JSON stlye (though SPARQL is not really harder)\\
Con GraphQL: need to write code to create data and schema (TODO: how comfortable or not?)\\
Con GraphQL: limited query capabilities (fixed type of queries)\\
Typical use: API for datasets with a few typical patterns

{\bf Size of knowledge graphs}
What is a \emph{statement} in Wikidata?\\
Similar measure in other knowledge graph?\\
Number of triples is a misleading measure because it can be artificially high due to modeling.\\

{\bf Cypher and Gremlin}
Query language for property graphs\\
Node: has a label (= type) and any number of optional values (= literals)\\
Edge: has a label (= type) and any number of optional values (= literals)\\
TODO: can the values also be nodes? If not, how to model an $n$-ary edge? Also via intermediate nodes?\\

{\bf Property Graphs vs.\ RDF Graphs}
Star-shaped queries are (of course) faster, because the properties are stored with each node.\\
The downside is that if you really have to connect different nodes (big sets of them), it is very slow.

TODO: Ask Johannes, whether we still need entities ordered in a certain way.

\newpage
\begin{appendix}
  \section{Knowledge Graphs Basics (Preliminary Notes)}

  \noindent \TODO{{\bf (0)
        We should clarify which terminology we want to use} (or explain the differences between the terms, if there are any differences): \\
    \,(a) \emph{statements vs. facts vs. triples}; \\
    \,(b) \emph{predicates vs. properties vs. relations}; \\
    \,(c) \emph{knowledge graph vs. ontology}%
  } \\

  \noindent \TODO{\bf (1) Motivate the need of KBs (structured vs. unstructured data; semantic web)} \\

  \noindent\TODO{\bf (2) Give a very fundamental introduction into knowledge graphs:} \\
  Most generally, a knowledge graph (\emph{KB}\,) is a collection of statements that provide any kind of ``knowledge'' about the real world.
  Each statement can either describe a single property of a specific \emph{entity} (for example: a human, an object, an event, a concept) or any relation between two entities.
  By convention, the statements are often stored in the form of \emph{subject}, \emph{predicate}, \emph{object} (SPO) triples as shown in the following (minimalistic and simplified) example KB:

  \begin{kb}
    \iri{\merylstreep}   \> \iri{instance of} \> \iri{Person} . \\
    \iri{\merylstreep}   \> \iri{instance of} \> \iri{Person} . \\
    \iri{\merylstreep}   \> \iri{gender}      \> \iri{Female} . \\
    \iri{\merylstreep}   \> \iri{birthday}    \> "22 June 1949" . \\
    \iri{\merylstreep}   \> \iri{won award}   \> \iri{Oscar for Best Actress} . \\
    %\iri{\merylstreep}   \> \iri{won award}   \> $<$Honorary César$>$ \\
    \iri{\bongjoon}   \> \iri{won award}   \> \iri{Oscar for Best Film} . \\
    % $<$Meryl\_Streep$>$   \> $<$won-award$>$   \> $<$Oscar Best S. Actress$>$ \\
    \iri{Oscar for Best Actress} \> \iri{instance of} \> \iri{Oscar} . \\
    \iri{Oscar for Best Film}    \> \iri{instance of} \> \iri{Oscar}
    % $<$Oscar Best S. Actress$>$ \> $<$instance-of$>$ \> \iri{Academy Award}
  \end{kb}

  \noindent\TODO{\bf (3) Explain the above example KB in more detail:}
  \begin{itemize}
    \item The format we just used is (a simplified version of) the \emph{N-Triples} format that is basically a list of SPO-triples, separated by dots.
          We will introduce this format together with other commonly used formats in more detail further below.
    \item The subject of each triple must be an entity.
    \item The entities are surrounded by angle brackets (e.g., \emph{\iri{\merylstreep}}).
    \item The predicates are also called \emph{properties} or \emph{relations}. \\
          \TODO{In the above example KB, the relations are also written in $<$...$>$ (just like the entities). Should we consider the relations as entities?}
    \item The object of each triple must be an entity or a value literal (e.g., \emph{"22 June 1949"}). \\
          \TODO{Many publications don't distinguish between entities and literals. Should we?}
    \item The format for knowledge graphs is standardized by the \emph{Resource Description Framework} (RDF) standard. \\
          \TODO{Should we introduce the RDF standard in more detail? If so, on which level of detail?}
  \end{itemize}

  \noindent\TODO{\bf (4) Explain the (slightly more complicated) format of real-life KBs:}
  \begin{itemize}
    \item In real-life KBs, the entities are often represented by Uniform Resource Identifiers (URIs).
    \item Reason: URIs make it possible to uniquely identify entities across all KBs of the world.
    \item Give an example, how a real-life KB looks like.
    \item Stress that we will continue to use the simplistic format throughout this proposal.
  \end{itemize}

  \noindent\TODO{\bf (5) Explain the importance of consistent data in KBs:}
  \begin{itemize}
    \item It is crucial that the same entity or relation has the same name (id) in different statements.
    \item It is also crucial that, when items were deleted, their ids are never reused.
    \item By the consistent use of identifiers we can easily derive information like a list of \emph{all female actors who won an Oscar}.
    \item Such queries can be formulated using an appropriate query language. Point to the section about query languages.
    \item Introduce possible applications, for example:
          \begin{itemize}
            \item \emph{Logical Reasoning:} Information about general relationships is used to derive additional facts: For example: a property “grandfather” can be obsolete, since its value can be inferred from values of properties father and mother.
            \item \emph{Statistical Evaluation}, e.g., average ages of german scientists, gender balance of persons with Wikipedia articles, etc.
          \end{itemize}
  \end{itemize}

  \noindent\TODO{\bf (6) Explain graph representations of KBs}
  \begin{itemize}
    \item knowledge graphs can also be thought of as (directed) graphs, where the nodes are the entities and the literals (or: the subjects and objects), and the edges are the predicates.
    \item Give an example showing the above example KB as a directed graph.
  \end{itemize}

  % ===============================================================================================

  \section{Additional Notes on DBpedia}

  \subsection{General Approach}

  \noindent\emph{DBpedia} automatically extracts (semi-)structured data from different Wikimedia projects (including the different language editions of \emph{Wikipedia}, \emph{Wikimedia Commons} and Wikidata) and provides it in a single, consistent and crowdsourced OWL-based ontology.
  To homogenize the extracted data and map them to its ontology, \emph{DBpedia} uses community-edited \emph{mappings}\footnote{\url{http://mappings.dbpedia.org}}.

  From Wikidata, \emph{DBpedia} contains all data which could be successfully mapped to the \emph{DBpedia} ontology.
  From \emph{Wikipedia}, \emph{DBpedia} extracts:
  \emph{labels} (= the name / title of an article);
  \emph{abstracts} (= the first paragraph of an article);
  \emph{full texts};
  \emph{infoboxes} (Note: meanwhile, many infoboxes come directly from Wikidata);
  \emph{internal and external links};
  \emph{geographic coordinates};
  \emph{categories};
  \emph{images} (the first image of each article);
  \emph{citations};
  \emph{genders} of persons (by counting gender-specific pronouns). \\[-5pt]

  \subsection{How the mapping between DBpedia and Wikipedia works}
  \begin{itemize}
    \item \emph{DBpedia} particularly extracts data from infoboxes of Wikipedia articles.
          An infobox contains data in key/value pair form, see the infobox of \emph{Tom Hanks} for an example: \url{https://en.wikipedia.org/wiki/Tom_Hanks}.
          See in particular how the infobox is defined in the \emph{Wikipedia} markup: \url{https://en.wikipedia.org/w/index.php?title=Tom_Hanks&action=edit}
    \item An infobox has a specific \emph{template type}, for example: \emph{person}. The template definition can be found here: \url{https://en.wikipedia.org/wiki/Template:Infobox_person}.
    \item For (almost) each template type, there is a (crowdsourced) \emph{DBpedia} mapping which specifies how to map the data contained in an infobox to the \emph{DBpedia} ontology.
          For example, an excerpt from the mapping for the template type \emph{person} looks as follows:
          \begin{sparql}
            \{\{TemplateMapping \\
            \;| mapToClass = Person \\
            \;| mappings = \\
            \;\;\;\{\{PropertyMapping | templateProperty = name | ontologyProperty = foaf:name \}\} \\
            \;\;\;\{\{PropertyMapping | templateProperty = birthdate | ontologyProperty = birthDate \}\} \\
            \;\;\;\{\{PropertyMapping | templateProperty = birth\_date | ontologyProperty = birthDate \}\} \\
            \}\}
          \end{sparql}
          The full mapping definition can be found here: \url{http://mappings.dbpedia.org/index.php/Mapping_en:Infobox_person}.
    \item \emph{mapToClass} denotes the \emph{DBpedia} class to which the entity should be mapped (\emph{Person} in the example above).
          The full definition of the class \emph{Person} can be found here: \url{http://mappings.dbpedia.org/index.php/OntologyClass:Person}.
    \item \emph{templateProperty} denotes the identifier used for a property in the Wikidata markup.
          Note that, in principle, there could be different mappings for the same \emph{ontologyProperty}, because occasionally, different identifiers for the same property are used in Wikipedia (see \emph{birthdate} vs. \emph{birth\_date} in the example above).
    \item \emph{ontologyProperty} denotes the corresponding identifier in the \emph{DBpedia} ontology.
          For example, the definition of the ontologyProperty \emph{birthDate} can be found here: \url{http://mappings.dbpedia.org/index.php/OntologyProperty:BirthDate}
    \item To understand how the data are exactly extracted to \emph{RDF triples}, consider the infobox of \emph{Tom Hanks} again, and in particular the entries \emph{name} and
          \emph{birth\_date}.
          The entity representing \emph{Tom Hanks} is identified via the URI \url{http://dbpedia.org/resource/Tom_Hanks} (the \emph{Tom\_Hanks} part is simply the title of the Wikipedia article).
          The entity is mapped to class \url{http://dbpedia.org/ontology/Person} (due to \emph{mapToClass = Person}), the property \emph{name} to \url{http://xmlns.com/foaf/0.1/name} (due to \emph{ontologyProperty = foaf:name}), and \emph{birth\_date} to \url{http://dbpedia.org/ontology/birthDate} (due to \emph{ontologyProperty = birthDate}).
          So the created \emph{RDF triples} are:
          \begin{tabbing}
            dbr:Tom\_Hanks \;\;\= rdf:type \qquad\quad\= dbo:Person \\
            dbr:Tom\_Hanks     \> foaf:name           \> "Tom\ Hanks" \\
            dbr:Tom\_Hanks     \> dbo:birthDate       \> "1956-07-09"
          \end{tabbing}
          An overview of all extracted triples can be found here: \url{http://dbpedia.org/page/Tom_Hanks}.
    \item There is also a concept called \emph{Intermediate Nodes} which is used to add contextual information to facts.
          The URI format of an intermediate node is "\emph{<entity-uri>\_\_\iri{int}}" where \emph{<entity-uri>} is the URI of the belonging entity and \emph{\iri{int}} is a sequential number.
          For an example, consider the following facts:
          \begin{tabbing}
            dbr:Tom\_Hanks \qquad\= dbo:occupation \qquad\qquad\= dbr:Tom\_Hanks\_\_1 \\
            dbr:Tom\_Hanks\_\_1  \> dbo:title                  \> "Actor, filmmaker"@en \\
            dbr:Tom\_Hanks\_\_1  \> dbo:functionStartYear   \> "1977"
          \end{tabbing}
          Note the "\emph{dbr:Tom\_Hanks\_\_1}" which is the URI of an intermediate node used to give contextual information about the occupation of Tom Hanks (the job title and the start year).
          \TODO{\textbf{Note:} The last fact is \textbf{not} an actual part of DBpedia and was added to the above example for illustration purposes only.
            Im not sure why this fact is missing in DBpedia, especially because this piece of information (the start year) is clearly included in the infobox of Tom Hanks' Wikipedia page.
            Obviously, the mapping of this information doesn't work perfectly well (although the corresponding mapping specification defines a special \emph{IntermediateNodeMapping}, see \url{http://mappings.dbpedia.org/index.php?title=Mapping_en:Infobox_person&action=edit}).}
    \item The full \emph{DBpedia} ontology can be found here: \url{http://mappings.dbpedia.org/server/ontology/classes/}
  \end{itemize}

  \subsection{How the mapping between DBpedia and Wikidata works}
  \begin{itemize}
    \item Each Wikidata item \emph{Qx} is identified by URI <\url{http://wikidata.dbpedia.org/resource/Qx}>.
    \item Properties and classes are mapped using the same mapping techniques described above.
    \item An \emph{ontologyClass} can have an \emph{owl:equivalentClass} entry which specifies the relating class in Wikidata, for example:
          \url{http://mappings.dbpedia.org/index.php/OntologyClass:Person}
    \item An \emph{ontologyProperty} can have an \emph{owl:equivalentProperty} entry, specifying the relating property in Wikidata; for example:
          \url{http://mappings.dbpedia.org/index.php/OntologyProperty:birthDate}.
    \item Note that a class and a property don't necessarily have to have an \emph{owl:equivalentClass} resp. \emph{owl:equivalentProperty} entry (if for example there is no equivalent thing in Wikidata). An example property that doesn't have an \emph{owl:equivalentProperty} entry is: \url{http://mappings.dbpedia.org/index.php/OntologyProperty:Age} (there is indeed no property in Wikidata referring to the age of a human).
    \item \emph{Reification}: For a Wikidata statement "\emph{wd:Qx wdt:Py wd:Qz}", $n$-ary relations are modelled by introducing extra \emph{reified} statements, with a subject identified by an URI of form \emph{dw:Qx\_Py\_Qz}. Here is an example for statement \emph{wd:Q42 wdt:P26 wd:Q14} (DBpedia doesn't provide precision):
          \begin{tabbing}
            dw:Q42\_P26\_Q14 \;\;\= rdf:type \;\;\;\;\;\;\;\;\;\;\= rdf:Statement . \\
            dw:Q42\_P26\_Q14 \> rdf:subject \> dw:Q42 . \\
            dw:Q42\_P26\_Q14 \> rdf:predicate \> dbo:spouse . \\
            dw:Q42\_P26\_Q14 \> rdf:object \> dw:Q14 . \\
            dw:Q42\_P26\_Q14 \> dbo:startDate \> "1991-11-25"\^{}\^{}xsd:date . \\
            dw:Q42\_P26\_Q14 \> dbo:endDate \> "2001-5-11"\^{}\^{}xsd:date .
          \end{tabbing}
          For a Wikidata statement "\emph{wd:Qx\; wdt:Py\; Lz}" (with literal \emph{Lz}), the subject URIs are of form \emph{dw:Qx\_Py\_H(Lz, 5)}, where \emph{H()} is a hash function that maps the literal to a hash of length 5.
  \end{itemize}

  \subsection{Similarities between DBpedia and Wikidata}
  \begin{itemize}
    \item Both schemas are crowdsourced and multilingual.
    \item Both projects provide RDF dumps and a SPARQL endpoint.
  \end{itemize}

  \subsection{Differences between DBpedia and Wikidata}
  \begin{itemize}
    \item The direction of information flow: DBpedia extracts data from Wikipedia and Wikidata; Wikidata provides data to Wikipedia.
    \item DBpedia uses human-readable identifiers; Wikidata uses numeric identifiers.
    \item DBpedia uses a standardized ontology (based on OWL); Wikidata uses a custom ontology.
    \item DBpedia is read-only (the data are extracted automatically); Wikidata is read+write.
    \item DBpedia releases are updated periodically (e.g., monthly); Wikidata changes can be seen instantly.
          \emph{Note:} There is also a "\emph{DBpedia live}" project (started in 2009) running on the dataset of the English, French and German Wikipedia, which is updated whenever an Wikipedia
          article was updated (this is implemented by using the \emph{Recent changes stream} provided by Wikipedia, which broadcasts all changes to the public immediately).
  \end{itemize}

  \subsection{DBpedia vs. Wikidata}
  DBpedia sees itself as a pioneer in adopting and creating best practices for Linked Data and RDF publishing.
  There is a large community using and maintaining DBpedia, and there exist many tools designed to consume the DBpedia ontology.
  Integrating Wikidata into DBpedia has the advantages that
  (1) these tools are now able to consume DBpedia + Wikidata simultaneously "out of the box" and
  (2) the community is able to browse Wikidata by using "familiar querying".
  Further, Wikidata would now have an additional data distribution channel.

  The fact that Wikidata is more and more replacing the infoboxes in Wikipedia seems to be very appreciated, because it is seen as a great chance for DBpedia to innovate as it frees up resource previously bound to scraping the infoboxes (which is a effortful and error-prone task).
  One future goal is to extend the DBpedia dataset with more detailed data extracted from Wikipedia articles (e.g., citations and \TODO{tables?}) and to provide these data also to Wikidata and the public.
  Extracting citations would be a particular important task, because Wikidata editors often copy facts from Wikipedia -- but with citing Wikipedia as the source instead of the external or authoritative source that is actually cited in the Wikipedia article.

  \subsection{FAQ}
  \begin{enumerate}
    \item {\bfseries What are the \emph{Extraction Groups} of DBpedia and how do they differ?} \\
    The data of DBpedia is split into the following groups: \\
    \emph{(a) Generic}: contains data extracted from Wikipedia using \emph{generic} parsers. These parsers particularly parse the infoboxes "as they are", i.e.: they use the name of a infobox attribute as predicate as it is and the value of an attribute as object. The issue is that, for example, synonyms like \emph{birthplace} and \emph{place of birth} are seen as two different predicates. \\
    \emph{(b) Mappings}: contains data extracted by parsers using the mappings specified by the community. These mappings define, for example, which attribute names should be mapped to which predicate in the ontology. The data in this group is cleaner and better structured than in the \emph{Generic} group. \\
    \emph{(c) Text}: contains the abstracts and full texts \\
    \emph{(d) Wikidata}: contains the mapped and cleaned Wikidata data. \\[1pt]

    \item {Why is the number of triples, which is reported in the \emph{SPARQL} endpoint (\url{https://dbpedia.org/sparql}) for the query "\emph{SELECT (COUNT(*) as ?count) WHERE \{ ?s ?p ?o \}}" much smaller (438,336,271) than the number reported at the DBpedia homepage (3B)?}
    The SPARQL endpoint contains only the core dataset of DBpedia, a small subset of the groups described above (approx. 100 of 4000 files or 2.5\%)
    (Source: \url{https://wiki.dbpedia.org/develop/datasets/latest-core-dataset-releases}).
    The core dataset focuses on English language. It is constantly improved and extended by hand. The concrete content can be found here: \url{https://databus.dbpedia.org/dbpedia/collections/latest-core}
  \end{enumerate}

  \subsection{BabelNet}
  BabelNet is a encyclopedic dictionary founded at the Sapienza University of Rome.
  It provides multilingual \emph{synsets}, covering 284 languages.
  Each synset represents a given meaning and contains all synonyms which express that meaning in a range of different languages.
  The synsets were obtained from the automatic integration of external datasets, like \emph{WordNet}, \emph{Wikipedia}, \emph{Wikidata}, \emph{GeoNames}, etc.

  \subsection{GeoNames}
  \emph{GeoNames} is an open, user editable geographical database founded by Marc Wick in 2005.
  It contains more than 25 million names of countries, cities, geographical locations, landmarks, POIs, etc. in various languages.
  Besides the names, GeoNames can also store the latitude, longitude, elevation, population and postal codes of the locations.

  \subsection{SciGraph}
  \emph{SciGraph} is an open knowledge graph published by \emph{Springer Nature} in 2017.
  It contains 1.5 billion triples with information about the research landscape around \emph{Springer Nature}, including: funders, research projects, conferences, affiliations and publications.

  \subsection{Microsoft Academic Graph / Microsoft Academic Knowledge Graph.}
  \emph{Microsoft Academic Graph} (MAG) is a knowledge graph containing triples with information about scientific publications and their authors, institutions, journals, conferences and field of study.
  It was founded by \emph{Microsoft} in June 2015 and is used in services like \emph{Bing}, \emph{Cortana}, \emph{Word} and \emph{Microsoft Word}.
  Contrarily to what the word ``graph'' suggests, \emph{Microsoft} does not provide the data in the form of a (knowledge) graph.
  Michael Färber introduced the \emph{Microsoft Academic Knowledge Graph} project in 2019 in order address this issue.
  His knowlegde base contains 8B triples with information about 210M scientific publications, authors, institutions, journals, and fields of study, taken from MAG. \\

  \subsection{Other noteworthy KBs/systems:}
  \TODO{\emph{Doremus} (music catalogs), \emph{LinkedGeoData} (geodata), \emph{OpenCitations} (bibliographic citations), \emph{DDBJ} (life sciences), \emph{NBDC RDF Portal} (collection of 26 life science datasets, for example: PubChem, UniProt),\emph{NELL}, \emph{data.gov} (open data portal of the U.S. government), \emph{Source Code Ecosystem} (open source coding project), \emph{Open Library} (library catalog)}


  \section{Data Formats (Preliminary Notes)}

  \vspace{1mm}\noindent\TODO{\bf (1) Introduce the different data formats (each with a meaningful example):}
  \begin{itemize}
    \item \textbf{N-triples:} the triples are stored in a text file, with a space between subject, predicate, and object, and a simple dot to separate triples (usually one triple per line).
    \item \textbf{N-quads:} like N-triples, but with one additional field per triple that provides an arbitrary context value (e.g., the source of the triple).
    \item \textbf{TSV:} one triple or quad per line, with the three or four components separated by a tab. TSV is an abbreviation for tab-separated values.
    \item \textbf{Turtle:} allows an explicit nested representation. Depending on the data, this can be more convenient for reading and producing than mere triples or quads.
          The price is a more complex format that requires more complex parsers. \\
          \TODO{Introduce prefix directives}
  \end{itemize}

  \section{Gremlin (Apache TinkerPop) (Preliminary Notes) }

  Gremlin is a graph traversal language.
  It was developed in 2009 by Apache TinkerPop.
  Gremlin is a very expressive, Turing-complete language.

  % "Apache TinkerPop and Gremlin are to graph databases what the JDBC and SQL are to relational databases. Likewise, the Gremlin traversal machine is to graph computing as what the Java virtual machine is to general purpose computing."

  % SPARQL: Graph pattern matching vs. Gremlin: functional/traversal matching

  Similar to Cypher, it organizes data in nodes and directed edges and distinguishes between ``relationships'', ``properties'' and ``labels''.
  However, the syntax of how to define and query (or \textit{traverse}) a graph differs from Cypher.
  Gremlin uses \textit{traversal steps}, instructions about how to traverse the graph (navigation instructions).
  We will discuss them in detail below after we have created a graph.
  Again, we will consider the example KG from Section \TODO{?}.
  Gremlin has bindings in many programming languages.
  The most used language is Apache Groovy.
  First of all, we need to create a graph and a traversal source:
\begin{sparql}
  $graph = TinkerGraph.open()$\\
  $g = graph.traversal()$
\end{sparql}
  The traversal source ($g$) is a beginning of the traversal that knows the graph and how to interpret and execute the traversal steps.

\begin{sparql}
  $\left.\begin{tabular}{l}
      Vertex P1 = graph.addVertex(``Person'') \\
      Vertex P2 = graph.addVertex(``Person'') \\
      Vertex O1 = graph.addVertex(``Oscar'')  \\
      Vertex O2 = graph.addVertex(``Oscar'')
    \end{tabular}\right\}$ Vertices/Nodes/Entities initialized with a label \\
  $\left.\begin{tabular}{l}
      Edge W1 = P1.addEdge(``won award'', O1) \\
      P2.addEdge(``won award'', O2)
    \end{tabular}\right\}$ Edges/Relationships \\
  $\left.\begin{tabular}{l}
      P1.property(``name'', ``Meryl Streep'')           \\
      P1.property(``bithday'', ``22 June 1949'')        \\
      P1.property(``gender'', ``female'')               \\
      P2.property(``name'', ``Bong Joon-ho'')           \\
      O1.property(``name'', ``Oscar for Best Actress'') \\
      O2.property(``name'', ``Oscar for Best Film'')    \\
      W1.property(``year'', ``1983'')                   \\
      W1.property(``film'', ``Sophie's Choice'')
    \end{tabular}\right\}$ Properties
\end{sparql}

  Note that there is no need to introduce a variable for the relationship between \emph{P2} and \emph{O2}, since this edge will not get additional properties.


\begin{sparql}
  g.V().match( \\
  \> as("entity").label().is("Person"), \\
  \> as("entity").out("gender").is("female"), \\
  \> as("entity").out("won award").is("award"),\\
  \> as("award").label().is("Oscar") ). \\
  \> \> select("a", "b", "c")
\end{sparql}

\end{appendix}

\end{document}
