Given a query graph, top-k subgraph matching finds up to$k$matches in a data graph with the highest scores according to a user-defined scoring function. It has wide applications across many fields, including knowledge graphs and social networks. Due to the enormous search space, existing methods are not efficient enough on large graphs. In this paper, we proposePTAB, an efficient serial algorithm for top-k subgraph matching. It traverses an efficiently pruned search space by topology-aware subspace score upper bounds computed from a novel hop index, which stores the range of node properties in a constrained multi-hop neighborhood of each node. Additionally,PTABintegrates a cost-aware root selection strategy, which chooses query nodes leading to a search process that utilizes the pruning power of the hop index as much as possible. Furthermore, we use a novel edge-cut strategy to handle general query graphs with cycles. We also extendPTABto a parallel version,PTABP, which further improves performance via multi-threading and enhanced pruning techniques. Experimental results on real and synthetic datasets demonstrate that our methods outperform existing methods.

With the advent of graph data, graph databases have garnered significant research interest and efforts in recent years, especially with respect to graph query processing. There have been a vast suite of methods for efficient graph query processing, especially for the core graph query constructs, regular path queries (RPQs) and subgraph matching queries (SMQs). In the meantime, there is an observable divide among these methods as well as confusion between them and their relational counterparts. We thus propose this tutorial to provide a unified narrative for graph query processing, so as to bridge the gap between existent lines of work and offer a comprehensive view of the query processing workflow in graph databases.

The proliferation of RDF datasets has resulted in studies focusing on optimizing SPARQL query processing. Most existing work focuses on basic graph patterns (BGPs) and ignores other vital operators in SPARQL, such as UNION and OPTIONAL. SPARQL queries with these operators, which we abbreviate as SPARQL-UO, pose serious query planning challenges. In this paper, we propose techniques for optimizing SPARQL-UO queries using BGP execution as a building block, based on a novel BGP-based Evaluation (BE)-Tree representation of query plans. On top of this, we propose a series of cost-driven BE-tree transformations to generate more efficient plans by reducing the search space and intermediate result sizes, and a candidate pruning technique that further enhances efficiency at query time. Experiments confirm that our method outperforms the state-of-the-art by orders of magnitude.

Graph databases play a pivotal role in the FinTech industry. However, existing graph benchmarks fail to capture the unique characteristics of financial datasets and workloads, rendering them inadequate for evaluating graph databases in financial scenarios. This paper presents the LDBC Financial Benchmark (FinBench) Transaction Workload, a novel benchmark that adopts a choke point-driven design methodology, emphasizing performance bottlenecks, and incorporates distinct features such as dataset skewness, edge multiplicity, temporal window filtering, recursive path filtering, read-write query patterns, and truncation on hub vertices. Key contributions include a scalable data generator that synthesizes datasets with financial-specific features, a parameter generator that leverages bucketed data statistics for runtime consistency across queries, and a scalable benchmark driver that biases query execution by time windows. Experimental evaluations on graph databases demonstrate the benchmark's capability to reveal novel choke points and provide insights into system performance in financial scenarios.

Given a query graph, top-k subgraph matching finds up to k matches in a data graph with the highest scores according to a user-defined scoring function. It has wide applications across many fields, including knowledge graphs and social networks. Due to the enormous search space, existing methods are not efficient enough on large graphs. In this paper, we propose PTAB, an efficient algorithm for top-k subgraph matching. It traverses an efficiently pruned search space by topology-aware sub-space score upper bounds computed from a novel hop index, which stores the range of node properties in a constrained multi-hop neighborhood of each node. Additionally, PTAB integrates a cost-aware root selection strategy, which chooses query nodes leading to a search process that utilizes the pruning power of the hop index as much as possible. Furthermore, we use a novel edge-cut strategy to handle general query graphs with cycles. Experimental results on real and synthetic datasets demonstrate that our method outperforms existing methods.

A regular path query (RPQ) returns node pairs connected by a path whose edge label sequence satisfies the given regular expression. Given a workload of RPQs, selecting the shared subqueries as materialized views to precompute offline can speed up the online processing. Since the available memory is limited, we define the materialized view selection (MVS) problem for RPQs as minimizing the total workload query cost within a memory budget. To tackle the problem's NP-hardness, we design an efficient MVS algorithm based on heuristics. To prevent redundancies in the selected views, we devise the AND-OR directed acyclic graph with closure (AODC) as the multi-RPQ query plan representation for the workload, which encodes the relations between subqueries. In addition to detecting view redundancy, the AODC also incrementally updates itself during view selection. To support query planning, we design a scalable cost and cardinality estimation scheme for full-fledged RPQs, including Kleene closures. Our method, when applied to the Wikidata Query Logs, shows a 9.73× speedup in the total query processing time compared to ad-hoc processing, using the views it selects.

Reachability is a fundamental graph operator. State-of-the-art index-based reachability processing frameworks can efficiently handle static graphs, but the recent advent of dynamic graph data poses new challenges. To address these challenges, we propose an index-free, community-aware (IFCA) reachability processing framework inspired by efficient Personalized PageRank approximation algorithms, which identifies community structures on-the-fly to accelerate query processing. On top of it, we devise a community contraction technique to bridge the gap between vertices in distinct communities, and a cost-based strategy selection procedure to efficiently handle the resulting reduced graph. We conduct experiments with realistic query workloads over large-scale real dynamic graphs, showing our approach’s superior efficiency compared with index-based and index-free state-of-the-art methods.

Query optimization is an especially challenging problem in graph databases due to its wide plan space and the difficulty in gathering statistics. In this demonstration, we propose a new cost-based query optimizer called gCBO for graph databases and implement it in a specific graph database (i.e., gStore). To tackle the aforementioned challenges, gCBO employs a hybrid plan enumerator based on dynamic programming, cost models that capture the characteristics of different types of joins, and a sampling-based cardinality estimation strategy that gathers the necessary statistics on-the-fly. What is more, to absorb the experience of users, we build an interactive component for gCBO, which allows users to receive the optimized execution plans with detailed information and generate their own plans for execution.