Introduction

1.1 List four significant differences between a file-processing system and a DBMS.

Answer: Some main differences between a database management system and a file-processing system are:

• Both systems contain a collection of data and a set of programs which access that data. A database management system coordinates both the physical and the logical access to the data, whereas a file-processing system coordinates only the physical access.

• A database management system reduces the amount of data duplication by ensuring that a physical piece of data is available to all programs authorized to have access to it, where as data written by one program in a file-processing system may not be readable by another program.

• A database management system is designed to allow flexible access to data (i.e., queries), whereas a file-processing system is designed to allow predetermined access to data (i.e., compiled programs).

• A database management system is designed to coordinate multiple users accessing the same data at the same time. A file-processing system is usually designed to allow one or more programs to access different data files at the same time. In a file-processing system, a file can be accessed by two programs concurrently only if both programs have read-only access to the file.

1.2 This chapter has described several major advantages of a database system. What are two disadvantages?

Answer: Two disadvantages associated with database systems are listed below.

a. Setup of the database system requires more knowledge, money, skills, and time.

b. The complexity of the database may result in poor performance.

1.3 Explain the difference between physical and logical data independence.

Answer:

• Physical data independence is the ability to modify the physical scheme without making it necessary to rewrite application programs. Such modifications include changing from unblocked to blocked record storage, or from sequential to random access files.

• Logical data independence is the ability to modify the conceptual scheme without making it necessary to rewrite application programs. Such a modification might be adding a field to a record; an application program’s view hides this change from the program.

1.4 List five responsibilities of a database management system. For each responsibility, explain the problems that would arise if the responsibility were not discharged.

Answer: A general purpose database manager (DBM) has five responsibilities:

a. interaction with the file manager.

b. integrity enforcement.

c. security enforcement.

d. backup and recovery.

e. concurrency control.

If these responsibilities were not met by a given DBM (and the text points out that sometimes a responsibility is omitted by design, such as concurrency control on a single-user DBM for a micro computer) the following problems can occur, respectively:

a. No DBM can do without this, if there is no file manager interaction then nothing stored in the files can be retrieved.

b. Consistency constraints may not be satisfied, account balances could go below the minimum allowed, employees could earn too much overtime (e.g., hours > 80) or, airline pilots may fly more hours than allowed by law.

c. Unauthorized users may access the database, or users authorized to access part of the database may be able to access parts of the database for which they lack authority. For example, a high school student could get access to national defense secret codes, or employees could find out what their supervisors earn.

d. Data could be lost permanently, rather than at least being available in a consistent state that existed prior to a failure.

e. Consistency constraints may be violated despite proper integrity enforcement in each transaction. For example, incorrect bank balances might be reflected due to simultaneous withdrawals and deposits, and so on.

1.5 What are five main functions of a database administrator?

Answer: Five main functions of a database administrator are:

• To create the scheme definition

• To define the storage structure and access methods

• To modify the scheme and/or physical organization when necessary

• To grant authorization for data access

• To specify integrity constraints

1.6 List seven programming languages that are procedural and two that are nonprocedural. Which group is easier to learn and use? Explain your answer.

Answer: Programming language classification:

• Procedural: C, C++, Java, Basic, FORTRAN, COBOL, Pascal

• Non-procedural: Lisp and Prolog

Note: Lisp and Prolog support some procedural constructs, but the core of both these languages is non-procedural.

In theory, non-procedural languages are easier to learn, because they let the programmer concentrate on what needs to be done, rather than how to do it. This is not always true in practice, especially if procedural languages are learned first.

1.7 List six major steps that you would take in setting up a database for a particular enterprise.

Answer: Six major steps in setting up a database for a particular enterprise are:

• Define the high level requirements of the enterprise (this step generates a document known as the system requirements specification.)

• Define a model containing all appropriate types of data and data relationships.

• Define the integrity constraints on the data.

• Define the physical level.

• For each known problem to be solved on a regular basis (e.g., tasks to be carried out by clerks or Web users) define a user interface to carry out the task, and write the necessary application programs to implement the user interface.

• Create/initialize the database.

1.8 Consider a two-dimensional integer array of size n × m that is to be used in your favorite programming language. Using the array as an example, illustrate the difference (a) between the three levels of data abstraction, and (b) between a schema and instances.

Answer: Let tgrid be a two-dimensional integer array of size n × m.

a. • The physical level would simply be m × n (probably consecutive) storage locations of whatever size is specified by the implementation (e.g., 32 bits each).

• The conceptual level is a grid of boxes, each possibly containing an integer, which is n boxes high by m boxes wide.

• There are 2m×n possible views. For example, a view might be the entire array, or particular row of the array, or all n rows but only columns 1 through i.

b. • Consider the following Pascal declarations:

type tgrid = array[1..n, 1..m] of integer;

var vgrid1, vgrid2 : tgrid

Then tgrid is a schema, whereas the value of variables vgrid1 and vgrid2 are instances.

• To illustrate further, consider the schema array[1..2, 1..2] of integer. Two instances of this scheme are:

17	90
412	8

1	16
7	89

Entity Relationship Model

2.1 Explain the distinctions among the terms primary key, candidate key, and superkey.

Answer: A superkey is a set of one or more attributes that, taken collectively, allows us to identify uniquely an entity in the entity set. A superkey may contain extraneous attributes. If K is a superkey, then so is any superset of K. A superkey for which no proper subset is also a superkey is called a candidate key. It is possible that several distinct sets of attributes could serve as candidate keys. The primary key is one of the candidate keys that is chosen by the database designer as the principal means of identifying entities within an entity set.

2.2 Construct an E-R diagram for a car-insurance company whose customers own one or more cars each. Each car has associated with it zero to any number of recorded accidents.

Answer:

2.3 Construct an E-R diagram for a hospital with a set of patients and a set of medical doctors. Associate with each patient a log of the various tests and examinations conducted.

Answer:

2.4 A university registrar’s office maintains data about the following entities: (a) courses, including number, title, credits, syllabus, and prerequisites; (b) course offerings, including course number, year, semester, section number, instructor(s), timings, and classroom; (c) students, including student-id, name, and program; and (d) instructors, including identification number, name, department, and title. Further, the enrollment of students in courses and grades awarded to students in each course they are enrolled for must be appropriately modeled.

Construct an E-R diagram for the registrar’s office. Document all assumptions that you make about the mapping constraints.

Answer: In the answer given here, the main entity sets are student, course, course-offering, and instructor. The entity set course-offering is a weak entity set dependent on course. The assumptions made are: a. a class meets only at one particular place and time. This E-R diagram cannot model a class meeting at different places at different times. b. There is no guarantee that the database does not have two classes meeting at the same place and time.

2.5 Consider a database used to record the marks that students get in different exams of different course offerings.

a. Construct an E-R diagram that models exams as entities, and uses a ternary relationship, for the above database.

b. Construct an alternative E-R diagram that uses only a binary relationship between students and course-offerings. Make sure that only one relationship exists between a particular student and course-offering pair, yet you can represent the marks that a student gets in different exams of a course offering.

Answer:

a)

b)

2.6 Construct appropriate tables for each of the E-R diagrams in Exercises 2.2 to 2.4.

Answer:

a. Car insurance tables:

person (driver-id, name, address)

car (license, year,model)

accident (report-number, date, location)

participated(driver-id, license, report-number, damage-amount)

b. Hospital tables:

patients (patient-id, name, insurance, date-admitted, date-checked-out)

doctors (doctor-id, name, specialization)

test (testid, testname, date, time, result)

doctor-patient (patient-id, doctor-id)

test-log (testid, patient-id) performed-by (testid, doctor-id)

c. University registrar’s tables:

student (student-id, name, program)

course (courseno, title, syllabus, credits)

course-offering (courseno, secno, year, semester, time, room)

instructor (instructor-id, name, dept, title)

enrols (student-id, courseno, secno, semester, year, grade)

teaches (courseno, secno, semester, year, instructor-id)

requires (maincourse, prerequisite)

2.7 Design an E-R diagramfor keeping track of the exploits of your favourite sports team. You should store thematches played, the scores in eachmatch, the players in each match and individual player statistics for each match. Summary statistics should be modeled as derived attributes.

Answer:

2.8 Extend the E-R diagram of the previous question to track the same information for all teams in a league.

Answer:

2.9 Explain the difference between a weak and a strong entity set.

Answer: A strong entity set has a primary key. All tuples in the set are distinguishable by that key. A weak entity set has no primary key unless attributes of the strong entity set on which it depends are included. Tuples in a weak entity set are partitioned according to their relationship with tuples in a strong entity.

