Free Essay

Dbms Class

In:

Submitted By adilmoha
Words 41091
Pages 165
Contents

Preface 1 Chapter 1 Introduction

Exercises 4

Chapter 2

Entity Relationship Model

Exercises 9

Chapter 3

Relational Model

Exercises 30

Chapter 4

SQL

Exercises 42

Chapter 5

Other Relational Languages

Exercises 58

Chapter 6

Integrity and Security

Exercises 74

iii

iv

Contents

Chapter 7

Relational-Database Design

Exercises 84

Chapter 8

Object-Oriented Databases

Exercises 98

Chapter 9

Object-Relational Databases

Exercises 109

Chapter 10 XML
Exercises 119

Chapter 11

Storage and File Structure

Exercises 129

Chapter 12 Indexing and Hashing
Exercises 141

Chapter 13 Query Processing
Exercises 155

Chapter 14 Query Optimization
Exercises 166

Chapter 15 Transactions
Exercises 175

Chapter 16 Concurrency Control
Exercises 182

Chapter 17 Recovery System
Exercises 194

Contents

v

Chapter 18 Database System Architectures
Exercises 201

Chapter 19 Distributed Databases
Exercises 208

Chapter 20 Parallel Databases
Exercises 217

Chapter 21 Application Development and Administration
Exercises 225

Chapter 22 Advanced Querying and Information Retrieval
Exercises 232

Chapter 23 Advanced Data Types and New Applications
Exercises 241

Chapter 24 Advanced Transaction Processing
Exercises 249

C H A P T E R

1

Introduction

Chapter 1 provides a general overview of the nature and purpose of database systems. The most important concept in this chapter is that database systems allow data to be treated at a high level of abstraction. Thus, database systems differ significantly from the file systems and general purpose programming environments with which students are already familiar. Another important aspect of the chapter is to provide motivation for the use of database systems as opposed to application programs built on top of file systems. Thus, the chapter motivates what the student will be studying in the rest of the course. The idea of abstraction in database systems deserves emphasis throughout, not just in discussion of Section 1.3. The overview of the structure of databases, starting from Section 1.4 is, of necessity, rather brief, and is meant only to give the student a rough idea of some of the concepts. The student may not initially be able to fully appreciate the concepts described here, but should be able to do so by the end of the course. The specifics of the E-R, relational, and object-oriented models are covered in later chapters. These models can be used in Chapter 1 to reinforce the concept of abstraction, with syntactic details deferred to later in the course. If students have already had a course in operating systems, it is worthwhile to point out how the OS and DBMS are related. It is useful also to differentiate between concurrency as it is taught in operating systems courses (with an orientation towards files, processes, and physical resources) and database concurrency control (with an orientation towards granularity finer than the file level, recoverable transactions, and resources accessed associatively rather than physically). If students are familiar with a particular operating system, that OS’s approach to concurrent file access may be used for illustration.

3

4

Chapter 1

Introduction

Exercises
1.1 List four significant differences between a file-processing system and a DBMS. Answer: Some main differences between a database management system and a file-processing system are: • Both systems contain a collection of data and a set of programs which access that data. A database management system coordinates both the physical and the logical access to the data, whereas a file-processing system coordinates only the physical access. • A database management system reduces the amount of data duplication by ensuring that a physical piece of data is available to all programs authorized to have access to it, whereas data written by one program in a file-processing system may not be readable by another program. • A database management system is designed to allow flexible access to data (i.e., queries), whereas a file-processing system is designed to allow predetermined access to data (i.e., compiled programs). • A database management system is designed to coordinate multiple users accessing the same data at the same time. A file-processing system is usually designed to allow one or more programs to access different data files at the same time. In a file-processing system, a file can be accessed by two programs concurrently only if both programs have read-only access to the file. 1.2 This chapter has described several major advantages of a database system. What are two disadvantages? Answer: Two disadvantages associated with database systems are listed below. a. Setup of the database system requires more knowledge, money, skills, and time. b. The complexity of the database may result in poor performance. 1.3 Explain the difference between physical and logical data independence. Answer: • Physical data independence is the ability to modify the physical scheme without making it necessary to rewrite application programs. Such modifications include changing from unblocked to blocked record storage, or from sequential to random access files. • Logical data independence is the ability to modify the conceptual scheme without making it necessary to rewrite application programs. Such a modification might be adding a field to a record; an application program’s view hides this change from the program. 1.4 List five responsibilities of a database management system. For each responsibility, explain the problems that would arise if the responsibility were not discharged. Answer: A general purpose database manager (DBM) has five responsibilities: a. interaction with the file manager.

Exercises

5

b. c. d. e.

integrity enforcement. security enforcement. backup and recovery. concurrency control.

If these responsibilities were not met by a given DBM (and the text points out that sometimes a responsibility is omitted by design, such as concurrency control on a single-user DBM for a micro computer) the following problems can occur, respectively: a. No DBM can do without this, if there is no file manager interaction then nothing stored in the files can be retrieved. b. Consistency constraints may not be satisfied, account balances could go below the minimum allowed, employees could earn too much overtime (e.g., hours > 80) or, airline pilots may fly more hours than allowed by law. c. Unauthorized users may access the database, or users authorized to access part of the database may be able to access parts of the database for which they lack authority. For example, a high school student could get access to national defense secret codes, or employees could find out what their supervisors earn. d. Data could be lost permanently, rather than at least being available in a consistent state that existed prior to a failure. e. Consistency constraints may be violated despite proper integrity enforcement in each transaction. For example, incorrect bank balances might be reflected due to simultaneous withdrawals and deposits, and so on. 1.5 What are five main functions of a database administrator? Answer: Five main functions of a database administrator are: • • • • • To create the scheme definition To define the storage structure and access methods To modify the scheme and/or physical organization when necessary To grant authorization for data access To specify integrity constraints

1.6 List seven programming languages that are procedural and two that are nonprocedural. Which group is easier to learn and use? Explain your answer. Answer: Programming language classification: • Procedural: C, C++, Java, Basic, Fortran, Cobol, Pascal • Non-procedural: Lisp and Prolog Note: Lisp and Prolog support some procedural constructs, but the core of both these languages is non-procedural. In theory, non-procedural languages are easier to learn, because they let the programmer concentrate on what needs to be done, rather than how to do it. This is not always true in practice, especially if procedural languages are learned first.

6

Chapter 1

Introduction

1.7 List six major steps that you would take in setting up a database for a particular enterprise. Answer: Six major steps in setting up a database for a particular enterprise are: • Define the high level requirements of the enterprise (this step generates a document known as the system requirements specification.) • Define a model containing all appropriate types of data and data relationships. • Define the integrity constraints on the data. • Define the physical level. • For each known problem to be solved on a regular basis (e.g., tasks to be carried out by clerks or Web users) define a user interface to carry out the task, and write the necessary application programs to implement the user interface. • Create/initialize the database. 1.8 Consider a two-dimensional integer array of size n × m that is to be used in your favorite programming language. Using the array as an example, illustrate the difference (a) between the three levels of data abstraction, and (b) between a schema and instances. Answer: Let tgrid be a two-dimensional integer array of size n × m. a. • The physical level would simply be m × n (probably consecutive) storage locations of whatever size is specified by the implementation (e.g., 32 bits each). • The conceptual level is a grid of boxes, each possibly containing an integer, which is n boxes high by m boxes wide. • There are 2m×n possible views. For example, a view might be the entire array, or particular row of the array, or all n rows but only columns 1 through i. • 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 7 16 89 17 90 412 8

b.

C 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.
7

8

Chapter 2

Entity Relationship Model

Changes from 3rd 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-officer), 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

address driver-id person name owns license

model year car report-number location date

driver

participated

accident

damage-amount

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 office 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 identification 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 office. 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

insurance date−admitted name ss# patients test−log Dr−Patient date−checked−out

test_id

test

performed_by

doctors

test_name

date

time

dss# result

name

specialization

Figure 2.2 sid name time

E-R diagram for a hospital. secno room iid name

student

enrols year

course− offerings semester is offered

teaches

instructor

dept

title

program

grade

syllabus prerequisite requires maincourse credits course

courseno

title

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

sid

name

time

secno

room

student

takes marks year

course− offerings semester

courseno

program

eid name

exam place

time

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

sid

name

time

secno

room

student

takes year

course− offerings semester

courseno

program marks

examof

exam name place

time

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 entity

Exercises

13

date

matchid

stadium

name

age

opponent

match

played

player

own _score

opp_score

score

season_score

Figure 2.6 matchid E-R diagram for favourite team statistics. stadium score name age

date

match

played

player

season_score score team_played player_of

result team

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 reflect 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 Define the concept of aggregation. Give two examples of where this concept is useful.

14

Chapter 2

Entity Relationship Model

name

deadline

name

employee

works−in

project

requires

machinery

name

Figure 2.8

E-R diagram Example 1 of aggregation.

name

tie−up−date

name

manufacturer

tie−up

distributor

distribute

product

name

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 specified for it the set of products which are to be distributed. See Figure 2.9

Exercises

15

name

address

name

address

phone URL

URL

author

publisher

address written-by published-by name customer year book title price ISBN contains shopping-basket basketID number basket-of

email phone

stocks

warehouse address phone

code

number
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 in

16

Chapter 2

Entity Relationship Model

ss#

name

dept

courseno

student

takes

class

ss#

name

teamname

student

plays

sport

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 final 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 defined, 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 influence 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 difficult 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

department

s-number

enrollment

course

section of

section

for

c-number room in exam

r-number

capacity

building

time

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 office 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 efficiency. 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, influence 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 efficient 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 difficult 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 office 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 specific class meets, scheme 2.14 is probably the best choice.

18

Chapter 2

Entity Relationship Model

sid

name

time

secno

room

iid

name

student

enrols year

course− offerings semester is offered

teaches

instructor

dept

title

program

grade

syllabus prerequisite requires maincourse credits course

courseno

title

Figure 2.13

E-R diagram for University(a) . room_no building room

ss#

name

time

secno

meetsin

iss#

name

student

enrols year

course− offerings semester is offered

teaches

instructor

dept

title

program

grade

syllabus prerequisite requires maincourse credits course

courseno

title

Figure 2.14

E-R diagram for University(b).

Exercises

19

ss#

name

time

secno

room

iss#

name

student

enrols year

course− offerings semester is offered

teaches

instructor

dept

title

program

grade

syllabus

courseno

prerequisite

course

title

credits

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

A A RA B R (a) C B RB E (b) RC C

R1

A

R3

B

R2 (c)

C

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 satisfies 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

A

RA

B

R B

E

R

C

C

Figure 2.17

E-R diagram to Exercise 2.17b.
A

RA

B

R B

E

R

C

C

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 figure. 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

model

sales-taxrate

sales-volume

commercialvehicle-tax-rate maxpassengers

vehicle isa luxury-vehicletax-rate

commercialvehicle isa

non-commercialvehicle isa

bus

van

car type

motorcycle

Figure 2.19

E-R diagram of motor-vehicle sales company.

cle tax, and each kind of commercial vehicle has a passenger carrying capacity specified 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-defined and user-defined 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 conditiondefined design constraint, membership in the lower level entity-sets is evaluated on the basis of whether or not an entity satisfies an explicit condition or predicate.User-defined 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-defined 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 more

Exercises

23

X

Y

ISA

ISA

A

B

C

Figure 2.20

E-R diagram for Exercise 2.24 (attributes not shown).

customer customer−id customer−name customer−street customer−city 1..1 borrower 0..1

loan loan−number amount

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 define 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 qualified 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 in

24

Chapter 2

Entity Relationship Model

customer customer−id customer−name customer−street customer−city 1..1

account account−number 0..* balance

depositor access−date

Figure 2.22

UML equivalent of Figure 2.10

employee employee−name 0..1 manager employee−id telephone−num 1..* worker works−for

Figure 2.23

UML equivalent of Figure 2.12

job title level

work−job employee employee−name emp−work employee−id street city
Figure 2.24

works−on workid

work−branch

branch branch−name assets branch−city

UML equivalent of Figure 2.13

Exercises

25

person name street city

employee salary

customer credit−rating

officer officer−num

teller station−num hrs−worked

secretary hrs−worked

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 difficulties. 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 identifiers 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 difficulties. 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 modification 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 field. 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 modified earlier due to the merger, is itself modified 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 modified 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 identified 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 difficult. 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.

29

30

Chapter 3

Relational Model

address driver-id person name owns license

model year car report-number location date

driver

participated

accident

damage-amount

Figure 3.38. E-R diagram.

Exercises
3.1 Design a relational database for a university registrar’s office. The office 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 definition, 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 Jones 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 (employee ½ (σcompany-name = “First Bank Corporation” (works)))

32

Chapter 3

Relational Model

