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

The lecture begins by defining graph databases and contrasting them with traditional relational databases, highlighting the shift from schema‑first to schema‑less models and the implications for data modeling and query processing.

It then introduces the core concept of 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, a problem that is NP‑Complete for decision and NP‑Hard for enumeration.

Two main families of algorithms are presented: depth‑first backtracking search (e.g., Ullmann, VF2) and breadth‑first multi‑way join methods, including worst‑case optimal joins that avoid large intermediate results by intersecting candidate vertex sets.

The article explains how subgraph matching underlies SPARQL and Cypher query execution, showing that SPARQL can be translated to SQL and solved via conjunctive queries, while Cypher directly expresses pattern matching.

Optimization techniques are discussed, notably accelerating set‑intersection operations using SIMD vector instructions and specialized data layouts, which significantly reduce CPU cycles in graph algorithms.

Research from Peking University’s PKUMOD lab is highlighted, including the gStore system that answers SPARQL via subgraph matching, its distributed extension for large RDF graphs, and recent work combining binary joins with worst‑case optimal joins for better performance.

Finally, hardware‑level acceleration on GPUs and lock‑free write strategies are described, and the article concludes with a summary of the presented concepts and references to further reading.