Algebraic Optimization of RDF Graph Pattern Queries on MapReduce - Large Scale and Big Data: Processing and Management - page 212

• Perfect Triplegroup: It is an unambiguous triplegroup, which contains no

properties except those in specific star patterns. Therefore, it can be con-
sidered as a valid answer for a query. The triplegroups tg 1 and tg 2 in Figure
6.13b are examples of perfect triplegroups.

Since the current TG _ GroupFilter semantics assume perfect triplegroups as
input, we need to extend its definition to deal with ambiguous triplegroups. Specifically,
the TG _ GroupFilter needs to split any ambiguous triplegroup ta into a set of sub-
groups (not necessarily disjoint) representing all perfect triplegroups that are derivable
ta with respect to the query. However, care must be taken not to introduce redundant or
invalid triplegroups, which could result in spurious results. This is handled by a con-
cept we call cloning , generating perfect triplegroups from an ambiguous triplegroup.

Example 6.6: Clone Operation

Figure 6.13b shows how perfect triplegroups tg 1 and tg 2 are cloned from the
ambiguous triplegroup tg 0 (note that tg_0 does not contain triples matching SJ3
and hence no triplegroup TG_{type, product, vendor} is generated [“_” means
the subscript notation]). (The detail on the concept of the clone operation and the
proof on losslessness are available in [24].)

6.8.1.2 Implementation of Clone Operation
Algorithm 6.4 shows the algorithm of the extended operator POTGGroupPackage ,
which supports handling of ambiguous triplegroups. In the reduce phase, all tuples
corresponding to the same subject component are processed in the same reduce
function. A bitmap (locBitset) is used to keep track of the property types processed
(line 3) and the (Property, Object) pairs are stored in a temporary map (tempMap in
line 4). After processing all tuples in the group, the locBitSet is matched with all the
equivalence classes (star subpatterns) in the query (ECList in line 5). A match with
a single equivalence class represents a perfect triplegroup (line 10). A match with
more than one equivalence class indicates an ambiguous triplegroup and the tem-
porary map is cloned to retrieve the relevant (Property, Object) pairs corresponding
to the matched star subpatterns (lines 7-8). The cloned maps are then used to create
perfect triplegroups (line 9) corresponding to the star subpatterns required in the
query. A mismatch with ALL star subpatterns results in filtering out of the group
of tuples.

6.8.2 C ase s tuDy : i mPaCt oF s Can -s haring For g raPh
P attern Q ueries with r ePeateD P roPerties
To compare the performance of the relational-style and NTGA-based approaches
and their ability to share scans while processing query patterns involving repeated
properties ( DupPs ), we present a case study evaluating three approaches, (i) 1-join-
per-cycle (SHARD), (ii) 1-star-join-per-cycle (VP approach), and (iii) all-star-joins-
1-cycle (NTGA).