Database Reference
In-Depth Information
europe
ruler
(
x
)
country
ruler
(
x
)
ruler
(
y
)
europe
country
(
Scotland
)
country
(
England
)
ruler
(
James V
)
ruler
(
Mary I
)
ruler
(
James VI&I
)
ruler
(
Charles I
)
ruler
(
Elizabeth I
)
ruler
(
James VI&I
)
ruler
(
Charles I
)
Figure 11.2 A homomorphism from a pattern to an XML tree
•
(
π
1
,
π
2
)
∈→
iff
π
contains (syntactically)
π
1
→
π
2
;and
+
iff
+
•
(
π
1
,
π
2
)
∈→
π
contains
π
1
→
π
2
.
+
country
[
ruler
(
x
)]] shown in
Fig-
ure 11.1
,
S
π
has five nodes:
u
corresponding to the whole pattern,
v
1
,
v
2
corresponding
to the two occurrences of
country
[
ruler
(
x
)],and
w
1
,
w
2
corresponding to the two oc-
currences of
ruler
(
x
). The relations are given as follows:
For instance, for
π
=
europe
[
country
[
ruler
(
x
)]
→
=
(
u
,
v
i
)
,
(
v
i
,
w
i
)
i
= 1
,
2
,
↓
+
=
(
u
,
v
i
)
,
(
v
i
,
w
i
)
,
(
u
,
w
i
)
i
= 1
,
2
,and
+
=
↓
.
Under this interpretation, there exists a natural notion of homomorphism.
→
=
→
{
(
v
1
,
v
2
)
}
+
,
+
,
lab
,
Definition 11.4 Let
π
be a pure pattern with
S
π
=(
U
,
↓
,
↓
→
,
→
π
,
ρ
),andlet
T
,
lab
T
,
(
T
=(
U
T
,
T
,
a
)
a
∈
Att
).A
homomorphism h
:
S
π
→
↓
→
ρ
T
is a function that maps
U
into
U
T
and the variables of
π
into the domain of attribute values
V
such that for all
π
1
,
π
2
∈
U
•
the root of
π
is mapped to the root of
T
, i.e.,
h
(
π
)=
ε
;
π
1
)=
lab
T
(
h
(
•
the labeling is preserved, i.e., if
lab
(
π
1
)
= ,then
lab
(
π
1
));
+
,
+
•
for every
∈{↓
,
↓
→
,
→
}
,if
π
1
π
2
in
S
π
,then
h
(
π
1
)
h
(
π
2
) in
T
;
•
if
ρ
(
π
1
)=
x
then
h
(
π
1
) stores the tuple
h
(
x
), i.e.,
h
(
π
1
) is a node with attributes
a
i
(
h
(
a
1
,
a
2
,...,
a
k
and
h
(
x
i
)=
ρ
π
1
)) where
x
=(
x
1
,
x
2
,...,
x
k
).
+
and
+
are externally defined as transitive closures
Note that while in
T
the relations
↓
→
+
= /0and
of
↓
and
→
,in
S
π
they are built-in relations. In fact, in
S
π
it is true that
↓∩↓
+
= 0 but all four relations can be extended in such a way that the structure becomes
a proper tree. An example of a homomorphism is given in
Figure 11.2
.
For
h
:
S
π
→
→∩→
T
, we say that
h
is a
homomorphism from
π
to T
. For a generalized pattern
π
=
π
0
∧
α
, a homomorphism from
π
to
T
is a homomorphism
h
:
S
π
0
→
T
extended to all
variables used in
α
in such a way that
•
for every equality
x
=
y
in
α
,wehave
h
(
x
)=
h
(
y
);
