
	Trending ▼ ICSE CBSE 10th ISC CBSE 12th CTET GATE UGC NET Vestibulares ResFinder

create response.

73 pages, 0 questions, 0 questions with responses, 0 total responses,

	ajaykumar3488	+Fave Message
	Profile Timeline Uploads

Home > ajaykumar3488 >

Formatting page ...

FUNCTIONAL DEPENDENCIES CSC343 Functional Dependencies Functional Dependencies Examples: PERSON Relation PERSON SIN NAME CITY 123 Laurent Toronto 324 Bill Toronto 574 Bill Montreal What can we say about Person table? If I know the sin number I know the name SIN attribute determines NAME attribute. Attribute NAME functionally depends on attribute SIN Warning: Knowing the NAME does not imply the SIN knowledge: NAME NOTATION: SIN SIM NAME 2 CSC343 Functional Dependencies Functional Dependencies COURSES Relation STUDENT 0,n Name enroll 0,n COURSES Name 1,1 teach 0,n Name PROF COURSE NAME Database Database Database Math PROF STUDENT MIGNET SMITH MIGNET BILL MIGNET SMITH HARDIN GEORGE A Course has only one Professor NAME PROF 2 tuples that have the same value for NAME have the same value for PROF 3 CSC343 Functional Dependencies Functional Dependencies Key Example PERSON (SIN, LastName, FirstName, Address) SIN SIN SIN LastName FirstName Address If we know the SIN value, we know all the attributes. 2 tuples sharing the same SIN are identical SIN identi es a tuple. SIN is a key SIN LastName FirstName SIN LastName is a superkey (LastName is redundant) 4 CSC343 Functional Dependencies Functional Dependencies SUPPLYING Relation SUPP (SNAME, PNAME, QUANT, PRICE) SNAME PNAME QUANT SNAME PNAME PRICE SNAME PNAME is a key. SUPPLIER Sname 0,n Quant SUPPLYING Price 0,n PRODUCT Pname 5 CSC343 Functional Dependencies Functional Dependencies ADDRESS Relation ADDRESS (STREET, NUMBER, CITY, ZIPCODE) Simplifying Hypothesis Several zipcode for a city: Toronto = M5B3F4, M5S2E4, . . . One city for a zipcode: Mxxxxx = Toronto An address (street + number + city) belongs only to one zipcode: 4 St George Street, Toronto = M5S 2E4 Number Street City Zipcode City Zipcode Keys of the relation ADDRESS: (Street Number City) and (Number Street Zipcode) 6 CSC343 Functional Dependencies Functional Dependencies De nitions a) Functional Dependencies Let R(U) a relational schema, r one relation of the schema R, X attribute sub-set of R. The functional dependencies X U, Y U two Y is true in r, iff (if and only if) for every tuples of r that share the same value for all attributes of X, they also share the same value for all attributes of Y. Example: ADDRESS(STREET, NUMBER, CITY, ZIPCODE) X = ZipCode Y = City 7 CSC343 Functional Dependencies Functional Dependencies b) SuperKey Let R(U) a schema and X U a attribute subset. X is a superkey superkey of r of the schema R, if X U. Example: SIN LASTNAME SIN LASTNAME FIRSTNAME ADDRESS SIN LASTNAME is a superkey c) KEY X is a key, if: 1. X is a superkey: X 2. it does not exist Y U X, such that Y U Example: STREET NUMBER CITY STREET NUMBER CITY ZIPCODE STREET NUMBER CITY is a key (why?) 8 CSC343 Functional Dependencies Functional Dependencies Finding a Key: Example COURSE(Name,Hour,Room,Prof) N HR, HR P We can proof from that if we know the name of the course, we also know the name of the professor. (Name is a key): 1. N HR: two tuples that share the name of the course share also the hour and the room value. 2. HR P: two tuples that share the hour and the room share also the name of the professor. 3. FD 1 and 2 implie that two tuples which have the same name for the course have also the same professor name: N P We can de ne some properties and rules on the FD which permit to deduct others FDs. 9 CSC343 Functional Dependencies Functional Dependencies Functional Dependencies Properties (Armstrong s Axioms) 1) Re exivity If X Y then Y X (for every attribute subsets X et Y) Example: NAME CITY NAME Trivial: Two persons who have the same name and live in the same city have the same name. 10 CSC343 Functional Dependencies Functional Dependencies 2) Transitivity If X Y and Y Z, then X Z Example : R(SIN, ZIPCODE, CITY) SIN ZIPCODE, ZIPCODE CITY SIN CITY If we know the zipcode from a sin number and the city form the zipcode then we know the city from the sin number. 3) Augmentation X Y Example: SIN XZ YZ ZIPCODE SIN CITY ZIPCODE CITY 11 CSC343 Functional Dependencies Functional Dependencies 4) Union et decomposition X A, X B X AB 5) Pseudotransitivity X Y, WY Z WX Z REMARK: Union, decomposition and pseudotransitivity can be deduced from the others axioms. 12 CSC343 Functional Dependencies Functional Dependencies Closing set of a functional dependencies set From the functional dependencies set given from the real world and using the preceding properties (Armstrong s axioms) we can deduce others FDs: Examples: 1) R(A,B,C,D) = A B, B Transitivity: A Notation: C C A C 13 CSC343 Functional Dependencies Functional Dependencies 2) R(Course, Prof, Hour, Room, Student, Mark) = C HR P, HR P, HS C, HP C,P,M R, CS M, HS R So HS is a key Why? The union of denoted . and every deduced FD is called closing set, or attribute closure of is 14 CSC343 Functional Dependencies Functional Dependencies Minimal Closure The minimal closure 1. We can infer from of a set of functional dependencies (FD) is a set of FD such that: the same FD than from : = 2. Only one attribute is on the right side on every FD in (decomposition) 3. Every FD are useful: if we delete one we can not obtain 4. Every FD are elemantary: the set A which is not elementary by A B. anymore. C; AC B is redundant: we replace AC B, 15 CSC343 Functional Dependencies Functional Dependencies Example Functional Dependencies AB C C A BC D ACD B D EG BE C CE AG CE ACD Minimal Closure AB C CA BC D CD B DE DG BE C CE G A is missing, why? B is not elementary, why? 16 CSC343 Functional Dependencies Functional Dependencies Answer: B is not elemenaty, why? ACD C CCD CD A CCD ACD ACD by augmentation CD ACD (A ACD and ACD B CD A by re exivity and union) B by transitivity Second demonstration By pseudotransitivity, C A, ACD B CCD B CD B. 17 CSC343 Functional Dependencies Functional Dependencies Minimal Closure Concretely, the minimal closure is either directly given by the real world analysis. is eitheir trivialy deduced because: every FD are useful and elementary It is enough to decompose the right side of every FDs. 18 CSC343 Functional Dependencies Functional Dependencies New De nition for a SuperKey Let R(U) a relational schema, a set of functional dependencies and X U a set of attributes. X is a superkey of R if for all A U X A or if: X Compute from But show that A might take time. X A is easy and fast. 19 CSC343 Functional Dependencies Functional Dependencies Calculation of a key of a relation Let R(U) a relational schema and X U a set of attributes. We de ne as a subset of attributes A such that If A belongs to , then by de nition X A is the set of functionally dependent attributes of X. X A To nd a key we use the following algorithm: = U X is a superkey X such that = U 2. X is a key, if it does not exist Y 1. We search for one X such that 20 CSC343 Functional Dependencies Functional Dependencies Step 1: We start from X For every Y A, such that Y We get . Step i: We start For every Y We get . X, Y A , Y A, such that Y A , we add A to X. , we add A to . We stop when we do not nd new FDs anymore. = = 21 CSC343 Functional Dependencies Functional Dependencies Examples 1. Show that HS is a key for R(CHSNRP) with the set of FD given before. 2. for the relation ADDRESS(CITY, STREET, NUMBER, ZIPCODE), show that CITY STREET NUMBER is a key. What is the other one? 22 CSC343 UPDATE ANOMALIES CSC343 Functional Dependencies Update Anomalies Example Let the schema S1: Supplier(SNAME, FADDRESS) Product(SNAME, PNAME, PRICE) and the set of DF: SNAME FADDRESS, (SNAME PNAME) PRICE Suppose now that we replace S1 by S2: R(SNAME, SADDRESS, PNAME, PRICE) 24 CSC343 Functional Dependencies Update Anomalies Anomalies R(SNAME, SADDRESS, PNAME, PRICE) SNAME SADDRESS, (SNAME PNAME) PRICE What is the key of R? SMITH JONS SMITH Toronto Montreal Toronto COMPUTER COMPUTER KEYBOARD 1000 900 400 1) REDONDANCY: the address for one supplier appears several times. 2) UPDATE: if we change the address in one tuple, we must also perform the same update in the others. 25 CSC343 Functional Dependencies Update Anomalies 3) DELETION: if JONS do not supply COMPUTER anymore, we delete the second tuple we lost any information about JONS. 4) INSERTION: we can not insert a new supplier and its address if we do not know, at least, one product that it supplies. SMITH JONS SMITH DURAND Toronto Montreal Toronto NICE COMPUTER COMPUTER KEYBOARD 1000 900 400 THE INITIAL SCHEMA S1 IS BETTER 26 CSC343 Functional Dependencies Update Anomalies Integrity Constraints The list of attributes is not suf cient to describe the semantic of the real world. It exists several types of constraints on the tuples: 1. dependencies (functional, multivalued, ...) 2. constraints that depend of the attribute domain: year 2000 3. etc. It is the dependencies which permits a good schema conception, i.e., the decomposition in good relations. 27 CSC343 Functional Dependencies Update Anomalies Qualities for a good schema 1. Avoid anomalies decomposition 2. The decomposition should keep the same amount of information Join a relation f1 of the schema SUPPLIER(SNAME, SADDRESS) and a relation f2 of the schema SUPPLIER(SNAME, PNAME, PRICE) got by decomposition of the relation r of the schema R(SNAME, SADDRESS, PNAME, PRICE) must give back r. 3. The decomposition must keep the same constraints (FD). The decomposition of R in R1(SNAME, SADDRESS, PRICE) and R2(PNAME, PRICE) do not preserve the FD. Why? 28 CSC343 DECOMPOSITION AND NORMAL FORM CSC343 Functional Dependencies Decomposition and Normal Form Relation in rst normal form (1NF) All attributes are atomic (elementary) Relation that we know. 30 CSC343 Functional Dependencies Decomposition and Normal Form Relation 1NF MARKS ( COURSE DB DB DB ARCHI ARCHI STUDENT John Mark Tom Tom John MARK ) 80 90 0 100 0 Relation N1FN MARKS ( COURS DB ARCHI PERF (STUDENT John Mark Tom Tom John MARK) ) 80 90 0 100 0 31 CSC343 Functional Dependencies Decomposition and Normal Form Relation in 3rd Normal Form 2nd Normal Form: Purely historical. 3rd normal form: 3NF avoid most of the anomalies Goal of the game: to decompose a relation (1NF) to a set of 3NF relations. 32 CSC343 Functional Dependencies Decomposition and Normal Form 3NF: First De nition Let (R, F) be a relational schema. We suppose that is a minimal closure. De nition: R is in 3NF, if for every X A of , either X is a key or A belongs to one of the keys. 33 CSC343 Functional Dependencies Decomposition and Normal Form Examples: 3rd Normal Form 1) Post(City, Street, Zipcode) = CS Z, Z C Keys: CS, SZ Post is in 3NF. 2) Supplier(SNAME, ADDR, PNAME, PRICE) = SNAME ADDR, SNAME PNAME PRICE Keys: (SNAME PNAME) Supplier is not in 3NF. 34 CSC343 Functional Dependencies Decomposition and Normal Form 3) Schedule(Course, Hour, Room) = RH C, C R Keys: RH, CH Schedule is in 3NF. 4) R(A, B, C, D) = AB C, B D, BC A Keys: AB, BC R is not in 3NF. 35 CSC343 Functional Dependencies Decomposition and Normal Form 3NF: Second De nition Remark: It is not necessary for of , to be a minimal closure. It is enough that for all FD X A A is only composed by one attribute. A is not one of the attribute of X The de nition of a 3NF schema becames: A of De nition: A relation R is in 3NF, if every FD X conditions, either X is a superkey or A belongs to one of the keys. Actually, it is not necessary to check all FD of It is enough to check the ones belonging to satis es the preceding . ! 36 CSC343 Functional Dependencies Decomposition and Normal Form RemarK (Cont d): Why superkey in the rst condition? With conditions 1 and 2 weaker than the condition on the minimal closure it may exist some non elementary conditions: If X A is a non elementary condition and if X = U, then X is a superkey. 37 CSC343 Functional Dependencies Decomposition and Normal Form Remark (end): R(A,B,C,D) = AB C, B D, D B, B is not a minimal closure, why? (R, A ) is in 3NF, why? 38 CSC343 Functional Dependencies Decomposition and Normal Form Lossless-Join Decomposition Example R and = A (A a a c B b b b C) c a d B We decompose in: R1 ( A a c B) b b R2 (B b b b C) c a d 39 CSC343 Functional Dependencies R1 = (R) R2 = (R) R = R1 R2 R Decomposition and Normal Form R: (A a a a c c c B b b b b b b C) c a d c a d The decomposition of R in R1 and R2 losses information. The join creates tuples that do not exist in R. 40 CSC343 Functional Dependencies Decomposition and Normal Form Now we decompose R in: R1 ( A a c B) b b R2 ( A a a c C) c a d R = R1 R2 = R : R (A a a c B b b b C) c a d this decomposition is lossless-join. The condition is that after the join we found the same information than before the decomposition. 41 CSC343 Functional Dependencies Decomposition and Normal Form De nition A decomposition of R in R1, R2, ..., Rk with regard to a set of FD lossless-join iff for every instance r of the schema R that satis es , we have: r= (r) (r). . . is (r) Theorem: If (R1, R2) is decomposition of R and w.r.t. , iff: R1 a set of FD, then (R1, R2) is lossless-join R1 - R2 R2 or R1 belongs to R2 R2 - R1 . 42 CSC343 Functional Dependencies Decomposition and Normal Form Examples R (A, B, C) =A B 1) R1(A, B), R2(B, C) AB BC = B AB - BC = A BC - AB = C The FD B A does not exist, nor B C in The decomposition loses information. 43 CSC343 Functional Dependencies Decomposition and Normal Form 2) R1(A, B), R3(A, C) AB AC = A AB - AC = B A B is ( ). the decomposition is lossless join. 44 CSC343 Functional Dependencies Decomposition and Normal Form Dependency Preserving Decomposition De nitions 1. Projection of a set of FD om Z U ( )= Example: R(A,B,C,D), = AB ( ) = AB C, C A C, C A, A D 2. Decomposition which preserves the FDs of Let = (R1,...,Rk) be a decomposition, and a set of FD. preserves the FDs of , if we can nd again every FDs of from the union all FDs projected from in ( ), . . . , ( ): = of 45 CSC343 Functional Dependencies Decomposition and Normal Form Examples R(A,B,C,D) = AB = (ABC, = (ABC, C, C A, A D BD) do not preserve the FDs of AD) preserves the FDs of R(A,B,C) = A B, B A, A C = (AB, BC) preserve the FDs of 46 CSC343 Functional Dependencies Decomposition and Normal Form R(A, B, C, D) =A B, B C, AB D The decomposition R1(AC) R2(AB) R3(CD) do not preserve the FDs of . Why? 47 CSC343 Functional Dependencies Decomposition and Normal Form Decomposition of a relation in 3NF Given a schema (R, F) not in 3NF, i.e. with some anomalies, we want to nd a decomposition of R: 1. with 3NF relations; 2. lossless-join; 3. preserve the FDs of 48 CSC343 Functional Dependencies Decomposition and Normal Form Remark: a lossless-join decomposition do not necessarily preserve the FDs and inversely. the result does not necessarily give relations in 3NF. Theorem: Every 1NF relation has a decomposition in 3NF relations which are lossless-join and preserve the functional dependencies. 49 CSC343 Functional Dependencies Decomposition and Normal Form Algorithm We assume that 1. For each X is a minimal closure. A , create a relation of schema (XA). 2. If no keys is contained in one a the schema created during the rst step, add a relation of schema Y where Y is one key. 3. If after the rst step, it exist one relation R1 with a schema (X1A1) contained in a schema (X2A2) of another relation R2, delete the relation R1. 4. Replace the relations (XA ),..., (XA ) (corresponding to FD with the same left member) by a unique relation: (XA ...A ). 50 CSC343 Functional Dependencies Decomposition and Normal Form Examples 1) R(A,B,C,D) = AB C, B D, C A Keys: AB, BC Step 1: R1(ABC) R2(BD) Step 2: No need to create a new relation: Step 3: Delete R3: CA R3(CA) the key AB belongs to R1 ABC Good decomposition: R1(ABC) R2(BD) We can check that R1 et R2 are in 3NF. 51 CSC343 Functional Dependencies Decomposition and Normal Form 2) R(A,B,C,D,E) = AB C, C D, C A Keys: ABE, BCE Step 1: R1(ABC) R2(CD) R3(CA) Step 2: We add a relation of schema for the key ABE: R4(ABE) Step 3: Delete R3: CA ABC Good decomposition: R1(ABC) R2(CD) R4(ABE) Other solutions: Step 4: We replace R2 and R3 from step 1 by the relation of schema (CAD) Other good decomposition: R1(ABC) R2 (CAD) R4(ABE) What happened if we have chosen the key CBE? 52 CSC343 Functional Dependencies Decomposition and Normal Form 3) R(A,B,C,D) = AB C, C D, C A, AB D Keys: BA, BC The relation is not in 3NF. Why? Step 1: R1(ABC) R2(CD) R3(CA) R4(ABD) Step 2: we do not add the relation: key AB R1(ABC) Step 3: Delete R3: CA ABC Step 4: We replace R1 et R4 by R5(ABCD) we can delete R2. Decomposition: R5(ABCD) This decomposition is not in 3NF. Where is the problem? 53 CSC343 Functional Dependencies Decomposition and Normal Form Boyce-Codd Normal Form (BCNF) Some anomalies still exist in 3NF. Example: Post(City,Street,ZipCode), = VC Z, V C Keys: CS, SZ Post ( City Toronto Toronto Street Queen King ZipCode M4F3G4 M4F3G4 ) Redondancy between the zipcode and the city. 54 CSC343 Functional Dependencies Decomposition and Normal Form De nition: A relation is in Boyce-Codd Normal Form (BCNF), if for every functional dependency of , the left member id a superkey. Interest: We eliminate all anomalies. Remark: Every BCNF relation is in 3NF. Unfortunately, it does not always exist a decomposition in BCNF which also: is lossless-join preserves the FD. 55 CSC343 Functional Dependencies Decomposition and Normal Form Post Example Post(City,Street,ZipCode), = CS Z, Z C Keys: CS, SZ R is in 3NF but not in BCNF (in Z Post ( City Toronto Toronto C, Z is not a key) Street Queen King ZipCode M4F3G4 M4F3G4 ) 56 CSC343 Functional Dependencies Decomposition and Normal Form The decomposition R1(City,ZipCode), R2(Street,ZipCode) avoids the redondancy City,ZipCode, it is lossless-join, but does not preserve the functional dependency CS Z R1 ( City Toronto Montreal ZipCode M T ) R2 ( Strret Queen Queen Code M T ) The insertion of Toronto Queen M4, i.e. Toronto M4 and King M4 respects Z C but do not respect anymore CS Z R1 ( Ville Toronto Montreal Toronto Code M T M4 ) R2 ( Street Queen Queen Queen Code M T M4 ) 57 CSC343 Functional Dependencies Decomposition and Normal Form Decomposition Algorithm We assume that R(U) is a relational schema and 1. Pick a FD X is a minimal cover. Y not verifying BCNF 2. Partition R into R1(X Y) and R2(X (U-Y)) 3. If R1 is not in BCNF start the algorithm with R1 in input 4. If R2 is not in BCNF start the algorithm with R2 in input 58 CSC343 Functional Dependencies Decomposition and Normal Form Example 1 R(BOSQID), Pick B = IS Q, B O, I B, S D Candidate Key: IS O: R1 (BO) R2 (BSQID) Now we decompose R2 using S D R3 (SD) R4 (BSQI) Now we decompose R4 using I B R5(IB) R6(ISQ) 59 CSC343 Functional Dependencies Decomposition and Normal Form Set of relational schema which are in BCNF from R and R1 (BO) R3 (SD) R5 (IB) R6 (ISQ) = B O = S D =I : B = IS Q 60 CSC343 Functional Dependencies Decomposition and Normal Form Example 2 R(ABCDEF), =A R1(ABC) = R2(ADF) = R3(DE) = BC, D A Candidate Key: DE BC D AF AF 61 CSC343 Functional Dependencies Decomposition and Normal Form Example 3 R(ABC), R1(AC) R@(DE) = AB = C C, C A Candidate Key: AB,CB A = 62 CSC343 Functional Dependencies Decomposition and Normal Form 63 CSC343 4NF CSC343 Functional Dependencies Decomposition and Normal Form De nition Functional dependencies rule out certain tuples from appearing in a relation: if A B, then we cannot have two tuples with the same A value but different B values. Multivalued dependencies do not rule out of the existence of certain tuples. Instead they require that other tuples of a certain form be present in the relation. Let R(U, ) be a relational schema and A,B U. The multivalued dependency: holds in R if any legal relation r(R), for all pairs of tuples and in r such that [A] = [A], there exist tuples and in r such that: [A] = [A] = [A] = [A] [B] = [B] [R-B] = [R-B] [B] = [B] [R-B] = [R-B] 65 CSC343 Functional Dependencies Decomposition and Normal Form Example name Tom Tom Tom Tom address North Rd. Oak St. North Rd. Oak St. car Toyota Honda Honda Toyota 66 CSC343 Functional Dependencies Decomposition and Normal Form Example name C. Fisher C. Fisher C. Fisher C. Fisher C. Fisher C. Fisher street 123 Maple St. 5 Locust Ln. 123 Maple St. 5 Locust Ln. 123 Maple St. 5 Locust Ln. city Hollywood Malibu Hollywood Malibu Hollywood Malibu title Star Wars Star Wars Empire Strike Back Empire Strike Back Return of the Jedi Return of the Jedi year 1977 1977 1980 1980 1983 1983 67 CSC343 Functional Dependencies Decomposition and Normal Form Theory of Multivalued Dependencies We will need to compute all the multivalued dependencies that are logically implied by a given set of multivalued dependencies. Let D denote a set of functional and multivalued dependencies. The closure of D is the set of all functional and multivalued dependencies logically implied by D. We can compute from D using the formal de nitions, but it is easier to use a set of inference rules. 68 CSC343 Functional Dependencies Decomposition and Normal Form Theory of Multivalued Dependencies The following set of inference rules is sound and complete. The rst three rules are Armstrong s axioms. Re exivity rule: if X is a set of attributes and Y X, then holds. Augmentation rule: . Transitivity rule: if holds, and holds, then holds. Complementation rule: if holds, then holds. Multivalued augmentation rule: if holds, and and , then holds. Multivalued transitivity rule: if holds, and holds, then holds. Replication rule: if Coalescence rule: if and holds, then . holds, and , then holds. , and there is a T such that and 69 CSC343 Functional Dependencies Decomposition and Normal Form An example of multivalued transitivity rule is as follows. If we have R(A,B,C,D) and and . Thus we have , where An example of coalescance rule is as follows. If we have R(A,B,C,D) and , then we have A MVD and for a relation R is nontrivial if: 1. None of the Y s is among the A s. 2. Not all the attributes of R are among the A s and B s. 70 CSC343 Functional Dependencies Decomposition and Normal Form Other Axioms Multivalued Union rule: if holds and holds, then holds. Intersection rule: If holds and holds, then holds. Difference rule: If holds, and , then holds and holds. 71 CSC343 Functional Dependencies Decomposition and Normal Form Fourth Normal Form (4NF) We saw that a BCNF schema was not an ideal design as it suffered from repetition of information. We can use the given multivalued dependencies to improve the database design by decomposing it into fourth normal form. A relation schema R is in 4NF with respect to a set D of functional and multivalued dependencies if for all multivalued dependencies in and : of the form , where is a non trivial multivalued dependency; and X is a superkey for schema R. A database design is in 4NF if each member of the set of relation schemas is in 4NF. The de nition of 4NF differs from the BCNF de nition only in the use of multivalued dependencies: Every 4NF schema is also in BCNF. 72 CSC343 Functional Dependencies Decomposition and Normal Form Summarize Property Eliminates redundancy due to FD s Eliminates redundancy due to MVD s hline Preserves FD s Preserves MVD s 3NF Most No Yes Maybe BCNF Yes No Maybe Maybe 4NF Yes Yes Maybe Maybe 73 CSC343

Formatting page ...

ajaykumar3488 chat

Horizontal lines at:
Guest Horizontal lines at:
AutoRM Data:
Box geometries: