Chris Pollett >
Old Classes
> |
HW5 Solutions PageNo solutions will be given for the Access problem as it is relatively easy. Below are the solutions to the book problems: 14.18 (a) 1. W ->Y (given) 2. X-> Z (given) Goal to prove: WX -> Y Follows from (1) by IR1 as WX contains W (b) 1. X ->Y (given) Goal to prove: X-> Z 2. Y is subset of Z (given) 3. Y ->Z (using IR1 on 2) 4. X ->Z (using IR3 on 1 & 3). (c) 1. X -> Y (given) Goal to prove: X->Z 2. X -> W (given) 3. WY ->Z (given) 4. X -> XY (using IR2 on 1 by augmenting with X ;notice that XX=X) 5. XY->WY (using IR2 on 2 by augmenting with Y) 6. X ->WY (using IR3 on 4 and 5) 7. X-> Z (using IR3 on 3 and 6) (d)Want to disprove: {XY->Z, Y->W} |= XW->Z Counterexample model X Y Z W 1 1 1 1 1 2 2 1 (e)Want to disprove: {X->Z, Y->Z} |= X->Y Counterexample model X Y Z 1 1 1 1 2 1 (f) 1. X -> Y (given) Goal to prove: X->Z 2. XY -> Z (given) 3. X -> XY (using IR2 on 1 by augmenting with X; notice that XX= X) 4. X -> Z (using IR3 on 2 and 3) (g) 1. X->Y (given) Goal to prove: XZ ->YW 2. Z->W (given) 3. XZ->YZ (using IR2 on 1 by augmenting with Z) 4. YZ ->YW (using IR2 on 2 by augmenting with Y) 5. XZ->YW (using IR3 on 3 and 4) (h) Want to disprove: {XY -> Z, Z->X} |= Z-> Y Counterexample model X Y Z 1 1 1 1 2 1 (i) 1. X -> Y (given) Want to prove: X->YZ 2. Y -> Z (given) 3. X -> Z (using IR3 on 1 & 2) 4. X -> XY (using IR2 on 1 by augmenting with X; notice that XX=X) 5. XY -> YZ (using IR2 on 3 by augmenting with Y) 6. X-> YZ (using IR3 on 4 & 5) (j) Want to disprove: {XY->Z, Z->W} |= X->W X Y Z W 1 1 1 1 1 2 2 2 14.20 Calculate {SSN}^+ and {DNUMBER}^+ with respect to the dependencies G={ (1) SSN->{ENAME, BDATE ADDRESS, DNUMBER}, (2) DNUMBER->{DNAME, DMGRSSN}} {SSN}^+={SSN, ENAME, BDATE, ADDRESS, DNUMBER, DNAME,DMGRSSN} How got: 1st five attributes gotten from rule (1). As this fixes DNUMBER, can apply (2) to derive last two attributes. {DNUMBER }^+ = {DNUMBER, DNAME, DMGRSSN} How got: only rule (2)can be applied. 15.27 (14.29 part) Want to find a key for R(A,B,C,D,E) given the dependencies: {AB->C, CD->E, DE->B } using the algorithm from book. Initially, set: K={A,B,C,D,E} Then compute: K' := {K-A}^+ = {B,C,D,E} As can't rederive A, we leave K unchanged. Next delete B: K' := {K-B}^+ = {A,B,C,D,E} As we can derive all the attributes back, set K := K' Next delete C, so K' := {A,D,E}^+ ={A,B,C,D,E} As we can derive all the attributes back, set K := K' Next delete D, so K' := {A,E}^+ ={A,E} As can't rederive all the attributes, we leave K unchanged. Finally, deleting E we get: K' := {A,D}^+ = {A,D} As can't rederive all the attributes, we leave K unchanged So our key is {A,D,E}. Given this key want to decompose R into 3NF using algorithm 15.4. 1st we find a minimal cover for the set of dependencies F:={ AB->C, CD -> E, DE-> B} using algorithm 14.2. Initially, set G := F. Each dependency in F only has one thing of the right hand side so we next try to delete attributes from the right hand side of rules. We check conditions like whether: {A->C, CD->E, DE -> b} ^+ =? F^+ This doesn't hold as A^+ with respect to F doesn't contain C. It turns out we can't delete any attributes from any of the rules in F and get an equivalent set of rules. Next we check if it's possible to delete any rules. Again, we won't be able to so a minimal cover is what we started with in this case: F:={ AB->C, CD->E, DE->B} Continuing with step (2) of the decomposition algorithm, we create the tables: R1 := ABC R2 := CDE R3 := DEB None of these contains a key of R, so we add the additonal table R4 := ADE and our final decomposition is (R1,R2,R3,R4). (14.30 part) Here R is {CourseNo, SecNo, OfferingDept, CreditHours, CourseLevel, InstructorSSN, Semester, Year, Days_Hours, RoomNo, NoOfStudents} Our set of functional dependencies F this time is: (1) CourseNo -> {OfferingDept, CreditHours, CourseLevel} (2) {CourseNo, SecNo, Semester, Year} -> {Days_Hours, RoomNo, NoOfStudents, InstructorSSN} (3) {RoomNo, Days_Hours, Semester, Year} -> {InstructorSSN, CourseNo, SecNo} We first apply the algorithm to find a key. We set K := R at first and proceed through the attributes left to right. By (3) we will be able to delete CourseNo and SecNo. Then by (3) and (1) we will be able to delete OfferingDept, CreditHours and CourseLevel. Next by (3) again we get rid of InstructorSSN. The next four attributes we won't be able to delete but by (3) and (2) we can get rid of NoOfStudents. Thus, our final key will be: {RoomNo, Days_Hours, Semester, Year}. Now we want to decompose R into 3NF tables using the algorithm from the book. We first need to compute a minimal cover G of F. In the first step of the algorithm for the minimal cover, we make it so each rule has only one attribute on the right-hand-side: (1) CourseNo -> OfferingDept (2) CourseNo -> CreditHours (3) CourseNo -> CourseLevel (4) CourseNo,SecNo,Semester,Year -> Days_Hours (5) CourseNo,SecNo,Semester,Year -> RoomNo (6) CourseNo,SecNo,Semester,Year -> NoOfStudents (7) CourseNo,SecNo,Semester,Year -> InstructorSSN (8) RoomNo,Days_Hours,Semester,Year -> InstructorSSN (9) RoomNo,Days_Hours,Semester,Year -> CourseNo (10) RoomNo,Days_Hours,Semester,Year -> SecNo We next try to delete attributes from the left hand sides of each rule. As there is only one attribute on the left-hand side of the first three rules above we can bypass these rules. It turns out for the remaining rules one also cannot delete attributes from the left-hand-sides and get an equivalent set of rules. Next we try to delete FDs, going down from (1) to (10) and seeing if we can get a equivalent set of FDs. FD (7) can be deleted in this manner since it follows from FD (4), (5), (8). Thus, our minimal cover will be: (1) CourseNo -> OfferingDept (2) CourseNo -> CreditHours (3) CourseNo -> CourseLevel (4) CourseNo,SecNo,Semester,Year -> Days_Hours (5) CourseNo,SecNo,Semester,Year -> RoomNo (6) CourseNo,SecNo,Semester,Year -> NoOfStudents (7) RoomNo,Days_Hours,Semester,Year -> InstructorSSN (8) RoomNo,Days_Hours,Semester,Year -> CourseNo (9) RoomNo,Days_Hours,Semester,Year -> SecNo Continuing with the 3NF algorithm, for each distinct LHS of a rule we make a table with those attributes unioned with the RHS of the rules it is in. This gives the tables: R1 := {CourseNo, OfferingDept, CreditHours, CourseLevel} R2 := {CourseNo, SecNo, Semester, Year, Days_Hours, RoomNo, NoOfStudents} R3 := {RoomNo, Days_Hours, Semester, Year, InstructorSSN, CourseNo, SecNo} Notice R3 contains our key. So (R1, R2, R3) will be the final decomposition. Recall for the JDBC and PL/SQL assignments we said in class could restrict to one parent. The grader suggested RC's solution (Good work RC) to HW5 was one of the better ones, so I am posting it as is (since I am time-pressed at the end of this semester). Caveat emptor. --PL/SQL -- create or replace parent table where y is the parent of x DROP TABLE PARENT CASCADE CONSTRAINTS; CREATE TABLE PARENT ( Y VARCHAR2 NOT NULL, X VARCHAR2 NOT NULL); -- insert 100 tuples into PARENT table INSERT INTO PARENT ("Maria", "Teresa"); -- start new family INSERT INTO PARENT ("Maria", "Kazik"); INSERT INTO PARENT ("Maria", "Halina"); INSERT INTO PARENT ("Maria", "Tadeusz"); INSERT INTO PARENT ("Teresa", "Kris"); INSERT INTO PARENT ("Teresa", "Jola"); INSERT INTO PARENT ("Halina", "Darek"); INSERT INTO PARENT ("Kazik", "Marek"); INSERT INTO PARENT ("Kazik", "Beata"); INSERT INTO PARENT ("Tadeusz", "Monika"); INSERT INTO PARENT ("Taduesz", "Maciek"); INSERT INTO PARENT ("Kris", "Jessica"); INSERT INTO PARENT ("Kris", "Kristin"); INSERT INTO PARENT ("Jola", "Natalie"); INSERT INTO PARENT ("Anna", "John"); -- start new family INSERT INTO PARENT ("Anna", "Courtney"); INSERT INTO PARENT ("John", "Geneen"); INSERT INTO PARENT ("Geneen", "Sebastian"); INSERT INTO PARENT ("Geneen", "Terry"); INSERT INTO PARENT ("Geneen", "Roger"); INSERT INTO PARENT ("Courtney", "Christiana"); INSERT INTO PARENT ("Vanessa", "Alexandra"); -- start new family INSERT INTO PARENT ("Vanessa", "Dylan"); INSERT INTO PARENT ("Alexandra", "Hannah"); INSERT INTO PARENT ("Alexandra", "Brianna"); INSERT INTO PARENT ("Hannah", "Adolf"); INSERT INTO PARENT ("Hannah", "Harry"); INSERT INTO PARENT ("Brianna", "Florence"); INSERT INTO PARENT ("Brianna", "Ruth"); INSERT INTO PARENT ("Florence", "William"); INSERT INTO PARENT ("Dylan", "Chloe"); INSERT INTO PARENT ("Dylan", "Jasmine"); INSERT INTO PARENT ("Jasmine", "Nick"); INSERT INTO PARENT ("Jasmine", "Jacob"); INSERT INTO PARENT ("Nick", "George"); INSERT INTO PARENT ("Nick", "Henry"); INSERT INTO PARENT ("Jacob", "Bertha"); INSERT INTO PARENT ("Ewa", "Michal"); -- start new family INSERT INTO PARENT ("Ewa", "Caroline"); INSERT INTO PARENT ("Michal", "Agnieszka"); INSERT INTO PARENT ("Michal", "Marcin"); INSERT INTO PARENT ("Caroline", "Paul"); INSERT INTO PARENT ("Larry", "Diane"); -- start new family INSERT INTO PARENT ("Larry", "Shirley"); INSERT INTO PARENT ("Diane", "Pamela"); INSERT INTO PARENT ("Diane", "Jerry"); INSERT INTO PARENT ("Pamela", "Steven"); INSERT INTO PARENT ("Pamela", "Laura"); INSERT INTO PARENT ("Steven", "Gary"); INSERT INTO PARENT ("Steven", "Lawrence"); INSERT INTO PARENT ("Shirley", "Kathy"); INSERT INTO PARENT ("Shirley", "Martha"); INSERT INTO PARENT ("Kathy", "Gloria"); INSERT INTO PARENT ("Kathy", "Carolyn"); INSERT INTO PARENT ("Gloria", "Jay"); INSERT INTO PARENT ("Carolyn", "Virginia"); INSERT INTO PARENT ("Carolyn", "Perry"); INSERT INTO PARENT ("Martha", "Wayne"); INSERT INTO PARENT ("Johann", "Peter"); -- start new family INSERT INTO PARENT ("Peter", "Darius"); INSERT INTO PARENT ("Peter", "Sylvia"); INSERT INTO PARENT ("Rudolf", "Damian"); INSERT INTO PARENT ("Rudolf", "Kristian"); INSERT INTO PARENT ("Hans", "Kurt"); INSERT INTO PARENT ("Hans", "Rudolf"); INSERT INTO PARENT ("Emily", "Sarah"); -- start new family INSERT INTO PARENT ("Emily", "Jacob"); INSERT INTO PARENT ("Emily", "Matthew"); INSERT INTO PARENT ("Sarah", "Sydney"); INSERT INTO PARENT ("Sarah", "Dalton"); INSERT INTO PARENT ("Jacob", "Alexis"); INSERT INTO PARENT ("Jacob", "Nicole"); INSERT INTO PARENT ("Jacob", "Jennifer"); INSERT INTO PARENT ("Alexis", "Sophia"); INSERT INTO PARENT ("Jennifer", "Jack"); INSERT INTO PARENT ("Jennifer", "Bill"); INSERT INTO PARENT ("Jack", "Erica"); INSERT INTO PARENT ("Jack", "Lindsay"); INSERT INTO PARENT ("Matthew", "Andrew"); INSERT INTO PARENT ("Matthew", "Anthony"); INSERT INTO PARENT ("Andrew", "Kyla"); INSERT INTO PARENT ("Andrew", "Olivia"); INSERT INTO PARENT ("Kyla", "Madeline"); INSERT INTO PARENT ("Kyla", "Autumn"); INSERT INTO PARENT ("Olivia", "David"); INSERT INTO PARENT ("Anthony", "Charles"); INSERT INTO PARENT ("Anthony", "William"); INSERT INTO PARENT ("William", "Colin"); INSERT INTO PARENT ("William", "Alex"); INSERT INTO PARENT ("Alex", "Meilissa"); INSERT INTO PARENT ("Alex", "Dominica"); INSERT INTO PARENT ("Debbie", "Julia"); -- start new family INSERT INTO PARENT ("Debbie", "Thomas"); INSERT INTO PARENT ("Debbie", "Joe"); INSERT INTO PARENT ("Thomas", "Bob"); INSERT INTO PARENT ("Thomas", "Dann"); INSERT INTO PARENT ("Julia", "Catherine"); INSERT INTO PARENT ("Julia", "Michael"); INSERT INTO PARENT ("Joe", "Christopher"); INSERT INTO PARENT ("Bob", "Juan"); -- PL/SQL procedure that when given an name X returns all the Y's -- that are sorta related to X. -- By definition, Y is sorta related to X if Y is a sibling of X or -- if Y is an ancestor of X or if Y is a sibling of someone who is sorta -- related to X. Y is an ancestor of X if Y is a parent of X or if Y is -- a parent of an ancestor of X. CREATE OR REPLACE PROCEDURE kinda_related(X_PARAM in paremt.X%TYPE) AS DECLARE RELATED_TO_X PARENT.Y%TYPE; CURSOR cur(cur_rel VARCHAR2()) IS BEGIN SELECT Y INTO V_RELATED FROM PARENT WHERE X = Y; -- needs more work DBMS_OUTPUT.PUT_LINE(RELATED_TO_X); EXCEPTION WHEN OTHERS DBMS_OUTPUT.PUT_LINE("Error"); END; -- Recursion Example: Traversing Tree-Structured Data -- Consider the procedure below, which finds the staff of a given manager. -- The procedure declares two formal parameters, mgr_no and tier, which -- represent -- the manager's employee number and a tier in his or her departmental -- organization. -- Staff members reporting directly to the manager occupy the first tier. PROCEDURE find_staff (mgr_no NUMBER, tier NUMBER := 1) IS boss_name VARCHAR2(10); CURSOR c1 (boss_no NUMBER) IS SELECT empno, ename FROM emp WHERE mgr = boss_no; BEGIN /* Get manager's name. */ SELECT ename INTO boss_name FROM emp WHERE empno = mgr_no; IF tier = 1 THEN INSERT INTO staff -- single-column output table VALUES (boss_name || ' manages the staff'); END IF; /* Find staff members who report directly to manager. */ FOR ee IN c1 (mgr_no) LOOP INSERT INTO staff VALUES (boss_name || ' manages ' || ee.ename || ' on tier ' || TO_CHAR(tier)); /* Drop to next tier in organization. */ find_staff(ee.empno, tier + 1); -- recursive call END LOOP; COMMIT; END; import java.util.*; import java.io.*; import java.sql.*; /** Given a table Parent, and a name X , print out data that is sort of related to X */ class sorta_related { public static void main (String [] args) throws SQLException { try { Class.forName ("oracle.jdbc.driver.OracleDriver"); } catch (Exception ee) { System.out.println("ee"); } // set up the connection to the database Connection conn = DriverManager.getConnection( "jdbc:oracle:thin:@sigma.mathcs.sjsu.edu:1521:cs157A","student","student"); // set up a statement Statement stmt = conn.createStatement(); String childIn = args[0]; // the input. try to find its sorta_related ancestors String parent; parent = getParent(stmt, childIn); if ( parent != null) System.out.println(parent); while (parent != null) // while still more ancestors { getSiblings(stmt, parent); parent = getParent(stmt, parent); if (parent != null) System.out.println(parent); } } /** return the parent of a given child @param st the statement @param child the child whose ancestors need to be found @return the parent of a child */ static public String getParent(Statement st, String child) throws SQLException { String query1 = "select Y from Parent where Parent.X = '" + child + "'"; String pare = " "; ResultSet rset1; try { rset1 = st.executeQuery(query1); rset1.next(); pare = rset1.getString(1); return pare; } catch (SQLException e) { return null; } } /** get the children of a given parent @param st the statement @param parent the parent whose children need to be found @return nothing */ static public void getSiblings(Statement st, String parent) throws SQLException { String query = "select X from Parent where Parent.Y = '" + parent + "'"; String children; ResultSet rset2; try { rset2 = st.executeQuery(query); while (rset2.next()) { children = rset2.getString(1); System.out.println(children); } } catch (SQLException e) { System.out.println("Problem reading scales"); } } } |