works ½ employee) d. Πperson-name (employee ½ works ½ company) e. Πperson-name ((employee ½ manages) ½(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 ½(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 (borrower

c. Πperson-name, street, city (σ(company-name = “First Bank Corporation” ∧ salary > 10000)

½

loan

½

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 ((borrower

½

loan)

½

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) (r ½θ s) can be defined as (r ½θ s) ∪ ((r − ΠR (r ½θ 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) (r ½ θ s) can be defined as (r ½θ s) ∪ ((null, null, . . . , null) × (s − ΠS (r ½θ 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) (r ½ θ s) can be defined as (r ½θ s) ∪ ((null, null, . . . , null) × (s − ΠS (r ½θ s))) ∪ ((r − ΠR (r ½θ s)) × (null, null, . . . , null)) The first 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. b. c. d. Modify the database so that Jones now lives in Newtown. Give all employees of First Bank Corporation a 10 percent salary raise. Give all managers in this database a 10 percent salary raise. 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 find 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-name Gcount-distinct person-name (works) t2 ← maxnum-employees (ρcompany-strength(company-name,num-employees) (t1 )) Πcompany-name (ρt3 (company-name,num-employees) (t1 ) ½ ρt4 (num-employees) (t2 )) b. t1 ← company-name Gsum salary (works) t2 ← minpayroll (ρcompany-payroll(company-name,payroll) (t1 )) Πcompany-name (ρt3 (company-name,payroll) (t1 ) ½ ρt4 (payroll) (t2 )) c. t1 ← company-name Gavg salary (works) t2 ← σcompany-name = “First Bank Corporation” (t1 )

Exercises

35

Πt3 .company-name ((ρt3 (company-name,avg-salary) (t1 )) ½t3 .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 define 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 significant problems if updates are expressed with them. The difficulty is that a modification to the database expressed in terms of a view must be translated to a modification 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 S = (A, B, C) = (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. b. c. d. ΠA (r) σB = 17 (r) r × s Π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. b. c. d. e. f. ΠA (r1 ) σB = 17 (r1 ) r1 ∪ r2 r1 ∩ r2 r1 − r2 ΠA,B (r1 ) ½ ΠB,C (r2 )

Answer: a. b. c. d. e. f. {< t > | ∃ p, q (< t, p, q > ∈ r1 )} {< a, b, c > | < a, b, c > ∈ r1 ∧ b = 17} {< a, b, c > | < a, b, c > ∈ r1 ∨ < a, b, c > ∈ r2 } {< a, b, c > | < a, b, c > ∈ r1 ∧ < a, b, c > ∈ r2 } {< a, b, c > | < a, b, c > ∈ r1 ∧ < a, b, c > ∈ r2 } {< 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. { < p > | ∃ 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

e.

f.

g.

h.

ii. {< p > | ∃ st, c, co, sa (< p, st, c > ∈ employee ∧ < p, co, sa > ∈ works ∧ < co, c > ∈ company)} 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)} 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. { < p > | ∃ 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. { < p > | ∃ s, c (< p, s, c > ∈ employee) ∧ ¬ ∃ x, y (y = “First Bank Corporation”∧ < p, y, x > ∈ works)} 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. {< p > | ∃ c, s (< p, c, s > ∈ works ∧ ∀ p2 , c2 , s2 (< p2 , c2 , s2 > ∈ works ∨ c2 = “Small Bank Corporation” ∨ s > s2 ))} 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. b. c. d.

{< a > | ∃ b (< a, b > ∈ r ∧ b = 17)} {< a, b, c > | < a, b > ∈ r ∧ < a, c > ∈ s} {< a > | ∃ b (< a, b > ∈ r) ∨ ∀ c (∃ d (< d, c > ∈ s) ⇒ < a, c > ∈ s)} {< a > | ∃ c (< a, c > ∈ s ∧ ∃ b1 , b2 (< a, b1 > ∈ r ∧ < c, b2 > ∈ r ∧ b1 > b2 ))}

Answer: a. b. c. d. ΠA (σB = 17 (r)) r ½ s ΠA (r) ∪ (r ÷ σB (ΠC (s))) Πr.A ((r ½ s) ½c = 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. r b. r c. r

½s ½s ½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 do

Exercises

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 significantly 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 3rd edition: Our coverage of SQL has been expanded to include the with clause, ODBC, JDBC, and schemas, catalogs and environments (Section 4.14).
41

42

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 from where and and count (distinct name) accident, participated, person accident.report-number = participated.report-number participated.driver-id = person.driver-id 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 from where count (distinct *) accident 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 find 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 = ’Toyota’ 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.city = R.city 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) (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. b. c. d. Modify the database so that Jones now lives in Newtown. Give all employees of First Bank Corporation a 10 percent raise. Give all managers of First Bank Corporation a 10 percent raise. 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) 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. b. c. d. ΠA (r) σB = 17 (r) r × s Π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 ∩ r2

50

Chapter 4

SQL

c. r1 − r2 d. ΠAB (r1 ) Answer: a. r1 ∪ r2

½

ΠBC (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 ) ½ Π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 satisfies (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 satisfies (x2 not in S). It cannot be equal to any element w belonging to S, and hence (x2 all S) will be satisfied. Therefore the two expressions are equivalent. 4.8 Consider the relational database of Figure 4.13. Using SQL, define 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 first (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 and

52

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 find 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 the 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 find 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 defined as follows: coalesce(A1, A2 , . . . , An ) returns the first 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 definition 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 create domain create table (employee-name street city primary key create table (employee-name company-name salary primary key create table (company-name city primary key create table (employee-name manager-name primary key

city-names char(30) person-names char(20) employee person-names, char(30), city-names, (employee-name)) works person-names, company-names, numeric(8, 2), (employee-name)) company company-names, city-names, (company-name)) manages person-names, person-names, (employee-name))

4.15 Write check conditions for the schema you defined 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 specific 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 efficient 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 3rd 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 briefly. Quel has been dropped.

57

58

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.CNT.ALL 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 I. report-number date location 4007 1997-01-01 Berkeley

Exercises

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 I. driver car license report-number damage-amount 4007 3000 license license

owns driver-id driver car person license license

year model year Toyota

driver-id name address driver Williams d. Delete the car “Mazda” that belongs to “John Smith.” person driver-id name driver John Smith owns driver-id driver license license address

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. person-name company-name P. x First Bank Corporation ii. query(X) :- works(X, “First Bank Corporation”, Y) works salary

b. Find the names and cities of residence of all employees who work for First Bank Corporation. i. works person-name company-name salary x First Bank Corporation

employee person-name street city P. x P. y ii. query (X, Y ) :- employee (X, Z, Y ), works (X, “First Bank Corporation”, W ) 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. If people may work for several companies, the following solutions will only list those who earn more than $10,000 per annum from “First Bank Corporation” alone. i. employee person-name street city P. x P. y P. z

Exercises

61

works ii.

person-name x

company-name First Bank Co

salary > 10000

query (X, Y, Z) :- lives (X, Y, Z), works (X, “First Bank Corporation”, W ), W > 10000 d. Find all employees who live in the city where the company for which they work is located. i. employee person-name street city P. x y works person-name company-name salary x c company

company-name city c y ii. query (X) :- employee (X, Y, Z), works (X, V, W ), company (V, Z) e. Find all employees who live in the same city and on the same street as their managers. i. employee person-name street city P. x s c y s c manages person-name manager − name x y ii. query (X) :- lives (X, Y, Z), manages (X, V ), lives (V, Y, Z) f. Find all employees in the database who do not work for First Bank Corporation. The following solutions assume that all people work for exactly one company. i. person-name company-name salary P. x ¬ First Bank Co ii. query (X) :- works (X, Y, Z), Y = “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 solutions are slightly more complicated. They are given below :works

62

Chapter 5

Other Relational Languages

i. employee person-name street city P. x works ¬ ii. person-name company-name x First Bank Corporation salary

query (X) :- employee (X, Y, Z), ¬ p1 (X) p1 (X) :- works(X, “First Bank Corporation”, W )

g. Find all employees who earn more than every employee of Small Bank Corporation. The following solutions assume that all people work for at most one company. i. works person-name P. x or works ¬ ii. query (X) :- works (X, Y, Z), ¬ p (X) p (X) :- works(X, C, Y 1), works (V, “Small Bank Corporation”, Y ), Y > Y 1 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. Note: Small Bank Corporation will be included in each answer. i. located-in company-name Small Bank Corporation P. c Small Bank Corporation conditions CNT.ALL. y = CNT.ALL. x ii. city x y y person-name P. x company-name salary y Small Bank Co > y company-name Small Bank Co salary y > MAX.ALL. y

Exercises

63

query(X) :- company(X, C), not p(X) p(X) :- company(X, C1), company(“Small Bank Corporation”, C2), not company(X, C2) 5.3 Consider the relational database of Figure 5.15. where the primary keys are underlined. Give expressions in QBE for each of the following queries: a. Find all employees who earn more than the average salary of all employees of their company. b. Find the company that has the most employees. c. Find the company that has the smallest payroll. d. Find those companies whose employees earn a higher salary, on average, than the average salary at First Bank Corporation. Answer: a. 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. works person-name company-name salary P. y x y z conditions x > AVG.ALL. z b. Find the company that has the most employees. works person-name company-name salary x P.G. y G.

conditions CNT.UNQ. x ≥ MAX.CNT.UNQ.ALL. y c. Find the company that has the smallest payroll.

employee (person-name, street, city) works (person-name, company-name, salary) company (company-name, city) manages (person-name, manager-name) Figure 5.15. Employee database.

64

Chapter 5

Other Relational Languages

works

person-name company-name salary P.G. x G. y conditions SUM.ALL. x ≤ MIN.SUM.ALL. y

d. Find those companies whose employees earn a higher salary, on average, than the average salary at First Bank Corporation. works person-name company-name salary P.G. x First Bank Corporation y

conditions AVG.ALL. x > AVG.ALL. y

5.4 Consider the relational database of Figure 5.15. Give expressions in QBE for each of the following queries: a. b. c. d. Modify the database so that Jones now lives in Newtown. Give all employees of First Bank Corporation a 10 percent raise. Give all managers in the database a 10 percent raise. Give all managers in the database a 10 percent 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: The solutions assume 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. employee person-name street city Jones U.Newtown b. Give all employees of First Bank Corporation a 10-percent raise. works U. c. Give all managers in the database a 10-percent raise. manages person-name manager-name x person-name company-name First Bank Corporation salary x x * 1.1

Exercises

65

salary y U. y * 1.1 d. Give all managers in the database a 10-percent raise, unless the salary would be greater than $100,000. In such cases, give only a 3-percent raise. Two separate update operations must be performed. Each update operation has its own set of skeleton tables. First update: manages person-name manager-name x works U. conditions y > 100000/1.1 Second update: manages person-name manager-name x works U. conditions y ≤ 100000/1.1 e. Delete all tuples in the works relation for employees of Small Bank Corporation. works person-name company-name salary D. Small Bank Co 5.5 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 expressions in QBE, and Datalog equivalent to each of the following queries: a. ΠA (r) b. σB = 17 (r) c. r × s person-name x company-name salary y y * 1.1 person-name company-name x salary y y * 1.03

works

person-name company-name x

66

Chapter 5

Other Relational Languages

d. ΠA,F (σC = D (r × s)) Answer: a. ΠA (r) i. r ii. query (X) :- r (X, Y, Z) b. σB = 17 (r) i. r P. A B C 17 A B P. C

ii. query (X, Y, Z) :- r (X, Y, Z), Y = 17 c. r × s i. result P. A a r B b A a D d C c B b E e D d C c F f E e F f

s

ii. query (X, Y, Z, U, V, W ) :- r (X, Y, Z), s (U, V, W ) d. ΠA,F (σC = D (r × s)) i. result P. r A a D c A a B F f C c F f

s

E

ii. query (X, Y ) :- r (X, V, W ), s (W, Z, Y )

Exercises

67

5.6 Let R = (A, B, C), and let r1 and r2 both be relations on schema R. Give expressions in QBE, and Datalog equivalent to each of the following queries: a. b. c. d. r1 ∪ r2 r1 ∩ r2 r1 − r2 ΠAB (r1 )

½

ΠBC (r2 )

Answer: a. r1 ∪ r2 i. result P. P. r1 A a A a d B b e B C b c C f C c f

r2 ii.

A B d e

query(X, Y, Z) :- r1 (X, Y, Z) query(X, Y, Z) :- r2 (X, Y, Z)

b. r1 ∩ r2 i. r1 P. r2 A a A a B C b c B b C c

ii. query(X, Y, Z) :- r1 (X, Y, Z), r2 (X, Y, Z) c. r1 − r2 i. r1 P. A a B C b c

68

Chapter 5

Other Relational Languages

r2 ¬

A a

B b

C c

ii. query(X, Y, Z) :- r1 (X, Y, Z), not r2 (X, Y, Z) d. ΠAB (r1 ) i.

½

ΠBC (r2 ) result P. r1 A a A A a B b B b B b C C c

r2

C c

ii. query(X, Y, Z) :- r1 (X, Y, V), r2 (W, Y, Z)

5.7 Let R = (A, B) and S = (A, C), and let r(R) and s(S) be relations. Write expressions in QBE and Datalog for each of the following queries: 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)} i. r ii. query (X) :- r (X, 17) b. {< a, b, c > | < a, b > ∈ r ∧ < a, c > ∈ s} i. r A a B b A B P. 17

Exercises

69

s

A a

C c

result A B C P. a b c ii. query(X, Y, Z) :- r(X, Y), s(X, Z) c. {< a > | ∃ c (< a, c > ∈ s ∧ ∃ b1 , b2 (< a, b1 > ∈ r ∧ < c, b2 > ∈ r ∧ b1 > b2 ))} i. r A a c A P. a B > s s C c

s

ii. query (X) :- s (X, Y ), r (X, Z), r (Y, W ), Z > W 5.8 Consider the relational database of Figure 5.15. Write a Datalog program for each of the following queries: a. Find all employees who work (directly or indirectly) under the manager “Jones”. b. Find all cities of residence of all employees who work (directly or indirectly) under the manager “Jones”. c. Find all pairs of employees who have a (direct or indirect) manager in common. d. Find all pairs of employees who have a (direct or indirect) manager in common, and are at the same number of levels of supervision below the common manager. Answer: a. Find all employees who work (directly or indirectly) under the manager “Jones”. query (X) :- p (X) p (X) :- manages (X, “Jones”) p (X) :- manages (X, Y ), p (Y ) b. Find all cities of residence of all employees who work (directly or indirectly) under the manager “Jones”. query(X, C) :- p(X), employee(X, S, C) p(X) :- manages(X, “Jones”) p(X) :- manages(X, Y), p(Y)

70

Chapter 5

Other Relational Languages

c. Find all pairs of employees who have a (direct or indirect) manager in common. query(X, Y) :- p(X, W), p(Y, W) p(X, Y) :- manages(X, Y) p(X, Y) :- manages(X, Z), p(Z, Y) d. Find all pairs of employees who have a (direct or indirect) manager in common, and are at the same number of levels of supervision below the common manager. query(X, Y) :- p(X, Y) p(X, Y) :- manages(X, Z), manages(Y, Z) p(X, Y) :- manages(X, V), manages(Y, W), p(V, W) 5.9 Write an extended relational-algebra view equivalent to the Datalog rule p(A, C, D) :– q1 (A, B), q2 (B, C), q3 (4, B), D = B + 1 . Answer: Let us assume that q1, q2 and q3 are instances of the schema (A1, A2). The relational algebra view is create view P as Πq1.A1,q2.A2,q1.A2+1 (σq3.A1=4 ∧ q1.A2=q2.A1 ∧ q1.A2=q3.A2 (q1 × q2 × q3)) 5.10 Describe how an arbitrary Datalog rule can be expressed as an extended relationalalgebra view. Answer: A Datalog rule has two parts, the head and the body. The body is a comma separated list of literals. A positive literal has the form p(t1 , t2 , . . . , tn ) where p is the name of a relation with n attributes, and t1 , t2 , . . . , tn are either constants or variables. A negative literal has the form ¬p(t1 , t2 , . . . , tn ) where p has n attributes. In the case of arithmetic literals, p will be an arithmetic operator like >, = etc. We consider only safe rules; see Section 5.2.4 for the definition of safety of Datalog rules. Further, we assume that every variable that occurs in an arithmetic literal also occurs in a positive non-arithmetic literal. Consider first a rule without any negative literals. To express the rule as an extended relational-algebra view, we write it as a join of all the relations referred to in the (positive) non-arithmetic literals in the body, followed by a selection. The selection condition is a conjunction obtained as follows. If p1 (X, Y ), p2 (Y, Z) occur in the body, where p1 is of the schema (A, B) and p2 is of the schema (C, D), then p1 .B = p2 .C should belong to the conjunction. The arithmetic literals can then be added to the condition. As an example, the Datalog query query(X, Y) :- works(X, C, S1), works(Y, C, S2), S1 > S2, manages(X, Y) becomes the following relational-algebra expression:

Exercises

71

E1 = σ(w1.company-name = w2.company-name ∧ w1.salary>w2.salary ∧ manages.person-name = w1.person-name ∧ manages.manager -name = w2.person-name) (ρw1 (works) × ρw2 (works) × manages) Now suppose the given rule has negative literals. First suppose that there are no constants in the negative literals; recall that all variables in a negative literal must also occur in a positive literal. Let ¬q(X, Y ) be the first negative literal, and let it be of the schema (E, F ). Let Ei be the relational algebra expression obtained after all positive and arithmetic literals have been handled. To handle this negative literal, we generate the expression Ej = Ei

½ (ΠA ,A
1

2

(Ei ) − q)

where A1 and A2 are the attribute names of two columns in Ei which correspond to X and Y respectively. Now let us consider constants occurring in a negative literal. Consider a negative literal of the form ¬q(a, b, Y ) where a and b are constants. Then, in the above expression defining Ej we replace q by σA1 =a∧A2 =b (q). Proceeding in a similar fashion, the remaining negative literals are processed, finally resulting in an expression Ew . Finally the desired attributes are projected out of the expression. The attributes in Ew corresponding to the variables in the head of the rule become the projection attributes. Thus our example rule finally becomes the view:create view query as Πw1.person-name, w2.person−name (E2 ) If there are multiple rules for the same predicate, the relational-algebra expression defining the view is the union of the expressions corresponding to the individual rules. The above conversion can be extended to handle rules that satisfy some weaker forms of the safety conditions, and where some restricted cases where the variables in arithmetic predicates do not appear in a positive non-arithmetic literal.

C H A P T E R

6

Integrity and Security

This chapter presents several types of integrity constraints, including domain constraints, referential integrity constraints, assertions and triggers, as well as security and authorization. Referential integrity constraints, and domain constraints are an important aspect of the specification of a relational database design. Assertions are seeing increasing use. Triggers are widely used, although each database supports its own syntax and semantics for triggers; triggers were standardized as part of SQL:1999, and we can expect databases to provide support for SQL:1999 triggers. Functional dependencies are now taught as part of normalization instead of being part of the integrity constraints chapter as they were in the 3rd edition. The reason for the change is that they are used almost exclusively in database design, and no database system to our knowledge supports functional dependencies as integrity constraints. Covering them in the context of normalization helps motivate students to spend the effort to understand the intricacies of reasoning with functional dependencies. Security is a major topic in its own right. Since any system is only as secure as its weakest component, a system builder must consider all aspects of security. This chapter focuses only on those security issues that are specific to databases. In an advanced course, this material can be supplemented by discussion of security issues in operating systems and in distributed systems. Changes from 3rd edition: Trigger coverage is now based on the SQL:1999 standard. At the time of publication of the 3rd edition, triggers had not been standardized. The notion of roles for authorization has been introduced in this edition, now that it is a part of the SQL:1999 standard. Coverage of encryption has been updated to cover recent developments.

73

74

Chapter 6

Integrity and Security

Exercises
6.1 Complete the SQL DDL definition of the bank database of Figure 6.2 to include the relations loan and borrower. Answer: create table loan (loan-number char(10), branch-name char(15), amount integer, primary key (loan-number), foreign key (branch-name) references branch)

create table borrower (customer-name char(20), loan-number char(10), primary key (customer-name, loan-number), foreign key (customer-name) references customer, foreign key (loan-number) references loan)

Declaring the pair customer-name, loan-number of relation borrower as primary key ensures that the relation does not contain duplicates. 6.2 Consider the following relational database: employee (employee-name, street, city) works (employee-name, company-name, salary) company (company-name, city) manages (employee-name, manager-name) Give an SQL DDL definition of this database. Identify referential-integrity constraints that should hold, and include them in the DDL definition. Answer: create table employee (person-name char(20), street char(30), city char(30), primary key (person-name) )

Exercises

75

create table works (person-name char(20), company-name char(15), salary integer, primary key (person-name), foreign key (person-name) references employee, foreign key (company-name) references company)

create table company (company-name char(15), city char(30), primary key (company-name)) create table manages (person-name char(20), manager-name char(20), primary key (person-name), foreign key (person-name) references employee, foreign key (manager-name) references employee) Note that alternative datatypes are possible. Other choices for not null attributes may be acceptable. 6.3 Referential-integrity constraints as defined in this chapter involve exactly two relations. Consider a database that includes the following relations: salaried-worker (name, office, phone, salary) hourly-worker (name, hourly-wage) address (name, street, city) Suppose that we wish to require that every name that appears in address appear in either salaried-worker or hourly-worker, but not necessarily in both. a. Propose a syntax for expressing such constraints. b. Discuss the actions that the system must take to enforce a constraint of this form. Answer: a. For simplicity, we present a variant of the SQL syntax. As part of the create table expression for address we include foreign key (name) references salaried-worker or hourly-worker b. To enforce this constraint, whenever a tuple is inserted into the address relation, a lookup on the name value must be made on the salaried-worker relation and (if that lookup failed) on the hourly-worker relation (or vice-versa).

76

Chapter 6

Integrity and Security

6.4 SQL allows a foreign-key dependency to refer to the same relation, as in the following example: create table manager (employee-name char(20), manager-name char(20), primary key employee-name, foreign key (manager-name) references manager on delete cascade ) Here, employee-name is a key to the table manager, meaning that each employee has at most one manager. The foreign-key clause requires that every manager also be an employee. Explain exactly what happens when a tuple in the relation manager is deleted. Answer: The tuples of all employees of the manager, at all levels, get deleted as well! This happens in a series of steps. The initial deletion will trigger deletion of all the tuples corresponding to direct employees of the manager. These deletions will in turn cause deletions of second level employee tuples, and so on, till all direct and indirect employee tuples are deleted. 6.5 Suppose there are two relations r and s, such that the foreign key B of r references the primary key A of s. Describe how the trigger mechanism can be used to implement the on delete cascade option, when a tuple is deleted from s. Answer: We define triggers for each relation whose primary-key is referred to by the foreign-key of some other relation. The trigger would be activated whenever a tuple is deleted from the referred-to relation. The action performed by the trigger would be to visit all the referring relations, and delete all the tuples in them whose foreign-key attribute value is the same as the primary-key attribute value of the deleted tuple in the referred-to relation. These set of triggers will take care of the on delete cascade operation. 6.6 Write an assertion for the bank database to ensure that the assets value for the Perryridge branch is equal to the sum of all the amounts lent by the Perryridge branch. Answer: The assertion-name is arbitrary. We have chosen the name perry. Note that since the assertion applies only to the Perryridge branch we must restrict attention to only the Perryridge tuple of the branch relation rather than writing a constraint on the entire relation. create assertion perry check (not exists (select * from branch where branch-name = ’Perryridge’ and assets = (select sum (amount) from loan where branch-name = ’Perryridge’)))

Exercises

77

6.7 Write an SQL trigger to carry out the following action: On delete of an account, for each owner of the account, check if the owner has any remaining accounts, and if she does not, delete her from the depositor relation. Answer: create trigger check-delete-trigger after delete on account referencing old row as orow for each row delete from depositor where depositor.customer-name not in ( select customer-name from depositor where account-number orow.account-number ) end 6.8 Consider a view branch-cust defined as follows: create view branch-cust as select branch-name, customer-name from depositor, account where depositor.account-number = account.account-number Suppose that the view is materialized, that is, the view is computed and stored. Write active rules to maintain the view, that is, to keep it up to date on insertions to and deletions from depositor or account. Do not bother about updates. Answer: For inserting into the materialized view branch-cust we must set a database trigger on an insert into depositor and account. We assume that the database system uses immediate binding for rule execution. Further, assume that the current version of a relation is denoted by the relation name itself, while the set of newly inserted tuples is denoted by qualifying the relation name with the prefix – inserted. The active rules for this insertion are given below – define trigger insert into branch-cust via depositor after insert on depositor referencing new table as inserted for each statement insert into branch-cust select branch-name, customer-name from inserted, account where inserted.account-number = account.account-number define trigger insert into branch-cust via account after insert on account referencing new table as inserted for each statement insert into branch-cust select branch-name, customer-name from depositor, inserted where depositor.account-number = inserted.account-number

78

Chapter 6

Integrity and Security

Note that if the execution binding was deferred (instead of immediate), then the result of the join of the set of new tuples of account with the set of new tuples of depositor would have been inserted by both active rules, leading to duplication of the corresponding tuples in branch-cust. The deletion of a tuple from branch-cust is similar to insertion, except that a deletion from either depositor or account will cause the natural join of these relations to have a lesser number of tuples. We denote the newly deleted set of tuples by qualifying the relation name with the keyword deleted. define trigger delete from branch-cust via depositor after delete on depositor referencing old table as deleted for each statement delete from branch-cust select branch-name, customer-name from deleted, account where deleted.account-number = account.account-number define trigger delete from branch-cust via account after delete on account referencing old table as deleted for each statement delete from branch-cust select branch-name, customer-name from depositor, deleted where depositor.account-number = deleted.account-number 6.9 Make a list of security concerns for a bank. For each item on your list, state whether this concern relates to physical security, human security, operatingsystem security, or database security. Answer: Let us consider the problem of protecting our sample bank database. Some security measures at each of the four levels are mentioned below a. Physical level - The system from which the relations can be accessed and modified should be placed in a locked, well-guarded, and impregnable room. b. Human level - A proper key transfer policy should be enforced for restricting access to the “system room” mentioned above. Passwords for gaining access to the database should be known only to trusted users. c. Operating System level - Login passwords should be difficult to guess and they should be changed regularly. No user should be able to gain unauthorized access to the system due to a software bug in the operating system. d. Database System level - The users should be authorized access only to relevant parts of the database. For example, a bank teller should be allowed to modify values for the customer’s balance, but not for her own salary. 6.10 Using the relations of our sample bank database, write an SQL expression to define the following views: a. A view containing the account numbers and customer names (but not the balances) for all accounts at the Deer Park branch.

Exercises

79

b. A view containing the names and addresses of all customers who have an account with the bank, but do not have a loan. c. A view containing the name and average account balance of every customer of the Rock Ridge branch. Answer: a. create view deer-park as select account-number, customer-name from depositor, account where branch-name = ’Deer Park’ and depositor.account-number = account.account-number b. create view no-debt as select * from customer where customer-name in (select customer-name from depositor) minus (select customer-name from borrower) c. create view avg-bal as select customer-name, avg(balance) from depositor, account where depositor.account-number = account.account-number and branch-name = ’Rock Ridge’ group by customer-name 6.11 For each of the views that you defined in Exercise 6.10, explain how updates would be performed (if they should be allowed at all). Hint: See the discussion of views in Chapter 3. Answer: To insert (account-number, name) into the view deer-park we insert the tuple (Deer Park, account-number, null) into the account relation and the tuple (name, account-number) into the depositor relation. Updates to the views no-debt and avg-bal present serious problems. If we insert into the no-debt view, the system must reject the insertion if the customer has a loan. The overhead of updating through this view is so high that most systems would disallow update. The avg-bal view cannot be updated since the result of an aggregate operation depends on several tuples, not just one. 6.12 In Chapter 3, we described the use of views to simplify access to the database by users who need to see only part of the database. In this chapter, we described the use of views as a security mechanism. Do these two purposes for views ever conflict? Explain your answer. Answer: Usually, a well-designed view and security mechanism can avoid con-

80

Chapter 6

Integrity and Security

flicts between ease of access and security. However, as the following example shows, the two purposes do conflict in case the mechanisms are not designed carefully. Suppose we have a database of employee data and a user whose view involves employee data for employees earning less than $10,000. If this user inserts employee Jones, whose salary is $9,000, but accidentally enters $90,000, several existing database systems will accept this update as a valid update through a view. However, the user will be denied access to delete this erroneous tuple by the security mechanism. 6.13 What is the purpose of having separate categories for index authorization and resource authorization? Answer: Index and resource authorization should be special categories to allow certain users to create relations (and the indices to operate on them) while preventing these time-consuming and schema-changing operations from being available to many users. Separating index and resource authorization allows a user to build an index on existing relations, say, for optimization purposes, but allows us to deny that user the right to create new relations. 6.14 Database systems that store each relation in a separate operating-system file may use the operating system’s security and authorization scheme, instead of defining a special scheme themselves. Discuss an advantage and a disadvantage of such an approach. Answer: Database systems have special requirements which are typically more refined than most operating systems. For example, a single user may have different privileges on different files throughout the system, including changing indices and attributes which file systems typically don’t monitor. The advantage of using the operating system’s security mechanism is that it simplifies the database system and can be used for simple (read/write) security measures. 6.15 What are two advantages of encrypting data stored in the database? Answer: a. Encrypted data allows authorized users to access data without worrying about other users or the system administrator gaining any information. b. Encryption of data may simplify or even strengthen other authorization mechanisms. For example, distribution of the cryptographic key amongst only trusted users is both, a simple way to control read access, and an added layer of security above that offered by views. 6.16 Perhaps the most important data items in any database system are the passwords that control access to the database. Suggest a scheme for the secure storage of passwords. Be sure that your scheme allows the system to test passwords supplied by users who are attempting to log into the system. Answer: A scheme for storing passwords would be to encrypt each password, and then use a hash index on the user-id. The user-id can be used to easily access the encrypted password. The password being used in a login attempt is then encrypted and compared with the stored encryption of the correct password. An

Exercises

81

advantage of this scheme is that passwords are not stored in clear text and the code for decryption need not even exist!

C H A P T E R

7

Relational-Database Design

This chapter presents the principles of relational database design. Undergraduates frequently find this chapter difficult. It is acceptable to cover only Sections 7.1, 7.2 and 7.4 for classes that find the material particularly difficult. However, a careful study of data dependencies and normalization is a good way to introduce students to the formal aspects of relational database theory. There are many ways of stating the definitions of the normal forms. We have chosen a style which we think is the easiest to present and which most clearly conveys the intuition of the normal forms. Changes from 3rd edition: There are many changes to this chapter from the 3rd edition. 1NF is now defined formally. Functional dependencies are now covered in this chapter, instead of Chapter 6. The reason is that normalization provides the real motivation for functional dependencies, since they are used primarily for normalization. We have described a simplified procedure for functional dependency inference based on attribute closure, and provided simplified procedures to test for normal forms. Coverage of multivalued dependency theory and normal forms beyond 4NF (that is, PJNF and DKNF) has been moved into Appendix C (which is available on the web, not in the print form of the book). The process of practical relational schema design has been described in significantly more detail, along with some design problems that are not caught by the usual normalization process.

83

84

Chapter 7

Relational-Database Design

Exercises
7.1 Explain what is meant by repetition of information and inability to represent information. Explain why each of these properties may indicate a bad relationaldatabase design. Answer: • Repetition of information is a condition in a relational database where the values of one attribute are determined by the values of another attribute in the same relation, and both values are repeated throughout the relation. This is a bad relational database design because it increases the storage required for the relation and it makes updating the relation more difficult. • Inability to represent information is a condition where a relationship exists among only a proper subset of the attributes in a relation. This is bad relational database design because all the unrelated attributes must be filled with null values otherwise a tuple without the unrelated information cannot be inserted into the relation. • Loss of information is a condition of a relational database which results from the decomposition of one relation into two relations and which cannot be combined to recreate the original relation. It is a bad relational database design because certain queries cannot be answered using the reconstructed relation that could have been answered using the original relation. 7.2 Suppose that we decompose the schema R = (A, B, C, D, E) into (A, B, C) (A, D, E). Show that this decomposition is a lossless-join decomposition if the following set F of functional dependencies holds: A → BC CD → E B→D E→A Answer: A decomposition {R1 , R2 } is a lossless-join decomposition if R1 ∩ R2 → R1 or R1 ∩ R2 → R2 . Let R1 = (A, B, C), R2 = (A, D, E), and R1 ∩ R2 = A. Since A is a candidate key (see Exercise 7.11), Therefore R1 ∩ R2 → R1 . 7.3 Why are certain functional dependencies called trivial functional dependencies? Answer: Certain functional dependencies are called trivial functional dependencies because they are satisfied by all relations. 7.4 List all functional dependencies satisfied by the relation of Figure 7.21. Answer: The nontrivial functional dependencies are: A → B and C → B,

Exercises

85

and a dependency they logically imply: AC → B. There are 19 trivial functional dependencies of the form α → β, where β ⊆ α. C does not functionally determine A because the first and third tuples have the same C but different A values. The same tuples also show B does not functionally determine A. Likewise, A does not functionally determine C because the first two tuples have the same A value and different C values. The same tuples also show B does not functionally determine C. 7.5 Use the definition of functional dependency to argue that each of Armstrong’s axioms (reflexivity, augmentation, and transitivity) is sound. Answer: The definition of functional dependency is: α → β holds on R if in any legal relation r(R), for all pairs of tuples t1 and t2 in r such that t1 [α] = t2 [α], it is also the case that t1 [β] = t2 [β]. Reflexivity rule: if α is a set of attributes, and β ⊆ α, then α → β. Assume ∃ t1 and t2 such that t1 [α] = t2 [α] t1 [β] = t2 [β] since β ⊆ α α → β definition of FD Augmentation rule: if α → β, and γ is a set of attributes, then γ α → γ β. Assume ∃ t1 , t2 such that t1 [γ α] = t2 [γ α] γ ⊆ γα t1 [γ] = t2 [γ] t1 [α] = t2 [α] α ⊆ γα t1 [β] = t2 [β] definition of α → β t1 [γ β] = t2 [γ β] γ β = γ ∪ β γα → γβ definition of FD Transitivity rule: if α → β and β → γ, then α → γ. Assume ∃ t1 , t2 such that t1 [α] = t2 [α] t1 [β] = t2 [β] t1 [γ] = t2 [γ] α → γ definition of α → β definition of β → γ definition of FD

7.6 Explain how functional dependencies can be used to indicate the following: • A one-to-one relationship set exists between entity sets account and customer. • A many-to-one relationship set exists between entity sets account and customer.

A a1 a1 a2 a2

B b1 b1 b1 b1

C c1 c2 c1 c3

Figure 7.21. Relation of Exercise 7.4.

86

Chapter 7

Relational-Database Design

Answer: Let P k(r) denote the primary key attribute of relation r. • The functional dependencies P k(account) → P k (customer) and P k(customer) → P k(account) indicate a one-to-one relationship because any two tuples with the same value for account must have the same value for customer, and any two tuples agreeing on customer must have the same value for account. • The functional dependency P k(account) → P k(customer) indicates a manyto-one relationship since any account value which is repeated will have the same customer value, but many account values may have the same customer value. 7.7 Consider the following proposed rule for functional dependencies: If α → β and γ → β, then α → γ. Prove that this rule is not sound by showing a relation r that satisfies α → β and γ → β, but does not satisfy α → γ. Answer: Consider the following rule: if A → B and C → B, then A → C. That is, α = A, β = B, γ = C. The following relation r is a counterexample to the rule. r: A B C a 1 b 1 c1 a 1 b 1 c2 Note: A → B and C → B, (since no 2 tuples have the same C value, C → B is true trivially). However, it is not the case that A → C since the same A value is in two tuples, but the C value in those tuples disagree. 7.8 Use Armstrong’s axioms to prove the soundness of the union rule. (Hint: Use the augmentation rule to show that, if α → β, then α → αβ. Apply the augmentation rule again, using α → γ, and then apply the transitivity rule.) Answer: To prove that:

if α → β and α → γ then α → βγ

Following the hint, we derive: α → β given αα → αβ augmentation rule α → αβ union of identical sets α → γ given αβ → γ β augmentation rule α → βγ transitivity rule and set union commutativity 7.9 Use Armstrong’s axioms to prove the soundness of the decomposition rule. Answer: The decomposition rule, and its derivation from Armstrong’s axioms are given below:

Exercises

87

if α → βγ, then α → β and α → γ. α → βγ βγ → β α → β βγ → γ α → γ given reflexivity rule transitivity rule reflexive rule transitive rule

7.10 Use Armstrong’s axioms to prove the soundness of the pseudotransitivity rule. Answer: Proof using Armstrong’s axioms of the Pseudotransitivity Rule: if α → β and γ β → δ, then αγ → δ. α → β αγ → γ β γβ → δ αγ → δ given augmentation rule and set union commutativity given transitivity rule

7.11 Compute the closure of the following set F of functional dependencies for relation schema R = (A, B, C, D, E). A → BC CD → E B→D E→A List the candidate keys for R. Answer: Compute the closure of the following set F of functional dependencies for relation schema R = (A, B, C, D, E). A → BC CD → E B→D E→A List the candidate keys for R. Note: It is not reasonable to expect students to enumerate all of F + . Some shorthand representation of the result should be acceptable as long as the nontrivial members of F + are found. Starting with A → BC, we can conclude: A → B and A → C. Since A → B and B → D, A → D Since A → CD and CD → E, A → E Since A → A, we have A → ABCDE from the above steps Since E → A, E → ABCDE Since CD → E, CD → ABCDE Since B → D and BC → CD, BC → ABCDE Also, C → C, D → D, BD → D, etc. (decomposition, transitive) (union, decomposition, transitive) (reflexive) (union) (transitive) (transitive) (augmentative, transitive)

88

Chapter 7

Relational-Database Design

Therefore, any functional dependency with A, E, BC, or CD on the left hand side of the arrow is in F + , no matter which other attributes appear in the FD. Allow * to represent any set of attributes in R, then F + is BD → B, BD → D, C → C, D → D, BD → BD, B → D, B → B, B → BD, and all FDs of the form A ∗ → α, BC ∗ → α, CD ∗ → α, E ∗ → α where α is any subset of {A, B, C, D, E}. The candidate keys are A, BC, CD, and E. 7.12 Using the functional dependencies of Exercise 7.11, compute B + . Answer: Computing B + by the algorithm in Figure 7.7 we start with result = {B}. Considering FDs of the form β → γ in F , we find that the only dependencies satisfying β ⊆ result are B → B and B → D. Therefore result = {B, D}. No more dependencies in F apply now. Therefore B + = {B, D} 7.13 Using the functional dependencies of Exercise 7.11, compute the canonical cover Fc . Answer: The given set of FDs F is:A → BC CD → E B→D E→A

The left side of each FD in F is unique. Also none of the attributes in the left side or right side of any of the FDs is extraneous. Therefore the canonical cover Fc is equal to F . 7.14 Consider the algorithm in Figure 7.22 to compute α+ . Show that this algorithm is more efficient than the one presented in Figure 7.7 (Section 7.3.3) and that it computes α+ correctly. Answer: The algorithm is correct because: • If A is added to result then there is a proof that α → A. To see this, observe that α → α trivially so α is correctly part of result. If A ∈ α is added to result there must be some FD β → γ such that A ∈ γ and β is already a subset of result. (Otherwise f dcount would be nonzero and the if condition would be false.) A full proof can be given by induction on the depth of recursion for an execution of addin, but such a proof can be expected only from students with a good mathematical background. • If A ∈ α+ , then A is eventually added to result. We prove this by induction on the length of the proof of α → A using Armstrong’s axioms. First observe that if procedure addin is called with some argument β, all the attributes in β will be added to result. Also if a particular FD’s fdcount becomes 0, all the attributes in its tail will definitely be added to result. The base case of the proof, A ∈ α ⇒ A ∈ α+ , is obviously true because the first call to addin has the argument α. The inductive hypotheses is that if α → A can be proved in n steps or less then A ∈ result. If there is a proof in n + 1

Exercises

89

result := ∅; /* fdcount is an array whose ith element contains the number of attributes on the left side of the ith FD that are not yet known to be in α+ */ for i := 1 to |F | do begin let β → γ denote the ith FD; fdcount [i] := |β|; end /* appears is an array with one entry for each attribute. The entry for attribute A is a list of integers. Each integer i on the list indicates that A appears on the left side of the ith FD */ for each attribute A do begin appears [A] := N IL; for i := 1 to |F | do begin let β → γ denote the ith FD; if A ∈ β then add i to appears [A]; end end addin (α); return (result); procedure addin (α); for each attribute A in α do begin if A ∈ result then begin result := result ∪ {A}; for each element i of appears[A] do begin fdcount [i] := fdcount [i] − 1; if fdcount [i] := 0 then begin let β → γ denote the ith FD; addin (γ); end end end end Figure 7.22. An algorithm to compute α+ .

90

Chapter 7

Relational-Database Design

steps that α → A, then the last step was an application of either reflexivity, augmentation or transitivity on a fact α → β proved in n or fewer steps. If reflexivity or augmentation was used in the (n + 1)st step, A must have been in result by the end of the nth step itself. Otherwise, by the inductive hypothesis β ⊆ result. Therefore the dependency used in proving β → γ, A ∈ γ will have f dcount set to 0 by the end of the nth step. Hence A will be added to result. To see that this algorithm is more efficient than the one presented in the chapter note that we scan each FD once in the main program. The resulting array appears has size proportional to the size of the given FDs. The recursive calls to addin result in processing linear in the size of appears. Hence the algorithm has time complexity which is linear in the size of the given FDs. On the other hand, the algorithm given in the text has quadratic time complexity, as it may perform the loop as many times as the number of FDs, in each loop scanning all of them once. 7.15 Given the database schema R(a, b, c), and a relation r on the schema R, write an SQL query to test whether the functional dependency b → c holds on relation r. Also write an SQL assertion that enforces the functional dependency. Assume that no null values are present. Answer: a. The query is given below. Its result is non-empty if and only if b → c does not hold on r. select b from r group by b having count(distinct c) > 1 b. create assertion b-to-c check (not exists (select b from r group by b having count(distinct c) > 1 ) ) 7.16 Show that the following decomposition of the schema R of Exercise 7.2 is not a lossless-join decomposition: (A, B, C) (C, D, E).

Exercises

91

Hint: Give an example of a relation r on schema R such that ΠA, B, C (r)

½

ΠC, D, E (r) = r

Answer: Following the hint, use the following example of r: A B a1 b 1 a2 b 2 With R1 A a1 a2 C D E c1 d1 e1 c1 d2 e2 = (A, B, C), R2 = (C, D, E) : B b1 b2 C c1 c1

a. ΠR1 (r) would be:

b. ΠR2 (r) would be: C c1 c1 c. ΠR1 (r) A a1 a1 a2 a2 D d1 d2 E e1 e2 ΠR2 (r) would be: C c1 c1 c1 c1 D d1 d2 d1 d2 E e1 e2 e1 e2

½
B b1 b1 b2 b2

Clearly, ΠR1 (r)

½

ΠR2 (r) = r. Therefore, this is a lossy join.

7.17 Let R1 , R2 , . . . , Rn be a decomposition of schema U. Let u(U ) be a relation, and let ri = ΠRI (u). Show that u ⊆ r1

½

r2

½

···

½

rn

Answer: Consider some tuple t in u. Note that ri = ΠRi (u) implies that t[Ri ] ∈ ri , 1 ≤ i ≤ n. Thus, t[R1 ]

½ ½

t[R2 ]

½

...

½

t[Rn ] ∈ r1

½

r2

½

...

½

rn

By the definition of natural join, t[R1 ]

½

t[R2 ]

...

½

t[Rn ] = Πα (σβ (t[R1 ] × t[R2 ] × . . . × t[Rn ]))

where the condition β is satisfied if values of attributes with the same name in a tuple are equal and where α = U . The cartesian product of single tuples generates one tuple. The selection process is satisfied because all attributes with

92

Chapter 7

Relational-Database Design

the same name must have the same value since they are projections from the same tuple. Finally, the projection clause removes duplicate attribute names. By the definition of decomposition, U = R1 ∪ R2 ∪ . . . ∪ Rn , which means that all attributes of t are in t[R1 ] ½ t[R2 ] ½ . . . ½ t[Rn ]. That is, t is equal to the result of this join. Since t is any arbitrary tuple in u, u ⊆ r1

½

r2

½

...

½

rn

7.18 Show that the decomposition in Exercise 7.2 is not a dependency-preserving decomposition. Answer: The dependency B → D is not preserved. F1 , the restriction of F to (A, B, C) is A → ABC, A → AB, A → AC, A → BC, A → B, A → C, A → A, B → B, C → C, AB → AC, AB → ABC, AB → BC, AB → AB, AB → A, AB → B, AB → C, AC (same as AB), BC (same as AB), ABC (same as AB). F2 , the restriction of F to (C, D, E) is A → ADE, A → AD, A → AE, A → DE, A → A, A → D, A → E, D → D, E (same as A), AD, AE, DE, ADE (same as A). (F1 ∪ F2 )+ is easily seen not to contain B → D since the only FD in F1 ∪ F2 with B as the left side is B → B, a trivial FD. We shall see in Exercise 7.22 that B → D is indeed in F + . Thus B → D is not preserved. Note that CD → ABCDE is also not preserved. A simpler argument is as follows: F1 contains no dependencies with D on the right side of the arrow. F2 contains no dependencies with B on the left side of the arrow. Therefore for B → D to be preserved there must be an FD B → α + + in F1 and α → D in F2 (so B → D would follow by transitivity). Since the + intersection of the two schemes is A, α = A. Observe that B → A is not in F1 + since B = BD. 7.19 Show that it is possible to ensure that a dependency-preserving decomposition into 3NF is a lossless-join decomposition by guaranteeing that at least one schema contains a candidate key for the schema being decomposed. (Hint: Show that the join of all the projections onto the schemas of the decomposition cannot have more tuples than the original relation.) Answer: Let F be a set of functional dependencies that hold on a schema R. Let σ = {R1 , R2 , . . . , Rn } be a dependency-preserving 3NF decomposition of R. Let X be a candidate key for R. Consider a legal instance r of R. Let j = ΠX (r) ½ ΠR1 (r) ½ ΠR2 (r) . . . ½ ΠRn (r). We want to prove that r = j. We claim that if t1 and t2 are two tuples in j such that t1 [X] = t2 [X], then t1 = t2 . To prove this claim, we use the following inductive argument – Let F = F1 ∪ F2 ∪ . . . ∪ Fn , where each Fi is the restriction of F to the schema Ri in σ. Consider the use of the algorithm given in Figure 7.7 to compute the closure of X under F . We use induction on the number of times that the f or loop in this algorithm is executed. • Basis : In the first step of the algorithm, result is assigned to X, and hence given that t1 [X] = t2 [X], we know that t1 [result] = t2 [result] is true.

Exercises

93

• Induction Step : Let t1 [result] = t2 [result] be true at the end of the k th execution of the f or loop. Suppose the functional dependency considered in the k + 1 th execution of the f or loop is β → γ, and that β ⊆ result. β ⊆ result implies that t1 [β] = t2 [β] is true. The facts that β → γ holds for some attribute set Ri in σ, and that t1 [Ri ] and t2 [Ri ] are in ΠRi (r) imply that t1 [γ] = t2 [γ] is also true. Since γ is now added to result by the algorithm, we know that t1 [result] = t2 [result] is true at the end of the k + 1 th execution of the f or loop. Since σ is dependency-preserving and X is a key for R, all attributes in R are in result when the algorithm terminates. Thus, t1 [R] = t2 [R] is true, that is, t1 = t2 – as claimed earlier. Our claim implies that the size of ΠX (j) is equal to the size of j. Note also that ΠX (j) = ΠX (r) = r (since X is a key for R). Thus we have proved that the size of j equals that of r. Using the result of Exercise 7.17, we know that r ⊆ j. Hence we conclude that r = j. Note that since X is trivially in 3NF, σ ∪ {X} is a dependency-preserving lossless-join decomposition into 3NF. 7.20 List the three design goals for relational databases, and explain why each is desirable. Answer: The three design goals are lossless-join decompositions, dependency preserving decompositions, and minimization of repetition of information. They are desirable so we can maintain an accurate database, check correctness of updates quickly, and use the smallest amount of space possible. 7.21 Give a lossless-join decomposition into BCNF of schema R of Exercise 7.2. Answer: From Exercise 7.11, we know that B → D is nontrivial and the left hand side is not a superkey. By the algorithm of Figure 7.13 we derive the relations {(A, B, C, E), (B, D)}. This is in BCNF. 7.22 Give an example of a relation schema R and set F of functional dependencies such that there are at least three distinct lossless-join decompositions of R into BCNF. Answer: Given the relation R = (A, B, C, D) the set of functional dependencies F = A → B, C → D, B → C allows three distinct BCNF decompositions. R1 = {(A, B), (C, D), (B, C)} is in BCNF as is R2 = {(A, B), (C, D), (A, C)} R2 = {(A, B), (C, D), (A, C)} R3 = {(B, C), (A, D), (A, B)}

94

Chapter 7

Relational-Database Design

7.23 In designing a relational database, why might we choose a non-BCNF design? Answer: BCNF is not always dependency preserving. Therefore, we may want to choose another normal form (specifically, 3NF) in order to make checking dependencies easier during updates. This would avoid joins to check dependencies and increase system performance. 7.24 Give a lossless-join, dependency-preserving decomposition into 3NF of schema R of Exercise 7.2. Answer: First we note that the dependencies given in Exercise 7.2 form a canonical cover. Generating the schema from the algorithm of Figure 7.14 we get R = {(A, B, C), (C, D, E), (B, D), (E, A)}. Schema (A, B, C) contains a candidate key. Therefore R is a third normal form dependency-preserving lossless-join decomposition. Note that the original schema R = (A, B, C, D, E) is already in 3NF. Thus, it was not necessary to apply the algorithm as we have done above. The single original schema is trivially a lossless join, dependency-preserving decomposition. 7.25 Let a prime attribute be one that appears in at least one candidate key. Let α and β be sets of attributes such that α → β holds, but β → α does not hold. Let A be an attribute that is not in α, is not in β, and for which β → A holds. We say that A is transitively dependent on α. We can restate our definition of 3NF as follows: A relation schema R is in 3NF with respect to a set F of functional dependencies if there are no nonprime attributes A in R for which A is transitively dependent on a key for R. Show that this new definition is equivalent to the original one. Answer: Suppose R is in 3NF according to the textbook definition. We show that it is in 3NF according to the definition in the exercise. Let A be a nonprime attribute in R that is transitively dependent on a key α for R. Then there exists β ⊆ R such that β → A, α → β, A ∈ α, A ∈ β, and β → α does not hold. But then β → A violates the textbook definition of 3NF since • A ∈ β implies β → A is nontrivial • Since β → α does not hold, β is not a superkey • A is not any candidate key, since A is nonprime Now we show that if R is in 3NF according to the exercise definition, it is in 3NF according to the textbook definition. Suppose R is not in 3NF according the the textbook definition. Then there is an FD α → β that fails all three conditions. Thus • α → β is nontrivial. • α is not a superkey for R. • Some A in β − α is not in any candidate key. This implies that A is nonprime and α → A. Let γ be a candidate key for R. Then γ → α, α → γ does not hold (since α is not a superkey), A ∈ α, and

Exercises

95

A ∈ γ (since A is nonprime). Thus A is transitively dependent on γ, violating the exercise definition. 7.26 A functional dependency α → β is called a partial dependency if there is a proper subset γ of α such that γ → β. We say that β is partially dependent on α. A relation schema R is in second normal form (2NF) if each attribute A in R meets one of the following criteria: • It appears in a candidate key. • It is not partially dependent on a candidate key. Show that every 3NF schema is in 2NF. (Hint: Show that every partial dependency is a transitive dependency.) Answer: Referring to the definitions in Exercise 7.25, a relation schema R is said to be in 3NF if there is no non-prime attribute A in R for which A is transitively dependent on a key for R. We can also rewrite the definition of 2NF given here as : “A relation schema R is in 2NF if no non-prime attribute A is partially dependent on any candidate key for R.” To prove that every 3NF schema is in 2NF, it suffices to show that if a nonprime attribute A is partially dependent on a candidate key α, then A is also transitively dependent on the key α. Let A be a non-prime attribute in R. Let α be a candidate key for R. Suppose A is partially dependent on α. • From the definition of a partial dependency, we know that for some proper subset β of α, β → A. • Since β ⊂ α, α → β. Also, β → α does not hold, since α is a candidate key. • Finally, since A is non-prime, it cannot be in either β or α. Thus we conclude that α → A is a transitive dependency. Hence we have proved that every 3NF schema is also in 2NF. 7.27 Given the three goals of relational-database design, is there any reason to design a database schema that is in 2NF, but is in no higher-order normal form? (See Exercise 7.26 for the definition of 2NF.) Answer: The three design goals of relational databases are to avoid • Repetition of information • Inability to represent information • Loss of information.
2NF does not prohibit as much repetition of information since the schema (A, B, C) with dependencies A → B and B → C is allowed under 2NF, although the same (B, C) pair could be associated with many A values, needlessly duplicating C values. To avoid this we must go to 3NF. Repetition of information is allowed in 3NF in some but not all of the cases where it is allowed in 2NF. Thus, in general, 3NF reduces repetition of information. Since we can always achieve a lossless join 3NF decomposition, there is no loss of information needed in going from 2NF to 3NF.

96

Chapter 7

Relational-Database Design

Note that the decomposition {(A, B), (B, C)} is a dependency-preserving and lossless-loin 3NF decomposition of the schema (A, B, C). However, in case we choose this decomposition, retrieving information about the relationship between A, B and C requires a join of two relations, which is avoided in the corresponding 2NF decomposition. Thus, the decision of which normal form to choose depends upon how the cost of dependency checking compares with the cost of the joins. Usually, the 3NF would be preferred. Dependency checks need to be made with every insert or update to the instances of a 2NF schema, whereas, only some queries will require the join of instances of a 3NF schema. 7.28 Give an example of a relation schema R and a set of dependencies such that R is in BCNF, but is not in 4NF. Answer: The relation schema R = (A, B, C, D, E) and the set of dependencies A → BC → B → CD → E → AD → constitute a BCNF decomposition, however it is clearly not in 4NF. (It is BCNF because all FDs are trivial). 7.29 Explain why 4NF is a normal form more desirable than BCNF. Answer: 4NF is more desirable than BCNF because it reduces the repetition of information. If we consider a BCNF schema not in 4NF (see Exercise 7.28), we observe that decomposition into 4NF does not lose information provided that a lossless join decomposition is used, yet redundancy is reduced. 7.30 Explain how dangling tuples may arise. Explain problems that they may cause. Answer: Dangling tuples can arise when one tuple is inserted into a decomposed relation but no corresponding tuple is inserted into the other relations in the decomposition. They can cause incorrect values to be returned by queries which form the join of a decomposed relation since the dangling tuple might not be included. As we saw in Chapter 5, dangling tuples can be avoided by the specification of referential integrity constraints.

C H A P T E R

8

Object-Oriented Databases

This chapter provides an introduction to object-oriented databases. This chapter and the next chapter form a logical unit and should be taught consecutively. It is possible to teach these chapters before covering normalization (Chapter 7). The sections of the chapter prior to the section on persistent C++ and ODMG (Section 8.5) do not assume any familiarity with an object-oriented programming language. However, it is quite possible that students may already be familiar with the basic concepts of object orientation, and with an object-oriented programming languages. For such students Section 8.2 can be covered relatively quickly. However, it is important to point out the motivation for object-oriented features in the context of a database, and how the requirements differ from those of a programming language. There is a tendency to confuse “persistent” object-oriented languages with objectoriented databases. A persistent object-oriented language should be merely a frontend to a database. It is important to remind students of all of the features that a database system must have, so that, they can distinguish full-fledged object-oriented database systems from systems that provide an object-oriented front-end, but provide little in the way of database facilities such as a query facility, an on-line catalog, concurrency control and recovery. There are several commercial object-oriented database systems available on the market, and a few public domain systems as well. Some of the commercial systems also offer low-cost or free copies for academic use. The commercial object-oriented database systems include Objectivity (www.objectivity.com), ObjectStore (www.odi.com), and Versant (www.versant.com). Changes from 3rd edition: Some examples have been updated to make them more intuitive. The coverage of ODMG has been updated to ODMG-2, including the new syntax (with a d prefix for keywords), and the new d rel ref feature to declare relationships.
97

98

Chapter 8

Object-Oriented Databases

Exercises
8.1 For each of the following application areas, explain why a relational database system would be inadequate. List all specific system components that would need to be modified. a. Computer-aided design b. Multimedia databases Answer: Each of the applications includes large, specialized data items (e.g., a program module, a graphic image, digitized voice, a document). These data items have operations specific to them (e.g., compile, rotate, play, format) that cannot be expressed in relational query languages. These data items are of variable length making it impractical to store them in the short fields that are allowed in records for such database systems. Thus, the data model, data manipulation language, and data definition language need to be changed. Also, long-duration and nested transactions are typical of these applications. Changes to the concurrency and recovery subsystems are likely to be needed. 8.2 How does the concept of an object in the object-oriented model differ from the concept of an entity in the entity-relationship model? Answer: An entity is simply a collection of variables or data items. An object is an encapsulation of data as well as the methods (code) to operate on the data. The data members of an object are directly visible only to its methods. The outside world can gain access to the object’s data only by passing pre-defined messages to it, and these messages are implemented by the methods. 8.3 A car-rental company maintains a vehicle database for all vehicles in its current fleet. For all vehicles, it includes the vehicle identification number, license number, manufacturer, model, date of purchase, and color. Special data are included for certain types of vehicles: • Trucks: cargo capacity • Sports cars: horsepower, renter age requirement • Vans: number of passengers • Off-road vehicles: ground clearance, drivetrain (four- or two-wheel drive) Construct an object-oriented database schema definition for this database. Use inheritance where appropriate. Answer: class vehicle { int string string string date

vehicle-id; license-number; manufacturer; model; purchase-date;

Exercises

99

};

color-type

color;

class truck isa vehicle { int cargo-capacity; }; class sports-car isa vehicle { int horsepower; int renter-age-requirement; }; class van isa vehicle { int num-passengers; }; class off-road-vehicle isa vehicle { real ground-clearance; drivetrain-type drivetrain; }; We assume that color-type and drivetrain-type are previously defined types. 8.4 Explain why ambiguity potentially exists with multiple inheritance. Illustrate your explanation with an example. Answer: A class inherits the variables and methods of all its immediate superclasses. Thus it could inherit a variable or method of the same name from more than one super-class. When that particular variable or method of an object of the sub-class is referenced, there is an ambiguity regarding which of the superclasses provides the inheritance. For instance, let there be classes teacher and student, both having a variable department. If a class teachingAssistant inherits from both of these classes, any reference to the department variable of a teachingAssistant object is ambiguous. 8.5 Explain how the concept of object identity in the object-oriented model differs from the concept of tuple equality in the relational model. Answer: Tuple equality is determined by data values. Object identity is independent of data values, since object-oriented systems use built-in identity. 8.6 Explain the distinction in meaning between edges in a DAG representing inheritance and a DAG representing object containment. Answer: An edge from class A to class B in the DAG representing inheritance means that an object of class B is also an object of class A. It has all the properties that objects of class A have, plus additional ones of its own. In particular, it

100

Chapter 8

Object-Oriented Databases

inherits all the variables and methods of class A. It can of course provide its own implementations for the inherited methods. And edge from class A to class B in the object containment DAG means that an object of class A contains an object of class B. There need not be any similarities in the properties of A and B. Neither B nor A inherit anything from the other. They function as independent types, to the extent that an object of class A can access the variables of the B object contained in it only via the B object’s methods. 8.7 Why do persistent programming languages allow transient objects? Might it be simpler to use only persistent objects, with unneeded objects deleted at the end of an execution? Explain your answer. Answer: Creation, destruction and access will typically be more time consuming and expensive for persistent objects stored in the database, than for transient objects in the transaction’s local memory. This is because of the over-heads in preserving transaction semantics, security and integrity. Since a transient object is purely local to the transaction which created it and does not enter the database, all these over-heads are avoided. Thus, in order to provide efficient access to purely local and temporary data, transient objects are provided by persistent programming languages. 8.8 Using ODMG C++ a. Give schema definitions corresponding to the relational schema shown in Figure 3.39, using references to express foreign-key relationships. b. Write programs to compute each of the queries in Exercise 3.10. Answer: a. The schema definitions can be written in two different ways, one of which is a direct translation from the relational schema, while the other uses objectoriented features more directly. • The first scheme is as follows: class employee : public d Object { public: d String person-name; d String street; d String city; }; class company : public d Object { public: d String company-name; d String city; }; class works : public d Object {

Exercises

101

public: d Ref person; d Ref comp; d Long salary; }; class manages : public d Object { public: d Ref person; d Ref manager; }; • The second schema is as follows

class employee : public d Object { public: d String person-name; d String street; d String city; d Rel Ref comp; d Ref manager; d Long salary; }; class company : public d Object { public: d String company-name; d String city; d Rel Set employees; }; const char employees[] = ”employees”; const char comp[] = ”comp”;

b. We present queries for the second schema. • Find the company with the most employees.

102

Chapter 8

Object-Oriented Databases

d Ref mostemployees(){ d Database emp db obj; d Database * emp db = ”” emp db obj; emp db− >open(”Emp-DB”); d Transaction Trans; Trans.begin(); d Extent all comps(emp db); d Iterator iter=all comps.create iterator(); d Iterator iter2; d Ref c, maxc; d Ref e; int count; int maxcount=0; while(iter.next(c)) { iter2=(c− >employees).create iterator(); count=0; while(iter2.next(e)) { count++; } if(maxcount < count) { maxcount=count; maxc=c; } } Trans.commit(); return maxc; }

• Find the company with the smallest payroll.

Exercises

103

d Ref smallestpay(){ d Database emp db obj; d Database * emp db = ”” emp db obj; emp db− >open(”Emp-DB”); d Transaction Trans; Trans.begin(); d Extent all comps(emp db); d Iterator iter=all comps.create iterator(); d Iterator iter2; d Ref c, minc; d Ref e; d Long sal; d Long minsal=0; while(iter.next(c)) { iter2=(c− >employees).create iterator(); sal=0; while(iter2.next(e)) { sal+=e− >salary; } if(minsal > sal) { minsal=sal; minc=c; } } Trans.commit(); return minc; }

• Find those companies whose employees earn a higher salary, on average, than the average salary at First Bank Corporation.

104

Chapter 8

Object-Oriented Databases

d Set highersal(){ d Database emp db obj; d Database * emp db = ”” emp db obj; emp db− >open(”Emp-DB”); d Transaction Trans; Trans.begin(); d Extent all comps(emp db); d Iterator iter=all comps.create iterator(); d Iterator iter2; d Ref c, FBC=all comps.select(company-name=”First Bank Corporation”); d Set result; d Ref e; int count; d Long avsal=0, avFBCsal=0, sal=0; iter2=(FBC− >employees).create iterator(); while(iter2.next(e)) { count++; sal+=e− >salary; } avFBCsal=sal/count; while(iter.next(c)) { iter2=(c− >employees).create iterator(); sal=0; count=0; while(iter2.next(e)) { sal+=e− >salary; count++; } avsal=sal/count; if(avsal > avFBCsal) { result.insert element(c); } } Trans.commit(); return result; } 8.9 Using ODMG C++, give schema definitions corresponding to the E-R diagram in Figure 2.29, using references to implement relationships. Answer: class person : public d Object { public: d String name; d String address; d String phone; };

Exercises

105

class author : public person { public: d String URL; d Rel Set books; }; class publisher : public person { public: d String URL; d Rel Set books; }; class customer : public person { public: d String email; d Rel Set baskets; }; class book : public d Object { public: int year; d String title; float price; d String ISBN; d Rel Set authors; d Rel Ref book publisher; }; class shoppingbasket : public d Object { public: d String basketID; d Rel Ref owner; d Set contains; }; class warehouse : public d Object { public: d String address; d String phone; d String code; d Set stocks; }; class book qty : public d Object { public:

106

Chapter 8

Object-Oriented Databases

};

d Ref book; int number;

const char const char const char const char const char

books[] = ”books”; authors[] = ”authors”; book publisher[] = ”book publisher”; baskets[] = ”baskets”; owner[] = ”owner”;

8.10 Explain, using an example, how to represent a ternary relationship in an objectoriented data model such as ODMG C++. Answer: To represent ternary relationships, create a class corresponding to the relationship and refer to the entities in this class. For example, to represent the ternary relationship in Figure 2.13, we do the following: class workson : public d Object { public: d Ref emp; d Ref branch; d Ref job; };

8.11 Explain how a persistent pointer is implemented. Contrast this implementation with that of pointers as they exist in general-purpose languages, such as C or Pascal. Answer: Persistent pointers can be implemented as Abstract Data Types (ADTs). These ADTs should provide the typical pointer operations like incrementing and dereferencing, so their usage and regular pointer usage is uniform. Regular pointers on the other hand are usually built-in types, implemented as part of the language. 8.12 If an object is created without any references to it, how can that object be deleted? Answer: If an object is created without any references to it, it can neither be accessed nor deleted via a program. The only way is for the database system to locate and delete such objects by itself. This is called garbage collection. One way to do garbage collection is by the method of mark and sweep. First, the objects referred to directly by programs are marked. Then references from these objects to other objects are followed, and those referred objects are marked. This procedure is followed repeatedly until no more unmarked objects can be reached by following reference chains from the marked objects. At this point, all these remaining unmarked objects are deleted. This method is correct; we can prove

Exercises

107

that if no new objects are marked after a round of mark and sweep, the remaining unmarked objects are indeed unreferenced. 8.13 Consider a system that provides persistent objects. Is such a system necessarily a database system? Explain your answer. Answer: A database system must provide for such features as transactions, queries (associative retrieval of objects), security, and integrity. A persistent object system may not offer such features.

C H A P T E R

9

Object-Relational Databases

This chapter describes extensions to relational database systems to provide complex data types and object-oriented features. Such extended systems are called objectrelational systems. Since the chapter was introduced in the 3rd edition most commercial database systems have added some support for object-relational features, and these features have been standardized as part of SQL:1999. It would be instructive to assign students exercises aimed at finding applications where the object-relational model, in particular complex objects, would be better suited than the traditional relational model. Changes from 3rd edition: The query language features are now based on the SQL:1999 standard, which was not ready when the 3rd edition was published; that edition was based from features from several different proposals for extending SQL.

Exercises
9.1 Consider the database schema Emp = (ename, setof(Children), setof(Skills)) Children = (name, Birthday) Birthday = (day, month, year) Skills = (type, setof(Exams)) Exams = (year, city) Assume that attributes of type setof(Children), setof(Skills), and setof(Exams), have attribute names ChildrenSet, SkillsSet, and ExamsSet, respectively. Suppose the database contains a relation emp (Emp). Write the following queries in SQL:1999 (with the extensions described in this chapter).
109

110

Chapter 9

Object-Relational Databases

a. Find the names of all employees who have a child who has a birthday in March. b. Find those employees who took an examination for the skill type “typing” in the city “Dayton”. c. List all skill types in the relation emp. Answer: a. Find the names of all employees who have a child who has a birthday in March. select ename from emp as e, e.ChildrenSet as c where ’March’ in (select birthday.month from c ) b. Find those employees who took an examination for the skill type “typing” in the city “Dayton”. select e.ename from emp as e, e.SkillSet as s, s.ExamSet as x where s.type = ’typing’ and x.city = ’Dayton’ c. List all skill types in the relation emp. select distinct s.type from emp as e, e.SkillSet as s 9.2 Redesign the database of Exercise 9.1 into first normal form and fourth normal form. List any functional or multivalued dependencies that you assume. Also list all referential-integrity constraints that should be present in the first- and fourth-normal-form schemas. Answer: To put the schema into first normal form, we flatten all the attributes into a single relation schema. Employee-details = (ename, cname, bday, bmonth, byear, stype, xyear, xcity) We rename the attributes for the sake of clarity. cname is Children.name, and bday, bmonth, byear are the Birthday attributes. stype is Skills.type, and xyear and xcity are the Exams attributes. The FDs and multivalued dependencies we assume are:ename, cname → ename → → ename, stype → → bday, bmonth, byear cname, bday, bmonth, byear xyear, xcity

The FD captures the fact that a child has a unique birthday, under the assumption that one employee cannot have two children of the same name. The MVDs capture the fact there is no relationship between the children of an employee and his or her skills-information.

Exercises

111

The redesigned schema in fourth normal form is:Employee = (ename) Child = (ename, cname, bday, bmonth, byear) Skill = (ename, stype, xyear, xcity) ename will be the primary key of Employee, and (ename, cname) will be the primary key of Child. The ename attribute is a foreign key in Child and in Skill, referring to the Employee relation. 9.3 Consider the schemas for the table people, and the tables students and teachers, which were created under people, in Section 9.3. Give a relational schema in third normal form that represents the same information. Recall the constraints on subtables, and give all constraints that must be imposed on the relational schema so that every database instance of the relational schema can also be represented by an instance of the schema with inheritance. Answer: A corresponding relational schema in third normal form is given below:People = (name, address) Students = (name, degree, student-department) Teachers = (name, salary, teacher-department) name is the primary key for all the three relations, and it is also a foreign key referring to People, for both Students and Teachers. Instead of placing only the name attribute of People in Students and Teachers, both its attributes can be included. In that case, there will be a slight change, namely – (name, address) will become the foreign key in Students and Teachers. The primary keys will remain the same in all tables. 9.4 A car-rental company maintains a vehicle database for all vehicles in its current fleet. For all vehicles, it includes the vehicle identification number, license number, manufacturer, model, date of purchase, and color. Special data are included for certain types of vehicles: • Trucks: cargo capacity • Sports cars: horsepower, renter age requirement • Vans: number of passengers • Off-road vehicles: ground clearance, drivetrain (four- or two-wheel drive) Construct an SQL:1999 schema definition for this database. Use inheritance where appropriate. Answer: For this problem, we use table inheritance. We assume that MyDate, Color and DriveTrainType are pre-defined types. create type Vehicle (vehicle-id integer, license-number char(15), manufacturer char(30),

112

Chapter 9

Object-Relational Databases

model char(30), purchase-date MyDate, color Color) create table vehicle of type Vehicle create table truck (cargo-capacity integer) under vehicle create table sportsCar (horsepower integer renter-age-requirement integer) under vehicle create table van (num-passengers integer) under vehicle create table offRoadVehicle (ground-clearance real driveTrain DriveTrainType) under vehicle

9.5 Explain the distinction between a type x and a reference type ref(x). Under what circumstances would you choose to use a reference type? Answer: If the type of an attribute is x, then in each tuple of the table, corresponding to that attribute, there is an actual object of type x . If its type is ref(x), then in each tuple, corresponding to that attribute, there is a reference to some object of type x. We choose a reference type for an attribute, if that attribute’s intended purpose is to refer to an independent object. 9.6 Consider the E-R diagram in Figure 2.11, which contains composite, multivalued and derived attributes. a. Give an SQL:1999 schema definition corresponding to the E-R diagram. Use an array to represent the multivalued attribute, and appropriate SQL:1999 constructs to represent the other attribute types. b. Give constructors for each of the structured types defined above. Answer: a. The corresponding SQL:1999 schema definition is given below. Note that the derived attribute age has been translated into a method. create type Name

Exercises

113

(first-name varchar(15), middle-initial char, last-name varchar(15)) create type Street (street-name varchar(15), street-number varchar(4), apartment-number varchar(7)) create type Address (street Street, city varchar(15), state varchar(15), zip-code char(6)) create table customer (name Name, customer-id varchar(10), address Adress, phones char(7) array[10], dob date) method integer age() b. create function Name (f varchar(15), m char, l varchar(15)) returns Name begin set first-name = f; set middle-initial = m; set last-name = l; end create function Street (sname varchar(15), sno varchar(4), ano varchar(7)) returns Street begin set street-name = sname; set street-number = sno; set apartment-number =ano; end create function Address (s Street, c varchar(15), sta varchar(15), zip varchar(6)) returns Address begin set street = s; set city = c; set state =sta; set zip-code =zip; end 9.7 Give an SQL:1999 schema definition of the E-R diagram in Figure 2.17, which contains specializations. Answer:

114

Chapter 9

Object-Relational Databases

create type Person (name varchar(30), street varchar(15), city varchar(15)) create type Employee under Person (salary integer) create type Customer under Person (credit-rating integer) create type Officer under Employee (office-number integer) create type Teller under Employee (station-number integer, hours-worked integer) create type Secretary under Employee (hours-worked integer) create table person of Person create table employee of Employee under person create table customer of Customer under person create table officer of Officer under employee create table teller of Teller under employee create table secretary of Secretary under employee

9.8 Consider the relational schema shown in Figure 3.39. a. Give a schema definition in SQL:1999 corresponding to the relational schema, but using references to express foreign-key relationships. b. Write each of the queries in Exercise 3.10 on the above schema, using SQL:1999. Answer: a. The schema definition is given below. Note that backward references can be addedbut they are not so important as in OODBS because queries can be written in SQL and joins can take care of integrity constraints. create type Employee (person-name varchar(30), street varchar(15),

Exercises

115

city varchar(15)) create type Company (company-name varchar(15), (city varchar(15)) create table employee of Employee create table company of Company create type Works (person ref(Employee) scope employee, comp ref(Company) scope company, salary int) create table works of Works create type Manages (person ref(Employee) scope employee, (manager ref(Employee) scope employee) create table manages of Manages b. i. select comp− >name from works group by comp having count(person) ≥ all(select count(person) from works group by comp) ii. select comp− >name from works group by comp having sum(salary) ≤ all(select sum(salary) from works group by comp) iii. select comp− >name from works group by comp having avg(salary) > (select avg(salary) from works where comp− >company-name=”First Bank Corporation”)

9.9 Consider an employee database with two relations employee (employee-name, street, city) works (employee-name, company-name, salary) where the primary keys are underlined. Write a query to find companies whose employees earn a higher salary, on average, than the average salary at First Bank Corporation. a. Using SQL:1999 functions as appropriate. b. Without using SQL:1999 functions. Answer: a. create function avg-salary(cname varchar(15)) returns integer

116

Chapter 9

Object-Relational Databases

declare result integer; select avg(salary) into result from works where works.company-name = cname return result; end select company-name from works where avg-salary(company-name) > avg-salary(”First Bank Corporation”) b. select company-name from works group by company-name having avg(salary) > (select avg(salary) from works where company-name=”First Bank Corporation”) 9.10 Rewrite the query in Section 9.6.1 that returns the titles of all books that have more than one author, using the with clause in place of the function. Answer: with multauthors(title, count) as select title, count(author) from authors group by title select books4.title from books4, multauthors where books4.title = multauthors.title and multauthors.count > 1

9.11 Compare the use of embedded SQL with the use in SQL of functions defined in a general-purpose programming language. Under what circumstances would you use each of these features? Answer: SQL functions are primarily a mechanism for extending the power of SQL to handle attributes of complex data types (like images), or to perform complex and non-standard operations. Embedded SQL is useful when imperative actions like displaying results and interacting with the user are needed. These cannot be done conveniently in an SQL only environment. Embedded SQL can be used instead of SQL functions by retrieving data and then performing the function’s operations on the SQL result. However a drawback is that a lot of query-evaluation functionality may end up getting repeated in the host language code. 9.12 Suppose that you have been hired as a consultant to choose a database system for your client’s application. For each of the following applications, state what type of database system (relational, persistent-programming-language– based

Exercises

117

OODB, object relational; do not specify a commercial product) you would recommend. Justify your recommendation. a. A computer-aided design system for a manufacturer of airplanes b. A system to track contributions made to candidates for public office c. An information system to support the making of movies

Answer: a. A computer-aided design system for a manufacturer of airplanes :An OODB system would be suitable for this. That is because CAD requires complex data types, and being computation oriented, CAD tools are typically used in a programming language environment needing to access the database. b. A system to track contributions made to candidates for public office :A relational system would be apt for this, as data types are expected to be simple, and a powerful querying mechanism is essential. c. An information system to support the making of movies :Here there will be extensive use of multimedia and other complex data types. But queries are probably simple, and thus an object relational system is suitable.

C H A P T E R

1 0

XML

In the 4 1/2 years since the previous edition was published, XML has gone from a little known proposal to the World Wide Web Consortium, to an extensive set of standards that are being used widely, and whose use is growing rapidly. In this period the goals of XML have changed from being a better form SGML or HTML, into becoming the primary data model for data interchange. Our view of XML is decidedly database centric: it is important to be aware that many uses of XML are document centric, but we believe the bulk of XML applications will be in data representation and interchange between database applications. In this view, XML is a data model that provides a number of features beyond that provided by the relational model, in particular the ability to package related information into a single unit, by using nested structures. Specific application domains for data representation and interchange need their own standards that define the data schema. Given the extensive nature of XML and related standards, this chapter only attempts to provide an introduction, and does not attempt to provide a complete description. For a course that intends to explore XML in detail, supplementary material may be required. These could include online information on XML and books on XML.

Exercises
10.1 Give an alternative representation of bank information containing the same data as in Figure 10.1, but using attributes instead of subelements. Also give the DTD for this representation. Answer: a. XML representation of data using attributes:
119

120

Chapter 10

XML

b. DTD for the bank: ]>

10.2 Show, by giving a DTD, how to represent the books nested-relation from Section 9.1, using XML. Answer:

Exercises

121

]> 10.3 Give the DTD for an XML representation of the following nested-relational schema Emp = (ename, ChildrenSet setof(Children), SkillsSet setof(Skills)) Children = (name, Birthday) Birthday = (day, month, year) Skills = (type, ExamsSet setof(Exams)) Exams = (year, city) Answer: ]> 10.4 Write the following queries in XQuery, assuming the DTD from Exercise 10.3. a. Find the names of all employees who have a child who has a birthday in March. b. Find those employees who took an examination for the skill type “typing” in the city “Dayton”. c. List all skill types in Emp. Answer: a. Find the names of all employees who have a child who has a birthday in March.

122

Chapter 10

XML

for $e in /db/emp, $m in distinct($e/children/birthday/month) where $m = ’March’ return $e/ename b. Find those employees who took an examination for the skill type “typing” in the city “Dayton”. for $e in /db/emp $s in $e/skills[type=’typing’] $exam in $s/exams where $exam/city= ’Dayton’ return $e/ename c. Find those employees who took an examination for the skill type “typing” in the city “Dayton”. for $t in distinct (/db/emp/skills/type) return $e/ename 10.5 Write queries in XSLT and in XPath on the DTD of Exercise 10.3 to list all skill types in Emp. Answer: a. XPath: /db/emp/skills/type b. XSLT: 10.6 Write a query in XQuery on the XML representation in Figure 10.1 to find the total balance, across all accounts, at each branch. (Hint: Use a nested query to get the effect of an SQL group by.) Answer: for $b in distinct (/bank/account/branch-name) return $b/text() let $s := sum (/bank/account[branch-name=$b]/balance return $s

Exercises

123

10.7 Write a query in XQuery on the XML representation in Figure 10.1 to compute the left outer join of customer elements with account elements. (Hint: Use universal quantification.) Answer: for $b in /bank/account, $c in /bank/customer, $d in /bank/depositor where $a/account-number = $d/account-number and $c/customer-name = $d/customer-name return $c $a | for $c in /bank/customer, where every $d in /bank/depositor satisfies (not ($c/customer-name=$d/customer-name)) return $c 10.8 Give a query in XQuery to flip the nesting of data from Exercise 10.2. That is, at the outermost level of nesting the output must have elements corresponding to authors, and each such element must have nested within it items corresponding to all the books written by the author. Answer: for $a in distinct (/bib/book/author) return $a/text() for $b in (/bib/book/[author=$a]) return $b/title $b/publisher $b/keyword < \book> < \author>

10.9 Give the DTD for an XML representation of the information in Figure 2.29. Create a separate element type to represent each relationship, but use ID and IDREF to implement primary and foreign keys. Answer: The answer is given in Figure 10.1. 10.10 Write queries in XSLT and XQuery to output customer elements with associated account elements nested within the customer elements, given the bank infor-

124

Chapter 10

XML

]> Figure 10.1 XML DTD for Bookstore

Exercises

125

mation representation using ID and IDREFS in Figure 10.8. Answer: for $c in /bank/customer return $c/* for $a in $c/id(@accounts) return $a 10.11 Give a relational schema to represent bibliographical information specified as per the DTD fragment in Figure 10.13. The relational schema must keep track of the order of author elements. You can assume that only books and articles appear as top level elements in XML documents. Answer: book (bid, title, year, publisher, place) article (artid, title, journal, year, number, volume, pages) book-author (bid, first-name,last-name, order) article-author (artid, first-name,last-name, order) 10.12 Consider Exercise 10.11, and suppose that authors could also appear as top level elements. What change would have to be done to the relational schema. Answer: book (bid, title, year, publisher, place) article (artid, title, journal, year, number, volume, pages) author (first-name, last-name) book-author (bid, first-name, last-name, order) article-author (artid, first-name,last-name, order) 10.13 Write queries in XQuery on the bibliography DTD fragment in Figure 10.13, to do the following. a. Find all authors who have authored a book and an article in the same year. b. Display books and articles sorted by year. c. Display books with more than one author. Answer: a. Find all authors who have authored a book and an article in the same year. for $a in distinct (/bib/book/author) $y in /bib/book[author=$a]/year $art in /bib/article[author=$a and year=$y] return $a

126

Chapter 10

XML

· · · similar PCDATA declarations for year, publisher, place, journal, year, number, volume, pages, last-name and first-name ]> Figure 10.13. DTD for bibliographical data. b. Display books and articles sorted by year. for $a in ((/bib/book) | (/bib/article)) return $a sortby(year) c. Display books with more than one author. for $a in ((/bib/book[author/count()>1]) return $a 10.14 Show the tree representation of the XML data in Figure 10.1, and the representation of the tree using nodes and child relations described in Section 10.6.1. Answer: The answer is given in Figure 10.2. 10.15 Consider the following recursive DTD. ]> a. Give a small example of data corresponding to the above DTD. b. Show how to map this DTD to a relational schema. You can assume that part names are unique, that is, whereever a part appears, its subpart structure will be the same. Answer: a. Give a small example of data corresponding to the above DTD. The answer is shown in Figure 10.3. b. Show how to map this DTD to a relational schema. part(partid,name) subpartinfo(partid, subpartid, qty) Attributes partid and subpartid of subpartinfo are foreign keys to part.

Exercises

127

nodes(1,element,bank,–) nodes(2,element,account,–) nodes(3,element,account,–) nodes(4,element,account,–) nodes(5,element,customer,–) nodes(6,element,customer,–) nodes(7,element,depositor,–) nodes(8,element,depositor,–) nodes(9,element,depositor,–) child(2,1) child(3,1) child(4,1) child(5,1) child(6,1) child(7,1) child(8,1) child(9,1) nodes(10,element,account-number,A-101) nodes(11,element,branch-name,Downtown) nodes(12,element,balance,500) child(10,2) child(11,2) child(12,2) nodes(13,element,account-number,A-102) nodes(14,element,branch-name,Perryridge) nodes(15,element,balance,400) child(13,3) child(14,3) child(15,3) nodes(16,element,account-number,A-201) nodes(17,element,branch-name,Brighton) nodes(18,element,balance,900) child(16,4) child(17,4) child(18,4) nodes(19,element,customer-name,Johnson) nodes(20,element,customer-street,Alma) nodes(21,element,customer-city,Palo Alto) child(19,5) child(20,5) child(21,5) nodes(22,element,customer-name,Hayes) nodes(23,element,customer-street,Main) nodes(24,element,customer-city,Harrison) child(22,6) child(23,6) child(24,6) nodes(25,element,account-number,A-101) nodes(26,element,customer-name,Johnson) child(25,7) child(26,7) nodes(27,element,account-number,A-201) nodes(28,element,customer-name,Johnson) child(27,8) child(28,8) nodes(29,element,account-number,A-102) nodes(30,element,customer-name,Hayes) child(29,9) child(30,9) Figure 10.2

Relational Representation of XML Data as Trees

128

Chapter 10

XML

bicycle wheel rim 1 spokes 40 tire 1 2 brake 2 gear 3 frame 1 Figure 10.3 Example Parts Data in XML

C H A P T E R

1 1

Storage and File Structure

This chapter presents basic file structure concepts. The chapter really consists of two parts — the first dealing with relational databases, and the second with objectoriented databases. The second part can be omitted without loss of continuity for later chapters. Many computer science undergraduates have covered some of the material in this chapter in a prior course on data structures or on file structures. Even if students’ backgrounds are primarily in data structures, this chapter is still important since it addresses data structure issues as they pertain to disk storage. Buffer management issues, covered in Section 11.5.1 should be familiar to students who have taken an operating systems course. However, there are database-specific aspects of buffer management that make this section worthwhile even for students with an operating system background. Changes from 3rd edition: The discussion of storage media, in particular magnetic disks (Section 11.2), has been updated to reflect current technology. The section on RAID structures (Section 11.3) has been improved with examples; the comparison of RAID levels has changed, since disk drive capacity improvements have whittled away at the advantages of RAID 5. Coverage of data dictionaries has been expanded.

Exercises
11.1 List the physical storage media available on the computers you use routinely. Give the speed with which data can be accessed on each medium. Answer: Your answer will be based on the computers and storage media that you use. Typical examples would be hard disk, floppy disks and CD-ROM drives.
129

130

Chapter 11

Storage and File Structure

11.2 How does the remapping of bad sectors by disk controllers affect data-retrieval rates? Answer: Remapping of bad sectors by disk controllers does reduce data retrieval rates because of the loss of sequentiality amongst the sectors. But that is better than the loss of data in case of no remapping! 11.3 Consider the following data and parity-block arrangement on four disks:
Disk 1 B1 P1 B8 . . . Disk 2 B2 B5 P2 . . . Disk 3 B3 B6 B9 . . . Disk 4 B4 B7 B10 . . .

The Bi ’s represent data blocks; the Pi ’s represent parity blocks. Parity block Pi is the parity block for data blocks B4i−3 to B4i . What, if any, problem might this arrangement present? Answer: This arrangement has the problem that Pi and B4i−3 are on the same disk. So if that disk fails, reconstruction of B4i−3 is not possible, since data and parity are both lost. 11.4 A power failure that occurs while a disk block is being written could result in the block being only partially written. Assume that partially written blocks can be detected. An atomic block write is one where either the disk block is fully written or nothing is written (i.e., there are no partial writes). Suggest schemes for getting the effect of atomic block writes with the following RAID schemes. Your schemes should involve work on recovery from failure. a. RAID level 1 (mirroring) b. RAID level 5 (block interleaved, distributed parity) Answer: a. To ensure atomicity, a block write operation is carried out as follows:i. Write the information onto the first physical block. ii. When the first write completes successfully, write the same information onto the second physical block. iii. The output is declared completed only after the second write completes successfully. During recovery, each pair of physical blocks is examined. If both are identical and there is no detectable partial-write, then no further actions are necessary. If one block has been partially rewritten, then we replace its contents with the contents of the other block. If there has been no partialwrite, but they differ in content, then we replace the contents of the first block with the contents of the second, or vice versa. This recovery procedure ensures that a write to stable storage either succeeds completely (that is, updates both copies) or results in no change.

Exercises

131

The requirement of comparing every corresponding pair of blocks during recovery is expensive to meet. We can reduce the cost greatly by keeping track of block writes that are in progress, using a small amount of nonvolatile RAM. On recovery, only blocks for which writes were in progress need to be compared. b. The idea is similar here. For any block write, the information block is written first followed by the corresponding parity block. At the time of recovery, each set consisting of the nth block of each of the disks is considered. If none of the blocks in the set have been partially-written, and the parity block contents are consistent with the contents of the information blocks, then no further action need be taken. If any block has been partially-written, it’s contents are reconstructed using the other blocks. If no block has been partially-written, but the parity block contents do not agree with the information block contents, the parity block’s contents are reconstructed. 11.5 RAID systems typically allow you to replace failed disks without stopping access to the system. Thus, the data in the failed disk must be rebuilt and written to the replacement disk while the system is in operation. With which of the RAID levels is the amount of interference between the rebuild and ongoing disk accesses least? Explain your answer. Answer: RAID level 1 (mirroring) is the one which facilitates rebuilding of a failed disk with minimum interference with the on-going disk accesses. This is because rebuilding in this case involves copying data from just the failed disk’s mirror. In the other RAID levels, rebuilding involves reading the entire contents of all the other disks. 11.6 Give an example of a relational-algebra expression and a query-processing strategy in each of the following situations: a. MRU is preferable to LRU. b. LRU is preferable to MRU. Answer:

a. MRU is preferable to LRU where R1 ½ R2 is computed by using a nestedloop processing strategy where each tuple in R2 must be compared to each block in R1 . After the first tuple of R2 is processed, the next needed block is the first one in R1 . However, since it is the least recently used, the LRU buffer management strategy would replace that block if a new block was needed by the system. b. LRU is preferable to MRU where R1 ½ R2 is computed by sorting the relations by join values and then comparing the values by proceeding through the relations. Due to duplicate join values, it may be necessary to “backup” in one of the relations. This “backing-up” could cross a block boundary into the most recently used block, which would have been replaced by a system using MRU buffer management, if a new block was needed.

132

Chapter 11

Storage and File Structure

Under MRU, some unused blocks may remain in memory forever. In practice, MRU can be used only in special situations like that of the nestedloop strategy discussed in example 0.a

11.7 Consider the deletion of record 5 from the file of Figure 11.8. Compare the relative merits of the following techniques for implementing the deletion: a. Move record 6 to the space occupied by record 5, and move record 7 to the space occupied by record 6. b. Move record 7 to the space occupied by record 5. c. Mark record 5 as deleted, and move no records. Answer: a. Although moving record 6 to the space for 5, and moving record 7 to the space for 6, is the most straightforward approach, it requires moving the most records, and involves the most accesses. b. Moving record 7 to the space for 5 moves fewer records, but destroys any ordering in the file. c. Marking the space for 5 as deleted preserves ordering and moves no records, but requires additional overhead to keep track of all of the free space in the file. This method may lead to too many “holes” in the file, which if not compacted from time to time, will affect performance because of reduced availability of contiguous free records.

11.8 Show the structure of the file of Figure 11.9 after each of the following steps: a. Insert (Brighton, A-323, 1600). b. Delete record 2. c. Insert (Brighton, A-626, 2000). Answer: (We use “↑ i” to denote a pointer to record “i”.) The original file of Figure 11.9: header record 0 record 1 record 2 record 3 record 4 record 5 record 6 record 7 record 8 ↑1 ↑4 ↑6 Perryridge Mianus Downtown Perryridge Downtown Perryridge A-102 400 A-215 700 A-101 500 A-201 900 A-110 600 A-218 700

a. The file after insert (Brighton, A-323, 1600).

Exercises

133

header record 0 record 1 record 2 record 3 record 4 record 5 record 6 record 7 record 8 header record 0 record 1 record 2 record 3 record 4 record 5 record 6 record 7 record 8

↑4 Perryridge Brighton Mianus Downtown Perryridge Downtown Perryridge ↑2 ↑4 ↑6 Perryridge Brighton Downtown Perryridge Downtown Perryridge A-102 400 A-323 1600 A-101 500 A-201 900 A-110 600 A-218 700 A-102 A-323 A-215 A-101 400 1600 700 500

↑6

A-201 900 A-110 600 A-218 700

b. The file after delete record 2.

The free record chain could have alternatively been from the header to 4, from 4 to 2, and finally from 2 to 6. c. The file after insert (Brighton, A-626, 2000). header record 0 record 1 record 2 record 3 record 4 record 5 record 6 record 7 record 8 ↑4 Perryridge Brighton Brighton Downtown Perryridge Downtown Perryridge A-102 A-323 A-626 A-101 400 1600 2000 500

↑6

A-201 900 A-110 600 A-218 700

11.9 Give an example of a database application in which the reserved-space method of representing variable-length records is preferable to the pointer method. Explain your answer. Answer: In the reserved space method, a query comparing the last existing field in a record to some value requires only one read from the disk. This single read is preferable to the potentially many reads needed to chase down the pointers to the last field if the pointer method is used.

134

Chapter 11

Storage and File Structure

11.10 Give an example of a database application in which the pointer method of representing variable-length records is preferable to the reserved-space method. Explain your answer. Answer: Using the pointer method, a join operation on attributes which are only in the anchor block can be performed on only this smaller amount of data, rather than on the entire relation, as would be the case using the reserved space method. Therefore, in this join example, the pointer method is preferable. 11.11 Show the structure of the file of Figure 11.12 after each of the following steps: a. Insert (Mianus, A-101, 2800). b. Insert (Brighton, A-323, 1600). c. Delete (Perryridge, A-102, 400). Answer: a. insert (Mianus, A-101, 2800) changes record 2 to: 2 Mianus A-215 700 A-101 2800 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥

b. insert (Brighton, A-323, 1600) changes record 5 to: 5 Brighton A-216 750 A-323 1600

c. delete (Perryridge, A-102, 400) changes record 0 to: 0 Perryridge A-102 900 A-218 700

Exercises

135

11.12 What happens if you attempt to insert the record

(Perryridge, A-929, 3000)

into the file of Figure 11.12? Answer: Inserting (Perryridge, A-929, 3000) into the file of Figure 11.12 causes an error because the Perryridge record has exceeded the maximum length reserved. 11.13 Show the structure of the file of Figure 11.13 after each of the following steps: a. Insert (Mianus, A-101, 2800). b. Insert (Brighton, A-323, 1600). c. Delete (Perryridge, A-102, 400). Answer: a. The figure after insert (Mianus, A-101, 2800). 0 1 2 3 4 5 6 7 8 9 ↑5 ↑9 ↑7 ↑8 Perryridge Round Hill Mianus Downtown Redwood Brighton A-102 A-305 A-215 A-101 A-222 A-201 A-216 A-110 A-218 A-101 400 350 700 500 700 900 750 600 700 2800

b. The figure after insert (Brighton, A-323, 1600). 0 1 2 3 4 5 6 7 8 9 10 ↑5 ↑9 ↑7 ↑8 ↑ 10 Perryridge Round Hill Mianus Downtown Redwood Brighton A-102 A-305 A-215 A-101 A-222 A-201 A-216 A-110 A-218 A-101 A-323 400 350 700 500 700 900 750 600 700 2800 1600

c. The figure after delete (Perryridge, A-102, 400).

136

Chapter 11

Storage and File Structure

1 2 3 4 5 6 7 8 9 10

↑9 ↑7 ↑8 ↑ 10

Round Hill Mianus Downtown Redwood Perryridge Brighton

A-305 A-215 A-101 A-222 A-201 A-216 A-110 A-218 A-101 A-323

350 700 500 700 900 750 600 700 2800 1600

11.14 Explain why the allocation of records to blocks affects database-system performance significantly. Answer: If we allocate related records to blocks, we can often retrieve most, or all, of the requested records by a query with one disk access. Disk accesses tend to be the bottlenecks in databases; since this allocation strategy reduces the number of disk accesses for a given operation, it significantly improves performance. 11.15 If possible, determine the buffer-management strategy used by the operating system running on your local computer system, and what mechanisms it provides to control replacement of pages. Discuss how the control on replacement that it provides would be useful for the implementation of database systems. Answer: The typical OS uses LRU for buffer replacement. This is often a bad strategy for databases. As explained in Section 11.5.2 of the text, MRU is the best strategy for nested loop join. In general no single strategy handles all scenarios well, and ideally the database system should be given its own buffer cache for which the replacement policy takes into account all the performance related issues. 11.16 In the sequential file organization, why is an overflow block used even if there is, at the moment, only one overflow record? Answer: An overflow block is used in sequential file organization because a block is the smallest space which can be read from a disk. Therefore, using any smaller region would not be useful from a performance standpoint. The space saved by allocating disk storage in record units would be overshadowed by the performance cost of allowing blocks to contain records of multiple files. 11.17 List two advantages and two disadvantages of each of the following strategies for storing a relational database: a. Store each relation in one file. b. Store multiple relations (perhaps even the entire database) in one file. Answer: a. Advantages of storing a relation as a file include using the file system provided by the OS , thus simplifying the DBMS, but incurs the disadvantage

Exercises

137

of restricting the ability of the DBMS to increase performance by using more sophisticated storage structures. b. By using one file for the entire database, these complex structures can be implemented through the DBMS, but this increases the size and complexity of the DBMS. 11.18 Consider a relational database with two relations: course (course-name, room, instructor) enrollment (course-name, student-name, grade) Define instances of these relations for three courses, each of which enrolls five students. Give a file structure of these relations that uses clustering. course relation course-name room instructor Pascal CS-101 Calvin, B c1 Answer: C CS-102 Calvin, B c2 LISP CS-102 Kess, J c3 enrollment relation course-name student-name grade Pascal Carper, D A Pascal Merrick, L A Pascal Mitchell, N B Pascal Bliss, A C Pascal Hames, G C C Nile, M A C Mitchell, N B C Carper, D A C Hurly, I B C Hames, G A Lisp Bliss, A C Lisp Hurly, I B Lisp Nile, M D Lisp Stars, R A Lisp Carper, D A

e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 e14 e15

Block 0 contains: c1 , e1 , e2 , e3 , e4 , and e5 Block 1 contains: c2 , e6 , e7 , e8 , e9 and e10 Block 2 contains: c3 , e11 , e12 , e13 , e14 , and e15 11.19 Consider the following bitmap technique for tracking free space in a file. For each block in the file, two bits are maintained in the bitmap. If the block is between 0 and 30 percent full the bits are 00, between 30 and 60 percent the bits are 01, between 60 and 90 percent the bits are 10, and above 90 percent the bits are 11. Such bitmaps can be kept in memory even for quite large files.

138

Chapter 11

Storage and File Structure

a. Describe how to keep the bitmap up-to-date on record insertions and deletions. b. Outline the benefit of the bitmap technique over free lists when searching for free space and when updating free space information. Answer: a. Everytime a record is inserted/deleted, check if the usage of the block has changed levels. In that case, update the corrosponding bits. b. If free space for n records is required, then in free lists technique, n accesses of the list of free records are required. However, in bitmap technique, a block with free space for n recores (or more that one blocks if required) can be directly found out. The free space thus obtained is also more contiguous than that obtained by free list technique. 11.20 Give a normalized version of the Index-metadata relation, and explain why using the normalized version would result in worse performance. Answer: The Index-metadata relation can be normalized as follows Index-metadata (index-name, relation-name, index-type, attrib-set) Attribset-metadata (relation-name, attrib-set, attribute-name) Though the normalized version will have less space requirements, but it will require extra disk accesses to read Attribset-metadata everytime an index has to be accessed. Thus, it will lead to worse performance. 11.21 Explain why a physical OID must contain more information than a pointer to a physical storage location. Answer: A physical OID needs to have a unique identifier in addition to a pointer to a physical storage location. This is required to prevent dereferences of dangling pointers. 11.22 If physical OIDs are used, an object can be relocated by keeping a forwarding pointer to its new location. In case an object gets forwarded multiple times, what would be the effect on retrieval speed? Suggest a technique to avoid multiple accesses in such a case. Answer: If an object gets forwarded multiple times, the retrieval speed will decrease because accessing it will require accessing the series of locations from which the object has been successively forwarded to the current location. Multiple accesses can be avoided by always keeping in the oldest location the latest address of the object. This can be done by checking while forwarding whether this object has already been forwarded and in that case updating the forwarding address at the oldest location. Thus, atmost two accesses will be required. 11.23 Define the term dangling pointer. Describe how the unique-id scheme helps in detecting dangling pointers in an object-oriented database.

Exercises

139

Answer: A dangling pointer is a pointer to an area which no longer contains valid data. In the unique-id scheme to detect dangling pointers, physical OIDs may contain a unique identifier which is an integer that distinguishes the OID from the identifiers of other objects that happened to be stored at the same location earlier, and were deleted or moved elsewhere. The unique identifier is also stored with the object, and the identifiers in an OID and the corresponding object should match. If the unique identifier in a physical OID does not match the unique identifier in the object to which that OID points, the system detects that the pointer is a dangling pointer, and signals an error. 11.24 Consider the example on page 435, which shows that there is no need for deswizzling if hardware swizzling is used. Explain why, in that example, it is safe to change the short identifier of page 679.34278 from 2395 to 5001. Can some other page already have short identifier 5001? If it could, how can you handle that situation? Answer: While swizzling, if the short identifier of page 679.34278 is changed from 2395 to 5001, it is either because a. the system discovers that 679.34278 has already been allocated the virtualmemory page 5001 in some previous step, or else b. 679.34278 has not been allocated any virtual memory page so far, and the free virtual memory page 5001 is now allocated to it. Thus in either case, it cannot be true that the current page already uses the same short identifier 5001 to refer to some database page other than 679.34278. Some other page may use 5001 to refer to a different database page, but then each page has its own independent mapping from short to full page identifiers, so this is all right. Note that if we do swizzling as described in the text, and different processes need simultaneous access to a database page, they will have to map separate copies of the page to their individual virtual address spaces. Extensions to the scheme are possible to avoid this.

C H A P T E R

1 2

Indexing and Hashing

This chapter covers indexing techniques ranging from the most basic one to highly specialized ones. Due to the extensive use of indices in database systems, this chapter constitutes an important part of a database course. A class that has already had a course on data-structures would likely be familiar with hashing and perhaps even B+ -trees. However, this chapter is necessary reading even for those students since data structures courses typically cover indexing in main memory. Although the concepts carry over to database access methods, the details (e.g., block-sized nodes), will be new to such students. The sections on B-trees (Sections 12.4), grid files (Section 12.9.3) and bitmap indexing (Section 12.9.4) may be omitted if desired. Changes from 3rd edition: The description of querying on B+ -trees has been augmented with pseudo-code. The pseudo-code for insertion on B+ -trees has been simplified. The section on index definition in SQL (Section 12.8) is new to this edition, as is the coverage of bitmap indices (Section 12.9.4).

Exercises
12.1 When is it preferable to use a dense index rather than a sparse index? Explain your answer. Answer: It is preferable to use a dense index instead of a sparse index when the file is not sorted on the indexed field (such as when the index is a secondary index) or when the index file is small compared to the size of memory. 12.2 Since indices speed query processing, why might they not be kept on several search keys? List as many reasons as possible. Answer: Reasons for not keeping several search indices include:
141

142

Chapter 12

Indexing and Hashing

a. Every index requires additional CPU time and disk I/O overhead during inserts and deletions. b. Indices on non-primary keys might have to be changed on updates, although an index on the primary key might not (this is because updates typically do not modify the primary key attributes). c. Each extra index requires additional storage space. d. For queries which involve conditions on several search keys, efficiency might not be bad even if only some of the keys have indices on them. Therefore database performance is improved less by adding indices when many indices already exist. 12.3 What is the difference between a primary index and a secondary index? Answer: The primary index is on the field which specifies the sequential order of the file. There can be only one primary index while there can be many secondary indices. 12.4 Is it possible in general to have two primary indices on the same relation for different search keys? Explain your answer. Answer: In general, it is not possible to have two primary indices on the same relation for different keys because the tuples in a relation would have to be stored in different order to have same values stored together. We could accomplish this by storing the relation twice and duplicating all values, but for a centralized system, this is not efficient. 12.5 Construct a B+ -tree for the following set of key values: (2, 3, 5, 7, 11, 17, 19, 23, 29, 31) Assume that the tree is initially empty and values are added in ascending order. Construct B+ -trees for the cases where the number of pointers that will fit in one node is as follows: a. Four b. Six c. Eight Answer: The following were generated by inserting values into the B+ -tree in ascending order. A node (other than the root) was never allowed to have fewer than n/2 values/pointers. a.
5 2 3 5 7 11 11 17 19 29 19 23 29 31

b.

Exercises

143

7 2 3 5
11 2 3 5 7

19 11 17 19 23 29 31

7

c.

11

17

19

23

29

31

12.6 For each B+ -tree of Exercise 12.5, show the steps involved in the following queries: a. Find records with a search-key value of 11. b. Find records with a search-key value between 7 and 17, inclusive. Answer: With structure 0.a: a. Find records with a value of 11 i. Search the first level index; follow the first pointer. ii. Search next level; follow the third pointer. iii. Search leaf node; follow first pointer to records with key value 11. b. Find records with value between 7 and 17 (inclusive) i. Search top index; follow first pointer. ii. Search next level; follow second pointer. iii. Search third level; follow second pointer to records with key value 7, and after accessing them, return to leaf node. iv. Follow fourth pointer to next leaf block in the chain. v. Follow first pointer to records with key value 11, then return. vi. Follow second pointer to records with with key value 17. With structure 0.b: a. Find records with a value of 11 i. Search top level; follow second pointer. ii. Search next level; follow second pointer to records with key value 11. b. Find records with value between 7 and 17 (inclusive) i. Search top level; follow second pointer. ii. Search next level; follow first pointer to records with key value 7, then return. iii. Follow second pointer to records with key value 11, then return. iv. Follow third pointer to records with key value 17. With structure 0.c: a. Find records with a value of 11 i. Search top level; follow second pointer. ii. Search next level; follow first pointer to records with key value 11. b. Find records with value between 7 and 17 (inclusive)

144

Chapter 12

Indexing and Hashing

i. Search top level; follow first pointer. ii. Search next level; follow fourth pointer to records with key value 7, then return. iii. Follow eighth pointer to next leaf block in chain. iv. Follow first pointer to records with key value 11, then return. v. Follow second pointer to records with key value 17. 12.7 For each B+ -tree of Exercise 12.5, show the form of the tree after each of the following series of operations: a. b. c. d. e. Insert 9. Insert 10. Insert 8. Delete 23. Delete 19.

Answer: • With structure 0.a: Insert 9:
19 5 2 3 5 7 11 9 11 17 29 19 23 29 31

Insert 10:
19 5 2 3 5 7 9 9 11 10 11 29 17 19 23 29 31

Insert 8:
19 5 2 3 5 7 8 9 9 11 10 11 29 17 19 23 29 31

Delete 23:

Exercises
11 5 2 3 5 7 8 9 9 10 19 11 17 19 29

145

31

Delete 19:
11 5 2 3 5 7 8 9 9 10 29 11 17 29 31

• With structure 0.b: Insert 9:
7 2 3 5 7 19 9 11 17 19 23 29 31

Insert 10:
7 2 3 5 7 19 9 10 11 17 19 23 29 31

Insert 8:
7 2 3 5 7 8 9 10 19 10 11 17 19 23 29 31

Delete 23:
7 2 3 5 7 8 9 10 19 10 11 17 19 29 31

Delete 19:
7 2 3 5 7 10 8 9 10 11 17 29 31

• With structure 0.c:

146

Chapter 12

Indexing and Hashing

Insert 9:
11 2 3 5 7 9 11 17 19 23 29 31

Insert 10:
11 2 3 5 7 9 10 11 17 19 23 29 31

Insert 8:
11 2 3 5 7 8 9 10 11 17 19 23 29 31

Delete 23:
11 2 3 5 7 8 9 10 11 17 19 29 31

Delete 19:
11 2 3 5 7 8 9 10 11 17 29 31

12.8 Consider the modified redistribution scheme for B+ -trees described in page 463. What is the expected height of the tree as a function of n? Answer: If there are K search-key values and m − 1 siblings are involved in the redistribution, the expected height of the tree is: log (m−1)n/m (K) 12.9 Repeat Exercise 12.5 for a B-tree. Answer: The algorithm for insertion into a B-tree is: Locate the leaf node into which the new key-pointer pair should be inserted. If there is space remaining in that leaf node, perform the insertion at the correct location, and the task is over. Otherwise insert the key-pointer pair conceptually into the correct location in the leaf node, and then split it along the middle. The middle key-pointer pair does not go into either of the resultant nodes of the split operation. Instead it is inserted into the parent node, along with the tree pointer to the new child. If there is no space in the parent, a similar procedure is repeated. The deletion algorithm is:

Exercises

147

Locate the key value to be deleted, in the B-tree. a. If it is found in a leaf node, delete the key-pointer pair, and the record from the file. If the leaf node contains less than n/2 − 1 entries as a result of this deletion, it is either merged with its siblings, or some entries are redistributed to it. Merging would imply a deletion, whereas redistribution would imply change(s) in the parent node’s entries. The deletions may ripple upto the root of the B-tree. b. If the key value is found in an internal node of the B-tree, replace it and its record pointer by the smallest key value in the subtree immediately to its right and the corresponding record pointer. Delete the actual record in the database file. Then delete that smallest key value-pointer pair from the subtree. This deletion may cause further rippling deletions till the root of the B-tree. Below are the B-trees we will get after insertion of the given key values. We assume that leaf and non-leaf nodes hold the same number of search key values. a.

??
b.

2

3

9

? ? ? XX ZZ XXXX ~ + z 7 11 19 23 31 ?? ?? ?
? ? XXXXXXX XXX ? z ???
11
11 17 19 7 23

5

17

29

???
c.

2

3

5

??

29 31

2

3

5

7

17 19 23 29 31

12.10 Explain the distinction between closed and open hashing. Discuss the relative merits of each technique in database applications. Answer: Open hashing may place keys with the same hash function value in different buckets. Closed hashing always places such keys together in the same bucket. Thus in this case, different buckets can be of different sizes, though the

148

Chapter 12

Indexing and Hashing

implementation may be by linking together fixed size buckets using overflow chains. Deletion is difficult with open hashing as all the buckets may have to inspected before we can ascertain that a key value has been deleted, whereas in closed hashing only that bucket whose address is obtained by hashing the key value need be inspected. Deletions are more common in databases and hence closed hashing is more appropriate for them. For a small, static set of data lookups may be more efficient using open hashing. The symbol table of a compiler would be a good example.

12.11 What are the causes of bucket overflow in a hash file organization? What can be done to reduce the occurrence of bucket overflows? Answer: The causes of bucket overflow are :a. Our estimate of the number of records that the relation will have was too low, and hence the number of buckets allotted was not sufficient. b. Skew in the distribution of records to buckets. This may happen either because there are many records with the same search key value, or because the the hash function chosen did not have the desirable properties of uniformity and randomness. To reduce the occurrence of overflows, we can :a. Choose the hash function more carefully, and make better estimates of the relation size. b. If the estimated size of the relation is nr and number of records per block is fr , allocate (nr /fr ) ∗ (1 + d) buckets instead of (nr /fr ) buckets. Here d is a fudge factor, typically around 0.2. Some space is wasted: About 20 percent of the space in the buckets will be empty. But the benefit is that some of the skew is handled and the probability of overflow is reduced.

12.12 Suppose that we are using extendable hashing on a file that contains records with the following search-key values:

2, 3, 5, 7, 11, 17, 19, 23, 29, 31

Show the extendable hash structure for this file if the hash function is h(x) = x mod 8 and buckets can hold three records. Answer:

Exercises

149

2 17

3 000 001 010 011 100 101 110 111

3 2

3 3 11 19 2 5 29 2

7 23 31

12.13 Show how the extendable hash structure of Exercise 12.12 changes as the result of each of the following steps: a. b. c. d. Delete 11. Delete 31. Insert 1. Insert 15.

Answer: a. Delete 11: From the answer to Exercise 12.12, change the third bucket to:

3 3 19
At this stage, it is possible to coalesce the second and third buckets. Then it is enough if the bucket address table has just four entries instead of eight. For the purpose of this answer, we do not do the coalescing. b. Delete 31: From the answer to 12.12, change the last bucket to:

150

Chapter 12

Indexing and Hashing

2

7 23

c. Insert 1: From the answer to 12.12, change the first bucket to:

2

1 17

d. Insert 15: From the answer to 12.12, change the last bucket to:

2

7 15 23

12.14 Give pseudocode for deletion of entries from an extendable hash structure, including details of when and how to coalesce buckets. Do not bother about reducing the size of the bucket address table. Answer: Let i denote the number of bits of the hash value used in the hash table. Let BSIZE denote the maximum capacity of each bucket.

Exercises

151

delete(value Kl ) begin j = first i high-order bits of h(Kl ); delete value Kl from bucket j; coalesce(bucket j); end coalesce(bucket j) begin ij = bits used in bucket j; k = any bucket with first (ij − 1) bits same as that of bucket j while the bit ij is reversed; ik = bits used in bucket k; if(ij = ik ) return; /* buckets cannot be merged */ if(entries in j + entries in k > BSIZE) return; /* buckets cannot be merged */ move entries of bucket k into bucket j; decrease the value of ij by 1; make all the bucket-address-table entries, which pointed to bucket k, point to j; coalesce(bucket j); end Note that we can only merge two buckets at a time. The common hash prefix of the resultant bucket will have length one less than the two buckets merged. Hence we look at the buddy bucket of bucket j differing from it only at the last bit. If the common hash prefix of this bucket is not ij , then this implies that the buddy bucket has been further split and merge is not possible. When merge is successful, further merging may be possible, which is handled by a recursive call to coalesce at the end of the function. 12.15 Suggest an efficient way to test if the bucket address table in extendable hashing can be reduced in size, by storing an extra count with the bucket address table. Give details of how the count should be maintained when buckets are split, coalesced or deleted. (Note: Reducing the size of the bucket address table is an expensive operation, and subsequent inserts may cause the table to grow again. Therefore, it is best not to reduce the size as soon as it is possible to do so, but instead do it only if the number of index entries becomes small compared to the bucket address table size.) Answer: If the hash table is currently using i bits of the hash value, then maintain a count of buckets for which the length of common hash prefix is exactly i.

152

Chapter 12

Indexing and Hashing

Consider a bucket j with length of common hash prefix ij . If the bucket is being split, and ij is equal to i, then reset the count to 1. If the bucket is being split and ij is one less that i, then increase the count by 1. It the bucket if being coalesced, and ij is equal to i then decrease the count by 1. If the count becomes 0, then the bucket address table can be reduced in size at that point. However, note that if the bucket address table is not reduced at that point, then the count has no significance afterwards. If we want to postpone the reduction, we have to keep an array of counts, i.e. a count for each value of common hash prefix. The array has to be updated in a similar fashion. The bucket address table can be reduced if the ith entry of the array is 0, where i is the number of bits the table is using. Since bucket table reduction is an expensive operation, it is not always advisable to reduce the table. It should be reduced only when sufficient number of entries at the end of count array become 0.

12.16 Why is a hash structure not the best choice for a search key on which range queries are likely? Answer: A range query cannot be answered efficiently using a hash index, we will have to read all the buckets. This is because key values in the range do not occupy consecutive locations in the buckets, they are distributed uniformly and randomly throughout all the buckets.

12.17 Consider a grid file in which we wish to avoid overflow buckets for performance reasons. In cases where an overflow bucket would be needed, we instead reorganize the grid file. Present an algorithm for such a reorganization. Answer: Let us consider a two-dimensional grid array. When a bucket overflows, we can split the ranges corresponding to that row and column into two, in both the linear scales. Thus the linear scales will get one additional entry each, and the bucket is split into four buckets. The ranges should be split in such a way as to ensure that the four resultant buckets have nearly the same number of values. There can be several other heuristics for deciding how to reorganize the ranges, and hence the linear scales and grid array.

12.18 Consider the account relation shown in Figure 12.25. a. Construct a bitmap index on the attributes branch-name and balance, dividing balance values into 4 ranges: below 250, 250 to below 500, 500 to below 750, and 750 and above. b. Consider a query that requests all accounts in Downtown with a balance of 500 or more. Outline the steps in answering the query, and show the final and intermediate bitmaps constructed to answer the query. Answer: We reproduce the account relation of Figure 12.25 below.

Exercises

153

A-217 A-101 A-1 10 A-215 A-102 A-201 A-218 A-222 A-305
Bitmaps for branch-name Brighton 1 0 0 0 Downtown 0 1 1 0 Mianus 0 0 0 1 Perryridge 0 0 0 0 Redwood 0 0 0 0 Round hill 0 0 0 0 Bitmaps for balance L1 L2 L3 L4 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0

Brighton Downtown Downtown Mianus Perryridge Perryridge Perryridge Redwood Round Hill

750 500 600 700 400 900 700 700 350

0 0 0 1 0 0 0 0 1 0

0 0 0 1 0 0 0 1 0 0

0 0 0 1 0 0

0 0 0 0 1 0

0 0 0 0 0 1

where, level L1 is below 250, level L2 is from 250 to below 500, L3 from 500 to below 750 and level L4 is above 750. To find all accounts in Downtown with a balance of 500 or more, we find the union of bitmaps for levels L3 and L4 and then intersect it with the bitmap for Downtown. Downtown L3 L4 L3 ∪ L4 Downtown Downtown ∩(L3 ∪ L4 ) 0 0 1 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0

Thus, the required tuples are A-101 and A-110. 12.19 Show how to compute existence bitmaps from other bitmaps. Make sure that your technique works even in the presence of null values, by using a bitmap for the value null. Answer: The existence bitmap for a relation can be calculated by taking the

154

Chapter 12

Indexing and Hashing

union (logical-or) of all the bitmaps on that attribute, including the bitmap for value null. 12.20 How does data encryption affect index schemes? In particular, how might it affect schemes that attempt to store data in sorted order? Answer: Note that indices must operate on the encrypted data or someone could gain access to the index to interpret the data. Otherwise, the index would have to be restricted so that only certain users could access it. To keep the data in sorted order, the index scheme would have to decrypt the data at each level in a tree. Note that hash systems would not be affected.

C H A P T E R

1 3

Query Processing

This chapter describes the process by which queries are executed efficiently by a database system. The chapter starts off with measures of cost, then proceeds to algorithms for evaluation of relational algebra operators and expressions. This chapter applies concepts from Chapters 3, 11, and 12. Changes from 3rd edition: The single chapter on query processing in the previous edition has been replaced by two chapters, the first on query processing and the second on query optimization. Another significant change is the separation of size estimation from the presentation of query processing algorithms. As a result, of these changes, query processing algorithms can be covered without tedious and distracting details of size estimation. Although size estimation is covered later, in Chapter 14, the presentation there has been simplified by omitting some details. Instructors can choose to cover query processing but omit query optimization, without loss of continuity with later chapters.

Exercises
13.1 Why is it not desirable to force users to make an explicit choice of a queryprocessing strategy? Are there cases in which it is desirable for users to be aware of the costs of competing query-processing strategies? Explain your answer. Answer: In general it is not desirable to force users to choose a query processing strategy because naive users might select an inefficient strategy. The reason users would make poor choices about processing queries is that they would not know how a relation is stored, nor about its indices. It is unreasonable to force users to be aware of these details since ease of use is a major object
155

156

Chapter 13

Query Processing

of database query languages. If users are aware of the costs of different strategies they could write queries efficiently, thus helping performance. This could happen if experts were using the system. 13.2 Consider the following SQL query for our bank database: select T.branch-name from branch T, branch S where T.assets > S.assets and S.branch-city = “Brooklyn” Write an efficient relational-algebra expression that is equivalent to this query. Justify your choice. Answer: ΠT.branch-name ((Πbranch-name, assets (ρT (branch))) ½T.assets>S.assets (Πassets (σ(branch-city = “Brooklyn”) (ρS (branch))))) This expression performs the theta join on the smallest amount of data possible. It does this by restricting the right hand side operand of the join to only those branches in Brooklyn, and also eliminating the unneeded attributes from both the operands. 13.3 What are the advantages and disadvantages of hash indices relative to B+ -tree indices? How might the type of index available influence the choice of a queryprocessing strategy? Answer: Hash indices enable us to perform point lookup (eg. σA=r (relation)) operations very fast, but for range searches the B+ -tree index would be much more efficient. If there is a range query to be evaluated, and only a hash index is available, the better strategy might be to perform a file scan rather than using that index. 13.4 Assume (for simplicity in this exercise) that only one tuple fits in a block and memory holds at most 3 page frames. Show the runs created on each pass of the sort-merge algorithm, when applied to sort the following tuples on the first attribute: (kangaroo, 17), (wallaby, 21), (emu, 1), (wombat, 13), (platypus, 3), (lion, 8), (warthog, 4), (zebra, 11), (meerkat, 6), (hyena, 9), (hornbill, 2), (baboon, 12). Answer: We will refer to the tuples (kangaroo, 17) through (baboon, 12) using tuple numbers t1 through t12 . We refer to the j th run used by the ith pass, as rij . The initial sorted runs have three blocks each. They are:r11 r12 r13 r14 = = = = {t3 , t1 , t2 } {t6 , t5 , t4 } {t9 , t7 , t8 } {t12 , t11 , t10 }

Exercises

157

Each pass merges three runs. Therefore the runs after the end of the first pass are:r21 r22 = = {t3 , t1 , t6 , t9 , t5 , t2 , t7 , t4 , t8 } {t12 , t11 , t10 }

At the end of the second pass, the tuples are completely sorted into one run:r31 = {t12 , t3 , t11 , t10 , t1 , t6 , t9 , t5 , t2 , t7 , t4 , t8 }

13.5 Let relations r1 (A, B, C) and r2 (C, D, E) have the following properties: r1 has 20,000 tuples, r2 has 45,000 tuples, 25 tuples of r1 fit on one block, and 30 tuples of r2 fit on one block. Estimate the number of block accesses required, using each of the following join strategies for r1 ½ r2 : a. b. c. d. Nested-loop join Block nested-loop join Merge join Hash join

Answer: r1 needs 800 blocks, and r2 needs 1500 blocks. Let us assume M pages of memory. If M > 800, the join can easily be done in 1500 + 800 disk accesses, using even plain nested-loop join. So we consider only the case where M ≤ 800 pages. a. Nested-loop join: Using r1 as the outer relation we need 20000 ∗ 1500 + 800 = 30, 000, 800 disk accesses, if r2 is the outer relation we need 45000 ∗ 800 + 1500 = 36, 001, 500 disk accesses. b. Block nested-loop join: 800 If r1 is the outer relation, we need M−1 ∗ 1500 + 800 disk accesses, if 1500 r2 is the outer relation we need M−1 ∗ 800 + 1500 disk accesses. c. Merge-join: Assuming that r1 and r2 are not initially sorted on the join key, the total sorting cost inclusive of the output is Bs = 1500(2 logM−1(1500/M ) + 2) + 800(2 logM−1(800/M ) + 2) disk accesses. Assuming all tuples with the same value for the join attributes fit in memory, the total cost is Bs + 1500 + 800 disk accesses. d. Hash-join: We assume no overflow occurs. Since r1 is smaller, we use it as the build relation and r2 as the probe relation. If M > 800/M , i.e. no need for recursive partitioning, then the cost is 3(1500 + 800) = 6900 disk accesses, else the cost is 2(1500 + 800) logM−1 (800) − 1 + 1500 + 800 disk accesses. 13.6 Design a variant of the hybrid merge – join algorithm for the case where both relations are not physically sorted, but both have a sorted secondary index on the join attributes. Answer: We merge the leaf entries of the first sorted secondary index with

158

Chapter 13

Query Processing

the leaf entries of the second sorted secondary index. The result file contains pairs of addresses, the first address in each pair pointing to a tuple in the first relation, and the second address pointing to a tuple in the second relation. This result file is first sorted on the first relation’s addresses. The relation is then scanned in physical storage order, and addresses in the result file are replaced by the actual tuple values. Then the result file is sorted on the second relation’s addresses, allowing a scan of the second relation in physical storage order to complete the join. 13.7 The indexed nested-loop join algorithm described in Section 13.5.3 can be inefficient if the index is a secondary index, and there are multiple tuples with the same value for the join attributes. Why is it inefficient? Describe a way, using sorting, to reduce the cost of retrieving tuples of the inner relation. Under what conditions would this algorithm be more efficient than hybrid merge– join? Answer: If there are multiple tuples in the inner relation with the same value for the join attributes, we may have to access that many blocks of the inner relation for each tuple of the outer relation. That is why it is inefficient. To reduce this cost we can perform a join of the outer relation tuples with just the secondary index leaf entries, postponing the inner relation tuple retrieval. The result file obtained is then sorted on the inner relation addresses, allowing an efficient physical order scan to complete the join. Hybrid merge–join requires the outer relation to be sorted. The above algorithm does not have this requirement, but for each tuple in the outer relation it needs to perform an index lookup on the inner relation. If the outer relation is much larger than the inner relation, this index lookup cost will be less than the sorting cost, thus this algorithm will be more efficient. 13.8 Estimate the number of block accesses required by your solution to Exercise 13.6 for r1 ½ r2 , where r1 and r2 are as defined in Exercise 13.5. Answer: r1 occupies 800 blocks, and r2 occupies 1500 blocks. Let there be n pointers per index leaf block (we assume that both the indices have leaf blocks and pointers of equal sizes). Let us assume M pages of memory, M < 800. r1 ’s index will need B1 = 20000 leaf blocks, and r2 ’s index will need n B2 = 45000 leaf blocks. Therefore the merge join will need B3 = B1 + B2 n accesses, without output. The number of output tuples is estimated as no = 20000∗45000 max(V (C,r1 ),V (C,r2 )) . Each output tuple will need two pointers, so the number no of blocks of join output will be Bo1 = n/2 . Hence the join needs Bj = B3 +Bo1 disk block accesses. Now we have to replace the pointers by actual tuples. For the first sorting, = Bs1 Bo1 (2 logM−1 (Bo1 /M ) + 2) disk accesses are needed, including the writing of output to disk. The number of blocks of r1 which have to be accessed in order to replace the pointers with tuple values is min(800, no). Let n1 pairs of the form (r1 tuple, pointer to r2 ) fit in one disk block. Therefore the intermediate result after replacing the r1 pointers will occupy Bo2 = (no /n1 ) blocks.

Exercises

159

Hence the first pass of replacing the r1 -pointers will cost Bf = Bs1 + Bo1 + min(800, no) + Bo2 disk accesses. The second pass for replacing the r2 -pointers has a similar analysis. Let n2 tuples of the final join fit in one block. Then the second pass of replacing the r2 -pointers will cost Bs = Bs2 + Bo2 + min(1500, no) disk accesses, where Bs2 = Bo2 (2 logM−1 (Bo2 /M ) + 2). Hence the total number of disk accesses for the join is Bj + Bf + Bs , and the number of pages of output is no /n2 . 13.9 Let r and s be relations with no indices, and assume that the relations are not sorted. Assuming infinite memory, what is the lowest cost way (in terms of I/O operations) to compute r ½ s? What is the amount of memory required for this algorithm? Answer: We can store the entire smaller relation in memory, read the larger relation block by block and perform nested loop join using the larger one as the outer relation. The number of I/O operations is equal to br + bs , and memory requirement is min(br , bs ) + 2 pages. 13.10 Suppose that a B+ -tree index on branch-city is available on relation branch, and that no other index is available. List different ways to handle the following selections that involve negation? a. σ¬(branch -city

Similar Documents

Free Essay

Netw 360 Ilab 2

...power can be measured in two ways: on the linear scale, by the number of watts that are being transmitted; and on a relative scale, by the number of decibels (dBs) instead of watts. Decibel milliwatt (dBm) is the logarithmic power ratio (in dB) of the measured power in milliwatts referenced to one milliwatt (mW). Notice that the reference point is specified as 1 mW = 0 dBm. 3’s and 10’s rules are shortcuts for estimating the increase or decrease of these power levels. In this lab, students will practice basic RF calculations, including · converting from mW to dBm; · converting from dBm to mW; and · estimating power levels using the 3’s and 10’s rules. Task 1: Converting between dBm and mW Applying the 3’s and 10’s rules, the relationship between dBm and mW is estimated as shown in the following (partial) table. 3’s rule|10’s rule| ……|……| 0.125 mW = -9 dBm|0.001 mW = -30 dBm| 0.25 mW = -6 dBm|0.01 mW = -20 dBm| 0.5 mW = -3 dBm|0.1 mW = -10 dBm| 1 mW = 0 dBm|1 mW = 0 dBm| 2 mW = 3 dBm|10 mW = 10 dBm| 4 mW = 6 dBm|100 mW = 20 dBm| 8 mW = 9 dBm|1,000 mW = 30 dBm| ……|……| Notice that as the mW value increases or decreased by the factor of 10, the dBm value increases and decrease by adding or subtracting 10. As the mW value doubles or halves, the corresponding dBm value increases and decrease by adding or...

Words: 894 - Pages: 4

Free Essay

Design Patterns

...by adapting its interface into a more common one. The adapter pattern translates one interface for a class into a compatible interface for a new class. An adapter allows the classes to work together when they normally could not because of their incompatible interfaces. The adapter also transforms data into an appropriate form. For example, if multiple Boolean values are stored as a single integer but the client requires a 'true'/'false', the adapter would extract the appropriate values from the integer. Another example would be transforming the format of a date for instance MM/DD/YYYY to DD/MM/YYYY or YYYY/MM/DD). The adapter design is about creating an intermediary abstraction that translates the old component to a new system. The Adapter pattern lets incompatible classes work with the interface of one class by converting it into the interface that is expected by the clients. For instance a socket wrench is a good example of an Adapter. A socket will attach to a wrench as long as the size of the drive is the same. A typical drive size in the US is 1/2” and 1/4”. There is no way a 1/2” drive on a wrench will fit in to a 1/4” drive socket unless you use an adapter. Using a 1/2” to 1/4” adapter will allow a 1/2” female connection to fit on the 1/2” drive on a wrench, and a 1/4” male connection will fit in the 1/4” drive socket. The main reason for this pattern is for a class that...

Words: 1139 - Pages: 5

Premium Essay

Cis 111

...1. What is the simplest SQL retrieval? The simplest versions of the most important SQL command are SELECT, FROM statement. Then if you need to limit the result you introduce the WHERE clause. In the WHERE clause you can use operators such as LIKE, AND, OR, EQUAL, BETWEEN and IN. 2. What is the purpose of the Where clause when using SELECT? The purpose of this clause is to be able to list any conditions that are to be applied to the data retrieved. 3. What are data types and why are they important? A data type is a classification identifying one of various types of data, they are important because assigning data types gives meaning to collections of information 4. Provide an example of the GROUP by clause, when would you use this clause? SELECT Salesperson, SUM(Revenue) AS ‘Total’, MIN(Revenue) AS ‘Smallest’, MAX(Revenue) AS ‘Largest’, AVG(Revenue) AS ‘Average’, COUNT(Revenue) AS ‘Number’ FROM Orders GROUP BY Salesperson You use this clause when you need to see the information in a certain order 5. What is an aggregate function (provide 4)? How are they used? An aggregate function is a function where the values of multiple rows are grouped together as input on certain criteria to form a single value of more significant meaning or measurement AVG() - Returns the average value (average) COUNT() - Returns the number of rows (count) FIRST() - Returns the first value LAST() - Returns the last value 6. Provide example using the COUNT()...

Words: 363 - Pages: 2

Free Essay

Cis247A Week 3

...using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace CIS247_Week3ilabrevised_JohnDoe //John Doe //CIS 247A Week 3 iLab //Employee Class Program { class Employee { private string firstName; private string lastName; private char gender; private int dependents; private double annualSalary; private double pay; public static int numEmployees = 0; public const string DEFAULT_FIRST = " not given"; public const string DEFAULT_LAST = " not given"; public const char DEFAULT_GENDER = 'U'; public const int DEFAULT_DEPENDENTS = 0; private const double DEFAULT_ANNUALSALARY = 20000; public Employee() { FirstName = DEFAULT_FIRST; LastName = DEFAULT_LAST; Gender = DEFAULT_GENDER; Dependents = DEFAULT_DEPENDENTS; AnnualSalary = DEFAULT_ANNUALSALARY; numEmployees++; } public Employee(string first, string last, char gen, int dep, double salary) { firstName = first; lastName = last; gender = gen; annualSalary = salary; numEmployees++; } public string FirstName { get { return firstName; } set {firstName = value;} } public string LastName { get { return lastName; } set {lastName = value;} } public char Gender { get { return gender; } set {gender = value;} } public int Dependents { get { return dependents; } set { dependents = value;} } public double AnnualSalary { get { return annualSalary; } set { if(value > 19999) ...

Words: 415 - Pages: 2

Free Essay

Computers

... nevertheless most importantly by my professor. Although, writing can be challenging when writing for professors or future employer or other authority in that category. Due to pressure of excelling , anxiety of doing passing/ failing or anticipation of the ending, for instance if a writing task is given by a supervisor or professor, the paper is not adequate. There is possibility that you can be written up, fired or receive an deteriorating grade . On the other hand, there is a affirmative side, That’s my target . Which will enable me to advance in all of my writing coursework in this class and future classes. In addition, I plan to use my writing skills , not only in the class room setting , but my professional life, instituting my writing ability through my resume, cover letter, or assigned writing task. I also will use writing in my personal life, Through reading more books and which is said to boost your writing skills. However, I take an slightly special approach when setting goals for my dissertations. The first step that take is writing down my ideas about the subject given. Next, I distribute those thoughts and organize them with the outline procedure. Proceeding, I design a first draft, which is...

Words: 328 - Pages: 2

Free Essay

Java Class Shape

...Shape class /** * This is a class that represent any shape. This is the superclass of all shapes. * @author yklam2 * */ public class Shape { private boolean canvas[][]; private int width; private int height; /** * Create an empty shape. */ public Shape() { this(0, 0); } /** * Create a shape with a specific width and height. * @param width The width of this shape. * @param height The height of this shape. */ protected Shape(int width, int height) { this.width = width; this.height = height; canvas = new boolean[height][width]; } /** * Set a pixel * @param row The row of the pixel. * @param column The column of the pixel. */ protected void setPixel(int row, int column) { if(row >=0 && row < height && column >=0 && column < width) canvas[row][column] = true; } /** * Clear a pixel * @param row The row of the pixel. * @param column The column of the pixel. */ protected void clearPixel(int row, int column) { if(row >=0 && row < height && column >=0 && column < width) canvas[row][column] = false; } /** * Get the area of this shape. Area is the number of pixel set in this * @return The area. */ public int getArea() { int area = 0; shape. for(boolean [] row: canvas) for(boolean pixel: row) if(pixel) ++area; } return area; /* (non-Javadoc) * @see java.lang.Object#toString() */ public String toString() { String drawing = ""; for(boolean [] row: canvas) { if(drawing.length() > 0) //...

Words: 704 - Pages: 3

Premium Essay

Classroom Discipline Andmanagement

...In a classroom setting, discipline and management are two key components for classroom success. The term classroom management is often used interchangeably with the term classroom discipline. However, the two ideas are very different in their application. Management and discipline are two halves of the same coin, they are intrinsicly connected to each other, but they have their own individual properties, with their own look and feel. Classroom management deals with how things in a class are done. Classroom management is the sole responsibility of the teacher. It encompasses all of the teacher’s interactions with students, classroom environment, rules and procedures, instructional strategies and development of engaging work. In a well managed classroom, the teacher implements policies and develops routines that stabilize and direct the flow of a class. Effective teachers manage their classes so that students spend their time more productively. Elements of classroom management vary. No two classes are alike. However the foundational elements a teacher takes into account before students ever set foot in the build can lend to better classroom management. Things such as classroom layout and organization.A neat and organized classroom tells your students you mean business and you expect them to keep the classroom organized as well. Deciding how to divide up classroom time is another important aspect to classroom management.Lunch, recess, breaks, down-time between lessons and activities...

Words: 1027 - Pages: 5

Free Essay

Violence Against Women

...Women My psychology class meets every Thursday morning. It is a small class of five students and one instructor. Being in such a small class was unsettling at first because I felt I could not be overlooked by the instructor. I have gotten accustomed to bigger classes where I would blend into the crowd and just be a name in the instructor’s book. Over the last three weeks, I have observed my classmates and my instructor and have learned a thing or two about them. I have also realized how being in a smaller class is actually much more pleasant than previously anticipated. Our classroom is fairly big considering the size of the class. There are eight tables with four chairs at each table. The walls are tasteless, showing only one poster advertising Bryant & Stratton’s impeccable ability to create the world’s best workforce. The teacher’s corner sits at the front of the room while the projector screen hangs on the left wall. Because this is a small class, this poses no problems but I can imagine the seating dilemma if the room were actually full while using the projector system. Mr. Streett is the instructor for this class, a recent graduate from Radford University with a Master’s of Art in Experimental Psychology. He speaks quickly repeating short sentences rephrased but implying the same meaning to help his students grasp the concept being taught. Though he seems to know his stuff, he comes to class unprepared, taking the first 30 minutes of class to make copies...

Words: 1052 - Pages: 5

Free Essay

Future Focus

...(FF) had been running a small, for-profit preschool program for young children between the ages of two and four for several decades. FF was one of several privately run programs in the suburban Boston area. For each of the three age groups (i.e., two-, three- and four- year olds), there were two classes per day for a total of six classes in the facility each day. The classes were held both in the morning and in the afternoon, five days a week between September and June; there were approximately 200 days (40 weeks), or 1,200 class meetings, per year. Only about one- third of FF's local competitors offered classes during the summer months. The morning classes ran from 9:00 a.m. to noon, and the afternoon meetings ran from 1:00 p.m. to 4:00 p.m. Lunch was not served in either class. However, each class served a snack to the children. Class size varied from nine to 15 students per class. Although there was a lot of pressure from parents to reduce class sizes, a recent article in an industry newsletter showed that, given current demographics, the market for such programs could increase by 10% a year for the next five years. The year before, a parent suggested that the school begin hosting birthday parties on the weekend. Since FF's three classrooms were empty during this time, it seemed like a good use of the space and could generate additional revenue. Over the past year, the school had managed to quickly build a sizable side business hosting birthday parties. Approximately...

Words: 431 - Pages: 2

Premium Essay

Java Class

...Java Class MIS 304 is not a class for everyone. Not just any student should take the class. This class is structured to assist students in learning how to program using the Java language. This class does not make a student an expert in the language of Java, but instead gives the student the basic fundamentals needed to have practical use of the language and gives them a solid foundation upon which they can build if they choose to do so. The material covered in the class is adequate. Java can be a complex language to learn, but in MIS 304 one is taught the basics and nothing too detailed or complicated. The resources that are given to the students are very good. I know that the Java book used for the class is one of the best reference materials on Java that is on the market today. The lab facilities and proctors are also great resources. The only problem I feel that exists is that students don’t take advantage of the resources they have available. Students hardly look through their book for answering questions they might have. Also students hardly even bring their books to the lab when doing programs. They sometimes look for proctors to fix their problems instead of fixing it themselves. I think it should be emphasized to students that the proctors are not their to do the programs for them, but to rather help them figure out what is going wrong in their programs. Also it should be emphasized that the book should be with them when working on programs so that if questions or...

Words: 2075 - Pages: 9

Free Essay

Lalla

...similar to a class, which can contain only constants, method signatures, and nested types. There are no method bodies. Interfaces cannot be instantiated—they can only be implemented by classes or extended by other interfaces. In Java, a class can inherit from only one class but it can implement more than one interface. | Superclass Instance Method | Superclass Static Method | Subclass Instance Method | Overrides | Generates a compile-time error | Subclass Static Method | Generates a compile-time error | Hides | An abstract class is a class that is declared abstract. Abstract classes cannot be instantiated, but they can be subclassed. It can contain abstract methods that did not have implemented. Subclasses then provide the implementations for the abstract methods. An abstract method is a method that is declared without an implementation (without braces, and followed by a semicolon), like this: Except for the Object class, a class has exactly one direct superclass. A class inherits fields and methods from all its superclasses, whether direct or indirect. A subclass can override methods that it inherits, or it can hide fields or methods that it inherits. (Note that hiding fields is generally bad programming practice.) The Object class is the top of the class hierarchy. All classes are descendants from this class and inherit methods from it. Useful methods inherited from Object include toString(), equals(), clone(), and getClass(). You can prevent a class from being...

Words: 328 - Pages: 2

Premium Essay

Arraylist, Hashmap, Queue Student Assignment

...util.ArrayList; public class Student { // Declare the variables private String name; private ArrayList homeworks; // Constructor with one argument public Student(String name) { this.name = name; this.homeworks = new ArrayList(); } // setter or mutator methods change the field values public void setName(String name) { this.name = name; } //Accessor or getter methods provide the field values public String getName() { return name; } public void addHomeworkGrade(int newGrade){ this.homeworks.add(newGrade); } //average homework score public double getComputeAverage(){ int total = 0; //loop through homeworks, add to total for(Integer grade : this.homeworks){ total += grade; } //calculate average double average = total / (double)this.homeworks.size(); return average; } //Override the toString method to return the string representation public String toString() { DecimalFormat pattern = new DecimalFormat("0.00"); return (getName() + "'s average grade is " + pattern.format(getComputeAverage())); } } ------------------------ import java.io.FileReader; import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.IOException; import java.util.HashMap; import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import java.util.Set; import java.util.StringTokenizer; public class Test { public static void...

Words: 366 - Pages: 2

Free Essay

Reflection Paper

...Reflection Paper In our GEP class we discussion many different topics about our first college experience. We were given a list of questions to discuss and one of the main questions we discussed was how different college is from high school. We also had a discussion on how we were all nervous about going to college. Knowing everyone else was just as scared as me made me feel a lot better and I didn’t doubt myself as much because I realized I wasn’t the only one going through those feelings, that it was normal. We all expressed our feelings on what we missed most about home and we love most about home. I felt like we all missed the same things and enjoyed the same things about college. Hearing them say they missed their parents, and animals just like made me feel like we all had a connection. That it’s normal for us to feel that way and it doesn’t mean we can’t do it. In class we also talked about our classes, which ones we like and which ones we don’t. Other students in our class gave me some helpful tips like being about to download Microsoft word for free for our campus help desk. Our teacher also made us feel like we were all the same and could express anything we wanted. He also gave us some helpful tips from his first college year. One topic we talked about that really invoked my feelings was if our parents helped us apply to college. My parents did not go to any college but they tried to help me as much as they could. I realized that some students in our class didn’t have that support...

Words: 613 - Pages: 3

Free Essay

Helping Hand

...Package ‘quantmod’ July 24, 2015 Type Package Title Quantitative Financial Modelling Framework Version 0.4-5 Date 2015-07-23 Depends xts(>= 0.9-0), zoo, TTR(>= 0.2), methods Suggests DBI,RMySQL,RSQLite,timeSeries,its,XML,downloader Description Specify, build, trade, and analyse quantitative financial trading strategies. LazyLoad yes License GPL-3 URL http://www.quantmod.com https://github.com/joshuaulrich/quantmod BugReports https://github.com/joshuaulrich/quantmod/issues NeedsCompilation yes Author Jeffrey A. Ryan [aut, cph], Joshua M. Ulrich [cre, ctb], Wouter Thielen [ctb] Maintainer Joshua M. Ulrich Repository CRAN Date/Publication 2015-07-24 21:10:42 R topics documented: quantmod-package addADX . . . . . . addBBands . . . . addCCI . . . . . . addExpiry . . . . . addMA . . . . . . addMACD . . . . . addROC . . . . . . addRSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...

Words: 4206 - Pages: 17

Free Essay

Java - Download and Study the Code Provided

...HELPIDO.COM Follow this link to get the tutorial http://helpido.com/download-and-study-the-code-provided-in-the-bluej-project/ Follow this link to get the tutorial http://helpido.com/download-and-study-the-code-provided-in-the-bluej-project/ Download and study the code provided in the BlueJ project roman_numerals_buggy.zip. Rename this BlueJ project to roman_numeral_soln (this is the BlueJ project you will be submitting). You can rename the project by renaming the folder from roman_numerals_buggy to roman_numeral_soln after extracting the zip file. The purpose of this code is to convert Arabic numerals into Roman numerals. Make an instance of RomanNumerals and invoke the method toRoman(int n). Enter a number in the Arabic notation and it will convert it to a Roman numeral. For example “17” will be converted to “XVII”.You will notice a test suite that we provide with the code. Run the test suite by right-clicking on RomanNumeralsTest and choosing Test All as shown in Figure 6.3 of the book. Alternatively, you can click on the Run Tests button as shown in Figure 6.2 of the book, if you have enabled the ‘Show unit testing tools’ preference. To enable it, go to Tools > Preferences > Miscellaneous, and select ‘Show unit testing tools’. You will notice a total of eight tests of which two fail. Your first task in this assignment is to study the given code, identify why the two tests fail, and correct the code. On studying the code further, you will...

Words: 568 - Pages: 3