Database Reference

In-Depth Information

R
r
(
rID
)

R
book
(
bookID,@title,rID,subID,@sub
)

R
author
(
authID,bookID,nameID,afID,@nam,@aff
)
.

In this schema, keys are underlined. In addition we also have the following foreign keys:

R
book
(
rID
)

⊆
FK

R
r
(
rID
)

R
author
(
bookID
)

⊆
FK

R
book
(
bookID
)
.

The first relation contains just the root node. The second relation corresponds to the ele-

ment
book
which appears under the Kleene star in
D
. It contains book id, as well as its

attribute (title), and the id of the parent (root). In addition,
book
serves as the nearest ap-

propriate ancestor for
subject
, so this relation also inlines the id of the
subject
node

and its attribute @
sub
.

The next starred element type is
author
. The third relation corresponds to this element

and includes its id, as well as the id of its
book
parent. In addition,
name
and
aff
are inlined

into this relation, so ids of these elements, and their attributes, are included in
R
author
too.

We now proceed with a formal definition of the inlining shredding scheme. We first

define the
nearest appropriate ancestor
for the element types used in
D
. Given a nested-

relational DTD
D
=(
P
D
,
A
D
,
r
), we define the graph of
D
, denoted by
G
(
D
), as the graph

whose nodes are element types, and where there is an edge from
to
if
appears in

P
D
(
).Wethen“mark”in
G
(
D
) each element type that occurs under a Kleene star in
P
D
.

In addition, we mark the root element type in
G
(
D
). Then, for a given element type
,

we define the
nearest appropriate ancestor
of
, denoted by

(
), as the closest marked

element type
in the path from the root element to
in the graph
G
(
D
). For example,

μ

μ

(
subject
)=
book
.

The inlining schema generation is formally captured by means of the procedure

I
NL
S
CHEMA
(
Algorithm 15.1
) that receives a nested-relational
D
and creates the inlin-

ing relational schema
inl
(
D
).

Recall that to ensure good behavior of relational data exchange, we had to restrict

target constraints to egds and weakly acyclic sets of tgds. In our case, all tgds will be

inclusion constraints (i.e., each tgd is a part of a foreign key), and we can impose an

even stronger restriction of
acyclicity
.Aset
F
of foreign keys defines a graph
G
(
F
)

whose nodes are attributes, and edges are generated as follows: for each foreign key

R
[
A
1
,...,
A
n
]

(
name
)=
author
and

μ

⊆
FK
R
[
B
1
,...,
B
n
], we add all the edges (
A
i
,
B
j
),for1

n
.Then
F

is acyclic if the resulting graph
G
(
F
) is acyclic. If we view
F
as a set of tgds, then its

acyclicity implies weak acyclicity as previously defined.

We call a relational schema
acyclic
if its constraints involve a set of egds, and an acyclic

set of foreign keys.

The tree structure of nested-relational DTDs then implies that Requirement 1 is satis-

fied.

≤

i
,
j

≤