Prepare for software Interviews online

Download:
http://www.2shared.com/document/1JjVB9Lw/DBMS_Korth_sol.html

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
iiiiv 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 194Contents 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 249Preface
This volume is an instructor’s manual for the 4
th
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
db-book@research.bell-labs.com
including your name, afﬁliation, 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
12 Preface
be addressed to db-book@research.bell-labs.com. 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 4
th
edition. This manual is
derived from the manuals for the earlier editions. The manual for the 3
rd
edition was
prepared by K. V. Raghavan with help from Prateek R. Kapadia, Sara Strandtman
helped with the instructor manual for the 2
nd
and 3
rd
editions, while Greg Speegle
and Dawn Bezviner helped us to prepare the instructor’s manual for the 1
st
edition.
A. S.
H. F. K.
S. S.
Instructor Manual Version 4.0.0C 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 signiﬁcantly
from the ﬁle 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 ﬁle 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 speciﬁcs 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
ﬁles, processes, and physical resources) and database concurrency control (with an
orientation towards granularity ﬁner than the ﬁle 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 ﬁle access may be
used for illustration.
34 Chapter 1 Introduction
Exercises
1.1 List four signiﬁcant differences between a ﬁle-processing system and a DBMS.
Answer: Some main differences between a database management system and
a ﬁle-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 ﬁle-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 ﬁle-processing
system may not be readable by another program.
• A database management system is designed to allow ﬂexible access to data
(i.e., queries), whereas a ﬁle-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 ﬁle-processing system is usually
designed to allow one or more programs to access different data ﬁles at
the same time. In a ﬁle-processing system, a ﬁle can be accessed by two
programs concurrently only if both programs have read-only access to the
ﬁle.
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 modiﬁ-
cations include changing from unblocked to blocked record storage, or from
sequential to random access ﬁles.
• Logical data independence is the ability to modify the conceptual scheme
without making it necessary to rewrite application programs. Such a modi-
ﬁcation might be adding a ﬁeld to a record; an application program’s view
hides this change from the program.
1.4 List ﬁve 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 ﬁve responsibilities:
a. interaction with the ﬁle 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 ﬁle manager interaction then
nothing stored in the ﬁles can be retrieved.
b. Consistency constraints may not be satisﬁed, account balances could go below the minimum allowed, employees could earn too much overtime (e.g.,
hours > 80) or, airline pilots may ﬂy 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 ﬁnd 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
reﬂected due to simultaneous withdrawals and deposits, and so on.
1.5 What are ﬁve main functions of a database administrator?
Answer: Five main functions of a database administrator are:
• To create the scheme deﬁnition
• To deﬁne 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 classiﬁcation:
• 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
ﬁrst.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:
• Deﬁne the high level requirements of the enterprise (this step generates a
document known as the system requirements speciﬁcation.)
• Deﬁne a model containing all appropriate types of data and data relationships.
• Deﬁne the integrity constraints on the data.
• Deﬁne 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) deﬁne 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 speciﬁed 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 8C 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.
78 Chapter 2 Entity Relationship Model
Changes from 3
rd
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-ofﬁcer), 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 9
person owns car
participated accident
address
damage-amount
model
license year
name
report-number
date
location
driver-id
driver
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 ofﬁce 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 identiﬁcation 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 ofﬁce. Document all assumptions
that you make about the mapping constraints.
Answer: See Figure 2.3.
In the answer given here, the main entity sets are student, course, course-offering,10 Chapter 2 Entity Relationship Model
specialization
doctors
test_name date time result
ss#
name
name
patients
Dr−Patient
insurance
date−admitted
date−checked−out
dss#
test−log
test
test_id
performed_by
Figure 2.2 E-R diagram for a hospital.
program
course−
offerings
dept title
course
courseno
title
credits
syllabus
prerequisite
maincourse
requires
secno
is
offered
student
name
grade
teaches
year semester
time room
enrols
sid
instructor
iid name
Figure 2.3 E-R diagram for a university.
and instructor. The entity set course-offering is a weak entity set dependent on
course. The assumptions made are :
a. a class meets only at one particular place and time. This E-R diagram cannot
model a class meeting at different places at different times.
b. There is no guarantee that the database does not have two classes meeting
at the same place and time.
2.5 Consider a database used to record the marks that students get in different exams of different course offerings.Exercises 11
course−
offerings
secno
courseno
exam
name place
time
marks
program
eid
student
name
year semester
time room
takes
sid
Figure 2.4 E-R diagram for marks database.
a. Construct an E-R diagram that models exams as entities, and uses a ternary
relationship, for the above database.
b. Construct an alternative E-R diagram that uses only a binary relationship
between students and course-offerings. Make sure that only one relationship
exists between a particular student and course-offering pair, yet you can
represent the marks that a student gets in different exams of a course offering.
Answer:
a. See Figure 2.4
b. See Figure 2.5
2.6 Construct appropriate tables for each of the E-R diagrams in Exercises 2.2 to
2.4.
Answer:
a. Car insurance tables:
person (driver-id, name, address)
car (license, year, model)
accident (report-number, date, location)
participated(driver-id, license, report-number, damage-amount)
b. Hospital tables:
patients (patient-id, name, insurance, date-admitted, date-checked-out)
doctors (doctor-id, name, specialization)
test (testid, testname, date, time, result)
doctor-patient (patient-id, doctor-id)
test-log (testid, patient-id) performed-by (testid, doctor-id)12 Chapter 2 Entity Relationship Model
course−
offerings
secno
courseno
program
exam
name place
time
examof
marks
student
name
year semester
time room
takes
sid
Figure 2.5 Another E-R diagram for marks database.
c. University registrar’s tables:
student (student-id, name, program)
course (courseno, title, syllabus, credits)
course-offering (courseno, secno, year, semester, time, room)
instructor (instructor-id, name, dept, title)
enrols (student-id, courseno, secno, semester, year, grade)
teaches (courseno, secno, semester, year, instructor-id)
requires (maincourse, prerequisite)
2.7 Design an E-R diagram for keeping track of the exploits of your favourite sports
team. You should store the matches played, the scores in each match, the players
in each match and individual player statistics for each match. Summary statistics should be modeled as derived attributes.
Answer: See Figure 2.6
2.8 Extend the E-R diagram of the previous question to track the same information
for all teams in a league.
Answer: See Figure 2.7 Note that a player can stay in only one team during a
season.
2.9 Explain the difference between a weak and a strong entity set.
Answer: A strong entity set has a primary key. All tuples in the set are distinguishable by that key. A weak entity set has no primary key unless attributes of
the strong entity set on which it depends are included. Tuples in a weak entity
set are partitioned according to their relationship with tuples in a strong entityExercises 13
date matchid stadium
match player
name age
played
season_score
opponent
own _score opp_score score
Figure 2.6 E-R diagram for favourite team statistics.
match player
name age
played
season_score
date
matchid stadium score
team
score team_played player_of
result
name ranking
Figure 2.7 E-R diagram for all teams statistics.
set. Tuples within each partition are distinguishable by a discriminator, which
is a set of attributes.
2.10 We can convert any weak entity set to a strong entity set by simply adding appropriate attributes. Why, then, do we have weak entity sets?
Answer: We have weak entities for several reasons:
• We want to avoid the data duplication and consequent possible inconsistencies caused by duplicating the key of the strong entity.
• Weak entities reﬂect the logical structure of an entity being dependent on
another entity.
• Weak entities can be deleted automatically when their strong entity is deleted.
• Weak entities can be stored physically with their strong entities.
2.11 Deﬁne the concept of aggregation. Give two examples of where this concept is
useful.14 Chapter 2 Entity Relationship Model
name name
name
employee works−in project
deadline
requires
machinery
Figure 2.8 E-R diagram Example 1 of aggregation.
manufacturer distributor tie−up
name tie−up−date name
product
name
distribute
Figure 2.9 E-R diagram Example 2 of aggregation.
Answer: Aggregation is an abstraction through which relationships are treated
as higher-level entities. Thus the relationship between entities A and B is treated
as if it were an entity C. Some examples of this are:
a. Employees work for projects. An employee working for a particular project
uses various machinery. See Figure 2.8
b. Manufacturers have tie-ups with distributors to distribute products. Each
tie-up has speciﬁed for it the set of products which are to be distributed. See
Figure 2.9Exercises 15
basketID
email
basket-of
ISBN
code
name
URL
address
name address phone
URL
publisher
written-by published-by
title
price
number
book
contains
phone
customer
address
name
phone
stocks warehouse
address
number
author
year
shopping-basket
Figure 2.10 E-R diagram for Exercise 2.12.
2.12 Consider the E-R diagram in Figure 2.10, which models an online bookstore.
a. List the entity sets and their primary keys.
b. Suppose the bookstore adds music cassettes and compact disks to its collection. The same music item may be present in cassette or compact disk
format, with differing prices. Extend the E-R diagram to model this addition, ignoring the effect on shopping baskets.
c. Now extend the E-R diagram, using generalization, to model the case where
a shopping basket may contain any combination of books, music cassettes,
or compact disks.
Answer:
2.13 Consider an E-R diagram in which the same entity set appears several times.
Why is allowing this redundancy a bad practice that one should avoid whenever
possible?
Answer: By using one entity set many times we are missing relationships in16 Chapter 2 Entity Relationship Model
ss# name
takes class
ss# name
dept
student
student
plays
sport
courseno
teamname
Figure 2.11 E-R diagram with entity duplication.
the model. For example, in the E-R diagram in Figure 2.11: the students taking
classes are the same students who are athletes, but this model will not show
that.
2.14 Consider a university database for the scheduling of classrooms for ﬁnal exams.
This database could be modeled as the single entity set exam, with attributes
course-name, section-number, room-number, and time. Alternatively, one or more
additional entity sets could be deﬁned, along with relationship sets to replace
some of the attributes of the exam entity set, as
• course with attributes name, department, and c-number
• section with attributes s-number and enrollment, and dependent as a weak
entity set on course
• room with attributes r-number, capacity, and building
a. Show an E-R diagram illustrating the use of all three additional entity sets
listed.
b. Explain what application characteristics would inﬂuence a decision to include or not to include each of the additional entity sets.
Answer:
a. See Figure 2.12
b. The additional entity sets are useful if we wish to store their attributes as
part of the database. For the course entity set, we have chosen to include
three attributes. If only the primary key (c-number) were included, and if
courses have only one section, then it would be appropriate to replace the
course (and section) entity sets by an attribute (c-number) of exam. The reason
it is undesirable to have multiple attributes of course as attributes of exam is
that it would then be difﬁcult to maintain data on the courses, particularly
if a course has no exam or several exams. Similar remarks apply to the room
entity set.Exercises 17
name
section for
time
department
c-number
section of
s-number enrollment
course
room in exam
r-number capacity building
exam-id
Figure 2.12 E-R diagram for exam scheduling.
2.15 When designing an E-R diagram for a particular enterprise, you have several
alternatives from which to choose.
a. What criteria should you consider in making the appropriate choice?
b. Design three alternative E-R diagrams to represent the university registrar’s
ofﬁce of Exercise 2.4. List the merits of each. Argue in favor of one of the
alternatives.
Answer:
a. The criteria to use are intuitive design, accurate expression of the real-world
concept and efﬁciency. A model which clearly outlines the objects and relationships in an intuitive manner is better than one which does not, because
it is easier to use and easier to change. Deciding between an attribute and
an entity set to represent an object, and deciding between an entity set and
relationship set, inﬂuence the accuracy with which the real-world concept
is expressed. If the right design choice is not made, inconsistency and/or
loss of information will result. A model which can be implemented in an
efﬁcient manner is to be preferred for obvious reasons.
b. Consider three different alternatives for the problem in Exercise 2.4.
• See Figure 2.13
• See Figure 2.14
• See Figure 2.15
Each alternative has merits, depending on the intended use of the database.
Scheme 2.13 has been seen earlier. Scheme 2.15 does not require a separate
entity for prerequisites. However, it will be difﬁcult to store all the prerequisites(being a multi-valued attribute). Scheme 2.14 treats prerequisites as
well as classrooms as separate entities, making it useful for gathering data
about prerequisites and room usage. Scheme 2.13 is in between the others,
in that it treats prerequisites as separate entities but not classrooms. Since a
registrar’s ofﬁce probably has to answer general questions about the number of classes a student is taking or what are all the prerequisites of a course,
or where a speciﬁc class meets, scheme 2.14 is probably the best choice.18 Chapter 2 Entity Relationship Model
program
course−
offerings
dept title
course
courseno
title
credits
syllabus
prerequisite
maincourse
requires
secno
is
offered
student
name
grade
teaches
year semester
time room
enrols
sid
instructor
iid name
Figure 2.13 E-R diagram for University(a) .
program
course−
offerings
dept title
course
courseno
title
credits
syllabus
prerequisite
maincourse
requires
secno
is
offered
meetsin
room
room_no building
iss#
instructor
name
student
ss# name
grade
teaches
year semester
time
enrols
Figure 2.14 E-R diagram for University(b).Exercises 19
program
course−
offerings
dept title
course
courseno
title
credits
syllabus
secno
is
offered
prerequisite
iss#
instructor
name
student
ss# name
grade
teaches
year semester
time room
enrols
Figure 2.15 E-R diagram for University(c).
2.16 An E-R diagram can be viewed as a graph. What do the following mean in terms
of the structure of an enterprise schema?
a. The graph is disconnected.
b. The graph is acyclic.
Answer:
a. If a pair of entity sets are connected by a path in an E-R diagram, the entity sets are related, though perhaps indirectly. A disconnected graph implies that there are pairs of entity sets that are unrelated to each other. If we
split the graph into connected components, we have, in effect, a separate
database corresponding to each connected component.
b. As indicated in the answer to the previous part, a path in the graph between
a pair of entity sets indicates a (possibly indirect) relationship between the
two entity sets. If there is a cycle in the graph then every pair of entity sets
on the cycle are related to each other in at least two distinct ways. If the E-R
diagram is acyclic then there is a unique path between every pair of entity
sets and, thus, a unique relationship between every pair of entity sets.
2.17 In Section 2.4.3, we represented a ternary relationship (Figure 2.16a) using binary relationships, as shown in Figure 2.16b. Consider the alternative shown in
Figure 2.16c. Discuss the relative merits of these two alternative representations
of a ternary relationship by binary relationships.
Answer: The model of Figure 2.16c will not be able to represent all ternary
relationships. Consider the ABC relationship set below.20 Chapter 2 Entity Relationship Model
R
R
B
R
A
RC
B
A
C
R
1
R
R
2
3
A
B C
B C
A
E
(c)
(b)
(a)
Figure 2.16 E-R diagram for Exercise 2.17 (attributes not shown.)
A B C
1 2 3
4 2 7
4 8 3
If ABC is broken into three relationships sets AB, BC and AC, the three will
imply that the relation (4, 2, 3) is a part of ABC.
2.18 Consider the representation of a ternary relationship using binary relationships
as described in Section 2.4.3 (shown in Figure 2.16b.)
a. Show a simple instance of E, A, B , C, RA, RB, and RC that cannot correspond to any instance of A, B, C, and R.
b. Modify the E-R diagram of Figure 2.16b to introduce constraints that will
guarantee that any instance of E, A, B , C, RA, RB, and RC that satisﬁes the
constraints will correspond to an instance of A, B, C, and R.
c. Modify the translation above to handle total participation constraints on the
ternary relationship.
d. The above representation requires that we create a primary key attribute for
E. Show how to treat E as a weak entity set so that a primary key attribute
is not required.
Answer:
a. Let E = {e1, e2}, A = {a1, a2}, B = {b1}, C = {c1}, RA = {(e1, a1), (e2, a2)},
RB = {(e1, b1)}, and RC = {(e1, c1)}. We see that because of the tuple
(e2, a2), no instance of R exists which corresponds to E, RA, RB and RC.Exercises 21
B E C
A
C
R
B
R
A
R
Figure 2.17 E-R diagram to Exercise 2.17b.
B E C
A
C
R
B
R
A
R
Figure 2.18 E-R diagram to Exercise 2.17d.
b. See Figure 2.17. The idea is to introduce total participation constraints between E and the relationships RA, RB, RC so that every tuple in E has a
relationship with A, B and C.
c. Suppose A totally participates in the relationhip R, then introduce a total
participation constraint between A and RA.
d. Consider E as a weak entity set and RA, RB and RC as its identifying relationship sets. See Figure 2.18.
2.19 A weak entity set can always be made into a strong entity set by adding to its
attributes the primary key attributes of its identifying entity set. Outline what
sort of redundancy will result if we do so.
Answer: The primary key of a weak entity set can be inferred from its relationship with the strong entity set. If we add primary key attributes to the weak
entity set, they will be present in both the entity set and the relationship set and
they have to be the same. Hence there will be redundancy.
2.20 Design a generalization– specialization hierarchy for a motor-vehicle sales company. The company sells motorcycles, passenger cars, vans, and buses. Justify
your placement of attributes at each level of the hierarchy. Explain why they
should not be placed at a higher or lower level.
Answer: Figure 2.19 gives one possible hierarchy, there could be many different solutions. The generalization– specialization hierarchy for the motor-vehicle
company is given in the ﬁgure. model, sales-tax-rate and sales-volume are attributes
necessary for all types of vehicles. Commercial vehicles attract commercial vehi-22 Chapter 2 Entity Relationship Model
isa
isa isa
model sales-volume
vehicle
vehicle
commercialbus van car
cycle
motortype
rate
sales-tax-
vehicle
non-commercialluxury-vehicletax-rate
vehicle-tax-rate
commercialmaxpassengers
Figure 2.19 E-R diagram of motor-vehicle sales company.
cle tax, and each kind of commercial vehicle has a passenger carrying capacity
speciﬁed for it. Some kinds of non-commercial vehicles attract luxury vehicle
tax. Cars alone can be of several types, such as sports-car, sedan, wagon etc.,
hence the attribute type.
2.21 Explain the distinction between condition-deﬁned and user-deﬁned constraints.
Which of these constraints can the system check automatically? Explain your
answer.
Answer: In a generalization– specialization hierarchy, it must be possible to decide which entities are members of which lower level entity sets. In a conditiondeﬁned design constraint, membership in the lower level entity-sets is evaluated on the basis of whether or not an entity satisﬁes an explicit condition or
predicate.User-deﬁned lower-level entity sets are not constrained by a membership condition; rather, entities are assigned to a given entity set by the database
user.
Condition-deﬁned constraints alone can be automatically handled by the system. Whenever any tuple is inserted into the database, its membership in the
various lower level entity-sets can be automatically decided by evaluating the
respective membership predicates. Similarly when a tuple is updated, its membership in the various entity sets can be re-evaluated automatically.
2.22 Explain the distinction between disjoint and overlapping constraints.
Answer: In a disjointness design constraint, an entity can belong to not moreExercises 23
X
B
Y
A C
ISA ISA
Figure 2.20 E-R diagram for Exercise 2.24 (attributes not shown).
customer
customer−id
customer−name
customer−street
customer−city
loan
amount
loan−number
1..1 0..1
borrower
Figure 2.21 UML equivalent of Figure 2.9c.
than one lower-level entity set. In overlapping generalizations, the same entity may belong to more than one lower-level entity sets. For example, in the
employee-workteam example of the book, a manager may participate in more
than one work-team.
2.23 Explain the distinction between total and partial constraints.
Answer: In a total design constraint, each higher-level entity must belong to a
lower-level entity set. The same need not be true in a partial design constraint.
For instance, some employees may belong to no work-team.
2.24 Figure 2.20 shows a lattice structure of generalization and specialization. For
entity sets A, B, and C, explain how attributes are inherited from the higherlevel entity sets X and Y . Discuss how to handle a case where an attribute of X
has the same name as some attribute of Y .
Answer: A inherits all the attributes of X plus it may deﬁne its own attributes.
Similarly C inherits all the attributes of Y plus its own attributes. B inherits the
attributes of both X and Y. If there is some attribute name which belongs to both
X and Y, it may be referred to in B by the qualiﬁed name X.name or Y.name.
2.25 Draw the UML equivalents of the E-R diagrams of Figures 2.9c, 2.10, 2.12, 2.13
and 2.17.
Answer: See Figures 2.21 to 2.25
2.26 Consider two separate banks that decide to merge. Assume that both banks
use exactly the same E-R database schema—the one in Figure 2.22. (This assumption is, of course, highly unrealistic; we consider the more realistic case in24 Chapter 2 Entity Relationship Model
customer
customer−id
customer−name
customer−street
customer−city
1..1
depositor
access−date
0..*
account
account−number
balance
Figure 2.22 UML equivalent of Figure 2.10
employee−name
employee−id
telephone−num
employee
works−for
worker
manager
1..*
0..1
Figure 2.23 UML equivalent of Figure 2.12
employee−name
employee−id
street
city
employee
branch
branch−name
branch−city
assets
title
level
job
works−on
workid
work−job
emp−work work−branch
Figure 2.24 UML equivalent of Figure 2.13Exercises 25
officer−num station−num
officer
teller secretary
hrs−worked
hrs−worked
employee customer
person
name
street
city
salary credit−rating
Figure 2.25 UML equivalent of Figure 2.17
Section 19.8.) If the merged bank is to have a single database, there are several
potential problems:
• The possibility that the two original banks have branches with the same
name
• The possibility that some customers are customers of both original banks
• The possibility that some loan or account numbers were used at both original banks (for different loans or accounts, of course)
For each of these potential problems, describe why there is indeed a potential
for difﬁculties. Propose a solution to the problem. For your solution, explain any
changes that would have to be made and describe what their effect would be on
the schema and the data.
Answer: In this example, we assume that both banks have the shared identiﬁers
for customers, such as the social security number. We see the general solution in
the next exercise.
Each of the problems mentioned does have potential for difﬁculties.
a. branch-name is the primary-key of the branch entity set. Therefore while merging the two banks’ entity sets, if both banks have a branch with the same
name, one of them will be lost.26 Chapter 2 Entity Relationship Model
b. customers participate in the relationship sets cust-banker, borrower and depositor. While merging the two banks’ customer entity sets, duplicate tuples
of the same customer will be deleted. Therefore those relations in the three
mentioned relationship sets which involved these deleted tuples will have
to be updated. Note that if the tabular representation of a relationship set is
obtained by taking a union of the primary keys of the participating entity
sets, no modiﬁcation to these relationship sets is required.
c. The problem caused by loans or accounts with the same number in both the
banks is similar to the problem caused by branches in both the banks with
the same branch-name.
To solve the problems caused by the merger, no schema changes are required.
Merge the customer entity sets removing duplicate tuples with the same socialsecurity ﬁeld. Before merging the branch entity sets, prepend the old bank name
to the branch-name attribute in each tuple. The employee entity sets can be merged
directly, and so can the payment entity sets. No duplicate removal should be
performed. Before merging the loan and account entity sets, whenever there is a
number common in both the banks, the old number is replaced by a new unique
number, in one of the banks.
Next the relationship sets can be merged. Any relation in any relationship
set which involves a tuple which has been modiﬁed earlier due to the merger,
is itself modiﬁed to retain the same meaning. For example let 1611 be a loan
number common in both the banks prior to the merger, and let it be replaced by
a new unique number 2611 in one of the banks, say bank 2. Now all the relations
in borrower, loan-branch and loan-payment of bank 2 which refer to loan number
1611 will have to be modiﬁed to refer to 2611. Then the merger with bank 1’s
corresponding relationship sets can take place.
2.27 Reconsider the situation described for Exercise 2.26 under the assumption that
one bank is in the United States and the other is in Canada. As before, the
banks use the schema of Figure 2.22, except that the Canadian bank uses the
social-insurance number assigned by the Canadian government, whereas the U.S.
bank uses the social-security number to identify customers. What problems (beyond those identiﬁed in Exercise 2.24) might occur in this multinational case?
How would you resolve them? Be sure to consider both the scheme and the actual data values in constructing your answer.
Answer: This is a case in which the schemas of the two banks differ, so the
merger becomes more difﬁcult. The identifying attribute for persons in the US is
social-security, and in Canada it is social-insurance. Therefore the merged schema
cannot use either of these. Instead we introduce a new attribute person-id, and
use this uniformly for everybody in the merged schema. No other change to the
schema is required. The values for the person-id attribute may be obtained by
several ways. One way would be to prepend a country code to the old socialsecurity or social-insurance values (“U” and “C” respectively, for instance), to
get the corresponding person-id values. Another way would be to assign fresh
numbers starting from 1 upwards, one number to each social-security and socialinsurance value in the old databases.Exercises 27
Once this has been done, the actual merger can proceed as according to the
answer to the previous question. If a particular relationship set, say borrower, involves only US customers, this can be expressed in the merged database by specializing the entity-set customer into us-customer and canada-customer, and making only us-customer participate in the merged borrower. Similarly employee can
be specialized if needed.C H A P T E R 3
Relational Model
This chapter presents the relational model and three relational languages. The relational model (Section 3.1) is used extensively throughout the text as is the relational
algebra (Section 3.2). The chapter also covers the tuple relational calculus (Section 3.6)
and domain relational calculus (Section 3.7) (which is the basis of the QBE language
described in Chapter 5). Classes that emphasize only SQL may omit the relational
calculus languages.
Our notation for the tuple relational calculus makes it easy to present the concept of a safe query. The concept of safety for the domain relational calculus, though
identical to that for the tuple calculus, is much more cumbersome notationally and
requires careful presentation. This consideration may suggest placing somewhat less
emphasis on the domain calculus for classes not planning to cover QBE.
Section 3.3 presents extended relational-algebra operations, such as outer-joins
and aggregates. The evolution of query languages such as SQL clearly indicates the
importance of such extended operations. Some of these operations, such as outerjoins can be expressed in the tuple/domain relational calculus, while extensions are
required for other operations, such as aggregation. We have chosen not to present
such extensions to the relational calculus, and instead restrict our attention to extensions of the algebra.
2930 Chapter 3 Relational Model
person owns car
participated accident
address
damage-amount
model
license year
name
report-number
date
location
driver-id
driver
Figure 3.38. E-R diagram.
Exercises
3.1 Design a relational database for a university registrar’s ofﬁce. The ofﬁce maintains data about each class, including the instructor, the number of students
enrolled, and the time and place of the class meetings. For each student– class
pair, a grade is recorded.
Answer: Underlined attributes indicate the primary key.
student (student-id, name, program)
course (courseno, title, syllabus, credits)
course-offering (courseno, secno, year, semester, time, room)
instructor (instructor-id, name, dept, title)
enrols (student-id, courseno, secno, semester, year, grade)
teaches (courseno, secno, semester, year, instructor-id)
requires (maincourse, prerequisite)
3.2 Describe the differences in meaning between the terms relation and relation schema.
Illustrate your answer by referring to your solution to Exercise 3.1.
Answer: A relation schema is a type deﬁnition, and a relation is an instance of
that schema. For example, student (ss#, name) is a relation schema and
ss# name
123-45-6789 Tom J ones
456-78-9123 Joe Brown
is a relation based on that schema.
3.3 Design a relational database corresponding to the E-R diagram of Figure 3.38.
Answer: The relational database schema is given below.
person (driver-id, name, address)
car (license, year, model)
accident (report-number, location, date)
owns (driver-id, license)
participated (report-number driver-id, license, damage-amount)Exercises 31
employee (person-name, street, city)
works (person-name, company-name, salary)
company (company-name, city)
manages (person-name, manager-name)
Figure 3.39. Relational database for Exercises 3.5, 3.8 and 3.10.
3.4 In Chapter 2, we saw how to represent many-to-many, many-to-one, one-tomany, and one-to-one relationship sets. Explain how primary keys help us to
represent such relationship sets in the relational model.
Answer: Suppose the primary key of relation schema R is {Ai1
, Ai2
, ..., Ain
}
and the primary key of relation schema S is {Bi1
, Bi2
, ..., Bim }. Then a relationship between the 2 sets can be represented as a tuple (Ai1
, Ai2
, ..., Ain
Bi1
, Bi2
, ..., Bim). In a one-to-one relationship, each value on {Ai1
, Ai2
, ..., Ain
}
will appear in exactly one tuple and likewise for {Bi1
, Bi2
, ..., Bim }. In a manyto-one relationship (e.g., many A - one B), each value on {Ai1
, Ai2
, ..., Ain
} will
appear once, and each value on {Bi1
, Bi2
, ..., Bin
} may appear many times. In a
many-to-many relationship, values on both {Ai1
, Ai2
, ..., Ain
} and { Bi1
, Bi2
, ...,
Bim } will appear many times. However, in all the above cases {Ai1
, Ai2
, ..., Ain
,
Bi1
, Bi2
, ..., Bim } is a primary key, so no tuple on (Aj1
, ..., Ajn
Bk1
, ..., Bkm) will
appear more than once.
3.5 Consider the relational database of Figure 3.39, where the primary keys are underlined. Give an expression in the relational algebra to express each of the following queries:
a. Find the names of all employees who work for First Bank Corporation.
b. Find the names and cities of residence of all employees who work for First
Bank Corporation.
c. Find the names, street address, and cities of residence of all employees who
work for First Bank Corporation and earn more than $10,000 per annum.
d. Find the names of all employees in this database who live in the same city
as the company for which they work.
e. Find the names of all employees who live in the same city and on the same
street as do their managers.
f. Find the names of all employees in this database who do not work for First
Bank Corporation.
g. Find the names of all employees who earn more than every employee of
Small Bank Corporation.
h. Assume the companies may be located in several cities. Find all companies
located in every city in which Small Bank Corporation is located.
Answer:
a. Πperson-name (σ
company-name = “First Bank Corporation”
(works))
b. Πperson-name, city (employee1
(σ
company-name = “First Bank Corporation”
(works)))32 Chapter 3 Relational Model
c. Πperson-name, street, city
(σ
(company-name = “First Bank Corporation” ∧ salary > 10000)
works1 employee)
d. Πperson-name (employee1 works1 company)
e. Πperson-name ((employee1 manages) 1(manager-name = employee2.person-name ∧ employee.street = employee2.street
∧ employee.city = employee2.city)
(ρemployee2 (employee)))
f. The following solutions assume that all people work for exactly one company. If one allows people to appear in the database (e.g. in employee) but
not appear in works, the problem is more complicated. We give solutions for
this more realistic case later.
Πperson-name (σ
company-name = “First Bank Corporation”
(works))
If people may not work for any company:
Πperson-name(employee) − Πperson-name
(σ
(company-name = “First Bank Corporation”)
(works))
g. Πperson-name (works) − (Πworks.person-name (works 1
(works.salary ≤works2.salary ∧ works2.company-name = “Small Bank Corporation”)
ρworks2(works)))
h. Note: Small Bank Corporation will be included in each answer.
Πcompany-name (company ÷
(Πcity (σ
company-name = “Small Bank Corporation”
(company))))
3.6 Consider the relation of Figure 3.21, which shows the result of the query “Find
the names of all customers who have a loan at the bank.” Rewrite the query
to include not only the name, but also the city of residence for each customer.
Observe that now customer Jackson no longer appears in the result, even though
Jackson does in fact have a loan from the bank.
a. Explain why Jackson does not appear in the result.
b. Suppose that you want Jackson to appear in the result. How would you
modify the database to achieve this effect?
c. Again, suppose that you want Jackson to appear in the result. Write a query
using an outer join that accomplishes this desire without your having to
modify the database.
Answer: The rewritten query is
Πcustomer-name,customer-city,amount(borrower1 loan1 customer)
a. Although Jackson does have a loan, no address is given for Jackson in the
customer relation. Since no tuple in customer joins with the Jackson tuple of
borrower, Jackson does not appear in the result.
b. The best solution is to insert Jackson’s address into the customer relation. If
the address is unknown, null values may be used. If the database system
does not support nulls, a special value may be used (such as unknown) for
Jackson’s street and city. The special value chosen must not be a plausible
name for an actual city or street.Exercises 33
c. Πcustomer-name,customer-city,amount((borrower1 loan)1 customer)
3.7 The outer-join operations extend the natural-join operation so that tuples from
the participating relations are not lost in the result of the join. Describe how the
theta join operation can be extended so that tuples from the left, right, or both
relations are not lost from the result of a theta join.
Answer:
a. The left outer theta join of r(R) and s(S) (r1θ s) can be deﬁned as
(r1θ s) ∪ ((r − ΠR(r1θ s)) × (null, null, . . . , null))
The tuple of nulls is of size equal to the number of attributes in S.
b. The right outer theta join of r(R) and s(S) (r1 θ s) can be deﬁned as
(r1θ s) ∪ ((null, null, . . . , null) × (s − ΠS (r1θ s)))
The tuple of nulls is of size equal to the number of attributes in R.
c. The full outer theta join of r(R) and s(S) (r1 θ s) can be deﬁned as
(r1θ s) ∪ ((null, null, . . . , null) × (s − ΠS (r1θ s))) ∪
((r − ΠR(r1θ s)) × (null, null, . . . , null))
The ﬁrst tuple of nulls is of size equal to the number of attributes in R, and
the second one is of size equal to the number of attributes in S.
3.8 Consider the relational database of Figure 3.39. Give an expression in the relational algebra for each request:
a. Modify the database so that Jones now lives in Newtown.
b. Give all employees of First Bank Corporation a 10 percent salary raise.
c. Give all managers in this database a 10 percent salary raise.
d. Give all managers in this database a 10 percent salary raise, unless the salary
would be greater than $100,000. In such cases, give only a 3 percent raise.
e. Delete all tuples in the works relation for employees of Small Bank Corporation.
Answer:
a. employee ← Πperson-name,street,“N ewtown
(σ
person-name=“Jones”
(employee))
∪ (employee − σ
person-name=“Jones”
(employee))
b. works ← Πperson-name,company-name,1.1∗salary(
σ
(company-name=“First Bank Corporation”)
(works))
∪ (works − σ
company-name=“First Bank Corporation”
(works))
c. The update syntax allows reference to a single relation only. Since this update requires access to both the relation to be updated (works) and the manages relation, we must use several steps. First we identify the tuples of works
to be updated and store them in a temporary relation (t1). Then we create
a temporary relation containing the new tuples (t2). Finally, we delete the
tuples in t1, from works and insert the tuples of t2.
t1 ← Πworks.person-name,company-name,salary
(σworks.person-name=manager-name(works × manages))34 Chapter 3 Relational Model
t2 ← Πperson-name,company-name,1.1∗salary (t1)
works ← (works − t1) ∪ t2
d. The same situation arises here. As before, t1, holds the tuples to be updated
and t2 holds these tuples in their updated form.
t1 ← Πworks.person-name,company-name,salary
(σworks.person-name=manager-name(works × manages))
t2 ← Πworks.person-name,company-name,salary∗1.03
(σt1 .salary ∗ 1.1 > 100000(t1))
t2 ← t2 ∪ (Πworks.person-name,company-name,salary∗1.1
(σt1 .salary ∗ 1.1 ≤ 100000(t1)))
works ← (works − t1) ∪ t2
e. works ← works − σ
company−name=“Small Bank Corporation”
(works)
3.9 Using the bank example, write relational-algebra queries to ﬁnd the accounts
held by more than two customers in the following ways:
a. Using an aggregate function.
b. Without using any aggregate functions.
Answer:
a. t1 ← account-number Gcount customer-name
(depositor)
Πaccount-number

σnum-holders>2

ρaccount-holders(account-number,num-holders)
(t1)

b. t1 ← (ρd1(depositor) × ρd2(depositor) × ρd3(depositor))
t2 ← σ(d1.account-number=d2.account-number=d3.account-number)
(t1)
Πd1.account-number (σ(d1.customer-name= d2.customer-name ∧
d2.customer-name= d3.customer-name ∧d3.customer-name= d1.customer-name)
(t2))
3.10 Consider the relational database of Figure 3.39. Give a relational-algebra expression for each of the following queries:
a. Find the company with the most employees.
b. Find the company with the smallest payroll.
c. Find those companies whose employees earn a higher salary, on average,
than the average salary at First Bank Corporation.
Answer:
a. t1 ← company-nameG
count-distinct person-name
(works)
t2 ← maxnum-employees(ρcompany-strength(company-name,num-employees)
(t1))
Πcompany-name(ρt3(company-name,num-employees)
(t1)1 ρt4(num-employees)
(t2))
b. t1 ← company-nameGsum salary(works)
t2 ← minpayroll
(ρcompany-payroll(company-name,payroll)
(t1))
Πcompany-name(ρt3(company-name,payroll)
(t1)1 ρt4(payroll)
(t2))
c. t1 ← company-nameGavg salary (works)
t2 ← σ
company-name = “First Bank Corporation”
(t1)Exercises 35
Πt3.company-name((ρt3(company-name,avg-salary)
(t1)) 1t3.avg-salary > f irst-bank.avg-salary (ρf irst-bank(company-name,avg-salary)
(t2)))
3.11 List two reasons why we may choose to deﬁne a view.
Answer:
a. Security conditions may require that the entire logical database be not visible to all users.
b. We may wish to create a personalized collection of relations that is better
matched to a certain user’s intuition than is the actual logical model.
3.12 List two major problems with processing update operations expressed in terms
of views.
Answer: Views present signiﬁcant problems if updates are expressed with them.
The difﬁculty is that a modiﬁcation to the database expressed in terms of a view
must be translated to a modiﬁcation to the actual relations in the logical model
of the database.
a. Since the view may not have all the attributes of the underlying tables, insertion of a tuple into the view will insert tuples into the underlying tables,
with those attributes not participating in the view getting null values. This
may not be desirable, especially if the attribute in question is part of the
primary key of the table.
b. If a view is a join of several underlying tables and an insertion results in
tuples with nulls in the join columns, the desired effect of the insertion will
not be achieved. In other words, an update to a view may not be expressible
at all as updates to base relations. For an explanatory example, see the loaninfo updation example in Section 3.5.2.
3.13 Let the following relation schemas be given:
R = (A, B, C)
S = (D, E, F )
Let relations r(R) and s(S) be given. Give an expression in the tuple relational
calculus that is equivalent to each of the following:
a. ΠA(r)
b. σB = 17 (r)
c. r × s
d. ΠA,F (σC = D(r × s))
Answer:
a. {t | ∃ q ∈ r (q[A] = t[A])}
b. {t | t ∈ r ∧ t[B] = 17}
c. {t | ∃ p ∈ r ∃ q ∈ s (t[A] = p[A] ∧ t[B] = p[B]∧ t[C] = p[C] ∧ t[D] = q[D]
∧ t[E] = q[E] ∧ t[F ] = q[F ])}
d. {t | ∃ p ∈ r ∃ q ∈ s (t[A] = p[A] ∧ t[F ] = q[F ] ∧ p[C] = q[D]}36 Chapter 3 Relational Model
3.14 Let R = (A, B, C), and let r1 and r2 both be relations on schema R. Give
an expression in the domain relational calculus that is equivalent to each of the
following:
a. ΠA(r1)
b. σB = 17 (r1)
c. r1 ∪ r2
d. r1 ∩ r2
e. r1 − r2
f. ΠA,B(r1)1 ΠB,C (r2)
Answer:
a. {< t > | ∃ p, q (< t, p, q > ∈ r1)}
b. {< a, b, c > | < a, b, c > ∈ r1 ∧ b = 17}
c. {< a, b, c > | < a, b, c > ∈ r1 ∨ < a, b, c > ∈ r2}
d. {< a, b, c > | < a, b, c > ∈ r1 ∧ < a, b, c > ∈ r2}
e. {< a, b, c > | < a, b, c > ∈ r1 ∧ < a, b, c > ∈ r2}
f. {< a, b, c > | ∃ p, q (< a, b, p > ∈ r1 ∧ < q, b, c > ∈ r2)}
3.15 Repeat Exercise 3.5 using the tuple relational calculus and the domain relational
calculus.
Answer:
a. Find the names of all employees who work for First Bank Corporation:-
i. {t | ∃ s ∈ works (t[person-name] = s[person-name]
∧ s[company-name] = “First Bank Corporation”)}
ii. { | ∃ c, s (< p, c, s > ∈ works ∧ c = “First Bank Corporation”)}
b. Find the names and cities of residence of all employees who work for First
Bank Corporation:-
i. {t | ∃ r ∈ employee ∃ s ∈ works ( t[person-name] = r[person-name]
∧ t[city] = r[city] ∧ r[person-name] = s[person-name]
∧ s[company-name] = “First Bank Corporation”)}
ii. {< p, c > | ∃ co, sa, st (< p, co, sa > ∈ works
∧ < p, st, c > ∈ employee ∧ co = “First Bank Corporation”)}
c. Find the names, street address, and cities of residence of all employees who
work for First Bank Corporation and earn more than $10,000 per annum:-
i. {t | t ∈ employee ∧ (∃ s ∈ works ( s[person-name] = t[person-name]
∧ s[company-name] = “First Bank Corporation” ∧ s[salary] >
10000))}
ii. {< p, s, c > | < p, s, c > ∈ employee ∧ ∃ co, sa (< p, co, sa > ∈ works
∧ co = “First Bank Corporation” ∧ sa > 10000)}
d. Find the names of all employees in this database who live in the same city
as the company for which they work:-
i. {t | ∃ e ∈ employee ∃ w ∈ works ∃ c ∈ company
(t[person-name] = e[person-name]
∧ e[person-name] = w[person-name]
∧ w[company-name] = c[company-name] ∧ e[city] = c[city])}Exercises 37
ii. { | ∃ st, c, co, sa (< p, st, c > ∈ employee
∧ < p, co, sa > ∈ works ∧ < co, c > ∈ company)}
e. Find the names of all employees who live in the same city and on the same
street as do their managers:-
i. { t | ∃ l ∈ employee ∃ m ∈ manages ∃ r ∈ employee
(l[person-name] = m[person-name] ∧ m[manager-name] =
r[person-name]
∧ l[street] = r[street] ∧ l[city] = r[city] ∧ t[person-name] =
l[person-name])}
ii. {< t > | ∃ s, c, m (< t, s, c > ∈ employee ∧ < t, m > ∈ manages ∧ <
m, s, c > ∈ employee)}
f. Find the names of all employees in this database who do not work for First
Bank Corporation:-
If one allows people to appear in the database (e.g. in employee) but not appear in works, the problem is more complicated. We give solutions for this
more realistic case later.
i. { t | ∃ w ∈ works ( w[company-name] = “First Bank Corporation”
∧ t[person-name] = w[person-name])}
ii. { | ∃ c, s (< p, c, s > ∈ works ∧ c = “First Bank Corporation”)}
If people may not work for any company:
i. { t | ∃ e ∈ employee ( t[person-name] = e[person-name] ∧ ¬ ∃ w ∈
works
(w[company-name] = “First Bank Corporation”
∧ w[person-name] = t[person-name]))}
ii. { | ∃ s, c (< p, s, c > ∈ employee) ∧ ¬ ∃ x, y
(y = “First Bank Corporation”∧ < p, y, x > ∈ works)}
g. Find the names of all employees who earn more than every employee of
Small Bank Corporation:-
i. {t | ∃ w ∈ works (t[person-name] = w[person-name] ∧ ∀ s ∈ works
(s[company-name] = “Small Bank Corporation” ⇒ w[salary] >
s[salary]))}
ii. { | ∃ c, s (< p, c, s > ∈ works ∧ ∀ p2, c2, s2
(< p2, c2, s2 > ∈ works ∨ c2 = “Small Bank Corporation” ∨ s >
s2))}
h. Assume the companies may be located in several cities. Find all companies
located in every city in which Small Bank Corporation is located.
Note: Small Bank Corporation will be included in each answer.
i. {t | ∀ s ∈ company (s[company-name] = “Small Bank Corporation” ⇒
∃ r ∈ company (t[company-name] = r[company-name] ∧ r[city] =
s[city]))}
ii. {< co > | ∀ co2, ci2 (< co2, ci2 > ∈ company
∨ co2 = “Small Bank Corporation” ∨ < co, ci2 > ∈ company)}
3.16 Let R = (A, B) and S = (A, C), and let r(R) and s(S) be relations. Write
relational-algebra expressions equivalent to the following domain-relationalcalculus expressions:38 Chapter 3 Relational Model
a. {< a > | ∃ b (< a, b > ∈ r ∧ b = 17)}
b. {< a, b, c > | < a, b > ∈ r ∧ < a, c > ∈ s}
c. {< a > | ∃ b (< a, b > ∈ r) ∨ ∀ c (∃ d (< d, c > ∈ s) ⇒ < a, c > ∈ s)}
d. {< a > | ∃ c (< a, c > ∈ s ∧ ∃ b1, b2 (< a, b1 > ∈ r ∧ < c, b2 >
∈ r ∧ b1 > b2))}
Answer:
a. ΠA (σB = 17 (r))
b. r1 s
c. ΠA(r) ∪ (r ÷ σB(ΠC (s)))
d. Πr.A ((r1 s)1c = r2.A ∧ r.B > r2.B (ρr2
(r)))
It is interesting to note that (d) is an abstraction of the notorious query
“Find all employees who earn more than their manager.” Let R = (emp, sal),
S = (emp, mgr) to observe this.
3.17 Let R = (A, B) and S = (A, C), and let r(R) and s(S) be relations. Using
the special constant null, write tuple-relational-calculus expressions equivalent
to each of the following:
a. r1 s
b. r1 s
c. r1 s
Answer:
a. {t | ∃r ∈ R ∃s ∈ S (r[A] = s[A] ∧ t[A] = r[A] ∧ t[B] = r[B] ∧ t[C] = s[C]) ∨
∃s ∈ S(¬∃r ∈ R(r[A] = s[A]) ∧ t[A] = s[A] ∧ t[C] = s[C] ∧ t[B] = null)}
b. {t | ∃r ∈ R ∃s ∈ S (r[A] = s[A] ∧ t[A] = r[A] ∧ t[B] = r[B] ∧ t[C] = s[C]) ∨
∃r ∈ R(¬∃s ∈ S(r[A] = s[A]) ∧ t[A] = r[A] ∧ t[B] = r[B] ∧ t[C] = null) ∨
∃s ∈ S(¬∃r ∈ R(r[A] = s[A]) ∧ t[A] = s[A] ∧ t[C] = s[C] ∧ t[B] = null)}
c. {t | ∃r ∈ R ∃s ∈ S (r[A] = s[A] ∧ t[A] = r[A] ∧ t[B] = r[B] ∧ t[C] = s[C]) ∨
∃r ∈ R(¬∃s ∈ S(r[A] = s[A]) ∧ t[A] = r[A] ∧ t[B] = r[B] ∧ t[C] = null)}
3.18 List two reasons why null values might be introduced into the database.
Answer: Nulls may be introduced into the database because the actual value
is either unknown or does not exist. For example, an employee whose address
has changed and whose new address is not yet known should be retained with
a null address. If employee tuples have a composite attribute dependents, and
a particular employee has no dependents, then that tuple’s dependents attribute
should be given a null value.
3.19 Certain systems allow marked nulls. A marked null ⊥i
is equal to itself, but if
i = j, then ⊥i = ⊥j. One application of marked nulls is to allow certain updates
through views. Consider the view loan-info (Section 3.5). Show how you can use
marked nulls to allow the insertion of the tuple (“Johnson”, 1900) through loaninfo.
Answer: To insert the tuple (“Johnson”, 1900) into the view loan-info, we can doExercises 39
the following:-
borrower ← (“Johnson”, ⊥k) ∪ borrower
loan ← (⊥k, ⊥, 1900) ∪ loan
such that ⊥k is a new marked null not already existing in the database.C H A P T E R 4
SQL
Chapter 4 covers the relational language SQL. The discussion is based on SQL-92,
since the more recent SQL:1999 is not widely supported yet. Extensions provided by
SQL:1999 are covered later in Chapters 9 and 22. Integrity constraint and authorization
features of SQL-92 are described in Chapter 6. SQL being a large language, many of its
features are not covered here, and are not appropriate for an introductory course on
databases. Standard books on SQL, such as Date and Darwen [1993] and Melton and
Simon [1993], or the system manuals of the database system you use can be used as
supplements for students who want to delve deeper into the intricacies of SQL.
Although it is possible to cover this chapter using only handwritten exercises, we
strongly recommend providing access to an actual database system that supports
SQL. A style of exercise we have used is to create a moderately large database and
give students a list of queries in English to write and run using SQL. We publish the
actual answers (that is the result relations they should get, not the SQL they must enter). By using a moderately large database, the probability that a “wrong” SQL query
will just happen to return the “right” result relation can be made very small. This
approach allows students to check their own answers for correctness immediately
rather than wait for grading and thereby it speeds up the learning process. A few
such example databases are available on the Web home page of this book.
Exercises that pertain to database design are best deferred until after Chapter 7.
Given the fact that the ODBC and JDBC protocols are fast becoming a primary
means of accessing databases, we have signiﬁcantly extended our coverage of these
two protocols, including some examples. However, our coverage is only introductory, and omits many details that are useful in practise. Online tutorials/manuals or
textbooks covering these protocols should be used as supplements, to help students
make full use of the protocols.
Changes from 3
rd
edition:
Our coverage of SQL has been expanded to include the with clause, ODBC, JDBC, and
schemas, catalogs and environments (Section 4.14).
4142 Chapter 4 SQL
Exercises
4.1 Consider the insurance database of Figure 4.12, where the primary keys are underlined. Construct the following SQL queries for this relational database.
a. Find the total number of people who owned cars that were involved in accidents in 1989.
b. Find the number of accidents in which the cars belonging to “John Smith”
were involved.
c. Add a new accident to the database; assume any values for required attributes.
d. Delete the Mazda belonging to “John Smith”.
e. Update the damage amount for the car with license number “AABB2000” in
the accident with report number “AR2197” to $3000.
Answer: Note: The participated relation relates drivers, cars, and accidents.
a. Find the total number of people who owned cars that were involved in accidents in 1989.
Note: this is not the same as the total number of accidents in 1989. We
must count people with several accidents only once.
select count (distinct name)
from accident, participated, person
where accident.report-number = participated.report-number
and participated.driver-id = person.driver-id
and date between date ’1989-00-00’ and date ’1989-12-31’
b. Find the number of accidents in which the cars belonging to “John Smith”
were involved.
select count (distinct *)
from accident
where exists
(select *
from participated, person
where participated.driver-id = person.driver-id
and person.name = ’John Smith’
and accident.report-number = participated.report-number)
c. Add a new accident to the database; assume any values for required attributes.
We assume the driver was “Jones,” although it could be someone else.
Also, we assume “Jones” owns one Toyota. First we must ﬁnd the license of
the given car. Then the participated and accident relations must be updated
in order to both record the accident and tie it to the given car. We assume
values “Berkeley” for location, ’2001-09-01’ for date and date, 4007 for reportnumber and 3000 for damage amount.Exercises 43
person (driver-id, name, address)
car (license, model, year)
accident (report-number, date, location)
owns (driver-id, license)
participated (driver-id, car, report-number, damage-amount)
Figure 4.12. Insurance database.
insert into accident
values (4007, ’2001-09-01’, ’Berkeley’)
insert into participated
select o.driver-id, c.license, 4007, 3000
from person p, owns o, car c
where p.name = ’Jones’ and p.driver-id = o.driver-id and
o.license = c.license and c.model = ’Toyot a’
d. Delete the Mazda belonging to “John Smith”.
Since model is not a key of the car relation, we can either assume that only
one of John Smith’s cars is a Mazda, or delete all of John Smith’s Mazdas
(the query is the same). Again assume name is a key for person.
delete car
where model = ’Mazda’ and license in
(select license
from person p, owns o
where p.name = ’John Smith’ and p.driver-id = o.driver-id)
Note: The owns, accident and participated records associated with the Mazda
still exist.
e. Update the damage amount for the car with license number “AABB2000” in
the accident with report number “AR2197” to $3000.
update participated
set damage-amount = 3000
where report-number = “AR2197” and driver-id in
(select driver-id
from owns
where license = “AABB2000”)
4.2 Consider the employee database of Figure 4.13, where the primary keys are underlined. Give an expression in SQL for each of the following queries.
a. Find the names of all employees who work for First Bank Corporation.
b. Find the names and cities of residence of all employees who work for First
Bank Corporation.
c. Find the names, street addresses, and cities of residence of all employees
who work for First Bank Corporation and earn more than $10,000.44 Chapter 4 SQL
d. Find all employees in the database who live in the same cities as the companies for which they work.
e. Find all employees in the database who live in the same cities and on the
same streets as do their managers.
f. Find all employees in the database who do not work for First Bank Corporation.
g. Find all employees in the database who earn more than each employee of
Small Bank Corporation.
h. Assume that the companies may be located in several cities. Find all companies located in every city in which Small Bank Corporation is located.
i. Find all employees who earn more than the average salary of all employees
of their company.
j. Find the company that has the most employees.
k. Find the company that has the smallest payroll.
l. Find those companies whose employees earn a higher salary, on average,
than the average salary at First Bank Corporation.
Answer:
a. Find the names of all employees who work for First Bank Corporation.
select employee-name
from works
where company-name = ’First Bank Corporation’
b. Find the names and cities of residence of all employees who work for First
Bank Corporation.
select e.employee-name, city
from employee e, works w
where w.company-name = ’First Bank Corporation’ and
w.employee-name = e.employee-name
c. Find the names, street address, and cities of residence of all employees who
work for First Bank Corporation and earn more than $10,000.
If people may work for several companies, the following solution will
only list those who earn more than $10,000 per annum from “First Bank
Corporation” alone.
select *
from employee
where employee-name in
(select employee-name
from works
where company-name = ’First Bank Corporation’ and salary ¿ 10000)
As in the solution to the previous query, we can use a join to solve this one
also.
d. Find all employees in the database who live in the same cities as the companies for which they work.Exercises 45
select e.employee-name
from employee e, works w, company c
where e.employee-name = w.employee-name and e.city = c.city and
w.company -name = c.company -name
e. Find all employees in the database who live in the same cities and on the
same streets as do their managers.
select P.employee-name
from employee P, employee R, manages M
where P.employee-name = M.employee-name and
M.manager-name = R.employee-name and
P.street = R.street and P. c it y = R. c it y
f. Find all employees in the database who do not work for First Bank Corporation.
The following solution assumes that all people work for exactly one company.
select employee-name
from works
where company-name = ’First Bank Corporation’
If one allows people to appear in the database (e.g. in employee) but not
appear in works, or if people may have jobs with more than one company,
the solution is slightly more complicated.
select employee-name
from employee
where employee-name not in
(select employee-name
from works
where company-name = ’First Bank Corporation’)
g. Find all employees in the database who earn more than every employee of
Small Bank Corporation.
The following solution assumes that all people work for at most one company.
select employee-name
from works
where salary > all
(select salary
from works
where company-name = ’Small Bank Corporation’)
If people may work for several companies and we wish to consider the
total earnings of each person, the problem is more complex. It can be solved
by using a nested subquery, but we illustrate below how to solve it using
the with clause.46 Chapter 4 SQL
with emp-total-salary as
(select employee-name, sum(salary) as total-salary
from works
group by employee-name
)
select employee-name
from emp-total-salary
where total-salary > all
(select total-salary
from emp-total-salary, works
where works.company-name = ’Small Bank Corporation’ and
emp-total-salary.employee-name = works.employee-name
)
h. Assume that the companies may be located in several cities. Find all companies located in every city in which Small Bank Corporation is located.
The simplest solution uses the contains comparison which was included
in the original System R Sequel language but is not present in the subsequent SQL versions.
select T.company-name
from company T
where (select R.city
from company R
where R.company-name = T.company-name)
contains
(select S.city
from company S
where S.company-name = ’Small Bank Corporation’)
Below is a solution using standard SQL.
select S.company-name
from company S
where not exists ((select city
from company
where company-name = ’Small Bank Corporation’)
except
(select city
from company T
where S.company-name = T.company-name))
i. Find all employees who earn more than the average salary of all employees
of their company.
The following solution assumes that all people work for at most one company.Exercises 47
employee (employee-name, street, city)
works (employee-name, company-name, salary)
company (company-name, city)
manages (employee-name, manager-name)
Figure 4.13. Employee database.
select employee-name
from works T
where salary > (select avg (salary)
from works S
where T.company-name = S.company-name)
j. Find the company that has the most employees.
select company-name
from works
group by company-name
having count (distinct employee-name) >= all
(select count (distinct employee-name)
from works
group by company-name)
k. Find the company that has the smallest payroll.
select company-name
from works
group by company-name
having sum (salary) <= all (select sum (salary)
from works
group by company-name)
l. Find those companies whose employees earn a higher salary, on average,
than the average salary at First Bank Corporation.
select company-name
from works
group by company-name
having avg (salary) > (select avg (salary)
from works
where company-name = ’First Bank Corporation’)
4.3 Consider the relational database of Figure 4.13. Give an expression in SQL for
each of the following queries.
a. Modify the database so that Jones now lives in Newtown.
b. Give all employees of First Bank Corporation a 10 percent raise.
c. Give all managers of First Bank Corporation a 10 percent raise.
d. Give all managers of First Bank Corporation a 10 percent raise unless the
salary becomes greater than $100,000; in such cases, give only a 3 percent
raise.48 Chapter 4 SQL
e. Delete all tuples in the works relation for employees of Small Bank Corporation.
Answer: The solution for part 0.a assumes that each person has only one tuple in
the employee relation. The solutions to parts 0.c and 0.d assume that each person
works for at most one company.
a. Modify the database so that Jones now lives in Newtown.
update employee
set city = ’Newton’
where person-name = ’Jones’
b. Give all employees of First Bank Corporation a 10-percent raise.
update works
set salary = salary * 1.1
where company-name = ’First Bank Corporation’
c. Give all managers of First Bank Corporation a 10-percent raise.
update works
set salary = salary * 1.1
where employee-name in (select manager-name
from manages)
and company-name = ’First Bank Corporation’
d. Give all managers of First Bank Corporation a 10-percent raise unless the
salary becomes greater than $100,000; in such cases, give only a 3-percent
raise.
update works T
set T.salary = T.salary * 1.03
where T.employee-name in (select manager-name
from manages)
and T.salary * 1.1 > 100000
and T.company-name = ’First Bank Corporation’
update works T
set T.salary = T.salary * 1.1
where T.employee-name in (select manager-name
from manages)
and T.salary * 1.1 <= 100000
and T.company-name = ’First Bank Corporation’
SQL-92 provides a case operation (see Exercise 4.11), using which we give
a more concise solution:-Exercises 49
update works T
set T.salary = T.salary ∗
(case
when (T.salary ∗ 1.1 > 100000) then 1.03
else 1.1
)
where T.employee-name in (select manager-name
from manages) and
T.company-name = ’First Bank Corporation’
e. Delete all tuples in the works relation for employees of Small Bank Corporation.
delete works
where company-name = ’Small Bank Corporation’
4.4 Let the following relation schemas be given:
R = (A, B, C)
S = (D, E, F )
Let relations r(R) and s(S) be given. Give an expression in SQL that is equivalent
to each of the following queries.
a. ΠA(r)
b. σB = 17 (r)
c. r × s
d. ΠA,F (σC = D(r × s))
Answer:
a. ΠA(r)
select distinct A
from r
b. σB = 17 (r)
select *
from r
where B = 17
c. r × s
select distinct *
from r, s
d. ΠA,F (σC = D(r × s))
select distinct A, F
from r, s
where C = D
4.5 Let R = (A, B, C), and let r1 and r2 both be relations on schema R. Give an
expression in SQL that is equivalent to each of the following queries.
a. r1 ∪ r2
b. r1 ∩ r250 Chapter 4 SQL
c. r1 − r2
d. ΠAB(r1)1 ΠBC (r2)
Answer:
a. r1 ∪ r2
(select *
from r1)
union
(select *
from r2)
b. r1 ∩ r2
We can write this using the intersect operation, which is the preferred
approach, but for variety we present an solution using a nested subquery.
select *
from r1
where (A, B, C) in (select *
from r2)
c. r1 − r2
select ∗
from r1
where (A, B, C) not in (select ∗
from r2)
This can also be solved using the except clause.
d. ΠAB(r1)1 ΠBC (r2)
select r1.A, r2.B, r3.C
from r1, r2
where r1.B = r2.B
4.6 Let R = (A, B) and S = (A, C), and let r(R) and s(S) be relations. Write an
expression in SQL for each of the queries below:
a. {< a > | ∃ b (< a, b > ∈ r ∧ b = 17)}
b. {< a, b, c > | < a, b > ∈ r ∧ < a, c > ∈ s}
c. {< a > | ∃ c (< a, c > ∈ s ∧ ∃ b1, b2 (< a, b1 > ∈ r ∧ < c, b2 > ∈ r ∧ b1 >
b2))}
Answer:
a. {< a > | ∃ b (< a, b > ∈ r ∧ b = 17)}
select distinct A
from r
where B = 17
b. {< a, b, c > | < a, b > ∈ r ∧ < a, c > ∈ s)}Exercises 51
select distinct r.A, r.B, s.C
from r, s
where r.A = s.A
c. {< a > | ∃ c (< a, c > ∈ s ∧ ∃ b1, b2 (< a, b1 > ∈ r ∧ < c, b2 > ∈ r ∧ b1 >
b2))}
select distinct s.A
from s, r e, r m
where s.A = e.A and s.C = m.A and e.B > m.B
4.7 Show that, in SQL, <> all is identical to not in.
Answer: Let the set S denote the result of an SQL subquery. We compare (x <>
all S) with (x not in S). If a particular value x1 satisﬁes (x1 <> all S) then for
all elements y of S x1 = y. Thus x1 is not a member of S and must satisfy (x1 not
in S). Similarly, suppose there is a particular value x2 which satisﬁes (x2 not in
S). It cannot be equal to any element w belonging to S, and hence (x2 <> all S)
will be satisﬁed. Therefore the two expressions are equivalent.
4.8 Consider the relational database of Figure 4.13. Using SQL, deﬁne a view consisting of manager-name and the average salary of all employees who work for
that manager. Explain why the database system should not allow updates to be
expressed in terms of this view.
Answer:
create view salinfo as
select manager-name, avg(salary)
from manages m, works w
where m.employee-name = w.employee-name
group by manager-name
Updates should not be allowed in this view because there is no way to determine how to change the underlying data. For example, suppose the request
is “change the average salary of employees working for Smith to $200”. Should
everybody who works for Smith have their salary changed to $200? Or should
the ﬁrst (or more, if necessary) employee found who works for Smith have
their salary adjusted so that the average is $200? Neither approach really makes
sense.
4.9 Consider the SQL query
select p.a1
from p, r1, r2
where p.a1 = r1.a1 or p.a1 = r2.a1
Under what conditions does the preceding query select values of p.a1 that are
either in r1 or in r2? Examine carefully the cases where one of r1 or r2 may be
empty.
Answer: The query selects those values of p.a1 that are equal to some value of
r1.a1 or r2.a1 if and only if both r1 and r2 are non-empty. If one or both of r1 and52 Chapter 4 SQL
r2 are empty, the cartesian product of p, r1 and r2 is empty, hence the result of
the query is empty. Of course if p itself is empty, the result is as expected, i.e.
empty.
4.10 Write an SQL query, without using a with clause, to ﬁnd all branches where
the total account deposit is less than the average total account deposit at all
branches,
a. Using a nested query in the from clauser.
b. Using a nested query in a having clause.
Answer: We output the branch names along with the total account deposit at
the branch.
a. Using a nested query in the from clauser.
select branch-name, tot-balance
from (select branch-name, sum (balance)
from account
group by branch-name) as branch-total(branch-name, tot-balance)
where tot-balance ¡
( select avg (tot-balance)
from ( select branch-name, sum (balance)
from account
group by branch-name) as branch-total(branch-name, tot-balance)
)
b. Using a nested query in a having clause.
select branch-name, sum (balance)
from account
group by branch-name
having sum (balance) ¡
( select avg (tot-balance)
from ( select branch-name, sum (balance)
from account
group by branch-name) as branch-total(branch-name, tot-balance)
)
4.11 Suppose that we have a relation marks(student-id, score) and we wish to assign
grades to students based on the score as follows: grade F if score < 40, grade C
if 40 ≤ score < 60, grade B if 60 ≤ score < 80, and grade A if 80 ≤ score. Write
SQL queries to do the following:
a. Display the grade for each student, based on the marks relation.
b. Find the number of students with each grade.
Answer: We use t he case operation provided by SQL-92:
a. To display the grade for each student:Exercises 53
select student-id,
(case
when score < 40 then ’F’,
when score < 60 then ’C’,
when score < 80 then ’B’,
else ’A’
end) as grade
from marks
b. To ﬁnd the number of students with each grade we use the following query, where
grades is the result of the query given as the solution to part 0.a.
select grade, count(student-id)
from grades
group by grade
4.12 SQL-92 provides an n-ary operation called coalesce, which is deﬁned as follows:
coalesce(A1, A2, . . . , An) returns the ﬁrst nonnull Ai
in the list A1, A2, . . . , An,
and returns null if all of A1, A2, . . . , An are null. Show how to express the coalesce operation using the case operation.
Answer:
case
when A1 is not null then A1
when A2 is not null then A2
. . .
when An is not null then An
else null
end
4.13 Let a and b be relations with the schemas A(name, address, title) and B(name, address, salary), respectively. Show how to express a natural full outer join b using
the full outer join operation with an on condition and the coalesce operation.
Make sure that the result relation does not contain two copies of the attributes
name and address, and that the solution is correct even if some tuples in a and b
have null values for attributes name or address.
Answer:
select coalesce(a.name, b.name) as name,
coalesce(a.address, b.address) as address,
a.title,
b.salary
from a full outer join b on a.name = b.name and
a.address = b.address
4.14 Give an SQL schema deﬁnition for the employee database of Figure 4.13. Choose
an appropriate domain for each attribute and an appropriate primary key for
each relation schema.
Answer:
create domain company-names char(20)54 Chapter 4 SQL
create domain city-names char(30)
create domain person-names char(20)
create table employee
(employee-name person-names,
street char(30),
city city-names,
primary key (employee-name))
create table works
(employee-name person-names,
company-name company-names,
salary numeric(8, 2),
primary key (employee-name))
create table company
(company-name company-names,
city city-names,
primary key (company-name))
create table manages
(employee-name person-names,
manager-name person-names,
primary key (employee-name))
4.15 Write check conditions for the schema you deﬁned in Exercise 4.14 to ensure
that:
a. Every employee works for a company located in the same city as the city in
which the employee lives.
b. No employee earns a salary higher than that of his manager.
Answer:
a. check condition for the works table:-
check((employee-name, company-name) in
(select e.employee-name, c.company-name
from employee e, company c
where e.city = c.city
)
)
b. check condition for the works table:-Exercises 55
check(
salary < all
(select manager-salary
from (select manager-name, manages.employee-name as emp-name,
salary as manager-salary
from works, manages
where works.employee-name = manages.manager-name)
where employee-name = emp-name
)
)
The solution is slightly complicated because of the fact that inside the select expression’s scope, the outer works relation into which the insertion is
being performed is inaccessible. Hence the renaming of the employee-name
attribute to emp-name. Under these circumstances, it is more natural to use
assertions, which are introduced in Chapter 6.
4.16 Describe the circumstances in which you would choose to use embedded SQL
rather than SQL alone or only a general-purpose programming language.
Answer: Writing queries in SQL is typically much easier than coding the same
queries in a general-purpose programming language. However not all kinds of
queries can be written in SQL. Also nondeclarative actions such as printing a
report, interacting with a user, or sending the results of a query to a graphical
user interface cannot be done from within SQL. Under circumstances in which
we want the best of both worlds, we can choose embedded SQL or dynamic
SQL, rather than using SQL alone or using only a general-purpose programming
language.
Embedded SQL has the advantage of programs being less complicated since it
avoids the clutter of the ODBC or JDBC function calls, but requires a specialized
preprocessor.C H A P T E R 5
Other Relational Languages
In this chapter we study two additional relational languages, QBE and Datalog. QBE,
based on the domain relational calculus, forms the basis for query languages supported by a large number of database systems designed for personal computers, such
as Microsoft Access, FoxPro, etc. Unfortunately there is no standard for QBE; our coverage is based on the original description of QBE. The description here will have to
be supplemented by material from the user guides of the speciﬁc database system
being used. One of the points to watch out for is the precise semantics of aggregate
operations, which is particularly non-standard.
The Datalog language has several similarities to Prolog, which some students may
have studied in other courses. Datalog differs from Prolog in that its semantics is
purely declarative, as opposed to the operational semantics of Prolog. It is important
to emphasize the differences, since the declarative semantics enables the use of efﬁ-
cient query evaluation strategies. There are several implementations of Datalog available in the public domain, such as the Coral system from the University of Wisconsin
– Madison, and XSB from the State University of New York, Stony Brook, which can
be used for programming exercises. The Coral system also supports complex objects
such as nested relations (covered later in Chapter 9). See the Tools section at the end
of Chapter 5 for the URLs of these systems.
Changes from 3
rd
edition:
The syntax and semantics of QBE aggregation and update have been changed to
simplify the semantics and to remove some ambiguities in the earlier semantics. The
version of QBE supported by Microsoft Access has been covered brieﬂy. Quel ha s
been dropped.
5758 Chapter 5 Other Relational Languages
Exercises
5.1 Consider the insurance database of Figure 5.14, where the primary keys are underlined. Construct the following QBE queries for this relational-database.
a. Find the total number of people who owned cars that were involved in accidents in 1989.
b. Find the number of accidents in which the cars belonging to “John Smith”
were involved.
c. Add a new accident to the database; assume any values for required attributes.
d. Delete the Mazda belonging to “John Smith.”
e. Update the damage amount for the car with license number “AABB2000” in
the accident with report number “AR2197” to $3000.
Answer: The participated relation relates car(s) and accidents. Assume the date
attribute is of the form “YYYY-MM-DD”.
a. Find the total number of people who owned cars that were involved in accidents in 1989.
accident report-number date location
report date
participated driver-id car report-number damage-amount
P.CNT.UNQ.ALL report
conditions
date =
( ≥ 1989-00-00 and
≤ 1989-12-31 )
b. Find the number of accidents in which the cars belonging to “John Smith”
were involved.
person driver-id name address
driver John Smith
participated driver-id car report-number damage-amount
driver P. C NT. A L L
c. Add a new accident to the database; assume any values for required attributes.
We assume that the driver was “Williams”, although it could have been
someone else. Also assume that “Williams” has only one Toyota.
accident report-number date location
I. 4007 1997-01-01 BerkeleyExercises 59
person (driver-id, name, address)
car (license, model, year)
accident (report-number, date, location)
owns (driver-id, license)
participated (driver-id, car, report-number, damage-amount)
Figure 5.14. Insurance database.
participated driver-id car report-number damage-amount
I. driver license 4007 3000
owns driver-id license
driver license
car license year model
license year Toyot a
person driver-id name address
driver Williams
d. Delete the car “Mazda” that belongs to “John Smith.”
person driver-id name address
driver John Smith
owns driver-id license
driver license
car license year model
D. license Mazda
e. Update the damage amount for the car with license number “AABB2000” in
the accident with report number “AR2197” to $3000.
owns driver-id license
driver “AABB2000”
participated driver-id car report-number damage-amount
driver “AR2197” U.3000
5.2 Consider the employee database of Figure 5.15. Give expressions in QBE, and
Datalog for each of the following queries:
a. Find the names of all employees who work for First Bank Corporation.60 Chapter 5 Other Relational Languages
b. Find the names and cities of residence of all employees who work for First
Bank Corporation.
c. Find the names, street addresses, and cities of residence of all employees
who work for First Bank Corporation and earn more than $10,000 per annum.
d. Find all employees who live in the same city as the company for which they
work is located.
e. Find all employees who live in the same city and on the same street as their
managers.
f. Find all employees in the database who do not work for First Bank Corporation.
g. Find all employees who earn more than every employee of Small Bank Corporation.
h. Assume that the companies may be located in several cities. Find all companies located in every city in which Small Bank Corporation is located.
Answer:
a. Find the names of all employees who work for First Bank Corporation.
i.
works person-name company-name salary

Prepare for software Interviews online

Friday, 16 September 2011

Full System Software Notes Download

Computer Networks

Download DBMS Notes...............

System Software Question Bank

Data Base Management System..........