Thursday - September 29, 2005

Light Reading

Definition 2.1 : A relation r is a table where each column is labeled and represents an attribute and each row represents a record. No two columns can have the same label, and no two rows can be identical (cf .[121]) . There are two relational operations of interest to us : projection and join.

Definition 2.2 : Let U be a set of attributes and let r be a relation over U.

(a) For any X c U, r(X), the projection of r on X, is a relation obtained by taking from each row of r those entries corresponding to the attributes of X an d identifying identical rows.

(b) For any family (X1,X2, . . .,Xk) of subsets of U such that X 1 uX2 u . . .uXk = U , the natural join of the projection of r onto the X 1 ‘s is r(X1)*r(X2)* . . .*r(Xk ) {uJ for each 1
Definition 2.3 : Let U be a finite set of attributes . A functional dependency (FD) f over U is an ordered pair (X,Y) of non-empty subsets of U . Following common notation, we shall write f : X Y and call X the left side of f, denoted L(f) , and Y the right side of f, denoted R(f).

Definition 2.4 : Let U be a set of attributes and let F be a set of FD's over U . The pair [U,F] is called a dependenc y system . A relation r is called a Valid relation over [U,F] if for every FD f : X + Y in F, no two rows of r with identical entries in the X-columns have differing entries in the Y-columns.

Definition 2.5 : Let F be a set of FD' s over U . For any X c U, we define CL F(X ) (or simply CL(X)), the closure of X unde r F, as follows [1,8]:

(1) X c CL(X)

(2) If Y c CL(X) and Y + Z is a FD in F then Z c CL(X).

(3) CL(X) is the least set (with respect to set inclusion) satisfying (1) and (2). A database scheme is a collection of sets of attributes used to define the relations in the database . A relation scheme is a set of attributes used to define a single relation. A decompositio n of a relation scheme R = A l A2 . . . An is its replacement by a database scheme T = {R1,R2, . . .,Rk} such that R1 uR2 u . . .uRk = R (cf .E16]).

Definition 2.6 : Let F be a set of FD' s over U and let T = {X1,X2, . . .,Xk} be a collection of subsets of U.

(a) T is said to be a lossless-join decomposition of U under F if for every valid relation r over [U,F]: r = r(X1)*r(X2)'* . . .*r(Xk) that is, r is the natural join of its projections onto X i's.

(b) For each 1si<_k, let F i be a set of FD's over Xi such that CLF (Z) = CLF (Z)nXi for every Z c Xi. T is said to be a dependency-preserving decomposition of U if for every Y c U, we have CLF (Y) = CLG (Y), where G = F 1 uF 2 u . . .uFk.

We note the following result of Aho, Beer and Ullman ([1], Corollary 1).

Remark 2.7 : {X,Y} is a lossless-join decomposition of XuY if and only if either Y c CL(XnY) or X c CL(XnY).

The next definition will formalize the concepts of key and Boyce-Codd Normal Form (BCNF) .

Definition 2.8 : Let F be a set of FD' s over U and let W c U.

(a) A subset X of W is said to be a key of W under F if W c CL(X) . Otherwise, it is a nonkey of W under F.

(b) W is said to be in BCNF if whenever A E CL (X) -X for A E W, X c W, then X is a key of W under F. (In other words, the only nontrivial dependencies in W are those in which a key functionally determines one or more attributes [16] .)

_{From: DECOMPOSITION OF A RELATION SCHEME INTO BOYCE-CODD NORMAL FORM by Don-Min Tsou, Patrick C . Fischer}

Posted by The Skipper     on 09/29/2005 at 11:19 PM   
Filed Under: •   
• Comments (20) • Trackbacks(0)  Permalink •  

DISCLAIMER

THE SERVICES AND MATERIALS ON THIS WEBSITE ARE PROVIDED "AS IS" AND THE HOSTS OF THIS SITE EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES, EXPRESS OR IMPLIED, TO THE EXTENT PERMITTED BY LAW INCLUDING BUT NOT LIMITED TO WARRANTIES OF SATISFACTORY QUALITY, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, WITH RESPECT TO THE SERVICE OR ANY MATERIALS.

Not that very many people ever read this far down, but this blog was the creation of Allan Kelly and his friend Vilmar. Vilmar moved on to his own blog some time ago, and Allan ran this place alone until his sudden and unexpected death partway through 2006. We all miss him. A lot. Even though he is gone this site will always still be more than a little bit his. We who are left to carry on the BMEWS tradition owe him a great debt of gratitude, and we hope to be able to pay that back by following his last advice to us all:

1. Keep a firm grasp of Right and Wrong
2. Stay involved with government on every level and don't let those bastards get away with a thing
3. Use every legal means to defend yourself in the event of real internal trouble, and, most importantly:
4. Keep talking to each other, whether here or elsewhere

It's been a long strange trip without you Skipper, but thanks for pointing us in the right direction and giving us a swift kick in the behind to get us going. Keep lookin' down on us, will ya? Thanks.

THE INFORMATION AND OTHER CONTENTS OF THIS WEBSITE ARE DESIGNED TO COMPLY WITH THE LAWS OF THE UNITED STATES OF AMERICA. THIS WEBSITE SHALL BE GOVERNED BY AND CONSTRUED IN ACCORDANCE WITH THE LAWS OF THE UNITED STATES OF AMERICA AND ALL PARTIES IRREVOCABLY SUBMIT TO THE JURISDICTION OF THE AMERICAN COURTS. IF ANYTHING ON THIS WEBSITE IS CONSTRUED AS BEING CONTRARY TO THE LAWS APPLICABLE IN ANY OTHER COUNTRY, THEN THIS WEBSITE IS NOT INTENDED TO BE ACCESSED BY PERSONS FROM THAT COUNTRY AND ANY PERSONS WHO ARE SUBJECT TO SUCH LAWS SHALL NOT BE ENTITLED TO USE OUR SERVICES UNLESS THEY CAN SATISFY US THAT SUCH USE WOULD BE LAWFUL.

Copyright © 2004-2015 Domain Owner