A Survey of RDF Stores & SPARQL Engines for Querying Knowledge Graphs

1 Introduction

• Growing RDF adoption, including knowledge graphs with billions of triples, has increased the need for optimized engines to query large RDF graphs.The paper defines RDF stores as engines that store, index, and process joins over RDF.Source: §1 · p. 1
• Storage choices vary by structure, encoding, and medium; indexes support fast lookups and execution, while join algorithms and join ordering affect query processing efficiency.The survey also notes that SPARQL engines must efficiently support features beyond joins, including filters, optionals, and path queries.Source: §1 · pp. 1–2
• Local stores manage RDF data on one machine, whereas distributed stores partition it across machines; single-machine resources limit local-store scalability.The paper describes distributed stores as typically running on clusters of shared-nothing machines.Source: §1 · p. 2
• The survey reviews local RDF storage, indexing, join processing, and query processing, alongside high-level graph partitioning strategies for distributed storage.Its extended version compares 135 local and distributed engines and 12 benchmarks.Source: §1 · p. 2

2 Literature Review

• Earlier surveys vary in coverage: some focus on relational storage or indexing, while others address distributed stores, and the comparison includes their discussion of engines and benchmarks.Table 1 uses check marks, approximate marks, and blank cells for detailed, partial, or little/no discussion relative to the current survey.Source: §2 · p. 2, Table 1 · p. 3
• Compared with surveys focused on relational storage and indexing, this survey adds join processing, query processing, and partitioning techniques, including SPARQL 1.1 features such as property paths.The cited works predate SPARQL 1.1 standardization.Source: §2 · p. 2
• The authors present their survey as the most comprehensive discussion to date of local SPARQL storage, indexing, join processing, and query processing techniques.They highlight compact-structure indexes, worst-case optimal and matrix-based joins, multi-query optimization, and property-path techniques as examples.Source: §2 · p. 3
• The survey also includes distributed stores and benchmarks for self-containment, while acknowledging that some prior works treat distributed stores in greater detail.The extended version’s engine and benchmark survey is described as more comprehensive than prior work [10].Source: §2 · p. 3

3.1 RDF

• RDF graphs are sets of triples whose subject, predicate, and object terms form directed labeled edges; RDF terms include IRIs, literals, and blank nodes.RDFS and OWL add further semantics, but the survey does not discuss those standards in detail.Source: §3.1 · pp. 3–4

3.2 SPARQL

• SPARQL is the standard RDF query language considered here, with a core defined around basic, navigational, and complex graph patterns and query types.BGPs match triple patterns, NGPs match paths, and CGPs combine or transform pattern results.Source: §3.2 · p. 4
• A BGP evaluation returns solution mappings that replace pattern variables with RDF terms while making every instantiated triple belong to the graph.Mappings are partial assignments defined for the BGP’s variables.Source: §3.2 · p. 4
• SPARQL property paths match pairs of graph nodes connected by paths accepted by path expressions, including concatenation, alternatives, repetition, and inverse paths.These path expressions are akin to 2-way regular path queries extended with negated property sets.Source: §3.2 · p. 4
• Complex graph patterns apply relational-algebra features such as FILTER, SELECT, UNION, EXISTS, MINUS, and OPTIONAL to pattern results.The default operator is a natural inner join; MINUS ignores right-side mappings with no overlapping variables.Source: §3.2 · p. 5
• SPARQL datasets support default and named graphs, while SELECT, CONSTRUCT, DESCRIBE, and ASK specify different result forms.GRAPH patterns can target a named graph or evaluate across active named graphs while binding each graph name.Source: §3.2 · pp. 5–6

4.1 Triple table

• Dictionary-encoded triple tables store numeric object identifiers instead of full terms, while row-wise layouts favor retrieving triples and column-wise layouts favor compression and scanning columns.OIDs can help queries with many intermediate results but few final results; decoding can hurt simple, high-result queries and selective filters.Source: §4.1 · p. 6

