Database Reference
In-Depth Information
2. DATA AND QUERY MODEL
R
FID
SSN
N
351
185
Smith
X
=
1
351
785
Smith
X
=
1
=
1
352
185
Brown
Y
352
186
Brown
Y
=
1
Figure 2.2:
A Simple C-table.
R
1
R
2
FID
SSN
N
FID
SSN
N
351
185
Smith
351
185
Smith
352
185
Brown
352
186
Brown
{
X
→
1
,Y
→
1
}
{
X
→
1
,Y
→
2
}
R
3
R
4
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
}
Figure 2.3:
The four possible worlds for C-table in
Figure 2.2
.
Dom
X
in its domain. When
θ(X)
=
a
, then we write
X
→
a
, or, with some abuse,
X
=
a
. The set
of all possible valuations is denoted by
Dom
X
n
.
A
propositional formula
is constructed from atomic events and the Boolean constants
true
and
false
, using the binary operations
=
Dom
X
1
×···×
∨
(logical “or”) and
∧
(logical “and”), and the unary operation
¬
(logical “not”). A formula
X
=
a
means
¬
(X
=
a)
, or, equivalently,
X
=
a
1
∨
...
∨
X
=
a
m
if
Dom
X
−{
a
}={
a
1
,...,a
m
}
. We also call
a
complex event
, or simply an
event
, and denote the set
of satisfying assignments of
by
ω()
={
θ
|
θ
is a valuation of variables in
,
[
θ
]=
true
}
Consider again our census scenario.
Figure 2.2
shows a c-table representing data about
name
and
social security numbers
only (we drop
marital-status
but will re-introduce it in
Subsection 2.7.3
).
The variables
X, Y
are discrete, and their domains are
Dom
X
=
. The conditions
under the columns
encode symbolically the assignments in which their corresponding tuples
exist. For instance, the first tuple occurs in all possible worlds where
X
Dom
Y
={
1
,
2
}
→
1 and does not occur in
worlds where
X
→
2. Every assignment gives rise to a possible world, consisting of those tuples
whose formula
is true. The c-table in
Figure 2.2
has four distinct worlds, corresponding to possible
assignments of variables
X
and
Y
. These four worlds are shown in
Figure 2.3
.
Now assume that we would like to enforce the integrity constraint that no two persons can
have the same social security number (SSN). That is, the world
R
1
in
Figure 2.3
is considered wrong
