DATABASE MANAGEMENT SYSTEMS SOLUTIONS MANUAL …

1 DATABASE MANAGEMENTSYSTEMSSOLUTIONS MANUALTHIRD EDITIONR aghu RamakrishnanUniversity of WisconsinMadison, WI, USAJ ohannes GehrkeCornell UniversityIthaca, NY, USAJeff Derstadt, Scott Selikoff, and Lin ZhuCornell UniversityIthaca, NY, USACONTENTSPREFACEiii1 INTRODUCTION TO DATABASE SYSTEMS12 INTRODUCTION TO DATABASE DESIGN73 THERELATIONALMODEL224 relational ALGEBRA AND CALCULUS425 SQL: QUERIES, CONSTRAINTS, TRIGGERS596 DATABASE APPLICATION DEVELOPMENT907 INTERNET APPLICATIONS948 OVERVIEW OF STORAGE AND INDEXING1029 STORING DATA: DISKS AND FILES11310 TREE-STRUCTURED INDEXING12211 HASH-BASED INDEXING14112 OVERVIEW OF QUERY EVALUATION16613 EXTERNAL SORTING17514 EVALUATION OF relational OPERATORS181iiiDatabase MANAGEMENT SYSTEMS SOLUTIONS MANUAL Third Edition15 A TYPICAL QUERY OPTIMIZER19716 OVERVIEW OF TRANSACTION MANAGEMENT21817 CONCURRENCY CONTROL22818 CRASH RECOVERY24519 SCHEMA REFINEMENT AND NORMAL FORMS25820 PHYSICAL DATABASE design AND TUNING27821 SECURITY292 PREFACEIt is not every question that deserves an Syrus, 42 hope that most of the questions in this book deserve an answer.

2 The set of questionsis unusually extensive, and is designed to reinforce and deepen students understandingof the concepts covered in each chapter. There is a strong emphasis on quantitativeand problem-solving type I wrote some of the SOLUTIONS myself, most were written originally by studentsin the DATABASE classes at Wisconsin. I d like to thank the many students who helpedin developing and checking the SOLUTIONS to the exercises; this MANUAL would not beavailable without their contributions. In alphabetical order: X. Bao, S. Biao, , C. Chan, W. Chen, N. Cheung, D. Colwell, J. Derstadt, C. Fritz, , J.

3 Gehrke, G. Glass, V. Gopalakrishnan, M. Higgins, T. Jasmin, M. Krish-naprasad, Y. Lin, C. Liu, M. Lusignan, H. Modi, S. Narayanan, D. Randolph, , J. Reminga, A. Therber, M. Thomas, Q. Wang, R. Wang, Z. Wang andJ. Yuan. In addition, James Harrington and Martin Reames at Wisconsin and NinaTang at Berkeley provided especially detailed students contributed to each chapter s SOLUTIONS , and answers were subse-quently checked by me and by other students. This MANUAL has been in use for severalsemesters. I hope that it is now mostly accurate, but I m sureit still contains er-rors and omissions. If you are a student and you do not understand a particularsolution, contact your instructor; it may be that you are missing something, but itmay also be that the solution is incorrect!

4 If you discover a bug, please send me and I will update the MANUAL latest version of this SOLUTIONS MANUAL is distributed freely through the Web; goto the home page mentioned below to obtain a More InformationThe home page for this book is at URL:iiiDatabase MANAGEMENT SYSTEMS SOLUTIONS MANUAL Third ~dbbookThis page is frequently updated and contains information about the book, past andcurrent users, and the software. This page also contains a link to all known errors inthe book, the accompanying slides, and the the SOLUTIONS MANUAL isdistributed electronically, all known errors are immediately fixed and no list of errors are advised to visit this site periodically; they can also registerat this site to be notified of important changes by TO DATABASESYSTEMSE xercise would you choose a DATABASE system instead of simply storing datain operating system files?