4.2 Vertical partitioning

• Vertical partitioning stores a subject–object relation per property, yielding fewer rows and more specific column domains than triple tables but requiring unions for variable predicates.Graphs with thousands of properties may also produce schemas with many relations.Source: §4.2 · pp. 6–7, Figure 5 · p. 7

4.3 Extended vertical partitioning

• S2RDF stores three semi-join reductions for each distinct property pair, letting joins read tuples that contribute to the result at the cost of additional relations to store and update.It omits the O–O reduction because most O–O joins share a predicate and occur in one relation; empty reductions can also be omitted.Source: §4.3 · p. 7

4.4 Property table

• Property tables group subjects with common properties into rows, enabling multiple triples per subject to be retrieved without joins but complicating multi-valued, optional, or changing properties.They can also place terms of the same type in a column, enabling better compression.Source: §4.4 · p. 7, Figure 7

4.5 Graph-based storage

• Graph-based storage exploits bounded graph arity and adjacency, using fixed-attribute triple or quad tables, adjacency-list tries, and index-free pointers from suffix terms to associated prefixes.Some adjacency-list structures also include inverse edges.Source: §4.5 · pp. 7–8, Figure 8 · p. 8
• AMBER decomposes RDF into a multigraph of non-literal nodes and edges, labeling edges with predicates and nodes with literal-valued attributes.In practice, AMBER uses dictionary encoding.Source: §4.5 · p. 8, Figure 9 · p. 8

4.6 Tensor-based storage

• Tensor-based storage represents dictionary-encoded graphs as bit tensors or adjacency matrices, with compact structures supporting operations on otherwise highly sparse representations.A full adjacency matrix with one property id per cell cannot directly represent node pairs connected by multiple properties.Source: §4.6 · p. 8, Figure 10 · p. 8

4.7 Miscellaneous storage / 4.8 Discussion

• Other engines use existing NoSQL key-value, tabular, or document stores for distributed storage, alongside a trend toward NoSQL for distributing RDF management.Relational storage remains broadly adopted, while newer approaches also exploit graph structure and tensors or matrices.Source: §4.7 · p. 8, §4.8 · p. 8

5.1 Triple indexes

• Vertical partitioning and per-property adjacency matrices efficiently support only constant-predicate patterns, with quadtrees or k2-trees indexing the matrices.The quadtree recursively divides a matrix into four sub-matrices, and only gray nodes require children.Source: §5.1 · p. 9, Figure 11 · p. 9
• Six triple permutations suffice to cover all eight abstract triple patterns when indexes support prefix lookups; SPO, POS, and OSP alone can cover them.Permutations can be implemented with standard tree structures or compact adjacency lists and tries.Source: §5.1 · p. 9
• Compact approaches reduce permutation redundancy: cross-compressed tries share ordering information, while RDFCSA and Ring use one compact suffix-array index to support all triple patterns.Ring is bidirectional, allowing traversal from O to S or backward to P in an SPO permutation.Source: §5.1 · p. 9

5.2 Entity-based indexes

• Property tables can support efficient star joins when relevant tables and column indexes are available, while EAGRE indexes entities in n-dimensional space using a space-filling curve.The curve maps multidimensional regions to one-dimensional ordinals that can be indexed sequentially.Source: §5.2 · pp. 9–10, Figure 12 · p. 10
• Entity-based indexes accelerate star joins by retrieving data around a shared entity, and signature structures can find candidate entities or subgraphs matching adjacent properties.gStore uses hierarchical bit-vector signatures for approximate containment checks; GRaSS uses a custom FDD-index for star subgraphs with incoming and outgoing edges.Source: §5.2 · pp. 9–10

5.3 Property-based indexes

• RDFBroker groups nodes by adjacent-property signatures, then uses a lattice to find property tables whose signatures subsume a star join’s required properties.A node signature is the set of predicates on its outgoing edges.Source: §5.3 · p. 10, Figure 13 · p. 10
• AxonDB indexes each triple with the characteristic sets of its subject and object, enabling efficient identification of two star joins connected by a given property.For example, the subject and object signatures of (:SW, skos:related, :DB) are indexed together.Source: §5.3 · p. 10

