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