182
Y. Sun et al.
The difference between BGP and DG is that the label of DG must be a
constant and the label of BGP can be a variable. The variables at the predicate
position are not considered in this paper because such variables are not common
in real-world query graphs, as shown in a previous study [3].
The basic graph pattern matching (B-PM) refers to finding all data subgraphs
that are isomorphic to a BGP. However, concurrent execution of multi-queries is
more realistic than single query in real world. And re-computations of common
subgraphs always limit the time efficiency of matching processing. Therefore, an
extended problem definition of B-PM is given as follows.
Definition 3. (M-PM Problem) Given a set of basic graph patterns Q =(q 1 ,
q 2 ,· · · q m ) and a set of data graphs D=(d 1 , d 2 , · · · , d n ), m, n ∈ N
+ . A multipattern matching (M-PM) refers to finding all data subgraphs from D that are
isomorphic to basic graph patterns of Q.
To reflect the inclusion relation among multiple BGP graphs, a dependent
tree (D-Tree) is designed. D-Tree exactly describes the executed orders of multiple BGP graphs. However, the inclusion relations are difficult to operate the
crossover between any two inclusive BGP graphs, because inclusion relation is an
abstract and single representation. Therefore, a node fragmentation table (NFT)
is proposed to solve the crossover problem between inclusive BGP graphs. NFT
detailedly depicts the inclusion relation based on residual edges among BGP
graphs. Based on D-Tree and NFT, a M-PM algorithm is designed to response
to multiple BGP graphs through one traversal of RDF graph. The working mechanisms about D-Tree and NFT are explained in Sect. 2.2.
2.2 Dependent Tree and Node Fragmentation Table
A D-Tree describes the inclusion relations among multiple BGP graphs.
The dependent relation among BGP graphs is presented by the dominating
set of queries. Given any two BGP graphs q 1 and q 2 , satisfying E q1 ⊂ E q2 , then
q 1 dominates q 2 , defined as q 1 ≺ q 2 . Given any two BGP graphs q 1 , q 2 , and an
edge e, satisfying e /
∈ q 1 , e ∈ q 2 and q 1 ≺ q 2 , then e is a residual edge of q 2 (RE q2
for short). That is, q 2 is at rear of q 1 in matching processing if and only if q 1 ≺ q 2 .
Figure 1 represents the multiple BGP graphs and a dependent Tree. Figure 1.
(1) depicts the multiple BGP graphs, and there are dependent relations among
BGP graphs. Figure 2b presents a D-Tree, where 0, 1, . . ., n refer to the subscripts
of q 0 , q 1 , . . ., q n , n ∈ N
+ and −1 is a subscript of virtual node that assigned to
a root node of each tree. Each node of D-Tree also contains the residual edges
with its parent node.
A node fragmentation table (NFT) is to solve the crossover problem between
inclusive BGP graphs. NFT detailedly depicts the inclusion relation among BGP
graphs based on residual edges.
NFT is classified as inner NFT and outer NFT, where inner and outer NFTs
are constructed by inner and outer edges, respectively. Given a BGP graph q
and a vertex u ∈ V q , there is a vertex v of V q , such that e(u, v) ∈ E q , then
edge e is an inner edge of vertex u. Given any two BGP graphs q 1 , q 2 and a
Y. Sun et al.
The difference between BGP and DG is that the label of DG must be a
constant and the label of BGP can be a variable. The variables at the predicate
position are not considered in this paper because such variables are not common
in real-world query graphs, as shown in a previous study [3].
The basic graph pattern matching (B-PM) refers to finding all data subgraphs
that are isomorphic to a BGP. However, concurrent execution of multi-queries is
more realistic than single query in real world. And re-computations of common
subgraphs always limit the time efficiency of matching processing. Therefore, an
extended problem definition of B-PM is given as follows.
Definition 3. (M-PM Problem) Given a set of basic graph patterns Q =(q 1 ,
q 2 ,· · · q m ) and a set of data graphs D=(d 1 , d 2 , · · · , d n ), m, n ∈ N
+ . A multipattern matching (M-PM) refers to finding all data subgraphs from D that are
isomorphic to basic graph patterns of Q.
To reflect the inclusion relation among multiple BGP graphs, a dependent
tree (D-Tree) is designed. D-Tree exactly describes the executed orders of multiple BGP graphs. However, the inclusion relations are difficult to operate the
crossover between any two inclusive BGP graphs, because inclusion relation is an
abstract and single representation. Therefore, a node fragmentation table (NFT)
is proposed to solve the crossover problem between inclusive BGP graphs. NFT
detailedly depicts the inclusion relation based on residual edges among BGP
graphs. Based on D-Tree and NFT, a M-PM algorithm is designed to response
to multiple BGP graphs through one traversal of RDF graph. The working mechanisms about D-Tree and NFT are explained in Sect. 2.2.
2.2 Dependent Tree and Node Fragmentation Table
A D-Tree describes the inclusion relations among multiple BGP graphs.
The dependent relation among BGP graphs is presented by the dominating
set of queries. Given any two BGP graphs q 1 and q 2 , satisfying E q1 ⊂ E q2 , then
q 1 dominates q 2 , defined as q 1 ≺ q 2 . Given any two BGP graphs q 1 , q 2 , and an
edge e, satisfying e /
∈ q 1 , e ∈ q 2 and q 1 ≺ q 2 , then e is a residual edge of q 2 (RE q2
for short). That is, q 2 is at rear of q 1 in matching processing if and only if q 1 ≺ q 2 .
Figure 1 represents the multiple BGP graphs and a dependent Tree. Figure 1.
(1) depicts the multiple BGP graphs, and there are dependent relations among
BGP graphs. Figure 2b presents a D-Tree, where 0, 1, . . ., n refer to the subscripts
of q 0 , q 1 , . . ., q n , n ∈ N
+ and −1 is a subscript of virtual node that assigned to
a root node of each tree. Each node of D-Tree also contains the residual edges
with its parent node.
A node fragmentation table (NFT) is to solve the crossover problem between
inclusive BGP graphs. NFT detailedly depicts the inclusion relation among BGP
graphs based on residual edges.
NFT is classified as inner NFT and outer NFT, where inner and outer NFTs
are constructed by inner and outer edges, respectively. Given a BGP graph q
and a vertex u ∈ V q , there is a vertex v of V q , such that e(u, v) ∈ E q , then
edge e is an inner edge of vertex u. Given any two BGP graphs q 1 , q 2 and a