`
`
`
`ABOUT THE BOOK
`
`
`
`This book lives up to its title by describing the fundamental concepts behind
`database systems. Database System Concepts shows how to solve many at
`
`the problems encountered In designing and using a database system.
`Readers are introduced to the entity/relationship and relational models lirst.
`
`totlowed by the network and hierarchical models. Several chapters are
`
`devoted to the physical organization at databases. index techniques. and
`
`query processing. and the latter pan ot the book delves into advanced areas.
`including coverage at distributed databases. database security. and anifrcial
`
`intelligence.
`
`ABOUT THE AUTHORS
`
`Henry F. Korth is Assistant Protessor at Computer Sciences at the
`University oi Texas at Austin. Prior to joining the University of Texas lawity,
`Dr. Korth was a start member of the IBM T..I. Watson Research
`Center in New York. where he was involved in the design and
`Implementation of a distributed office automation system. His writings on
`database systems have appeared in several ACM and IEEE publications.
`Abraham Silberschelz is Prolassor at Computer Sciences at the University
`oi Texas at Austin. where he specializes in the area at concurrent
`processing. His research Interests include operating systems. database
`systemsfidistnbo‘teii'systems, and programing languages. 0r. Silberschalz
`is the header oi the First DavidBruton J_r. Centennial Prolessorship in
`Computer Sciences. and coauthor oi the best—selling Operating System
`Concepts textbook.
`
`sissr AVAiLABLE COPY
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ileana-Hut Book Company
`
`Serving the Need for Knowledge‘
`
`122i Mama at the Americas
`ISBN U-D?-UH‘i?SE-?
`NuYorlt.N.V.10020
`
`
`
`
`

`

`~
`
`.
`.
`¢
`.
`.
`.
`.
`.
`.
`.
`.,
`,~ ,...,.-...,.
`;'~:>.'. _., 1".f11".'.- .,
`-'...~- my: -,_.
`~5'--1:.-,£a..€
`-.<5.21¢.’-.=-Eu'..:15.~.- h«mu-.33{m»;3-$:2.=;é.-m:d_.--'u1"::m’;m§au!zz._:'a--.'u==
`
`‘
`
`‘
`
`‘
`
`hmimm‘fi’l H
`
`l
`
`was
`
`v I3
`
`:
`i!-
`
`-:;nr.----,.....,1........
`W.»~9¢4~
`mega-owl:
`Ems..m53&§:e§:&.
`5i
`
`gland Bogoté Hamburg
`
`‘I
`.i
`23
`z!
`i
`i}
`
`..se-...0»,-
`
`'
`.;§
`New York SQLou
`Londpir
`Panatfi'é
`
`Paris
`
`.
`
`mpany
`
`

`

`
`
`
`
`
`
`
`McCraw—Hill Advanced Computer Science Series
`Davis and tent: Knowledge-Based Systems in Artificial Intelligence
`.
`Kogge: The Architecture of I’ipelined Compute-s
`Lindsay, Buchanan. Rigenbaum, and lederberg: Applications of Artificial Intelligence
`for Organic Chemistry: The Dendral Projeét
`Nilsson: Problem-Solving Methods in Artificial Intelligence
`Wulf, Levin, and Harbison: HYDRA/Cmmp: An uperimental Computer System
`
`
`
`11
`
`In memory
`
`.~
`
`
`
`.
`
`
`«mags-s"_-_.‘-‘v‘3..
`
`—NIH—“wax
`
`‘'-—-=.'5_—-~A:-H“-
`umends-
`
`
`DATABASE SYSTEM CONCEPIS .
`
`
`*W
`Copyright 9 1986 by McGraw-Hill, Inc. All rights reserved. Printed in the United
`'
`
`
`sum ot America. Emept or permitted under the United Sutes Copyright Act ot
`.
`1976 no part at this publication may be reproduced or distributed In any form or
`‘
`
`
`r—'ammwam' ISBN OeUT-DHH752-7
`
`by any means, or stored in a data base or rattle-val system, without the prim written
`permission ol the publisher.
`
`
`67890 DODO 89
`-.—-—.'
`
`
`
`The editor was Kaye Face; the production supervisor was Joe Campanella; the
`cover was designed by Anne Canevari Green. Project supervision was done by
`Caliber Design Planning, Inc.
`
`
`
`
`
`

`

