HW5 Solutions Page

Return to homework page.

No 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");
		}
   }

}