MV4PG: Materialized Views for Property Graphs

We adopt the definition of the property graph database model given by Angles [21], and the schema is supported by Neo4j and TuGraph. Assume that L, P, V represent the sets of labels, property names, and property values, respectively.

For $\lambda$, the set of labels associated with a single node or a single edge in this paper always contains exactly one label.

Here the MATCH clause corresponds to the pattern graph of  Figure 1(a).

As shown in  Figure 4, the public patterns of the query statements are manually extracted from the workload, and the corresponding view creation statements are given, which are directly inputted into the graph database system. At the same time, for each view creation statement, we will generate the corresponding view maintenance statement template, which is put into  Section IV-B to talk about it in detail.

Since existing graph database systems do not support the materialized view, we use part of the GQL grammar to extend the Cypher grammar, the relevant core grammar is shown in  Figure 5.

The main part of our view is the pattern element (PatElem) of Match clause that represents a path from the start to the end. The PatElem of the Construct clause has only two nodes and one view edge, the two nodes are the source and the end of the PatElem of the Match clause. The role of the view is to compress a path that may contain variable-length edges into a single view edge, speeding up the query rate.

After the view is created, any write operations such as creating, deleting, or property updating in a graph database require updating the view to maintain consistency. As shown in  Figure 6, we predefine maintenance statement templates for views. When the graph database is modified, these templates are iterated over, with the relevant parameters replaced, and the resulting statements are executed in the graph database system.

Since the views in this paper do not involve properties, we focus solely on creation and deletion operations. Specifically, we handle four cases: creating a node, deleting a node, creating an edge, and deleting an edge. Next, we will explain how to generate maintenance statement templates for these scenarios.

In the path of a view, nodes may appear in two places, one is explicit nodes and the other is implicitly in variable-length edges. Lines 4-6 of the  algorithm 1 iterates through all the explicit nodes and calls ReplNode to generate a maintenance statement, which instantiates the node to the deleted node $\mathcal{N}$ and leaves the rest of the view unchanged, which finds all view edges when $\mathcal{N}$ is at the certain position when all view edges are found and deleted; Lines 7-26 deal with the case in variable-length edges, setting n,m as the minimum and maximum hops of variable-length edges, respectively. We need to traverse all possible locations of the $\mathcal{N}$, so we traverse from the smallest to the largest distance of $\mathcal{N}$ from the starting node of the variable-length edge, and we don’t need to consider the case where the distance from the start node or the end node is 0 here, because a distance of 0 is an overlap with the start node or the end node, which is the case in lines 4-6 of the  algorithm 1.

Because the maximum hop may equal $\infty$, we discuss in two cases, if the maximum hop is infinite, the only limit is the number of hops is greater than or equal to n. When the distance between $\mathcal{N}$ and the start node of e is $i<n-1$, the distance between $\mathcal{N}$ and the end node of e must be $>=n-i$, such as lines 13-14; when the distance between $\mathcal{N}$ and the start node of e is $i>=n-1$, then the distance between $\mathcal{N}$ and the end node of e can be $>=1$, so this case can be merged into one statement, such as lines 16-17, there will be a total of $n-2+1=n-1$ statements. Of course, if $n<2$, there will also be 1 statement.

If the maximum hop is not infinite, then traverse the distance from $\mathcal{N}$ to the start node from $1$ to $m-1$, generating a total of m-1 statements, as shown in lines 21-23. When the distance from $\mathcal{N}$ to the start node of e is i, the distance from $\mathcal{N}$ to the end node of e will be $max(n-i,1)$ at minimum, and the maximum will be $m-i$.

Here the ReplNodeInVlen function expands the variable-length edge e into three parts: edge-node-edge. The first parameter $(i,i)$ of ReplNodeInVlen, i.e., the minimum and maximum hops of the first edge, denotes the distance between the $\mathcal{N}$ and the start node of e, the second parameter is the minimum and maximum hops of the second edge, which denotes the distance between the $\mathcal{N}$ and the end node of e, and the intermediate node is instantiated with the $\mathcal{N}$.