2.10 We can convert any weak entity set to a strong entity set by simply adding appropriate attributes. Why, then, do we have weak entity sets?

Answer: We have weak entities for several reasons:

• We want to avoid the data duplication and consequent possible inconsistencies caused by duplicating the key of the strong entity.

• Weak entities reflect the logical structure of an entity being dependent on another entity.

• Weak entities can be deleted automatically when their strong entity is deleted.

• Weak entities can be stored physically with their strong entities.

2.11 Define the concept of aggregation. Give two examples of where this concept is useful.

Answer: Aggregation is an abstraction through which relationships are treated as higher-level entities. Thus the relationship between entities A and B is treated as if it were an entity C. Some examples of this are:

a. Employees work for projects. An employee working for a particular project uses various machinery.

b. Manufacturers have tie-ups with distributors to distribute products. Each tie-up has specified for it the set of products which are to be distributed. See

2.13 Consider an E-R diagram in which the same entity set appears several times. Why is allowing this redundancy a bad practice that one should avoid whenever possible?

Answer: By using one entity set many times we are missing relationships in the model. For example, in the E-R diagram in Figure 2.11: the students taking classes are the same students who are athletes, but this model will not show that.

2.14 Consider a university database for the scheduling of classrooms for final exams. This database could be modeled as the single entity set exam, with attributes course-name, section-number, room-number, and time. Alternatively, one or more additional entity sets could be defined, along with relationship sets to replace some of the attributes of the exam entity set, as

• course with attributes name, department, and c-number

• section with attributes s-number and enrollment, and dependent as a weak entity set on course

• room with attributes r-number, capacity, and building

a. Show an E-R diagram illustrating the use of all three additional entity sets listed.

b. Explain what application characteristics would influence a decision to include or not to include each of the additional entity sets.

Answer:

a.

b. The additional entity sets are useful if we wish to store their attributes as part of the database. For the course entity set, we have chosen to include three attributes. If only the primary key (c-number) were included, and if courses have only one section, then it would be appropriate to replace the course (and section) entity sets by an attribute (c-number) of exam. The reason it is undesirable to have multiple attributes of course as attributes of exam is that it would then be difficult to maintain data on the courses, particularly if a course has no exam or several exams. Similar remarks apply to the room entity set.

2.15 When designing an E-R diagram for a particular enterprise, you have several alternatives from which to choose.

a. What criteria should you consider in making the appropriate choice?

b. Design three alternative E-R diagrams to represent the university registrar’s office of Exercise 2.4. List the merits of each. Argue in favor of one of the alternatives.

Answer:

a. The criteria to use are intuitive design, accurate expression of the real-world concept and efficiency. A model which clearly outlines the objects and relationships in an intuitive manner is better than one which does not, because it is easier to use and easier to change. Deciding between an attribute and an entity set to represent an object, and deciding between an entity set and relationship set, influence the accuracy with which the real-world concept is expressed. If the right design choice is not made, inconsistency and/or loss of information will result. A model which can be implemented in an efficient manner is to be preferred for obvious reasons.

b. Consider three different alternatives for the problem in Exercise 2.4.

Each alternative has merits, depending on the intended use of the database. Scheme 2.13 has been seen earlier. Scheme 2.15 does not require a separate entity for prerequisites. However, it will be difficult to store all the prerequisites( being a multi-valued attribute). Scheme 2.14 treats prerequisites as well as classrooms as separate entities, making it useful for gathering data about prerequisites and room usage. Scheme 2.13 is in between the others, in that it treats prerequisites as separate entities but not classrooms. Since a registrar’s office probably has to answer general questions about the number of classes a student is taking or what are all the prerequisites of a course, or where a specific class meets, scheme 2.14 is probably the best choice.

2.16 An E-R diagram can be viewed as a graph. What do the following mean in terms of the structure of an enterprise schema?

a. The graph is disconnected.

b. The graph is acyclic.

Answer:

a. If a pair of entity sets is connected by a path in an E-R diagram, the entity sets are related, though perhaps indirectly. A disconnected graph implies that there are pairs of entity sets that are unrelated to each other. If we split the graph into connected components, we have, in effect, a separate database corresponding to each connected component.

b. As indicated in the answer to the previous part, a path in the graph between a pair of entity sets indicates a (possibly indirect) relationship between the two entity sets. If there is a cycle in the graph then every pair of entity sets on the cycle are related to each other in at least two distinct ways. If the E-R diagram is acyclic then there is a unique path between every pair of entity sets and, thus, a unique relationship between every pair of entity sets.

2.17 In Section 2.4.3, we represented a ternary relationship (Figure 2.16a) using binary relationships, as shown in Figure 2.16b. Consider the alternative shown in Figure 2.16c. Discuss the relative merits of these two alternative representations of a ternary relationship by binary relationships.

Answer: The model of Figure 2.16c will not be able to represent all ternary relationships. Consider the ABC relationship set below.

If ABC is broken into three relationships sets AB, BC and AC, the three will imply that the relation (4, 2, 3) is a part of ABC.

2.18 Consider the representation of a ternary relationship using binary relationships as described in Section 2.4.3 (shown in Figure 2.16b.)

a. Show a simple instance of E, A, B, C, R_A,R_B, and R_C that cannot correspond to any instance of A,B,C, and R.

b. Modify the E-R diagram of Figure 2.16b to introduce constraints that will guarantee that any instance of E,A,B,C, R_A,R_B, and R_C that satisfies the constraints will correspond to an instance of A,B,C, and R.

c. Modify the translation above to handle total participation constraints on the ternary relationship.

d. The above representation requires that we create a primary key attribute for E. Show how to treat E as a weak entity set so that a primary key attribute is not required.

Answer:

a. Let E = {e₁, e₂}, A = {a₁, a₂}, B = {b₁}, C = {c₁}, R_A = {(e₁, a₁), (e₂, a₂)}, R_B = {(e₁, b₁)}, and R_C = {(e₁, c₁)}. We see that because of the tuple (e₂, a₂), no instance of R exists which corresponds to E, R_A, R_B and R_C.

b. See Figure 2.17. The idea is to introduce total participation constraints between E and the relationships R_A, R_B, R_C so that every tuple in E has a relationship with A, B and C.

c. Suppose A totally participates in the relationship R, and then introduce a total participation constraint between A and R_A.

d. Consider E as a weak entity set and R_A, R_B and R_C as its identifying relationship sets. See Figure 2.18.

2.19 A weak entity set can always be made into a strong entity set by adding to its attributes the primary key attributes of its identifying entity set. Outline what sort of redundancy will result if we do so.

Answer: The primary key of a weak entity set can be inferred from its relationship with the strong entity set. If we add primary key attributes to the weak entity set, they will be present in both the entity set and the relationship set and they have to be the same. Hence there will be redundancy.

2.20 Design a generalization–specialization hierarchy for a motor-vehicle sales company. The company sells motorcycles, passenger cars, vans, and buses. Justify your placement of attributes at each level of the hierarchy. Explain why they should not be placed at a higher or lower level.

Answer: Figure 2.19 gives one possible hierarchy; there could be many different solutions. The generalization–specialization hierarchy for the motor-vehicle company is given in the figure. model, sales-tax-rate and sales-volume are attributes necessary for all types of vehicles. Commercial vehicles attract commercial vehicle tax, and each kind of commercial vehicle has a passenger carrying capacity specified for it. Some kinds of non-commercial vehicles attract luxury vehicle tax. Cars alone can be of several types, such as sports-car, sedan, wagon etc., hence the attribute type.

2.21 Explain the distinction between condition-defined and user-defined constraints. Which of these constraints can the system check automatically? Explain your answer.

Answer: In a generalization–specialization hierarchy, it must be possible to decide which entities are members of which lower level entity sets. In a condition defined design constraint, membership in the lower level entity-sets is evaluated on the basis of whether or not an entity satisfies an explicit condition or predicate. User-defined lower-level entity sets are not constrained by a membership condition; rather, entities are assigned to a given entity set by the database user.

Condition-defined constraints alone can be automatically handled by the system. Whenever any tuple is inserted into the database, its membership in the various lower level entity-sets can be automatically decided by evaluating the respective membership predicates. Similarly when a tuple is updated, its membership in the various entity sets can be re-evaluated automatically.

2.22 Explain the distinction between disjoint and overlapping constraints.

