Database Reference
In-Depth Information
V AR . Source instances are usually denoted
S , S 1 , S 2 ,... , while target instances are denoted T , T 1 , T 2 ,... .
Instances like
V AR . That is, they are instances over C ONST
{ ROUTES (
1 , Paris , Santiago ) , INFO FLIGHT (
1 , 2320 ,
2 , AirFrance )
}
,
in the above example are solutions : they satisfy all the dependencies in the mapping for a
given source instance. That is, given a source instance S over C ONST , a target instance T
over C ONST
M
,if( S , T ) satisfies every sentence in
V AR is a solution for S under
Σ
st and
T satisfies every sentence in
is clear
from the context, we call simply call T a solution for S . As before, the set of solutions for
instance S will be denoted by S OL M ( S ).
The notion ( S , T )
Σ
t . In symbols, ( S , T )
|
=
Σ
st and T
|
=
Σ
t .When
M
Σ st from the above definition is formally stated as follows. If the
source schema R s contains relation symbols U 1 ,..., U m and the target schema R t contains
relation symbols W 1 ,..., W n (with no relation symbols in common), then
|
=
refers
to the schema with relation symbols U 1 ,..., U m , W 1 ,..., W n .If S is an instance of R s and
T is an instance of R t ,then( S , T ) denotes an instance of
R s , R t
R s , R t
in which every relation
symbol U i is interpreted as U i
and every relation symbol W j is interpreted as W j , for each
1
i
m and 1
j
n .
The general definition of relational schema mappings does not put restrictions on the
type of source-to-target dependencies one can use. Admitting arbitrary dependencies how-
ever easily leads to undecidability of some fundamental problems, such as checking for the
existence of solutions. Thus, it is customary to impose restrictions on classes of mappings
M
that guarantee efficient algorithms for the key computational tasks associated with data
exchange.
The standard restrictions used in data exchange are as follows: constraints used in
Σ st are
tuple-generating dependencies (which generalize inclusion dependencies), and constraints
in
Σ t are either tuple-generating dependencies or equality-generating dependencies (which
generalize functional dependencies). More precisely:
Σ st consists of a set of source-to-target tuple-generating dependencies (st-tgds) of the
form
x
y (
ϕ s ( x , y )
→∃
z ψ t ( x , z )) ,
where
ϕ s ( x , y ) and
ψ t ( x , z ) are conjunctions of atomic formulae in R s and R t , respec-
tively; and
Σ t is the union of a set of tuple-generating dependencies (tgds) , i.e., dependencies of the
form
x
y (
ϕ
( x , y )
→∃
z
ψ
( x , z )) ,
where ϕ( x , y ) and ψ( x , z ) are conjunctions of atomic formulae in R t , and a set of
equality-generating dependencies (egds) , i.e., dependencies of the form
x (
ϕ
( x )
x i = x j ) , Search WWH ::

Custom Search