The maintenance statement for creating or deleting an edge is similar to that for deleting a node; first, all explicit edges are found and instantiated, and the replacement will instantiate the start node, the end node, and the edge itself all in $\mathcal{E}$. Then deal with the case in the variable-length edge e, also divided into two cases according to whether the maximum hop is infinite or not like  algorithm 1, but changing $i$ to the distance from the starting node of e to the starting node in $\mathcal{E}$, the specific process will not be repeated. The first parameter of ReplEdgeInVlen is the minimum and maximum number of hops for variable-length edges between the start node in $\mathcal{E}$ and the start node of e. The second parameter is the minimum and maximum number of hops for variable-length edges between the end node in $\mathcal{E}$ and the end node of e. The final addition of an extra isCreate compared to  algorithm 1 to indicate whether to create an edge or to delete an edge does not affect the core of the maintenance statement, which will be explained in the subsequent examples.

For the view created by  LABEL:lst:view_maintenance_example, we generate templates for three view maintenance sets based on  algorithm 1 and  algorithm 2, representing deleting a node, creating an edge, and deleting an edge, respectively.

LABEL:lst:view_maintenance_node demonstrates the maintenance template for the view shown in  LABEL:lst:view_maintenance_example when deleting a node with a total of four statements, i.e., $|$$\mathcal{S}_{\textsf{VMT}}$ $|=4$. In  algorithm 1, the first two statements are generated by lines 4-6. The last two statements are for the case where the deleted node is in the variable-length edge, and since the maximum number of hops is infinite, they correspond to lines 11-19 in  algorithm 1. In the example, $n=3,m=\infty$, $i=1\ to\ 2$. When $i$ is $1$, corresponding to lines 12-14 of  LABEL:lst:view_maintenance_node, the third statement of  LABEL:lst:view_maintenance_node is generated, i.e., the deleted node is greater than or equal to $2$ from the end node when the distance from the start node is $1$; When $i$ is $2$, corresponding to lines 15-18 of  algorithm 1, when the deleted node is at a distance greater than or equal to $2$ from the start node, it is all at a distance greater than or equal to $1$ from the end node, so they can be combined as a single statement, i.e., the last statement of  LABEL:lst:view_maintenance_node.

It can be noted that each statement has an identical clause headed by the WITH keyword, which is the part that removes the view edges from each pair of views found for their start and end nodes. One thing to note here is that for each pair of (s,d) found, if there are multiple view edges in s and d, not all of them are deleted, but only one of them is deleted, because each view edge actually corresponds to one of the cases in which all the nodes and edges are instantiated in the $\mathcal{V}$, and also corresponds to each pair of s,d that we found here.

This is correct for a single statement, since a Match statement such as

MATCH (s:Person:$L{$K:$V})-[:knows*3..]->(d:Person),
the result of each graph instance matched by the Match statement corresponds to a different graph instance matched in the view creation statement, so for each pair of s,d matched, deleting or creating one of their edges is consistent with the database.

But if there are multiple statements, different maintenance statements may match to the same view, meaning that the deleted node may appear in two locations at the same time making the deleted view duplicated. For example, if Person{id:1} is deleted, the first statement of  LABEL:lst:view_maintenance_node may match this case:

MATCH (s:Person{id:1})-[:knows]->(:Person{id:2})-[:knows]->(d:Person{id:1}).
However, the second statement will match the same case, which could result in the removal of two view edges (if any) of s->d when deleting, but only one view edge should be removed for the same instance. So we need to save the matched graph instances, i.e., the actual graph data corresponding to each node and each edge in the pattern graph of the view $\mathcal{V}$, to make sure that only one view edge is deleted or created for the same graph instance.

LABEL:lst:view_maintenance_edge demonstrates the maintenance template for the view shown in  LABEL:lst:view_maintenance_example when creating an edge, by Union combining the three statements into one, i.e., $|$$\mathcal{S}_{\textsf{VMT}}$ $|=3$. All statements are for the case where the created edge is in the variable-length edge, generated by lines 11-19 of  algorithm 2. Deleting an edge is largely similar to creating an edge, except that the statement following the WITH keyword is different; when deleting an edge, the portion following the WITH keyword is the same as the maintenance template for deleting a node. Another point of detail is that edges don’t necessarily have a primary key, so we use the internal id of the graph database system to uniquely lock the edge.

In practice, in most cases, the $N$ involved in a single node or a single edge is not large, so the maintenance time required for small-scale updates under incremental maintenance will not increase significantly, which can be verified in  Section VI.

