Databases Reference

In-Depth Information

Irrelevant components:
Every JD
J
is equivalent to a JD
J′
that's obtained from
J
by adding or dropping

irrelevant components.

Combining components:
Every JD
J
implies a JD
J′
that's obtained from
J
by replacing two components by

their union.

Irreducibility:
Every JD
J
that holds in relvar
R
is equivalent to at least one JD
J′
─not necessarily distinct

from
J
─that holds in
R
and is irreducible (where
equivalent
and
irreducible
must both be understood as being

with respect to
R
). It follows that
R
's irreducible JDs in fact imply all of
R
's JDs.

The following observations are also valid (I haven't discussed them in detail, but they're intuitively obvious):

Adding attributes:
If JD
J
holds in relvar
R
, then so does every JD
J′
that's obtained from
J
by adding some

attribute of
R
to some component of
J
.

Adding components:
If JD
J
holds in relvar
R
, then so does every JD
J′
that's obtained from
J
by adding any

subset of the heading of
R
as another component.

Observe in both of these cases, however, that we're talking about implication, not equivalence. For example,

in relvar S (but ignoring SNAME once again, for simplicity), the JD
{SNO,STATUS},{SNO,CITY}} holds, and

therefore the following JD holds too:
{{SNO,STATUS},{SNO,CITY},{CITY,STATUS}}. However, the

converse is false─if the latter JD holds, it doesn't follow that the former one does.
3

We can also say the following: If
J
is a JD that holds in relvar
R
and
J
implies another JD
J′
, where
J′
is

obtained from
J
by dropping attributes from components of
J
and/or dropping entire components from
J
, then
J
is

certainly a “bad” JD (see the remarks on the topic of good vs. bad JDs at the end of the section “Combining

Components”). However, not all “bad” JDs can be obtained in this simple fashion, as we'll see.

Now I'd like to generalize the discussion somewhat. First of all, from this point forward I'll take the term

dependencies
to mean either FDs or JDs or both, as the context demands.
4
Now, throughout this topic so far,

whenever I've considered the question of dependencies being implied by others, I've tacitly limited my attention to

ones that are implied by an
individual
dependency. More generally, however, it turns out that certain
sets
of

dependencies can imply others. Let me give an example.

Consider a relvar SPT, with attributes SNO, PNO, and STATUS (only), where the attributes have their usual

meanings. Suppose we're told, not unreasonably, that the following dependencies (one FD and one JD) both hold in

this relvar:

{ SNO , PNO }
→
{ STATUS }

{ { SNO , PNO } , { SNO , STATUS } }

Now, given the semantics of the situation, it's intuitively obvious that (a) {SNO} isn't a key for SPT and yet

(b) the FD {SNO} → {STATUS} holds in SPT implicitly (and so SPT isn't in 2NF, incidentally). Note that I say

3
Of course, the former JD does hold in our running example, thanks to the fact that the FD {CITY} → {STATUS} also holds. But the latter JD

doesn't imply the former in general.

4
As we know, other kinds of dependencies─e.g., equality dependencies, which were mentioned in passing in Chapter 3 and elsewhere and are

discussed further in Chapter 13─exist also, but I'm deliberately excluding them from consideration at this time.