GRBench: A Comprehensive Benchmark Evaluation for Graph-relational Data Management

GRBench: A Comprehensive Benchmark Evaluation for Graph-relational Data Management Zepeng Liu1 , Xinxin Huang1 , Xuanming Liu1 , Sheng Wang1 , Zhiyong Peng1,2 1 School of Computer Science, Wuhan University, 2 Big Data Institute, Wuhan University

[liuzp_063, xinxinhuang976, Teddy233, swangcs, peng]@whu.edu.cn

arXiv:2608.31027v1 [cs.DB] 31 Aug 2026

ABSTRACT Modern data-intensive applications increasingly require database systems to manage structured records and graph data. This demand gives rise to graph-relational data management, spanning storage, query processing, and optimization across relational and graph data. In response, relational database extensions, multi-model databases, and dedicated graph-relational systems have emerged with diverse architectures. However, evaluation methodologies have not kept pace. Existing relational and graph benchmarks assess the two models largely in isolation, while multi-model benchmarks provide limited coverage of graph-relational workloads. Available graph-relational workloads mainly support functional validation and end-to-end latency measurement, revealing little about how storage, operator, and optimization designs affect performance. To evaluate system capabilities in graph-relational data management, we present GRBench. First, GRBench constructs a linked graphrelational schema from the real-world SciSciNet-v2 dataset and derives scalable instances through consistency-preserving subset extraction. Second, it organizes purpose-built query series for controlled evaluation of query processing and system components. Third, GRBench provides semantically equivalent native query formulations and evaluates representative system architectures through a unified, multidimensional methodology. Based on this evaluation, we analyze design trade-offs and identify open challenges to guide future system design and optimization. PVLDB Reference Format: Zepeng Liu, Xinxin Huang, Xuanming Liu, Sheng Wang, Zhiyong Peng. GRBench: A Comprehensive Benchmark Evaluation for Graph-relational Data Management. PVLDB, 18(11): XXX-XXX, 2027. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/whu-totemdb/GRBench.

1

INTRODUCTION

Graph data [9, 24] has become widely used for representing entities and their relationships, while structured attributes and records remain naturally managed in relational form. Modern data-intensive applications [12, 17, 18, 44] increasingly require database systems to support relational and graph data within the same workload. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 18, No. 11 ISSN 2150-8097. doi:XX.XX/XXX.XX

For example, a scholarly analyst may ask, “which papers published after 2020 by authors from a target institution are within one citation hop of a given paper?” Answering this query requires relational filtering and joins over publication and author metadata with graph pattern matching over citation relationships, where relational results constrain graph search. We refer to such queries as graph-relational hybrid queries (GRHQs), which combine relational and graph operations in one query. This demand gives rise to graph-relational data management, requiring systems to support relational data management and graph processing and, more importantly, efficiently execute and optimize GRHQs. Motivations and Research Gaps. To date, graph-relational data management has been supported by a growing range of database extensions [2, 5], multi-model databases [3, 46], and dedicated graphrelational systems [23, 27, 28, 33, 36]. The proliferation of such systems raises a natural research question: Is there a unified benchmark that can systematically evaluate the capabilities of these systems for graph-relational data management? Existing relational benchmarks, including Transaction Processing Performance Council (TPC) workloads [52–54] and optimizer benchmarks such as the Join Order Benchmark (JOB) [34], are valuable for studying transaction processing, analytics, join optimization, and cardinality estimation [21], but do not evaluate graph-specific query processing, such as graph pattern matching. Conversely, graph benchmarks, including the Linked Data Benchmark Council (LDBC) suites [13, 26, 45, 50], primarily target graphnative transactional, analytical, and algorithmic workloads, without explicitly evaluating the interaction between relational joins and graph operations. Multi-model benchmarks broaden the evaluation scope to heterogeneous data management [16, 30, 57], but prioritize broad model coverage over the interaction between relational and graph processing, resulting in limited support for graph-relational workloads. As a result, existing benchmarks largely evaluate relational and graph capabilities in isolation, or provide only limited support for the systematic evaluation of graph-relational data management. We summarize the research gaps as follows:

• Gap 1: Single-model benchmarks evaluate relational and graph processing in isolation. Even when relational and graph benchmarks are used together, they cannot capture the cross-model interactions and therefore cannot evaluate graph-relational data management as an integrated workload. • Gap 2: Multi-model benchmarks provide almost no workloads dedicated to GRHQs. None of UniBench’s 10 queries [57] and only one of M2Bench’s 17 tasks [30] jointly exercise relational and graph processing. Such sparse coverage is insufficient to systematically characterize performance differences across systems.

• Gap 3: For the few available graph-relational workloads, existing benchmarks primarily support functional validation and endto-end latency measurement, but lack controlled query series for fine-grained evaluation of graph-relational storage designs, operator implementations, and GRHQ optimizations.

and retail analytics with scalable generators, and the Star Schema Benchmark [40] distills TPC-H into a star-schema workload for data warehouse engines. These standardized benchmarks provide reproducible workloads for comparing transaction processing, scans, joins, and aggregations. Their synthetic data follows predefined distributions and is less suited to optimizer robustness under realworld correlations and skew. Real-data optimizer benchmarks address this gap by focusing on real-world datasets and query patterns. For example, JOB [34] uses the IMDB data [25] and 113 multi-join SQL queries to reveal join ordering and cardinality estimation errors. Han et al. [21] extend this work using the STATS dataset [10], providing a broader workload measuring estimation accuracy and end-to-end execution. These benchmarks move relational evaluation beyond standardized OLTP/OLAP benchmarking toward optimizer robustness under real-world conditions. The LDBC series provides graph database benchmarks covering distinct aspects of graph processing. LDBC SNB Interactive [13] emphasizes transactional graph processing, including short reads, complex graph pattern matching, and updates. LDBC SNB Business Intelligence [50] targets graph OLAP over a social-network dataset, with aggregation-heavy queries involving graph pattern matching, traversal, and connectivity tests. However, these queries operate over a single logical graph dataset or its relational encoding, rather than coordinating relational and graph representations. For algorithmic use cases, LDBC Graphalytics [26] evaluates kernels such as breadth-first search (BFS), PageRank [37], and connected components. LDBC FinBench [45] targets financial graph transactions with temporal filters, path predicates, and read/write operations. These benchmarks, while comprehensive in their domains, primarily focus on graph-native processing and do not adequately cover relational and graph operations within one system [41, 45, 50].

Our Contributions. To address these gaps, we propose GRBench, a comprehensive benchmark for graph-relational data management. To address Gap 1, GRBench constructs an integrated graphrelational schema from SciSciNet-v2 [35], a large real-world scienceof-science dataset, and derives multiple scale factors through consistent subset extraction. Relational tuples and graph entities are linked through common identifiers and primary/foreign-key constraints, enabling queries to combine relational attribute access with graph traversal. To address Gap 2, GRBench defines 24 GRHQs, each instantiated into three variants preserving the same logical structure while varying predicate selectivity, yielding 72 instances. This systematically parameterized workload expands GRHQ coverage and enables controlled characterization of performance differences across selectivity regimes. To address Gap 3, GRBench organizes its workload into purpose-built query series, each designed to stress a distinct layer of graph-relational processing. Through controlled variations in query structure, operator composition, data scale, and equivalent graph and relational formulations, these query series help isolate the effects of system components rather than exposing only aggregate system-level performance. This design enables fine-grained evaluation of storage, operator, and optimization choices, extending the benchmark beyond functional validation and end-to-end latency. As systems expose different graph-relational query languages and syntax, we further provide semantically equivalent formulations tailored to each system and evaluate query language conciseness. This paper makes the following contributions:

Benchmarks for Multi-model Databases. Multi-model benchmarks extend beyond a single data model to evaluate systems that support multiple data models. For instance, BigBench [16] adapts the TPC-DS retail benchmark to include semi-structured (e.g., web click logs) and unstructured data (e.g., text reviews), focusing on large-scale analytics, including SQL analytics, machine learning, and text/pattern analysis. UniBench [57] simulates an e-commerce scenario, combining relational, document, and graph data to evaluate cross-model joins, aggregations, and transactional consistency. M2Bench [30], targeting relational, document, graph, and array models across e-commerce and healthcare, involves tasks combining at least two data models. While these benchmarks advance multi-model system evaluation, none is specifically designed to evaluate graph-relational workloads, where relational operations and graph processing interact within the same query execution. Although few tasks jointly exercise relational and graph processing, their limited coverage and lack of controlled query variants are insufficient to characterize graph-relational performance.

• We present GRBench, a comprehensive benchmark built on an integrated real-world graph-relational schema, consistently scaled datasets, and purpose-built query series. • We systematically characterize representative systems on graphrelational data management in terms of their storage architectures, execution models, and optimization techniques. • We conduct a cross-system evaluation using unified metrics and semantically equivalent queries tailored to different query languages and system interfaces. • We identify key design trade-offs and open challenges in GRHQ optimization, graph-aware execution, update consistency, and cross-language usability.

2

RELATED WORK

To the best of our knowledge, no existing benchmark has been explicitly designed to evaluate graph-relational data management in a systematic manner. We therefore review representative relational, graph, and multi-model benchmarks, focusing on their workload coverage and limitations for graph-relational evaluation.

Adjacent Benchmarks on Heterogeneous Data. Recent benchmarks also consider heterogeneous or relationally connected data. FDABench [55] evaluates data agents over structured and unstructured sources, while RelBench [47] represents relational tables connected through primary and foreign keys as graphs for predictive

Benchmarks for Relational and Graph Databases. Relational benchmarks cover workloads including online transaction processing (OLTP), online analytical processing (OLAP), and optimizer evaluation. TPC-C [52] evaluates OLTP through order-entry transactions. TPC-H and TPC-DS [53, 54] evaluate decision support 2

