A Dependency-Extended Method of Multi-pattern Matching . . .
185
In one-hop traversal on temp results, given any an initial data vertex v d1
and its a obtained vertex v d2 , there is a pattern vertex v q1 , satisfying v d1 is an
instance of v q1 and e(v d1 , v d2 ) ∈ RE q1 ∩oE vq 1 , then triple instance d t (v d1 , e,
v d2 ) is written into the results of q 1 . The one-hop traversal on temp results is
continuous executed until no new triple instance of temp results is written.
(4) Taking final initial data vertexes on temp results as initial data vertexes
on data graphs, and executing the (2) and (3) in the process of obtaining the
results of root node.
(5) Re-executing (1)–(4) until results of all BGP graphs are obtained.
e7
a1
f1
e5
e1
e2
e6
e4
e3
e2
e4
b1
c1
d1
g1
d2
g2
b1
?B [e1, e2]
b1 [e1, c1], [e2, d1],[e2, d2]
d1
?D [e2]
d1 [e2, b1]
?C
[e2]
c1
[e1, b1]
c1
d2
?D [e2]
d2 [e2, b1]
0
-1 e1,e2
4
3 e6,e7
?A [e7]
2
3
e6
?C
[e3,e6]
?D
[e4,e6]
f1
?F [e7]
f1 [e7, a1]
?A
[e7]
a1
[e7, f1]
d1
a1
c1
?C [e6]
c1 [e6, d1]
?D
[e6]
d1
[e6, c1]
d1
c1
?C [e6]
c1 [e6, d1]
?D
[e6]
d1
[e6, c1]
b1
?B [e3]
b1 [e3, g1]
?D
[e4]
d1
[e4, g1]
?D
[e4]
d2
[e4, g2]
?G
[e3,e4]
g1
[e4, b1]
d1
d2
g1 g2
?G [e3,e4]
g2 [e4, b2]
3
0
e5
?B [e5]
b1
?B [e5]
b1
[e5, a1]
?A
[e5]
a1
[e5, b1]
a1
1
0 e3,e4
?B
[e3,e5]
?D
[e4,e6]
BT:
BT:
BT:
BT:
BT:
(a) A Data Graph
(b) q0 Node
(c) q1 Node
(d) q3 Node
(e) q4 Node
(f) q2 Node
Data node matched outer NFT
Data node matched inner NFT
b1 [e3, g1]
Temp:
d1 [e3, g1]
d1 [e4, g2]
b1 [e5, a1]
a1 [e7, f1]
Temp:
c1 [e6, d1]
d1 [e6, c1]
?G
[e3,e4]
Fig. 3. Processing of multi-patterns matching for RDF graphs
The processing of M-PM is described in Fig. 3a represents a matched data
graph. (b)–(f) depicts the obtained results of multiple BGP graphs on D-Tree in
Fig. 2.
q 0 . The results of q 0 are only assisted with inner table, because q 0 is a root
node of D-Tree. Firstly, F i : RE q0 ∩ iN F T → →?B, iE ?B (e 1 , e 2 ) iE ?C (e 1 )
and iE ?D (e 2 ), and arbitrarily choosing one of ?B, ?C, and ?D as a fixed
pattern vertex. Assumed that ?B is a fixed pattern vertex, then b 1 is an instance
of ?B and set as an initial data vertex on (a). Through one-hop traversal from b 1 ,
triple instances [b 1 , [e 1 , c 1 ], [e 2 , d 1 ], [e 2 , d 2 ]] are written into the results of q 0 , and
triple instances [b 1 , [e 3 , a 1 ], [e 5 , g 1 ]] are written into temp results. Then, c 1 , d 1
and d 2 are obtained sequentially and set as the next initial vertexes, respectively.
Through one-hop traversals of c 1 , d 1 , and d 2 , triple instances [c 1 , [e 1 , b 1 ]], [d 1 ,
[e 2 , b 1 ]], and [d 2 , [e 2 , b 1 ]] are written into the results of q 0 , and triple instances
[d 1 , [e 4 , g 1 ]], [d 2 , [e 4 , g 2 ]], [c 1 , [e 6 , d 1 ]] and [d 1 , [e 6 , c 1 ]] are written into temp
results. Finally, final results of q 0 are carried out because b 1 has included into
results of q 0 .
q 1 . The results of q 1 are assisted with inner and outer tables, and final results
of q 0 are copied to the results of q 1 , because q 0 is a parent node of q 1 . Firstly,
RE q1 ∩ oN F T = oE ?B (e 5 ) thus, ?B is a fixed pattern vertex, then b 1 is
an instance of ?B and set as an initial data vertex on temp results. Through
185
In one-hop traversal on temp results, given any an initial data vertex v d1
and its a obtained vertex v d2 , there is a pattern vertex v q1 , satisfying v d1 is an
instance of v q1 and e(v d1 , v d2 ) ∈ RE q1 ∩oE vq 1 , then triple instance d t (v d1 , e,
v d2 ) is written into the results of q 1 . The one-hop traversal on temp results is
continuous executed until no new triple instance of temp results is written.
(4) Taking final initial data vertexes on temp results as initial data vertexes
on data graphs, and executing the (2) and (3) in the process of obtaining the
results of root node.
(5) Re-executing (1)–(4) until results of all BGP graphs are obtained.
e7
a1
f1
e5
e1
e2
e6
e4
e3
e2
e4
b1
c1
d1
g1
d2
g2
b1
?B [e1, e2]
b1 [e1, c1], [e2, d1],[e2, d2]
d1
?D [e2]
d1 [e2, b1]
?C
[e2]
c1
[e1, b1]
c1
d2
?D [e2]
d2 [e2, b1]
0
-1 e1,e2
4
3 e6,e7
?A [e7]
2
3
e6
?C
[e3,e6]
?D
[e4,e6]
f1
?F [e7]
f1 [e7, a1]
?A
[e7]
a1
[e7, f1]
d1
a1
c1
?C [e6]
c1 [e6, d1]
?D
[e6]
d1
[e6, c1]
d1
c1
?C [e6]
c1 [e6, d1]
?D
[e6]
d1
[e6, c1]
b1
?B [e3]
b1 [e3, g1]
?D
[e4]
d1
[e4, g1]
?D
[e4]
d2
[e4, g2]
?G
[e3,e4]
g1
[e4, b1]
d1
d2
g1 g2
?G [e3,e4]
g2 [e4, b2]
3
0
e5
?B [e5]
b1
?B [e5]
b1
[e5, a1]
?A
[e5]
a1
[e5, b1]
a1
1
0 e3,e4
?B
[e3,e5]
?D
[e4,e6]
BT:
BT:
BT:
BT:
BT:
(a) A Data Graph
(b) q0 Node
(c) q1 Node
(d) q3 Node
(e) q4 Node
(f) q2 Node
Data node matched outer NFT
Data node matched inner NFT
b1 [e3, g1]
Temp:
d1 [e3, g1]
d1 [e4, g2]
b1 [e5, a1]
a1 [e7, f1]
Temp:
c1 [e6, d1]
d1 [e6, c1]
?G
[e3,e4]
Fig. 3. Processing of multi-patterns matching for RDF graphs
The processing of M-PM is described in Fig. 3a represents a matched data
graph. (b)–(f) depicts the obtained results of multiple BGP graphs on D-Tree in
Fig. 2.
q 0 . The results of q 0 are only assisted with inner table, because q 0 is a root
node of D-Tree. Firstly, F i : RE q0 ∩ iN F T → →?B, iE ?B (e 1 , e 2 ) iE ?C (e 1 )
and iE ?D (e 2 ), and arbitrarily choosing one of ?B, ?C, and ?D as a fixed
pattern vertex. Assumed that ?B is a fixed pattern vertex, then b 1 is an instance
of ?B and set as an initial data vertex on (a). Through one-hop traversal from b 1 ,
triple instances [b 1 , [e 1 , c 1 ], [e 2 , d 1 ], [e 2 , d 2 ]] are written into the results of q 0 , and
triple instances [b 1 , [e 3 , a 1 ], [e 5 , g 1 ]] are written into temp results. Then, c 1 , d 1
and d 2 are obtained sequentially and set as the next initial vertexes, respectively.
Through one-hop traversals of c 1 , d 1 , and d 2 , triple instances [c 1 , [e 1 , b 1 ]], [d 1 ,
[e 2 , b 1 ]], and [d 2 , [e 2 , b 1 ]] are written into the results of q 0 , and triple instances
[d 1 , [e 4 , g 1 ]], [d 2 , [e 4 , g 2 ]], [c 1 , [e 6 , d 1 ]] and [d 1 , [e 6 , c 1 ]] are written into temp
results. Finally, final results of q 0 are carried out because b 1 has included into
results of q 0 .
q 1 . The results of q 1 are assisted with inner and outer tables, and final results
of q 0 are copied to the results of q 1 , because q 0 is a parent node of q 1 . Firstly,
RE q1 ∩ oN F T = oE ?B (e 5 ) thus, ?B is a fixed pattern vertex, then b 1 is
an instance of ?B and set as an initial data vertex on temp results. Through