Database Reference
In-Depth Information
•
type
(
E
[
E'
]) =
type
(
E
).
Example 3.
Schemas
S
1
and
S
a
from Figure 1 can be specified as follows:
S
1
(
x
1
,
x
2
,
x
3
,
x
4
) := /
pubs
[
pub
[
title
=
x
1
,
year
=
x
2
,
author
[
name
=
x
3
,
univer-
sity
=
x
4
]]]
S
a
(
x
1
,
x
2
,
x
3
) := /
part
[
pId
=
x
1
,
part
[
pId
=
x
2
,
part
[
pId
=
x
3
]]]
type
S
1
(
x
1
) = /
pubs
/
pub
/
title
,
type
(
S
1
) = /
pubstype
(
TP
2
) = /
pubs/pub
/
year
(see Example 2).
Instances of XML Schemas
An XML database consists of a set of XML data. We define XML data as an unranked rooted node-
labeled tree (
XML tree
) over a set
L
of labels, and a set
Str
∧
{
∧
} of strings (
Str
) and the distinguished
null value
∧
- both strings and the null value are used as values of text (i.e. terminal) nodes. The value
∧
denotes that the path with this value is in fact missing in the XML tree under consideration.
Definition 7.
(
XML tree
) An
XML tree I
is a tuple (
r
,
N
e
,
N
t
,
child
, λ, ν), where:
•
r
is a distinguished
top node
,
N
e
is a finite set of
element nodes
, and
N
t
is a finite set of
text nodes
;
•
child
∧
({
r
}
∧
N
e
) × (
N
e
∧
N
t
) - a relation introducing tree structure into the set {
r
}
∧
N
e
∧
N
t
,
where
r
is the root, each element node has at least one child (being an element or text node), text
nodes are leaves;
•
λ:
N
e
→
L
- a function labeling element nodes with
names
(labels);
•
ν:
N
t
→
Str
∧
{
∧
} - a function labeling text nodes with
text values
from
Str
or with the null value
∧
.
It will be useful to perceive an XML tree
I
with a schema
S
(
x
), as a pair (
S
(
x
), Ω) (called the
instance
description
), where Ω is a set of
valuations
of variables in
x
.
Definition 8.
(
variable valuation
) Let
Str
∧
{
∧
} be a set of values of text nodes. Let
x
be a set of vari-
able names. A
valuation
ω for variables in
x
is a function
ω:
x
→
Str
∧
{
∧
}
assigning values in
Str
∧
{
∧
} to variables in
x
.
An XML tree
I
satisfies a description (
S
, Ω), denoted
I
≤ (
S
, Ω), if
I
satisfies (
S
, ω) for every ω
∧
Ω,
where this satisfaction is defined as follows.
Definition 9.
(
schema satisfaction
) Let
S
be a schema,
x
be a set of variables in
S
, and ω be a valuation
of variables in
x
. An XML tree
I
= (
r
,
N
e
,
N
t
,
child
, λ, ν) satisfies
S
by ω, denoted
I
≤ (
S
, ω), if the root
r
of
I
satisfies
S
by ω, denoted (
I
,
r
) ≤ (
S
, ω), where:
