Databases Reference
In-Depth Information
(G)
Person2
Person1
Person1
Person2
hasSupervisor
Person3
hasSupervisor
hasSupervisor
hasAuthor
hasAuthor
hasAuthor
Person4
hasAuthor
Person3
hasSupervisor
hasAuthor
hasAuthor
hasAuthor
hasAuthor
Article2
hasAuthor
Article3
Article1
hasAuthor
year
publishedIn
publishedIn
hasTitle
“2008”
publishedIn
hasTitle
hasTitle
year
year
Person4
Journal1
Article2
“Title1”
“Title3”
“Title2”
“2005”
Article1
(G
2
)
“2008”
Journal2
Article1
Person4
Article2
hasAuthor
hasAuthor
publishedIn
publishedIn
(G
3
)
Article3
hasTitle
year
(G
1
)
Article1
year
hasTitle
publishedIn
“2008”
year
hasTitle
“Title2”
Journal1
“Title3”
“2008”
“2005”
Journal2
“Title1”
Fig. 3.
3-triple partition of the data graph
G
of Fig. 1
4 Query Decomposition
In this section we show that in order to find the answers to a query
Q
,itsuf-
fices to decompose
Q
into a set of subqueries
{
Q
1
,...,Q
m
}
, find the answers of
{
Q
1
,...,Q
m
}
and then to join them to find the answer to
Q
.
Definition 6.
A
decomposition
of a query
Q
is a n-tuple
F
=(
Q
1
,...,Q
n
)
such
Q
and
i
Q
i
=
Q
.
that
Q
1
,...,Q
n
⊆
F
is
non-redundant
if
Q
i
∩
Q
j
=
∅
for all
i
,
j
with
1
≤
i<j
≤
n
.A
branching node
in
Q
is a node in
nd
(
Q
i
)
∩
nd
(
Q
j
)
for a pair
i
,
j
,where
i
=
j
.
B
(
Q
)
denotes all branching nodes of
Q
.
Theorem 1.
Let
F
=(
Q
1
,...,Q
n
)
be a query decomposition of a query graph
Q
and
=(
G
1
,...,G
m
)
be a m-triple partition of a data graph
G
. Then the
following statements are equivalent:
1.
e
is a total embedding of
Q
in
G
.
2. for every
j
,with
1
P
n
, there exist useful partial embeddings
e
j,
1
,...,e
j,k
j
of
Q
j
in
G
i
j,
1
,...,G
i
j,k
j
for some
i
j,
1
,...,i
j,k
j
with
1
≤
j
≤
≤
i
j,
1
<...<i
j,k
j
≤
m
that satisfy the following properties:
(a) for every
j
,with
1
Q
j
there exists
some
such that
e
j,
(
v
)
,
e
j,
(
u
)
are defined and
(
e
j,
(
v
)
,p,e
j,
(
u
))
≤
j
≤
n
, and every triple
(
v,p,u
)
∈
G
i
j,
.
(b) for every
j
1
,j
2
,
1
,
2
,with
1
≤ j
1
≤ j
2
≤ n
,
1
≤
1
≤ k
j
1
,
1
≤
2
≤ k
j
2
,
the partial embeddings
e
j
1
,
1
and
e
j
2
,
2
are compatible.
(c) the join of
e
j,
j
for all
j
∈
∈{
1
,...,n
}
and all
j
∈{
1
,...,k
j
}
is
e
.
Search WWH ::
Custom Search