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 .
 
Search WWH ::




Custom Search