We address the problem of evaluating graph pattern queries involving reachability (edge-to-path mapping) and direct (edge-to-edge mapping) relationships under homomorphisms on data graphs using materialized graph pattern views. We propose an original approach for view materialization which materializes views as summary graphs, an approach that records, in a compact way, all the homomorphisms of the view to the data graph. In this context, we characterize view usability in terms of query edge coverage and provide necessary and sufcfiient conditions for answering queries using views. We design algorithms for deciding whether a query can be answered using a set of views, for generating the summary graph of a query from the view materializations, and for producing a minimal view set capable of answering a query. Our experimental evaluation demonstrates that our approach outperforms, by several orders of magnitude, a state-of-the-art approach which does not use materialized views, and substantially improves upon its scalability. *The research of this author was supported by the National Natural Science Foundation of China under Grant No. 61872276.
Graphs model complex relationships between entities in a
multitude of modern applications. A fundamental operation for
querying, exploring and analyzing graphs is graph matching, which
consists of finding the matches of a query graph pattern in the data
graph. Graph matching is crucial in many application domains,
such as social network analysis [
Existing approaches are characterized by: (a) the type of edges
the patterns have, and (b) the type of morphism used to map
the pattern to the data graph. An edge in a query pattern can be
either a child edge, which represents a parent-child relationship
in the data graph (edge-to-edge mapping) [
Earlier contributions considered isomorphisms and edge-toedge mappings, while more recent ones focus on homomorphic mappings. By allowing edge-to-path mapping on graphs, patterns with descendent edges are able to extract matches “hidden” deeply within large graphs which might be missed by patterns with only child edges. On the other hand, the patterns with child edges can discover important parent-child relationships in the data graph which can be missed by patterns with only descendant edges. We adopt, in this paper, a general framework that considers patterns which allow both child and descendant edges. This framework incorporates the benefits from both types of edges.
Graph pattern matching is an NP-hard problem, even for
isomorphic matching of patterns with only child edges [
Answering queries using materialized views is a well known
technique for improving the performance of query evaluation and
for evaluating queries without accessing the base data, in particular
in a distributed environment [
In this paper we adopt a novel approach for materializing graph pattern views over data graphs: a view materialization is a graph, called a summary graph of the view, which is a compact representations of the view answer. A summary graph constitutes a search space for the view answer and the view results can be enumerated by applying multiway joins while traversing the graph. Contribution. The main contributions of the paper are as follows: • We consider hybrid queries (i.e., queries involving parent-child and reachability relationships) to be mapped against large data graphs using homomorphisms. In this context, we address the problem of answering graph pattern queries using materialized views. This problem has not been addressed before for this type of queries and views. • We suggest an original way for representing materialized views as summary graphs. A summary graph of a view compactly encodes all the homomorphisms of the view to the data graph in a structure which is, typically, much smaller than the view answer (Section 3). • We characterize answering a query using one or multiple views in terms of query edge coverage from view edges. We provide necessary and sufficient conditions for answering a query using materialized views (Section 4). • We design an algorithm which identifies the views from a pool of materialized views that can be used for answering a query, and computes the summary graph of a query from the summary graphs of these views (Section 5). • Not all available views might be needed for answering a query.
We provide an algorithm which finds a minimal set of views (this is a set of views which does not include redundant views) from the view pool (Section 5). • We run extensive experiments to evaluate the efcfiiency and scalability of our approach for answering queries using views. We also compare it with a previous state-of-the-art approach which does not use materialized views. Our results show that our view-based approach outperforms that approach by orders of magnitude in terms of execution time and displays better scalability (Section 6). 2
In this section, we present the data model, graph pattern queries, edge-to-path mappings and homomorphisms. We also present related concepts that are needed for the results presented later. Data Graph. We assume that the data is presented in the form of a data graph defined below.
Definition 2.1 (Data Graph). A data graph is a directed nodelabeled graph = ( , ) where denotes the set of nodes and denotes the set of edges (ordered pairs of nodes). Let L be a ifnite set of node labels. Each node in has a label ( ) ∈ L associated with it.
Given a label in L, the inverted list is the list of nodes in whose label is . Figure 1(a) shows a data graph with labels , , , and . Label subscripts are used to distinguish nodes with the same label. The inverted list of label in is = {1, 2, 3, 4, 5}
Definition 2.2 (Node reachability). A node is said to reach node in , denoted by ≺ , if there exists a path from to in . Clearly, if (, ) ∈ , then ≺ . Abusing tree notation, we refer to as a child of (or as a parent of ) if (, ) ∈ , and as a descendant of (or is an ancestor of ) if ≺ .
Given two nodes and in , in order to efcfiiently check
whether ≺ , graph pattern matching algorithms use some kind
of reachability indexing scheme. In most reachability indexing
schemes the data graph node labels are the entries in the index for
the data graph [
Queries. We consider graph pattern queries that involve child and/or descendant edges.
Definition 2.3 (Graph Pattern Query). A query is a graph . Every node in has a label ( ) from L. There can be two types of edges in . A child (resp. descendant) edge denotes a child (resp. descendant) structural relationship between the respective two nodes. A graph pattern that contains both child and descendant edges is a hybrid graph pattern.
Intuitively, a child edge represents an edge in the data graph . A descendant edge represents a path of edges in . Figure 1(b) shows a query . Single line arrows denote child edges while double line arrows denote descendant edges.
The match set ( ) of a node in is the inverted list () of the label of node . A match of an edge = (, ) in is a pair (, ) of nodes in such that ( ) = (), () = ( ) and: (a) ≺ if is a descendant edge, while (b) (, ) is an edge in if is a child edge. The match set () of is the set of all the matches of in .
The match set () of an edge = (, ) on a data graph can be computed using the match sets ( ) and () along with reachability information on the nodes of (if is a descendant edge), or the adjacency lists for the nodes of (if is a child edge).
The notion of node reachability provided in Definition 2.2 for nodes in a data graph is extended to nodes in a graph pattern in a natural way.
Homomorphisms. Queries are matched to the data graph using homomorphisms.
Definition 2.4 (Graph Pattern Homomorphism to a Data Graph). Given a graph pattern and a data graph , a homomorphism from to is a function ℎ mapping the nodes of to nodes of , such that: (1) for any node ∈ , ( ) = (ℎ ( )); and (2) for any edge (, ) ∈ , if (, ) is a child edge, (ℎ ( ), ℎ ()) is an edge of , while if (, ) is a descendant edge, ℎ ( ) ≺ ℎ () in .
Definition 2.5 (Homomorphism between Graph Patterns). Given a graph pattern and another graph pattern , a homomorphism from to is a function ℎ mapping the nodes of to nodes of , such that: (1) for any node ∈ , ( ) = (ℎ ( )); and (2) for any edge (, ) ∈ , if (, ) is a child edge, (ℎ ( ), ℎ ()) is a child edge of , while if (, ) is a descendant edge, ℎ ( ) ≺ ℎ () in .
Note that if (, ) is a descendant edge in , the path (of child and/or descendant edges) in from ℎ ( ) to ℎ (), can be a single child or descendant edge. Figures 2(a) and (b) show a query and a query (view) 1 with a homomorphism from 1 to . Query Answer. We call an occurrence of a pattern query on a data graph a tuple indexed by the nodes of whose values are the images of the nodes in under a homomorphism from to .
Definition 2.6 (Query Answer). The answer of on , denoted as ( ), is a relation whose schema is the set of nodes of , and whose instance is the set of occurrences of under all possible homomorphisms from to .
homomorphic matches of a graph pattern query on a data graph can very large. Therefore, we use summary graphs to compactly encode all possible homomorphisms of a query to a data graph.
Definition 3.1 (Query Summary Graph). The summary graph of a pattern query is a k-partite graph where is the number of nodes in . Graph has an independent node set, denoted (), for every node ∈ such that () ⊆ () ⊆ (). Every node in () is incident to an edge in if is incident to an edge in . The set () is called the candidate occurrence set of in . For every edge = (, ) in , the set of edges ( ) between the data graph nodes in the sets ( ) and () satisfies the inclusion relationships: ( ) ⊆ ( ) ⊆ ( ). The set ( ) is called the candidate occurrence set of in .
Figure 1(d) shows a summary graph for the query of
Figure 1(a), and Figure 2(c) shows a summary graph for the query
(view) 1 of Figure 2(b). A summary graph losslessly
summarizes all the occurrences of on . Similarly to factorized
representations of query results studied in the context of classical
databases and probabilistic databases [
We define a partial order ≺ on the summary graphs of a query . Let 1 and 2 be two summary graphs for . Then 1 ≺ 2 iff for every edge in , the candidate occurrence set for in 1 is a subset of the candidate occurrence set for in 2 . Partial order ≺ has a least element called the answer graph of on , and a greatest element called the match graph of on . One can see that for any edge in , the candidate occurrence set for in is the occurrence set (), while the candidate occurrence set for in is the match set ().
The class of views is not restricted. Any type of query can be a view. We materialize views on a data graph by storing a summary graph of this view.
Definition 3.2 (View Materialization). The materialization of a view on a data graph is a summary graph of on . A view is characterized as materialized if it has a materialization.
View Usability in Graph Pattern Query Answering. Graph pattern queries can be evaluated by computing the match sets of their edges on a data graph and then joining them on their common query nodes. Let be an edge in a query . The match set of is ( ) and its occurrence set is ( ) (recall that ( ) ⊆ ( )). If there is a materialized view which has an edge such that ( ) ⊆ ( ) ⊆ ( ) for every data graph, then can be used for evaluating since ( ) can be used instead of ( ) in the join. That is, “covers” . In addition, as ( ) is not bigger than ( ), this option is, in general, beneficial in the evaluation of . We define view usability in query answering based on this remark. As we will see later, when this happens, other edges of view might cover an edge in as well, in which case, their occurrence sets can also be exploited in evaluating query . We now formalize query edge coverage:
Definition 4.1. An edge of a query is covered by an edge of a view if ( ) ⊆ ( ) ⊆ ( ) on any data graph .
In the example of Figure 2, one can see that the edge (1, 2) of view 1 covers the edge (1, 2) of query 1 since for every mapping of to , there is a mapping of 1 to which is a restriction of . We can now define view usability.
Definition 4.2. A view is usable in answering a query if there is an edge in which is covered by an edge in . View Usability Conditions. We characterize query edge coverage in terms of homomorphisms from a view to the query. We say that a homomorphism ℎ from a view to a query maps an edge = (, ) in to an edge = (, ) in if ℎ ( ) = and ℎ () = .
THEOREM 4.3. Let be an edge in a graph pattern query and be an edge in a view . Edge in is covered by edge in iff there is a homomorphism from to that maps to such that if is a child edge then is also a child edge.
The proof can be found in the full version of the paper [
Redundant Query Edges. Two graph pattern queries are equivalent if they have the same answer on any data graph. A graph pattern query can have redundant edges. An edge in a query is redundant if its removal from results in a query which is equivalent to . A descendant edge = (, ) in a query is transitive if there is a path from to in other than edge . Clearly, a transitive edge is redundant. Therefore, transitive edges can be removed from without altering the answer of . that the answer of query can be computed using only the answers of the materialized view(s).
Definition 4.4. Let be a query and V be a set of materialized views which can be used for answering . Query can be answered using the views in V if, for every data graph, the answer of can be computed from a relational algebra expression in {, , ⊲⊳, ∪} involving exclusively the answers of the views in V.
The following theorem provides necessary and sufficient conditions for answering a query using exclusively a set of materialized views.
THEOREM 4.5. Let be a query and V be a set of usable views. Query can be answered using the views in V if and only if every non-redundant edge in is covered by an edge of a view in V.
The proof can be found in the full version of the paper [
Given an edge in a query and a view , the covering set of in , denoted (, ), is the set of edges in which cover . Given a set of views V, the covering set of in V, denoted (, V), is defined as (, V) = Ð ∈V (, ). Based on Theorem 4.5, can be answered using V if (, V) ≠ ∅ for every non-redundant edge of .
Minimal Set of Views. A query edge can be covered by multiple view edges of the same and/or different views. However, it is possible that not all of the usable views are needed for answering the query.
Definition 4.6. Let be a query and let V be a set of views such that can be answered using the views in V. Set V is minimal if there is no proper subset V ′ of V such that can be answered using the views in V ′.
Set V ′ does not have redundant views. In the example of Figure 2, query can be answered using the view set {1, 2, 3} which is minimal. We present in the next section an algorithm which computes a minimal set of views for answering a query. 5
the presence of one or multiple materialized views, it is possible In this Section, we present an algorithm called SumGraphBuild which computes a summary graph for a pattern query using the materializations (summary graphs) of the views in a view set V. Algorithm SumGraphBuild uses another algorithm, called FindQCover, which computes the covering set (, ) of a view for each query edge . Therefore, Algorithms SumGraphBuild and FindQCover can be used to check if a query can be answered using the view set V. Finally, we present an algorithm called FindMinimalVSet which finds a minimal set of views for answering a query from a view pool.
Computing the Covering View Edges for a Query Edge. Algorithm FindQCover, shown in Algorithm 1, takes as input a query and a view and returns the covering sets of the edges and nodes of in through a function on the nodes and edges of . The covering set of a query node in a view is defined analogously to the covering set of a query edge in a view. Algorithm FindQCover ifrst calls procedure homEnumerate to enumerate all the homomorphisms from to that satisfy the condition of Theorem 4.3 (line 5). It encodes homomorphisms as n-ary tuples, where n is the number of nodes in (lines 1,2). The homomorphisms found are stored in set (line 4). () denotes the covering set of query edge in and () denotes the covering nodes of query node in (line 6). Procedure homEnumerate performs a recursive backtracking search to find (candidate) matches in for the nodes of iteratively, one at a time, according to the chosen order (line 1) before returning any generated homomorphism. Finding homomorphisms of graphs to graphs is an NP-hard problem but this is not an issue in this context since the number of nodes and edges of queries and views is restricted. Using set , Algorithm FindQCover calls procedure findCover to compute the covering nodes and edges of in .
Algorithm SumGraphBuild on the query and the view 1 of Figure 2 will return ( (1, 2)) = {(1, 2)}, ( (1, 2)) = ∅, and ( (1, 2)) = ∅, as there is only one homomorphism from 1 to .
Graphs of the Materialized Views. Algorithm SumGraphBuild, shown in Algorithm 2, takes as input a query and a set of materialized views (summary graphs) V, and produces a summary graph for in the form of a function on the nodes and edges of representing their candidate occurrence sets. The algorithm consists of two phases: the first phase initializes the candidate occurrence sets () of the nodes and edges of (line 1) and the second phase builds a summary graph by iteratively refining the candidate occurrence sets generated in the first phase until a fixed point is reached (lines 2-4).
To initialize function for the node and edges of , SumGraphBuild begins by computing the covering sets of the nodes and edges of with respect to each view in V using algorithm FindQCover (Algorithm 1) (lines 3-4 in Procedure initializeCos()). Then, for every node in , the algorithm intersects the occurrence sets ( ) of the covering nodes ∈ () to obtain the candidate occurrence set () (lines 5-6). Similarly, for every edge in , it intersects the occurrence sets ( ) of the covering edges ∈ ( ) to obtain the candidate occurrence set ( ) (lines 7-11).
In the second phase, SumGraphBuild refines function using two procedures, which iterate on the edges of in different directions. The first procedure, called forwardPrune(), visits each edge = (, ) ∈ from the tail node to the head node , and removes node and its associated outgoing edges from ( ) and ( ), respectively, if there is no ∈ ( ) such that Algorithm 1 Algorithm FindQCover.
Input: Graph pattern query , and graph pattern view . Output: Function on the nodes and edges of . 1. Pick an order 1, . . . , for the nodes of ; 2. Let be a n-tuple initialized so that [ ] is for ∈ [1, ]; 3. Let be the set of nodes of having the same label as view node ; 4. := ∅ /* set records the homomorphisms from to */ 5. homEnumerate(1, ); 6. For every node in and for every edge in , () = ∅ and () = ∅; 7. findCover(); 8. return ; Procedure homEnumerate(index , tuple ) 1. if (=+1) then 2. add to and return; 3. := { | (, ) ∈ ( , ) ∈ , ∈ [1, − 1] } 4. ′ := ; 5. for (every ∈ ) do 6. ′ := { ∈ ′ | ≺ [ ] [ ] ≺ }; 7. for (every ∈ ′ ) do 8. if (( , ) is a child edge in and ( [ ], ) is not a child edge in ) or ((, ) is a child edge in and (, [ ]) is not a child edge in ) then 9. Remove from ′ ; 10. for (every node ∈ ′ ) do 11. [ ] := ; 12. homEnumerate( + 1, ); Procedure findCover() 1. for (every tuple ∈ ) do 2. for (every node ∈ ) do 3. add to ( [ ]); 4. for every edge (, ) in do 5. if = ( [ ], [ ]) is an edge in which is a child edge if (, ) is a child edge then 6. add (, ) to (); ( , ) is an occurrence of in ( ). The second procedure, called backwardPrune(), visits each edge = (, ) ∈ from the head node to the tail node and removes and its associated incoming edges from ( ) and ( ), respectively, if there is no ∈ ( ) such that ( , ) is an occurrence in ( ). The above process is repeated until function becomes stable, i.e., no further removals can be applied to it.
Finally, the refined function representing the summary graph of is returned to the user (line 5).
Consider the query and the views 1, 2, 3 and 4 in the example of Figure 2. Algorithm SumGraphBuild on the answer graph for 1 of Figure 2(c) and the answer graphs for the views 2, 3 and 4 (not shown in figure) will return the summary graph of Figure 1(d) which is, in fact, the answer graph of .
Note that the candidate occurrence sets of the query node and edges can be stored as bitmaps on data graph nodes resulting not only in space savings but also in substantial performance savings as all candidate occurrence set intersection operations can be implemented as bit-wise AND operations.
in Algorithm 3, takes as input a set of views V which can be used for answering and returns a minimal subset V ′ of V which can be used for answering . The algorithm begins with an empty set of views V ′. It adds a view to V ′ as long as this view covers at least one query edge not covered by the set of views already
Input: Graph pattern query and set V of materialized views on which can be used for answering .
Output: A summary graph of on (represented by function on the nodes and edges of ). 1. initializeCos(); 2. while ( has changes) do 3. forwardPrune(); 4. backwardPrune(); 5. return ; Procedure initializeCos() 1. For every node ∈ , initialize () to be () . 2. For every edge ∈ , initialize ( ) to be ∅ 3. for (every view ∈ V) do 4. := (, ); 5. for (every node ∈ ) do 6. ():= () ∩ ∈ () (); 7. for (every edge ∈ ) do 8. if ( () = ∅) then 9. () := ∩ ∈ () ( ); 10. else 11. () := () ∩ ∈ () ( ); Procedure forwardPrune() 1. for (each edge = (, ) ∈ and each ∈ ( )) do 2. if (there is no ∈ ( ) such that ( , ) is an occurrence in ( )) then 3. Remove and its associated outgoing edges from ( ) and ( ), respectively; Procedure backwardPrune() 1. for (each edge = (, ) ∈ and each ∈ ( )) do 2. if (there is no ∈ ( ) such that ( , ) is an occurrence in ( )) then 3. Remove and its associated incoming edges from ( ) and ( ), respectively;
Input: Graph pattern query and a set V of views which can be used for answering .
Output: A minimal set V ′ ⊆ V of views which can be used for answering . 1. V′ := ∅; 2. findViews(); 3. removeRedundant();
Procedure findViews() 1. := (); 2. while ( ≠ ∅) do 3. Select an edge in ; 4. Find a view in V which has an edge covering ; 5. Let be the set of edges in which are covered by ; 6. V′ := V′ ∪ { }; 7. := − ; Procedure removeRedundant()
/* the set of uncovered edges of */ 1. for (every view ∈ V′) do 2. if ( can be answered using exclusively V′ − { } ) then 3. Remove from V′; selected in V ′. After all the query edges are covered, the algorithm eliminates redundant views by checking if the removal of that view would cause a query edge to be uncovered by the set of views in V ′.
In the example of Figure 2, Algorithm 3 will initially add to V ′ all the views 1, 2, 3 and 4 if the views are considered in the order 1, 2, 3, 4. It will subsequently identify the view 3 as redundant and it will remove it from V ′ to return the minimal view set {1, 2, 4}.
As our experiments show, considering additional views for answering a query beyond a set of views that cover all the edges of does not significantly reduce the query evaluation cost. Thus, a minimal set of views from the materialized view pool constitutes a reasonable choice for answering a query. 6
In this section, we present an experimental evaluation of our materialized view approach in terms of time performance and scalability. 6.1
Algorithms in comparison. We implemented our approach for answering queries using materialized views. In our implementation of Algorithm SumGraphBuild, we used bitmaps to represent query and view node occurrence sets and adjacency lists and bit-wise AND operations for intersecting sets. We refer to this approach in this section as MatView.
We compare MatView with the approach presented in [
The main difference between FltSim and SumGraphBuild lies in the summary graph edge construction: FltSim needs to access a reachability index on in order determine the existence of reachability relationships between nodes in the candidate occurrence sets and connect them by edges. In contrast, SumGraphBuild obtains edges for the candidate occurrence sets of the query edges from the candidate occurrence sets of the covering view edges. This is much cheaper than accessing a reachability index and gives the upper hand to MatView which benefits from the materialized views. We refer to the base approach that does not use materialized views as FltSim.
We do not compare MatView with other approaches as FltSim is
shown in [
A query edge can be covered by more than one view edge. Algorithm SumGraphBuild initially intersects the candidate occurrence sets of its covering view edges in order to compute the candidate occurrence set of a query edge. The more covering edges on are intersected, the smaller their resulting candidate occurrence set would be when this is computed by algorithm The average number of covering edges for a query edge in ︁∑ ∈V (, V) =
(, )/| () |
When (, V) = 1, each query edge is covered by exactly one view edge. We expect that the higher (, V) is, the smaller the summary graph will be. The lowest value for (, V) is produced by a minimal set V.
For each query computation, we used a set of views V with the same number of edges. With the exception of the experiment where (, V) is varied, (, V) is manitained within a fixed range:
1 ≤ (, V) ≤ 2. For the experiments in sections 6.2, 6.3, and 6.6, all sets of views V used by MatView contained views with mixed edges and exactly two edges, and were chosen to be minimal using Algorithm 3.
Metrics. We measured the evaluation time of the queries in a query set in seconds (sec). In the case of FltSim, this includes the preprocessing time (i.e., the time spent on filtering data graph nodes and edges). Given that the number of query results can be very large, we terminated the evaluation of a query after finding 107 matches.
Our implementation was coded in Java. All the experiments reported were performed on a 64-bit Linux machine equipped with an Intel Xeon 6240 @ 2.60 Hz processor and 768GB RAM.
In all cases, the execution time for all algorithms increased when the total number of graph nodes increased. MatView provided significantly better performance than FltSim for evaluating the two queries. In addition, the slope of is much steeper than that of .
We also observed that in Figure 7, for the data point with 100K nodes, the evaluation time for MatView was very small. This is because, in contrast to the other data points, there were no matches for query 7; while FltSim had to spend time to filter out irrelevant nodes and edges from the data graph before it discovered that the query has an empty answer, MatView was able to quickly discover that this query has empty answer.
(a) 5 (b) 7
We ran experiments comparing the performance of FltSim and MatView varying (, V) (using a different number of views). All views had mixed edges and exactly two edges. We started by evaluating a query using a minimal set of views, where each query edge is covered by only one covering edge, and gradually added one view at a time. Each time a new view was added, (, V) increased slightly. In Figure 8 we plotted the value of (, V) for each new set of views V on the top row label of the X-axis, and plotted the number of views in V on the bottom row label of the X-axis.
The results for two of these queries, 5 and 7, that are run on the bs data graph with 20 labels and 350K nodes are shown in Figure 8. We observed that for sets of views with a higher (, V), the summary graphs obtained were only smaller, but the differences did not have much impact on the evaluation times. Thus, selecting a minimal view set for evaluating query is a viable solution. 6.5
We compared the performance of MatView and FltSim using views with two edges versus views with three edges. Both the set of views with two edges and the set of views with three edges met the condition where 1 < (, V) < 2; this was achieved by varying the number of views within V such that, for each query , the set with three-edge views contained less views than the set with two-edge views.
The results for all 10 queries evaluated on the bs data graph with 20 labels and 350K nodes are shown in Figure 9. Overall, for nine out of ten queries, we found that using views with three edges obtained better evaluation times than using views with two edges, while for one of the queries (3), they obtained approximately the same evaluation time. We measured the execution time of the two appoaches varying the number of edges in the queries. To obtain these queries, we started with the original query, then removed one edge at a time.
The results for two of these queries, 2 and 5, on the bs data graph with 20 labels and 350K nodes using a logarithmic scale are shown in Figure 10. We can see that the execution time does not follow a specific pattern as adding on more edge to a query can increase or decrease the number of query results. 6.7
The experiments reported here have examined the performance of pattern query evaluation algorithms on graphs. The results can be summarized as follows: - The performance of a graph pattern matching algorithm is affected significantly by costly computations using the reachability index. - The view materialization approach MatView significantly reduces evaluation times by using the view materializations instead of accessing the reachability index. - MatView shows the best efficiency and scalability performance between the two algorithms, while displaying a negligible occurrence set intersection time cost. This demonstrates the effectiveness of the view materialization approach. 7
Answering queries using views has been extensively studied for
relational data (see [
Fan et al. [
More recently, Trindade et al. [
To speed up graph query processing, Wang et al. [
The problem we address in this paper is different than those addressed by existing graph view approaches. We consider general graph patterns and not simply paths or trees. Our patterns contain child and descendant edges, allowing for both edge-to-edge and edge-to-path matches to the data graph. Patterns are mapped to the data graph using homomorphisms which relax the strict one-to-one mapping entailed by isomorphisms and, unlike graph simulation, preserve the topology of the data graph. We adopt the concept of a summary graph to encode all possible homomorphisms from a query pattern to the data graph, and materialize views as summary graphs. By generating a summary graph for a query pattern using the summary graphs of multiple materialized views, our approach greatly reduces the time to find the homomorphic matches of the query. 8
We have addressed the problem of answering graph pattern queries using graph pattern materialized views to efficiently evaluate such queries on large data graphs under homomorphisms. We considered a broad class of pattern queries that involve both node reachability and direct relationships. We suggested an original approach which materializes views as summary graphs, therein compactly representing the homomorphic matches of the views. In this context, we characterized the view usability problem in terms of query edge coverage, and provided necessary and suf-fi cient conditions for answering graph pattern queries using views. We designed algorithms for deciding whether a query can be answered from materialized views, for computing query summary graphs from the summary graphs of the views, and for producing minimal sets of views for answering a query. Our experimental results showed that our approach outperforms, by several orders of magnitude, approaches that do not use materialized views, and provides much better scalability.
We are currently working on scale-independently answering queries using views based on the framework set in this paper.