Answer: In a disjointness design constraint, an entity can belong to not more than one lower-level entity set. In overlapping generalizations, the same entity may belong to more than one lower-level entity sets. For example, in the employee-work team example of the book, a manager may participate in more than one work-team.

2.23 Explain the distinction between total and partial constraints.

Answer: In a total design constraint, each higher-level entity must belong to a lower-level entity set. The same need not be true in a partial design constraint. For instance, some employees may belong to no work-team.

2.24 Figure 2.20 shows a lattice structure of generalization and specialization. For entity sets A, B, and C, explain how attributes are inherited from the higher level entity sets X and Y. Discuss how to handle a case where an attribute of X has the same name as some attribute of Y.

Answer: A inherits all the attributes of X plus it may define its own attributes. Similarly C inherits all the attributes of Y plus its own attributes. B inherits the attributes of both X and Y. If there is some attribute name which belongs to both X and Y, it may be referred to in B by the qualified name X.name or Y.name.

2.25 Draw the UML equivalents of the E-R diagrams of Figures 2.9c, 2.10, 2.12, 2.13 and 2.17.

Answer: See Figures 2.21 to 2.25

2.26 Consider two separate banks that decide to merge. Assume that both banks use exactly the same E-R database schema—the one in Figure 2.22. (This assumption is, of course, highly unrealistic; we consider the more realistic case in Section 19.8.) If the merged bank is to have a single database, there are several potential problems:

• The possibility that the two original banks have branches with the same name

• The possibility that some customers are customers of both original banks

• The possibility that some loan or account numbers were used at both original banks (for different loans or accounts, of course)

For each of these potential problems, describe why there is indeed a potential for difficulties. Propose a solution to the problem. For your solution, explain any changes that would have to be made and describe what their effect would be on the schema and the data.

Answer: In this example, we assume that both banks have the shared identifiers for customers, such as the social security number. We see the general solution in the next exercise.

Each of the problems mentioned does have potential for difficulties.

a. branch-name is the primary-key of the branch entity set. Therefore while merging the two banks’ entity sets, if both banks have a branch with the same name, one of them will be lost.

b. customers participate in the relationship sets cust-banker, borrower and depositor. While merging the two banks’ customer entity sets, duplicate tuples of the same customer will be deleted. Therefore those relations in the three mentioned relationship sets which involved these deleted tuples will have to be updated. Note that if the tabular representation of a relationship set is obtained by taking a union of the primary keys of the participating entity sets, no modification to these relationship sets is required.

c. The problem caused by loans or accounts with the same number in both the banks is similar to the problem caused by branches in both the banks with the same branch-name. To solve the problems caused by the merger, no schema changes are required. Merge the customer entity sets removing duplicate tuples with the same social security field. Before merging the branch entity sets, prepend the old bank name to the branch-name attribute in each tuple. The employee entity sets can be merged directly, and so can the payment entity sets. No duplicate removal should be performed. Before merging the loan and account entity sets, whenever there is a number common in both the banks, the old number is replaced by a new unique number, in one of the banks.

Next the relationship sets can be merged. Any relation in any relationship set which involves a tuple which has been modified earlier due to the merger, is itself modified to retain the same meaning. For example let 1611 be a loan number common in both the banks prior to the merger, and let it be replaced by a new unique number 2611 in one of the banks, say bank 2.Now all the relations in borrower, loan-branch and loan-payment of bank 2 which refer to loan number 1611 will have to be modified to refer to 2611. Then the merger with bank 1’s corresponding relationship sets can take place.

2.27 Reconsider the situation described for Exercise 2.26 under the assumption that one bank is in the United States and the other is in Canada. As before, the banks use the schema of Figure 2.22, except that the Canadian bank uses the social-insurance number assigned by the Canadian government, whereas the U.S. bank uses the social-security number to identify customers. What problems (beyond those identified in Exercise 2.24) might occur in this multinational case? How would you resolve them? Be sure to consider both the scheme and the actual data values in constructing your answer.

Answer: This is a case in which the schemas of the two banks differ, so the merger becomes more difficult. The identifying attribute for persons in the US is social-security, and in Canada it is social-insurance. Therefore the merged schema cannot use either of these. Instead we introduce a new attribute person-id, and use this uniformly for everybody in the merged schema. No other change to the schema is required. The values for the person-id attribute may be obtained by several ways. One way would be to prepend a country code to the old social security or social-insurance values (“U” and “C” respectively, for instance), to get the corresponding person-id values. Another way would be to assign fresh numbers starting from 1 upwards, one number to each social-security and social insurance

1. value in the old databases.

Once this has been done, the actual merger can proceed as according to the answer to the previous question. If a particular relationship set, say borrower, involves only US customers, this can be expressed in the merged database by specializing the entity-set customer into us-customer and canada-customer, and making only us-customer participate in the merged borrower. Similarly employee can be specialized if needed.

Relational Model

3.11 List two reasons why we may choose to define a view.

Answer:

a. Security conditions may require that the entire logical database be not visible to all users.

b. We may wish to create a personalized collection of relations that is better matched to a certain user’s intuition than is the actual logical model.

3.12 List two major problems with processing update operations expressed in terms of views.

Answer: Views present significant problems if updates are expressed with them. The difficulty is that a modification to the database expressed in terms of a view must be translated to a modification to the actual relations in the logical model of the database.

a. Since the view may not have all the attributes of the underlying tables, insertion of a tuple into the view will insert tuples into the underlying tables, with those attributes not participating in the view getting null values. This may not be desirable, especially if the attribute in question is part of the primary key of the table.

b. If a view is a join of several underlying tables and an insertion results in tuples with nulls in the join columns, the desired effect of the insertion will not be achieved. In other words, an update to a view may not be expressible at all as updates to base relations.

6.12 In Chapter 3, we described the use of views to simplify access to the database by users who need to see only part of the database. In this chapter, we described the use of views as a security mechanism. Do these two purposes for views ever conflict? Explain your answer.

Answer: Usually, a well-designed view and security mechanism can avoid conflicts between ease of access and security. However, as the following example shows, the two purposes do conflict in case the mechanisms are not designed carefully.

Suppose we have a database of employee data and a user whose view involves employee data for employees earning less than $10,000. If this user inserts employee Jones, whose salary is $9,000, but accidentally enters $90,000, several existing database systems will accept this update as a valid update through a view. However, the user will be denied access to delete this erroneous tuple by the security mechanism.

6.13 What is the purpose of having separate categories for index authorization and resource authorization?

Answer: Index and resource authorization should be special categories to allow certain users to create relations (and the indices to operate on them) while preventing these time-consuming and schema-changing operations from being available to many users. Separating index and resource authorization allows a user to build an index on existing relations, say, for optimization purposes, but allows us to deny that user the right to create new relations.

6.14 Database systems that store each relation in a separate operating-system file may use the operating system’s security and authorization scheme, instead of defining a special scheme themselves. Discuss an advantage and a disadvantage of such an approach.

Answer: Database systems have special requirements which are typically more refined than most operating systems. For example, a single user may have different privileges on different files throughout the system, including changing indices and attributes which file systems typically don’t monitor. The advantage of using the operating system’s security mechanism is that it simplifies the database system and can be used for simple (read/write) security measures.

6.15 What are two advantages of encrypting data stored in the database?

Answer:

a. Encrypted data allows authorized users to access data without worrying about other users or the system administrator gaining any information.

b. Encryption of data may simplify or even strengthen other authorization mechanisms. For example, distribution of the cryptographic key amongst only trusted users is both, a simple way to control read access, and an added layer of security above that offered by views.

6.16 Perhaps the most important data items in any database system are the passwords that control access to the database. Suggest a scheme for the secure storage of passwords. Be sure that your scheme allows the system to test passwords supplied by users who are attempting to log into the system.

Answer: A scheme for storing passwords would be to encrypt each password, and then use a hash index on the user-id. The user-id can be used to easily access the encrypted password. The password being used in a login attempt is then encrypted and compared with the stored encryption of the correct password. An advantage of this scheme is that passwords are not stored in clear text and the code for decryption need not even exist!

Relational-Database Design

7.1 Explain what is meant by repetition of information and inability to represent information. Explain why each of these properties may indicate a bad relational database design.

Answer:

• Repetition of information is a condition in a relational database where the values of one attribute are determined by the values of another attribute in the same relation, and both values are repeated throughout the relation. This is a bad relational database design because it increases the storage required for the relation and it makes updating the relation more difficult.

