Back to search

Purdue University

Native Graph Support in Relational Data Systems

Abstract

dc:description.abstract

A variety of data management applications spanning various domains, e.g., social networks, transportation, and bioinformatics, have graphs as first-class citizens. Specialized graph databases can serve these applications to evaluate vital graph-traversal queries, e.g., shortest path and reachability queries. However, specialized graph databases are not as mature as the pervasive relational database systems. Although the literature has several proposals to process graph queries inside an RDBMS, none of these proposals process graphs natively inside an RDBMS for potentially better performance, which is particularly challenging due to the impedance mismatch between the relational and the graph models. Additionally, to scale for large graphs and heavy query-workloads, the state-of-the-art approaches pre-construct indexing structures to improve query latency. However, updates that dynamically change the underlying graphs may frequently invalidate these costly pre-constructed indexes. This dissertation presents GRFusion, an RDBMS that manages graphs as first-class citizens as well as novel methods to index and summarize dynamic graphs for efficient query processing, namely, EDP and SBG-Sketch. GRFusion is based on VoltDB, an open-source in-memory relational database. This dissertation shows how the SQL query engine of GRFusion is empowered to declaratively define graphs and execute cross-data-model query plans acting on graphs and relations, resulting in up to four orders-of-magnitude in query-time speedup w.r.t. state-of-the-art approaches. To scale for large graphs and heavy query-workloads, this dissertation presents Edge-Disjoint Partitioning (EDP) and Self-Balanced Graph Sketch (SBG-Sketch). EDP is a new technique for efficiently answering shortest-path queries with filtering predicates over dynamic graphs. EDP has two main components: a graph-partitioning index and an efficient traversal algorithm. EDP can dynamically handle various types of online graph updates, e.g., graph topology and attribute updates. Experimental results demonstrate that EDP can achieve query performance gains of up to four orders-of-magnitude in comparison to state-of-the-art techniques. SBG-Sketch is a graph sketch that summarizes edge-labeled graph streams, coping with highly imbalanced edge-labels. SBG-Sketch maintains synopsis for both the edge attributes (e.g., edge weight) as well as the topology of the streamed graph. SBG-Sketch allows efficient processing of frequency-based queries (e.g., edge counts) and graph-traversal queries (e.g., reachability queries). Experimental results over a variety of real labeled-graph streams show SBG-Sketch to reduce the estimation errors of the state-of-the-art methods by up to 99%.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hassan, Mohamed S.
Contributors dc:contributor
  • Walid G. Aref
  • Sunil Prabhakar
  • Susanne E. Hambrusch
  • Tiark Rompf

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Purdue University
Base URL
docs.lib.purdue.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Hassan, Mohamed S.. Native Graph Support in Relational Data Systems. Dissertation thesis, https://docs.lib.purdue.edu/open_access_dissertations/1947