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

be mapped to a single equivalence class in the current TG _ GroupFilter . This
assumption is no longer valid because the grouping operation ( TG _ GroupBy ) does
not enforce any structural constraints (hence, the need for structural filtering using
TG _ GroupFilter ) and simply assembles related triples. Consequently, the triples
in a triplegroup may span multiple star pattern subqueries.

Example 6.5: Ambiguity due to Repeated Properties

This ambiguity can also occur if a query itself has repeated properties in different
star subqueries. The query in Figure 6.12a includes five unique properties ( hpage ,
type , label , date , and pub ) and both patterns SJ 1 and SJ 2 include type , label , or
date . In addition, it is possible that TG _ GroupBy produces a triplegroup contain-
ing all the five properties. Hence, it is ambiguous to determine the equivalence
class partition to which the triplegroup belongs. Therefore, we need to extend
NTGA for managing and identifying triplegroups in a way that relaxes the assump-
tion of a single equivalence class for each triplegroup.

6.8.1.1 Classification of Triplegroups
We first classify the triplegroup into three types: well-formed , ambiguous , and per-
fect triplegroups. (The formal definitions are available in [24]).

• Well-Formed Triplegroup: It contains triples whose properties overlap
with some star pattern in a query; thus, it can be considered relevant to the
query. For example, the triplegroups tg 0 , tg 1 , and tg 2 in Figure 6.13b are well
formed in terms of the extended example query in Figure 6.13a.
• Ambiguous Triplegroup: It is a triplegroup whose properties span multi-
ple star patterns in a query, for example, tg 0 in Figure 6.13b is an ambigu-
ous triplegroup.

SELECT * WHERE{
?producer type
?producer label
?producer date
?producer hpage

Clone
( type , label,
date, hpage)

type o1
label o2
date o3
hpage o4

Producer .
?prcLabel .
?prcdate .
?hpage .

s1,

tg 1 =

SJ 1

Clone
(pub, type ,
label, date )

?product pub
?product type
?product label
?product date

?producer .
Product .
?prodLabel .
?prodDate

type o1
labelo2
date o3
hpageo4
pub o5

pub o5
type o1

SJ 2

s1,

tg 0 = tg 2 =

s1,

label o2

date o3

Clone

?offer type
?offer product

Offer .

SJ 3 ( type , product,

vendor)

?product .

?offer vendor ?vendor.

}

(a) (b)

FIGURE 6.13 (a) Extended query and (b) cloning in the context of ambiguous triplegroups.