A Dependency-Extended Method of Multi-pattern Matching . . .
181
vertically partition the RDF graphs into a set of tables based on bounded labels
of triple patterns and use a bidirectional index on top of it to locate the required
tables. However, it is hard to migrate the technique of single-pattern matching to
M-PM problem, due to the complex dependent relations among multiple query
graphs.
The multi-pattern’s matching optimization is to identify common tasks
among multiple query graphs and select one exact plan for each query graph.
Ismail et al. [8] propose a dynamic programming solution. The solution can avoid
to generate redundant candidates and reaches the solution set before generating
larger candidates. Zahid Abul-Basher et al. [2] propose a framework for multiple
query optimization. The key idea of this framework is to expand repeatedly the
search wavefront until no new answers are produced, where each search wavefront is guided by non-deterministic finite automata. However, those heuristic
algorithms pay a big cost on training plans.
Therefore, a novel algorithm of M-PM problem is proposed. Firstly, a dependent tree (D-Tree) is designed for reflecting the inclusion of relation among
multiple queries. 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. Then, a node fragmentation table (NFT) is proposed
to solve the crossover problem between inclusive BGP graphs. NFT depicts the
inclusion relations in detail based on residual edges among BGP graphs. Finally,
a M-PM algorithm is designed based on D-Tree and NFT, which can response to
multiple BGP graphs through one traversal of RDF graph. M-PM algorithm can
effectively avoid the re-computations about the matching processing on common
subgraphs of multiple query graphs.
2 Dependent Tree and Node Fragment Tables
The formal definitions of basic graph pattern (BGP) and data graph (DG) are
first given, and then, our problem definition is given.
2.1 Problem Definition
Definition 1. (Basic Graph Pattern) A basic graph pattern BGP(V q , E q , L q ,
φ q , vars q ) is a directed labeled graph, where V q is a set of vertexes; E q represents
a multi-set of directed edges; E q : (u, v) is a directed function denoting a directed
edge from u to v, u, v ∈ V q ; L q is a set of edge and vertex labels; vars is a set
of query variables, and q : V q ∪ E q → (L q ∪ vars q ) is a labeling function that
maps a vertex or an edge to the corresponding label.
Definition 2. (Data Graph) A data graph DG(V d , E d , L d , φ d ) is a directed
labeled graph, where V d is a set of vertexes; E d represents a multi-set of directed
edges; E d : (u, v) is a directed function denoting a directed edge from u to v,
u, v ∈ V d ; L d is a set of edge and vertex labels, and d : V d ∪ E d → (L d ∪ vars d )
is a labeling function that maps a vertex or an edge to the corresponding label.
181
vertically partition the RDF graphs into a set of tables based on bounded labels
of triple patterns and use a bidirectional index on top of it to locate the required
tables. However, it is hard to migrate the technique of single-pattern matching to
M-PM problem, due to the complex dependent relations among multiple query
graphs.
The multi-pattern’s matching optimization is to identify common tasks
among multiple query graphs and select one exact plan for each query graph.
Ismail et al. [8] propose a dynamic programming solution. The solution can avoid
to generate redundant candidates and reaches the solution set before generating
larger candidates. Zahid Abul-Basher et al. [2] propose a framework for multiple
query optimization. The key idea of this framework is to expand repeatedly the
search wavefront until no new answers are produced, where each search wavefront is guided by non-deterministic finite automata. However, those heuristic
algorithms pay a big cost on training plans.
Therefore, a novel algorithm of M-PM problem is proposed. Firstly, a dependent tree (D-Tree) is designed for reflecting the inclusion of relation among
multiple queries. 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. Then, a node fragmentation table (NFT) is proposed
to solve the crossover problem between inclusive BGP graphs. NFT depicts the
inclusion relations in detail based on residual edges among BGP graphs. Finally,
a M-PM algorithm is designed based on D-Tree and NFT, which can response to
multiple BGP graphs through one traversal of RDF graph. M-PM algorithm can
effectively avoid the re-computations about the matching processing on common
subgraphs of multiple query graphs.
2 Dependent Tree and Node Fragment Tables
The formal definitions of basic graph pattern (BGP) and data graph (DG) are
first given, and then, our problem definition is given.
2.1 Problem Definition
Definition 1. (Basic Graph Pattern) A basic graph pattern BGP(V q , E q , L q ,
φ q , vars q ) is a directed labeled graph, where V q is a set of vertexes; E q represents
a multi-set of directed edges; E q : (u, v) is a directed function denoting a directed
edge from u to v, u, v ∈ V q ; L q is a set of edge and vertex labels; vars is a set
of query variables, and q : V q ∪ E q → (L q ∪ vars q ) is a labeling function that
maps a vertex or an edge to the corresponding label.
Definition 2. (Data Graph) A data graph DG(V d , E d , L d , φ d ) is a directed
labeled graph, where V d is a set of vertexes; E d represents a multi-set of directed
edges; E d : (u, v) is a directed function denoting a directed edge from u to v,
u, v ∈ V d ; L d is a set of edge and vertex labels, and d : V d ∪ E d → (L d ∪ vars d )
is a labeling function that maps a vertex or an edge to the corresponding label.