• Inability to represent information is a condition where a relationship exists among only a proper subset of the attributes in a relation. This is bad relational database design because all the unrelated attributes must be filled with null values otherwise a tuple without the unrelated information cannot be inserted into the relation.

• Loss of information is a condition of a relational database which results from the decomposition of one relation into two relations and which cannot be combined to recreate the original relation. It is a bad relational database design because certain queries cannot be answered using the reconstructed relation that could have been answered using the original relation.

7.3 Why are certain functional dependencies called trivial functional dependencies?

Answer: Certain functional dependencies are called trivial functional dependencies because they are satisfied by all relations.

7.20 List the three design goals for relational databases, and explain why each is desirable.

Answer: The three design goals are lossless-join decompositions, dependency preserving decompositions, and minimization of repetition of information. They are desirable so we can maintain an accurate database, check correctness of updates quickly, and use the smallest amount of space possible.

Object-Oriented Databases

8.1 For each of the following application areas, explain why a relational database system would be inadequate. List all specific system components that would need to be modified.

a. Computer-aided design

b. Multimedia databases

Answer: Each of the applications includes large, specialized data items (e.g., a program module, a graphic image, digitized voice, a document). These data items have operations specific to them (e.g., compile, rotate, play, format) that cannot be expressed in relational query languages. These data items are of variable length making it impractical to store them in the short fields that are allowed in records for such database systems. Thus, the data model, data manipulation language, and data definition language need to be changed. Also, long-duration and nested transactions are typical of these applications. Changes to the concurrency and recovery subsystems are likely to be needed.

8.2 How does the concept of an object in the object-oriented model differ from the concept of an entity in the entity-relationship model?

Answer: An entity is simply a collection of variables or data items. An object is an encapsulation of data as well as the methods (code) to operate on the data. The data members of an object are directly visible only to its methods. The outside world can gain access to the object’s data only by passing pre-defined messages to it, and these messages are implemented by the methods.

8.4 Explain why ambiguity potentially exists with multiple inheritance. Illustrate your explanation with an example.

Answer: A class inherits the variables and methods of all its immediate super classes. Thus it could inherit a variable or method of the same name from more than one super-class. When that particular variable or method of an object of the sub-class is referenced, there is an ambiguity regarding which of the super classes provides the inheritance.

For instance, let there be classes teacher and student, both having a variable department. If a class teachingAssistant inherits from both of these classes, any reference to the department variable of a teachingAssistant object is ambiguous.

8.5 Explain how the concept of object identity in the object-oriented model differs from the concept of tuple equality in the relational model.

Answer: Tuple equality is determined by data values. Object identity is independent of data values, since object-oriented systems use built-in identity.

8.6 Explain the distinction in meaning between edges in a DAG representing inheritance and a DAG representing object containment.

Answer: An edge from class A to class B in the DAG representing inheritance means that an object of class B is also an object of class A. It has all the properties that objects of class A have, plus additional ones of its own. In particular, it inherits all the variables and methods of class A. It can of course provide its own implementations for the inherited methods.

And edge from class A to class B in the object containment DAG means that an object of class A contains an object of class B. There need not be any similarities in the properties of A and B. Neither B nor A inherit anything from the other. They function as independent types, to the extent that an object of class A can access the variables of the B object contained in it only via the B object’s methods.

8.7 Why do persistent programming languages allow transient objects? Might it be simpler to use only persistent objects, with unneeded objects deleted at the end of an execution? Explain your answer.

Answer: Creation, destruction and access will typically be more time consuming and expensive for persistent objects stored in the database, than for transient objects in the transaction’s local memory. This is because of the over-heads in preserving transaction semantics, security and integrity. Since a transient object is purely local to the transaction which created it and does not enter the database, all these over-heads are avoided. Thus, in order to provide efficient access to purely local and temporary data, transient objects are provided by persistent programming languages.

8.11 Explain how a persistent pointer is implemented. Contrast this implementation with that of pointers as they exist in general-purpose languages, such as C or Pascal.

Answer: Persistent pointers can be implemented as Abstract Data Types (ADTs). These ADTs should provide the typical pointer operations like incrementing and dereferencing, so their usage and regular pointer usage is uniform. Regular pointers on the other hand are usually built-in types, implemented as part of the language.

8.12 If an object is created without any references to it, how can that object be deleted?

Answer: If an object is created without any references to it, it can neither be accessed nor deleted via a program. The only way is for the database system to locate and delete such objects by itself. This is called garbage collection. One way to do garbage collection is by the method of mark and sweep. First, the objects referred to directly by programs are marked. Then references from these objects to other objects are followed, and those referred objects are marked. This procedure is followed repeatedly until no more unmarked objects can be reached by following reference chains from the marked objects. At this point, all these remaining unmarked objects are deleted. This method is correct; we can prove that if no new objects are marked after a round of mark and sweep, the remaining unmarked objects are indeed unreferenced.

8.13 Consider a system that provides persistent objects. Is such a system necessarily a database system? Explain your answer.

Answer: A database system must provide for such features as transactions, queries (associative retrieval of objects), security, and integrity. A persistent object system may not offer such features.

Object-Relational Databases

9.5 Explain the distinction between a type x and a reference type ref(x). Under what circumstances would you choose to use a reference type?

Answer: If the type of an attribute is x, then in each tuple of the table, corresponding to that attribute, there is an actual object of type x. If its type is ref(x), then in each tuple, corresponding to that attribute, there is a reference to some object of type x. We choose a reference type for an attribute, if that attribute’s intended purpose is to refer to an independent object.

9.11 Compare the use of embedded SQL with the use in SQL of functions defined in a general-purpose programming language. Under what circumstances would you use each of these features?

Answer: SQL functions are primarily a mechanism for extending the power of SQL to handle attributes of complex data types (like images), or to perform complex and non-standard operations. Embedded SQL is useful when imperative actions like displaying results and interacting with the user are needed. These cannot be done conveniently in an SQL only environment. Embedded SQL can be used instead of SQL functions by retrieving data and then performing the function’s operations on the SQL result. However a drawback is that a lot of query-evaluation functionality may end up getting repeated in the host language code.

9.12 Suppose that you have been hired as a consultant to choose a database system for your client’s application. For each of the following applications, state what type of database system (relational, persistent-programming-language–based OODB, object relational; do not specify a commercial product) you would recommend. Justify your recommendation.

a. A computer-aided design system for a manufacturer of airplanes

b. A system to track contributions made to candidates for public office

c. An information system to support the making of movies

Answer:

a. A computer-aided design system for a manufacturer of airplanes: - An OODB system would be suitable for this. That is because CAD requires complex data types, and being computation oriented, CAD tools are typically used in a programming language environment needing to access the database.

b. A system to track contributions made to candidates for public office: - A relational system would be apt for this, as data types are expected to be simple, and a powerful querying mechanism is essential.

c. An information system to support the making of movies: - Here there will be extensive use of multimedia and other complex data types. But queries are probably simple, and thus an object relational system is suitable.

Storage and File Structure

11.2 How does the remapping of bad sectors by disk controllers affect data-retrieval rates?

Answer: Remapping of bad sectors by disk controllers does reduce data retrieval rates because of the loss of sequentiality amongst the sectors. But that is better than the loss of data in case of no remapping!

11.4 A power failure that occurs while a disk block is being written could result in the block being only partially written. Assume that partially written blocks can be detected. An atomic block write is one where either the disk block is fully written or nothing is written (i.e., there are no partial writes). Suggest schemes for getting the effect of atomic block writes with the following RAID schemes.

Your schemes should involve work on recovery from failure.

a. RAID level 1 (mirroring)

b. RAID level 5 (block interleaved, distributed parity)

Answer:

a. To ensure atomicity, a block write operation is carried out as follows:-

i. Write the information onto the first physical block.

ii. When the first write completes successfully, write the same information onto the second physical block.

iii. The output is declared completed only after the second write completes successfully.

During recovery, each pair of physical blocks is examined. If both are identical and there is no detectable partial-write, then no further actions are necessary. If one block has been partially rewritten, then we replace its contents with the contents of the other block. If there has been no partial write, but they differ in content, then we replace the contents of the first block with the contents of the second, or vice versa. This recovery procedure ensures that a write to stable storage either succeeds completely (that is, updates both copies) or results in no change.

The requirement of comparing every corresponding pair of blocks during recovery is expensive to meet. We can reduce the cost greatly by keeping track of block writes that are in progress, using a small amount of nonvolatile RAM. On recovery, only blocks for which writes were in progress need to be compared.