Pure Graph Query Capability. This dimension isolates graph operator efficiency by evaluating graph pattern matching without relational joins. By removing relational composition while retaining comparable graph structures and patterns, GRBench examines graph-specific operators and topology access paths without conflating them with graph-relational coordination or optimization. These graph-only queries provide controlled baselines for GRHQ workloads, helping determine whether bottlenecks arise from graph operator execution or relational-graph interaction. Including these baselines ensures that pure graph and hybrid queries are evaluated under consistent data, schema, and execution settings [19, 31].

tasks. These benchmarks target agent-based data analysis or predictive learning rather than execution and optimization of relational and graph operations within database systems.

3

DATA MODEL AND EVALUATION SCOPE

This section sets the modeling assumptions and evaluation boundary used by GRBench. We treat relational tables and property graphs as distinct but connected representations, where relational data captures structured records and graph data captures relationshipcentric topology. This separation lets GRBench evaluate how systems support interaction across the two representations within the query processing core of graph-relational data management.

3.1

Graph Update Support. Graph updates include vertex and edge insertions and deletions. Across database systems that support relational and graph processing, graph records and topology are maintained using different storage organizations, such as edge tables [2, 19, 29, 51], adjacency indexes [11, 22, 28, 42], and explicit source and target vertex identifiers [2, 3]. Update workloads therefore reveal the cost of maintaining consistency across data records, topology structures, and auxiliary indexes, rather than merely the raw cost of inserting or deleting an individual record [48, 56].

Relational and Graph Representations

We consider two separate data representations. The relational representation stores structured entities and attributes in tables. Formally, a system contains a set of tables R = {𝑅1, 𝑅2, . . . , 𝑅𝑛 }. Each table 𝑅𝑖 has a schema attr(𝑅𝑖 ) and stores tuples over these attributes. In GRBench, relational query fragments are expressed through selection, projection, and join. Among them, join is the main mechanism for linking records across relational tables. The graph representation stores entities and their relationships as a property graph. We denote it as 𝐺 = (𝑉 , 𝐸, 𝜆, 𝜙), where 𝑉 is the set of vertices, 𝐸 ⊆ 𝑉 × 𝑉 is the set of edges, 𝜆 assigns labels to vertices and edges, and 𝜙 maps each vertex or edge to a set of properties. In this representation, entities are modeled as vertices and semantic associations are modeled as edges. Graph queries mainly rely on graph-specific operators, including pattern matching and shortest-path search [8, 12, 38]. Although these representations remain distinct, they can be connected through shared identifiers. In GRBench, relational tuples and graph vertices may reference each other through foreign keys, so relational tuples can be joined with graph vertices, while graph query results can be joined back with relational records through the same identifiers. This key-based correspondence provides the basis for relational-graph interaction in the benchmark and reflects a common pattern where structured records and graph entities are maintained separately but linked through entity identifiers [39, 43].

3.2

Relational-equivalent Baseline. We compare selected graph queries and GRHQs with semantically equivalent join-based relational translations. This comparison evaluates whether graphoriented operators and execution frameworks provide measurable benefits over mature relational execution for graph and hybrid workloads, thereby identifying when relational operators and optimizations are sufficient and when graph processing is necessary.

3.3

Scope Boundaries

GRBench focuses on the query processing core of graph-relational data management. It targets centralized database workloads where structured records and graph relationships are queried together, with basic graph updates included to characterize the cost of topology maintenance. The current scope excludes highly concurrent OLTP workloads, distributed execution, aggregation-heavy hybrid analytics, and graph algorithm workloads.

4 GRBENCH 4.1 Benchmark Overview

Evaluation Dimensions

GRBench follows the pipeline shown in Figure 1. We first construct a graph-relational benchmark instance from SciSciNet-v2 [7, 35], as illustrated in Figure 1(a). The raw scientific data is transformed into two coordinated representations: relational tables that store entity attributes and structured records, and graphs that capture citation, collaboration, and other relationship-centric structures. In this way, the benchmark focuses on the interaction between relational tables and graphs without introducing additional data models. Since the original dataset is already sufficiently large, GRBench uses subset extraction rather than synthetic data generation for data scaling, as shown in Figure 1(b). Different scale factors are obtained by extracting consistent subsets from the full dataset, while preserving the correspondence between the relational and graph parts. Based on the scaled data instances, GRBench organizes its workload into five query series, as summarized in Figure 1(c). The Hseries contains GRHQs, combining few/many joins, single/multiple

GRHQ Capability. As the core dimension of GRBench, it measures whether a system can execute GRHQs combining relational selection, projection, and joins with graph pattern matching in one logical task. It further examines whether the system supports relational-graph interaction and whether its optimizer can exploit information from both models to optimize GRHQs. Operator Scalability. Most non-graph-native systems [2, 4, 51] prioritize pattern matching when adding graph query support. We therefore examine whether such systems can provide effective compatibility and extension strategies for other common graph operators, such as shortest-path search, and how these operators perform when they participate in hybrid queries with relational joins. This dimension also tests whether the system can optimize such workloads when relational predicates determine path endpoints and graph expansion must be coordinated with relational filtering. 3

(a) Data Modeling and Generation Citation Raw Dataset Papers Details, etc. Relationships, etc.

(b) Data Scaling

Pure Graph Query (G-series) Pattern-matching on Single Graph or Multi Graphs

Match:

SF=102

SF=103

SF=104 SF=100

SciSciNet-v2 Relational Tables Graphs (c) Query Design Graph-relational Hybrid Query (H-series) Match: (Few/Many Joins) × (Simple/Complex Topology) × (Few/Many Graphs) = 8 Categories

Subset Extraction

Subset Extraction Subset Extraction

Subset

SF=101 Extraction

Operator Scalability Test (S-series) Source Relational Joins with Source or Target Vertices in Shortest-path Search

Update Capability Test (U-series) Insert/Delete Insert Vertices and Edges Delete in a Graph

Target

Pure Relational Query (R-series) H-series

Relational-only Equivalents

G-series

(d) System Under Test

ArangoDB

AgensGraph

DuckDB + DuckPGQ

PostgreSQL + Apache AGE

GRainDB

Kuzu

OrientDB

Figure 1: An overview of GRBench. matched subgraphs, and single-/multi-hop graph patterns to evaluate the core dual-model processing capability. The S-series targets operator scalability, especially relational joins over source or target vertices involved in shortest-path search. The G-series contains pure graph pattern matching queries over one or multiple matched subgraphs, serving as the graph-only baseline. The U-series evaluates update capability through vertex and edge insertions/deletions. The R-series provides relational-only equivalents of all queries in Hand G-series, helping isolate the relational execution cost. Finally, GRBench evaluates representative systems as shown in Figure 1(d).

4.2

Tables

Vertices Authors

AuthorDetails

Joins Affiliated

ContributedFrom NobelLaureates

AuthorsPaper

Patents

Edges Affiliations

NSF

Associated

HIN

LinkNSF Papers

References PaperDetails

LinkHIN LinkClinicalTrials LinkNewsFeed

ClinicalTrials

LinkTwitter

NewsFeed

PaperFields Twitter

PaperSources

CitationsLevel0

HitPapersLevel0

Sources

CitationsLevel1

HitPapersLevel1

Dataset and Schema Design

Fields

Dataset Selection. GRBench uses SciSciNet-v2 [7, 35], a large-scale linked dataset for science-of-science research, as its data source. The dataset describes the scholarly publication ecosystem and contains major entities such as papers, authors, and institutions, together with relationship records including authorship and citation links. The public release contains approximately 250M1 papers, 100M authors, and 2.49B paper-reference records. SciSciNet-v2 is well aligned with graph-relational benchmarking for the following reasons:

Figure 2: Schema design of GRBench. • Open availability. The dataset is publicly available, improving reproducibility and avoiding licensed-data dependencies. Schema Design. We organize SciSciNet-v2 into the coupled schema shown in Figure 2. The design keeps descriptive attributes in relational tables and represents relationship-centric records as property graphs. Concretely, the schema contains 10 relational tables, 9 vertex labels, and 11 edge-labeled property graphs, where each distinct edge label in the figure corresponds to one graph. Papers and authors act as the main anchors between the two models. Relational tables provide paper, author, and hit-paper attributes, while graph edges capture authorship, citation, and field membership. The red solid lines in Figure 2 denote the relational join backbone. In total, the schema supports up to 12 schema-level joins, connecting metadata tables to their corresponding paper and field entities. This organization exposes the intended graph-relational interaction without flattening the dataset into a single representation. Relational predicates can restrict structured records, and graph patterns can then be evaluated over the aligned property graphs through shared identifiers.

• Large scale. The dataset is large enough to support non-trivial subset extraction and to stress storage, indexing, and query execution over both relations and graphs. • Complex real-world distributions. It preserves skewed degree distributions, correlated attributes, and long-tail scientific relationships, making it more representative than synthetic generators for optimizer and execution studies. • Rich join and graph settings. Structured metadata can be joined by paper, author, and affiliation identifiers, while citation, authorship, and external-link records form graph topologies. Together, they enable workloads where relational predicates and joins interact with graph pattern matching or traversal. 1We use K for Thousand, M for Million, and B for Billion in this paper.

4

4.3

Table 1: Organization of the GRBench workload.

Data Scaling

GRBench derives five scale factors, ranging from 𝑆𝐹 = 100 to 𝑆𝐹 = 104 , from SciSciNet-v2 through subset extraction rather than synthetic data generation, as shown in Figure 1(b). The resulting instances span from 488K to 249M papers, from 74.1K to 100M authors, and from 249K to 2.49B reference edges, providing graph-relational workloads over a broad range of data scales. All retained records originate from the original dataset, so attribute values, key correlations, degree skew, and long-tail relationship patterns remain grounded in real data. For each entity type, we define a per-step extraction ratio 𝜌. For large tables and graphs, we set 𝜌 = 0.1, yielding an approximately one-order-of-magnitude reduction between adjacent scale factors. Smaller external-evidence entities use larger ratios to avoid undersized instances. For example, Associated and NobelLaureates use 𝜌 = 0.4, whereas the fixed field taxonomy is retained in full with 𝜌 = 1.0. Consequently, even at 𝑆𝐹 = 100 , all scalable entities contain thousands of records, while the field taxonomy remains fixed at 303 entries. The extraction is performed jointly over the relational and graph components. We first sample anchor structures, such as paper references, and then derive the required paper, author, field, affiliation, and external-evidence entities from the retained identifiers. Dependent edges and relational tables are filtered using the same identifiers or deterministic key-based sampling over join attributes. This procedure preserves referential integrity and joinability across the two representations while making the scale factors reproducible. It also maintains graph consistency by retaining only edges with valid source and target identifiers and constructing graph projections from incident vertices, thereby avoiding isolated vertices in the evaluated graphs. Meanwhile, metadata required for relational joins remains available as structured tables or vertex attributes.

