Database Reference
In-Depth Information
6.5.2.1 Content Equivalence
Triplegroups produced by the grouping-based star-join computation are considered
to be “content-equivalent” (represented as ≅) to the set of n-tuples computed using a
set of relational star joins. Let
Stp
be a star subpattern comprising of the set of bound
properties {
P
1
,
P
2
, …,
P
k
} and
Tup
Stp
be the join result of vertically partitioned subset
relations
TT
,
,
,
. Let
Tup
Stp
s
represent the subset of
Tup
Stp
with subject Sub = s.
T
PP
P
k
1
2
⋈
T
P
2
⋈…⋈
T
P
k
)
Tup
=
σ
(
T
Stp
Sub
=
sP
s
1
Each tuple in
Tup
Stp
s
is of 3k arity (each property in
Stp
is associated with three
columns). Let
π
P
i
denote the projection of the (Sub, Prop, Obj) columns correspond-
ing to the parent relation
T
P
i
with bound property
P
i
. Let
tg
s
represent the set union of
triples formed by the three columns, that is,
(
)
∪
(
)
∪∪
(
)
tg
=
π
Tup
π
Tup
π
Tup
s
P
Stp
P
Stp
P
Stp
1
s
2
s
k
s
Remark 6.3
In summary, the tuples in
Tup
Stp
s
can be vertically partitioned into “triples” whose
union is equivalent to a subject triplegroup
tg
s
in the NTGA data model. For our
example data in Figure 6.5, we have
tg
1
≅ σ
Sub
=
&V
1
(
T
homepage
⋈
T
Tlabel)
⋈
T
country
)
tg
2
≅ σ
Sub
=
&Off
1
(
T
vendor
⋈
T
Tprice
⋈
T
product
⋈
T
Tlabel)
)
Note that the two n-tuples corresponding to
SJ
1 containing a multivalued prop-
erty
home-page
are implicitly represented using a single triplegroup
tg
1
as shown in
Figure 6.5.
6.6
RAPID+—AN IMPLEMENTATION OF NTGA
6.6.1 s
ystem
a
rChiteCture
In this section, we discuss our implementation strategy for NTGA in a system called
RAPID+ [23], which is an extension of Apache Pig. Figure 6.8 shows the overall sys-
tem architecture of RAPID+. (The gray boxes denote new or extended components.)
The user interface layer introduces support for expression of graph pattern matching
queries via either an integrated SPARQL query interface that integrates Jena's ARQ
[29] or NTGA-related high level commands that have been added to the Pig Latin lan-
guage. A SPARQL query is parsed and compiled into an ARQ-compliant SPARQL
S-expression tree [4]. The
query analyzer
and the
Pig Latin/NTGA plan generator
are
added as new components in the logical plan layer. Based on the given query execution
Search WWH ::
Custom Search