Databases Reference
In-Depth Information
The
nodes
nd
(
G
)(resp.
nd
(
Q
)) of a data graph
G
(resp. a query graph
Q
)is
the set of elements of
U
so
∪
V
) that occur in the triples of
G
(resp.
Q
). The
arc labels
al
(
G
)(resp.
al
(
Q
)) of a data graph
G
(resp. a query
graph
Q
)isthesetofelementsof
U
p
that occur in the triples of
G
(resp.
Q
).
L
(resp.
U
so
∪
L
∪
Definition 1.
An (total)
embedding
of a query graph
Q
in a data graph
G
is a
total mapping
e
:
nd
(
Q
)
→
nd
(
G
)
with the following properties:
1) For each node
v
nd
(
Q
)
either
v
is a variable or
v
=
e
(
v
)
.
2) For each triple
(
v
1
,p,v
2
)
∈
Q
,thetriple
(
e
(
v
1
)
,p,e
(
v
2
))
is in
G
.
The tuple
(
e
(
X
1
)
,...,e
(
X
n
))
,where
(
X
1
,...,X
n
)
is the output pattern of
Q
,
is said to be an
answer
to the query
Q
.
∈
Example 2.
Fig. 2 shows an embedding of the query
Q
in data graph
G
.The
answer obtained is (?
A,
?
W,
?
T
)=(
Article
2
,Person
3
,
“
Title
2”). Note that a
second embedding exists giving (?
A,
?
W,
?
T
)=(
Article
2
,Person
2
,
“
Title
2”).
Person1
Person2
hasSupervisor
Person3
?W
hasSupervisor
hasAuthor
hasAuthor
Person4
hasAuthor
hasAuthor
hasAuthor
?A
hasAuthor
hasAuthor
Article2
hasTitle
Article3
Article1
?T
year
year
publishedIn
publishedIn
publishedIn
“2008”
hasTitle
hasTitle
hasTitle
year
year
publishedIn
Journal1
“2008”
“Title1”
“Title3”
“Title2”
Journal1
“2005”
“2008”
Journal2
(G)
(Q)
Fig. 2.
An embedding of the query graph
Q
in the data graph
G
Definition 2.
A
partial embedding
of a query graph
Q
in a data graph
G
is
a partial mapping
e
:
nd
(
Q
)
→
nd
(
G
)
such that for every node
v
∈
nd
(
Q
)
for
which
e
(
v
)
is defined the following properties hold:
1) if
v
is not a variable, then
e
(
v
)=
v
.
2) if
v
is a variable, then there exists a node
u
∈
nd
(
Q
)
for which
e
(
u
)
is
defined and an arc label
p
∈
al
(
Q
)
, such that
(
v,p,u
)
∈
Q
and
(
e
(
v
)
,p,e
(
u
))
∈
G
or
(
u,p,v
)
G
.
A partial embedding is
non-trivial
if there is a triple
(
v
1
,p,v
2
)
∈
Q
and
(
e
(
u
)
,p,e
(
v
))
∈
Q
such that
both
e
(
v
1
)
and
e
(
v
2
)
are defined and the triple
(
e
(
v
1
)
,p,e
(
v
2
))
belongs to
G
.
∈
Definition 3.
Two partial mappings
e
1
:
D
1
→
R
1
and
e
2
:
D
2
→
R
2
are said
to be
compatible
if for every
v
∈
D
1
∩
D
2
such that
e
1
(
v
)
and
e
2
(
v
)
are defined,
Search WWH ::
Custom Search