Subgraph Matching in Graph Databases: Concepts, Algorithms, and Optimizations

The lecture begins by defining databases and reviewing relational (RDBMS) concepts, then explains how graph databases directly map E‑R models to nodes and edges, highlighting the distinction between conceptual (schema‑first) and physical (schema‑less) models.

It contrasts relational and graph databases, emphasizing that relational systems rely on predefined schemas while graph databases allow flexible, attribute‑rich nodes and edges, making them suitable for heterogeneous, user‑generated data.

The core topic is subgraph matching: given a query graph Q and a data graph G, each vertex of Q must be injectively mapped to a vertex of G. The problem is NP‑Complete for decision and NP‑Hard for enumeration, but practical systems use filtering and indexing to improve performance.

Two main algorithmic families are presented: (1) Backtracking Search (depth‑first with recursion) and (2) Multi‑way Join (breadth‑first). The latter includes Binary Join and Worst‑Case‑Optimal Join, the latter guaranteeing output‑size‑proportional intermediate results.

Worst‑Case‑Optimal Join relies heavily on set‑intersection operations. The authors propose SIMD‑based data layouts to accelerate set intersections, achieving significant speedups in graph algorithms and in systems such as Stanford’s graph processing engine.

Hardware acceleration is also discussed: GPU‑friendly implementations of set‑intersection avoid write conflicts without locks, enabling massive parallelism.

PKUMOD’s contributions are highlighted: the RDF‑graph database gStore (SPARQL answered via subgraph matching), its distributed version for large RDF graphs, and optimizations such as set‑intersection acceleration and hybrid join strategies (combining Worst‑Case‑Optimal and Binary Joins) that improve query performance.

References to the gStore project website, cloud service, and related publications are provided for further exploration.