5.4 Path indexes

• Yaanii clusters encoded paths by template and indexes them in B+trees, while Fletcher et al. restrict indexed paths to a maximum length k.Path indexes can grow exponentially; HPRD therefore expects users to specify paths to index.Source: §5.4 · p. 10
• Maharjan et al. and HPRD use suffix arrays to index paths as strings, an alternative to B+tree path indexes.The section frames path indexing as a way to speed up navigational patterns that may match arbitrary-length paths.Source: §5.4 · p. 10
• Bartoň linearizes a tree by preorder, using postorder labels to find descendants; graphs are supported by decomposing them into indexed forests.Figure 14 illustrates the traversals; descendant status follows from a node’s preorder being greater and postorder less than its ancestor’s.Source: §5.4 · p. 10, Figure 14 · p. 11
• PLSD in System Π indexes transitivity for queries of the form (s, p*, o), encoding nodes and their ancestors through prime numbers and least common multiples.Cycles are handled using strongly connected components, but factorizing the resulting large numbers has no known polynomial-time algorithm.Source: §5.4 · pp. 10–11
• FERRARI indexes each property’s directed graph, using merged strongly connected components and reachability intervals to test whether one node can reach another.Approximate intervals can reduce time and space at the cost of false positives that require separate verification.Source: §5.4 · p. 11

5.5 Join indexes

• Groppe et al. propose 96 indexes for six types of non-symmetric joins, but the high space cost leads some systems to index only frequent joins.Hash maps cover the 24 permutations of the remaining elements, excluding the join variable.Source: §5.5 · p. 11

5.6 Structural indexes

• GRIN hierarchically partitions the graph into distance-based regions, with leaves inducing subgraphs that can be searched for nodes within a specified distance.Figure 16 illustrates regions organized around selected nodes and distances.Source: §5.6 · p. 11, Figure 16 · p. 11
• A quotient graph groups input nodes into supernodes while retaining labeled edges between groups, and any BGP solutions in the input graph also yield solutions at supernode granularity.The quotient graph can reveal candidate supernodes without identifying exact input-graph solutions.Source: §5.6 · pp. 11–12, Figure 17 · p. 12
• DOGMA builds a balanced binary tree whose parents contain quotient-like graphs of their children, while (O)SQP uses an in-memory quotient index partitioned by bisimulation.Source: §5.6 · p. 12
• SAINT-DB partitions triples into supernodes and labels edges between them by join type, such as S–S or P–O.Source: §5.6 · p. 12

5.7 Quad indexes

• Quad indexing yields 16 abstract index patterns and 24 potential permutations, while flat and circular indexes use six and two permutations, respectively.A practical compromise is to maintain selected permutations covering common patterns rather than every possibility.Source: §5.7 · p. 12
• RIQ hashes seven abstract triple patterns for each named graph into pattern vectors, then uses locality-sensitive hashing to group and retrieve vectors similar to a BGP.Source: §5.7 · p. 12

5.8 Miscellaneous Indexing

• RDF stores may reuse legacy NoSQL systems, but these are not RDF-tailored and often map conceptually to previously discussed schemes; specialized spatial or temporal indexes are not covered in detail.Source: §5.8 · p. 12

5.9 Discussion

• Entity-, property-, path-, and structural indexes can optimize star joins, path joins, or graph-region identification, while more comprehensive indexes enable faster queries at the cost of space and costlier updates.Source: §5.9 · p. 12

6.1 Pairwise join algorithms

• Pairwise nested-loop, hash, and merge joins combine two patterns at a time; nested loops can suit a much smaller input when indexes avoid scanning the other input.Sideways information passing can filter intermediate results, including through shared ranges or domain filters.Source: §6.1 · p. 13

6.2 Multiway joins

• Multiway joins evaluate several operands together, exploiting locality in entity-based indexes, path indexes, or sorted triple tables.A BGP can be divided into sub-BGPs for multiway evaluation, then joined across the subresults.Source: §6.2 · p. 13

6.3 Worst case optimal joins

• Worst-case-optimal joins resolve BGP variables one by one and can enumerate results in time bounded by the AGM bound, unlike traditional pairwise joins.Leapfrog Triejoin is one such algorithm; efficient intersections require reading triple-pattern results in sorted order for each variable.Source: §6.3 · pp. 13–14

6.4 Translations to linear algebra

• Translating joins into linear algebra can use GPU and HPC parallelism, though MAGiQ’s single-matrix representation cannot encode multiple differently labeled edges between two nodes.Other approaches use GPU-resident triple tables or optimize star-like joins and sparse-matrix representations.Source: §6.4 · p. 14

6.5 Join reordering

• Join order can change intermediate-result counts substantially: one plan produces 25 intermediate results, while another produces 5 before each returns 5 final results.The survey notes that differences may reach orders of magnitude on larger graphs.Source: §6.5 · p. 15
• Join planners use graph statistics, runtime sampling, or query heuristics to estimate cardinalities and selectivity, then choose join orders and algorithms.Greedy ordering is simple but not always optimal; dynamic programming and other metaheuristics are alternatives.Source: §6.5 · p. 15

6.6 Caching

• Caching query or subquery results can reduce future costs, but cache choices trade off cost reduction, reuse, storage overhead, and validity over time.Caching hot triples limits space overhead but leaves joins to be recomputed.Source: §6.6 · pp. 15–16

6.7 Discussion

• The survey presents pairwise, multiway, worst-case-optimal, and GPU-based joins alongside planning and caching, highlighting trade-offs in runtime, planning, and storage.Statistics can improve plan selection but incur space and update costs; caching likewise involves a time–space trade-off.Source: §6.7 · p. 16

7.1 Relational algebra (beyond joins)

• Algebraic rewriting can derive equivalent SPARQL plans, including by splitting filters, swapping their order, and pushing filters inside operators.Optionals return partial solutions over incomplete data, but can emulate negation and lead to jumps in computational complexity.Source: §7.1 · p. 16

7.2 Property paths

• Property-path approaches include graph search, indexes, path splitting, recursive queries, and hybrid plans; the survey notes that complex paths can be costly while simple transitive expressions cover 99.99% of queries in Wikidata SPARQL logs.Waveguide combines breadth-first search guided like finite automata with memoized results that can be reused.Source: §7.2 · pp. 16–17

7.3 Recursion

• SPARQL extensions support graph-based recursion through fixpoint construction and relation-based recursion through repeated SELECT-query execution.Linear recursion can support features such as property paths by joining each new triple with the base graph rather than the temporary graph.Source: §7.3 · p. 17

7.4 Analytics

• Analytical workloads can be supported by translating SPARQL to systems such as PigLatin, Hadoop, or Spark, or translating analytical queries into SPARQL.Existing distributed frameworks may not support every SPARQL feature easily; graph analytics can also be invoked through extensions or recursive languages.Source: §7.4 · pp. 17–18

7.5 Graph query rewriting

• SPARQL-to-Gremlin rewriting enables evaluation on graph engines that support Gremlin, while Semantic Property Graph projects reified RDF graphs into a property-graph model..Source: §7.5 · p. 18

7.6 Multi-query optimization

• Multi-query optimization groups queries by common subgraphs or sub-automata, evaluates shared structures, and derives individual query results from them.Related work also addresses federated systems and continuous queries over streaming RDF data.Source: §7.6 · p. 18

7.7 Discussion

• The survey contrasts rewriting to existing engines with custom implementations, noting that existing language-engine combinations are unlikely to support every SPARQL feature efficiently.Property paths, filters, optionals, multi-query optimization, recursion, and analytics are among the surveyed targets.Source: §7.7 · p. 18

