Database Reference
In-Depth Information
W
VD P
X
1
0.2
X
2
0.8
Y
1
0.3
Y
2
0.7
The probabilities of the four possible worlds in
Figure 2.3
are the following:
P(R
1
)
P(R
2
)
P(R
3
)
P(R
4
)
=
0
.
2
·
0
.
3
=
0
.
2
·
0
.
7
=
0
.
8
·
0
.
3
=
0
.
8
·
0
.
7
These four probabilities are 0
.
06, 0
.
14, 0
.
24, 0
.
56, and obviously they add up to 1.
On the other hand, the probabilities of the three possible worlds in
Figure 2.5
are:
P(R
2
)
=
P(R
3
)
=
P(R
4
)
=
0
.
2
·
0
.
3
+
0
.
2
·
0
.
7
=
0
.
2
0
.
8
·
0
.
3
=
0
.
24
0
.
8
·
0
.
7
=
0
.
56
.
In summary, pc-tables extend traditional relations in two ways: each tuple is annotated with
a propositional formula, and we are given a separate table representing the probability space. This
is a very general and very powerful representation mechanism: we will consider several restrictions
later in this chapter.
2.5
LINEAGE
Consider a c-database
D
and a query
Q
in the Relational Calculus. The
lineage
of a possible answer
t
to
Q
on
D
is a propositional formula representing the event
t
∈
Q(W )
, over the possible worlds
W
of
D
; we define the lineage formally in this section.
With some abuse, we will extend the definition of lineage to the case when
D
is a standard
relational database (not a c-database). In that case, we introduce a new, distinct Boolean variable
X
t
for each tuple
t
in the database, and define the tuple condition to be
t
=
X
t
, thus, transforming
the database into a c-database. Therefore, we will freely refer to the lineage of a query on either a
c-database or on a regular database.
Definition 2.8
Let
D
be a database (either a standard database, or c-database), and let
Q
be a
Boolean query in the Relational Calculus. The
lineage
of
Q
on
D
is the propositional formula
Q
,
or simply
Q
if
D
is understood from the context, defined inductively as follows. If
Q
is a ground
tuple
t
, then
t
is the propositional formula associated with
t
. Otherwise,
Q
is defined by the
following six cases:
a
=
a
=
true
a
=
b
=
false
Q
1
∧
Q
2
=
Q
1
∧
Q
2
Q
1
∨
Q
2
=
Q
1
∨
Q
2
∃
x.Q
=
¬
Q
=¬
(
Q
)
Q
[
a/x
]
(2.4)
a
∈
ADom(
D
)