Different view traversal orders lead to different optimization results. For example, assuming that $\mathbb{V}$ have two views in  Figure 9 and  Figure 9, for the query pattern graph in  Figure 12, if View1 is used first to optimize, then the optimized result is shown in  Figure 12, which only applies View1; if View2 is used first to optimize, then the optimized result is shown in  Figure 12, which only applies View2.

So the SortByOptEff function sorts the collection of views from largest to smallest according to the optimization effect of the views. Assume $\textsf{DBHit}_{\textsf{}}$ represents the total number of accesses made by all operators to the storage engine to retrieve necessary data during the execution plan, e.g., accessing a node or an edge in the database is counted as one time. The subscript noV and V stand for “no Views” and “with Views”, respectively. The currently adopted practice is to consider only the optimization effect of the view itself, i.e., $\textsf{DBHit}_{\textsf{noV}}$ - $\textsf{DBHit}_{\textsf{V}}$. And $\textsf{DBHit}_{\textsf{V}}$=$|N_{\$SL}|+2*|E_{\$VL}|$($\$SL$ and $\$VL$ are the labels for the start node of view and view edge, respectively, $|N_{\$SL}|$ is the number of nodes in the graph database labeled $\$SL$, $|E_{\$VL}|$ is the number of edges in the graph database labeled $\$VL$), i.e., the cost is to traverse the starting node, then traversing all view edges adjacent to the starting node and obtaining the corresponding end node. So the final optimization effect formula is shown in  Equation 1.

In this example, the optimization effect of View1 is the difference between  Figure 12 and  Figure 12, where  Figure 12 goes from a node of label Comment through two hops to a node of label Tag, which is the original query cost of View1, while  Figure 12 goes from a node of label Comment through View1 directly to a node of label Tag, where the query cost becomes the number of View1, and the two differences are the effect of optimization. The $|N_{\$SL}|$, $|E_{\$VL}|$ and DBHit will have an initial value when the view is created. Both $|N_{\$SL}|$ and $|E_{\$VL}|$ can be easily maintained by changing them when the corresponding nodes or edges are created or deleted. But the DBHit is more difficult to maintain, We use an estimation approach for maintenance, specifically we will save the value of initial$\textsf{DBHit}/(|initialN_{\$SL}|+2*|initialE_{\$VL}|)$ as the $optRate$, assuming that the ratio $optRate$ constant, then the value of DBHit is shown in  Equation 2.

The algorithm of MatchView is shown in  algorithm 4, the general idea is similar to the VF2 algorithm [24], which is to do matching between $\mathcal{V}$ and $\mathcal{Q}$ from the start node of $\mathcal{V}$. The matchResult stores the matching result, nowVN is a global variable, which indicates the latest view node that has been matched so far. When matchResult.size and $\mathcal{V}$.nodes.size are equal, then the match is complete and returns true; conversely, if there is no feasible match, false is returned in the last line. Specifically, lines 4-17 iterate over all the nodes in $\mathcal{Q}$ to match the $\mathcal{V}$.startNode. If the NodeCanMatch function is true, the match result is saved and the MatchView function is called recursively, if the recursively called MatchView function finds a feasible match, then it returns true, otherwise, it backs up nowVN to the state before the match and deletes the match result in matchResult; Lines 18-32 are executed after matching the $\mathcal{V}$.startNode with $\mathcal{Q}$, and firstly call GetNext(nowVN) function to get the unmatched neighbors of nowVN. Since $\mathcal{V}$ is a path, the set size of GetNext(nowVN) is 1. Then get the set of unmatched neighbor nodes and neighbor edges of matchResult[nowVN](matchResult[nowVN] is the node in $\mathcal{Q}$ that matches with nowVN), iterate through the set, and call NodeCanMatch and RelpCanMatch functions to determine whether it can match, if it can be matched, it is handled the same as the previous lines 9-15.

When the MatchView function finds a feasible match, the ChangePG function changes $\mathcal{Q}$ based on the match. For path $\mathcal{MP}$ in $\mathcal{Q}$ that matches the view, ChangePG replaces the path between the start and end nodes in $\mathcal{MP}$ with a view edge.