4.4

Series

Queries

Description

H

H1–H3 H4–H6 H7–H9 H10–H12 H13–H15 H16–H18 H19–H21 H22–H24

Many joins / Multiple subgraphs / Multi-hop Many joins / Multiple subgraphs / Single-hop Many joins / Single subgraph / Multi-hop Many joins / Single subgraph / Single-hop Few joins / Multiple subgraphs / Multi-hop Few joins / Multiple subgraphs / Single-hop Few joins / Single subgraph / Multi-hop Few joins / Single subgraph / Single-hop

S

S1–S5

Shortest-path search combined with relational joins

G

G1–G2 G3–G4 G5–G6 G7–G8

Multiple subgraphs / Multi-hop Multiple subgraphs / Single-hop Single subgraph / Multi-hop Single subgraph / Single-hop

U

U1–U2 U3–U4 U5–U6

Vertex-only insertion/deletion Edge insertion/deletion Vertex and incident-edge insertion/deletion

R

RH1–RH24 RG1–RG8

Relational equivalents of H-series queries Relational equivalents of G-series queries

can substantially affect intermediate result cardinalities, making the query a compact test of whether the optimizer can apply selective predicates early and coordinate graph-derived results with relational execution. Example 1. Retrieve papers with fewer than 150 citations that are referenced by a selected paper, together with newsfeed and Nobellaureate records associated with that paper. SELECT MIN(Citation.cited_id), MIN(Feed.newsfeed_id), MIN(NL.laureate_id) 3 FROM GRAPH_TABLE( 4 sciscinet_graph 5 MATCH (src IS Papers)-[r IS References]-> 6 (dst IS Papers) -- pattern matching 7 WHERE src.paperid = 'W2122344208' 8 AND dst.citation_count < 150 -- filtering 9 COLUMNS (src.paperid AS src_id, dst.paperid AS cited_id) 10 ) AS Citation 11 JOIN GRAPH_TABLE( 12 sciscinet_graph 13 MATCH (p IS Papers)-[n IS LinkNewsFeed]-> 14 (f IS NewsFeed) -- pattern matching 15 COLUMNS (p.paperid AS paperid, f.newsfeed_id AS newsfeed_id) 16 ) AS Feed 17 ON Citation.src_id = Feed.paperid -- graph-result join 18 JOIN NobelLaureates AS NL 19 ON Citation.src_id = NL.paperid; -- relational join 1 2

Workload Design

GRBench organizes its workload into five query series, as summarized in Table 1. All series share the same schema and scaled instances, allowing performance differences to be interpreted through controlled changes in query structure. The examples below use compact SQL/PGQ skeletons from the executable workload. They retain the core filtering, join, pattern matching, shortest-path search, and update operations. For each H-, S-, and G-series query template, we define three predicate-selectivity variants, denoted by the suffixes a, b, and c. Averaged across all query templates, the selectivities of the three variants are 45.19%, 33.15%, and 4.01%, respectively. The corresponding R-series translations retain the same suffixes. H-series: Graph-relational Hybrid Queries. The H-series follows a 2 × 2 × 2 design over relational-join intensity (few or many), the number of matched subgraphs (single or multiple), and graph pattern depth (single- or multi-hop). This factorial design enables controlled analysis of how relational joins interact with graph pattern matching. For instance, Example 1 instantiates the few-join, multiple-subgraph, single-hop design cell with two matched subgraphs and two joins: one join combines the two graph query results, and the other associates the combined result with a relational table. The optimizer may vary when to apply the vertex predicates, the order in which to evaluate the two graph patterns, and when to perform the graph query result and relational joins. These choices

S-series: Operator Scalability Queries. The S-series evaluates whether database systems can extend their graph processing support beyond pattern matching to additional graph operators and execute these operators efficiently. We use shortest-path search as the representative operator because it is one of the most widely used graph operations beyond pattern matching and requires systems to support topology expansion beyond fixed graph patterns. The five templates cover bounded and unbounded shortest paths, the composition of path results with other query relations, and cost-based path search. Their variants modify endpoint constraints and path cases, enabling controlled analysis of operator efficiency 5

U-series: Update Capability Queries. The U-series contains six update tasks, each organized as a deletion–insertion pair over the same records. The tasks cover isolated vertex updates, edge updates, and dependency-aware vertex updates that also modify incident edges, enabling controlled evaluation of both direct modification cost and consistency maintenance overhead. Example 4 removes and restores the batch of paper–author edges listed in grbench_update5_papers_to_authors. Using the same batch keeps the update scope fixed, allowing deletion and insertion costs to be compared under identical data conditions. Graph pattern queries executed before and after each operation verify that the logical graph view reflects the update. The task evaluates whether a system can maintain edge records, endpoint references, and topologyrelated structures consistently and efficiently.

under different search spaces and binding conditions. Example 2 combines a bounded ANY SHORTEST search over 1 to 4 hops with a single-hop contribution pattern and one join between the two graph query results. The source and destination predicates constrain the path endpoints, while the join composes the shortest-path result with paper–institution bindings produced by graph pattern matching. This combination evaluates whether a system can extend its graph-processing architecture beyond pattern matching to support shortest-path search and whether the operator can be executed efficiently when integrated with graph-derived relations. Example 2. Retrieve institutions with productivity above 8,000 that are reachable from institution I4210136388 by a shortest association path of 1 to 4 hops and that have contributed papers. SELECT MIN(Contribution.institutionid) FROM GRAPH_TABLE( 3 sciscinet_graph 4 MATCH path = ANY SHORTEST 5 (src IS Affiliations)-[af IS Associated]->{1,4} 6 (dst IS Affiliations) -- shortest-path search 7 WHERE src.institutionid = 'I4210136388' 8 AND dst.productivity > 8000 -- endpoint filtering 9 COLUMNS (dst.institutionid AS institutionid) 10 ) AS Reachable 11 LEFT JOIN GRAPH_TABLE( 12 sciscinet_graph 13 MATCH (paper IS Papers)-[cf IS ContributedFrom]-> 14 (inst IS Affiliations) -- pattern matching 15 COLUMNS ( 16 paper.paperid AS paperid, 17 inst.institutionid AS institutionid 18 ) 19 ) AS Contribution 20 ON Reachable.institutionid = 21 Contribution.institutionid; -- graph-result join 1

Example 4. Remove a predefined batch of paper–author relationships and subsequently restore the same relationships.

2

DELETE FROM Papers_to_Authors AS E WHERE EXISTS ( 3 SELECT 1 4 FROM grbench_update5_papers_to_authors AS U 5 WHERE U.paperid = E.paperid AND U.authorid = E.authorid 6 ); -- edge deletion 7 INSERT INTO Papers_to_Authors 8 SELECT * 9 FROM grbench_update5_papers_to_authors; -- edge insertion 1 2

R-series: Relational-only Equivalents. The R-series translates selected H- and G-series queries into relational-only formulations over vertex and edge tables. Each translation preserves the semantics of the original query. This paired design provides a controlled baseline for assessing whether each system’s graph query processing design delivers measurable performance benefits over semantically equivalent join-based relational execution. For instance, Example 5 translates the GRHQ in Example 1 by replacing its two graph patterns with relational joins. The one-hop citation pattern becomes joins among Papers and References, while the paper–newsfeed pattern becomes joins through LinkNewsFeed.

G-series: Pure Graph Queries. The G-series follows a 2 × 2 design over the number of matched subgraphs (single or multiple) and pattern depth (single- or multi-hop), with two query templates in each design cell. By excluding relational joins, this series evaluates graph query execution at the operator level and isolates the efficiency of graph pattern matching from graph-relational composition. Example 3 instantiates the single-subgraph, multi-hop design cell with one four-hop association pattern. The query requires the system to apply vertex filtering and execute a fixed-depth graph pattern entirely within graph processing. Its performance therefore reflects graph query operator efficiency and provides an operator-level baseline for the corresponding H-series queries.

Example 5. Retrieve the same papers, newsfeed records, and Nobellaureate records as Example 1 using only relational joins. SELECT MIN(dst.paperid), MIN(NF.newsfeed_id), MIN(NL.laureate_id) 3 FROM Papers AS src 4 JOIN References AS R ON src.paperid = R.citing_paperid 5 JOIN Papers AS dst ON R.cited_paperid = dst.paperid 6 AND dst.citation_count < 150 7 JOIN LinkNewsFeed AS LNF ON src.paperid = LNF.paperid 8 JOIN NewsFeed AS NF ON LNF.newsfeed_id = NF.newsfeed_id 9 JOIN NobelLaureates AS NL ON src.paperid = NL.paperid 10 WHERE src.paperid = 'W2122344208'; 1 2

Example 3. Retrieve institutions that are exactly four association hops away from institutions whose identifiers begin with I42101230. SELECT MIN(G.dst_id) FROM GRAPH_TABLE( 3 sciscinet_graph 4 MATCH (src IS Affiliations)-[e1 IS Associated]-> 5 (m1 IS Affiliations)-[e2 IS Associated]-> 6 (m2 IS Affiliations)-[e3 IS Associated]-> 7 (m3 IS Affiliations)-[e4 IS Associated]-> 8 (dst IS Affiliations) -- pattern matching 9 WHERE src.institutionid LIKE 'I42101230%'-- vertex filtering 10 COLUMNS (dst.institutionid AS dst_id) 11 ) AS G; 1

