Database Reference
In-Depth Information
Figure 1. Graphical representation of DTDs (D
1
and D
a
) and tree-pattern formulas (schemas) S
1
and S
a
for documents conforming to those DTDs, S
a
is restricted to depth of 3
are represented in a form of trees, whose leaves are labeled with text-valued variables. We will consider
two classes of tree-pattern formulas:
schemas
and
functional dependencies
.
Definition 2.
(
tree pattern
) A
tree pattern
over
D
= (
top
,
L
,
Ter
, σ) is an expression that can be defined
recursively by the following grammar:
TP
::= /
E
|
EE
::=
l
|
l
[
E
1
, ...,
E
k
] |
E
/
E'
, and
first
(
E
i
)
∧
σ(
l
), for
i
= 1,
...,
k
; and
first
(
E'
)
∧
σ(
last
(
E
)),
•
irst
(
l
) =
last
(
l
) =
l
,
•
irst
(
l
[
E
1
, ...,
E
k
]) =
last
(
l
[
E
1
, ...,
E
k
]) =
l
,
•
irst
(
E
/
E'
) =
irst
(
E
),
•
last
(
E
/
E'
) =
last
(
E'
).
Example 2
. For
L
= {
pubs, pub, title, year, author, name, university
}, the following expressions are tree
patterns over
L
:
TP
1
= /
pubs
[
pub
[
title
,
year
[
author
[
name
,
university
]]]],
TP
2
=
pubs/pub
[
title, author
]/
year
,
TP
3
=
pub
/
author
.
TP
a
= /
parts
[
part
[
pid
,
part
[
pid part
[
pid
]]]].