8 Partitioning

• Partitioning seeks to reduce network communication by placing data so that some intermediate joins can run on individual machines.A partition assigns subgraphs of an RDF graph to machines; replication or other redundancy is allowed in the paper’s definition.Source: §8 · p. 19

8.2 Graph-based Partitioning

• Graph-based k-way partitioning seeks balanced node partitions while minimizing triples whose subject and object lie in different partitions.Finding an optimal partition is intractable, so large graphs require approximations such as spectral methods, recursive bisection, or multilevel partitioning.Source: §8.2 · p. 19

8.3 Query-based Partitioning

• Workload-based partitioning uses query-log joins to partition or replicate data so common joins can be executed on individual machines.It may be planned from a query log or adapted as queries arrive.Source: §8.3 · p. 20

8.4 Replication

• Replication ranges from copying the full graph to copying high-demand partitions, aiming to increase throughput or reduce hotspots and balance workloads.These approaches store redundant data across machines.Source: §8.4 · p. 20

8.1 Triple/Quad-based Partitioning

• Triple- or quad-based partitioning is simple to compute and maintain, and can localize joins on the chosen partition key.Hashing avoids a range-to-machine mapping but skewed keys can cause imbalance; range partitioning supports range queries but requires mapping and balancing.Source: §8.1 · p. 19, §8.5 · p. 20

8.5 Discussion

• Graph-based methods can localize more complex patterns but cost more to compute and maintain; replication can improve locality and load balancing at the cost of storage.Query information can guide partitions or replication toward frequently used subpatterns.Source: §8.5 · p. 20

9 Systems and Benchmarks

• The extended survey covers 135 local and distributed RDF stores and SPARQL engines, describing the techniques they use.The appendix also presents synthetic and real-world benchmarks for evaluating systems under varied criteria.Source: §9 · p. 20
• The systems survey includes both local and distributed engines.Source: §9 · p. 20
• The benchmark appendix includes synthetic and real-world benchmarks for evaluation under a variety of criteria.Source: §9 · p. 20

10.1 Current trends

• RDF stores are moving toward native graph-based storage, indexing, and query processing alongside greater use of modern hardware.Graph-native approaches optimize compression and navigation, while graph-aware indexes and join algorithms extend beyond relational-style techniques.Source: §10.1 · p. 21
• NoSQL systems and distributed frameworks scale RDF stores across machines, while compact in-memory structures and GPU/HPC processing exploit modern hardware.Matrix- and tensor-based graph representations further enable hardware acceleration.Source: §10.1 · p. 21

10.2 Research Challenges and Future Directions

• Many surveyed works assume static data, leaving efficient querying of dynamic RDF graphs and support for updates as open challenges.The survey points to storage for reads and writes, incremental indexing, and caching as areas for further work.Source: §10.2 · p. 21
• Relatively few works optimize SPARQL 1.1 features such as property paths and negation, and new language features will require techniques of their own.The survey gives SPARQL 1.2 as an example of possible future expressivity.Source: §10.2 · p. 21
• Millions of daily endpoint queries motivate workload-aware caching and effective policies for serving many clients without server overload.Preemption, which pauses and resumes costly requests, is identified as a promising idea for further development.Source: §10.2 · p. 21
• System-level benchmarks can conflate techniques, and many SPARQL 1.0 benchmarks omit features such as property paths.The survey calls for finer-grained technique evaluation and benchmarks that cover these features.Source: §10.2 · p. 21
• SPARQL engines need further work integrating federated querying, reasoning, enrichment, learning, and analytics tasks for knowledge graphs.Open questions include efficient support for reasoning, graph algorithms, embeddings, and graph neural networks within SPARQL engines.Source: §10.2 · p. 21

Survey scope

• The survey includes stores with technical details on storage, indexing, and join processing, ordered approximately by publication or release year and covering published and widely used unpublished systems.Some systems appear in both local and distributed discussions; systems without described support for joins or basic graph patterns, or without key technical details, are excluded.Source: A Survey of RDF Stores · p. 29, §A.1 · p. 29

