Database Reference
In-Depth Information
By
Path
(
TP
) we will denote the set of all paths defined by the tree pattern
TP
. This set is defined
recursively as follows:
•
Path
(/
E
) = {/
p
|
p
∧
Path
(
E
)},
•
Path
(
l
) = {
l
},
•
Path
(
E
/
E'
) = {
p/p'
|
p
∧
Path
(
E
),
p'
∧
Path
(
E'
)},
•
Path
(
l
[
E
1
, ...,
E
k
]) = {
l/p
i
|
p
i
∧
Path
(
E
i
),
i
∧
[1, ...,
k
] }.
Definition 3.
(
schema pattern
) A tree pattern
TP
over
D
= (
top
,
L
,
Ter
, σ) is called a
schema pattern
over
D
, if the following two conditions hold:
•
TP
is of the form /
top
[
E
],
•
each path in
Path
(
TP
) ends with a terminal label.
Tree pattern
TP
1
and
TP
a
from Example 2 are tree-pattern schemas over
D
1
and
D
a
, respectively.
Definition 4.
(
arity of tree patterns
) A tree pattern
TP
over
D
= (
top
,
L
,
Ter
, σ) is of
arity m
if there are
m
paths in
Path
(
TP
) ending with a terminal label from
Ter
. To indicate these terminal labels (possibly
with more that one occurrences) and their ordering we use the notation
TP
(
l
1
, ...,
l
m
) meaning that the
occurrence of the terminal label
l
1
proceeds the occurrence of
l
2
, and so on.
Note that a label can have many occurrences in a tree pattern (e.g. for
S
a
in Example 1, we have
S
a
(
pid, pid, pid
)) .
Definition 5.
(
tree-pattern formula, schema
) Let
TP
be a tree pattern of arity
m
over
D
= (
top
,
L
,
Ter
,
σ), and (
l
1
, ...,
l
m
) be a list of (not necessarily distinct) terminal labels occurring in
TP
and
x
= (
x
1
, ...,
x
m
)
be a tuple of distinct text-valued variables. Then the formula
TP
(
x
) created from
TP
by replacing the
if
i-th terminal label
l
i
with the equality
l
i
=
x
i
, is called a
tree-pattern formula
. If
TP
is a schema pattern,
then
TP
(
x
) will be referred to as a
schema
.
Schemas will be denoted by
S
(
x
), or by
S
if variable names are not important or clear from the con-
text. Note that a schema
S
(
x
) is an XPath expression (XPath, 2006}, where the first slash, /, denotes the
root of the corresponding XML document. Any variable
x
occurring in the schema has the
type
being
the sequence of labels (the path) leading from the root to the leaf the variable
x
is assigned to.
Definition 6.
(
variable types
) Let
S
be a schema over
x
and let an atom
l = x
occur in
S
. Then the path
p
starting with
top
and ending with
l
is called the
type
of the variable
x
, denoted type
S
(
x
) =
p
.
A tree pattern has the type being the type of the elements returned by its evaluation according to the
XPath semantics. This type is a path determined as follows:
•
type
(/
E
) = /
type
(
E
),
•
type
(
l
) =
l,
•
type
(
E
/
E'
) =
type
(
E
)/
type
(
E'
),