Example 6 translates the pure graph query in Example 3. Its four-hop association pattern becomes an alternating sequence of joins over Affiliations vertices and Associated edges. Because the original query contains no relational composition, this pair directly compares graph pattern matching with join-based relational evaluation at the graph-query operator level.

2

Example 6. Retrieve the same four-hop associated institutions as Example 3 using relational joins. 6

SELECT MIN(a4.institutionid) FROM Affiliations AS a0 3 JOIN Associated AS e1 4 ON a0.institutionid = e1.institution_id 5 JOIN Affiliations AS a1 6 ON e1.associated_institution_id = a1.institutionid 7 JOIN Associated AS e2 8 ON a1.institutionid = e2.institution_id 9 JOIN Affiliations AS a2 10 ON e2.associated_institution_id = a2.institutionid 11 JOIN Associated AS e3 12 ON a2.institutionid = e3.institution_id 13 JOIN Affiliations AS a3 14 ON e3.associated_institution_id = a3.institutionid 15 JOIN Associated AS e4 16 ON a3.institutionid = e4.institution_id 17 JOIN Affiliations AS a4 18 ON e4.associated_institution_id = a4.institutionid 19 WHERE a0.institutionid LIKE 'I42101230%';

are created automatically. ArangoDB query language (AQL) provides native traversal and path operators over named or anonymous graphs, with controls for direction, depth, and traversal strategy.

1 2

5

AgensGraph [1]. Built on PostgreSQL’s storage and transaction infrastructure, AgensGraph is a multi-model database supporting relational, document, and graph models. Property graphs use vertex and edge labels, with hierarchical label organization and indexes on both vertices and edges. SQL and openCypher can be used independently or combined within a single query, while both query modes share the same underlying database infrastructure. Both modes execute within the same PostgreSQL-derived engine. OrientDB [46]. OrientDB supports graph, document, key-value, and object models over a common record store. Regular edges are separate records linked from both endpoint vertices, whereas lightweight edges are stored as direct links inside vertex records. Its SQL dialect provides MATCH and TRAVERSE for link navigation, and indexed predicates can locate starting records before traversal.

SYSTEM LANDSCAPE

This section reviews representative systems that support graphrelational data management, mainly focusing on where graph storage and execution are integrated in the original system.

5.1

5.3

Relational Systems with Graph Extensions

Kùzu [14]. Kùzu is a disk-based, columnar graph DBMS based on a structured property-graph model and the Cypher query language. Node properties are stored in column files, while graph topology and relationship properties are double-indexed in forward and backward CSR adjacency structures. Its factorized query processor provides binary and worst-case-optimal join operators for manyto-many, cyclic, and recursive graph patterns.

These systems retain relational storage and add graph interfaces or execution components above an existing relational engine. Vertexica [29]. Vertexica layers Pregel’s vertex-centric computation model [37] over Vertica [32]. It stores vertices, edges, and inter-superstep messages in three relational tables, while a stored procedure coordinator invokes parallel worker user-defined functions (UDFs). Graph algorithms are thereby compiled into SQL/UDF workflows and executed by the unmodified relational engine.

GRFusion [22]. Built into the in-memory relational engine of VoltDB [49], GRFusion introduces first-class graph views. Vertex and edge properties remain in relational storage, whereas graph topology is maintained in adjacency-list indexes. During query execution, VertexScan, EdgeScan, and PathScan produce tuples that are connected to relational operators through binding joins.

PostgreSQL with Apache AGE [2, 6]. AGE creates a PostgreSQL namespace for each graph and stores vertex and edge labels in label-specific tables derived from parent vertex and edge tables. Cypher statements embedded in cypher() are parsed and transformed into PostgreSQL query tree nodes, while graph entities and properties are represented with agtype. These query trees are planned and executed by PostgreSQL. The returned SETOF record can be composed with ordinary SQL relations.

GRainDB [27, 28]. Rather than materializing a separate graph store, GRainDB retains DuckDB’s relational tables and columnar executor. For each declared relationship, system-level row identifiers are stored in extended tables, with optional adjacency-list-like RID indexes. Graph traversal is then evaluated through predefined RID-based joins over this metadata.

DuckDB with DuckPGQ [4, 5, 51]. DuckPGQ defines property graphs over existing typed vertex and edge tables without duplicating the base data. The extension adds SQL/PGQ parsing, vectorized UDFs, and graph-specific data structures and algorithms that are injected into DuckDB plans. Fixed patterns reuse DuckDB’s relational execution, while path queries can build an on-the-fly compressed sparse row (CSR) representation [19].

5.2

Native Graph-relational Systems

Systems in this group integrate graph-specific storage and execution mechanisms directly into the database core, including graphrelational designs and Kùzu as a native graph database reference.

RelGo [36]. Using relational tables as its physical storage layer, RelGo stores vertices and edges while exposing topology through RID-based graph indexes. Its execution model represents graphrelational queries as selection, projection, join, and match plans, retaining an explicit matching operator rather than immediately lowering graph patterns into joins. The resulting physical plan is encapsulated as a graph-table scan in DuckDB.

Graph-native Multi-model Systems

These systems natively support the graph model alongside other models, sharing storage or execution infrastructure rather than exposing graph functionality as an extension to a relational engine.

Chimera [33]. In contrast to the relational-storage designs above, Chimera adopts a dual-store architecture that places topology in a native graph store and properties in PostgreSQL. A bijective mapping links graph records to relational tuples. The TraversalJoin operator combines topology traversal, relational joining, and graph-relational mapping within a single execution abstraction.

ArangoDB [3]. ArangoDB stores vertices as documents in vertex collections and edges as documents in edge collections. Each edge carries _from and _to endpoint references, for which edge indexes 7

5.4

Graph-relational Query Acceleration

• End-to-end Latency. For a query 𝑄, L (𝑄) denotes the wall-clock time from submission to complete result materialization. For a query set 𝐶, we report the geometric mean: ! 1 ∑︁ ln L (𝑄) . (1) L𝐺𝐸𝑂 (𝐶) = exp |𝐶 | 𝑄 ∈𝐶

Reuse of Relational Execution. Vertexica obtains parallelism from Vertica’s worker UDF execution, while AGE and AgensGraph mainly reuse the scans, joins, indexes, and planning infrastructure of their underlying relational engines. DuckPGQ further uses vectorized graph functions: bounded SQL/PGQ patterns are translated into relational plans, while path queries use vectorized path algorithms over an on-demand CSR representation. These approaches benefit from mature relational execution, although long or cyclic patterns may still expand into costly join plans [15, 51].

• Graph-relational Speedup. For an H- or G-series query 𝑄 and its R-series equivalent 𝑅𝑄, we use L (𝑅𝑄)/L (𝑄) as the speedup. A value above one indicates faster graph-based execution. • Query Language Conciseness. We express each query in the native form supported by each system and quantify conciseness using Halstead-style complexity metrics [20]. After removing comments and normalizing formatting, a unified tokenizer counts distinct operators 𝑛 1 , distinct operands 𝑛 2 , and their total occurrences 𝑁 1 and 𝑁 2 . We compute:

Topology-aware Graph Processing. ArangoDB accelerates traversal through endpoint and vertex-centric indexes, traversal pruning, and configurable search strategies. OrientDB’s MATCH executor selects indexed starting records before following graph links. GRFusion provides native scan and path operators, while GRainDB replaces value-based joins with predefined RID joins and propagates bitmap filters through sideways information passing (SIP). Kùzu targets many-to-many and cyclic patterns through factorized execution with binary and worst-case-optimal joins.

𝑛 = 𝑛 1 + 𝑛 2,

𝑁 = 𝑁 1 + 𝑁 2, V = 𝑁 log2 𝑛, (2) 𝑛1 𝑁2 D= × , E = D × V, 2 𝑛2 where V, D, and E denote query volume, difficulty, and estimated effort, respectively. Lower values indicate more concise formulations for the same logical task. • CPU and Memory Utilization. For each query 𝑄, we sample CPU and memory usage during execution and record their average and peak values. CPU is reported as equivalent utilized cores, where 100% corresponds to one core, and memory in GB. These metrics distinguish efficient execution from low latency achieved through greater resource consumption.

Cross-model Query Optimization. RelGo retains graph matching in selection, projection, join, and match plans, applies graph-specific decomposition and rewrite rules, and maps matching operations to expansion and expansion-intersection operators before relational optimization. Chimera constructs Traversal-Join graphs and uses dynamic programming to enumerate plans that interleave graph traversal, relational joins, and graph-relational mappings. These designs optimize cross-model orderings instead of relying on graphagnostic relational planning.

6

Implementation Details. Experiments run on a server with two Intel Xeon Platinum 8352V CPUs (2.10 GHz, 72 physical cores and 144 threads), 512 GiB DDR4 memory, and Ubuntu 22.04.5 LTS. All systems use default configurations in Docker containers without CPU or memory limits. DuckDB therefore uses 144 threads by default. Before execution, we construct system-specific indexes and auxiliary structures, including primary-key indexes on relational tables, adjacency structures, and predefined-join indexes for graph processing. For each system, we run the complete workload three times in fixed order without restarting or clearing database and operating system caches, and report median latency. Later repetitions benefit from a warmed execution environment. Each query is limited to five hours (18,000 seconds), with timeouts recorded as 18,000 seconds. For each query, we verify that all systems produce identical results to ensure semantic equivalence across implementations.

EXPERIMENTS

In this section, we systematically evaluate the dimensions introduced in Section 3.2 to answer the following research questions: • (RQ1) How do existing systems perform on GRHQs overall, and which design choices explain their efficiency advantages? • (RQ2) How extensible is graph query support, and can their architectures incorporate operations beyond pattern matching? • (RQ3) How efficiently do existing systems execute graph pattern matching at the operator level? • (RQ4) How efficiently do systems process graph updates, and can they preserve consistency during updates? • (RQ5) Compared with equivalent relational execution, do graph query designs deliver measurable performance gains? Furthermore, we examine how data scale and predicate selectivity affect query execution in Sections 6.7–6.8, and evaluate querylanguage conciseness and resource utilization in Sections 6.9–6.10.