b. The idea is similar here. For any block write, the information block is written first followed by the corresponding parity block. At the time of recovery, each set consisting of the nth block of each of the disks is considered. If none of the blocks in the set have been partially-written, and the parity block contents are consistent with the contents of the information blocks, then no further action need be taken. If any block has been partially-written, it’s contents are reconstructed using the other blocks. If no block has been partially-written, but the parity block contents do not agree with the information block contents, the parity block’s contents are reconstructed.

11.5 RAID systems typically allow you to replace failed disks without stopping access to the system. Thus, the data in the failed disk must be rebuilt and written to the replacement disk while the system is in operation. With which of the RAID levels is the amount of interference between the rebuild and ongoing disk accesses least? Explain your answer.

Answer: RAID level 1 (mirroring) is the one which facilitates rebuilding of a failed disk with minimum interference with the on-going disk accesses. This is because rebuilding in this case involves copying data from just the failed disk’s mirror. In the other RAID levels, rebuilding involves reading the entire contents of all the other disks.

11.6 Give an example of a relational-algebra expression and a query-processing strategy in each of the following situations:

a. MRU is preferable to LRU.

b. LRU is preferable to MRU.

Answer:

a. MRU is preferable to LRU where R1 1 R2 is computed by using a nested loop processing strategy where each tuple in R2 must be compared to each block in R1. After the first tuple of R2 is processed, the next needed block is the first one in R1. However, since it is the least recently used, the LRU buffer management strategy would replace that block if a new block was needed by the system.

b. LRU is preferable to MRU where R1 1 R2 is computed by sorting the relations by join values and then comparing the values by proceeding through the relations. Due to duplicate join values, it may be necessary to “backup” in one of the relations. This “backing-up” could cross a block boundary into the most recently used block, which would have been replaced by a system using MRU buffer management, if a new block was needed.

Under MRU, some unused blocks may remain in memory forever. In practice, MRU can be used only in special situations like that of the nested loop strategy discussed in example 0.a

11.7 Consider the deletion of record 5 from the file of Figure 11.8. Compare the relative merits of the following techniques for implementing the deletion:

a. Move record 6 to the space occupied by record 5, and move record 7 to the space occupied by record 6.

b. Move record 7 to the space occupied by record 5.

c. Mark record 5 as deleted, and move no records.

Answer:

a. Although moving record 6 to the space for 5, and moving record 7 to the space for 6, is the most straightforward approach, it requires moving the most records, and involves the most accesses.

b. Moving record 7 to the space for 5 moves fewer records, but destroys any ordering in the file.

c. Marking the space for 5 as deleted preserves ordering and moves no records, but requires additional overhead to keep track of all of the free space in the file. This method may lead to too many “holes” in the file, which if not compacted from time to time, will affect performance because of reduced availability of contiguous free records.

11.9 Give an example of a database application in which the reserved-space method of representing variable-length records is preferable to the pointer method. Explain your answer.

Answer: In the reserved space method, a query comparing the last existing field in a record to some value requires only one read from the disk. This single read is preferable to the potentially many reads needed to chase down the pointers to the last field if the pointer method is used.

11.10 Give an example of a database application in which the pointer method of representing variable-length records is preferable to the reserved-space method. Explain your answer.

Answer: Using the pointer method, a join operation on attributes which are only in the anchor block can be performed on only this smaller amount of data, rather than on the entire relation, as would be the case using the reserved space method. Therefore, in this join example, the pointer method is preferable.

11.14 Explain why the allocation of records to blocks affects database-system performance significantly.

Answer: If we allocate related records to blocks, we can often retrieve most, or all, of the requested records by a query with one disk access. Disk accesses tend to be the bottlenecks in databases; since this allocation strategy reduces the number of disk accesses for a given operation, it significantly improves performance.

11.15 If possible, determine the buffer-management strategy used by the operating system running on your local computer system, and what mechanisms it provides to control replacement of pages. Discuss how the control on replacement that it provides would be useful for the implementation of database systems.

Answer: The typical OS uses LRU for buffer replacement. This is often a bad strategy for databases. As explained in Section 11.5.2 of the text, MRU is the best strategy for nested loop join. In general no single strategy handles all scenarios well, and ideally the database system should be given its own buffer cache for which the replacement policy takes into account all the performance related issues.

11.16 In the sequential file organization, why is an overflow block used even if there is, at the moment, only one overflow record?

Answer: An overflow block is used in sequential file organization because a block is the smallest space which can be read from a disk. Therefore, using any smaller region would not be useful from a performance standpoint. The space saved by allocating disk storage in record units would be overshadowed by the performance cost of allowing blocks to contain records of multiple files.

11.17 List two advantages and two disadvantages of each of the following strategies for storing a relational database:

a. Store each relation in one file.

b. Store multiple relations (perhaps even the entire database) in one file.

Answer:

a. Advantages of storing a relation as a file include using the file system provided by the OS, thus simplifying the DBMS, but incur the disadvantage of restricting the ability of the DBMS to increase performance by using more sophisticated storage structures.

b. By using one file for the entire database, these complex structures can be implemented through the DBMS, but this increases the size and complexity of the DBMS.

11.21 Explain why a physical OID must contain more information than a pointer to a physical storage location.

Answer: A physical OID needs to have a unique identifier in addition to a pointer to a physical storage location. This is required to prevent dereferences of dangling pointers.

11.22 If physical OIDs are used, an object can be relocated by keeping a forwarding pointer to its new location. In case an object gets forwarded multiple times, what would be the effect on retrieval speed? Suggest a technique to avoid multiple accesses in such a case.

Answer: If an object gets forwarded multiple times, the retrieval speed will decrease because accessing it will require accessing the series of locations from which the object has been successively forwarded to the current location.

Multiple accesses can be avoided by always keeping in the oldest location the latest address of the object. This can be done by checking while forwarding whether this object has already been forwarded and in that case updating the forwarding address at the oldest location. Thus, at most two accesses will be required.

11.23 Define the term dangling pointer. Describe how the unique-id scheme helps in detecting dangling pointers in an object-oriented database.

Answer: A dangling pointer is a pointer to an area which no longer contains valid data.

In the unique-id scheme to detect dangling pointers, physical OIDs may contain a unique identifier which is an integer that distinguishes the OID from the identifiers of other objects that happened to be stored at the same location earlier, and were deleted or moved elsewhere. The unique identifier is also stored with the object, and the identifiers in an OID and the corresponding object should match. If the unique identifier in a physical OID does not match the unique identifier in the object to which that OID points, the system detects that the pointer is a dangling pointer, and signals an error.

Query Processing

13.1 Why is it not desirable to force users to make an explicit choice of a query processing strategy? Are there cases in which it is desirable for users to be aware of the costs of competing query-processing strategies? Explain your answer.

Answer: In general it is not desirable to force users to choose a query processing strategy because naive users might select an inefficient strategy. The reason users would make poor choices about processing queries is that they would not know how a relation is stored, nor about its indices. It is unreasonable to force users to be aware of these details since ease of use is a major object of database query languages. If users are aware of the costs of different strategies they could write queries efficiently, thus helping performance. This could happen if experts were using the system.

15.1 List the ACID properties. Explain the usefulness of each.

Answer: The ACID properties, and the need for each of them are:-

• Consistency:

Execution of a transaction in isolation (that is, with no other transaction executing concurrently) preserves the consistency of the database. This is typically the responsibility of the application programmer who codes the transactions.

• Atomicity: Either all operations of the transaction are reflected properly in the database, or none are. Clearly lack of atomicity will lead to inconsistency in the database.

• Isolation: When multiple transactions execute concurrently, it should be the case that, for every pair of transactions Ti and Tj , it appears to Ti that either Tj finished execution before Ti started, or Tj started execution after Ti finished. Thus, each transaction is unaware of other transactions executing concurrently with it. The user view of a transaction system requires the isolation property, and the property that concurrent schedules take the system from one consistent state to another. These requirements are satisfied by ensuring that only serializable schedules of individually consistency preserving transactions are allowed.

• Durability: After a transaction completes successfully, the changes it has made to the database persist, even if there are system failures.

15.2 Suppose that there is a database system that never fails. Is a recovery manager required for this system?

Answer: Even in this case the recovery manager is needed to perform roll-back of aborted transactions.

15.3 Consider a file system such as the one on your favorite operating system.

a. What are the steps involved in creation and deletion of files, and in writing data to a file?

b. Explain how the issues of atomicity and durability are relevant to the creation and deletion of files, and to writing data to files.

