Exam (elaborations) TEST BANK FOR DATABASE SYSTEMS AN APPLICATION-ORIENTED APPROACH 2ND EDITION BY Michael Kifer, Arthur Bernstein, Philip M. Lewis (SOLUTION MANUAL)

Exam (elaborations) TEST BANK FOR DATABASE SYSTEMS AN APPLICATION-ORIENTED APPROACH 2ND EDITION BY Michael Kifer, Arthur Bernstein, Philip M. Lewis (SOLUTION MANUAL) Contents PART ONE Introduction 1 1 Overview of Databases and Transactions 3 Exercises 3 2 The Big Picture 5 Exercises 5 PART TWO Database Management 13 3 The Relational Data Model 15 Exercises 15 4 Conceptual Modeling of Databases with Entity-Relationship Diagrams and the Unified Modeling Language 25 Exercises 25 5 Relational Algebra and SQL 39 Exercises 39 6 Database Design with the Relational Normalization Theory 57 Exercises 57 7 Triggers and Active Databases 71 Exercises 71 iv Contents 8 Using SQL in an Application 77 Exercises 77 PART THREE Optimizing DBMS Performance 81 9 Physical Data Organization and Indexing 83 Exercises 83 10 The Basics of Query Processing 95 Exercises 95 11 An Overview of Query Optimization 103 Exercises 103 12 Database Tuning 115 Exercises 115 PART FOUR Advanced Topics in Databases 125 13 Relational Calculus, Visual Query Languages, and Deductive Databases 127 Exercises 127 14 Object Databases 145 Exercises 145 15 XML and Web Data 163 Exercises 163 16 Distributed Databases 201 Exercises 201 17 OLAP and Data Mining 207 Exercises 207 Contents v PART FIVE Transaction Processing 217 18 ACID Properties of Transactions 219 Exercises 219 19 Models of Transactions 225 Exercises 225 20 Implementing Isolation 231 Exercises 231 21 Isolation in Relational Databases 247 Exercises 247 22 Atomicity and Durability 261 Exercises 261 PART SIX Distributed Applications and the Web 267 23 Architecture of Transaction Processing Systems 269 Exercises 269 24 Implementing Distributed Transactions 275 Exercises 275 25 Web Services 285 Exercises 285 26 Security and Electronic Commerce 301 Exercises 301 A An Overview of Transaction Processing A-1 Exercises A-1 vi Contents B Requirements and Specifications B-1 Exercises B-1 C Design, Coding, and Testing C-1 Exercises C-1 PART ONE Introduction 1 Overview of Databases and Transactions EXERCISES This chapter has no exercises. 2 The Big Picture EXERCISES 2.1 Design the following two tables (in addition to that in Figure 2.1) that might be used in the Student Registration System. Note that the same student Id might appear in many rows of each of these tables. a. A table implementing the relation CoursesRegisteredFor, relating a student’s Id and the identifying numbers of the courses for which she is registered Solution: Id CrsCode CSE515 CSE505 CSE532 CSE532 CSE541 CSE504 CSE504 CSE515 CSE505 b. A table implementing the relation CoursesTaken, relating a student’s Id, the identifying numbers of the courses he has taken, and the grade received in each course Solution: Id CrsCode Grade CSE501 A 6 CHAPTER 2 The Big Picture CSE533 B+ CSE505 A- CSE541 C CSE533 B- CSE515 B+ CSE505 A CSE532 B+ Specify the predicate corresponding to each of these tables. Solution: For the first table: Student X is registered for Course Y For the second table: Student X has taken Course Y and gotten Grade Z 2.2 Write an SQL statement that a. Returns the Ids of all seniors in the table Student Solution: SELECT S.Id FROM Student WHERE S.Status = ’senior’ b. Deletes all seniors from Student Solution: DELETE FROM Student S WHERE S.Status = ’senior’ c. Promotes all juniors in the table Student to seniors Solution: UPDATE Student S SET S.Status = ’senior’ WHERE S.Status = ’junior’ 2.3 Write an SQL statement that creates the Transcript table. Solution: Exercises 7 CREATE TABLE Transcript ( StudId INTEGER, CrsCode CHAR(6), Semester CHAR(6), Grade CHAR(1), PRIMARY KEY (StudId, CrsCode, Semester) ) 2.4 Using the Transcript table, write an SQL statement that a. Deregisters the student with Id = from the course CS305 for the fall of 2001 Solution: DELETE FROM Transcript WHERE StudId = ’’ AND CrsCode = ’CS305’ AND Semester = ’F2001’ b. Changes to an A the grade assigned to the student with Id = for the course CS305 taken in the fall of 2000 Solution: UPDATE Transcript SET Grade = ’A’ WHERE StudId = ’’ AND CrsCode = ’CS305’ AND Semester =’F2000’ c. Returns the Id of all students who took CS305 in the fall of 2000 Solution: SELECT StudId FROM Transcript WHERE CrsCode = ’CS305’ AND Semester = ’F2000’
2.5 Given the relation Married that consists of tuples of the form
a, b, w here a is the husband and b is the wife, the relation Brother that has tuples of the form
c, d, where c is the brother of d, and the relation Sibling, which has tuples of the form
e, f , w here e and f are siblings, use SQL to define the relation Brother-In-Law, where tuples have the form
x, y with x being the brother-in-lawof y. (Hint: This query can be represented as a union of three separate SQL queries. SQL provides the operator UNION to achieve this effect.) 8 CHAPTER 2 The Big Picture Solution: The first SQL query, below, describes the situation where someone is the brother of the wife and hence the brother-in-law of the husband. The second disjunct describes the situation where someone is the brother of the husband and hence the brother-in-law of the wife. The third disjunct describes the situation where, someone is the husband and hence the brother-in-lawof all the wife’s brothers and sisters. (SELECT B1, M1 FROM Married, Brother WHERE B2 = M2) UNION (SELECT B1, M2 FROM Married, Brother WHERE B2 = M1) UNION (SELECT M1, S2 FROM Married, Sibling WHERE S1 = M2) 2.6 Write an SQL statement that returns the names (not the Ids) of all students who received an A in CS305 in the fall of 2000. Solution: SELECT Name FROM Student, Transcript WHERE StudId = Id AND Grade = ’A’ AND CrsCode = ’CS305’ AND Semester = ’F2000’ 2.7 State whether or not each of the following statements could be an integrity constraint of a checking account database for a banking application. Give reasons for your answers. a. The value stored in the balance column of an account is greater than or equal to $0. Solution: Yes. It describes a constraint on a snapshot of the database. b. The value stored in the balance column of an account is greater than it was last week at this time. Solution: No. It does not describe a snapshot. c. The value stored in the balance column of an account is $128.32. Solution: No. The balance will change. Exercises 9 d. The value stored in the balance column of an account is a decimal number with two digits following the decimal point. Solution: Yes. It is a domain constraint. e. The social_security_number column of an account is defined and contains a nine-digit number. Solution: Yes. It is a domain constraint. f. The value stored in the check_credit_in_use column of an account is less than or equal to the value stored in the total_approved_check_credit column. (These columns have their obvious meanings.) Solution: Yes. It describes a constraint on a snapshot 2.8 State five integrity constraints, other than those given in the text, for the database in the Student Registration System. Solution: 1. The courses for which the student enrolled (registered) must be offered this semester(next semester). 2. An instructor cannot be assigned to two courses taught at the same time in the same semester. 3. Two courses are not taught in the same room at the same time in a given semester. 4. No student must be registered (enrolled) in two courses taught at the same hour. 5. No studentmust be allowed to register for more than 20 credits in a given semester. 6. The room assigned to a course must have at least as many seats as the maximum allowed enrollment for the course. 2.9 Give an example in the Student Registration System where the database satisfies the integrity constraints IC0–IC3 but its state does not reflect the state of the real world. Solution: We register a student, but do not change the database. 2.10 State five (possible) integrity constraints for the database in an airline reservation system. Solution: 1. The flight for which a person makes a reservation must be on the schedule. 2. The number of reservations on each flight must not exceed the number of seats on the plane. 3. A passenger cannot order two meals 4. The number of meals ordered must equal the number of passengers who ordered meals 5. The same seat on the plane must not be reserved for two passengers. 10 CHAPTER 2 The Big Picture 2.11 A reservation transaction in an airline reservation system makes a reservation on a flight, reserves a seat on the plane, issues a ticket, and debits the appropriate credit card account. Assume that one of the integrity constraints of the reservation database is that the number of reservations on each flight does not exceed the number of seats on the plane. (Of course, many airlines purposely over-book and so do not use this integrity constraint.) Explain howt ransactions running on this system might violate a. Atomicity Solution: A passenger makes a reservation and reserves a seat. The transaction records the reservation, but the system crashes before it records the seat reservation. b. Consistency Solution: Flight is over-booked (More reservations are made than there are seats on the airplane.) c. Isolation Solution: The same seat is given to two people because of a particular interleaving of the reservation transactions. d. Durability Solution: A reservation is made; the system crashes; the system forgets the reservation 2.12 Describe informally in what ways the following events differ from or are similar to transactions with respect to atomicity and durability. a. A telephone call from a pay phone (Consider line busy, no answer, and wrong number situations. When does this transaction “commit?”) Solution: Commit occurs when caller hangs up. Billing information is durable. For line busy or no answer, the transaction aborts. For a wrong number the transaction commits, but later is compensated for by returning the callers money (Read about compensation later in the book,) b. A wedding ceremony (Suppose that the groom refuses to say “I do.” When does this transaction “commit?”) Solution: Commit occurs when license is signed. Marriage is durable (hopefully). c. The purchase of a house (Suppose that, after a purchase agreement is signed, the buyer is unable to obtain a mortgage. Suppose that the buyer backs out during the closing. Suppose that two years later the buyer does not make the mortgage payments and the bank forecloses.) Solution: Various levels of commit; Every time someone signs something. For example, when purchaser makes an offer to purchase and includes a deposit, he is committed to Exercises 11 either purchase the house at that price (assuming he is approved for the mortgage) or forfeit the deposit. If he is not approved for the mortgage, he is no longer committed to purchase the house and gets his deposit back. If he does not pay his mortgage payment the transaction is compensated for when the bank forecloses. d. A baseball game (Suppose that it rains.) Solution: Commit occurs after game is official. If it rains before the game is official, the game is aborted. 2.13 Assume that, in addition to storing the grade a student has received in every course he has completed, the system stores the student’s cumulative GPA. Describe an integrity constraint that relates this information. Describe howthe constraintwould be violated if the transaction that records a newgrade were not atomic. Solution: The integrity constraint is that the GPA stored in the database is the GPA of the course grades stored. That constraint could be violated if a transaction updated a course grade and aborted before it could update the GPA. 2.14 Explain howa lost update could occur if, under the circumstances of the previous problem, two transactions that were recording grades for a particular student (in different courses) were run concurrently. Solution: The first transaction reads the course grades before the second updated its grade and then updates the GPA. The second transaction reads the course grades before the first updated its grade and then updates the GPA. The first update of the GPA is lost and the final one is incorrect. PART TWO Database Management 3 The Relational Data Model EXERCISES 3.1 Define data atomicity as it relates to the definition of relational databases. Contrast data atomicity with transaction atomicity as used in a transaction processing system. Solution: These concepts are not related. Data atomicity means that the relational model does not specify any means for looking into the internal structure of the values, so they appear as indivisible to the relational operators. Transaction atomicity means that the system must ensure that either the transaction runs to completion or, if it does not complete, it has no effect at all. It does not mean that the transaction must be indivisible, but it is a type of all-or-none execution. 3.2 Prove that every relation has a key. Solution: Since relations are sets and, thus, cannot have identical elements, the set of all attributes in a relation must be a superkey. If this is not a minimal superkey, some strict subset of it must also be a superkey. Since the number of the attributes in every relation is finite, we will eventually get a minimal superkey, i.e., a key of the relation. 3.3 Define the following concepts: a. Key Solution: A key, key(¯K ), associated with a relation schema, S, is a minimal (by inclusion) subset ¯K of attributes of S with the following property: An instance s of S satisfies key(¯K ) if it does not contain a pair of distinct tuples whose values agree on all of the attributes in ¯K . b. Candidate key Solution: Every key of a relation is also called a candidate key for that relation c. Primary key Solution: One of the keys of a relation is designated as primary key. 16 CHAPTER 3 The Relational Data Model d. Superkey Solution: A superkey is a set of attributes in a relation that contains a key of that relation 3.4 Define a. Integrity constraint Solution: An integrity constraint is an application-specific restriction on the tuples in one or several relations. b. Static, as compared with dynamic, integrity constraint Solution: Static integrity constraints restrict the legal instances of a database. Examples of static ICs are domain constraints, key constraints, foreign-key constraints, etc. Dynamic integrity constraints restrict the evolution (over time) of legal instances of a database, for instance, a salary increase should not exceed 5%. c. Referential integrity Solution: A referential integrity constraint is a requirement that the referenced tuple must exist. d. Reactive constraint Solution: A reactive constraint is a static constraint with a trigger attached. The trigger specifies what to do if the constraint is violated by an update. e. Inclusion dependency Solution: An inclusion dependency is a statement “S(¯F ) references T(¯K )”, which states that for every tuple s ∈ s, there is a tuple t ∈ t that has the same values over the attributes in ¯K as does s over the corresponding attributes in ¯F. f. Foreign-key constraint Solution: A foreign-key constraint is an inclusion dependency in which the set of attributes referred to is a candidate key in the referenced relation. 3.5 Looking at the data that happens to be stored in the tables for a particular application at some particular time, explain whether or not you can tell a. What the key constraints for the tables are Solution: No, in one particular instance of the table, a particular attribute might uniquely identify the rows (and thus appear to be a key), but in other instances it might not. b. Whether or not a particular attribute forms a key for a particular table Exercises 17 Solution: You cannot tell whether a particular attribute is a key (for the reasons mentioned in (a)), but you can sometimes tell that a particular attribute cannot form a key by itself (if two distinct rows have the same value over that attribute). c. What the integrity constraints for the application are Solution: No. Again, one cannot determine integrity constraints just by looking at database instances. d.Whether or not a particular set of integrity constraints is satisfied Solution: Yes. Simply check if every constraint in the set is satisfied in the given instance. 3.6 We state in the book that once constraints have been specified in the schema, it is the responsibility of the DBMS to make sure that they are not violated by the execution of any transactions. SQL allows the application to control when each constraint is checked. If a constraint is in immediate mode, it is checked immediately after the execution of any SQL statement in a transaction that might make it false. If it is in deferred mode, it is not checked until the transaction requests to commit. Give an example where it is necessary for a constraint to be in deferred mode. Solution: Suppose the constraint states that the value of one attribute, A, is the sum of the values of two other attributes, B and C. If we want to increment the value of B, w e must also increment the value of A in the same transaction. But no matter in what order we do the incrementing, the constraint will be false between the two statements that do the incrementing, and if we used immediate mode checking, the transaction would abort when the first increment statement was attempted. 3.7 Suppose we do not require that all attributes in the primary key are non-null and instead request that, in every tuple, at least one key (primary or candidate) does not have nulls in it. (Tuples can have nulls in other places and the non-null key can be different for different tuples.) Give an example of a relational instance that has two distinct tuples that might become one once the values for all nulls become known (that is, are replaced with real values). Explain why this is not possible when one key (such as the primary key) is designated to be non-null for all tuples in the relation. Solution: Let the relation have attributes A and B, each of which is a key. The tuples can be
a, NULL and
NULL, b. If the first NULL becomes b and the second a then these tuples become the same. If all tuples are non-NULL over the same key, then they must differ over that key somewhere and thus they cannot become the same regardless of what is substituted for nulls in other places. 3.8 Use SQL DDL to specify the schema of the Student Registration System fragment shown in Figure 3.4, including the constraints in Figure 3.6 and Example 3.2.2. Specify SQL domains for attributes with small numbers of values, such as DeptId and Grade. 18 CHAPTER 3 The Relational Data Model Solution: CREATE TABLE Student ( Id INTEGER, Name CHAR(20), Address CHAR(50), Status CHAR(10) PRIMARY KEY (Id) ) CREATE TABLE Professor ( ProfId INTEGER, Name CHAR(20), DeptId Departments,