6.1

6.2

Efficiency on GRHQs (RQ1)

We evaluate all seven systems on 24 H-series GRHQs and report their latencies in Figure 3. We make the following observations: (1) PostgreSQL with AGE shows the highest latency in most H-series queries, especially with multiple graph subqueries or multi-hop patterns. AGE exposes Cypher execution through the set-returning cypher() interface, and graph results are composed through PostgreSQL joins. This separation between graph execution and relational composition introduces overhead when multiple graphderived relations interact. (2) OrientDB achieves the lowest latency in most queries, while DuckDB performs best in the remaining cases. OrientDB’s advantage mainly appears with exact identifier

Experimental Setup

Systems Under Test. Since not all systems surveyed in Section 5 are open source, we evaluate all open-source systems among them, as shown in Figure 1(d). Specifically, we use PostgreSQL 15.6 with Apache AGE 1.6.0, DuckDB 1.2.2 with DuckPGQ (commit 97a0c65), ArangoDB 3.12.4, AgensGraph 2.16, OrientDB Community 3.2.37, GRainDB (commit be901b3), and Kùzu 0.11.3. Evaluation Metrics. We evaluate all comparisons from: 8

PostgreSQL

DuckDB

ArangoDB

AgensGraph

Latency (s)

(a) Many joins / Multiple subgraphs / Multi-hop (b) Many joins / Multiple subgraphs / Single-hop 10

102 10

Kùzu

(d) Many joins / Single subgraph / Single-hop 100

101 10 10−1

10−1

10−2

H1

H2

H3

(e) Few joins / Multiple subgraphs / Multi-hop

Latency (s)

GRainDB

100

1

100

101 10

OrientDB

(c) Many joins / Single subgraph / Multi-hop

1

10−1

10−1

10−1 H4

H5

H6

H7

(f) Few joins / Multiple subgraphs / Single-hop

101

H8

H9

10−1

10−2 H13

H14

H15

H16

H17

Query

H18

H12

1

100

10−1

10−1

H11

(h) Few joins / Single subgraph / Single-hop 10

100

10−2

H10

(g) Few joins / Single subgraph / Multi-hop 101

100

0

0

H19

H20

Query

H21

H22

H23

Query

H24

Query

Figure 3: Geometric mean latency across the three predicate-selectivity variants of each H-series query at 𝑆𝐹 = 101 . PostgreSQL

DuckDB

(a) Multiple subgraphs / Multi-hop

ArangoDB

AgensGraph

(b) Multiple subgraphs / Single-hop

OrientDB

GRainDB

(c) Single subgraph / Multi-hop 10

Latency (s)

Kùzu (d) Single subgraph / Single-hop

1

100

100

100

100 10−1

10

−1

10−1

10−1 G1

Query

G2

G3

Query

G4

G5

Query

G6

G7

Query

G8

Figure 4: Geometric mean latency across the three predicate-selectivity variants of each G-series query at 𝑆𝐹 = 101 . Table 2: S-series latency (seconds) at 𝑆𝐹 = 101 . Systems

S1

S2

S3

S4

S5

PostgreSQL DuckDB ArangoDB AgensGraph OrientDB GRainDB Kùzu

4.73E−01 1.03E−01 4.00E−01 1.11E−01 2.05E−02 – 3.66E−02

7.42E−02 1.01E−01 3.16E+00 5.76E−02 1.66E−01 – 2.33E−02

2.80E+00 1.65E−01 3.44E−01 1.15E+00 2.03E−01 – 1.62E−01

7.18E−02 7.82E−02 3.94E−01 4.54E−02 1.24E−02 – 3.32E−02

1.90E+01 1.37E−01 3.39E−01 1.74E+01 2.86E−02 – 1.44E−02

GRainDB supports variable-length path patterns through recursive common table expressions but does not implement the shortestpath semantics required by the S-series. This shows that efficient pattern matching does not necessarily imply extensibility to additional graph operators. (2) No implementation dominates all S1–S5 queries at 𝑆𝐹 = 101 : Kùzu achieves the lowest latency on S2, S3, and S5, while OrientDB performs best on S1 and S4. Both systems provide native path operators, while DuckPGQ uses an on-demand CSR representation with vectorized path search, and AGE and AgensGraph rely on PostgreSQL-backed path expansion. Although these designs all support shortest-path processing at this scale, their different execution mechanisms may exhibit different scaling behavior as the graph grows, which we examine in Section 6.7.

predicates, where the starting vertex can be located before traversal through its MATCH execution and indexes. (3) H10–H12 and H22– H24 show a different pattern. DuckDB achieves the lowest latency, while OrientDB and ArangoDB become less competitive. These queries use prefix predicates rather than exact identifiers, preventing direct binding of a starting vertex before traversal. DuckPGQ translates SQL/PGQ graph patterns into DuckDB plans for execution within the relational framework. (4) DuckDB maintains consistently low latency across H-series structures. DuckPGQ lowers graph patterns into DuckDB’s relational execution framework, allowing graph matching to reuse existing relational operators and benefit from its vectorized execution model. (5) Join count, matched-subgraph count, and hop depth affect systems differently rather than producing a monotonic trend. PostgreSQL becomes increasingly costly with more graph-relational composition, while GRainDB remains relatively stable across query structures. Its predefined joins and RID-based access paths reduce repeated relationship expansion, showing that GRHQ efficiency depends on how systems integrate graph and relational execution.

6.3

6.4

Pure Graph Query Performance (RQ3)

We evaluate all systems on the 8 pure-graph G-series queries at 𝑆𝐹 = 101 and report their latencies in Figure 4. Observations: (1) DuckDB achieves the lowest latency across most G-series queries. This is because DuckPGQ lowers SQL/PGQ graph patterns into DuckDB’s relational execution framework, allowing graph matching to reuse its vectorized parallel execution engine without a separate graph execution layer. (2) PostgreSQL is competitive on selected queries such as G1, G5, and G8, but becomes substantially slower on G2–G4 and G6–G7. For multi-subgraph queries, AGE processes multiple graph matching results through the cypher() interface before aggregation, increasing overhead as intermediate results grow. (3) OrientDB performs well on selected anchored queries such as G7 and G8, but becomes less competitive on queries such as G3 and G4. Its traversal execution benefits from selective starting points and direct navigation, but provides less advantage when graph patterns produce larger intermediate results or multiple results must be combined. (4) ArangoDB and GRainDB show relatively stable but moderate performance across G-series structures. This indicates

Graph Operator Scalability (RQ2)

Table 2 reports the geometric-mean latency across the three predicateselectivity variants of each S-series query at 𝑆𝐹 = 101 . Observations: (1) GRainDB is the only system unable to execute any S-series query. 9

Table 3: Update latency at 𝑆𝐹 = 102 (seconds). The task templates are grouped by update type: U1–U2 are vertex-only updates, U3–U4 update edges, and U5–U6 update vertices with their incident edges. Each template has deletion and insertion variants. Dark and light green denote the fastest and second-fastest results, respectively. “–” denotes unavailable measurements. Deletion

Systems PostgreSQL DuckDB ArangoDB AgensGraph OrientDB GRainDB Kùzu

U2

U3

U4

U5

U6

U1

U2

U3

U4

U5

U6

– 1.68E+00 1.31E+02 – 1.80E+04 3.89E+01 2.74E+03

– 5.72E−01 2.59E+02 – 4.02E+03 4.00E+01 8.51E+01

2.04E+02 4.95E+00 5.37E+02 2.13E+03 5.19E+03 7.53E+01 7.83E−01

5.05E+01 1.16E+00 4.38E+02 1.54E+03 1.31E+03 6.31E+01 2.31E−01

8.08E+02 1.64E+01 1.77E+03 1.80E+04 1.80E+04 3.53E+02 3.19E+02

8.16E+01 4.88E+00 8.73E+02 5.86E+03 1.60E+03 1.90E+02 5.14E+01

– 7.41E+00 1.25E+02 – 6.26E+03 5.88E+00 1.47E+01

– 3.88E+00 2.39E+02 – 1.29E+03 6.09E+00 6.29E+00

2.96E+01 4.73E+00 2.66E+02 1.19E+03 2.75E+03 1.21E+01 2.34E+01

6.38E+00 3.14E+00 3.42E+02 8.22E+02 9.56E+02 9.13E+00 1.97E+01

1.53E+02 2.01E+01 1.15E+03 1.71E+04 6.45E+03 7.10E+01 1.02E+02

8.37E+00 5.49E+00 5.92E+02 3.67E+03 9.31E+02 4.61E+01 2.90E+01

PostgreSQL

DuckDB

ArangoDB

AgensGraph

OrientDB

(a) GRHQ speedup over relational equivalents

1065 104 103 102 10

Speedup

Insertion

U1

1054 103 102 10

100

100

10−1

10−1

10−2

GRainDB

Kùzu

(b) Pure graph speedup over relational equivalents

10−2 H1-H3

H4-H6

H7-H9

H10-H12

Query

H13-H15

H16-H18

H19-H21

H22-H24

G1-G2

G3-G4

Query

G5-G6

G7-G8

Figure 5: Speedup over relational equivalents for H- and G-series queries. that graph-native storage or predefined access structures alone do not determine latency, which also depends on starting predicates and intermediate result sizes. (5) Hop depth and matched-subgraph count do not cause monotonic latency growth. For example, G6 has a deeper pattern than G5 but does not incur proportionally higher latency, while G2 is much slower than G1 despite sharing the same structural category. Thus, intermediate result cardinality and execution strategy can matter more than hop count alone.

6.5

not support the standalone vertex deletions in U1 and U2 because both systems reject deleting vertices that still have incident edges.

6.6

Speedup over Relational Equivalents (RQ5)

