Databases Reference
In-Depth Information
Given a source instance D
S
and a possible mapping m
2
m
, there can be an
infinite number of target instances that are consistent with D
S
and m. We denote by
Ta r
m
.D
S
/ the set of all such instances.
In the probabilistic context, we assign a probability to every answer. Intuitively,
we consider the certain answers with respect to each possible mapping in isolation.
The probability of an answer t is the sum of the probabilities of the mappings for
which t is deemed to be a certain answer. We define by-table answers as follows:
Definition 6
(By-table Answer).
Let pM
D
.S;T;
m
/ be a p-mapping. Let Q be
a query over T and let D
S
be an instance of S.
Let t be a tuple. Let
m.t/ be the subset of
m
, such that for each m
2
m.t/ and
for each D
T
2
Ta r
m
.D
S
/, t
2
Q.D
T
/.
Let p
D
P
m
2
m.t /
Pr
.m/.Ifp>0,thenwesay.t;p/ is a
by-table answer of
Q
with respect to
D
S
and
pM.
t
By-tuple semantics:
If we follow the possible-world notions, in by-tuple semantics,
different tuples in a source table can fall in different possible worlds, that is, different
possible mappings associated with those possible worlds can apply to the different
source tuples.
Formally, the key difference in the definition of by-tuple semantics from that
of by-table semantics is that a consistent target instance is defined by a mapping
sequence
that assigns a (possibly different) mapping in
m
to each source tuple in
D
S
. (Without losing generality, to compare between such sequences, we assign
some order to the tuples in the instance.)
Definition 7
(By-tuple
Consistent
Instance).
Let pM
D
.S;T;
m
/ be
a
p-mapping and let D
S
be an instance of S with d tuples.
An instance D
T
of T is said to be
by-tuple consistent with
D
S
and
pM,ifthere
h
m
1
;:::;m
d
i
is a sequence
such that d is the number of tuples in D
S
and for every
1
i
d,
m
i
2
m
,and
For the ith tuple of D
S
, t
i
, there exists a target tuple t
i
2
D
T
such that for each
attribute correspondence .a
s
;a
t
/
2
m
i
,thevalueofa
s
in t
i
is the same as the
in t
i
value of a
t
.
t
Dh
m
1
;:::;m
d
i
, we denote by
Ta r
seq
.D
S
/ the
set of all target instances that are consistent with D
S
and
seq
. Note that if D
T
is
by-table consistent with D
S
and m,thenD
T
is also by-tuple consistent with D
S
and a mapping sequence in which each mapping is m.
We can think of every sequence of mappings
seq
Given a mapping sequence
seq
Dh
m
1
;:::;m
d
i
as a separate
event whose probability is
Pr
.
seq
/
D
˘
i
D
1
Pr
.m
i
/. (Section
3.5
relaxes this inde-
pendence assumption and introduces
conditional mappings
.) If there are l mappings
in pM, then there are l
d
sequences of length d, and their probabilities add up to
1. We denote by
seq
d
.pM/ the set of mapping sequences of length d generated
from pM.
