Re: Who first (publicly) asserted 3NF is "good enough"?

On 2006-09-18, Roy Hann wrote:

> It has always seemed to me that nothing looks more obviously and
> intuitively wrong than a table that is in third normal form (3NF) but
> not also 4NF. [...] It's probably far too late to get a confident
> answer now, but does anyone know if there was a single authoritative
> writer (long ago) who expressed this foolish idea?

I believe the practical sufficiency of 3NF became an appropriate topic of academic discussion for two reasons. First, [BB79] shows that the database design problem for 3NF is solvable in at most quadratic time, while in general it's NP-hard already for BCNF. This limits our ability to show that complex schemas in fact *are* in 4NF, and around '79 they seem to have worried a whole lot about that sort of thing. Second, while lossless join, dependency preserving decomposition into 3NF is always possible, the same does not hold for BCNF. This is even worse because loss of dependency preservation implies a run time penalty for constraint checking.

I wasn't able to come up with the original reference for the second half, but the issue is spelled out at least in [Ma83] (at 6.7.1), and is illustrated by example at least as early as [Ri77] (at 3, second example).

As people have already said, the practical impact of such results is limited [DF92]. But that doesn't mean it's nil, especially after you take into consideration the limitations of existing constraint checking engines. My favorite example in this vein is the so called scientific dataset, like a pile of images or higher rank tensors, where the key of the aggregate/image/function multidetermines the set of valid indices for each of its dimensions {A->>B, A->>C} and they in turn determine the value of the function at the indexed point {ABC->D}. How would you represent that if you want to maintain it under completeness semantics [GM86], and you're given, say, Oracle?

[BB79] Beeri, Catriel and Bernstein, Philip: Computational Problems

        Related to the Design of Normal Form Relational Schemas, ACM
        Transactions on Database Systems, Vol. 4, No. 1, March 1979
[DF92] Date, Chris and Fagin, Ronald: Simple Conditions for
        Guaranteeing Higher Normal Forms in Relational Databases, ACM
        Transactions on Database Systems, Vol. 17, No. 3, September 1992
[GM86] Graham, Marc, Mendelzon, Alberto and Vardi, Moshe: Notions of
        Dependency Satisfaction, Journal of the ACM, Vol. 33, No. 1,
        January 1986
[Ma83] Maier, David: The Theory of Relational Databases, Computer
        Science Press, 1983
[Ri77] Rissanen, Jorma: Independent Components of Relations, ACM
        Transactions on Database Systems, Vol. 2, No. 4, December 1977

-- 
Sampo Syreeni, aka decoy - mailto:decoy_at_iki.fi, tel:+358-50-5756111
student/math+cs/helsinki university, http://www.iki.fi/~decoy/front
openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2