Because of the flexibility and expressiveness of their model, Knowledge Graphs (KGs) have received increasing interest. These resources are usually represented in RDF and stored in specialized data management systems called triplestores. Yet, while there exists a multitude of such systems, exploiting varying data representation and indexing schemes, it is unclear which of the many design choices are the most efective for a given database and query workload. Thus, first, we introduce a set of 20 access patterns, which we identify within 6 categories, adopted to analyze the needs of a given query workload. Then, we identify a novel three-dimensional design space for RDF data representations built on the dimensions of subdivision, redundancy, and compression of data. This design space maps the trade-ofs between diferent RDF data representations employed to store RDF data within a triplestore. Thus, each of the required access patterns is compared against its compatibility with a given data representation. As we show, this approach allows identifying both the most efective RDF data representation for a given query workload as well as unexplored design solutions.
Knowledge Graphs (KGs) are nowadays already in widespread use because of their ability to
represent entities and their relationships in many domains [
The RDF data model revolves around the concepts of RDF triples and RDF graph patterns. An
RDF triple, which corresponds to an edge in the graph, is a factual statement consisting of a
subject (), a predicate (), and an object (). Subjects and objects, which represent nodes, can
be resources identified by International Resource Identifiers (IRI), anonymous nodes identified
by internal IDs (called blank nodes), or literals (which can appear only as objects). Thus, an
RDF graph is a set of RDF triples. An RDF graph is queried by issuing a SPARQL query whose
answers are computed based on the subgraphs matching the structural and logical constraints
it prescribes. SPARQL queries contain one or more basic graph patterns (BGPs), which are sets
of triples with zero or more of their components replaced with variables from an infinite set
of variables . Thus, triple patterns are (, , ) triples, where any position may be replaced
by a variable ∈ . We refer to each value in each position as an atom. Moreover, there are
special types of patterns that match pairs of atoms connected through sequences of edges
satisfying a specific set of predicates, e.g., all nodes connected by an arbitrary sequence of edges
with ex:childOf predicates. These patterns are called property paths. They are defined via a
specialized form of expressions called path expressions (similar to regular expressions) and ofer
a succinct way to extend matching of triple patterns to paths of arbitrary length [
FILTER(DATATYPE(?date) = xsd:dateTime).
FILTER(?date <= 2019-12-31 && ?date > 2019-12-01).
FILTER(LANG(?eventLabel) = "en").
Return Values Constants PO Constants P Range Closed Range Special Pivot N-way S≡S ★ 1-hop SàO ★ 1-hop OàS ✪ SàP*àO } Figure 1: SPARQL query with annotated access patterns. solutions of a query are the variables bindings, i.e., the mappings from each variable to a given node or edge in the graph that satisfies the conditions in the BGP.
In its simplest form, a SPARQL query has the form “SELECT ⃗ WHERE ”, with = {1, ... , } being a set of triple patterns (as in Figure 1, the annotations are explained in the next section). Optionally, one or more FILTER clauses further constrain the variables in . Let denote the finite set of variables occurring in , i.e., ⊂ , then ⃗ is the vector of variables returned by the query such that ⃗ ⊆ . Additional operators such as UNION or OPTIONAL allow more than one BGP in a query by defining the non-conjunctive semantics of their combination. Finally, SPARQL queries can also make use of GROUP BY and aggregate operators. SPARQL queries are declarative and are therefore designed to be decoupled from the physical data access methods, i.e., the low-level algorithms and data structures for organizing and accessing data. This decoupling allows specific triplestore implementations to use diferent data representations and query processing techniques to execute a given query.
To identify the best internal representation for an RDF dataset and a given SPARQL query, we decompose the query’s triple patterns into atomic operators and identify how they access a given data representation. In particular, we identify a set of access patterns that enable the required translation from the declarative query language to its logical query plan. Thus, an access pattern is the set of logical operations that, given a set of variable bindings over a graph, determine what data to access (and optionally to change) and what output to produce. The feature space of access patterns (summarized in Table 1) is comprised of 6 dimensions, each containing a set of alternative features, namely: Constants, the presence of constant values as atoms (instead of variables); Filter, the presence (or absence) of a filter on a range of values; Traversal, the connection of two nodes by means of one or more subsequent triple patterns; Pivot, the atom connecting multiple triple patterns in a BGP; Return, the information expected to be returned; Write, whether and how a change in the content of the graph is needed. Consider the example in Figure 1, representing a query to retrieve location coordinates of archaeological sites, and compare it to the access patterns in Table 1. We can recognize, for instance, the property path wdt:P31/wdt:P279*, of the form p1/p2* o, meaning that it would match two alternative access patterns: (1) 1-hop traversals over p1 = wdt:P31 reaching the target node o=wd:Q1190554 directly, and (2) *-hop traversals starting with one edge for wdt:P31 and reaching the object through a sequence of arbitrarily long paths matching the p2 = wdt:P279 triple pattern. On the other hand, the ?event variable is a 3-way pivot, which can also be executed as a set of binary ≡ pivot access patterns. Similarly, we can also identify range filters and the presence of constant values. Each of these access patterns can be efectively implemented and answered by specific RDF data representations and indexes.
To support the data access patterns, triplestores implement a set of diferent data representations storing all or a subset of the graph . A data representation to answer the given access pattern needs to provide a way to retrieve the values for the bindings of the variables ⃗ from the information stored in (or to modify for write operations). Therefore, given an access pattern and a data representation of , we evaluate the performance of in providing the correct instantiations of ⃗ for . Moreover, we also evaluate how efective, in terms of time, it is to execute over , i.e., its cost. Answering such a question allows, given two distinct data representations, to select the most appropriate one, i.e., the one with the lowest cost.
Cost model. Answering a query using a particular data representation incurs a cost expressed
in terms of the time it takes to retrieve all such answers. Several such cost models have
been proposed for RDF [
?s ?p ?o <uri1> <p1> <o1> <uri1> <p2> <o2> <uri2> <p1> <o3> <uri2> <p3> <o4> <uri3> <p1> <o1> <uri4> <p2> <o5> . . . . . . . . . <uri22> <p1> <o14> <uri22> <p3> <o15> b)
?s
<uri1>
<uri2>
<uri3>
<uri4>
. . .
<uri22>
<p1>,<o1> <p2>,<o2>
<p1>,<o3> <p3>,<o4>
<p1>,<o1>
<p2>,<o5>
set of cost constants [
Data Representation Compatibility. To assess if a data representation can eficiently support a specific access pattern, we define the notion of compatibility. We define this notion specifically for read operations, under the assumption that a read operation is required before deletion (to locate the data to be deleted) and before insertion (to locate where to insert the data and to avoid duplicates) and is therefore required for every type of access pattern. Therefore, given an access pattern and a data representation able to answer , we assume that there is a sequence of operations specified by an algorithm Γ defined over that can compute an answer , such that = Γ(, ). The number and cost of the operations specified by Γ directly determine whether is a representation suitable for eficiently computing the answers to . When measuring the number of operations required to be executed over , we distinguish between random seek and sequential operations. In particular, an RDF data representation can be seek compatible, sequence compatible, or selection compatible.
For instance, one way to store is as a list of 3-tuples (one per edge) sorted by subject and then by predicate and object (Figure 2.a and 2.d) with a clustered B+ tree index over them. In this representation, the query processing cost would be analogous to that of a relational table with three attributes (, , ), all part of a primary index. This representation is sequence compatible with any 1-hop access pattern that binds , both and , or all three positions. That is, the algorithm Γ(⟨s1,p1,?o⟩, {B+tree,sorted()}), would first find the first tuple performing () steps traversing the B+ tree looking for s1, p1, and then perform a linear scan over the file to retrieve the remaining tuples. However, the B+ tree is not seek compatible because the time to ifnd the first result depends on the size of the graph, i.e., it involves (||) seek operations to reach the first result. A diferent data representation is to employ a key-value data structure (similar to Figure 2b) and use the pair subject-predicate as the key, and the object as the value. In this data structure, triples sharing the same and will store the list of objects contiguously. This data structure is both seek and sequence compatible for a traversal that, given and , retrieves all corresponding objects. Nevertheless, this representation is neither seek compatible nor sequence compatible if the query requires all edges for predicate regardless of . Thus, the definitions of cost and compatibility presented above allow analyzing the advantages and drawbacks of the diferent choices in each dimension of the design space.
The Design Space Dimensions. When designing data representations for an RDF store, one can model the design decisions over three axes: Subdivision, Compression, and Redundancy. Each of these orthogonal axes, whose properties are summarized in Table 2, represents a continuum along which the data representation adopted by a system can be positioned.
The Subdivision axis determines how fragmented the data is. At one extreme, all data is stored contiguously in a single structure; at the other extreme, each edge and node is stored as a separate object with pointers to its neighbors. In between, there are various data structures such as B+ trees or hash maps. This axis contains design decisions such as sorting, grouping, and hashing. Each of these decisions creates an additional subdivision in the data. Increasing the extent of subdivision, allows us to minimize the number of unneeded data items accessed to answer an access pattern (resulting in fewer operations that return items not in the result set). For instance, in a sorted file (Figure 2a), the sorting keys act as the simplest subdivision by collecting all triples with the same value together. On the other hand, with a hash table (Figure 2b), given the target IRI, the hash function separates all relevant triples sharing the same key. Therefore, decisions across the subdivision axis easily determine whether a data structure is selection compatible, i.e., if it binds all and only the answers within a specific subdivision, but it also impacts random and sequence compatibility.
The goal of Compression is to minimize the number of bits read to reach the first tuple in the
result set and the number of bits required to read and potentially store the result set for further
processing. The potentially negative impact of compression is, of course, the decompression
required to evaluate a predicate in the access pattern if the access pattern is incompatible or
partially incompatible. For example, consider a compressed data representation tuned for queries
of the form (, ?, ?) and ≡ access patterns (e.g., BitMat [
The third axis is Redundancy which causes (redundant) copies of the data to be stored in the system. By adding redundant data representations and indexes, it is possible to define ideal (seek, sequence, and selection compatible) data representations for each access pattern. However, this comes at the cost of having to store the same information multiple times. For example, by holding both an SPO clustered index and a PSO clustered index, each triple is stored twice. Thus, this hinders the compatibility with write access patterns. Moreover, design decisions including full/partial replication need to find a trade-of between storage space and eficient support of query access patterns. Hence, the cost of maintaining multiple representations is three-fold: (i) Increased latency for delete and insert operations with possibly reduced performance of read operations as well. (ii) An increase in space requirements, subsequently straining the limited space in main memory and causing an increase in all read costs. (iii) An increase in query optimization time because alternative structures to access the data result in a higher number of query execution plans that have to be considered.
Thanks to the feature space for analyzing query workload access patterns, and the
SubdivisionCompression-Redundancy (SCR) design space of data representations for RDF databases, we
enable the analysis of RDF store design decisions, specifically, which data representations can
efectively support a given workload. Previous workload analyses are centered around those
characteristics that would impact mainly the query optimizer. Instead, we present an analysis
of the access patterns specific to the storage layer . The efect of various choices along the three
axes is summarized in Table 2. We performed an analysis of popular RDF store benchmarks
under these assumptions and identified a number of workload requirements for which systems
rarely provide efective optimizations. Considering the Subdivision dimension, many systems
implement dedicated tables for triples sharing a specific predicate. Alternatively, queries that
match triples with the same subject can usually exploit the clustered representation where
several properties for the same subject (or object) are stored together in a single row [
Thus, researchers can use the SCR design space to design novel solutions in an informed
manner. Such designs can be achieved either manually or even semi-automatically as proposed
by the recent efort in self-designing data structures [
This research is supported by the European Union H2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No 838216 and the Poul Due Jensen Foundation.