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 )
R r ( rID )
R author ( bookID )
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-
i , j
Search WWH ::

Custom Search