5 When would it make sensenotto use a DATABASE system?Answer an integrated collection of data, usually so large that ithas to be stored on secondary storage devices such as disks or tapes. This data canbe maintained as a collection of operating system files, or stored in aDBMS(databasemanagement system). The advantages of using a DBMS are:Data independence and efficient application programs are in-dependent of the details of data representation and storage. The conceptual andexternal schemas provide independence from physical storage decisions and logicaldesign decisions respectively. In addition, a DBMS provides efficient storage andretrieval mechanisms, including support for very large files, index structures andquery application development the DBMS provides several impor-tant functions required by applications, such as concurrency control and crashrecovery, high level query facilities, etc.

6 , only application-specific code needs tobe written. Even this is facilitated by suites of application development toolsavailable from vendors for many DATABASE MANAGEMENT integrity and view mechanism and the authorization facilitiesof a DBMS provide a powerful access control mechanism. Further, updates to thedata that violate the semantics of thedata can be detected and rejected by theDBMS if users specify the appropriateintegrity providing a common umbrella for a large collection ofdata that is shared by several users, a DBMS facilitates maintenance and dataadministration tasks. A good DBA can effectively shield end-users from the choresof fine-tuning the data representation, periodic back-ups 1 Concurrent access and crash DBMS supports the notion of atrans-action, which is conceptually a single user s sequential program.

7 Users can writetransactions as if their programs were running in isolation against the DBMS executes the actions of transactions in an interleaved fashion to obtaingood performance, but schedules them insuch a way as to ensure that conflictingoperations are not permitted to proceed concurrently. Further, the DBMS main-tains a continuous log of the changes to the data, and if there is a system crash,it can restore the DATABASE to atransaction-consistentstate. That is, the actionsof incomplete transactions are undone, so that the DATABASE state reflects only theactions of completed transactions. Thus,if each complete transaction, executingalone, maintains the consistency criteria, then the DATABASE state after recoveryfrom a crash is these advantages are not important for the application at hand, using a collection offiles may be a better solution because of the increased cost and overhead of purchasingand maintaining a is logical data independence and why is it important?

8 Answer data independencemeans that users are shielded from changes inthe logical structure of the data, , changes in the choice of relations to be example, if a relation Students(sid, sname, gpa) is replaced by Studentnames(sid,sname) and Studentgpas(sid, gpa) for some reason, application programs that operateon the Students relation can be shielded from this change by defining a view Stu-dents(sid, sname, gpa) (as the natural join of Studentnames and Studentgpas). Thus,application programs that refer to Students need not be changed when the relation Stu-dents is replaced by the other two relations. The only change is that instead of storingStudents tuples, these tuples are computed as needed by using the view definition; thisis transparent to the application the difference between logical and physical data data independence means that users are shielded from changesin the logical structure of the data, while physical data independence insulates usersfrom changes in the physical storage of the data.

9 We saw an example of logical dataindependence in the answer to Exercise Consider the Students relation from thatexample (and now assume that it is not replaced by the two smaller relations). Wecould choose to store Students tuples in a heap file, with a clustered index on thesname field. Alternatively, we could choose to store it with an index on the gpa field,or to create indexes on both fields, or to store it as a file sorted by gpa. These storagealternatives are not visible to users, except in terms of improved performance, sincethey simply see a relation as a set of tuples. This is what is meant by physical to DATABASE Systems3 Exercise the difference between external, internal, and conceptual sche-mas.

10 How are these different schema layers related to the concepts of logical andphysical data independence?Answer schemas allows data access to be customized (and authorized)at the level of individual users or groups of users. Conceptual (logical) schemas de-scribes all the data that is actually stored in the DATABASE . While there are severalviews for a given DATABASE , there isexactly one conceptual schema toallusers. Internal(physical) schemas summarize how the relations described in the conceptual schemaare actually stored on disk (or other physical media).External schemas provide logical data independence, while conceptual schemas offerphysical data are the responsibilities of a DBA?