DATABASE MANAGEMENTSYSTEMSSOLUTIONS MANUALRaghu Ramakrishnan et al.University of WisconsinMadison, WI, USACONTENTSPREFACE iii1 INTRODUCTION TO DATABASE SYSTEMS 12 THE ENTITY-RELATIONSHIP MODEL 53 THE RELATIONAL MODEL 144 RELATIONAL ALGEBRA AND CALCULUS 235 SQL: QUERIES, PROGRAMMING, TRIGGERS 406 QUERY-BY-EXAMPLE (QBE) 567 STORING DATA: DISKS AND FILES 658 FILE ORGANIZATIONS AND INDEXES 729 TREE-STRUCTURED INDEXING 7510 HASH-BASED INDEXING 8711 EXTERNAL SORTING 10512 EVALUATION OF RELATIONAL OPERATORS 10913 INTRODUCTION TO QUERY OPTIMIZATION 11814 A TYPICAL QUERY OPTIMIZER 119iii Database Management Systems Solutions Manual15 SCHEMA REFINEMENT AND NORMAL FORMS13416 PHYSICAL DATABASE DESIGN AND TUNING 14517 SECURITY 15818 TRANSACTION MANAGEMENT OVERVIEW 16319 CONCURRENCY CONTROL 16820 CRASH RECOVERY 18021 PARALLEL AND DISTRIBUTED DATABASES 190PREFACEIt is not every question that deserves an answer.Publius Syrus, 42 B.C.I hope that most of the questions in this book deserve an answer. 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 quantitative andproblem-solving type exercises. Answers to almost all chapter exercises are includedin this solutions manual for Chapters 1 through 19. Solutions for Chapters 20 through22 are currently unavailable.While 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, M.Chakrabarti, C. Chan, W. Chen, N. Cheung, D. Colwell, C. Fritz, V. Ganti, J. Gehrke,G. Glass, V. Gopalakrishnan, M. Higgins, T. Jasmin, M. Krishnaprasad, Y. Lin, C. Liu,M. Lusignan, H. Modi, S. Narayanan, D. Randolph, A. Ranganathan, J. Reminga, A.Therber, M. Thomas, Q. Wang, R. Wang, Z. Wang and J. Yuan. In addition, JamesHarrington and Martin Reames at Wisconsin and Nina Tang at Berkeley providedespecially detailed feedback.Several 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 sure it 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! If you discover a bug, please send me mail([email protected]) and I will update the manual promptly.The latest version of this solutions manual is distributed freely through the Web; goto the home page mentioned below to obtain a copy.iiiDatabase Management Systems Solutions ManualFor More InformationThe home page for this book is at URL:http://www.cs.wisc.edu/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 software. Since the solutions manual isdistributed electronically, all known errors are immediately fixed and no list of errors ismaintained. Instructors are advised to visit this site periodically; they can also registerat this site to be notified of important changes by email.1INTRODUCTION TODATABASE SYSTEMSExercise 1.1 Why would you choose a database system instead of simply storing datain operating system files? When would it make sense not to use a database system?Answer 1.1 A database is 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 a DBMS (databasemanagement system). The advantages of using a DBMS are:Data independence and efficient access. Database 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 optimization.Reduced application development time. Since the DBMS provides several impor-tant functions required by applications, such as concurrency control and crashrecovery, high level query facilities, etc., only application-specific code needs tobe written. Even this is facilitated by suites of application development toolsavailable from vendors for many database management systems.Data integrity and security. The view mechanism and the authorization facilitiesof a DBMS provide a powerful access control mechanism. Further, updates to thedata that violate the semantics of the data can be detected and rejected by theDBMS if users specify the appropriate integrity constraints.Data administration. By 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 etc.12 Chapter 1Concurrent access and crash recovery. A DBMS supports the notion of a trans-action, which is conceptually a single user’s sequential program. Users can writetransactions as if their programs were running in isolation against the database.The DBMS executes the actions of transactions in an interleaved fashion to obtaingood performance, but schedules them in such 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 a transaction-consistent state. 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 consistent.If 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 DBMS.Exercise 1.2