Database Reference
In-Depth Information
as shown in Figure 6.6b. It is easy to observe that the information content in both
formats is equivalent. We refer to this kind of equivalence as
content equivalence
,
which we will denote as ≌. Consequently, computing query results in terms of triple-
groups is lossless in terms of information. Other triplegroup functions are defined as
shown in Figure 6.7b.
Given a query
Q
over triple relation
T
,
TG _ Load
loads the triples, and
TG _ GroupBy
groups them based on the subject column to produce a set of triple-
groups
TG
. The
structure-labeling function
λ assigns each triplegroup
tg
, with a label
that is constructed as some function of
tg
.props()
. Further, for two triplegroups
tg
1
,
tg
2
such that
tg
1
.props()
⊆
tg
2
.props()
, λ assigns labels such that
tg
1
.
λ
()
⊆
tg
2
.
λ
()
. The labeling function λ induces a partition on a set of triplegroups based
on the structure represented by the property types present in that triplegroup. Each
equivalence class in the partition consists of triplegroups that have the exact same
set of property types. Next, we discuss some of the triplegroup operators that are
formally defined in Figure 6.7c.
•
TG _ Proj
operator extracts from each triplegroup, the required triple
component from the triple matching the triple pattern. For triplegroup
tg
in
Figure 6.6a,
TG _ Proj
?
hpage
(
TG
) extracts the object component of the triple
with property
hpage
, that is,
www.vendors.org/V1
}.
•
TG _ Filter
operator enforces
value-based filtering,
, that is, checks if triple-
groups satisfy the filter condition. For our example data, TG_Filter
price
<500
(
TG
)
eliminates triplegroup
ntg
in Figure 6.6c since the triple (&
Offer
1,
price
,
1008) violates the filter condition.
•
TG _ GroupBy
groups the triples
t
i
based on the subject column to produce
a set of triplegroups
TG
.
•
TG _ GroupFilter
enforces the structural constraints in a star subpattern
such that triplegroups missing any of the edges in the structure are pruned
(
structure-based filtering).
). For example, triplegroup
tg
in Figure 6.6a is a
valid match for the set of bound properties {
label, country, homepage
} but
violates the structure in {
label, country, homepage, mbox
}.
•
TG _ Join
operator is semantically equivalent to the relational join
operator but is defined on triplegroups. The join expression
TG _ Join
?:
( )
computes the join between a triplegroup
tg
x
in
equivalence class
TG
x
with a triplegroup
tg
y
in equivalence class
TG
y
based on the given triple patterns. The triple patterns
tp
x
and
tp
y
share a
common variable ?
v
at
O
or
S
component. The result of an object-subject
(O-S) join is a nested triplegroup in which
tg
y
is nested at the
O
compo-
nent of the join triple in
tg
x
. For example, Figure 6.6c shows the nested
triplegroup resulting from the
TG _ Join
operation between equivalence
classes
TG
{
price,product,validFrom,vendor
}
and
TG
{
label,country,homepage
}
that join based
on triple patterns {?
o
vendor
?
v
} and {?
v country
?
vcountry
}, resp e ct ively.
For object-object (O-O) joins, the
TG _ Join
operator computes a triple-
group by union of triples in the individual triplegroups.
v Gv TG
tp
,?
:
x
tp
y
x
y
Search WWH ::
Custom Search