Database Reference
In-Depth Information
it is common to refer to them as naıve tables and Codd tables. For example, the instance
12
⊥
1
S
1
:
⊥
2
⊥
1
3
(2.3)
⊥
3
51
is a naıve table: the null
⊥
1
occurs twice. On the other hand, the instance
12
⊥
1
S
2
:
(2.4)
⊥
2
⊥
3
3
is a Codd table, since each null occurs just once.
The semantics of an incomplete instance
S
is the set of
complete
instances (i.e., in-
stances without nulls) it can represent. These are defined via homomorphisms. We write
C
ONST
(
S
) and V
AR
(
S
) for the sets of constants and nulls, respectively, that occur in
S
. For example, in the instance
S
1
above
(2.3)
,wehaveC
ONST
(
S
1
)=
{
1
,
2
,
3
,
5
}
and
V
AR
(
S
1
)=
.
A
homomorphism h
:
S
{⊥
1
,
⊥
2
,
⊥
3
}
S
between two database instances of the same schema is a
→
map
C
ONST
(
S
)
V
AR
(
S
)
h
:V
AR
(
S
)
→
∪
such that, for every relation symbol
U
, if the fact
U
(
t
) is in
S
, then the fact
U
(
h
(
t
)) is in
S
.
In defining
h
(
t
),weextend
h
to constants by letting
h
(
c
)=
c
for every
c
C
ONST
.
The semantics of an incomplete database instance
S
, denoted by
Rep
(
S
), is then defined
as the set of complete databases
S
such that there is a homomorphism
h
:
S
∈
S
.Thatis,
→
S
with D
OM
(
S
)
S
}
Rep
(
S
)=
{
⊂
C
ONST
|∃
homomorphism
h
:
S
→
.
For example, given the incomplete database
S
1
in
(2.3)
, the instance
124
343
S
:
551
378
is in
Rep
(
S
1
), as witnessed by the homomorphism
h
(
⊥
1
)=4,
h
(
⊥
2
)=3, and
h
(
⊥
3
)=5.
Certain answers and naıve evaluation
Given an incomplete database
S
and a query
Q
,
one normally tries to compute
certain answers
, i.e., answers that are true regardless of the
