Database Reference
In-Depth Information
2. DATA AND QUERY MODEL
for our topic; more expressive query languages have been considered in the literature, and we will
give some bibliographic references in
Section 2.8
.
2.3.1 VIEWS: POSSIBLE ANSWER SETS SEMANTICS
The possible answer sets semantics returns all possible sets of answers to a query. This semantics is
compositional, and especially useful for defining views over incomplete or probabilistic databases:
thus, here we will denote a query by
V
, and call it a
view
instead of a query, emphasizing that we
consider it as a transformation mapping a world
W
to another world
V(W)
.
W
1
,...,W
n
Let
V
be a view and
W
={
}
be an incomplete database. The
possible
Definition 2.3
answer set
is the incomplete database
V(
W
)
={
V(W)
|
W
∈
W
}
.
(
W
,P)
be a probabilistic database.The
possible answer set
is the prob-
ability space
(
W
,P
)
, where
W
=
V(
W
)
, and
P
is defined by
P
(W
)
=
W
∈
W
:
V(W)
=
W
P(W)
,
for all
W
∈
Let
V
be a view and
D
=
W
.
We denote by
V(
W
)
(or
V(
D
)
) the possible answer sets of
V
on the incomplete database
W
(or on the probabilistic database
D
).
This semantics is, conceptually, very simple. For an incomplete database, we simply apply
V
to every possible state of the database, then eliminate duplicates from the answers. It is important
to note that if the input
W
has
n
possible worlds, then the output has
m
=|
V(
W
)
|≤
n
possible
worlds. Thus, the number of possible worlds can only decrease, never increase. For a probabilistic
database, the probability of an answer
W
is the sum of all probabilities of those inputs
W
that are
mapped into
W
.
The possible answer sets semantics is
compositional
: once we computed
D
=
V(
D
)
,wecan
apply a new view
V
, and obtain
V
(
D
)
=
V
(V (
D
))
=
(V
◦
V)(
D
)
.
2.3.2 QUERIES: POSSIBLE ANSWERS SEMANTICS
For a query, it is impractical to represent all possible answer sets to a query. Instead, it is more
convenient to consider one answer at a time, which we call the
possible answers
semantics, or, also,
the
possible tuples
semantics.
Definition 2.4
Let
Q
be a query and
W
be an incomplete database. A tuple
t
is called a
possible
answer
to
Q
if there exists a world
W
∈
W
such that
t
∈
Q(W )
. The
possible answers semantics
of
the query is
Q
poss
(
W
)
={
t
1
,t
2
,...
}
, where
t
1
,t
2
,...
are all possible answers.
A tuple is called a
certain answer
if for every world
W
∈
W
,
t
∈
Q(W )
. The
certain answers
semantics
of the query is
Q
cert
(
W
)
={
t
1
,t
2
,...
}
, where
t
1
,t
2
,...
are all certain answers.
=
(
W
,P)
be a probabilistic database. The
marginal
probability
or
output probability
of a tuple
t
is
P(t
∈
Q)
=
W
∈
W
:
t
∈
Q(W )
P(W)
.The
possible answers
Let
Q
be a query and
D
Definition 2.5
