Databases Reference
In-Depth Information
as mailing address; thus, for different tuples, we may apply different mappings so
that the correct mapping depends on the particular tuple.
We define query answering under both interpretations. The first interpretation
is referred to as the
by-table
semantics, and the second one is referred to as the
by-tuple
semantics of probabilistic mappings. Note that one cannot argue for one
interpretation over the other; the needs of the application should dictate the appro-
priate semantics. Furthermore, the complexity results for query answering, which
will show advantages to by-table semantics, should not be taken as an argument in
the favor of by-table semantics.
We next define query answering with respect to p-mappings in detail, and the
definitions for schema p-mappings are the obvious extensions. Recall that given a
query and an ordinary mapping, we can compute
certain answers
to the query with
respect to the mapping. Query answering with respect to p-mappings is defined as a
natural extension of certain answers, which we next review.
A mapping defines a relationship between instances of S and instances of T that
are
consistent
with the mapping.
Definition 3
(Consistent Target Instance).
Let M
D
.S;T;m/ bearelation
mapping and D
S
be an instance of S.
An instance D
T
of T is said to be
consistent with
D
S
and
M, if for each tuple
t
s
2
D
S
there exists a tuple t
t
2
D
T
, such that for every attribute correspondence
.a
s
;a
t
/
2
m the value of a
s
t
in t
s
is the same as the value of a
t
in t
t
.
For a relation mapping M and a source instance D
S
, there can be an infinite num-
ber of target instances that are consistent with D
S
and M. We denote by
Ta r
M
.D
S
/
the set of all such target instances. The set of answers to a query Q is the intersection
of the answers on all instances in
Ta r
M
.D
S
/.
Definition 4
(Certain Answer).
Let M
D
.S;T;m/be a relation mapping. Let Q
be a query over T and let D
S
be an instance of S.
A tuple t is said to be a
certain answer of
Q
with respect to
D
S
and
M,iffor
every instance D
T
2
Ta r
M
.D
S
/, t
2
Q.D
T
/.
t
By-table semantics:
We now generalize these notions to the probabilistic setting,
beginning with the by-table semantics. Intuitively, a p-mapping pM describes a set
of possible worlds, each with a possible mapping m
2
pM. In by-table semantics,
a source table can fall in one of the possible worlds, that is, the possible mapping
associated with that possible world applies to the whole source table. Following this
intuition, we define target instances that are
consistent with
the source instance.
Definition 5
(By-table
Consistent
Instance).
Let pM
D
.S;T;
m
/ be
a
p-mapping and D
S
be an instance of S.
An instance D
T
of T is said to be
by-table consistent with
D
S
and
pM,ifthere
exists a mapping m
2
and D
T
satisfy m.
t
m
such that D
S
