Source-linked AI summary
gMark: Schema-Driven Generation of Graphs and Queries
Guillaume Bagan, Angela Bonifati, Radu Ciucanu, George H. L. Fletcher, Aurélien Lemay, Nicky Advokaat
TL;DR
Graph-system experiments need controllable synthetic graph instances and corresponding workloads, but existing resources often rely on fixed graphs or schemas or provide limited tailored-workload support. gMark generates graphs and query workloads from schemas, with query selectivity as a control; its empirical study reports quality and practicality, while noting limits in which benchmark schema constraints it can encode.
Problem
Method
gMark uses graph schemas to generate synthetic instances and tailored query workloads, with query selectivity set as an input parameter.
Source: §5.2.2 · p. 8Results
The authors report that gMark generates interesting queries and diverse workloads that stress-test state-of-the-art systems on small graphs, and that standard PostgreSQL UCRPQ implementation typically outperforms dedicated systems across constant and linear queries.
Source: §7.2 · p. 13Takeaways & Limitations
The authors conclude that gMark's schema-driven generator is domain-independent, configurable, and supports workloads exhibiting recursive path queries.
Source: §8 · p. 13gMark cannot encode some benchmark characteristics, including subtyping and hardcoded correlations.
Source: §6.1 · p. 11
Abstract
from arXiv · showhide
Massive graph data sets are pervasive in contemporary application domains. Hence, graph database systems are becoming increasingly important. In the experimental study of these systems, it is vital that the research community has shared solutions for the generation of database instances and query workloads having predictable and controllable properties. In this paper, we present the design and engineering principles of gMark, a domain- and query language-independent graph instance and query workload generator. A core contribution of gMark is its ability to target and control the diversity of properties of both the generated instances and the generated workloads coupled to these instances. Further novelties include support for regular path queries, a fundamental graph query paradigm, and schema-driven selectivity estimation of queries, a key feature in controlling workload chokepoints. We illustrate the flexibility and practical usability of gMark by showcasing the framework's capabilities in generating high quality graphs and workloads, and its ability to encode user-defined schemas across a variety of application domains.
1 INTRODUCTION
gMark addresses the need for controllable graph instances and corresponding workloads with a schema-driven, workload-centric framework. It targets diversity in graph structures and query workloads while supporting practical domains and query languages.
1 INTRODUCTION
- Its workload-centric approach controls diversity in graph schemas and query workloads, tailoring data structure and queries to particular domains or applications.The paper identifies multi-query optimization, workload-driven tuning, streaming, mapping discovery, and query rewriting as relevant settings.Source: §1 · p. 1
- gMark is a domain- and query-language-independent framework for tightly controlled generation of synthetic graph instances paired with query workloads.It is provided as open-source software ready for use in the graph processing community.Source: §1 · p. 1, §1.1 · p. 2
- gMark's core workload-generation method estimates selectivity for graph queries, a contribution the authors describe as first of its kind.They also identify query optimization and query inference on graphs and relational data as potential applications.Source: §1 · pp. 1–2
1.1 gMark design principles
- An optional graph configuration specifies edge predicates, node types, and their properties in generated instances.This schema definition supports domain-independent generation that can target varied realistic domains.Source: §1.1 · p. 2
- Workload generation relies primarily on the graph configuration rather than generated instances, with configurable parameters for query behavior and no fixed query-template set.The parameters can target navigational and recursive query execution performance.Source: §1.1 · p. 2
- gMark supports graph output as N-triples and query workloads in SQL, SPARQL, Datalog, and openCypher, with extensible output formats.The paper demonstrates adapting scenarios from LDBC Social Network Benchmark, SP2Bench, and WatDiv into gMark configurations, subject to incomparable features.Source: §1.1 · p. 2
1.2 Contributions and organization
- The paper formalizes graph and workload generation and shows both problems are generally intractable.Its contributions also include recursive-query support and selectivity estimation, plus empirical studies of graph and workload coverage, selectivity accuracy, generator scalability, and graph-query engines.Source: §1.2 · p. 2
- Selectivity tuning is supported only for binary queries, or queries of arity two.The paper notes that regular path queries are binary.Source: §1.2 · pp. 2–3
2 RELATED WORK
Prior graph-generation resources often use fixed graphs or schemas, or offer limited support for tailored workloads, while schema-based workload selectivity control remains difficult. gMark generates tailored workloads from schemas and supports recursive path queries.
2 RELATED WORK
- Graph benchmarking resources include synthetic tools such as SP2Bench, LDBC, LUBM, BSBM, Grr, and WatDiv, as well as real-world graph collections SNAP and KONECT.Application-driven derivation of graph configurations and synthetic instances has also been studied,,.Source: §2 · p. 3
- Existing resources often rely on fixed graphs or schemas, or provide limited support for tailored workloads; estimating selectivity on generated instances becomes unfeasible for massive graphs and workloads.The paper also notes the absence of consensus on graph-schema formalisms and the difficulty of constructing workloads with specified selectivity and structure.Source: §2 · p. 3
- gMark generates tailored workloads directly from graph schemas with selectivity as an input, unlike the finer-grained control absent from BSBM and WatDiv.The authors know of no solution that controls selectivity during query generation using only graph schemas.Source: §2 · p. 3
- gMark is presented as the first solution for generating workloads with recursive path queries, including unions of conjunctive regular path queries.These queries are core constructs in SPARQL 1.1 and openCypher and are expressible in Datalog-like languages and SQL:1999.Source: §2 · p. 3
3 THE GENERATION PROBLEM
This section frames graph and workload generation as a constrained benchmark problem, motivated by needs for diverse, tunable experiments and gaps in existing benchmarks. It formalizes graph and query workload configurations, then shows that deciding whether either can be satisfied is NP-complete.
3.1 Motivating example
- Existing benchmarks limit schema control: SP2Bench hardcodes constraints, while WatDiv lacks global edge-predicate and in-distribution constraints.The motivating bibliographical scenario illustrates configurable node and predicate counts, degree distributions, and relationships between types and predicates.Source: §3.1 · p. 3
3.2 Graph generation
- A graph configuration combines graph size with a schema specifying node types, predicates, occurrence constraints, and in- and out-degree distributions.Supported degree distributions include uniform, Gaussian, and Zipfian.Source: §3.2 · p. 4
3.3 Query workload generation
- A query workload configuration controls query count, arity, shape, selectivity, recursion probability, and size; gMark supports UCRPQs and translates them to four syntaxes.The supported output syntaxes are SPARQL, openCypher, PostgreSQL, and Datalog.Source: §3.3 · pp. 4–5
3.4 Intractability of the generation problem
- Deciding whether a graph configuration or query workload configuration has a satisfying instance is NP-complete.The graph result follows by reduction from SAT1-in-3; the workload result follows because its configuration includes a graph configuration.Source: §3.4 · pp. 5–6
- Because exact workload constraints are intractable, gMark uses a heuristic that may relax some parameters to achieve linear-time generation.The authors report fast generation and good-quality graph instances and queries in their experiments.Source: §3.4 · p. 6
4 GRAPH GENERATION
Graph generation is NP-complete to decide exactly, so gMark uses a heuristic that guarantees linear-time generation by relaxing constraints when needed. The algorithm builds source and target node vectors for each schema constraint and emits edges up to the shorter vector’s length.
4 GRAPH GENERATION
- The algorithm guarantees linear-time generation by relaxing some graph-configuration constraints when necessary for scalability.Deciding whether a graph satisfying a configuration exists is NP-complete.Source: §4 · p. 6
- For each constraint, gMark samples source and target node vectors from the specified degree distributions, then emits labeled edges up to the shorter vector’s length.The vectors’ lengths depend on the fixed or proportional type counts, and their random draws are independent.Source: §4 · p. 6
- An implementation optimization avoids constructing vectors when the in- or out-distributions are Gaussian, using their average information instead.Experiments are reported to confirm practical efficiency and scalability.Source: §4 · p. 7
- When the source and target vectors differ in size, the output may not meet exact in- or out-distribution parameters for some nodes.The method preserves distribution types rather than exact parameters and always returns a graph instead of performing a potentially costly satisfiability check.Source: §4 · p. 7
5 QUERY GENERATION
gMark generates schema-coupled query workloads with configurable diversity and selectivity. Its query algorithm builds varied query forms, then uses schema-derived selectivity classes and data structures to guide path instantiation.
5 QUERY GENERATION
- The same input schema drives graph and query generation, coupling workloads to instances while preserving fine-grained workload diversity.Source: §5 · p. 7
5.1 General algorithm
- The base algorithm generates queries with configurable arity, shape, recursion, and size, in time linear in input and output size.It builds query skeletons, chooses projection variables, and instantiates placeholders with regular expressions; selectivity constraints are handled separately.Source: §5.1 · pp. 7–8, §5 · p. 7
5.2.1 Constant, linear, and quadratic queries
- Selectivity is modeled as result growth |Q(G)| = β|G|^α; for binary queries, α ranges from 0 to 2 and approximates constant, linear, or quadratic growth.The study reports experimental confirmation of this asymptotic assumption.Source: §5.2.1 · p. 8
5.2.2 Estimating the selectivity value
- The estimator assigns schema- and endpoint-type-specific selectivity classes, then combines them with algebraic rules for regular-expression union, concatenation, and eligible Kleene-star paths.The resulting class maps to an estimated α of 0, 1, or 2.Source: §5.2.2 · pp. 8–9
5.2.3 Data structures
- Estimation uses a schema graph of type-and-class states, a shortest-path distance matrix, and a selectivity graph linking states reachable within configured path lengths.Source: §5.2.3 · pp. 9–10
5.2.4 Accommodating selectivity in query generation
- For each placeholder, the generator chooses a type-consistent path through the selectivity graph to satisfy the query’s target selectivity class and size configuration.Kleene-star conjuncts inherit endpoint types from neighboring conjuncts; when constraints conflict, the algorithm can relax path length rather than backtrack.Source: §5.2.4 · p. 10
- Selectivity-aware estimation and generation have quadratic time and data-structure size in the schema size, due to the distance matrix.Source: §5.2.4 · p. 10
6 EMPIRICAL EVALUATION OF GMARK
Across diverse schemas and query workloads, gMark’s estimated selectivities closely match observed result growth, while its generators handle varied graph sizes and workloads efficiently. Its benchmark-schema encodings capture key characteristics but cannot represent every benchmark constraint.
6.1 Coverage of practical graph scenarios
- gMark encoded key characteristics of LDBC, SP2Bench, and WatDiv schemas, but not subtyping or hardcoded correlations, whose constraints are incomparable with gMark’s.For SP2Bench, generated queries matched the original load’s asymptotic runtime behavior across constant, linear, and quadratic classes, without reproducing the exact queries.Source: §6.1 · p. 11, Figure 10 · p. 11
6.2 Quality and scalability
- Estimated selectivity curves closely overlap theoretical curves for constant, linear, and quadratic Bib queries, with similar results reported for other shapes and use cases.Across workloads and Bib, WD, and LSN, estimated α values are approximately 0, 1, and 2 for constant, linear, and quadratic queries, respectively.Source: §6.2 · pp. 11–12, Table 2 · p. 11, Figure 11 · p. 12
- Graph generation scaled across Bib, WD, LSN, and SP, although WD was less efficient because its instances were denser, with two orders of magnitude more edges than Bib at equal node counts.Source: §6.2 · p. 12, Table 3 · p. 12
- gMark generated workloads of 1,000 queries in about one second for Bib, LSN, and SP, and about 10 seconds for WD.Translating 1,000 queries into all four supported syntaxes took one tenth of a second for each scenario.Source: §6.2 · p. 12
7 EVALUATION OF QUERY ENGINES
The evaluation uses gMark to compare graph-query engines across workload selectivities and graph sizes, aiming to demonstrate its benchmarking capabilities and expose system limitations. It finds differing strengths across non-recursive workloads and substantial difficulty handling recursive queries.
7 EVALUATION OF QUERY ENGINES
- The evaluation was intended both to demonstrate gMark’s benchmarking capabilities and to identify limitations and improvement areas in current graph-query engines.Source: §7 · p. 12
7.1 Design of experiments
- The comparison covered PostgreSQL, a SPARQL engine, a native graph database, and a Datalog engine, using default configurations; commercial system names were withheld.PostgreSQL used recursive SQL views, while the other systems used their supported query languages.Source: §7.1 · p. 12
- The study varied selectivity class, graph size (2K–16K nodes), and use case, with 30 queries per workload; each runtime averaged three of five warm runs after excluding the cold run and two outliers.Databases were reopened between queries to clear caching effects; the authors report that even these small graphs revealed failures and runtimes of hundreds or thousands of seconds.Source: §7.1 · p. 13
- Queries were chains and results emphasized the Bib use case, where other use cases showed comparable trends; openCypher supports a narrower UCRPQ subset and uses different semantics, so its answers can differ.The study notes that openCypher omits some inverse and recursive-concatenation patterns; SQL uses linear recursion for the UCRPQ translation.Source: §7.1 · pp. 12–13
7.2 Results of experiments
- PostgreSQL was faster across all sizes for constant queries; for linear queries, it led on Con at all sizes and Len/Dis at 2K and 4K, while SPARQL led at larger sizes and on quadratic queries.Constant and linear runtimes were generally similar in order of magnitude; quadratic queries were typically an order of magnitude slower, except that Datalog blurred the distinction.Source: §7.2 · p. 13
- gMark-generated workloads stress-tested current systems on small graphs and exposed query-processing strengths and limitations; PostgreSQL typically outperformed dedicated systems on constant and linear queries.The authors describe this as a broad pattern, not a result for every query class.Source: §7.2 · p. 13
- Only Datalog evaluated the quadratic recursive query, and it was the only system with measurable runtimes at all sizes; most tested systems failed on most recursive queries or ran unexpectedly long.The authors therefore caution that the recursive-query results do not support a clear broad comparison.Source: §7.2 · p. 13, Table 4 · p. 13
8 CONCLUDING REMARKS
The paper presents gMark as a configurable, schema-driven generator for graphs and query workloads, including recursive path queries and selectivity control. Its experiments show that current graph-processing engines have important limitations even on small instances, and the authors identify extensions and benchmarking alignment as future work.
8 CONCLUDING REMARKS
- gMark combines domain independence, extensibility, schema-driven generation, and control over expected query selectivity, and supports workloads with recursive path queries.The authors also describe selectivity estimation as applicable to other benchmarks and problems, including workloads over real graphs after schema extraction.Source: §8 · p. 13
- Experiments exposed important limitations in current graph-processing engines on small instances for both recursive and non-recursive queries.Source: §8 · p. 14
- Future work includes aligning gMark with benchmarking bodies such as LDBC and extending selectivity estimation to n-ary queries.Source: §8 · p. 14