Databases Reference
In-Depth Information
3.2
Definition and Semantics
3.2.1
Schema Mappings and p-Mappings
We begin by reviewing nonprobabilistic schema mappings. The goal of a schema
mapping is to specify the semantic relationships between a
source schema
and a
target schema
. We refer to the source schema as
S, and a relation in
S as S
D
T , and a relation in
T as
h
s
1
;:::;s
m
i
. Similarly, we refer to the target schema as
T
Dh
t
1
;:::;t
n
i
.
We consider a limited form of schema mappings that are also referred to as
schema matching
in the literature. Specifically, a schema matching contains a set of
attribute correspondences
. An attribute correspondence is of the form c
ij
D
.s
i
;t
j
/,
where s
i
is a
source attribute
in the schema S and t
j
is a
target attribute
in the
schema T . Intuitively, c
ij
specifies that there is a relationship between s
i
and t
j
.
In practice, a correspondence also involves a function that transforms the value of
s
i
to the value of t
j
. For example, the correspondence
(c-degree, temperature)
can be specified as
temperature
1:8
C
32, describing a transforma-
tion from Celsius to Fahrenheit. These functions are irrelevant to our discussion,
and therefore, we omit them. This class of mappings are quite common in practice
and already expose many of the novel issues involved in probabilistic mappings. In
Sect.
3.5
, we will briefly discuss extensions to a broader class of mappings.
Formally, relation mappings and schema mappings are defined as follows.
D
c-degree
Definition 1
(Schema Mapping).
Let S and T be relational schemas. A
relation
mapping
M is a triple .S;T;m/,whereS is a relation in
S, T is a relation in
T ,and
m is a set of attribute correspondences between S and T .
When each source and target attribute occurs in at most one correspondence in
m, we call M a
one-to-one relation mapping
.
A
schema mapping
M is a set of one-to-one relation mappings between relations
S and in
T , where every relation in either
S or
T appears at most once.
in
t
A pair of instances D
S
and D
T
satisfies
a relation mapping m if for every source
tuple t
s
2
D
S
, there exists a target tuple t
t
2
D
t
, such that for every attribute
correspondence .s;t/
2
m, the value of attribute s in t
s
is the same as the value of
attribute t in t
t
.
Example 2.
Consider the mappings in Example
1
. The source database in Fig.
4.2
b
(repeated in Fig.
4.3
a) and the target database in Fig.
4.3
b satisfy m
1
.
t
Intuitively, a probabilistic schema mapping describes a probability distribution
of a set of
possible
schema mappings between a source schema and a target schema.
For completeness, we repeat its definition as follows (also see Definition 3 in
Chap. 3).
Definition 2
(Probabilistic Mapping).
Let S and T be relational schemas. A
prob-
abilistic mapping (p-mapping)
, pM, is a triple .S;T;
m
/,whereS
2
S, T
2
T ,and
m
is a set
f
.m
1
;
Pr
.m
1
//;:::;.m
l
;
Pr
.m
l
//
g
, such that
