Database Reference
In-Depth Information
a constraint is satisfied in an instance-database
A
if for each tuple
t
1
∈
r
1
A
there exists a tuple
t
2
∈
r
2
A
such that
π
K
(
{
t
1
}
)
=
π
K
(
{
t
2
}
)
.
z
r
2
(
x
,
z
))
∈
Σ
tgd
It can be provided by a tgd
∀
x
(
∃
y
r
1
(
x
,
y
)
⇒∃
.
G
be the set of attribute indexes
of
r
2
that are not key-attributes and let us define the set of terms
S
={
t
j
k
|
t
j
k
=
f
r
2
,j
k
(x
i
1
,...,x
i
h
)
for 1
Let
{
j
1
,...,j
m
−
h
}={
1
,...,m
}\{
i
1
,...,i
h
}
≤
k
≤
m
−
h
}
and the tuple
t
1
of terms (the variables
are terms as well) in
{
x
i
1
,...,x
i
h
}∪
S
ordered by their indexes from 1 to
m
.
Hence, this foreign key constraint can be given by the SOtgd
f
r
2
,j
1
,...,f
r
2
,j
m
−
h
∀
x
1
,...,x
n
r
1
(x
1
,...,x
n
)
r
2
(
t
1
)
,
∃
⇒
i.e., by
r
2
(
t
1
)
,
where
f
1
is the tuple of Skolem function symbols that appear in the tuple of
terms
t
1
and
x
1
is the tuple of variables (i.e., of attributes) of
r
1
.
f
1
∀
x
1
r
1
(
x
1
)
∃
⇒
(FK)
•
The
mapping
is defined following the GAV approach: to each relation
r
of
the global schema
M
G
we associate a query
ρ(r)
over the source schema
S
.We
assume that this query preserves the key constraint of
r
.
Thus, a map
ρ(r)
r
is a tgd
∀
x
(ρ(r)(
x
)
⇒
r(
x
))
, i.e.,
M
is a set of tgds.
•
For each relational symbol
r
of the global schema
G
, we may compute the rela-
tion
G
by evaluating the query
ρ(r)
over the source database
D
. The various
relations so obtained define what we call the
retrieved global database ret(
r
,D)
.
Notice that, since we assume that
ρ(r)
has been designed so as to resolve all key
conflicts regarding
r
, the retrieved global database satisfies all the key constraints
in
I
.
In our case, with the
integrity constraints
and with
sound mapping
, the semantics
of a data integration system
G
is specified in terms of a set of
legal
global instance-
databases, namely, those databases (they exits iff
I
I
is consistent
w.r.t.
D
, i.e., iff
ret(
I
,D)
does not violate any key constraint in
G
) that are supersets of the
retrieved
global database
ret(
,D)
.
For a given retrieved global database
ret(
I
I
,D)
, we may inductively construct the
canonical database
can(
I
,D)
by starting from
ret(
I
,D)
and repeatedly applying
the following rule (FR) [
2
]:
if
d
i
1
,...,d
i
h
∈
π
K
(
r
1
can(
I
,D)
)
and
d
i
1
,...,d
i
h
∈
π
K
(
r
2
can(
I
,D)
)
,where
K
=
i
1
,...,i
h
is an ordered sequence of indexes in
key(r
2
)
,
K
is the correspondent sequence
of the same attributes in
r
1
, and the foreign key constraint
π
K
(r
1
)
⊆
π
K
(r
2
)
is in
Σ
T
⊆
G
,
then insert in
r
2
can(
I
,D)
the tuple
t
=
d
1
,...,d
ar(r
2
)
such that
•
π
K
(
{
t
}
)
=
d
i
1
,...,d
i
h
,and
•
for each
i
such that 1
≤
i
≤
ar(r
2
)
and
i
not in
K
,
π
i
(
{
t
}
)
=
f
r
2
,i
(d
i
1
,...,d
i
h
)
,where
π
i
is the
i
th projection.
Notice that the this rule (FR) does enforce the satisfaction of the foreign key con-
straint
π
K
(r
1
)
π
K
(r
2
)
by adding a suitable tuple in
r
2
: the key of the new tuple
is determined by the values in
π
K
(r
1
)
, and the values of the non-key attributes are
provided by means of the Skolem function symbols
f
r
2
,i
.
⊆