Answer: There are several steps in the creation of a file. A storage area is assigned to the file in the file system, a unique i-number is given to the file and an i-node entry is inserted into the i-list. Deletion of file involves exactly opposite steps. For the file system user in UNIX, durability is important for obvious reasons, but atomicity is not relevant generally as the file system doesn’t support transactions. To the file system implementor though, many of the internal file system actions need to have transaction semantics. All the steps involved in creation/deletion of the file must be atomic, otherwise there will be unreferenceable files or unusable areas in the file system.

15.4 Database-system implementers have paid much more attention to the ACID properties than have file-system implementers. Why might this be the case?

Answer: Database systems usually perform crucial tasks whose effects need to be atomic and durable, and whose outcome affects the real world in a permanent manner. Examples of such tasks are monetary transactions, seat bookings etc. Hence the ACID properties have to be ensured. In contrast, most users of file systems would not be willing to pay the price (monetary, disk space, time) of supporting ACID properties.

15.5 During its execution, a transaction passes through several states, until it finally commits or aborts. List all possible sequences of states through which a transaction may pass. Explain why each state transition may occur.

Answer: The possible sequences of states are:-

a. active → partially committed → committed. This is the normal sequence a successful transaction will follow. After executing all its statements it enters the partially committed state. After enough recovery information has been written to disk, the transaction finally enters the committed state.

b. active → partially committed → aborted. After executing the last statement of the transaction, it enters the partially committed state. But before enough recovery information is written to disk, a hardware failure may occur destroying the memory contents. In this case the changes which it made to the database are undone, and the transaction enters the aborted state.

c. active → failed → aborted. After the transaction starts, if it is discovered at some point that normal execution cannot continue (either due to internal program errors or external errors), it enters the failed state. It is then rolled back, after which it enters the aborted state.

15.6 Justify the following statement: Concurrent execution of transactions is more important when data must be fetched from (slow) disk or when transactions are long, and is less important when data is in memory and transactions are very short.

Answer: If a transaction is very long or when it fetches data from a slow disk, it takes a long time to complete. In absence of concurrency, other transactions will have to wait for longer period of time. Average responce timewill increase. Also when the transaction is reading data from disk, CPU is idle. So resources are not properly utilized. Hence concurrent execution becomes important in this case. However, when the transactions are short or the data is available in memory, these problems do not occur.

15.7 Explain the distinction between the terms serial schedule and serializable schedule.

Answer: A schedule in which all the instructions belonging to one single transaction appear together is called a serial schedule. A serializable schedule has a weaker restriction that it should be equivalent to some serial schedule. There are two definitions of schedule equivalence – conflict equivalence and view equivalence. Both of these are described in the chapter.

15.9 Since every conflict-serializable schedule is view serializable, why do we emphasize conflict serializability rather than view serializability?

Answer: Most of the concurrency control protocols (protocols for ensuring that only serializable schedules are generated) used in practise are based on conflict serializability—they actually permit only a subset of conflict serializable schedules. The general form of view serializability is very expensive to test, and only a very restricted form of it is used for concurrency control.

15.11 What is a recoverable schedule? Why is recoverability of schedules desirable? Are there any circumstances under which it would be desirable to allow nonrecoverable schedules? Explain your answer.

Answer: A recoverable schedule is one where, for each pair of transactions Ti and Tj such that Tj reads data items previously written by Ti, the commit operation of Ti appears before the commit operation of Tj. Recoverable schedules are desirable because failure of a transaction might otherwise bring the system into an irreversibly inconsistent state. Non recoverable schedules may sometimes be needed when updates must be made visible early due to time constraints, even if they have not yet been committed, which may be required for very long duration transactions.

15.12 What is a cascadeless schedule? Why is cascadelessness of schedules desirable? Are there any circumstances under which it would be desirable to allow noncascadeless schedules? Explain your answer.

Answer: A cascadeless schedule is one where, for each pair of transactions Ti and Tj such that Tj reads data items previously written by Ti, the commit operation of Ti appears before the read operation of Tj. Cascadeless schedules are desirable because the failure of a transaction does not lead to the aborting of any other transaction. Of course this comes at the cost of less concurrency. If failures occur rarely, so that we can pay the price of cascading aborts for the increased concurrency, noncascadeless schedules might be desirable.

16.3 What benefit does strict two-phase locking provide? What disadvantages result?

Answer: Because it produces only cascadeless schedules, recovery is very easy. But the set of schedules obtainable is a subset of those obtainable from plain two phase locking, thus concurrency is reduced.

16.4 What benefit does rigorous two-phase locking provide? How does it compare with other forms of two-phase locking?

Answer: Rigorous two-phase locking has the advantages of strict 2PL. In addition it has the property that for two conflicting transactions, their commit order is their serializability order. In some systems users might expect this behavior.

16.5 Most implementations of database systems use strict two-phase locking. Suggest three reasons for the popularity of this protocol.

Answer: It is relatively simple to implement, imposes low rollback overhead because of cascadeless schedules, and usually allows an acceptable level of concurrency.

16.12 Locking is not done explicitly in persistent programming languages. Rather, objects (or the corresponding pages) must be locked when the objects are accessed. Most modern operating systems allow the user to set access protections (no access, read, writes) on pages, and memory access that violate the access protections result in a protection violation (see the Unix mprotect command, for example). Describe how the access-protection mechanism can be used for page-level locking in a persistent programming language. (Hint: The technique is similar to that used for hardware swizzling in Section 11.9.4).

Answer: The access protection mechanism can be used to implement page level locking. Consider reads first. A process is allowed to read a page only after it read-locks the page. This is implemented by using mprotect to initially turn off read permissions to all pages, for the process. When the process tries to access an address in a page, a protection violation occurs. The handler associated with protection violation then requests a read lock on the page, and after the lock is acquired, it uses mprotect to allow read access to the page by the process, and finally allows the process to continue. Write access is handled similarly.

16.15 When a transaction is rolled back under timestamp ordering, it is assigned a new timestamp. Why can it not simply keep its old timestamp?

Answer: A transaction is rolled back because a newer transaction has read or written the data which it was supposed to write. If the rolled back transaction is re-introduced with the same timestamp, the same reason for rollback is still valid, and the transaction will have be rolled back again. This will continue indefinitely.

16.16 In multiple-granularity locking, what is the difference between implicit and explicit locking?

Answer: When a transaction explicitly locks a node in shared or exclusive mode, it implicitly locks all the descendents of that node in the same mode. The transaction need not explicitly lock the descendent nodes. There is no difference in the functionalities of these locks, the only difference is in the way they are acquired, and their presence tested.

16.17 Although SIX mode is useful in multiple-granularity locking, an exclusive and intend-shared (XIS) mode is of no use. Why is it useless?

Answer: An exclusive lock is incompatible with any other lock kind. Once a node is locked in exclusive mode, none of the descendents can be simultaneously accessed by any other transaction in any mode. Therefore an exclusive and intend-shared declaration has no meaning.

16.18 Use of multiple-granularity locking may require more or fewer locks than an equivalent system with a single lock granularity. Provide examples of both situations, and compare the relative amount of concurrency allowed.

Answer: If a transaction needs to access a large a set of items, multiple granularity locking requires fewer locks, whereas if only one item needs to be accessed, the single lock granularity system allows this with just one lock. Because all the desired data items are locked and unlocked together in the multiple granularity scheme, the locking overhead is low, but concurrency is also reduced.

16.19 Consider the validation-based concurrency-control scheme of Section 16.3. Show that by choosing Validation(Ti), rather than Start(Ti), as the timestamp of transaction Ti, we can expect better response time provided that conflict rates among transactions are indeed low.

Answer: In the concurrency control scheme of Section 16.3 choosing Start(Ti) as the timestamp of Ti gives a subset of the schedules allowed by choosing Validation(Ti) as the timestamp. Using Start(Ti) means that whoever started first must finish first. Clearly transactions could enter the validation phase in the same order in which they began executing, but this is overly restrictive. Since choosing Validation(Ti) causes fewer nonconflicting transactions to restart, it gives the better response times.

16.21 For each of the following protocols, describe aspects of practical applications that would lead you to suggest using the protocol, and aspects that would suggest not using the protocol:

• Two-phase locking

• Two-phase locking with multiple-granularity locking

• The tree protocol

• Timestamp ordering

• Validation

• Multiversion timestamp ordering

• Multiversion two-phase locking

Answer:

