## Announcements - Exam #1 this thursday during class time - Expected duration: 110 minutes - Open book and notes, nothing electronic - No new lecture exercises today - unless you really want to! --- Exam #1 Review Relational Data Model - First normal form: Each attribute should have a simple value - Basic definition of a key: A minimal set of attributes such that no two tuples can have the same values for the key - A relation can have many keys - Keys are minimal, no subset of the attributes can be a key - Example: A, BC Relational Algebra Operations A relation is a set of tuples Each relational algebra operation takes as input one or two relations (set of tuples) and produces as output a new relation (set of tuples). - Select (select_(C) R) - Project (project_(A1,..,An) (R)) - Rename ( S(A1,B1,C,D,E1) = R(A,B,C,D,E) ) - Set compatible: R and S must have the same schema - Set union: R union S (in R or S or both) - Set intersection: R intersect S (in R and S both) - Set difference: R - S (in R but not in S) - Cartesian Product and join (only works if R and S have no attributes in common) - Cartesian Product: R x S (all combination of tuples in R and S) - R join_(C) S = select_(C) (R x S) - Natural join - R * S (an equality join of the attributes in common to R and S) Relational Algebra Queries Simple join queries Simple set queries (union/intersection) Set subtraction (never did something, have all of something) Complex joins (a pair, at least two/three of something, exactly one of something, max value, etc.) (Examples come from Hw#1 in Fall 2021) (a) Return name, min and max playtime and link of all games that can be played with 4 people, came out in 2020 and were published by 'Rio Grande Games'. R = select_(4>= min_players and 4<=max_players and year=2020 and publisher='Rio Grande') (Games) Result = project_(name,playtime_min, playtime_max,link) (R) (b) Return the name and designername of games that won or were nominated for the 'Golden Geek Most Innovative Board Game' award in 2019 or 2020. R = select_((year=2019 or year=202) and awardname='GGMIBG') (awardsnominations ) R1 = project_{gameid} (R) Result = project_(name, designername) (games * R1 * gamedesigners) (c) Return the userid of all users who never reviewed a game with the 'Loose a Turn' mechanic. - all users who reviewed a game with the 'Loose a Turn' mechanic. R = select_(mechanic='Loose a Turn') (GameMechanics) R1 = Project(Userid)(R * gamereviews) - subtract from all users Result = Project(Userid)(gamereviews) - R1 (d) Return gameid of all award winner games in categories 'Exploration' and 'Adventure' that do not involve any 'Dice Rolling' mechanic. (e) Return the name, publisherof all names in the Strategycategory that won an 'SXSW'award and are either available for less than $40 in a store or can be played online. (f) Find the name, publisher of cooperative games in the 'Farming' category that are either of type 'Strategy' or have the 'Hidden Victory Points' mechanic. - type 'Strategy' (gametypes) or have the 'Hidden Victory Points' mechanic. (gamemechanics) R1 = project_(gameid) (select_(type='strategy') gametypes) R2 = project_(gameid) (select_(mechanic ='Hidden Victory Points') gamemechanics) R3 = R1 union R2 - cooperative games in the 'Farming' category R4 = games * gamecategories * R3 R5 = Select_(category='Farming' and iscooperative=True) (R4) R6 = Project_(name, publisher) (R5) ### Normalization - Definition of functional dependencies (fds) R: X->Y Given a relation R and a set F of functional dependencies: - Inference rules for fds: finding fds implied by F - Trivial: XY->X or X->X - Transitivity: X->Y, Y->Z means X->Z - Decomposition: X->YZ means X->Y and X->Z - Combining: X->Y and X->Z means X->YZ - Augmentations: X->Y means XZ->YZ - Closure of a set of fds: F+ is the set of all f.ds implied by F - F+ contains all fds in F - F+ contains all trivials fd - F+ also contains all other implications - Closure of a set of attributes: X+ F={AB->CD, AC->DE, EF->AG} AEF+ = {A,E,F,G} AEF-> AEFG Is AEF->AG in F+, Check if AG is in AEF+ - Equivalence of two sets of fds: Given a relation R and f.d. sets F1 and F2 are equivalent iff F1+ = F2+ => Check first, for all X->Y in F1 is implied by F2. <= Check second, for all X->Y in F2 is implied by F1. - Finding keys/superkeys/prime attributes given a set of fds - A superkey a set of attributes X such that X+ is all attributes in R - A key is the minimal set of attributes X such that X+ is all attributes in R - A key is a superkey that is also minimal - A prime attribute is an attribute in a key. R(A,B,C,D,E,F,G) F={AB->CD, AC->DE, EF->AG} Keys: ABF, BEF Prime attributes: A B E F Not in BCNF BF+ = {B,F} ABF+ = {A,B,C,D,E,F,G} Not in 3NF because AC->DE not trivial, AC is not a superkey and D is not a prime attribute R(A,B,C,D,E,F,G) F={AB->CDEF, ABE->G, B->B} Key: AB In BCNF, in 3NF AB->CDEF AB is a superkey ABE->G ABE is a superkey B->B trivial fd In BCNF R(A,B,C,D,E,F,G) F={AB->CDEFG, CE->A} Keys: AB, BCE (prime attributes: A,B,C,E) Not in BCNF, CE->A and CE is not a superkey In 3NF AB->CDEFG because AB is a superkey CE->A because A is a prime attribute - Checking if a relation is in BCNF - every functional dependency is either trivial or has a superkey on the left - Checking if a relation is in 3NF every functional dependency is - either trivial or has a superkey on the left or all attributes on the right are prime attributes - If a relation is in BCNF, then it is in 3NF. - lossless decompositions R1 = Project_() R R2 = Project_() R R = R1 * R2 R(A,B,C,D,E,F,G) F={AB->CD, AC->DE, EF->AG} Keys: ABF, BEF R1(A,C,D,E) R2(A,B,C) R3(A,B,F,G,H) a b1 c d e f1 g1 a b c d2 e2 f2 g2 a b c3 d3 e f g AB->CD a b1 c d e f1 g1 a b c d2 e2 f2 g2 a b c d2 e f g AC->DE a b1 c d e f1 g1 a b c d e f2 g2 a b c d2 e f g AC->DE a b1 c d e f1 g1 a b c d e f2 g2 a b c d e f g <- no subscript, then this is lossless - Finding projection of a set of fds to a decomposed relation R(A,B,C,D,E,F,G) F={AB->CD, AC->DE, EF->AG} Keys: ABF, BEF R1(A,C,D,E) All fds in F+ that involve ACDE AC+ = {A,C,D,E} AE+ = {A,E} CE+ = {C,E} ACE+ = {A,C,D,E} AC->DE R2(A,B,D,F) AB+ -> ABCDE AB->D - dependency preserving decompositions - Check if the original set of fds implied by the union of the fds found by the projection of a set of fds to a decomposed relation - Finding minimal basis/cover - 3NF Decomposition - Given Minimal fds, create a new relation for each fd - SImplify - Add one for a key if needed R(A,B,C,D,E,F,G) F={AB->CD, AC->DE, EF->AG} Keys: ABF, BEF (A,B,C,D) (A,C,D,E) (A,E,F,G) (B,E,F) - BCNF Decomposition - One functional at a time, find one that violates BCNF R(A,B,C,D,E,F,G) F={AB->CDEFG, CE->A} Keys: AB, BCE CE->A violates BCNF CE+={A,C,E} (A,C,E) {CE->A} (B,C,D,E,F,G) {BCE->DFG} F' = {CE->A, BCE->DFG} If AB->CDEFG implied by F' (no, not dependency preserving) 4NF basic idea ER Diagrams Entities: basic rules (key/simple attributes) Relationships: basic rules (what to connect to) Participation constraints Ternary (or higher order) relationhips (including checking whether they can be decomposed further) Converting basic ER diagrams to relational data model