Because ChangePG replaces all nodes and edges in $\mathcal{MP}$ other than the start and end nodes with the view edge, if there are other references to these replaced nodes or edges in $\mathcal{Q}$ (e.g., in other clauses such as WHERE, WITH, RETURN, etc.), it will affect the execution of the query statement, so an attribute isReferenced of whether or not the nodes and edges are referenced is added to each node and edge at the parser stage. And in the NodeCanMatch(nextVN, n) function, we need to first determine whether the label is the same, if nextVN is not the start or end node of $\mathcal{V}$, then the isRenferenced attribute of n needs to be false, and the node of the degree of outgoing and incoming degrees add up to 2, that is, n will have no neighbors outside $\mathcal{MP}$; In RelpCanMatch, we also need to make sure that the labels are the same, that there are no other references, and that the direction, min-hop and max-hop are the same.

The worst case of MatchView iterates through all possible matches, matching node in $\mathcal{V}$ with every node in $\mathcal{Q}$, i.e., $|\mathcal{Q}_{N}|^{|\mathcal{VQ}_{N}|}$, as mentioned before for each view MatchView can match successfully up to $|\mathcal{Q}_{E}|$ times, so time complexity is $O(\displaystyle\sum_{\mathcal{VQ}\ in\ \mathbb{VQ}}|\mathcal{Q}_{E}|*|\mathcal{Q}_{N}|^{|\mathcal{VQ}_{N}|})$.

ChangePG replaces the matched paths in the query graph with view edges, i.e., remove the paths first and then insert the view edges, the complexity is $O(|\mathcal{VQ}_{N}|)$ for each call. The number of calls is the same as the number of successful MatchView matches, the total complexity is $\displaystyle O(\sum_{\mathcal{VQ}\ in\ \mathbb{VQ}}|\mathcal{Q}_{E}|*|\mathcal{VQ}_{N}|)$, compared to the MatchView can be ignored.

In summary, the total time complexity is $\displaystyle O(|\mathbb{VQ}|*log(|\mathbb{VQ}|)+\sum_{\mathcal{VQ}\ in\ \mathbb{VQ}}|\mathcal{Q}_{E}|*|\mathcal{Q}_{N}|^{|\mathcal{VQ}_{N}|})$. The graph schema under the property graph model is relatively simple, the number of views will not be very large, and the number of nodes and edges in $\mathcal{Q}$ and $\mathcal{V}$ is also very small, and the estimation of MatchView is in the worst-case scenario, in fact, due to the presence of filtering operations such as labeling for nodes, edges, etc., the real traversal number is much less than the worst-case scenario, so the time taken to optimize the query graph using the view is completely negligible compared to the actual query time, which can be verified in the  Section VI.

• •

  SNB: the social network benchmark provided by LDBC [25], which simulates real online social networking scenarios, is a better way to evaluate the performance of a graph database in real-world scenarios. The SNB dataset used in this paper contains 3,181,724 nodes and 17,256,038 edges.

• •

  Finbench: LDBC FinBench(Financial Benchmark) [26] intends to define a benchmark characterized by special data and query patterns in financial industry to test graph database systems to make the evaluation of graph databases representative, reliable and comparable, especially in financial scenarios. The Finbench dataset used in this paper contains 5,376,981 nodes and 26,633,151 edges.

• •

  SNB:  Figure 14 shows the results of SNB’s workload tested in TuGraph and  Figure 14 shows the results of SNB’s workload tested in Neo4j where ORI_QUERY and OPT_QUERY represent the execution time without view optimization and with view optimization, respectively, and OPT_VPG represents the time required by the  algorithm 3 to change the pattern graph. And it can be seen that the OPT_VPG is very short and negligible compared with OPT_QUERY. The OPT_VPG in Neo4j is longer than in TuGraph because, when executing in Neo4j, the TuGraph interface is called to get the optimized statement (as shown in Figure 7), which introduces additional transmission time.

  Table IV summarizes the speedup ratios of SNB’s workload in TuGraph and Neo4j, where CE, DE, and DV denote creating edge, deleting edge, and deleting node, respectively.  Table V counts the speedup ratios of the whole Workload, where $W_{ori}$ denotes the execution time of the unoptimized workload, $W_{opt}$ denotes the execution time of the optimized workload, and $MV$ denotes the total time for the creation of all materialized views.

  

  

  	TuGraph	Neo4j
  Q1	2.27	1.87
  Q2	2.20	3.80
  Q3	45.00	4.41
  Q4	2.36	2.97
  Q5	2.81	1.06
  Q6	60.99	1.35
  Q7	96.91	1.27
  Q8(CE)	0.91	0.99
  Q9(DE)	0.87	0.40
  Q10(DV)	0.68	0.30

  	TuGraph	Neo4j
  $W_{ori}/W_{opt}$	28.71	1.64
  $W_{ori}/(MV+W_{opt}$)	16.19	1.32

  

  

  	TuGraph	Neo4j
  Q1	1.94	1.71
  Q2	2.15	3.30
  Q3	4.32	4.42
  Q4	5.18	1.62
  Q5	3.54	4.49
  Q6	3.49	8.94
  Q7	12.68	4.34
  Q8(CE)	0.91	0.91
  Q9(DE)	0.60	0.34
  Q10(DV)	0.68	0.29

  	TuGraph	Neo4j
  $W_{ori}/W_{opt}$	9.49	2.47
  $W_{ori}/(MV+W_{opt})$	4.43	1.19

• •

  Finbench:  Figure 16 shows the results of Finbench’s workload tested in TuGraph and  Figure 16 shows the results of Finbench’s workload tested in Neo4j.  Table VI summarizes the speedup ratios of Finbench’s workload in TuGraph and Neo4j, and  Table VII counts the speedup ratios of the whole Workload.

From  Table V and  Table VII, we can see that the speedup ratio of the whole workload is also good, and the best speedup ratio in TuGraph is as high as 28.71x. There is also a good optimization effect after adding the time of view creation, that is to say the optimization effect of adding views is greater than the additional overhead that the views bring.

Metric Rows indicates the size of the intermediate results when the query is executed. A decrease in the number of intermediate results will result in less data being passed between multiple operators, thereby reducing processing time and improving query performance.

Metric DBHit as mentioned in indicates the number of times an operator needs to access the storage engine. The decrease of DBHit will lead to improved query performance.

Figure 17 shows the analysis results of the execution plan of Q3 in SNB on TuGraph. Q3 optimizes the two-hop path as n1->n2->n3 into a single edge from n1 to n3 using a view. It can be seen that the value of DBHit is significantly reduced, especially for the Expand node from n2 to n3, which originally had nearly 300 million DBHit. However, the total DBHit after view optimization is only over 4 million, which is only one-sixtieth of the original. The final speedup ratio also reached 45.00.

Figure 18 shows the analysis results of the execution plan of Q3 in SNB on Neo4j. Without view optimization, Neo4j chooses to traverse in two paths and finally merges the two paths at n2. The optimized execution plan is similar to TuGraph. Although this results in a small difference in the number of DBHit, both in the millions, the extra time consumed by NodeHashJoin still results in a speedup ratio of 4.41.

The efficiency of the write statements in  Table IV and  Table VI is relatively high, but they only create or delete a very small number of nodes or edges. To further illustrate the speed of view maintenance, we increased the number of edges deleted to $10^{0},10^{1},...,10^{4}$, because most updates in dynamic graphs do not involve a very large amount of data; a range of $1$ to $10^{4}$ deleted edges can cover the vast majority of cases where the number of the total edges is on the order of tens of millions. We conducted tests in both TuGraph and Neo4j, and the speedup ratios are shown in  Figure 19.

As we can see, the speedup ratio in TuGraph drops significantly when the number of edges reaches $10^{4}$. Our analysis indicates that this is not an issue with our incremental maintenance algorithm, which is also validated by the results from Neo4j. Instead, it’s because TuGraph cannot locate a specific edge based on its edge ID. During maintenance, it must first obtain the starting node through $SK:$SV in  LABEL:lst:view_maintenance_edge, then traverse all adjacent edges of the starting node, and use an Edge Filter to exclude edges that do not match the specified edge ID. When the starting node has a large number of adjacent edges, the extra traversal becomes substantial, leading to decreased efficiency. We also measured the time required by the Edge Filter during deletion in TuGraph and found that when deleting $10^{4}$ edges, the Edge Filter accounts for 93% of the total time. After removing the time taken by the Edge Filter, the speedup ratios all exceed 20%.

In Neo4j, the speedup ratio is relatively stable, remaining at 20% to 30% overall, and the DBHit and the number of deletions show a perfect linear relationship. This indicates that the overhead introduced by our maintenance algorithm is linear. In absolute time, the additional cost of view maintenance is much smaller than the efficiency gains of query optimization. However, for graph data that is updated extremely frequently, real-time incremental maintenance may have a negative impact, which will be addressed in future work.