• Two-phase locking: Use for simple applications where a single granularity is acceptable. If there are large read-only transactions, multiversion protocols would do better. Also, if deadlocks must be avoided at all costs, the tree protocol would be preferable.

• Two-phase locking with multiple granularity locking: Use for an application mix where some applications access individual records and others access whole relations or substantial parts thereof. The drawbacks of 2PL mentioned above also apply to this one.

• The tree protocol: Use if all applications tend to access data items in an order consistent with a particular partial order. This protocol is free of deadlocks, but transactions will often have to lock unwanted nodes in order to access the desired nodes.

• Timestamp ordering: Use if the application demands a concurrent execution that is equivalent to a particular serial ordering (say, the order of arrival), rather than any serial ordering. But conflicts are handled by roll-back of transactions rather than waiting, and schedules are not recoverable. To make them recoverable, additional overheads and increased response time have to be tolerated. Not suitable if there are long read-only transactions, since they will starve. Deadlocks are absent.

• Validation: If the probability that two concurrently executing transactions conflict is low, this protocol can be used advantageously to get better concurrency and good response times with low overheads. Not suitable under high contention, when a lot of wasted work will be done.

• Multiversion timestamp ordering: Use if timestamp ordering is appropriate but it is desirable for read requests to never wait. Shares the other disadvantages of the timestamp ordering protocol.

• Multiversion two-phase locking: This protocol allows read-only transactions to always commit without ever waiting. Update transactions follow 2PL, thus allowing recoverable schedules with conflicts solved by waiting rather than roll-back. But the problem of deadlocks comes back, though read-only transactions cannot get involved in them. Keeping multiple versions adds space and time overheads though, therefore plain 2PL may be preferable in low conflict situations.

16.22 Under a modified version of the timestamp protocol, we require that a commit bit be tested to see whether a read request must wait. Explain how the commit bit can prevent cascading abort. Why is this test not necessary for write requests?

Answer: Using the commit bit, a read request is made to wait if the transaction which wrote the data item has not yet committed. Therefore, if the writing transaction fails before commit, we can abort that transaction alone. The waiting read will then access the earlier version in case of a multiversion system, or the restored value of the data item after abort in case of a single-version system. For writes, this commit bit checking is unnecessary. That is because either the write is a “blind” write and thus independent of the old value of the data item or there was a prior read, in which case the test was already applied.

16.24 Under what conditions is it less expensive to avoid deadlock than to allow deadlocks to occur and then to detect them?

Answer: Deadlock avoidance is preferable if the consequences of abort are serious (as in interactive transactions), and if there is high contention and a resulting high probability of deadlock.

16.25 If deadlock is avoided by deadlock avoidance schemes, is starvation still possible? Explain your answer.

Answer: A transaction may become the victim of deadlock-prevention rollback arbitrarily many times, thus creating a potential starvation situation.

16.27 Explain the phantom phenomenon. Why may this phenomenon lead to an incorrect concurrent execution despite the use of the two-phase locking protocol?

Answer: The phantom phenomenon arises when, due to an insertion or deletion, two transactions logically conflict despite not locking any data items in common. The insertion case is described in the book. Deletion can also lead to this phenomenon. Suppose Ti deletes a tuple from a relation while Tj scans the relation. If Ti deletes the tuple and then Tj reads the relation, Ti should be serialized before Tj . Yet there is no tuple that both Ti and Tj conflict on. An interpretation of 2PL as just locking the accessed tuples in a relation is incorrect. There is also an index or a relation data that has information about the tuples in the relation. This information is read by any transaction that scans the relation, and modified by transactions that update, or insert into, or delete from the relation. Hence locking must also be performed on the index or relation data, and this will avoid the phantom phenomenon.

17.1 Explain the difference between the three storage types—volatile, nonvolatile, and stable—in terms of I/O cost.

Answer: Volatile storage is storage which fails when there is a power failure. Cache, main memory, and registers are examples of volatile storage. Nonvolatile storage is storage which retains its content despite power failures. An example is magnetic disk. Stable storage is storage which theoretically survives any kind of failure (short of a complete disaster!). This type of storage can only be approximated by replicating data. In terms of I/O cost, volatile memory is the fastest and non-volatile storage is typically several times slower. Stable storage is slower than non-volatile storage because of the cost of data replication.

17.2 Stable storage cannot be implemented.

a. Explain why it cannot be.

b. Explain how database systems deal with this problem.

Answer:

a. Stable storage cannot really be implemented because all storage devices are made of hardware, and all hardware is vulnerable to mechanical or electronic device failures.

b. Database systems approximate stable storage by writing data to multiple storage devices simultaneously. Even if one of the devices crashes, the data will still be available on a different device. Thus data loss becomes extremely unlikely.

17.3 Compare the deferred- and immediate-modification versions of the log-based recovery scheme in terms of ease of implementation and overhead cost.

Answer:

• The recovery scheme using a log with deferred updates has the following advantages over the recovery scheme with immediate updates:

a. The scheme is easier and simpler to implement since fewer operations and routines are needed, i.e., no UNDO.

b. The scheme requires less overhead since no extra I/O operations need to be done until commit time (log records can be kept in memory the entire time).

c. Since the old values of data do not have to be present in the log-records, this scheme requires less log storage space.

• The disadvantages of the deferred modification scheme are :

a. When a data item needs to accessed, the transaction can no longer directly read the correct page from the database buffer, because a previous write by the same transaction to the same data item may not have been propagated to the database yet. It might have updated a local copy of the data item and deferred the actual database modification. Therefore finding the correct version of a data item becomes more expensive.

b. This scheme allows less concurrency than the recovery scheme with immediate updates. This is because write-locks are held by transactions till commit time.

c. For long transaction with many updates, the memory space occupied by log records and local copies of data items may become too high.

17.5 Explain the purpose of the checkpoint mechanism. How often should checkpoints be performed? How does the frequency of checkpoints affect

• System performance when no failure occurs

• The time it takes to recover from a system crash

• The time it takes to recover from a disk crash

Answer: Checkpointing is done with log-based recovery schemes to reduce the time required for recovery after a crash. If there is no checkpointing, then the entire logmust be searched after a crash, and all transactions undone/redone from the log. If checkpointing had been performed, then most of the log-records prior to the checkpoint can be ignored at the time of recovery. Another reason to perform checkpoints is to clear log-records from stable storage as it gets full. Since checkpoints cause some loss in performance while they are being taken, their frequency should be reduced if fast recovery is not critical. If we need fast recovery checkpointing frequency should be increased. If the amount of stable storage available is less, frequent checkpointing is unavoidable. Checkpoints have no effect on recovery from a disk crash; archival dumps are the equivalent of checkpoints for recovery from disk crashes.

17.6 When the system recovers from a crash (see Section 17.6.4), it constructs an undo-list and a redo-list. Explain why log records for transactions on the undo list must be processed in reverse order, while those log records for transactions on the redo-list are processed in a forward direction.

Answer: The first phase of recovery is to undo the changes done by the failed transactions, so that all data items which have been modified by them get back the values they had before the first of the failed transactions started. If several of the failed transactions had modified the same data item, forward processing of log-records for undo-list transactions would make the data item get the value which it had before the last failed transaction to modify that data item started. This is clearly wrong, and we can see that reverse prcessing gets us the desired result. The second phase of recovery is to redo the changes done by committed transactions, so that all data items which have been modified by them are restored to the value they had after the last of the committed transactions finished. It can be seen that only forward processing of log-records belonging to redo-list transactions can guarantee this.

17.7 Compare the shadow-paging recovery scheme with the log-based recovery schemes in terms of ease of implementation and overhead cost.

Answer: The shadow-paging scheme is easy to implement for single-transaction systems, but difficult for multiple-transaction systems. In particular it is very hard to allow multiple updates concurrently on the same page. Shadow paging could suffer from extra space overhead, but garbage collection can take care of that. The I/O overhead for shadow paging is typically higher than the log based schemes, since the log based schemes need to write one record per update to the log, whereas the shadow paging scheme needs to write one block per updated block.

17.9 Explain how the buffer manager may cause the database to become inconsistent if some log records pertaining to a block are not output to stable storage before the block is output to disk.

Answer: If a data item x is modified on disk by a transaction before the corresponding log record is written to stable storage, then the only record of the old value of x is in main memory where it would be lost in a crash. If the transaction had not yet finished at the time of the crash, an unrecoverable inconsistency will result.

17.10 Explain the benefits of logical logging. Give examples of one situation where logical logging is preferable to physical logging and one situation where physical logging is preferable to logical logging.