Relational and vertical-partitioned stores

• Relational-backed stores commonly map RDF data to tables and translate graph queries into SQL, as in Jena, 3store, and SW-Store.Their storage differs: Jena uses triple tables, 3store separates triples and dictionaries, and SW-Store uses vertical partitioning over a column-oriented DBMS.Source: §A.1 · pp. 29, 32

Native stores and indexing

• Native stores use varied index permutations and join strategies: Jena TDB [9] uses custom B+trees and pairwise joins, while RDF-3X combines six-way indexing with cardinality-based join reordering.Blazegraph supports multiple join algorithms, including multiway star joins.Source: §A.1 · pp. 31–33

Alternative storage and graph-based approaches

• Other designs include SW-Store’s vertical partitioning, BitMat’s compressed matrix representation with bitwise multiway joins, and graph-based stores such as DOGMA and gStore.DOGMA partitions graphs into subgraphs and uses candidate pruning; gStore indexes vertex signatures in a tree to evaluate basic graph patterns.Source: §A.1 · pp. 32–34

Local RDF stores

• Triplebit, WaterFowl, and BMatrix [38] use compact matrix, trie, or k2-tree representations to index RDF data.Triplebit uses two orders and auxiliary indexes; WaterFowl encodes its SPO trie with bit strings and wavelet trees; BMatrix’s indexes cover all eight triple patterns.Source: §A.1 · pp. 35, 36, 38
• R3F adds path-based indexes and path-aware filtering to RDF-3X, while RQ-RDF-3X extends its techniques to quads.RQ-RDF-3X indexes all 24 quad permutations and supports reification through named graphs and triple identifiers.Source: §A.1 · p. 36
• RIQ [120], axonDB, and AMBER use graph-pattern or node signatures to narrow candidates and support join processing.RIQ filters candidate named graphs, axonDB matches characteristic sets, and AMBER processes core query nodes before satellite nodes.Source: §A.1 · pp. 37–38
• TripleID-Q [49] scans dictionary-encoded triple-table chunks in parallel on GPUs, while MAGiQ translates graph patterns into matrix or tensor operations.TripleID-Q also implements operators such as joins and filters on the GPU and supports RDFS entailment.Source: §A.1 · p. 38
• Jena-LTJ, Tentris, and Ring use different index structures to support worst-case-optimal joins for basic graph patterns.Jena-LTJ extends Jena TDB with all six triple orders; Tentris uses a hypertrie, while Ring uses a bidirectional circular FM-index.Source: §A.1 · pp. 38–39

Distributed RDF Engines

• The survey turns to distributed stores, describing YARS2 indexes and query processing and Clustered TDB ’s master–slave design.YARS2 uses indexed nested-loop joins and dynamic-programming join reordering; Clustered TDB assigns graph partitions to slaves that can perform joins.Source: §A.2 · p. 39

Distributed partitioning and query execution

• SHARD, PigSPARQL, and Rapid+ [193] target batch processing without indexes, using Hadoop or Pig/MapReduce to execute joins and translated SPARQL queries.PigSPARQL applies filter and selectivity-based join-reordering optimizations; Rapid+ supports star joins and a look-ahead heuristic to reduce Hadoop tasks.Source: §A.2 · pp. 41–42
• CumulusRDF, H2RDF(+), and Jena-HBase use NoSQL-backed RDF layouts with multiple triple permutations or hybrid storage to support lookups and query processing.CumulusRDF proposes hierarchical and flat Cassandra layouts; Jena-HBase combines simple, vertical-partitioned, and fully indexed tables, with hybrid layouts trading additional space for better query times.Source: §A.2 · pp. 41–42
• Trinity.RDF indexes inward and outward adjacency lists and POS/PSO permutations, then uses graph exploration and cardinality-based dynamic programming to plan queries.Adjacency lists for high-degree nodes may be partitioned further.Source: §A.2 · p. 43
• WARP uses RDF-3X with graph-based partitioning and k-hop replication, while workload-aware partitioning keeps k low and selectively replicates to guarantee workload queries with reduced storage overhead.Single-node subqueries are evaluated locally, and custom merge joins are used across nodes rather than Hadoop.Source: §A.2 · p. 43
• CK15 combines triple- and query-based partitioning with vertical tables and secondary indexes that cache intermediate results and support semi-join reductions.Its indexes provide P →SO, PS →O, and PO →S lookups; cached results can be reused by later queries to reduce network traffic.Source: §A.2 · p. 44
• Dydra supports versioned RDF graphs using six quad-table permutations in on-disk B+trees, with SPARQL 1.1 queries, updates, and cloud-based multi-tenant storage.Its indexes capture revisions for versioned queries and archival features; replication using convergent replicated data types is also proposed.Source: §A.2 · p. 45