` 44
`
`
`
`Entity-Relationship Model
`
`Chapter 2
`
`2.7 Every weak entity set can be converted to a strong entity set by
`simply adding appropriate attributes. Why, then, do we have weak
`entities?
`
`2.8 Suppose that you design an E-R diagram in which the same entity
`set appears several times. Why is this a bad practice that should be
`avoided whenever possible?
`
`2.9 When designing an ER diagram for a particular enterprise, there
`exists several alternative designs.
`
`should you consider
`criteria
`a. What
`appropriate choice?
`
`in deciding on
`
`the
`
`b. Come up with several alternative E-R diagrams to represent an
`enterprise. List
`the merits of each alternative and argue in
`favor of one of the alternatives.
`
`2.10 Explain the difference between generalization and specialization.
`
`Bibliographic Notes
`The entity relationship data model was introduced by Chen [1976].
`Discussions concerning the applicability of the E-R approach to database
`design are offered by Chen [1977], Sakai {1980], and Ng [1981]. Modeling
`techniques based on the E-R approach are covered by Schiffner and
`Scheuermann [1979], Lusk et al. [1980], Casanova [1984], and Wang [1984].
`Various data manipulation languages for the E-R model have been
`proposed. These include CABLE [Shoshani 1978], GERM [Benneworth et
`al. 1981], and GORDAS [ElMasri and Wiederhold 1983]. A graphical query
`Eggplage for the E—R database was proposed by Zhang and Mendelzon
`The concepts of generalization, specialization, and aggregation were
`introduced by Smith and Smith [1977]. benzerini and Santucd [1983] have
`used these concepts in defining cardinality constraints in the E-R model.
`Basic textbook discussions are offered by Tsicluitzis and Lochovsky
`[1982] and by Chen [1983].
`
` ‘u‘l‘j
`
`
` -r—A—:,.fl—-=-==~.1m,p.“it???“f—c-v
`
`3
`
`Relational Model
`
`
`
`~,.has-v.3.1::
`
`
`
`
`From a historical perspective, the relational data model is relatively new.
`
`The first database systems were based on either the hierarchical model (see
`Chapter 5) or the network model (see Chapter 4). Those two older models
`
`are tied more closely to the underlying implementation of the database
`than is the relational model.
`
`The relational data model represents the database as a collection of
`tables. Although tables are a simple,
`intuitive notion,
`there is a direct
`correspondence between the concept of a table and the mathematical
`concept of a relation.
`In the years following the introduction of the relational model, a
`substantial
`theory has developed for relational databases. This theory
`assists in the design of relational databases and in the efficient processing
`of user requests for information from the database. We shall study this
`theory in Chapter 6, after we have introduced all the major data models.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`3.1 Structure of Relational Databases
`A relational database consists of a collection of tables, each of which is
`assigned a unique name. Each table has a structure similar
`to that
`presented in Chapter 2, where we represented E-R databases by tables. A
`row in a table represents a relationship among a set of values. Since a table
`is a collection of such relationships,
`there is a close correspondence
`between the concept of table and the mathematical concept of relation, from
`which the relational data model
`takes its name.
`in what follows, we
`introduce the concept of relation.
`In this chapter, we shall be using a number of different relations to
`
`illustrate the various concepts underlying the relational data model. These
`
`relations represent part of a banking enterprise. They differ slightly from
`the tables
`that were used in Chapter 2 in. order
`to simplify our
`
`presentation. We shall discuss appropriate relational structures in great
`detail in Chapter 6.
`Consider the deposit table of Figure 3.1. it has four attributes: brunch-
`
`rmme, account-number, customer-name, balance. For each attribute, there is a
`
`
`set of permitted values, called the domain of
`that attribute. For
`the
`
`
`\
`
`
`
`
`

`

`
`
`~;-'4323;.
`
`“are?-34it.
`
`\Z.
`
`....,.,.
`
`46
`
`Relational Model
`
`Chapter 3
`
`Section 3.1
`
`\
`
`Structure of Relational Databases
`
`47
`
`
`
`_——m
`Downtown
`500
`Mianus
`700
`Perryridge
`400
`Round Hill
`Perryridge
`Redwood
`
`Bri . hton
`
`,
`
`Figure 3.1 The deposit relation.
`
`the domain would be the set of all
`attribute branch—name, for example,
`branch names. Let Dl denote this set and let 02 denote the set of all
`account-numbers, 03 the set of all customer names, and D4 the set of all
`balances. As we saw in Chapter 2, any row of deposit must consist of a 4-
`tuple (01, v2, 03, 114) where Ul
`is a branch name (that is, ”I is in domain
`01), 02 is an account number (that is, 122 is in domain Dz), v; is a customer
`name (that is, 113 is in domain D3), and v‘ is a balance (that is,
`214 is in
`domain 0,). In general, deposit will contain only a subset of the set of all
`possible rows. Therefore deposit is a subset of:
`
`Mathematicians define a relation to be a subset of a cartesian product of
`a list of domains. This corresponds almost exactly with our definition of
`table. The only difference is that we have assigned names to attributes,
`while mathematicians rely on numeric “names," using the integer l to
`denote the attribute whose domain appears first in the list of domains, 2
`for the attribute whose domain appears second, etc. Because tables are
`essentially relations, we shall use the mathematical terms relation and tuple
`in place of the terms table and raw.
`In the deposit relation of Figure 3.1, there are seven tuples. Let the tuple
`variable I refer to the first
`tuple of the relation. We use the notation
`t[branch-name] to denote the value of t on the branch-name attribute. Thus,
`t[branch-name| = “Downtown". Similarly,
`t[account-number] denotes the
`value of t on the account-number attribute, etc. Alternatively, we may write
`
`t[2]
`ill] to denote the value of‘tuple t on the first attribute (branch-name),
`for account-number, etc. Since a relation is a set of tuples, we use the
`mathematical notation of l a r to denote that tuple t is in relation r.
`When we talk about a database, we must differentiate between the
`database schema, that is, the logical design of the database, and a database
`instance, which‘is the data in the database at a given instant in time.
`The concept of a relation scheme corresponds to the programming
`language notiori of type definition. A variable of a given type has a
`particular value at a given instant
`in time. Thus,
`a variable in
`programming languages corresponds to the concept of an instance of a
`relation.
`'
`It is convenient to give a name to a relation scheme, just as we give
`names to type definitions in programming languages. We adopt
`the
`convention of using lowercase names for relations and names beginning
`with an uppercase letter for relation schemes. Following this notation, we
`use Deposit-scheme to denote the relation scheme for relation deposit. Thus,
`
`Deposit—scheme = (branch-name, account-number, customer-name, balance)
`
`In general, a relation scheme is a list of attributes and their corresponding
`domains. We denote the fact that deposit is a relation on scheme Deposit by
`
`deposit (Deposit-scheme)
`
`We shall not, in general, be concerned about the precise definition of
`the domain of each attribute until we discuss file systems in Chapter 7.
`However, when we do wish to define our domains, we use the notation
`
`(branch-name : string, account-number : integer,
`customer-name : string, balance : integer)
`
`to define the relation scheme for the relation deposit.
`As another example, consider the customer relation of Figure 3.2. The
`scheme for that relation is
`'
`
`Customer-scheme = (customer-name, street, customer-city)
`
`Note that the attribute customer-name appears in both relation schemes.
`This is not a coincidence. Rather, the use of common attributes‘in relation
`schemes is one way of relating tuples of distinct relations. For example,
`suppose we wish to find the cities where depositors of the Perryridge
`branch live. We would look first at the deposit relation to find all depositors
`of the Perryridge branch. Then, for each such customer, we look in the
`customer relation to find the city he or she lives in. Using the terminology
`
`Hr...
`
`an>i...5.-
`
`a(:2;
`
`
`
`
`
`

`

`48
`
`Relational Model
`
`Chapter 3
`
`Section 3.1
`
`\
`
`Structure of Relational Databases
`
`49
`
`For the purpose of this'chapter. we assume that the relation schemes
`for our banking enterprise are as follows:
`
`Branch-scheme = (branch—name, assets, branch-city)
`Customer-scheme = (customemmnie, street, custonm-city)
`Deposit—scheme = (branch-name, account-number, customer-name, balance)
`' Borrow-scheme = (branch-name, loan-number, customer-name, amount)
`
`We have already seen an example of a deposit relation and a customer
`relation. Figure 3.3 shows a sample barrow (Borrow-scheme) relation.
`The notion of a superkey, candidate key, and primary key, as discussed in
`Chapter 2,
`is applicable also to the relational model. For example,
`in
`Branch—scheme,
`{branch-name}
`and
`(branch-name,
`branch-city} are both
`superkeys.
`{branch-name, branclr‘city} is not a candidate key because
`{branch—name} (_: {branch-name, branch-city) and {branch-name} itself is a
`superkey.
`{branch-name}, however,
`is a candidate key, which for our
`purpose will also serve as a primary key. The attribute branch-city is not a
`superkey since two branches in the same city may have different names
`(and different asset figures). The primary key for the customer~scheme is
`customer-name. We are not using the social-security number, as was done in
`Chapter 2,
`in order to have smaller relation schemes in our running
`example of a bank database. We expect that in a real world database the
`social—security attribute would serve as a primary key.
`Let R be a relation scheme. If we say that a subset K of R is a superkey
`for R, we are restricting consideration to relations r(R) in which no two
`distinct tuples have the same values on all attributes in K. That
`is,
`if
`tl and (2 are in rand tl 1H2, then t1[KJ $121K].
`
`
`
`.“q-q
`
`customer-name m customer~cit
`Jones
`Harrison
`Smith
`Rye
`Hayes
`Harrison
`Curry
`Rye
`Pittsfield
`Lindsay
`Turner
`Stamford
`Williams
`Princeton
`Adams
`Pittslield
`Johnson
`Palo Alto
`Glenn
`Woodside
`Brooks
`Brooklyn
`Green
`
`Stamford
`
`Figure 3.2 The customer relation.
`
`of the entity—relationship model, We would say that the attribute customer-
`name represents the same entity set in both relations.
`It would appear that, for our banking example, we could have just one
`relation scheme rather than several. That is,
`it may be easier for a user to
`think in terms of one relation scheme rather than-several. Suppose we
`used only one relation for our example, with scheme
`
`Account~info—scheme = (branch-name, account-number, customer-name,
`balance, street, customer-city)
`
`Observe that if a customer has several accounts, we must list her or his
`address once for each account. That is, we must repeat certain information
`several times. This repetition is wasteful and was avoided by our use of
`two relations.
`[f a customer has one or more accounts, but has not
`provided an address, we cannot construct a tuple on Account-info-sdreme,
`since the values for the street and customer-city are not known. To represent
`incomplete tuples, we must use null values. Thus, in the above example,
`the values for street and customer-city must be null. By using two relations,
`one on Customer-scheme and one on Deposit—scheme, we can represent
`customers whose address is unknown, without using null valu s. We
`simply use a tuple on Deposit-scheme to represent the information ab ut the
`account, and create no tuple on Customer-scheme until
`the address
`information becomes available. In Chapter 6, we shall study criteria to help
`us decide when one set of relation schemes is better than another. For
`now, we shall assume the relation schemes are given.
`
`,.-.-.'-om.
`
`'
`
`Am.A.~3-
`
`a.
`
`-Mists-
`
`
`
`-sun-tam:Maw.
`
`
`
`
`
`
`
`
`
`
`
`17
`
`
`
`
`
`
`
`branch-name
`customer-name m
`Downtown
`Jones
`1000
`Redwood
`Smith
`2000
`
`
`Perryridge
`Hayes
`
`Downtown
`Jackson
`Mianus
`Curry
`
`Round Hill
`Turner
`Pownal
`Williams
`
`
`North Town
`Adams
`
`Downtown
`Johnson
`
`
`Perryridge
`Glenn
`
`Brooks
` Brighton
`
`
`Figure 3.3 The barrow relation.
`
`

`

`
`SO
`Relational Model
`Chapter 3
`\
`
`
`Section 3.2
`'
`Formal Query Languages
`51
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`following the 0. Thus, to select those tuples of the borrow relation where
`the branch is “Perryr-idge," we write
`
`"brandivname. = “Pctryridge” (W)
`.
`.
`‘
`'l
`.
`If the borrow relation Is as shown in Figure 3.3, then the relation that
`results from the above query is as shown in Figure 3.4. We may find all
`tuples in which the amount borrowed is more than $1200 by writing
`
`"amount > I200 (borrow)
`
`it, <, S, >, 2 in the
`In general, we allow comparisons using =,
`selection predicate. Furthermore, several predicates may be combined into
`a larger predicate using the connectives and (A) and or (v). Thus, to find
`those tuples pertaining to loans of more than $1200 made by the
`Perryn'dge branch, we write
`
`“branch-name = “Perryridgc” A amount > 1200 (borrow)
`
`The selection predicate may include comparisons between two attributes.
`To illustrate this, we consider the relation scheme
`
`Client-scheme = (customer-name, employee-name)
`
`indicating that the employee is the "personal banker" of the customer. The
`relation client (Client-scheme) is shown in Figure 3.5. We may find all those
`customers who have the same name as their personal banker by writing.
`
`o’custarrrer‘rmrnc a employee-name (dim!)
`
`If the client relation is as given in Figure 3.5, the answer is the relation
`shown in Figure 3.6.
`In the above example, we obtained 2-. relation (Figure 3.6) on (customer-
`name, employee-name) in which “customer-name] = “employee-name] for all
`tuples t. It seems redundant to list the person's name twice. We would .
`
`
`
`
`
`3.2 Formal Query Languages
`
`A query language is a language in which a user requests information from
`the database. These languages are typically higher-level languages than
`standard programming languages. Query languages can be mtegorized as
`being either procedural or nonproceduml. In a procedural language, the user
`instructs the system to perform a sequence of operations on the database
`to compute the desired result.
`In a nonprocedural
`language,
`the user
`describes the information desired without giving a specific procedure for
`obtaining that information.
`Most commercial relational database systems offer a query language
`includes elements of both the procedural and the nonprocedural
`that
`approaches. We shall study several commercial
`languages later in this
`chapter. First, we look at two "pure” languages: one procedural and one
`nonprocedural. These “pur'e” languages lack the "syntactic sugar" of
`commercial languages, but they illustrate the fundamental techniques for
`extracting data from the database.
`'
`
`3.2.1 The Relational Algebra
`
`The relational algebra is a procedural query language. There are five
`fundamental operations in the relational algebra. These operations are:
`select,
`project, mrtesian-product, union, and set—difference. All of
`these
`operations produce a new relation as their result.
`introduce
`In addition to the five fundamental operations, we shall
`several other operations, namely, set intersection, theta join, natural join, and
`division. These operations will be defined in terms of the fundamental
`operations.
`
`Fundamental operations
`
`The select and project operations are called unary operations, since they
`operate on one relation. The-other three relations operate on pairs of
`relations and are, therefore, called binary operations.
`The select operation selects tuples that satisfy a given predicate. We use
`the lowercase Greek letter sigma (a) to denote selection. The predicate
`appears as a subscript to 0'. The argument relation is given in parentheses
`
`
`
`
`
`
`
`
`
`
`
`
`—m_m
`
`
`
`Perryridge
`15
`Hayes
`1500
`Perryridge
`25
`Glenn
`2500
` Figure 3.4 Result of ”branch-mime = “Perryridge
`
`
`
`.. (borrow).
`
`Figure 3.5 The client relation.
`
`
`
`

`

`52
`
`Relational Model
`
`Chapter 3
`
`I
`
`.
`
`SCCHOH 3-2
`
`_
`client.
`C“5’°’"”'"""‘
`
`;
`
`'
`”I'm"
`em '1“ ee-namc
`
`Formal Query Languages
`
`53
`
`
`
`-
`
`i
`E
`
`;
`3
`
`i
`
`;
`.3
`:1
`E
`
`1
`
`prefer a one attribute relation on (customer-name) which lists all those who
`have the same name as their personal banker. The project operation allows
`us to produce this relation. The project operation is a unary operation that
`copies its argument relation, with certain columns left out. Since a relation
`is a set. any duplicate rows are eliminated. Projection is denoted by the
`Greek letter pi (II). We list those attributes that we wish to appear in the
`
`result as a subscript to n. The argument relation follows It in parentheses.
`
`Suppose we want a relation showing customers and the branches from
`which they borrow, but do not care about the amount of the loan, nor the
`loan number. We may write
`
`"brand-want, customer-name (borrow)
`Let us revisit the query “Find those customers who have the same
`name as their personal banker." We write
`
`‘
`
`"customer-name (”customer-name = emplacement-“mm”
`
`Notice that instead of giving the name of a relation as the argument of the
`projection operation, we give an expression that evaluates to a relation.
`The operations we have discussed up to this point allow us to extract
`information from only one relation at at time. We have not yet been able to
`combine information from several relations. One operation that allows us
`to do that is the cartesian product operation, denoted by a cross (x). This
`operation is a binary operation. We shall use infix notation for binary
`operations and, thus, write the cartesiah product of relations rl and r2 as
`1' X r2. We saw the definition of Cartesian product earlier in this chapter
`(recall that a relation is defined to be a subset of a cartesian product of a
`set of domains). From that definition we should already have some
`intuition about
`the definition of
`the relational algebra operation X.
`However, we face the problem of choosing the attribute names for the
`relation that results from a Cartesian product.
`Suppose we want to find all clients of bank employee johnson, as well
`as the dties in which the clients live. We need the information in both the
`client relation and.the customer relation in order to do so. Figure 3.7 shows
`the relation r = client x customer. The relation scheme for I 15
`
`.
`
`_m
`—-mai-
`figure 3'6 new" of"alumna-Mme = “Plow-MW (Chem)
`
`Rye
`Harrison
`
`Rye
`
`Pittsfield
`Stamford
`Princeton
`Pittsfield
`P310 Alto
`Sand Hill Woodside
`Brooklyn
`Senator
`Walnut
`Stamford
`Main
`Harrison
`North
`Rye .
`Main
`Hamson
`North
`Rye
`Park
`““556“
`Putnam
`Stamford
`Nassau
`Princeton
`Spnng
`“"558“
`_
`Alma
`P310 Alto
`Sand "'11 Woodside
`Senator
`Brooklyn
`nalnut
`Stamford
`N33]
`garrison '
`Main
`ultimo
`North
`R e
`n
`Park
`“£55 ld
`Putnam
`5' mterd
`Nassau
`pé a;
`5' fin
`“it; 1‘3“
`Arlmag
`[’an like
`Sand Hill Woodside
`Senator
`Brooklyn
`Walnut
`Stamford
`
`_
`
`'
`
`-
`
`,
`
`.
`
`.
`_
`Williams
`Adams
`Johnson
`Glenn
`Brooks
`fife“
`Smiet:
`Hayes
`Cu
`Uni-(3’3
`Tumery
`Williams
`Adams
`Iohnson
`Glenn
`Brooks
`Green
`
`-
`
`{gfifiion
`Johnson
`Johnson
`Johnson
`Johnson
`Johnson
`Johnson
`Johnson
`Johnson
`Johnson
`Johnson
`lohnson
`
`Figure 3.7 Resultofclient x customer.
`
`.
`
`l
`l
`
`l
`
`[.{Ii
`
`I“:
`it'll
`I
`.“j,
`i'jll
`Ill];
`fl;
`[1
`
`’ 91
`
`{'11
`’
`
`l'
`
`,
`
`I
`1
`l
`l
`
`_
`
`‘
`‘
`
`;
`i
`l
`l
`'
`'
`;
`‘1
`V'
`j
`‘
`;
`'
`i
`3
`ill
`f l
`
`ll'
`.
`I
`;
`l,
`i
`3
`,
`.» i
`2
`I
`2
`t
`l
`‘
`i
`‘
`l
`gl
`
`‘,
`
`l
`
`i
`‘
`
`v
`j
`i
`”'1
`1'1
`‘j
`§=
`.
`I.
`
`,7
`/
`
`7.
`
`
`
`El
`
`}
`
`

`

`1g:
`
`
`
`
`
`
`
`
`
`54
`
`Relational Model
`
`Chapter 3
`
`Section 3.2
`
`‘
`
`Formal Query Languages
`
`55
`
`new
`
`ma-"i
`.t‘h-‘grurflll..
`
`ms..»..a».
`
`(clientrustomtrmnme, client.employee—name, customerxuslomer-nnme
`customerslrcet, customer.custonwr-city)
`
`That is, we simply list all the attributes of both relations, and attach
`the name of the relation from which the attribute originally came. We need
`to attach the relation name to distinguish clicnt.customer-name trom
`customer.customer—name.
`Now that we know the relation scheme for r = client x customer, what
`tuples appear in r? As you may have suspected; we construct a tuple of I
`out of each possible pair of tuples: one from the client relation and one
`from the customer relation. Thus r is a large relation, as can be seen from
`Figure 3.7.
`Assume we have n, tuples in client and "2 tuples in customer. Then
`there are nln2 ways of choosing a pair of tuples: one tuple from each
`relation, so there are "1"2 tuples in r. In particular, note that it may be the
`case for some tuples t in r that t[cIient.custorner-name] # l[customer.custamer—
`name].
`then rl x r2 is a
`if we have relations rl(Rl) and r2(R2),
`in general,
`relation whose scheme is the concatenation of RI and R2. Relation R
`contains all tuples t {or which there is a tuple il
`in 'l' and t2 in r2 for
`which rum = MN and t[R21 = tlezl.
`,
`Returning to the query “Find all clients of Johnson and the city in
`which they live," we consider the relation r = client x customer. If we write
`
`0clientemployee-mm - “lohnson’ (client x customer)
`
`then the result relation is as shown in Figure 3.8. We have a relation
`pertaining only to employee Johnson. However, the customer.customer—name
`column may contain customers of employees other than Johnson (if you
`don’t see why, look at the definition of cartesian product again). Note that
`the client.custonrer‘narne column contains only customers of Johnson. Since
`the cartesian product operation associates every tuple of customer with every
`tuple of client, we know that some tuple in client x customer has the
`address of, the employee‘s customer. This occurs in those cases where it
`happens that client.customer-name = customer.customer—name. So if we write
`
`"clientmstomer-mm: = customer.custmner-name
`
`("clientmployee-namz = “Johnson" (client x customer»
`\
`we get only those tuples of client x customer that:
`o Pertain to Johnson.
`
`0 Have the street and city of the customer of Johnson.
`
`
`
`
`customer.
`customer.
`customer.
`client.
`client.
`
`
`
`
`customer-name
`emlo ce-mmic
`customer-name
`street
`customercil
`
`Main
`Han'ison
`Johnson
`‘Jones
`M
`
`Johnson
`Smith
`North
`Rye
`
`
`
`
`
`Johnson
`Hayes
`Main
`Harrison
`
`
`Johnson
`Curry
`North
`Rye
`
`
`
`
`
`Johnson
`Lindsay
`Park
`Pittsfield
`
`
`
`
`
`Johnson
`Turner
`Putnam
`Stamford
`
`
`
`
`
`Johnson
`Williams
`Nassau
`Princeton
`
`
`
`
`
`Johnson
`Adams
`Spring
`Pittsfield
`
`
`
`
`
`
`Johnson
`Johnson
`Alma
`Palo Alto
`
`Sand Hill Woodside
`Johnson
`Glenn '
`
`
`
`
`
`
`
`Johnson
`Brooks
`Senator
`Brooklyn
`
`
`
`Johnson
`Green
`Walnut
`Stamford
`
`
`Johnson
`Jones
`Main
`Harrison
`
`
`
`
`
`
`
`
`Johnson
`Smith
`North
`Rye
`
`
`Johnson
`Hayes
`Main
`Harrison
`
`
`
`Johnson
`Curry
`North
`Rye
`
`
`
`
`
`Johnson
`Lindsay
`Park
`Pittsfield
`
`
`
`
`
`Johnson
`Turner
`Putnam
`Stamford
`
`
`
`
`
`Johnson
`Williams
`Nassau
`Princeton
`
`
`
`
`Johnson
`Adams
`Spring
`Pittsfield
`
`
`
`
`
`Johnson
`Johnson
`Alma
`Palo Alto
`
`
`Sand Hill Woodside
`Johnson
`Glenn
`
`
`
`
`
`
`
`Brooks
`Senator
`Johnson
`Brooklyn
`
`
`
`Walnut Stamford
`Green
`
`Johnson
`
`
`
`Figure 3.8 Result of acthLemployec-name = "Johnson" (client x customer).
`
`Finally, since we want only customer-name and customer-city, we do a
`projection
`
`ncilentxustamer-name. customa.custamtr-cily
`(“clientxustamer-Mme = customa.customer~mme
`(adienl.employee-name =- “Johnson"
`(client x mstnmer)»
`
`'Ihe result of this expression is the correct answer to our query.
`Let us now consider a query that might be posed by a bank’s
`advertising department: “Find all customers of the Perryridge branch."
`That is, find everyone who has a loan, an account, or both. To answer. this
`
`
`
`
`
`

`

`
` query, we need the information in the borrow relation (Figure 3.3) and the
`
`2. megomains of the ith attribute of r and the ith attribute of 5 must be
`me.
`
`
`l]
`.
`_
`‘
`(a
`= ..
`.. (borrow))
`Penyndge
`brand! name
`customer mm:
`
` We know also how to find all customers with an account at the Perryn'dge
`branch:
`
`
`
`
`deposit relation (Figure 3.1). We know how to find all customers with a
`loan at the Perryridge branch:
`
`.
`
`a:
`
`“customer-name (“brunch-name = “‘Perryridgc" (deposim
`
`The set-difference operator, denoted by -, allows us to find tuples that
`are in one relation, but not'in another. The expression r - 5
`results in a
`relation containing those tuples infr but not in s .
`We can find all customers of the Perryridge branch who have an
`account there but do not have a loan there by writing:
`
`....a
`
`"customer-Mme (”Mandi-Mme = "Pcrryridge" (deposfln
`—
`customer-name ("brandy-name = "Perryridge" (barman)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`56
`
`Relational Model
`
`Chapter 3
`
`l'
`
`mu” 3'2
`
`‘
`‘
`
`F°m=1 Qusry Languages
`
`57
`
`
`
`
`
`
`
`
`
`
`
`is, all
`To answer the query, we need the union of these two sets, that
`customers appearing in either or both of the two relations. This is
`accomplished by the binary operation union, denoted, as in set theory, by
`U. So the expression the advertising department needs in our example is
`llcummmme (omndpmm = “Pctryridge” (borrow))
`.
`U "customer-name (chandbmm = "Pcrryridge" «4,05,,»
`
`-
`
`’
`
`\ m
`
`m
`mm
`
`Figure 3.9 Names of all customers of the Perryridge branch.
`
`Figure 3'10 Customers with only an account 3‘ the Perryridge branch.
`
`The result relation for this query appears in Figure 3.10.
`Formal definition of the relational algebra
`
`Tpe five operators we have justseen allow us to give a complete definition
`0 an expressron in the relational algebra. A basic expression in the
`
`
`
`
`relational algebra consists of either one of the following:
`,
`.
` The result relation tor this query appears in Figure 3.9. Notice that
`
`. A relation m the database.
`there are three tuples in the result even though the Perryridge branch has
`
`
`o Aconstant relation.
`two borrowers and two depositors. This is due to the fact that Hayes is
`both a borrower and a depositor of the Perryridge branch. Since relations
`
`
`
`
`A general expression in the relational algebra is constructed out of smaller
`are sets, duplicate values are eliminated.
`subexpressions. Let EI and 52 be relational algebra expressions Then
`Observe that, in our example, we took the union of two sets, both of
`
`
`'
`’
`which consisted of customer-name values. In general, we must ensure that
`
`
`0 E U E
`unions are taken between compatible relations. For example,
`it would not
`2
`I
`make sense to take the union of the borrow relation and the customer
`
`
`0 El - £2
`relation. The former is a relation of four attributes and the latter of three.
`
`
`. E x E
`Furthermore, consider a union of a set of customer names and a set of
`I
`2
`cities. Such a union would not make sense in most situations. Therefore,
`
`
`. ofiEI): where [7 is_a predicate on attributes on E.
`:31; umon operation r U s to be legal, we require that two conditions
`
`
`0 II E ), where S is a list cons'stin
`t
`‘
`'
`ins-15"
`l '
`g 0 some 0‘ *he attributes appearing
`1. The relations r and 5 must be of the same arity. That is, they must
`
`
`have the same number of attributes.
` are all relational algebra expressions.
`
`
`
`
`
`
`
`

`

`--5Earn
`
`58
`
`Relational Model
`
`I
`
`Chapter 3
`
`Additional operators
`
`
`
`Section 3.2
`
`‘
`
`Formal Query languages
`
`59
`
`custamrr~name
`
`.wanna.-
`
`Figure 3.11 Customers with an account and a loan at the Perryridge branch.
`
`\‘Ve have now seen the five fundamental operations of the relational
`algebra: o, n, x, U, -. These five operators are sufficient to express any
`relational algebra query; However,
`if we restrict ourselves to just the five
`fundamental operators, some common queries are lengthy to express.
`Therefore. we define additional operators. These new operators do not add
`any power to the algebra, but they do simplify common queries.
`For each new operator we define, we give an equivalent expression
`using only the five fundamental operators.
`The first additional relational algebra operation we shall define is set
`intersection (n). Suppose we wish to find all customers that have both a
`loan and an account at the Perryridge branch. Using set intersection, we
`could write:
`
`chstomrr-name (”brunch-name = “Perryridgc“ (bor'row))
`n nmstmner-name (obmndr-hame - “Pcrryridge” (deposit))
`
`The result relation for this query appears in Figure 3.11.
`intersection as a
`Note, however,
`that we do not
`include set
`fundamental operation. We do not do so because we can rewrite any
`relational algebra expression using set
`intersection by replacing the
`intersection operation with a pair of set difference operations as follows:
`rns=r-(r—5)
`
`Thus, set intersection does not add any power to the relational algebra. It
`is simply more convenient to write I n 5
`than r - (r - s).
`The next operations we add to the algebra are used to simplify many
`queries that require a Cartesian product. Typically, a query that involves a
`(anesian product
`includes a selection operation on the result of the
`Cartesian product. Consider the query “Find all customers who have a loan
`at the Perryridge branch and the cities in which they live." We first form
`the Cartesian product of the borrow and customer relations, then we select
`those tuples that pertain to IPerryr-idge and pertain to only one customer-
`name. Thus we write
`
`“humanism-name. customer.custnmcr—dty ("P‘bo mm x custom»
`Where:
`\
`
`P = borrow.branch-name = "Pen-yddge"
`A bonaw.customer—name = customer.customer-nnme
`
`The theta join is a binary operation that allows us to combine the
`selection and cartesian product
`into one operation. The theta join is
`denoted by W 9, where N is the "join" symbol and the subscript 8 (the
`Greek letter theta) is replaced