184
Y. Sun et al.
then ?G and e 3 are assigned into iNFT. For a root node of D-Tree, all vertexes
and edges are assigned into iNFT. Note that the directed characteristic of edges
are not considered; that is, NFT is executed on ground graphs of directed BGP
graphs.
3 M-PM Algorithm
M-PM algorithm is based on D-Tree and NFT. The matched results were
response sequentially with multiple BGP graphs through a pre-order traversal
on D-Tree.
Before description of MP algorithm, a vertex relation between BGP and data
graph is given. Given any a vertex of data graph v d , there is a pattern vertex
v q of one BGP graph matching v d , then v d is an instance of v q . Given any two
vertexes of data graph v d1 and v d2 , there are two pattern vertexes v q1 and v q2 ,
satisfying e (v d1 , v d2 )= e(v q1 , v q2 ), v d1 is an instance of v q1 and v d2 is an instance
of v q2 , then d t v d1 , e, v d2 is a triple instance of d t v q1 , e, v q2 .
In M-PM algorithm, the results of multiple query graphs are incrementally
acquired through a pre-order traversal on D-Tree. The process of obtaining the
results of root node q 0 is described as follows:
(1) Giving a fixed pattern vertex v q0 of q 0 , acquiring a data vertex v d that is
an instance of v q0 and setting v d as an initial data vertex.
The fixed pattern vertexes are chosen by computation of inner table and DTree. A pattern vertex v q0 is fixed if and only if RE q0 ∩ iE vq 0 = ∅. The fixed
pattern vertex v q0 is obtained by a function F i : RE q0 ∩ iN F T → →v q0 , iE vq 0 .
(2) Obtaining other vertexes sequentially by one-hop traversal from v d and
setting as initial data vertexes of next one-hop traversal.
In one-hop traversal on data graphs, given any an initial data vertex v d1 and
its a obtained vertex v d2 , there is a pattern vertex v q , satisfying v d1 is an instance
of v q and e(v d1 , v d2 ) ∈ iE vq , then triple instance d t (v d1 , e, v d2 ) is written into the
results of q 0 . And if e(v d1 , v d2 ) ∈ oE vq , triple instance d t v d1 , e, v d2 is written
into temp results.
(3) Carrying out the results of q 0 until there are not new triple instances to
be written.
The process of obtaining the results of child nodes is different with root node.
It needs to be assisted by parent nodes and temp results.
(1) Copying parent node results to child node results, because parent node
results are a part of child node results.
(2) Giving a pattern node v q1 of the child node q 1 , then acquiring a data
vertex v d that is an instance of v q1 and setting v d as an initial data vertex on
temp results.
The fixed pattern vertexes are chosen by computation of outer table and
D-Tree. A pattern vertex v q0 is fixed if and only if RE q0 ∩ oE vq 0 = ∅. The fixed
pattern vertex v q0 is obtained by a function F o : RE q0 ∩ oN F T → →v q0 , oE vq 0 .
(3) Obtaining other vertexes of temp results sequentially by one-hop traversal
from v d and setting as initial data vertexes of next one-hop traversal.
Y. Sun et al.
then ?G and e 3 are assigned into iNFT. For a root node of D-Tree, all vertexes
and edges are assigned into iNFT. Note that the directed characteristic of edges
are not considered; that is, NFT is executed on ground graphs of directed BGP
graphs.
3 M-PM Algorithm
M-PM algorithm is based on D-Tree and NFT. The matched results were
response sequentially with multiple BGP graphs through a pre-order traversal
on D-Tree.
Before description of MP algorithm, a vertex relation between BGP and data
graph is given. Given any a vertex of data graph v d , there is a pattern vertex
v q of one BGP graph matching v d , then v d is an instance of v q . Given any two
vertexes of data graph v d1 and v d2 , there are two pattern vertexes v q1 and v q2 ,
satisfying e (v d1 , v d2 )= e(v q1 , v q2 ), v d1 is an instance of v q1 and v d2 is an instance
of v q2 , then d t v d1 , e, v d2 is a triple instance of d t v q1 , e, v q2 .
In M-PM algorithm, the results of multiple query graphs are incrementally
acquired through a pre-order traversal on D-Tree. The process of obtaining the
results of root node q 0 is described as follows:
(1) Giving a fixed pattern vertex v q0 of q 0 , acquiring a data vertex v d that is
an instance of v q0 and setting v d as an initial data vertex.
The fixed pattern vertexes are chosen by computation of inner table and DTree. A pattern vertex v q0 is fixed if and only if RE q0 ∩ iE vq 0 = ∅. The fixed
pattern vertex v q0 is obtained by a function F i : RE q0 ∩ iN F T → →v q0 , iE vq 0 .
(2) Obtaining other vertexes sequentially by one-hop traversal from v d and
setting as initial data vertexes of next one-hop traversal.
In one-hop traversal on data graphs, given any an initial data vertex v d1 and
its a obtained vertex v d2 , there is a pattern vertex v q , satisfying v d1 is an instance
of v q and e(v d1 , v d2 ) ∈ iE vq , then triple instance d t (v d1 , e, v d2 ) is written into the
results of q 0 . And if e(v d1 , v d2 ) ∈ oE vq , triple instance d t v d1 , e, v d2 is written
into temp results.
(3) Carrying out the results of q 0 until there are not new triple instances to
be written.
The process of obtaining the results of child nodes is different with root node.
It needs to be assisted by parent nodes and temp results.
(1) Copying parent node results to child node results, because parent node
results are a part of child node results.
(2) Giving a pattern node v q1 of the child node q 1 , then acquiring a data
vertex v d that is an instance of v q1 and setting v d as an initial data vertex on
temp results.
The fixed pattern vertexes are chosen by computation of outer table and
D-Tree. A pattern vertex v q0 is fixed if and only if RE q0 ∩ oE vq 0 = ∅. The fixed
pattern vertex v q0 is obtained by a function F o : RE q0 ∩ oN F T → →v q0 , oE vq 0 .
(3) Obtaining other vertexes of temp results sequentially by one-hop traversal
from v d and setting as initial data vertexes of next one-hop traversal.