Database Reference
In-Depth Information
The idea of triplegroup “matching” a star subpattern in a query has to ensure that
the underlying structure is represented in a triplegroup. For example, triplegroup
tg
3
in Figure 6.5 does not match either of the required star subpatterns since it does
not contain triples with some of the properties required by those subpatterns, for
example,
label
,
product
.
In addition, to complete the process, these triplegroups may need to be “joined”
together, for example, using subject-object joins to create the desired subgraph. All
of this essentially implies a data model and algebra for capturing and manipulating
“triplegroups” as first-class citizens. The following section presents this data model
and algebra and its implementation in more detail.
6.5.2
t
he
n
esteD
t
riPle
g
rouP
D
ata
m
oDel
anD
a
lgebra
(ntga)
Definition 6.1
(TripleGroup) A triplegroup tg is a relation of triples
t
1
,
t
2
,…
t
k
,
whose schema is
defined as (S, P, O)
.
Further,
any two triples ti,
i
, t
j
∈
tg have overlapping components,
that is, ti
i
[coli]
i
] = t
j
[coli]
j
], where coli,
i
, coli,
j
refer to subject or
object component. When
all triples agree on their subject (object) values, we call them subject (object)
triple-
groups, respectively.
Figure 6.6a is an example of a
subject triplegroup
that corresponds to a
star subgraph. Our data model allows triplegroups to be nested at the object
component.
Definition 6.2
(Nested TripleGroup) A nested triplegroup ntg consists of a root triplegroup ntg.
root
and one or more child triplegroups returned by the function ntg
.child()
such that: For each child triplegroup ctg
∈
ntg
.child()
,
• ∃
t
1
∈
ntg
.root
, t
2
∈
ctg such that
t
1
.Object
=
t
2
.
Triplegroup
ntg
in Figure 6.6c is an example of a nested triplegroup. A nested
triplegroup can be “unnested” into a triplegroup using the
unnest
operator. Figure
6.6d shows the triplegroup
untg
resulting from an
unnest
operation on the nested
triplegroup
ntg
. In addition, we define the
flatten
operation to generate an “equiv-
alent” n-tuple for a given triplegroup. For example, if
tg
=
t
1
,
t
2
,…, then the n-tuple
tu
has triple
t
1
= (
s
1,
p
1,
o
1) stored in the first three columns of
tu
, triple
t
2
= (
s
2,
p
2,
o
2) is stored in the fourth through sixth column, and so on. For convenience, we
define the function
triples()
to extract the triples in a triplegroup. For triple-
group
tg
in Figure 6.6a, the
flatten
is computed as
tg
.triples(
label
)
⋈
tg
.triples(
country
)
⋈
tg
.triples(
homepage
)
, resulting in an n-tuple
nt
Search WWH ::
Custom Search