Answer: Logical logging has less log space requirement, and with logical undo logging it allows early release of locks. This is desirable in situations like concurrency control for index structures, where a very high degree of concurrency is required. An advantage of employing physical redo logging is that fuzzy checkpoints are possible. Thus in a system which needs to perform frequent checkpoints, this reduces checkpointing overhead.

17.11 Explain the reasons why recovery of interactive transactions is more difficult to deal with than is recovery of batch transactions. Is there a simple way to deal with this difficulty? (Hint: Consider an automatic teller machine transaction in which cash is withdrawn.)

Answer: Interactive transactions are more difficult to recover from than batch transactions because some actions may be irrevocable. For example, an output (write) statement may have fired a missile, or caused a bank machine to give money to a customer. The best way to deal with this is to try to do all output statements at the end of the transaction. That way if the transaction aborts in the middle, no harm will be have been done.

Database System Architectures

18.1 Why is it relatively easy to port a database from a single processor machine to

a multiprocessor machine if individual queries need not be parallelized?

Answer: Porting is relatively easy to a shared memory multiprocessor machine.

Databases designed for single-processor machines already providemultitasking,

allowing multiple processes to run on the same processor in a timeshared

manner, giving a view to the user of multiple processes running in parallel.

Thus, coarse-granularity parallel machines logically appear to be identical

to single-processor machines, making the porting relatively easy.

Porting a database to a shared disk or shared nothing multiprocessor architecture

is a little harder.

18.2 Transaction server architectures are popular for client-server relational databases,

where transactions are short. On the other hand, data server architectures

are popular for client-server object-oriented database systems,where transactions

are expected to be relatively long. Give two reasons why data servers may be popular for object-oriented databases but not for relational databases.

Answer: Data servers are good if data transfer is small with respect to computation,

which is often the case in applications of OODBs such as computer

aided design. In contrast, in typical relational database applications such as

transaction processing, a transaction performs little computation butmay touch

several pages, which will result in a lot of data transfer with little benefit in a

data server architecture. Another reason is that structures such as indices are

heavily used in relational databases, and will become spots of contention in

a data server architecture, requiring frequent data transfer. There are no such

points of frequent contention in typical current-day OODB applications such

as computer aided design.

18.3 Instead of storing shared structures in shared memory, an alternative architecture

would be to store them in the local memory of a special process, and access

the shared data by interprocess communication with the process. What would

be the drawback of such an architecture?

Answer: The drawbacks would be that two interprocess messages would be

required to acquire locks, one for the request and one to confirm grant. Interprocess

communication is much more expensive than memory access, so the

cost of locking would increase. The process storing the shared structures could

also become a bottleneck.

The benefit of this alternative is that the lock table is protected better from

erroneous updates since only one process can access it.

18.4 In typical client–server systems the server machine is much more powerful

than the clients; that is, its processor is faster, it may have multiple processors,

and it has more memory and disk capacity. Consider instead a scenario

where client and server machines have exactly the same power.Would it make

sense to build a client–server system in such a scenario? Why? Which scenario

would be better suited to a data-server architecture?

Answer: With powerful clients, it still makes sense to have a client-server

system, rather than a fully centralized system. If the data-server architecture

is used, the powerful clients can off-load all the long and compute intensive

transaction processing work from the server, freeing it to perform only the

work of satisfying read-write requests. even if the transaction-server model

is used, the clients still take care of the user-interface work, which is typically

very compute-intensive.

A fully distributed system might seem attractive in the presence of powerful

clients, but client-server systems still have the advantage of simpler concurrency

control and recovery schemes to be implemented on the server alone,

instead of having these actions distributed in all the machines.

18.5 Consider an object-oriented database system based on a client-server architecture,

with the server acting as a data server.

a. What is the effect of the speed of the interconnection between the client

and the server on the choice between object and page shipping?

b. If page shipping is used, the cache of data at the client can be organized

either as an object cache or a page cache. The page cache stores data in units

of a page, while the object cache stores data in units of objects. Assume

objects are smaller than a page. Describe one benefit of an object cache

over a page cache.

Answer:

a. We assume that objects are smaller than a page and fit in a page. If the interconnection

link is slow it is better to choose object shipping, as in page

shipping a lot of time will be wasted in shipping objects that might never

be needed. With a fast interconnection though, the communication overheads

and latencies, not the actual volume of data to be shipped, becomes

the bottle neck. In this scenario page shipping would be preferable.

b. Two benefits of an having an object-cache rather than a page-cache, even if

page shipping is used, are:-

i. When a client runs out of cache space, it can replace objects without

replacing entire pages. The reduced caching granularity might result

in better cache-hit ratios.

ii. It is possible for the server to ask clients to return some of the locks

which they hold, but don’t need (lock de-escalation). Thus there is

scope for greater concurrency. If page caching is used, this is not possible.

18.6 What is lock de-escalation, and under what conditions is it required?Why is it

not required if the unit of data shipping is an item?

Answer: In a client-server system with page shipping, when a client requests

an item, the server typically grants a lock not on the requested item, but on the

page having the item, thus implicitly granting locks on all the items in the page.

The other items in the page are said to be prefetched. If some other client subsequently

requests one of the prefetched items, the server may ask the owner

of the page lock to transfer back the lock on this item. If the page lock owner

doesn’t need this item, it de-escalates the page lock that it holds, to item locks

on all the items that it is actually accessing, and then returns the locks on the

unwanted items. The server can then grant the latter lock request.

If the unit of data shipping is an item, there are no coarser granularity locks;

even if prefetching is used, it is typically implemented by granting individual

locks on each of the prefetched items. Thus when the server asks for a return of

a lock, there is no question of de-escalation, the requested lock is just returned

if the client has no use for it.

18.7 Suppose you were in charge of the database operations of a company whose

main job is to process transactions. Suppose the company is growing rapidly

each year, and has outgrown its current computer system. When you are choosing

a new parallel computer, what measure is most relevant—speedup, batch

scaleup, or transaction scaleup?Why?

Answer: With increasing scale of operations, we expect that the number of transactions submitted per unit time increases. On the other hand,wewouldn’t

expect most of the individual transactions to grow longer, nor would we require

that a given transaction should execute more quickly now than it did before.

Hence transaction scale-up is the most relevant measure in this scenario.

18.8 Suppose a transaction is written in C with embedded SQL, and about 80 percent

of the time is spent in the SQL code, with the remaining 20 percent spent in C

code. How much speedup can one hope to attain if parallelism is used only for

the SQL code? Explain.

Answer: Since the part which cannot be parallelized takes 20% of the total

running time, the best speedup we can hope for has to be less than 5.

18.9 What are the factors that can work against linear scaleup in a transaction processing

system?Which of the factors are likely to be themost important in each

of the following architectures: shared memory, shared disk, and shared nothing?

Answer: Increasing contention for shared resources prevents linear scale-up

with increasing parallelism. In a shared memory system, contention for memory

(which implies bus contention) will result in falling scale-up with increasing

parallelism. In a shared disk system, it is contention for disk and bus access

which affects scale-up. In a shared-nothing system, inter-process communication

overheadswill be themain impeding factor. Since there is no shared memory,

acquiring locks, and other activities requiring message passing between

processes will take more time with increased parallelism.

18.10 Consider a bank that has a collection of sites, each running a database system.

Suppose the only way the databases interact is by electronic transfer of money

between one another. Would such a system qualify as a distributed database?

Why?

Answer: In a distributed system, all the sites typically run the same database

management software, and they share a global schema. Each site provides an

environment for execution of both global transactions initiated at remote sites

and local transactions. The system described in the question does not have

these properties, and hence it cannot qualify as a distributed database.

18.11 Consider a network based on dial-up phone lines, where sites communicate

periodically, such as every night. Such networks are often configured with a

server site and multiple client sites. The client sites connect only to the server,

and exchange data with other clients by storing data at the server and retrieving

data stored at the server by other clients. What is the advantage of such an

architecture over one where a site can exchange data with another site only by

first dialing it up?

Answer: With the central server, each site does not have to remember which

site to contact when a particular data item is to be requested. The central server

alone needs to remember this, so data items can be moved around easily, depending

onwhich sites accesswhich itemsmost frequently.Other house-keeping

tasks are also centralized rather than distributed, making the system easier to

develop and maintain. Of course there is the disadvantage of a total shutdown in case the server becomes unavailable. Even if it is running, it may become a

bottleneck because every request has to be routed via it.