e upcoming RDF 1.2 recommendation is scheduled to introduce the concept of quoted triples, which allows statements to be made about other statements. Since quoted triples enable new forms of data access in SPARQL 1.2, in the form of quoted triple paerns, there is a need for new indexing strategies that can efficiently handle these data access paerns. As such, we explore and evaluate different in-memory indexing approaches for quoted triples. In this paper, we investigate four indexing approaches, and evaluate their performance over an artificial dataset with custom triple paern queries. Our findings show that the so-called indexed quoted triples dictionary vastly outperforms other approaches in terms of query execution time at the cost of increased storage size and ingestion time. Our work shows that indexing quoted triples in a dictionary separate from non-quoted RDF terms achieves good performance, and can be implemented using well-known indexing techniques into existing systems. erefore, we illustrate that the addition of quoted triples into the RDF stack can be achieved in a performant manner.
triples in their triplestore, and enable queryable access using SPARQL. Even though some approaches offer reports of their systems passing RDF-star specification tests, and provide high-level documenta‐ tion explaining the concepts of quoted triples for end-users, none of them offer detailed descriptions of their indexing approach, or query performance evaluations over them. As such, there is an open knowl‐ edge gap on the research question “How to index quoted triples, and what is the impact on ingestion, storage, and query performance?”.
To fill this gap, we explore four different indexing approaches, implement them in a single system for
fair comparison, and evaluate them in terms of ingestion time, storage size, and query performance. We
focus on in-memory indexing, but approaches are generalizable to mixed disk/memory approaches such
as HDT [
Given the recent introduction of RDF-star and the concept of quoted triples, scientific literature on
making use of it is limited. First, several use cases [6, 7] have been explored using quoted triples.
Furthermore, a declarative language called RML-star [
RDF-star is seeing wide adoption among SPARQL implementations, for which a full list of implemen‐
tations that adhere to the RDF-star community group specification can be found in [
Indexing is an important and well-understood element of RDF storage systems and SPARQL query
engines, where it provides a trade-off between query execution time, storage space, and ingestion time.
Existing approaches are either based on existing database technologies, such as relational
databases [
A first important concept in RDF indexing is the storage of triples in different orders [
A second important aspect in RDF indexing is the encoding of RDF terms using dictionaries. e main purposes of dictionary-encoding are the reduction in storage overhead if RDF terms are reused across multiple triples inside indexes, and more efficient comparison of RDF terms during query pro‐ cessing. e dictionary itself is a datastructure that maintains a bidirectional mapping of RDF terms to their encodings. Instead of storing RDF terms directly inside indexes, terms are first encoded into a more compact datatype, such as an integer, which is then stored inside the index instead. At query time, non-variable triple paern terms can also be encoded, and queried inside the index. When returning query results, encoded triples can be decoded using the dictionary.
Fig. 1 shows an illustration of the typical components of a triplestore. is example store contains three indexes, with triples stored in SPO, POS, and OSP orders in tree-like structure. ese indexes make use of a single shared dictionary, which encodes the RDF terms inside all RDF triples stored by the indexes.
To simplify discussions involving triple paern queries, we outline a traditional high-level query exe‐ cution approach for triple paern queries in Algorithm 1, Algorithm 2, and Algorithm 3. As shown in Algorithm 1, the first step involves determining the most suitable index for a given triple paern query. For example, a ??O query can be answered most efficiently using the OSP index, because O can be select‐ ed in constant time from the root of the tree. e triple paern query is then delegated to the index, which is executed according to Algorithm 2. In this step, we recursively drill down into the tree-like in‐ dex by iterating over all matching terms of each triple paern component. e algorithm for finding all matches for a single triple paern component is shown in Algorithm 3, which either returns all terms in this part of the index if the term is a variable, or returns the term itself if the term is inside the index if the term is not a variable. We will replace parts of these algorithms when introducing our quoted triples indexing approaches in Section 5.
FUNCTION QueryStore(store, tp)
INPUT: store: triple store tp: triple pattern OUTPUT:
ts: sequence of triples idx = most suitable index from store.indexes ts = QueryIndex(idx, store.dict, tp) RETURN ts
Algorithm 1: Pseudocode for executing a triple pattern query over a triplestore containing one or more indexes.
FUNCTION QueryIndex(idx, dict, tp)
INPUT: idx: triple pattern index dict: dictionary tp: triple pattern OUTPUT:
ts: sequence of triples tpe = dict.encode(tp); ts = []; FOR subject IN QueryIndexComponent(idx, dict, tpe.subject]) indx_s = idx[subject] FOR predicate IN QueryIndexComponent(indx_s, dict, tpe.predicate]) indx_p = indx_s[predicate] FOR object IN QueryIndexComponent(indx_p, dict, tpe.object]) object = indx_p[object] ts.push(subject, predicate, object)
END
END END RETURN ts
Algorithm 2: Pseudocode for executing a triple pattern query over an index, sorted in SPO order. FUNCTION QueryIndexComponent(idxc, dict, term)
INPUT: idxc: a certain triple component of a triple index dict: dictionary term: a term inside a triple pattern OUTPUT:
ts: sequence of triples matchingTerms = [] IF term.type === 'Variable'
FOR key IN idxc
matchingTerms.push(dict.decode(key))
END ELSE
IF idxc contains dict.encode(term)
matchingTerms.push(term)
END END RETURN matchingTerms
Algorithm 3: Pseudocode for finding all matches of a single triple component inside an index.
As example use case to illustrate different indexing approaches, we introduce a fictional dataset con‐ taining statements from different people on the color of violets in Listing 1. @prefix : <http://example.org/foo#> . :Alice :says << :Violets :haveColor :Blue >> . :Bob :says << :Violets :haveColor :Yellow >> .
Listing 1: Turtle snippets containing statements by Alice and Bob on the color of violets.
To find out what color each person says violets have, we can execute the SPARQL query from Listing 2. is query contains a variable in the subject position, and a variable inside the quoted triple paern of the object position. For brevity in the remainder of this article, we refer to the variables in‐ side quoted triple paerns as quoted variables.
PREFIX : <http://example.org/foo#> SELECT ?person ?color WHERE {
?person :says << :Violets :haveColor ?color >> . }
Listing 2: SPARQL query to find what color each person says violets have.
More advanced datasets may also contain nested quoted triples, in which any term inside a quoted triple could be another quoted triple. ere is no upper limit of the nesting depth that can occur.
In this section, we introduce four approaches for indexing quoted triples, with increasing levels of complexity. ese approaches build upon the well-established methods of using dictionary encoding and storing triples in different orders as explained in Section 3. Our approaches only rely on changes within the dictionary mechanism, while the triple index itself can remain unchanged. 5 / 15
A straightforward way to achieve dictionary encoding of quoted triples, is to include quoted triples directly inside the dictionary with all other RDF terms. As such, quoted triples are handled in exactly the same manner as other RDF term types. For dictionaries that map strings to integers, this requires a mechanism to convert quoted triples into strings. Fig. 2 shows an example of such dictionary contents based on our use case data.
Executing triple paern queries is identical to the baseline approach as explained in Section 3, except for triple paerns containing quoted variables, such as the query ?person :says <<Violets haveColor ?color>>. As this approach has no direct way of matching the ?color variable to quoted triples, we are required to convert quoted triple paern terms containing variables to variables, and perform a postprocessing step to only emit those triples that match the quoted triple paern. e pseudo-code of this algorithm is shown in Algorithm 4.
e main advantage of this approach lies in its simplicity of implementation. However, we hypothe‐ size two main disadvantages: 6 / 15 1. Storage overhead: oted triples with shared terms lead to a storage overhead, such as the dupli‐ cate storage of :Violets and :haveColor in Fig. 2. 2. Slow quoted triple pattern execution: When executing triple paern queries with quoted vari‐ ables, there is no indexed access to matching quoted triples, which can lead to query performance issues.
In an aempt to cope with the two disadvantages of the singular dictionary approach, we can dedi‐ cate the storage of quoted triples to a separate dictionary, as shown in Fig. 3.
To execute triple paern queries in this approach, the post-processing step from the singular dictio‐ nary is not needed anymore. Instead, we can hook directly into the internal processing of separate triple component indexes. Concretely, when finding all matches of a given term inside a triple compo‐ nent index, we check if our term is a quoted triple paern. If so, we perform an inner join between all quoted triple entries within the quoted triples dictionary, and the terms within the triple component in‐ dex. If the triple component index is index in a hash-like manner, then this inner join can be done effi‐ ciently in a hash join manner. e pseudo-code of this algorithm is shown in Algorithm 5. FUNCTION QueryIndexComponentQuotedDict(idxc, dict, term)
INPUT: idxc: a certain triple component of a triple index dict: quoted triples dictionary term: a term inside a triple pattern IF term.type === 'Quoted' && term contains variables matchingTerms = [] FOR quotedTriple IN dict.getAllQuotedTriples()
IF idxc contains dict.encode(quotedTriple)
matchingTerms.push(quotedTriple)
END
RETURN matchingTerms ELSE
RETURN QueryIndexComponent(idxc, dict, term) END
Algorithm 5: Pseudocode of the algorithm for finding all matching terms of a certain triple component inside an index using a quoted triples dictionary. is algorithm is a variant of QueryIndexComponent from Algorithm 3.
We hypothesize that this separated quoted triples dictionary will result in a lower storage overhead. Furthermore, we expect triple paern execution to be faster due to the fact that a quoted triple paern will only lead to matches with entries in the quoted triples dictionary, as opposed to all possible terms. 7 / 15 However, as shown in Fig. 3, this approach can still lead to redundant storage if terms are shared across different quoted triples, such as :Violet and :haveColor. Furthermore, the join inside the triple compo‐ nent index using all quoted triples might become too expensive if there are many non-matching quoted triples.
To solve the redundant storage issue within the quoted triples dictionary approach, we extend upon that approach by not storing quoted triples in full, but by instead encoding the three components of that quoted triples, and using those encodings as key inside the dictionary. Fig. 4 illustrates an example of this approach.
Fig. 4: Plain terms and quoted triples are stored in separate dictionaries, where quoted triples are recursively encoded using existing dictionary encodings.
e triple paern query algorithm is identical to the one from Algorithm 5, except for the fact that dictionary encoding and decoding will require the extra step of encoding and decoding of the three triple components.
We hypothesize that this approach will lead to lower storage usage due to the shared encoding of re‐ dundant terms inside quoted triples.
e oted Triples Dictionary approach requires triple component indexes to join with all quoted triples, which may be costly for selective quoted triple paerns in the presence of many non-matching quoted triples. To solve this problem, we can modify the storage of our oted Triples Dictionary from a map-like structure to a tree-like structure, so that triple paern matching can be done more efficiently. Concretely, this tree-like structure can be implemented similar to a triple index, but it must map to inte‐ ger encodings of quoted triples. Fig. 5 illustrates an example of this approach. is example only makes use of the SPO order for encodings, but in practise multiple other collation orders may be used.
Fig. 5: Plain terms and quoted triples are stored in separate dictionaries, where quoted triples are recursively encoded using existing dictionary encodings, and indexed in a tree structure based on triple components.
Executing triple paern queries is very similar to the approach of the oted Triples Dictionary, with the difference that instead of joining with all quoted triples, we join with only those quoted triples that match with the current quoted triple paern. e pseudo-code of this algorithm is shown in Algorithm 6.
FUNCTION QueryIndexComponentQuotedDictIndex(idxc, dict, term)
INPUT: idxc: a certain triple component of a triple index dict: quoted triples dictionary term: a term inside a triple pattern IF term.type === 'Quoted' && term contains variables matchingTerms = [] FOR quotedTriple IN dict.getMatchingQuotedTriples(term)
IF idxc contains dict.encode(quotedTriple)
matchingTerms.push(quotedTriple)
END END
RETURN matchingTerms ELSE
RETURN QueryIndexComponent(idxc, dict, term) END
Algorithm 6: Pseudocode of the algorithm for finding all matching terms of a certain triple component inside an index using an indexed quoted triples dictionary. is algorithm is a variant of QueryIndexComponent from Algorithm 3.
We hypothesize that this approach will speed up triple paern query performance due to the higher selectivity during joins between the quoted triples dictionary and the current component index.
In this section, we evaluate the impact of the indexing approaches discussed in Section 5 in terms of storage size, ingestion time, and query execution time. We start by discussing our implementation of the approaches, followed by our experimental setup, results, and end with a discussion. 9 / 15
To achieve a fair comparison between the different indexing approaches, we have implemented all approaches in the same programming language (TypeScript/JavaScript). e implementation of these approaches is open-source, and is available on GitHub at hps://github.com/rubensworks/rdf-stores.js.
To measure the performance impact of different quoted triple depths, we create synthetic datasets of various sizes. Our dataset generator is based on the data model of Section 4 with different people (size / 10) and colors (10), and allows any number of triples to be generated. Furthermore, it allows a depth pa‐ rameter to be specified, which defines the nesting depth of quoted triples in object positions. For in‐ stance, a depth value of 1 generates quoted triples in the form of ?person :says << :Violets :haveColor ?color >>, while a depth value of 3 generated quoted triples in the form of ?person :says << ?person :says << ?person :says << :Violets :haveColor ?color >> >> >>.
For our experiments, we range the dataset from 1.000 to 1.000.000 triples, with the depth ranging from 1 to 5. For each combination, we measure the performance of the four indexing approaches in terms of the following metrics:
Storage size: e total memory consumption aer ingestion in MB.
Ingestion time: e duration of ingesting the generated triples in milliseconds. ery execution time: e total duration of executing all triple paern queries in milliseconds. ery execution time was measured using 3 categories of queries (examples assume depth 2): Low selectivity: ery people in the form of: ?person :says << ?person :says << :Violets :haveColor :Red >> >>. Each query produces size / 10 results.
Medium selectivity: ery colors in the form of: ?person :says << :Bob :says << :Violets :haveColor ?color >> >>. Each query produces 10 results.
High selectivity: ery colors of specific people in the form of: :Alice :says << :Bob :says << :Violets :haveColor ?color >> >>. Each query produces 1 results.
e four indexing approaches were configured with three indexes (SPO, POS, OSP), and the indexed quoted triples dictionary was also configured with these three indexes. All experiments were executed on a MacBook Pro 13-inch, 2020 with 16GB of RAM and a 2,3 GHz ad-Core Intel Core i7 processor. Our experimental setup is fully reproducible, and is available together with the raw results at hps:// github.com/rubensworks/experiments-indexing-quoted-triples.
e labels inside each figure map to the indexing approaches as follows:
Subfig. 8.1: Depth 1
Subfig. 10.1: Depth 1
Subfig. 10.2: Depth 3 Subfig. 10.3: Depth 4
Subfig. 10.4: Depth 5 6.4.1. Storage Size
e results from Fig. 6 show that in terms of storage size, the singular dictionary and referential quoted triples dictionary approaches perform the best. e quoted triples dictionary and indexed quot‐ ed triples dictionary approaches on the other hand require significantly more memory. Contrary to what we hypothesized in Section 5, the storage overhead of the singular dictionary for terms inside quoted triples is less significant than expected, and the gains from the removal of storage redundancy with the referential quoted triples dictionary are minimal. is is due to the string interning memory optimization that is used by Node.js, whereby multiple equal string instances are only stored once in memory. e indexed quoted triples dictionary approach results in a significantly higher storage size due to the three indexes that are used to index quoted triples. 6.4.2. Ingestion Time
As expected, we observe similar results in terms of ingestion time in Fig. 7, where the singular dictio‐ nary and quoted triples dictionary are significantly faster than the referential and indexed quoted triples dictionary approaches. ese approaches are faster due to their simpler encoding approach, whereas the referential and indexed quoted triples dictionary approaches require more operations dur‐ ing triple encoding. 13 / 15 6.4.3. ery Execution Time
e results in Fig. 8, Fig. 9, and Fig. 10 show that on average, the indexed quoted triples dictionary approach vastly outperforms all other approaches. is is most significant for triple paerns with medi‐ um selectivity due to the fact that this approach has indexes corresponding exactly to these queries, while the other approaches require iteration over all quoted triples. For triple paerns with low selec‐ tivity, the difference is smaller, but the indexed quoted triples dictionary approach is still faster overall. e difference for triple paerns with high selectivity is minimal, as the overhead of triple paern dic‐ tionary encoding during query execution when fetching a single result becomes more apparent.
In this article, we discussed four approaches for the in-memory indexing of quoted triples, ranging from very naive to highly optimized for quoted triple paern access.
Our results show that the indexed quoted triples dictionary approach is on average orders of magni‐ tude faster than other indexing approaches. In the most extreme case, this approach is over 4.000 to 11.000 times faster than other indexing approaches for a dataset size of 1 million with quoted triples at depth 5. For smaller dataset sizes, lower quoted triple depths, and other types of queries, the difference becomes smaller. is significant speedup at query time comes with the expected cost of increased stor‐ age size and ingestion time, which is approximately two-fold for a large dataset.
As such, for use cases where quoted triple paern queries occur at various depths, and an increase in storage size and ingestion time are acceptable, the indexed quoted triples dictionary approach is highly beneficial for achieving good query performance. Furthermore, given the fact that this approach stores quoted triple terms separate from all other terms inside the dictionary, there is no significant overhead of using such a dictionary by default in triplestores, even if is unknown before ingestion starts if quoted triples are present in the datasets.
In future work, there is a need to evaluate the performance of different indexing approaches over
real-world data, as we only evaluated performance over artifically generated datasets, which do not
capture real-world properties [
In conclusion, the outcomes of this work show that the inclusion of the concept of quoted triples into the RDF and SPARQL recommendations necessitates changes in triplestores in terms of indexing and dictionary encoding, but that approaches such as the indexed quoted triples dictionary are able to pro‐ vide very good performance, while not requiring overly complicated additions implementation-wise. References 14 / 15