Databases Reference
In-Depth Information
(“
X
double arrow
Y
bar
Z
”). In the case of relvar CTX, for example, we have:
{ CNO }
→→
{ TNO } | { XNO }
Now, we might say,
very
loosely, that an MVD is like an FD, except that instead of “For one of these, there's
one of those,” it's “For one of these, there's a
set
of those” (it's this informal characterization that makes MVDs a
little easier to understand than JDs in general). But the point about always going in pairs is important (note that
nothing analogous applies to FDs). Indeed, if the MVD concept is defined
too
imprecisely (as I've just done, in
fact!), one could incorrectly conclude that for
every
pair of subsets
X
and
Y
of the heading of the pertinent relvar,
there's an MVD from
X
to
Y
. For example, in the shipments relvar SP, there's certainly a set of quantities for each
supplier number, but the MVD {SNO} →→ {QTY} does
not
hold─it's not the case that for a given supplier number
s
and given part number
p
, the set of quantities
q
associated with that (
s
,
p
) pair depends on
s
alone.
MULTIVALUED DEPENDENCIES (FORMAL)
The definitions in this section parallel those given in earlier chapters for FDs and JDs and are therefore presented
with little by way of further commentary.
Definition:
Let
H
be a heading; then a
multivalued dependency
(MVD)
with respect to
H
is an expression
of the form
X
→→
Y
, where
X
(the
determinant
) and
Y
(the
dependant
) are both subsets of
H
.
Note:
The
phrase
MVD with respect to H
can be abbreviated to just
MVD
, if
H
is understood.
Note carefully that, like FDs and JDs, MVDs are defined with respect to some heading, not with respect to
some relation or some relvar. Note too that from a formal point of view (again like FDs and JDs), MVDs are just
expressions: expressions that, when interpreted with respect to some specific relation, become propositions that by
definition can evaluate to either TRUE or FALSE.
Definition:
Let relation
r
have heading
H
; let
X
→→
Y
be an MVD,
M
say, with respect to
H
; and let
Z
be
the attributes of
H
not contained in either
X
or
Y
. (In other words,
Z
is the complement with respect to
H
of
the union of
X
and
Y
, and the union of
X
,
Y
, and
Z
is equal to
H
.) If
r
satisfies the JD
{
XY
,
XZ
}, then
r
satisfies
M
; otherwise
r
violates
M
.
Note that the foregoing definition is symmetric in
Y
and
Z
, whence it follows that
r
satisfies the MVD
X
→→
Y
if and only if it satisfies the MVD
X
→→
Z
(and we can therefore write them as a “one liner,” as noted in the
previous section).
Definition:
The MVD
M
holds
in relvar
R
(equivalently, relvar
R
is subject to
the MVD
M
) if and only if
every relation that can ever be assigned to relvar
R
satisfies
M
. The MVDs that hold in relvar
R
are
the
MVDs of
R
.
From this definition and the previous one, it follows that
R
is subject to the MVD
X
→→
Y
if and only if it's
subject to the MVD
X
→→
Z
.
Fagin's Theorem:
Relvar
R
can be nonloss decomposed into its projections on
XY
and
XZ
if and only if the
MVDs
X
→→
Y
|
Z
hold in
R
.
