Database Reference
In-Depth Information
R
FID
SSN
N
R
FID
SSN
N
351
185
Smith
X
=
1
∧
Z
=
1
351
185
Smith
X
=
1
351
785
Smith
X
=
1
351
785
Smith
X
=
1
=
1
∧
Z
=
1
=
1
∧
X
=
1
352
185
Brown
Y
352
185
Brown
Y
352
186
Brown
Y
=
1
352
186
Brown
Y
=
1
∨
X
=
1
(a)
(b)
Figure 2.4:
Two ways to enforce unique SSN in
Figure 2.2
.
R
2
R
3
R
4
FID SSN N
351 185 Smith
352 186 Brown
{
X
→
1
,Y
→
1
}
{
FID SSN N
351 785 Smith
352 185 Brown
{
X
→
2
,Y
→
1
}
FID SSN N
351 785 Smith
352 186 Brown
{
X
→
2
,Y
→
2
}
X
→
1
,Y
→
2
}
Figure 2.5:
The three possible worlds for C-table in
Figure 2.4
(b).
because both Smith and Brown have the same SSN. There are two options: we could repair
R
1
,by
removing one of the two tuples, or we could remove the world
R
1
altogether.
The first option is given by the c-table
R
shown in
Figure 2.4
(a). Here a new variable
Z
ensures that the first and third tuple cannot occur in the same world, by making their conditions
mutually exclusive. This c-table has five possible worlds, which are derived from those in
Figure 2.3
as follows:
R
1
is replaced with two worlds,
, while
R
2
,R
3
,R
4
remain unchanged. Thus, in this c-table, we enforced the constraint by repairing world
R
1
, and this can be done in two possible ways, by removing one of its tuples.
The second option is given by the c-table
R
in
Figure 2.4
(b). In this c-table, the world
R
1
does not exists at all; instead, both assignments
X
→
1
,Y
→
1 and
X
→
1
,Y
→
2 result in the
same possible world
R
2
. This c-table has only three possible worlds, namely
R
2
,R
3
,R
4
, which are
shown again in
Figure 2.5
, together with the assignment that generated them.
With this example in mind, we give now the definition of c-tables and pc-tables.
{
(351, 185, Smith)
}
,
{
(352, 185, Brown)
}
A
conditional database
,or
c-table
for short, is a tuple
CD
=
R
1
,...,R
k
,
Definition 2.6
, where
is a relational database instance, and
assigns a propositional formula
t
to each
tuple
t
in each relation
R
1
,...,R
k
.
Given a valuation
θ
of the variables in
, the
world associated with θ
is
W
θ
R
1
,...,R
k
=
R
1
,...,R
k
where
R
i
={
t
|
t
∈
R
i
,
t
[
θ
]=
true
}
for each
i
=
1
,k
.