Database Reference
In-Depth Information
bookID
@title
rID
subID
@sub
id
1
'Algorithm Design'
id
ε
id
13
CS
id
2
'Algebra'
id
ε
id
22
Math
(a) Relation
R
book
in I
NL
D
OC
(
T
,
D
)
authID
bookID
nameID
afID
@nam
@af
id
11
id
1
id
111
id
112
Kleinberg
CU
id
12
id
1
id
121
id
122
Tardos
CU
id
21
id
2
id
211
id
212
Hungerford
SLU
(b) Relation
R
author
in I
NL
D
OC
(
T
,
D
)
Figure 15.3 Shredding of
T
into I
NL
S
CHEMA
(
D
)
that
lab
(
n
) is starred in
D
, as well as the root of
T
.Then
μ
(
n
) is the closest marked node
n
that belongs to the path from the root to
n
.
In algorithm I
NL
D
OC
, and for the remainder of the chapter, we denote by
id
n
the rela-
tional element representing the node
n
of a tree
T
.
Algorithm 15.2 I
NL
D
OC
(
T
,
D
)
Require:
D
is a nested relational DTD,
T
conforms to
D
.
Ensure:
I
is a relational instance of the schema I
NL
S
CHEMA
(
D
).
for all marked nodes
n
of
T
do
let
be the label of
n
;
add to the relation
R
of
I
a tuple that contains elements
⎧
⎨
id
n
ρ
@
a
(
n
)
|
@
a
∈
A
D
(
)
id
μ(
n
)
|
if
=
r
(
n
)=
n
,
n
is not marked.
⎩
id
n
|
μ
ρ
@
a
(
n
)
(
n
)=
n
,@
a
(
n
)) and
|
μ
∈
A
D
(
λ
n
is not marked
where the identifiers and attributes values for each of the elements
id
n
,
id
μ(
n
)
and
ρ
@
a
(
n
) coincide with the position of the attributes for
id
λ (
n
)
,
id
μ(
)
and
A
D
(
(
n
))
λ
of
R
.
end for
return
I
It is then easy to verify that our Requirement 2 is satisfied: that is, given a DTD
D
and
