From: Vadim Tropashko Newsgroups: comp.databases.theory Subject: RE: 4NF is Where It Is At! [WAS Re: 1:1 relationships] Date: Wed, 14 Feb 2001 20:51:36 -0500 Organization: Posted via Supernews, http://www.supernews.com Message-ID: <3A8CBD26@MailAndNews.com> X-InterChange-Posted-By: vadic@MailAndNews.com Sender: Vadim Tropashko X-EXP32-SerialNo: 50000000 Mime-Version: 1.0 Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: 7bit X-Newsreader: InterChange (Hydra) News v3.61.08 X-Complaints-To: newsabuse@supernews.com Lines: 128 >===== Original Message From hidders@win.tue.nl (Jan Hidders) ===== > >Actually, the math behind 5NF is much simpler than >that of 4NF. And I was really baffled when I saw that Date doesn't tell >how you can check if you are in 5NF because that is really quite >simple. But later I found that some books (and a lot of web pages) >actually do not tell this correctly. Quite amazing. > I half baked some geometric interpretation below. Basically, I agree that 5NF is simpler that 4NF. Consider Course-Teacher-Text (CTX) example from C.Date's textbook: Course Teacher Text ------------------- Phys Green Mech Phys Green Opt Phys Brown Mech Phys Brown Opt Math Green Mech Math Green Vect Math Green Trig Let's picture those records in 3-dimensional space 1 --- 1 --- 0 --- 0 / | / | / | / | / | / | / | / | 1 0 1 0 0 0 0 0 | / | / | / | / | / | / | / | / 1 --- 0 --- 1 --- 1 where the axes are Phys Brown ^ ^ | / Course (C) Teacher (T) | / Text (X) | / Mech---Opt---Vect-->Trig Math Green We assume that records in the active domain are represented as 1s. The shapes of both the set of all 1s, and the set of all 0s are of our primary interest here. Let's call them 1-image, and 0-image, correspondingly. What does the statement "CTX relation could be decomposed into a join of CT and CX" mean in this interpretation? Whenever a 3D geometric solid is defined through a synthesis of its projections we deal with cylinder sets. In our example {,} is a cylinder set, because it doesn't vary along axis T. It is sometimes more convenient to write this set as {| c=Phys & x=Mech}. Note, that when describing a geometric shape as a composition of projections, 0s are more important than 1s, because whenever you have a cylinder of 0s (0-cylinder, for short), it means that a view along 0-cylinder axis through 1-image is unobstructed. In other words, the cylinder is disjoint to 1-image. Now, the steps of reconstructing a shape from its projections are: 1. Consider 0-image within each projection subspace (CT, or CX) 2. Build 0-cylinders upon them (in CTX) 3. Make a union of those cylinders 4. The result is 0-image (Note, that this construction is very similar to Conjunctive Normal Form in Boolean algebra). Now, the condition of a set in CTX being decomposable into a join of its projections upon CT and CX is: ___________________________________________________ Every 0 point in active domain must be enclosed into either 0-cylinder along T or 0-cylinder along X axes. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ For example, is enclosed into {| c=Math & t=Green} So far we were talking about decomposition of a set into a join of projections, which is really 5NF definition. (BTW, our example doesn't really distinguish 4NF and 5NF). Let's consider MVDs. Let's call a 0-point in CTX that cannot be covered by any 0-image cylinder set as *isolated* point. It is easy to see that if there exists an isolated 0-point p, then no MVD is present. Indeed, let's try covering p with 0-cylinder along T axis. Since, p is isolated, no such cylinder exists, therefore, there must be a 1-point s such that p(T)=s(T) & p(C)=s(C). Similarly, there must be 1-point t such that p(X)=t(X) & p(C)=t(C). Now, if MVD C->T|X holds, then both u and v defined as u(C)=v(C)=t(C)=s(C) & u(T)=t(T) & v(T)=s(T) & u(X)=s(X) & v(X)=t(X) would necessarily be 1-points. Now, let's focus on point v, which components are: v(C)=t(C), v(T)=s(T), v(X)=t(X) Compare those with components of p: p(C)=t(C), p(T)=s(T), p(X)=t(X) Now that a point in CTX is uniquely defined by its components, p and v must be the same point. Therefore, our conclusion that it's both 0-point and 1-point is a contradiction. Unfortunately, the last paragraph was not quite a geometric explanation. Note, however, that if we introduce total order relations on each of C, T, and X, then definitions of points u and v becomes inf(t,s) and sup(t,s) lattice operations induced by partial order on CTX. A set with multidependency becomes a 1-image that is closed under those inf and sup operations. Fagin's theorem could be interpreted then as: "1-image sets closed under inf and sup operations are equivalent to O-images without isolated points". In summary, 4NF is about lattice operations, while 5NF is about cylindric sets, and cylindric sets are geometrically more intuitive. Hope that this summary doesn't look like "Theory-in-a-minite" (http://rinkworks.com/bookaminute/:-) ------------------------------------------------------------ Get your FREE web-based e-mail and newsgroup access at: http://MailAndNews.com Create a new mailbox, or access your existing IMAP4 or POP3 mailbox from anywhere with just a web browser. ------------------------------------------------------------