Database Management Systems ITLEducation Solutions Limited Research and Development Wing New Delhi Copyright © 2011 Dorling Kindersley (India) Pvt. Ltd. Licensees of Pearson Education in South Asia No part of this eBook may be used or reproduced in any manner whatsoever without the publisherıs prior written consent. This eBook may or may not include all assets that were part of the print version. The publisher reserves the right to remove any material present in this eBook at any time. ISBN 9788131760802 eISBN 9788131797600 Head Office: A-8(A), Sector 62, Knowledge Boulevard, 7th Floor, NOIDA 201 309, India Registered Office: 11 Local Shopping Centre, Panchsheel Park, New Delhi 110 017, India Contents Preface v 1. Database System 1 2. Conceptual Modeling 17 3. Relational Model 42 4. Relational Algebra and Calculus 63 5. Structured Query Language 83 6. Relational Database Design 114 7. Data Storage and Indexing 142 8. Query Processing and Optimization 168 9. Introduction to Transaction Processing 198 10. Concurrency Control Techniques 213 11. Database Recovery System 233 12. Database Security 248 13. Database System Architecture 261 14. Data Warehousing, OLAP, and Data Mining 277 15. Information Retrieval 295 16. Miscellaneous Questions 302 Index 325 Prelims.indd 3 8/17/2011 4:37:13 PM This page is intentionally left blank. Prelims.indd 4 8/17/2011 4:37:13 PM Preface A s organizations strive to excel in a modern competitive environment, managing information acquires greater relevance. Database systems now play a vital role in the effective management of informa- tion. Database being an essential ingredient of modern computing systems, the subject Database Management Systems is compulsory for students enrolled in various computer science courses in most universities. The book Database Management Systems aims to provide an in-depth knowledge of most important aspects of database systems in an easy-to-understand question-and-answer format. The book comprises questions and their corresponding answers on fundamental concepts like data- base design, languages and implementation as well as advanced concepts like distributed databases and query processing and optimization. In addition, some miscellaneous questions on emerging tech- nologies like object-based databases and XML are also included. The organized and accessible format allows students to quickly fi nd questions on specifi c topics. The book Database Management Systems is a part of series named Express Learning Series, which has a number of books designed as quick reference guides. Unique Features 1. D esigned as a student friendly self-learning guide. The book is written in a clear, concise and lucid manner. 2. Easy-to-understand question-and-answer format. 3. Includes previously asked as well as new questions organized in chapters. 4. All types of questions including MCQs, short and long questions are covered. 5. Solutions to numerical questions asked at examinations are provided. 6. All ideas and concepts are presented with clear examples. 7. Text is well structured and well supported with suitable diagrams. 8. Inter-chapter dependencies are kept to a minimum. Chapter Organization All the questions–answers are organized into 16 chapters. The outline of the chapters is as follows:  Chapter 1 provides an introduction of database and database management system, its advan- tages over the traditional fi le system, the DBMS environment, various data models and the steps involved in database design.  Chapter 2 deals with conceptual modeling using E-R and the enhanced E-R model. It represents all the concepts with the help of an example of the Online Book database.  Chapter 3 describes the basic concepts of the relational model, which is the most commonly used data model. It also covers integrity constraints and deals with constraint violations. ‰‰Chapter 4 discusses two formal query languages, namely, relational algebra and relational calcu- lus. The concepts of relational algebra and calculus are explained in a simple way that helps in  the easy understanding of these query languages.  ‰‰Chapter 5 discusses the structured query language (SQL), which is used as the standard query  language in most of the commercial databases. ‰‰Chapter 6 deals with normalization, which is the most important process in database design. It  begins with various issues that are confronted while designing a database schema. It then dis- cusses the formal methodology (normalization) that is used to resolve these issues and design an  efficient database system.  ‰‰Chapter 7 covers the concepts of physical database design including database storage and index- ing. It describes the primary methods of organizing files on the disks and various indexing tech- niques that help in fast retrieval of data. ‰‰Chapter 8 introduces the basics of query processing and optimization. It provides an understand- ing of how queries are evaluated and how data are retrieved from the database. ‰‰Chapter 9 introduces the properties of transaction including atomicity, consistency, isolation and  durability. It then discusses fundamentals of transaction processing and introduces the concept  of serializability. ‰‰Chapter 10 covers a number of concurrency control techniques including locking, timestamping  and optimistic concurrency control technique. It also covers deadlock handling. ‰‰Chapter 11 describes the database recovery system to ensure the normal execution of transac- tions regardless of any type of system failure. It discusses various recovery techniques such as  system log, checkpoints, etc.  ‰‰Chapter 12 focuses on database security and presents various security issues, the types of threats  to the database and the role of DBA in implementing database security. In addition, it discusses  how the user access to database is controlled. ‰‰Chapter 13 explores the concepts of database storage, query processing, transaction manage- ment, concurrency control and recovery in distributed database systems. ‰‰Chapter 14 introduces data warehousing, online transaction processing (OLAP) and data mining. ‰‰Chapter 15 discusses information retrieval techniques to extract information from unstructured  textual data along with the retrieval techniques used in Web search engines. ‰‰Chapter 16 covers miscellaneous topics such as object-relational and object-oriented databases,  XML and four leading database systems that include PostgreSQL, Oracle, Microsoft SQL Server  and IBM DB2.  Acknowledgements ‰‰Our publisher, Pearson Education, their editorial team and panel reviewers for their valuable  contributions toward content enrichment. ‰‰Our technical and editorial consultants for devoting their precious time to improve the quality of  the book. ‰‰Our entire research and development team who have put in their sincere efforts to bring out a  high-quality book. Feedback For any suggestions and comments about this book, please send an e-mail to [email protected]. Hope you enjoy reading this book as much as we have enjoyed writing it. Rohit KhuRana Founder and CEO ITL ESL Prelims.indd 6 8/17/2011 4:37:13 PM 1 Database System 1. Define the term database. Ans: A database can be definedas a collection of related data from which users can efficiently retrieve the desired information. A database can be anything from a simple collection of roll numbers, names, addresses and phone numbers of students to a complex collection of sound, images and even video or filmclippings. Though databases are generally computerized, instances of non-computerized databases from everyday life can be cited in abundance. A dictionary, a phone book, a collection of recipes and a TV guide are examples of non-computerized databases. The examples of computerized databases include customer files,employee rosters, books catalog, equipment inventories and sales transactions. 2. What do you mean by a Database Management System? Ans: A Database Management System (DBMS) is an integrated set of programs used to cre- ate and maintain a database. The main objective of a DBMS is to provide a convenient and effective method of defining, storing, retrieving and manipulating the data contained in the database 3. What is a file-processing system? What are the disadvantages of a file-processing sys- tem that led to the development of the database system? Ans: In the file-processing system, the data are stored in the form of files,and a number of appli- cation programs are written by programmers to add, modify, delete and retrieve data to and from appropriate files.New application programs are written as and when needed by the organization. For example, consider a bookstore that uses a file-processingsystem to keep track of all the available books. The system maintains a filenamed to store the information related to books. This infor- BOOK mation includes the book title, ISBN, price, year of publishing, copyright date, category, number of pages, name of the author and the name and address of the publisher. In addition, the system has many application programs that allow users to manipulate the infor- mation stored in the file. For example, a system may contain programs to add information BOOK about a new book, modify any existing book information, print the details of books according to their categories, etc. If a need arises to keep additional information about the publishers of the books, which include the phone number and email id, the system creates a new file,say , which PUBLISHER DBMS_CH_01.indd 1 7/9/2011 4:02:49 PM 2 Database Management Systems includes the name, address, phone number and email id of the publishers. New application programs are written and added to the system to manipulate the information in the file.In this PUBLISHER way, as time goes by, more files and application programs are added to the system The file-processingsystem has a number of disadvantages that lead to the development of database systems. These disadvantages are given below: q Same information may be duplicated in several files.For example, the name and the address of the publisher are stored in the fileas well as in the file.This duplication of BOOK PUBLISHER data is known as data redundancy, which leads to wastage of storage space. The other prob- lem with the file-processingsystem is that the data may not be updated consistently. Suppose a publisher requests for a change in his address. Since the address of the publisher is stored in the as well as the file,both the filesmust be updated. If the address of the pub- BOOK PUBLISHER lisher is not modifiedin any of the two files,then the same publisher will have different addresses in two different files. This is known asdata inconsistency. q In any application, there are certain data integrity rules that need to be maintained. These rules could be in the form of certain conditions or constraints. In a file-processingsystem, all these rules need to be explicitly programmed in all application programs that use that particular data item. For example, the integrity rule that each book should have a book title has to be imple- mented in all the application programs separately that use the file.In addition, when new BOOK constraints are to be enforced, all the application programs should be changed accordingly. q The file-processingsystem lacks the insulation between program and data. This is because the file structure is embedded in the application program itself; thus, it is difficult to change the structure of a fileas it requires changing all the application programs accessing it. For example, an application program in C++ definesthe filestructure using the keyword or . struct class Suppose the data type of the fieldISBN is changed from string to number, changes have to be made in all the application programs that are accessing the file BOOK q Handling new queries is difficult,since it requires change in the existing application programs or requires a new application program. For example, suppose a need arises to print the details of all the textbooks published by a particular publisher. One way to handle this request is to use the existing application program that prints the details of the books according to their categories, and then manually generate the list of textbooks published by a particular publisher. Obviously, it is unacceptable. Alternatively, the programmer is requested to write a new application program. Suppose such a new application program is written. Now suppose after some time, a request arises to filterthe list of textbooks with a price greater than $50. Then again we have to write a new application program. q Since many users are involved in creating filesand writing application programs, the various files in the system may have different filestructures. Moreover, the programmers may choose differ- ent programming languages to write application programs. q Since application programs are added in an unplanned manner, due to which the details of each fileare easily available to every user. Thus, the file-processingsystem lacks the security feature. 4. Explain DBMS catalog and metadata. Ans: To provide a high degree of data independence, the definitionor the description of the data- base structure (structure of each file,the type and storage format of each data item) and various con- straints on the data are stored separately in a table. This table is known as the DBMS catalog. The information contained in the catalog is called the metadata (data about data). DBMS_CH_01.indd 2 7/9/2011 4:02:49 PM Database System 3 5. What do you understand by the term data abstraction? Ans: The property of DBMS that allows program-data independence is known as data abstrac- tion. Data abstraction allows the database system to provide an abstract view of the data to its users without giving the physical storage and implementation details. 6. Discuss the advantages of a database system. Explain the various cost and risk factors involved in implementing a database system. Ans: The main advantage of DBMS is centralized data management where the data are stored at a centralized location and are shared among multiple users. The centralized nature of the database sys- tem provides several advantages, which overcome the limitations of the conventional file-processing system. These advantages are as follows: q Controlled data redundancy: During database design, various files are integrated, and each logical data item is stored at a central location. This eliminates replicating the data item in differ- ent files, and ensures consistency and saves the storage space q Enforcing data integrity: In the database approach, enforcing data integrity is much easier. Various integrity constraints are identified by the database designer during the database design q Data sharing: The data stored in the database can be shared among multiple users or application programs. Due to shared data, it is possible to satisfy the data requirements of the new applica- tions without having to create any additional data or with minimal modification q Ease of application development: The application programmer develops the application pro- grams according to the needs of the users. The other issues like concurrent access, security, data integrity, etc. are handled by the DBMS itself. This makes application development an easier task. q Data security: The DBMS ensures that the only means of access to the database is through an authorized channel. To ensure security, a DBMS provides security tools such as user codes and passwords. q Multiple user interfaces: DBMS provides different types of interfaces such as query languages, application program interfaces and graphical user interfaces (GUI) that include forms-style and menu-driven interfaces. q Backup and recovery: The DBMS provides a backup and recovery subsystem, which is respon- sible for recovery from hardware and software failures. In addition to centralized data management, DBMS also has some other advantages as follows: q Program-data independence: The independence between the programs and the data is known as program-data independence. It allows changing the structure of the database without making any changes in the application programs that use the database. q Data abstraction: The property of DBMS that allows program-data independence is known as data abstraction. Data abstraction allows the database system to provide an abstract view of the data to its users without giving the physical storage and implementation details. q Supports multiple views of the data: A database can be accessed by many users and each of them may have a different perspective or view of the data. A database system provides a facility to definedifferent views of the data for different users. A view is a subset of the database that contains virtual data derived from the database files but it does not exist in physical form The various cost and risk factors involved in implementing a database system are: q High cost: Installing a new database system may require investment in hardware and software. The DBMS requires more main memory and disk storage. Moreover, DBMS is quite expensive. DBMS_CH_01.indd 3 7/9/2011 4:02:49 PM