Re: Fails Relational, Fails Third Normal Form

In article <20150212012341.d8329e51.jklowden_at_speakeasy.net>,  "James K. Lowden" <jklowden_at_speakeasy.net> wrote:

> Quoth Nicola on Thu, 05 Feb 2015:
> > A few years ago I implemented a few algorithms from Koehler's PhD
> > thesis in a Ruby script. Given a set of FDs, the script finds all the
> > keys and all the minimal covers.... Then, I had a graduating student
> > re-implement it in Java and adding a dependency-preserving
> > decomposition in BCNF (when it exists) or in 3NF to the output.
>
> My first reaction is a little unkind. I think this is what lawyers call
> "assuming facts not in evidence". *Given* a set of FDs, the program
> generated a 3NF database design. Hurray! Now, where to find those
> pesky FDs for input?

From the requirements? I'm not sure I grasp what your point is. Do you mean that turning some requirements into FDs is difficult (you would not be alone: Stonebraker says that "mere mortals do not understand FDS")? Or that FDs (and even MVDs, JDs, etc) comprise only a tiny fraction of real system's set of requirements, so it's not worth bothering?

> It reminds me of a joke my Economics professor told the class about
> three professors stuck on a desert island devising a way to open a can
> of beans. The Economist's solution was simple, "First, assume a can
> opener".

FDs do not come out of void, they follow from your requirements. They are just a formal version of a very special (and relatively simple) type of requirement. I don't arbitrarily decide to assume that {desert island} -> {can opener}, unless you tell me that there cannot be two can openers in the same desert island, in the world of desert islands you are interested in.

> On second thought, though, it's cause for optimism. If a Ruby script
> and a grad student can generate a correct design, then it is a
> tractable problem.

Computationally, database design problems are (highly) intractable in general. But in practice many problems can be solved. For example, finding the keys of a schema (given the FDs) is an inherently hard problem, but for schemas with up to a few tens of attributes or so, only in few cases you are not able to find them in a reasonable amount of time. On the contrary, finding all the minimal covers is much less practical, even when there are not many of them.

> What remains is a convenient syntax for capturing
> the "pesky FDs", something that is the purview of academia.

FDs are a special type of first-order formulas. I can imagine defining an English-like syntax for them.

Nicola

• news://freenews.netfront.net/ - complaints: news_at_netfront.net ---