Uploads Notes btech 5sem ece DBMS Korth sol PDF

Preview

Summary

it's all notes of DBMS...

Description

INSTRUCTOR’S MANUAL TO ACCOMPANY ALPHA (incomplete) VERSION DATED: August 28, 2001

Database System Concepts Fourth Edition

Abraham Silberschatz Bell Laboratories Henry F. Korth Bell Laboratories S. Sudarshan Indian Institute of Technology, Bombay

c Copyright 2001 A. Silberschatz, H. Korth, and S. Sudarshan

Contents

Preface 1 Chapter 1

Introduction

Exercises 4

Chapter 2

Entity Relationship Model

Exercises 9

Chapter 3

Relational Model

Exercises 30

Chapter 4

SQL

Exercises 42

Chapter 5

Other Relational Languages

Exercises 58

Chapter 6

Integrity and Security

Exercises 74

iii

iv

Contents

Chapter 7

Relational-Database Design

Exercises 84

Chapter 8

Object-Oriented Databases

Exercises 98

Chapter 9

Object-Relational Databases

Exercises 109

Chapter 10

XML

Exercises 119

Chapter 11

Storage and File Structure

Exercises 129

Chapter 12

Indexing and Hashing

Exercises 141

Chapter 13

Query Processing

Exercises 155

Chapter 14

Query Optimization

Exercises 166

Chapter 15

Transactions

Exercises 175

Chapter 16

Concurrency Control

Exercises 182

Chapter 17

Recovery System

Exercises 194

Contents

Chapter 18

Database System Architectures

Exercises 201

Chapter 19

Distributed Databases

Exercises 208

Chapter 20

Parallel Databases

Exercises 217

Chapter 21

Application Development and Administration

Exercises 225

Chapter 22

Advanced Querying and Information Retrieval

Exercises 232

Chapter 23

Advanced Data Types and New Applications

Exercises 241

Chapter 24

Advanced Transaction Processing

Exercises 249

v

Preface

This volume is an instructor’s manual for the 4th edition of Database System Concepts by Abraham Silberschatz, Henry F. Korth and S. Sudarshan. It contains answers to the exercises at the end of each chapter of the book. Before providing answers to the exercises for each chapter, we include a few remarks about the chapter. The nature of these remarks vary. They include explanations of the inclusion or omission of certain material, and remarks on how we teach the chapter in our own courses. The remarks also include suggestions on material to skip if time is at a premium, and tips on software and supplementary material that can be used for programming exercises. Beginning with this edition, solutions for some problems have been made available on the Web. These problems have been marked with a “ * ” in the instructor’s manual. The Web home page of the book, at http://www.bell-labs.com/topic/books/db-book, contains a variety of useful information, including up-to-date errata, online appendices describing the network data model, the hierarchical data model, and advanced relational database design, and model course syllabi. We will periodically update the page with supplementary material that may be of use to teachers and students. We provide a mailing list through which users can communicate among themselves and with us. If you wish to be on the list, please send an email to [email protected] including your name, affiliation, title, and electronic mail address. We would appreciate it if you would notify us of any errors or omissions in the book, as well as in the instructor’s manual. Although we have tried to produce an instructor’s manual which will aid all of the users of our book as much as possible, there can always be improvements. These could include improved answers, additional questions, sample test questions, programming projects, suggestions on alternative orders of presentation of the material, additional references, and so on. If you would like to suggest any such improvements to the book or the instructor’s manual, we would be glad to hear from you. Internet electronic mail should 1

2

Preface

be addressed to [email protected]. Physical mail may be sent to Avi Silberschatz, Bell Laboratories, Room 2T-310, 600 Mountain Avenue, Murray Hill, NJ 07974, USA. All contributions that we make use of will, of course, be properly credited to their contributor. Nilesh Dalvi, Sumit Sanghai, Gaurav Bhalotia and Arvind Hulgeri did the bulk of the work in preparing the instructors manual for the 4th edition. This manual is derived from the manuals for the earlier editions. The manual for the 3rd edition was prepared by K. V. Raghavan with help from Prateek R. Kapadia, Sara Strandtman helped with the instructor manual for the 2nd and 3rd editions, while Greg Speegle and Dawn Bezviner helped us to prepare the instructor’s manual for the 1st edition. A. S. H. F. K. S. S. Instructor Manual Version 4.0.0

C H A P T

E R

1

Introduction

