Database Reference
In-Depth Information
+
and
+
which are transi-
To define the semantics of patterns, we introduce relations
↓
→
+
is the descendant relation, and
+
is the following-
tive closures of
↓
and
→
.Thatis,
↓
→
+
s
s
, whenever
s
is a nonempty string, and
sibling relation. Formally, we have
s
↓
·
+
s
s
·
i
→
·
j
whenever
i
<
j
. With this, we are ready to introduce the semantics of pat-
terns.
Definition 11.2 (Pattern semantics) The semantics of patterns is formally defined by
means of the relation (
T
,
s
)
(
x
) is satisfied in a node
s
of a tree
T
when its variables
x
are interpreted as
a
. It is defined inductively as follows:
|
=
π
(
a
),sayingthat
π
(
T
,
s
)
|
=
(
a
)
iff
s
is labeled by
(or
= )and
a
is the tuple of at-
tributes of
s
(or is empty);
(
T
,
s
)
|
=
(
a
)[
λ
1
,
λ
2
]
iff
(
T
,
s
)
|
=
(
a
)[
λ
1
] and (
T
,
s
)
|
=
(
a
)[
λ
2
];
=
(
a
) and (
T
,
s
)
for some
s
with
s
s
;
(
T
,
s
)
|
=
(
a
)[
(
T
,
s
)
|
|
↓
μ
]
iff
=
μ
=
(
a
) and (
T
,
s
)
for some
s
with
s
+
s
;
(
T
,
s
)
|
=
(
a
)[
//
π
]
iff
(
T
,
s
)
|
|
=
π
↓
and (
T
,
s
)
for some
s
with
s
s
;
(
T
,
s
)
|
=
π
→
μ
iff
(
T
,
s
)
|
=
π
|
=
μ
→
+
and (
T
,
s
)
for some
s
with
s
+
s
.
(
T
,
s
)
|
=
π
→
μ
iff
(
T
,
s
)
|
=
π
|
=
μ
→
Patterns are witnessed at the root: for a tree
T
and a pattern
π
, we write
T
|
=
π
(
a
)
if (
T
,
ε
)
|
=
π
(
a
).Wealsodefine
π
(
T
)=
{
a
|
T
|
=
π
(
a
)
}
and write
T
|
=
π
if
π
(
T
) is not empty.
If
T
is the tree from
Figure 10.1
,then
π
1
(
T
)=
{
(
James V
,
Mary I
)
,
(
Mary I
,
James VI & I
)
,
(
James VI & I
,
Charles I
)
,
(
Elizabeth I
,
James VI & I
)
}
,
π
2
(
T
)=
{
James V
,
Mary I
,
James VI & I
,
Charles I
,
Elizabeth I
}
,
π
3
(
T
)=
{
James VI & I
,
Charles I
}
.
Note that witnessing patterns at the root is not a restriction since we have descendant
//
in the language, and can thus express satisfaction of a pattern in an arbitrary node of a
tree. Also note that “sets” in tree patterns are literally sets, i.e., the listed subpatterns do
not have to be witnessed by distinct nodes. That is, for a node satisfying
(
a
)[
λ
1
,
λ
2
],the
nodes witnessing
λ
2
. For instance,
the pattern
r
[
,
a
] is witnessed by a tree with an
r
-labeled root and a single
a
-labeled child,
as that child witnesses both and
a
.
Observe that the patterns can already express equalities between data values by simply
λ
1
are not necessarily distinct from the ones witnessing