To quantify graph-oriented execution benefits, we compare each H- and G-series query with its equivalent relational formulation in the R-series at 𝑆𝐹 = 101 . For each group, Figure 5 reports the geometric mean of the graph-relational speedup over its queries and three selectivity variants. We make the following observations: (1) PostgreSQL with AGE remains below the break-even line for every H- and G-series group. AGE translates Cypher into PostgreSQL plans over vertex and edge label tables and represents graph values with agtype. Fixed-depth patterns incur Cypher translation and graph-type handling while still executing on relational storage, whereas the relational equivalents directly join typed identifiers. The G-series results show that the disadvantage stems from AGE’s graph representation and MATCH execution, not only from composing cypher() outputs with SQL. (2) DuckDB and ArangoDB remain close to, but mostly below, the break-even line. DuckPGQ lowers SQL/PGQ patterns into plans over the same DuckDB base tables as the relational equivalents, so the graph formulation gains no separate graph access path while incurring additional lowering and extension-processing overhead. In ArangoDB, native traversal and join-based AQL both exploit the automatically maintained _from and _to indexes for endpoint lookup, so the shallow, fixeddepth patterns incur similar access costs and exhibit comparable latency. (3) OrientDB exceeds the break-even line across nearly all H- and G-series groups, while GRainDB does so in many groups and AgensGraph only in selected cases. OrientDB’s MATCH executor can select indexed starting vertices before navigating graph links, while GRainDB replaces joins on identifier values with predefined RID joins and optional RID indexes. These graph-aware access paths avoid the repeated identifier-based joins required by the relational translations. In the inspected AgensGraph plans, graph query results are materialized before outer joins, and one intermediate sort

Graph Update Performance (RQ4)

We evaluate the paired U-series deletion and insertion tasks at 𝑆𝐹 = 102 and report their query-level latencies in Table 3. We make the following observations: (1) DuckDB is fastest on most insertion and deletion tasks. This is because it defines a property graph directly over its vertex and edge tables, so the measured graph updates are ordinary relational INSERT and DELETE operations on the underlying tables and require no synchronization with a separate graph copy. (2) Kùzu and GRainDB achieve the best or second-best latency on many U-series tasks. In particular, GRainDB consistently outperforms ArangoDB, AgensGraph, and OrientDB across all measured deletion and insertion tasks. Kùzu stores graph topology in native CSR-based adjacency structures, allowing topology updates to operate directly on its graph storage. GRainDB reuses DuckDB’s table-update path but additionally maintains materialized RID references and optional RID indexes, making its deletion latencies 4.1–6.9× higher than the corresponding insertion latencies. (3) ArangoDB, AgensGraph, and OrientDB generally exhibit substantially higher update latencies, with AgensGraph and OrientDB frequently forming the slowest tier. ArangoDB maintains edge collections and the automatic indexes on their _from and _to fields, while OrientDB removes edge references from both endpoint vertices. AgensGraph stores vertices and edges in PostgreSQL label tables and enforces consistency between them. These additional index and topology maintenance operations contribute to their higher bulk update costs. (4) PostgreSQL with AGE and AgensGraph do 10

PostgreSQL

DuckDB

Latency (s)

(a) H1-H3

10

100 102

101

102

104

103

104

10

2

10

2

10

0

100

100 10−1 100

101

102

103

104

100

10

10

10

2

10

3

10

4

102

103

104

10−2

100

101

(i) RG3-RG4

102

103

104

(j) RG7-RG8 103

102 101

100

100

10−2 1

101

(h) RH22-RH24 102

0

(e) G7-G8

102

(g) RH16-RH18

104

10

4

101

10−1 100

Kùzu

103

100

(f) RH1-RH3

GRainDB (d) G3-G4

101

0

104

103

OrientDB

102

102

102

101

AgensGraph (c) H22-H24

104

104

100

Latency (s)

ArangoDB

(b) H16-H18

10

0

10

1

SF

10

2

10

3

10

4

10−1

10−2 10

0

10

1

10

SF

2

10

3

10

4

10

0

10

1

SF

10

2

10

3

10

4

100

101

SF

102

103

104

SF

Figure 6: Impact of data scale on representative H- and G-series query groups and their relational equivalents. Table 4: Relative predicate-selectivity response for represenPostgreSQL DuckDB ArangoDB AgensGraph tative H-, G-, and S-series queries at 𝑆𝐹 = 101 . OrientDB GRainDB Kùzu Latency (s)

(a) S2

(b) S3

(c) S5

104

104

104

102

10

2

102

100

100 100

101

102

103

104

Systems PostgreSQL DuckDB ArangoDB AgensGraph OrientDB GRainDB Kùzu

100

100

101

SF

102

SF

103

10−2 104 100

101

102

103

104

SF

Figure 7: Impact of data scale on representative S-series queries (seconds). spills to disk, which limits its speedup for some query structures. (4) Kùzu exposes only a Cypher-based graph query interface and has no semantically equivalent relational formulation. We therefore set its speedup to 1 as a reference value.

6.7

H3b H3c H10b H10c G1b G1c G4b G4c S3b S3c 0.88 0.99 0.99 0.86 0.25 1.00 1.10

0.07 0.99 0.98 0.85 0.50 0.96 0.87

0.78 0.97 1.00 0.88 0.99 1.00 0.96

0.64 0.63 0.99 0.70 1.07 0.83 0.95

0.95 1.29 1.00 0.93 0.69 0.97 1.06

0.81 1.18 1.00 0.92 0.68 3.54 0.95

0.96 0.91 0.99 0.88 0.09 1.00 1.03

0.50 0.70 0.99 0.61 0.02 0.18 1.03

0.99 1.01 0.61 0.60 0.96 0.87 0.54 0.02 0.96 0.02 – – 0.83 0.81

Impact of Data Scale on S-series. Figure 7 shows how data scale affects geometric mean latency across three predicate selectivity variants of representative S-series queries. Observations: (1) PostgreSQL exhibits the sharpest latency growth across S2, S3, and S5, while AgensGraph grows sharply on S3 and S5 but remains stable on S2. Their PostgreSQL-backed path execution can expand increasing traversal states and intermediate results as the graph grows. (2) ArangoDB scales well on S3 and S5 but deteriorates markedly on S2. This is because S2 searches from a fixed source toward predicateselected destinations, whereas ArangoDB’s shortest-path execution uses explicit source–destination traversal, causing the growing destination set to amplify repeated path-search work. (3) DuckDB remains comparatively stable across all three queries. DuckPGQ constructs an on-demand CSR representation and executes shortestpath search with vectorized graph algorithms, limiting repeated relational or traversal overhead as the graph expands.

Impact of Data Scale

Impact of Data Scale on H-, G-, and R-series. We evaluate scalability by varying the scale factor from 𝑆𝐹 = 100 to 𝑆𝐹 = 104 and report latency trends of representative H-, G-, and R-series workloads in Figure 6. At each scale, the first row reports geometric mean latency for each selected H- or G-series group, while the second reports that of corresponding relational equivalents. We observe that: (1) DuckDB shows the most stable scaling across workloads. This is consistent with DuckPGQ lowering graph patterns into DuckDB’s relational execution framework, allowing graph matching and relational operators to scale through the same execution engine. (2) PostgreSQL shows steep latency growth for H-series queries as scale increases, especially on H1–H3 and H16–H18. The increase mainly occurs in workloads with larger joins and graph-derived intermediate results, where AGE must materialize Cypher results before combining them with PostgreSQL relational execution. (3) Graph and relational formulations can exhibit substantially different scaling behavior. OrientDB’s H- and G-series queries remain competitive on several workloads, whereas their relational equivalents grow rapidly with scale. In contrast, GRainDB maintains relatively stable growth on graph queries by exploiting predefined relationships and RID-based access paths. (4) Increasing scale does not uniformly amplify the effect of hop depth or query structure. For example, some multi-hop queries scale better than shorter queries when intermediate results remain limited. Therefore, scalability is mainly determined by how systems handle intermediate graph results and relational composition rather than hop count alone.

6.8

Impact of Predicate Selectivity

We evaluate the effect of predicate selectivity using representative H-, G-, and S-series queries with three selectivity variants. Specifically, for each query 𝑄, we use L (𝑄𝑏 )/L (𝑄 𝑎 ) and L (𝑄𝑐 )/L (𝑄 𝑎 ) to quantify each system’s sensitivity to selectivity changes, where 𝑄 𝑎 , 𝑄𝑏 , and 𝑄𝑐 denote the three variants of 𝑄 with progressively lower predicate selectivities. Table 4 reports the resulting latency ratios. We make the following observations: (1) OrientDB shows the strongest response to predicate selectivity on several graph queries, with G4b and G4c reducing latency to 0.09 and 0.02 of their baseline values. PostgreSQL and AgensGraph also benefit substantially on selected queries, such as H3c and S3c, when selective predicates can be applied before graph expansion or pushed into scans and joins, thereby reducing starting vertices or intermediate results. In contrast, ArangoDB, most Kùzu cases, and several 11

Table 5: Language conciseness evaluation. H

Systems PostgreSQL DuckDB ArangoDB AgensGraph OrientDB GRainDB Kùzu

Volume Difficulty

Effort

Volume Difficulty

Effort

1.11E+03 9.95E+02 1.33E+03 1.22E+03 2.09E+03 8.43E+02 9.81E+02

3.43E+04 2.89E+04 4.60E+04 3.68E+04 9.68E+04 2.32E+04 2.64E+04

5.95E+02 5.42E+02 3.46E+02 6.54E+02 7.27E+02 4.03E+02 4.63E+02

1.69E+04 1.41E+04 7.67E+03 1.86E+04 2.19E+04 9.67E+03 9.86E+03

2.94E+01 2.81E+01 3.41E+01 2.88E+01 4.25E+01 2.66E+01 2.66E+01

