12 Pages
Unlock Document

Electrical and Computer Engineering
ECE 356
Wojciech Golab

CS 348 Introduction to Database Systems (Fall 2012) Final Exam (Sections 001 and 003) Instructor: M. Tamer Ozsu 19 December 2012 Start: 7:30PM End: 10:00PM Duration: 150 minutes Student Id: Student Name: Instructions: 1. This is a closed book examination. No additional materials are allowed. 2. Answer all the questions. 3. Answer each question in the space provided. 4. You can use the back of the sheets for rough work. 5. The exam consists of 7 questions and 12 (twelve) pages; make sure you have all of the pages. Question Points Score 1 10 2 10 3 10 4 6 5 4 6 4 7 6 Total: 50 1 Student ID: ..............................Student Name: ................................................... Q1. (10 points) Answer the following questions with a few sentences (no longer than the allocated space). (a) What are the three major steps of the database design (data modeling) process? De▯ne each by one sentence. Solution: ▯ Conceptual modeling: The process of identifying the entities, their proper- ties, and the relationships among these entities that are part of the environ- ment that the information system models. In our case, we used E-R model for conceptual modeling. ▯ Logical modeling: The process of mapping the conceptual model to the primitives of the data model that is used. In the case of relational DBMSs, this is the process of de▯ning the relational schema. ▯ Physical modeling: The process of de▯ning the physical organization char- acteristics (e.g., indexes, ▯le structure) of the database. (b) What types of participation constraints can you have in an E-R model? De▯ne each by one sentence. Solution: Two types: 1. Total participation constraint: If entity type E1 is in total participation in relation R with entity type E2, then every entity instance of E1 has to participate via relation R to an entity instance of entity type E2. 2. Partial participation constraint: If, in the above situation, it is acceptable that some instances of E1 participate in relationship R with instances of E2,while others do not have to, then we have a partial participation con- straint. (c) Given relation R(A, B, C, D, E) where (A,B) is the key, and the functional de- pendencies (A, B) ! (C, D, E) and B ! D, is R in Boyce-Codd Normal Form (BCNF)? Justify your answer with one sentence. Solution: Relation R is not in BCNF, because D is functionally dependent on part of the key (B) and not the full key. (d) What is the main di▯erence between relational calculus and relational algebra? Solution: Relational calculus is a declarative language that requires the user to specify the predicates that need to be satis▯ed by all the tuples in the result relation. Relational algebra, on the other hand, is procedural where the user speci▯es how to execute the query by means of relational algebraic operators. (e) What is the di▯erence between logical data independence and physical data inde- pendence? CS 348 Page 2 of 12 Final Exam Student ID: ...............................Student Name: ................................................... Solution: Logical data independence refers to the immutability of the application programs and users to changes in the logical schema of the database (and vice versa) whereas the physical data independence refers to the immutability of the application programs and users to the changes in the physical schema of the database (and vice versa). (f) What is referential integrity? How do you represent it in relational model? Solution: Referential integrity refers to the relationship between two entities such that if there is a referential integrity from entity E1 to entity E2, an instance of E2 has to exist for an instance of E1 to exist. In the relational model, this is represented by foreign keys. (g) What are insertion, deletion, and update anomalies? Solution: These anomalies exist when relations are not normalized properly. In- sertion anomaly refers to the condition where it is not possible to insert into the database information about a new fact unless (a) a certain relationship is estab- lished, or (b) null values are inserted for some key attributes. Deletion anomaly occurs when the deletion of a fact from the database forces the deletion of another fact that we wish to remain in the database. Update anomaly is the case where the modi▯cation of one value in a relation cascades to modi▯cations to a number of tuples due to information repetition. (h) When writing application programs using C and embedded SQL standard, what is the role of a cursor? Solution: Cursors assist with the impedance mismatch between SQL and the host language C. SQL queries return set-oriented results, but there is no C construct to hold these results. A cursor over the result of an SQL query will return each tuple of the result one-by-one to the host C program. (i) What is the main di▯erence between discretionary access control and mandatory access control? Solution: From your book \Discretionary access control is based on the concept of rights, or privileges, and mechanism for giving users such privileges. ... Man- daroy access control is based on systemwide policies that cannot be changed by individual users." The fundamental point is that in the ▯rst case, the granting of rights to objects are at the discretion of users who already hold rights to those objects, while in the latter case, this is done systemwide. (j) What are ACID properties of transactions. Explain each by one sentence. Solution: Atomicity: All actions of a transaction are atomic and either they are all performed or none of the actions are performed. Consistency: Each transaction, when run alone, must preserve the consistency of the database. Isolation: Each transaction is isolated (protected) from the e▯ects of other con- currently running transactions. Durability: Once a transaction successfully completes (commits), its e▯ects on the database will survive any future crashes. CS 348 Page 3 of 12 Final Exam Student ID: ........................Student Name: ................................................... Q2. (10 points) You are designing a database for KW Humane Society. The result is the following set of relations where the type of each relations attribute is given following the attribute (e.g., ID: integer): Animals(ID: integer, Name: string, PrevOwner: string, DateAdmitted: date, Type: string) Adopter(SIN: integer, Name: string, Address: string, OtherAnimals: integer) Adoption(AnimalID: integer, SIN: integer, AdoptDate: date, chipNo: integer) where (a) The primary keys are underlined. (b) Animals stores information about the animals currently at the Humane Society. Each is given an ID, and their names together with the SIN of their previous owners (attribute PrevOwner), and their date of admission is recorded. Type refers to the type of animal (dog, cat, etc). (c) Adopter is the relation that holds information about animal adopters. The at- tributes are self-descriptive, except OtherAnimals which records the number of other animals that the adopter currently has at home. (d) AnimalID in Adoption refers to the ID of Animals. Similarly, SIN in Adoption refers to the SIN of Adopter. Attribute chipNo stores the number on the microchip that is implanted on the animal for tracking. Owner in Animals refers to the SIN of Adopter (in this case the previous adopter). Formulate the following queries in SQL; each one is worth 2 points: (a) Retrieve the total number of dogs that were brought to the Humane Society on 18 April 2000. Solution: SELECT COUNT(▯) FROM Animals WHERE Type = ‘ ‘ dog ’ ’ AND DateAdmitted = ‘ ‘18/04/2000 ’ ’ (b) List the name of the adopter who has adopted every type of animal. Solution: SELECT Name FROM Adopter WHERE NOT EXISTS (SELECT ▯ FROM Animals A1 WHERE NOT EXISTS CS 348 Page 4 of 12 Final Exam Student ID: ......................Student Name: ................................................... (SELECT ▯ FROM Adoption , Animals A2 WHERE AnimalID = A2. ID AND A2. Type = A1. Type AND Adoption . SIN = Adopter . SIN)) (c) For each animal type, list the animal type and total number of adoptions on 14 June 1999. Solution: SELECT Type , COUNT(▯) FROM Animals , Adoption WHERE AdoptDate = ‘ ‘14/06/1999 ’ ’ AND Animals . ID = Adoption . AnimalID GROUP BY Type ; (d) List the types of animals who have not had any adoptions. Solution: SELECT DISTINCT Type FROM Animals WHERE NOT EXISTS (SELECT ▯ FROM Adoption WHERE Adoption . AnimalID = Animals . ID) (e) For each adopter who has made at least two adoptions, list their names and addresses. Solution: SELECT Name, Address FROM Adopter , Adoption WHERE Adopter . SIN = Adoption . SIN GROUP BY Adoption . SIN HAVING COUNT(SIN) > 1; Note: Some of you were confused with the semantics of the Animals relation (did the entry for an animal get deleted from this table when they are adopted) and I think our answers during the exam did not help. So, we marked (b) and (d) lightly to account for that. Q3. (10 points) Given relation R(A, B, C, D, E, F, G) and the set of functional dependencies F=fBCD ! A, BC ! E, A ! F, F!G, C!D, A!Gg, decompose R into 3NF. Show your steps. Is this decomposition also BCNF? Why or why not? Note: This requires you to ▯rst determine the key(s) of R. CS 348 Page 5 of 12 Final Exam Student ID: ........................Student Name: ................................................... Solution: The key of this relation is (B,C). The argument is simple. BC!E C!D, by augmentation BC!DC, by decomposition BC!D BC!D and BCD!A, by pseudotransitivity BC!A BC!A and A!F, by transitivity BC!F BC!F and F!G, by transitivity BC!G Thus, BC!ADEFG and there is (are) no other attribute(s) that function- ally determine all attributes of R. Now we apply the 3NF Synthesize algorithm. Step 1. We start with result = ; Step 2. Compute minimal cover for F. 1. The right-hand sides are single attributes, so this step is not necessary. 2. Consider BCD!A (CD)+ = C,D + (BD) = B,D (BC)+ = A, B,C + Since A is in (BC) , we replace BCD!A by BC!A Now consider BC!E C+ = C,D + B = B So, nothing happens. 3. Now consider each FD: Consider A!F; A +w.r.t. G▯(AF) = fA, Gg + Consider F!G; F w.r.t. G▯(FG) = fFg Consider C!D; C + w.r.t. G▯(CD) = fCg + Consider A!G; A w.r.t. G▯(AG) = fA, F, Gg Therefore A!G is redundant. Thus, the minimal cover F = fBC!A, BC!E, A!F, F!G, C!Dg. 0 Step 3. For each X ! Y 2 F , create a relation: R1(B, C, A, E) R2(A, F) R3(F, G) R4(C, D) CS 348 Page 6 of 12 Final Exam Student ID: ..............................Student Name: ................................................... This decomposition is also in BCNF. There are a number of ways to reason about this: 1. You can do a BCNF decomposition to show that you can get a decomposition that is the same as this one. However, note that the BCNF decomposition is not unique, so you have to be careful with the particular decomposition { you may need to try a few. 2. You can show that the decomposition is lossless and has no redundancy by show- ing that elimination of any one of the decomposed relations will make it lossy. Remember that BCNF is guaranteed to be lossless, but not dependency preserv- ing while the 3NF decomposition will be lossless and dependency preserving at the cost of (potentially) adding redundancy. If you can show that there is no redundancy in the resulting decomposition, then it would
More Less

Related notes for ECE 356

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.