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 v
 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
 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 5
 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.
 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. • 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:
1 16 17 90
7 89 412 8
C H A P T E R 2