H, G, and S than on R, while ArangoDB remains near 41 GB across read workloads. AGE carries Cypher results as agtype records, increasing memory pressure from graph intermediates, whereas ArangoDB’s RocksDB engine retains a hot set of data and indexes in memory, so cache allocation dominates its stable footprint. (3) Update workloads produce the highest memory peaks for OrientDB and GRainDB. OrientDB updates edge records together with references at both endpoint vertices, while GRainDB maintains base tuples, materialized RIDs, and RID indexes, causing batch updates to retain more topology state in memory.

G

2.52E+01 2.38E+01 1.89E+01 2.51E+01 2.58E+01 2.02E+01 2.03E+01

Table 6: Resource utilization (CPU: mean; MEM: peak). System

7

H (CPU, MEM) G (CPU, MEM) S (CPU, MEM) U (CPU, MEM) R (CPU, MEM)

PostgreSQL DuckDB ArangoDB AgensGraph OrientDB GRainDB Kùzu

(2.45, 47.9) (58.6, 3.49) (0.12, 41.4) (3.35, 25.1) (1.84, 6.70) (0.85, 31.5) (6.01, 10.7)

(1.73, 37.2) (55.9, 2.96) (0.13, 41.4) (3.35, 25.2) (1.40, 11.9) (0.68, 33.3) (5.03, 11.2)

(0.98, 73.7) (4.60, 0.69) (0.18, 41.7) (0.65, 0.11) (1.86, 12.3) –

(1.77, 1.29)

(0.95, 48.7) (8.16, 3.05) (1.04, 25.4) (0.30, 30.0) (1.72, 64.9) (0.62, 71.6) (2.74, 30.6)

(0.92, 6.39) (57.0, 2.40) (0.13, 41.0) (3.07, 0.92) (3.88, 25.2) (0.90, 29.8)

Based on our experimental results, we identify the following five open problems for graph-relational data management: • Joint Optimization of Graph and Relational Operators. Hseries performance varies substantially with join count, matched subgraphs, and intermediate-result size, exposing the limitations of optimizing graph and relational operators in isolation. A key challenge is to develop unified cardinality and cost models with plan-search strategies that jointly optimize graph pattern evaluation and graph-relational join orders. • Extensible Graph Operator Integration. The S-series shows efficient pattern matching does not necessarily extend to shortestpath processing. Graph operators therefore need common algebraic representations, plan organizations, statistics, and physical interfaces, allowing optimizers to compose, transform, and cost new operators without per-operator redesign. • Selectivity-aware Optimization. Predicate selectivity causes large, sometimes non-monotonic performance differences across systems. This motivates graph-aware cardinality estimation that captures how predicate effects propagate through starting vertices, graph expansion, joins, and intermediate results, enabling better predicate placement and traversal pruning. • Adaptive Graph vs. Relational Execution. Our relationalequivalent comparison shows graph execution is not consistently faster than relational joins. Optimizers should treat graph operators and relational joins as alternative physical implementations and choose based on query and data characteristics. • Update-oriented Graph-relational Storage and Consistency. The U-series shows that update cost and support depend on topology representation, from table-backed graphs to RID- and adjacency-based structures. An open problem is to maintain consistency across base records, topology structures, and auxiliary indexes while preserving update and query efficiency.

–

DuckDB cases remain close to one. In these queries, stricter predicates do not substantially reduce the starting set or prune graph expansion early, so similar scans and fixed-depth patterns still dominate execution. (2) G1b and G1c add an endpoint-property predicate absent from G1a, introducing additional property access and filtering. GRainDB reaches 3.54 on G1c, suggesting that the additional predicate changes the placement of filtering or join evaluation in its predefined relational access path; the exact cause requires execution plans. (3) S3 shows the strongest response in AgensGraph and OrientDB under the most selective variant, moderate sensitivity in DuckDB and Kùzu, and little change in PostgreSQL and ArangoDB. S3 places the predicate on the terminal vertex of a threehop citation pattern before joining the graph result with metadata relations. Systems that push it into traversal or graph result production can prune intermediates early, whereas broad fixed-depth scans or similar materialization gain less.

6.9

Query Language Conciseness

We compare the complexity of H and G query formulations and present their geometric mean in Table 5. Lower values indicate more concise query expressions. Observations: (1) GRainDB is the most concise for H-series queries, whereas OrientDB has the highest complexity. GRainDB compactly expresses graph patterns and composes bindings with SQL joins, while OrientDB nests MATCH, LET, and IN clauses for multiple graph outputs and joins, increasing both operator and operand counts. (2) ArangoDB is the most concise for G-series queries. Pure graph patterns map directly to compact AQL traversal constructs, whereas H-series formulations require additional LET subqueries and explicit join logic to compose graph results, increasing complexity.

6.10

OPEN PROBLEMS

8

CONCLUSIONS

In this work, we present GRBench, a comprehensive benchmark for graph-relational data management. GRBench combines a scalable real-world graph-relational dataset, purpose-built query series, and semantically equivalent native formulations to systematically evaluate representative database systems. Our evaluation reveals substantial differences across storage, execution, and optimization designs, with no single architecture consistently dominating all workloads. These results highlight the trade-offs of existing approaches and provide guidance for future graph-relational system design and optimization.

Resource Utilization

We measure the mean CPU utilization and peak memory usage across the five GRBench workload series at 𝑆𝐹 = 102 and report the geometric mean in Table 6. We make the following observations: (1) DuckDB consumes higher CPU resources than most systems, especially on H and G workloads. This higher utilization corresponds to its parallel execution model and is consistent with its low query latency. (2) PostgreSQL uses substantially more memory on 12

REFERENCES

[26] Alexandru Iosup, Tim Hegeman, Wing Lung Ngai, Stijn Heldens, Arnau PratPérez, Thomas Manhardt, Hassan Chafi, Mihai Capotă, Narayanan Sundaram, Michael Anderson, Ilie Gabriel Tănase, Yinglong Xia, Lifeng Nai, and Peter Boncz. 2016. LDBC Graphalytics: A Benchmark for Large-Scale Graph Analysis on Parallel and Distributed Platforms. Proc. VLDB Endow. 9, 13 (2016), 1317–1328. [27] Guodong Jin, Nafisa Anzum, and Semih Salihoglu. 2022. GRainDB: A Relationalcore Graph-Relational DBMS. 12th Conference on Innovative Data Systems Research, CIDR 2022. https://www.vldb.org/cidrdb/papers/2022/p57-jin.pdf [28] Guodong Jin and Semih Salihoglu. 2022. Making RDBMSs Efficient on Graph Workloads Through Predefined Joins. Proc. VLDB Endow. 15, 5 (2022), 1011–1023. [29] Alekh Jindal, Praynaa Rawlani, Eugene Wu, Samuel Madden, Amol Deshpande, and Michael Stonebraker. 2014. Vertexica: Your Relational Friend for Graph Analytics! Proceedings of the VLDB Endowment 7, 13 (2014), 1669–1672. [30] Bogyeong Kim, Kyoseung Koo, Undraa Enkhbat, Sohyun Kim, Juhun Kim, and Bongki Moon. 2022. M2bench: A database benchmark for multi-model analytic workloads. Proc. VLDB Endow. 16, 4 (2022), 747–759. [31] Hyunjoon Kim, Yunyoung Choi, Kunsoo Park, Xuemin Lin, Seok-Hee Hong, and Wook-Shin Han. 2021. Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching. In Proceedings of the 2021 International Conference on Management of Data. ACM, 925–937. [32] Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, Nga Tran, Ben Vandiver, Lyric Doshi, and Chuck Bear. 2012. The Vertica Analytic Database: C-Store 7 Years Later. Proc. VLDB Endow. 5, 12 (2012), 1790–1801. [33] Geonho Lee, Jeongho Park, and Min-Soo Kim. 2024. Chimera: A system design of dual storage and traversal-join unified query processing for SQL/PGQ. Proc. VLDB Endow. 18, 2 (2024), 279–292. [34] Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How Good Are Query Optimizers, Really? Proc. VLDB Endow. 9, 3 (2015), 204–215. [35] Zihang Lin, Yian Yin, Lu Liu, and Dashun Wang. 2023. SciSciNet: A Large-Scale Open Data Lake for the Science of Science Research. Scientific Data 10, Article 315 (2023). [36] Yunkai Lou, Longbin Lai, Bingqing Lyu, Yufan Yang, Xiaoli Zhou, Wenyuan Yu, Ying Zhang, and Jingren Zhou. 2024. Towards a Converged Relational-Graph Optimization Framework. Proc. ACM Manag. Data 2, 6 (2024), 252:1–252:27. [37] Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: a system for large-scale graph processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, Indiana, USA, June 6-10, 2010, Ahmed K. Elmagarmid and Divyakant Agrawal (Eds.). ACM, 135–146. [38] Wim Martens, Matthias Niewerth, Tina Popp, Carlos Rojas, Stijn Vansummeren, and Domagoj Vrgoc. 2023. Representing Paths in Graph Database Pattern Matching. Proceedings of the VLDB Endowment 16, 7 (2023), 1790–1803. [39] Sergi Nadal, Alberto Abelló, Oscar Romero, Stijn Vansummeren, and Panos Vassiliadis. 2023. Graph-Driven Federated Data Management. IEEE Transactions on Knowledge and Data Engineering 35, 1 (2023), 509–520. [40] Patrick E. O’Neil, Elizabeth J. O’Neil, Xuedong Chen, and Stephen Revilak. 2009. The Star Schema Benchmark and Augmented Fact Table Indexing. In Performance Evaluation and Benchmarking, First TPC Technology Conference, TPCTC 2009, Lyon, France, August 24-28, 2009, Revised Selected Papers (Lecture Notes in Computer Science), Raghunath Othayoth Nambiar and Meikel Poess (Eds.). Springer, 237– 252. [41] Anil Pacaci, Angela Bonifati, and M. Tamer Ozsu. 2022. Evaluating Complex Queries on Streaming Graphs. In 2022 IEEE 38th International Conference on Data Engineering. IEEE, 272–285. [42] Prashant Pandey, Brian Wheatman, Helen Xu, and Aydin Buluc. 2021. Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs. In Proceedings of the 2021 International Conference on Management of Data. ACM, 1372–1385. [43] George Papastefanatos, Marios Meimaris, and Panos Vassiliadis. 2022. Relational Schema Optimization for RDF-Based Knowledge Graphs. Information Systems 104 (2022), 101754. [44] Jason Priem, Heather A. Piwowar, and Richard Orr. 2022. OpenAlex: A Fullyopen Index of Scholarly Works, Authors, Venues, Institutions, and Concepts. CoRR abs/2205.01833 (2022). https://doi.org/10.48550/arXiv.2205.01833 [45] Shipeng Qi, Bing Tong, Jiatao Hu, Heng Lin, Yue Pang, Wei Yuan, Songlin Lyu, Zhihui Guo, Ke Huang, Xujin Ba, Qiang Yin, Youren Shen, Yan Zhou, Tao Lv, Jia Li, Lei Zou, Yongwei Wu, Gábor Szárnyas, Xiaowei Zhu, Wenguang Chen, and Chuntao Hong. 2025. The LDBC Financial Benchmark: Transaction Workload. Proc. VLDB Endow. 18, 9 (2025), 3007–3020. https://doi.org/10.14778/3746405. 3746424 [46] Daniel Ritter, Luigi Dell’Aquila, Andrii Lomakin, and Emanuele Tagliaferri. 2021. OrientDB: A NoSQL, Open Source MMDMS. In Proceedings of the British International Conference on Databases 2021 (CEUR Workshop Proceedings), Vol. 3163. CEUR-WS.org, 10–19. [47] Joshua Robinson, Rishabh Ranjan, Weihua Hu, Kexin Huang, Jiaqi Han, Alejandro Dobles, Matthias Fey, Jan E. Lenssen, Yiwen Yuan, Zecheng Zhang, Xinwei He, and Jure Leskovec. 2024. RelBench: A Benchmark for Deep Learning on Relational

