Databases Reference
In-Depth Information
Theorem 5.
Let
pCM
be a complex schema p-mapping between schemas
S
and
T
.Let
D
S
be an instance of
S
.Let
Q
be an SPJ query over
T
. The
data c
om-
plexity and mapping complexity of computing
Q
table
.D
S
/
with respect
to
pC
M
are
PTIME. The data complexity of computing
Q
tuple
.D
S
/
with respect to
pCM
is #P-
complete. The mapping complexity of computing
Q
tuple
.D
S
/
with respect to
pCM
is in PTIME.
t
Union mapping: Union mappings
specify relationships such as both attribute
home-
address
and attribute
office-address
can be mapped to
address
. Formally, a
union mapping
is a triple .S;T; m/,where
m is a set of mappings between S and T .
Given a source relation D
S
and a target relation D
T
,wesayD
S
and D
T
are con-
sistent with respect to the union mapping if for each source tuple t and m
2
m there
exists a target tuple t
0
, such that t and t
0
satisfy m.A
union p-mapping
is of the form
pUM
Df
. m
i
;Pr.m
i
//
j
i
2
Œ1;n
g
,where
P
i
D
1
Pr
. m
i
/
D
1.
Both by-table and by-tuple semantics apply to probabilistic union mappings.
Theorem 6.
Let pUM be a union schema p-mapping between a source schema
S
and a target schema
T
.Let
D
S
be an instance of
S
.Let
Q
be a
conju
nctive query
over
T
. The problem of computing
Q
table
.D
S
/
with respect to pUM is in PTIME
in the size
of the
data and the mapping; the problem of computing
Q
t
u
ple
.D
S
/
with
respect to pUM is in PTIME in the size of the mapping and #P-complete in the size
of the data.
t
Conditional mappings:
In practice, our uncertainty is often conditioned. For exam-
ple, we may want to state that
daytime-phone
maps to
work-phone
with prob-
ability 60% if
age
65, and maps to
home-phone
with probability 90% if
age
>65.
We d e fi n e a
conditional p-mapping
as a set cpM
Df
.pM
1
;C
1
/;:::;.pM
n
;C
n
/
g
,
where pM
1
;:::;pM
n
are p-mappings, and C
1
;:::;C
n
are pairwise disjoint con-
ditions. Intuitively, for each i
2
Œ1;n, pM
i
describes the probability distribution
of possible mappings when condition C
i
holds. Conditional mappings make more
sense for by-tuple semantics. The following theorem shows that the complexity
results carry over to such mappings.
Theorem 7.
Let
cpM
be a conditional schema p-mapping between
S
and
T
.Let
D
S
be an instance of
S
.Let
Q
be
an SPJ query over
T
. The problem of computing
Q
t
u
ple
.D
S
/
with respect to
cpM
is in PTIME in the size of the mapping and #P-
complete in the size of the data.
t
3.6
Other Types of Approximate Schema Mappings
There have been various models proposed to capture uncertainty on mappings
between attributes.
Galetal.
(
2005b
) proposes keeping the top-K mappings
between two schemas, each with a probability (between 0 and 1) of being true.
