5.3. Background and preliminaries
In this section, we provide basic definitions on the interplay between RDF and its multigraph representation. Later, we explain how the task of answering SPARQL queries can be reduced to a multigraph homomorphism problem.
5.3.1. RDF data
According to the W3C standards3, RDF data are represented as a set of triples <S,P,O>, as shown in Figure 5.1(a), where each triple <s,p,o> consists of the following three components: a subject, a predicate and an object. Further, each component of the RDF triple can be either of the two forms: an IRI (Internationalized Resource Identifier) or a literal. For brevity, an IRI is usually written with a prefix (e.g. <http://dbpedia.org/resource/isPartOf> is written as “x:isPartOf”), whereas a literal is always written with double quotes (e.g. “90000”). While a subject s and a predicate p are always an IRI, an object o can be either an IRI or a literal.
RDF data can also be represented...
