Database Reference
In-Depth Information
Algorithm 15.1 I
NL
S
CHEMA
(
D
)
Require:
D
is a nested relational DTD.
Ensure: S
D
and
Δ
D
are the inlining relational schema
inl
(
D
).
S
D
:= 0
Δ
D
:= 0
for all marked element types
of
D
do
add to S
D
a relation
R
, with attributes
⎧
⎨
id
A
D
(
)
id
μ(
)
attr
(
R
)=
|
if
=
r
.
⎩
(
)=
,
is not marked,
id
|
μ
A
D
(
)
(
)=
,
is not marked.
|
μ
end for
for all relations
R
in S
D
do
add to
Δ
D
the constraint stating that
id
is key of
R
if
=
r
then
add to
Δ
D
the foreign key
R
[
id
μ(
)
]
⊆
FK
R
μ(
)
[
id
μ(
)
]
.
end if
end for
add to
Δ
D
the dependency (stating the uniqueness of the root)
R
r
(
x
,
z
)
x
=
x
.
∀
y
∀
zR
r
(
x
,
y
)
∧
→
return (S
D
,
Δ
D
)
Proposition 15.2
For every nested relational DTD D, the output of
I
NL
S
CHEMA
(D) is
an acyclic relational schema.
Shredding of XML documents We now move to the shredding procedure. Given the
inlining I
NL
S
CHEMA
(
D
) =(S
D
,
Δ
D
) of a DTD
D
,andanXMLtree
T
conforming to
D
,
we use the algorithm I
NL
D
OC
to shred
T
into an instance of the relational schema S
D
that satisfies the constraints in
Δ
D
. The algorithm basically follows the intuition behind
the definition of the inlining schema: a tuple is created for each starred element, and its
unstarred children and descendants, as well as parent, are inlined with its id.
Example 15.3 Recall tree
T
from
Figure 15.2
.
Figure 15.3
shows relations
R
book
and
R
author
in the shredding of
T
.
(
n
) of a node
n
of
an XML document
T
that conforms to a DTD
D
, as follows. Mark each node
n
of
T
such
To present the algorithm, we define the
nearest appropriate ancestor
μ