• Local stores shifted from mature relational backends and schema-specific designs toward native storage, complete triple-pattern indexes, graph-oriented techniques, compact in-memory representations, GPUs, and worst-case optimal joins.Source: §A.3 · p. 49
• Distributed RDF stores progressed from extending native systems with partitioning and distributed joins to using Hadoop, Spark, NoSQL, graph-processing frameworks, in-memory designs, and distributed CPU/GPU acceleration.Source: §A.3 · pp. 49–50
• Most surveyed stores focus on triples rather than quads, while distributed property-path optimization and support for dynamic RDF graphs have received relatively little attention.Many systems also target write-once, read-many workloads.Source: §A.3 · p. 50
• The technical trade-offs among RDF-store proposals and which techniques perform better in different settings remain poorly understood, motivating benchmarks that compare their performance.The survey discusses those benchmarks in the following section.Source: §A.3 · p. 50

Benchmark Design

• SPARQL benchmarks comprise RDF graphs or datasets, queries, and performance measures.The survey organizes benchmark design around these three elements.Source: §B.1 · p. 50

Benchmark Comparison and Results

• Synthetic graphs support scale and graph-property variation, while real-world graphs reflect complex and diverse data encountered in practice.Synthetic graphs can also emulate selected real-world properties; benchmark graphs tend to differ in measures such as structuredness and relationship specialty, with greater uniformity observed in synthetic graphs.Source: §B.1 · p. 50

Benchmark Design

• Queries may be hand-crafted, induced from graph subgraphs, or extracted from real-world logs; templates can generate multiple concrete queries.Log-based workloads may require selecting a subset from millions of queries, while templates can smooth performance variance across individual queries.Source: §B.1 · pp. 50–51
• Query diversity and complexity can be characterized by language features, graph-pattern structure, and measures such as triple patterns, variables, joins, and cyclic queries.A high-level diversity score can be computed from the average coefficient of variation across measures.Source: §B.1 · p. 51

Performance Measures

• Performance measures cover query processing, storage, result correctness and completeness, and updates.Query measures include runtimes and intermediate results; storage measures include loading time and index size; update measures can include insertions or deletions per second.Source: §B.1 · p. 51
• Complementary measures contextualize runtime because aggressive indexing may improve query speed while increasing storage use and update cost.Benchmarks may combine measures to summarize different aspects of system performance.Source: §B.1 · p. 51

Synthetic Benchmarks

• Synthetic benchmarks range from university, e-commerce, bibliographic, and social-network datasets to configurable graph-and-query generators.Examples include LUBM, BSBM, SP2Bench, and LDBC-SNB; WatDiv generates graphs and query templates with adjustable properties.Source: §B.2 · pp. 51–52

Real-World Benchmarks

• Real-world benchmarks use datasets or workloads from DBpedia, FishBase, bioinformatics graphs, Semantic Web Dog Food, and Wikidata.Examples include DBPSB, FishMark, BioBenchmark, FEASIBLE, and WGPB.Source: §B.3 · p. 52