[1] 2025. AgensGraph: Powerful Multi-Model Graph Database. https://github.com/ skaiworldwide-oss/agensgraph. [2] 2025. Apache AGE Graph Database for PostgreSQL. https://age.apache.org/. [3] 2025. ArangoDB: The Most Complete And Scalable Graph Database For Realworld Use Cases. https://arangodb.com/. [4] 2025. DuckDB: An in-process SQL OLAP database management system. https: //duckdb.org/. [5] 2025. DuckPGQ. https://duckpgq.org/. [6] 2025. PostgreSQL: The World’s Most Advanced Open Source Relational Database. https://www.postgresql.org/. [7] 2025. SciSciNet-v2: A Linked Dataset for Science of Science Research. https: //northwestern-cssi.github.io/sciscinet/. [8] Angelos Christos G. Anadiotis, Ioana Manolescu, and Madhulika Mohanty. 2023. Integrating Connection Search in Graph Queries. In 2023 IEEE 39th International Conference on Data Engineering. IEEE, 2607–2620. [9] Maciej Besta, Robert Gerstenberger, Emanuel Peter, Marc Fischer, Michal Podstawski, Claude Barthels, Gustavo Alonso, and Torsten Hoefler. 2024. Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries. Comput. Surveys 56, 2 (2024), 31:1–31:40. [10] Czech Technical University in Prague. 2021. STATS Dataset. https://relational. fit.cvut.cz/dataset/Stats. [11] Dean De Leo and Peter Boncz. 2021. Teseo and the Analysis of Structural Dynamic Graphs. Proceedings of the VLDB Endowment 14, 6 (2021), 1053–1066. [12] Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, Filip Murlak, Stefan Plantikow, Petra Selmer, Oskar van Rest, Hannes Voigt, Domagoj Vrgoc, Mingxi Wu, and Fred Zemke. 2022. Graph Pattern Matching in GQL and SQL/PGQ. In Proceedings of the 2022 International Conference on Management of Data. ACM, 2246–2258. [13] Orri Erling, Alex Averbuch, Josep Lluís Larriba-Pey, Hassan Chafi, Andrey Gubichev, Arnau Prat-Pérez, Minh-Duc Pham, and Peter Boncz. 2015. The LDBC Social Network Benchmark: Interactive Workload. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 619–630. https://doi.org/10.1145/2723372.2742786 [14] Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Salihoğlu. 2023. Kùzu Graph Database Management System. In 13th Conference on Innovative Data Systems Research (CIDR 2023). [15] Diego Figueira, Artur Jez, and Anthony W. Lin. 2022. Data Path Queries over Embedded Graph Databases. In Proceedings of the 41st ACM SIGMOD-SIGACTSIGAI Symposium on Principles of Database Systems. ACM, 189–201. [16] Ahmad Ghazal, Tilmann Rabl, Minqing Hu, Francois Raab, Meikel Poess, Alain Crolotte, and Hans-Arno Jacobsen. 2013. BigBench: Towards an Industry Standard Benchmark for Big Data Analytics. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM, 1197–1208. [17] Amélie Gheerbrant, Leonid Libkin, Liat Peterfreund, and Alexandra Rogova. 2025. GQL and SQL/PGQ: Theoretical Models and Expressive Power. Proceedings of the VLDB Endowment 18, 6 (2025), 1798–1810. https://doi.org/10.14778/3725688. 3725707 [18] Qingsong Guo, Chao Zhang, Shuxun Zhang, and Jiaheng Lu. 2024. Multi-model Query Languages: Taming the Variety of Big Data. Distributed and Parallel Databases 42 (2024), 31–71. [19] Pranjal Gupta, Amine Mhedhbi, and Semih Salihoglu. 2021. Columnar Storage and List-Based Processing for Graph Database Management Systems. Proceedings of the VLDB Endowment 14, 11 (2021), 2491–2504. [20] Maurice H. Halstead. 1977. Elements of Software Science. Elsevier, New York, NY, USA. [21] Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Jiangneng Li, and Bin Cui. 2021. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. Proc. VLDB Endow. 15, 4 (2021), 752– 765. [22] Mohamed S. Hassan, Tatiana Kuznetsova, Hyun Chai Jeong, Walid G. Aref, and Mohammad Sadoghi. 2018. Extending In-Memory Relational Database Engines with Native Graph Support. In Proceedings of the 21st International Conference on Extending Database Technology, EDBT 2018, Vienna, Austria, March 26-29, 2018. OpenProceedings.org, 25–36. [23] Yang He, Ruijie Fang, Isil Dillig, and Yuepeng Wang. 2025. Graphiti: Bridging Graph and Relational Database Queries. Proceedings of the ACM on Programming Languages 9, PLDI (2025), 1716–1740. [24] Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d’Amato, Gerard De Melo, Claudio Gutierrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, et al. 2021. Knowledge graphs. ACM Computing Surveys (Csur) 54, 4 (2021), 1–37. [25] IMDb.com, Inc. 2013. IMDB: Internet Movie Database. http://www.imdb.com/. The JOB data snapshot is hosted at http://homepages.cwi.nl/~boncz/job/imdb.tgz.

13

Databases. In Advances in Neural Information Processing Systems, Vol. 37. [48] Jifan Shi, Biao Wang, and Yun Xu. 2024. Spruce: A Fast yet Space-Saving Structure for Dynamic Graph Storage. Proceedings of the ACM on Management of Data 2, 1 (2024), 1–26. [49] Michael Stonebraker and Ariel Weisberg. 2013. The VoltDB Main Memory DBMS. IEEE Data Engineering Bulletin 36, 2 (2013), 21–27. [50] Gábor Szárnyas, Jack Waudby, Benjamin A. Steer, Dávid Szakállas, Altan Birler, Mingxi Wu, Yuchen Zhang, and Peter Boncz. 2022. The LDBC Social Network Benchmark: Business Intelligence Workload. Proc. VLDB Endow. 16, 4 (2022), 877–890. [51] Daniel ten Wolde, Gábor Szárnyas, and Peter Boncz. 2023. DuckPGQ: Bringing SQL/PGQ to DuckDB. Proc. VLDB Endow. 16, 12 (2023), 4034–4037. [52] Transaction Processing Performance Council. [n.d.]. TPC Benchmark C Standard Specification, Revision 5.11.0. https://www.tpc.org/tpcc/. Accessed: 2026-08-31. [53] Transaction Processing Performance Council. [n.d.]. TPC Benchmark DS Standard Specification, Revision 4.0.0. https://www.tpc.org/tpcds/. Accessed: 202608-31.

[54] Transaction Processing Performance Council. [n.d.]. TPC Benchmark H Standard Specification, Revision 3.0.1. https://www.tpc.org/tpch/. Accessed: 2026-08-31. [55] Ziting Wang, Shize Zhang, Haitao Yuan, Jinwei Zhu, Wei Dong, and Gao Cong. 2026. FDABench: A Benchmark for Data Agents on Analytical Queries over Heterogeneous Data. In Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining. [56] Song Yu, Shufeng Gong, Qian Tao, Sijie Shen, Yanfeng Zhang, Wenyuan Yu, Pengxi Liu, Zhixin Zhang, Hongfu Li, Xiaojian Luo, Ge Yu, and Jingren Zhou. 2024. LSMGraph: A High-Performance Dynamic Graph Storage System with Multi-Level CSR. Proceedings of the ACM on Management of Data 2, 6, Article 243 (2024), 243:1–243:28 pages. [57] Chao Zhang, Jiaheng Lu, Pengfei Xu, and Yuxing Chen. 2019. UniBench: A Benchmark for Multi-Model Database Management Systems. In Performance Evaluation and Benchmarking for the Era of Artificial Intelligence (Lecture Notes in Computer Science), Vol. 11135. Springer, 7–23.

14

Related documents

• TGMS: An Agent-Native Bi-Temporal Graph Management System#363360
• Samyama: A Unified Graph-Vector Database with In-Database Optimization, Agentic Enrichment, and Hardware Acceleration#1050831
• Validation of graph databases against PG-Schema#259583
• CVE-2026-103921 — HIGH 7.4#1167515
• Data Management and Sharing Plan for: Understanding the Mechanisms of Low Temperature Catalytic Graphitization#207857