Database Reference
In-Depth Information
using a nested
propMap
, which contains another RDFMap as a value. The
prop-
Map
provides a property-based indexed structure that eliminates the need to iterate
through the tuples in each bag.
6.6.3.2 Implementation of
TG _ GroupBy
In the physical layer,
TG _ GroupBy
in NTGA is mapped into the physical opera-
tors
POTGGroupAnnotator
and
POTGGroupPackage
. As a reminder, physical
operators in MapReduce-based systems are executed in
map
() and
reduce
() functions.
In the
map
phase, the
TripleLoader
loads triples from HDFS and filters them out
if their properties do not match with any properties in a graph pattern. This filtering
process offers some cost savings by avoiding future processing and materialization
for irrelevant triples to a given query. The operator
POTGGroupAnnotator
comes
next to annotate the triples based on the
S
component, for example, tag
t
in triples
T
as (
t
.
S
,
t
). In the
reduce
function, the operator
POTGGroupPackage
is executed,
which packages the same
S
component into an
RDFMap
that corresponds to a sub-
ject triplegroup (line 5-7 of Algorithm 6.1).
Algorithm 6.1:
POTGGroupPackage
Reduce
(
key:Subject Sub,val:List of tuples T
)
;
//locBitSet—record property types in T
//ECList—list of global BitSets for all ECs
1
for each
tup
(
s
,
p
,
o
)
T
do
2
set
p
in
locBitset
;
3
add (
p
,
o
) to
tempMap
;
4
matchedECList match(locBitSet, ECList)
;
5 foreach
EC
matchedECList
do
6
propMap
extract subset of
tempMap
based on
properties in
EC
;
7
emit
RDFMap
(
Sub, EC, propMap
)
;
6.6.3.3 Implementation of
TG _ GroupFilter
TG _ GroupFilter
is also mapped into the
POTGGroupPackage
, that is, the struc-
ture-based filter in
TG _ GroupFilter
is integrated into the
POTGGroupPackage
to filter irrelevant triplegroups based on the query substructures before generating
actual
RDFMap
instances. Algorithm 6.1 describes the algorithm of this operator
using the two types of bit patterns:
global
and
local
bit patterns. The global ones rep-
resent the property types in the query substructures.
Example 6.3: Structure-Based Filtering
Figure 6.10b shows that properties in the two star patterns (
SJ
1 and
SJ
2 in Figure
6.10a) are encoded into two 6-bit bitmaps. The local ones keep track of the prop-
erty types processed as the triples are packaged into a triplegroup (lines 1-3),
Search WWH ::
Custom Search