Chapter 1 provides a general overview of the nature and purpose of database systems. The most important concept in this chapter is that database systems allow data to be treated at a high level of abstraction. Thus, database systems differ significantly from the file systems and general purpose programming environments with which students are already familiar. Another important aspect of the chapter is to provide motivation for the use of database systems as opposed to application programs built on top of file systems. Thus, the chapter motivates what the student will be studying in the rest of the course. The idea of abstraction in database systems deserves emphasis throughout, not just in discussion of Section 1.3. The overview of the structure of databases, starting from Section 1.4 is, of necessity, rather brief, and is meant only to give the student a rough idea of some of the concepts. The student may not initially be able to fully appreciate the concepts described here, but should be able to do so by the end of the course. The specifics of the E-R, relational, and object-oriented models are covered in later chapters. These models can be used in Chapter 1 to reinforce the concept of abstraction, with syntactic details deferred to later in the course. If students have already had a course in operating systems, it is worthwhile to point out how the OS and DBMS are related. It is useful also to differentiate between concurrency as it is taught in operating systems courses (with an orientation towards files, processes, and physical resources) and database concurrency control (with an orientation towards granularity finer than the file level, recoverable transactions, and resources accessed associatively rather than physically). If students are familiar with a particular operating system, that OS’s approach to concurrent file access may be used for illustration.

3

4

Chapter 1

Introduction

Exercises 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, whereas 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.

Exercises

b. c. d. e.

5

integrity enforcement. security enforcement. backup and recovery. 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.

6

Chapter 1

Introduction

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.

b.

• 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. • 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: 1 7

16 89

17 90 412 8

C H A P T

E R

2

Entity Relationship Model

This chapter introduces the entity-relationship model in detail. The chapter covers numerous features of the model, several of which can be omitted depending on the planned coverage of the course. Weak entity sets (Section 2.6), design constraints (Section 2.7.4) and aggregation (Section 2.7.5), and the corresponding subsections of Section 2.9 (Reduction of an E-R Schema to Tables) can be omitted if time is short. We recommend covering specialization (Section 2.7.1) at least in some detail, since it is an important concept for object-oriented databases (Chapter 8). The E-R model itself and E-R diagrams are used often in the text. It is important that students become comfortable with them. The E-R model is an excellent context for the introduction of students to the complexity of database design. For a given enterprise there are often a wide variety of E-R designs. Although some choices are arbitrary, it is often the case that one design is inherently superior to another. Several of the exercises illustrate this point. The evaluation of the goodness of an E-R design requires an understanding of the enterprise being modeled and the applications to be run. It is often possible to lead students into a debate of the relative merits of competing designs and thus illustrate by example that understanding the application is often the hardest part of database design. Considerable emphasis is placed on the construction of tables from E-R diagrams. This serves to build intuition for the discussion of the relational model in the subsequent chapters. It also serves to ground abstract concepts of entities and relationships into the more concrete concepts of relations. Several other texts places this material along with the relational data model, rather than in the E-R model chapter. Our motivation for placing this material here is help students to appreciate how E-R data models get used in reality, while studying the E-R model rather than later on. The material on conversion of E-R diagrams to tables in the book is rather brief in some places, the book slides provide better coverage of details that have been left implicit in the book. 7

8

Chapter 2

Entity Relationship Model

Changes from 3rd edition: In the fourth edition we have updated several examples, including ternary relations (employee, branch, job instead of customer, loan, branch) and aggregation (manages instead of loan-officer), to make them more realistic. We have also added more examples, for instance for specialization we use person, customer and employee as the main example, instead of account, checking-account and savings-account, which also makes the example more realistic. We have replaced the US centric social-security by the more global (and more realistic) customer-id and employee-id. We have added notation to make disjointedness constraints and total participation explicit (overlapping and partial participation are the default). We have introduced alternative E-R notations since many real world applications use alternative notations. We have also provided a brief introduction to UML class diagrams, which are being used increasingly in place of E-R diagrams, in tools such as Oracle designer. We have dropped coverage of existence dependencies since total participation constraints provide a very similar constraint. The distinction between total participation and existence dependencies is too minor to be of practical use, and only confuses students. Design issues are discussed in more detail.

Exercises

model

address driver-id

9

license

name person

owns

year location

car report-number

driver

participated

date

accident

damage-amount

Figure 2.1

E-R diagram for a Car-insurance company.

Exercises 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: See Figure 2.1 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: See Figure 2.2 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: See Figure 2...