(Solution Manual) Database Systems, The Complete Book

Garcia-Molina, Ullman, Widom, 2

Computer Science & Engineering

Solution Manual

2nd Edition

• $15.00 $50.00

---

Description

Solution Manual for Database Systems, The Complete Book, The downloadable file consists of 482 pages, and the total size of the file is 3.66 MB. Purchase now only for highly discounted price.

Author(s): Garcia-Molina, Ullman, Widom

---

---

Study Note Preview

Chapter 1 There is no solutions manual for chapter 1. (Database Systems, The Complete Book, 2e Hector Garcia-Molina, Jeffrey Ullman, Jennifer Widom ) Solution Manual)Exercise 2.2.1a For relation Accounts, the attributes are: acctNo, type, balance For relation Customers, the attributes are: firstName, lastName, idNo, account Exercise 2.2.1b For relation Accounts, the tuples are: (12345, savings, 12000), (2345 6, checking, 1000), (34567, savings, 25) For relation Customers, the tuples are: (Robbie, Banks, 901 -222, 12345), (Lena, Hand, 805 -333, 12345), (Lena, Hand, 805 -333, 23456) Exercise 2.2.1c For relation Accounts and the first tuple, the components a re: 123456 → acctNo savings → type 12000 → balance For relation Customers and the first tuple, the components are: Robbie → firstName Banks → lastName 901-222 → idNo 12345 → account Exercise 2.2.1d For relation Accounts, a relation schema is: Accounts(acctNo, type, balance) For relation Customers, a relation schema is: Customers(firstName, lastName, idNo, account) Exercise 2.2.1e An example database schema is: Accounts ( acctNo, type, balance ) Customers ( firstName, lastName, idNo, account ) Exercise 2.2.1f A suitable domain for each attribute: acctNo → Integer type → String balance → Integer firstName → String lastName → String idNo → String (because there is a hyphen we cannot use Integer) account → Integer Exercise 2.2.1g Another equivalent way to present the Account relation: acctNo balance type 34567 25 savings 23456 1000 checking 12345 12000 savings Another equivalent way to present the Customers relation: idNo firstName lastName account 805-333 Lena Hand 23456 805-333 Lena Hand 12345 901-222 Robbie Banks 12345 Exercise 2.2.2 Examples of attributes that are created for primarily serving as keys in a relation: Universal Product Code (UPC) used widely in United States and Canada to track products in stores. Serial Numbers on a wide variety of products to allow the manufacturer to individually track each product. Vehicle Identification Numbers (VIN), a unique serial number used by the automotive industry to identify vehicles. Exercise 2.2.3a We can order the three tuples in any of 3! = 6 ways. Also, the columns can be ordered in any of 3! = 6 ways. Thus, the number of presentations is 6*6 = 36. Exercise 2.2.3b We can order the three tuples in any of 5! = 120 ways. Also, the co lumns can be order ed in any of 4! = 24 ways. Thus, the number of presentations is 120*24 = 2880 Exercise 2.2.3c We can order the three tuples in any of m! ways. Also, the columns can be ordered in any of n! ways. Thus, the number of presentations is n!m! Exercise 2.3.1a CREATE TABLE Product ( maker CHAR(30), model CHAR(10) PRIMARY KEY, type CHAR(15) ); Exercise 2.3.1 b CREATE TABLE PC ( model CHAR(30), speed DECIMAL(4,2), ram INTEGER, hd INTEGER, price DECIMAL(7,2) ); Exercise 2.3.1 c CREATE TABLE Laptop ( model CHAR(30), speed DECIMAL(4,2), ram INTEGER, hd INTEGER, screen DECIMAL(3,1), price DECIMAL(7,2) ); Exercise 2.3.1 d CREATE TABLE Printer ( model CHAR(30), color BOOLEAN, type CHAR (10), price DECIMAL(7,2) ); Exercise 2.3.1 e ALTER TABLE Printe r DROP color; Exercise 2.3.1 f ALTER TABLE Laptop ADD od CHAR (10) DEFAULT ‘none’; Exercise 2.3.2 a CREATE TABLE Classes ( class CHAR(20), type CHAR(5), country CHAR(20), numGuns INTEGER, bore DECIMAL(3,1), displacement INTEGER ); Exercise 2.3.2b CREATE TABLE Ships ( name CHAR(30), class CHAR(20), launched INTEGER ); Exercise 2.3. 2c CREATE TABLE Battles ( name CHAR(30), date DATE ); Exercise 2.3. 2d CREATE TABLE Outcomes ( ship CHAR(30), battle CHAR(30), result CHAR(10) ); Exercise 2.3 .2e ALTER TABLE Classes DROP bore; Exercise 2.3. 2f ALTER TABLE Ships ADD yard CHAR(30); Exercise 2.4 .1a R1 := σspeed ≥ 3.00 (PC) R2 := πmodel(R1) Exercise 2.4 .1b R1 := σhd ≥ 100 (Laptop) R2 := Product (R1) R3 := πmaker (R2) model 1005 1006 1013 Exercise 2.4 .1c R1 := σmaker= B (Product PC) R2 := σmaker= B (Product Laptop) R3 := σmaker= B (Product Printer) R4 := πmodel,price (R1) R5 := πmodel,price (R2) R6: = πmodel,price (R3) R7 := R4 R5 R6 model price 1004 649 1005 630 1006 1049 2007 1429 Exercise 2.4 .1d R1 := σcolor = true AND type = laser (Printer) R2 := πmodel (R1) Exercise 2.4 .1e R1 := σtype=laptop (Product) R2 := σtype=PC (Product) R3 := πmaker(R1) R4 := πmaker(R2) R5 := R3 – R4 Exercise 2.4 .1f maker E A B F G model 3003 3007 maker F G R1 := ρ PC1(PC) R2 := ρ PC2(PC) R3 := R1 (PC1.hd = PC2.hd AND PC1.model <> PC2.model) R2 R4 := π hd(R3) Exercise 2.4 .1g R1 := ρ PC1(PC) R2 := ρ PC2(PC) R3 := R1 (PC1.speed = PC2.speed AND PC1.ram = PC2.ram AND PC1.model < PC2.model ) R2 R4 := π PC1.model,PC2.model (R3) Exercise 2.4 .1h R1 := πmodel(σspeed ≥ 2. 80(PC)) πmodel(σspeed ≥ 2. 80(Laptop)) R2 := π maker,model (R1 Product ) R3 := ρ R3(maker2,model2 )(R2) R4 := R2 (maker = maker2 AND model <> model2) R3 R5 := π maker(R4) Exercise 2.4 .1i R1 := π model ,speed(PC) R2 := π model ,speed(Laptop) R3 := R1 R2 R4 := ρ R4(model 2,speed2) (R3) R5 := π model,speed (R3 (speed < speed2 ) R4) R6 := R3 – R5 R7 := π maker(R6 Product) maker B Exercise 2.4 .1j hd 250 80 160 PC1.model PC2.model 1004 1012 maker B E R1 := π maker,speed (Product PC) R2 := ρ R2(maker2,speed2 )(R1) R3 := ρ R3(maker3,speed3 )(R1) R4 := R1 (maker = maker2 AND speed <> speed2) R2 R5 := R4 (maker 3 = maker AND speed3 <> speed2 AND speed3 <> speed) R3 R6 := π maker(R5) Exercise 2.4 .1k R1 := πmaker,model (Product PC) R2 := ρ R2(maker2,model2) (R1) R3 := ρ R3(maker3,model3) (R1) R4 := ρ R4(maker4,model4) (R1) R5 := R1 (maker = maker2 AND model <> model2) R2 R6 := R3 (maker3 = maker AND model3 <> model2 AND model3 <> model) R5 R7 := R4 (maker4 = maker AND (model4=model OR model4=model2 OR model4= model3)) R6 R8 := π maker(R7) Exercise 2.4.2 a πmodel σspeed≥3.00 PC Exercise 2.4.2b maker A D E maker A B D E Laptopσhd ≥ 100 Productπmaker Exercise 2.4.2c σmaker=B πmodel,price σmaker=B πmodel,price σmaker=B πmodel,price Product PC Laptop Printer Product Product Exercise 2.4.2d Printerσcolor = true AND type = laser πmodel Exercise 2.4.2e σtype=laptop σtype=PCπmaker πmaker– Product Product Exercise 2.4.2f ρPC1 ρPC2 (PC1.hd = PC2.hd AND PC1.model <> PC2.model) πhd PC PC Exercise 2.4.2g ρPC1 ρPC2 PC PC(PC1.speed = PC2.speed AND PC1.ram = PC2.ram AND PC1.model < PC2.model) πPC1.model,PC2.model Exercise 2.4.2h PC Laptopσspeed ≥ 2.80 σspeed ≥ 2.80πmodel πmodel Product πmaker,modelρR3(maker2,model2)(maker = maker2 AND model <> model2) πmaker Exercise 2.4.2i PC LaptopProduct πmodel,speed πmodel,speed ρR4(model2,speed2)πmodel,speed (speed < speed2 )–πmaker Exercise 2.4.2j Product PC πmaker,speedρR3(maker3,speed3) ρR2(maker2,speed2)(maker = maker2 AND speed <> speed2) (maker3 = maker AND speed3 <> speed2 AND speed3 <> speed)πmaker Exercise 2.4.2k Product PCπmaker,model ρR2(maker2,model2) ρR3(maker3,model3) ρR4(maker4,model4)(maker = maker2 AND model <> model2)(maker3 = maker AND model3 <> model2 AND model3 <> model)(maker4 = maker AND (model4=model OR model4=model2 OR model4=model3))πmaker Exercis e 2.4.3 a R1 := σbore ≥ 16 (Classes) R2 := πclass,country (R1) class country Iowa USA North Carolina USA Yamato Japan Exercise 2.4.3b R1 := σlaunched < 1921 (Ships) R2 := πname (R1) name Haruna Hiei Kirishima Kongo Ramillies Renown Repulse Resolution Revenge Royal Oak Royal Sovereign Tennessee Exercise 2.4.3c R1 := σbattle=Denmark Strait A ND result= sunk(Outcomes) R2 := πship (R1) ship Bismarck Hood Exercise 2.4.3d R1 := Classes Ships R2 := σlaunched > 1921 AND displacemen t > 35000 (R1) R3 := πname (R2) name Iowa Missouri Musashi New Jersey North Carolina Washington Wisconsin Yamato Exercise 2.4.3e R1 := σbattle=Guadalcanal (Outcomes) R2 := Ships (ship=name) R1 R3 := Classes R2 R4 := πname,displacement,nu mGuns (R3) name displacement numGuns Kirishima 32000 8 Washington 37000 9 Exercise 2.4.3f R1 := πname(Ships) R2 := πship(Outcomes) R3 := ρR3(name )(R2) R4 := R1 R3 name California Haruna Hiei Iowa Kirishima Kongo Missouri Musashi New Jer sey North Carolina Ramillies Renown Repulse Resolution Revenge Royal Oak Royal Sovereign Tennessee Washington Wisconsin Yamato Arizona Bismarck Duke of York Fuso Hood King George V Prince of Wales Rodney Scharnhorst Exercise 2.4.3g From 2.3.2, assuming that every class has one ship named after the class. R1 := πclass(Classes) R2 := πclass(σname <> class (Ships)) R3 := R1 – R2 Exercise 2.4.3h R1 := πcountry (σtype=bb (Classes)) R2 := πcountry (σtype=bc (Classes)) R3 := R1 ∩ R2 Exercise 2.4.3i R1 := πship, result, date(Battles (battle=name) Outcomes) R2 := ρ R2(ship2,result2,date2) (R1) R3 := R1 (ship=ship2 AND result=damaged AND date < date2) R2 R4 := πship(R3) No results from sample data. Exercise 2.4.4 a σbore ≥ 16 πclass,country Classes South Dakota West Virginia Yamashiro class Bismarck country Japan Gt. Britain Exercise 2.4. 4b σlaunched < 1921 πname Ships Exercise 2.4.4c Outcomesπship σbattle=Denmark Strait AND result=sunk Exercise 2.4.4d Classes Ships σlaunched > 1921 AND displacement > 35000πname Exercise 2.4.4e σbattle=Guadalcanal OutcomesShipsClasses (ship=name) πname,displacement,numGuns Exercise 2.4.4f Ships Outcomesπname πshipρR3(name) Exercise 2.4.4g Classes Shipsπclass σname <> classπclass– Exercise 2.4.4h Classes Classesσtype=bb σtype=bcπcountry πcountry∩ Exercise 2.4.4i Battles Outcomes(battle=name) πship,result,dateρR2(ship2,result2,date2)(ship=ship2 AND result=damaged AND date < date2) πship Exercise 2.4.5 The result of the natural join has only one attribute from each pair of equated attributes. On the other hand, the result of the theta -join has both columns of the attributes and their values are identical. Exercise 2.4.6 Union If we add a tuple to the arguments of the union operator, we will get all of the tuples of the original result and maybe the added tuple. If the added tuple is a duplicate tuple, then the set behavior will eliminate that tuple. Thus the union operator is monotone. Intersection If we add a tuple to the arguments of the intersection operator, we will get all of the tuples of the original result and maybe the added tuple. If the added tuple does not exist in the relation that it is added but does exist in the other relation, then the result set will include the added tuple. Thus the intersection operator is monotone. Difference If we add a tuple to the arg uments of the difference operator, we may not get all of the tuples of the original result. Suppose we have relations R and S and we are computing R – S. Suppose also that tuple t is in R but not in S. The result of R – S would include tuple t. However, if we add tuple t to S, then the new result will not have tuple t. Thus the difference operator is not monotone. Projection If we add a tuple to the arguments of the projection operator, we will get all of the tuples of the original result and the projectio n of the added tuple. The projection operator only selects columns from the relation and does not affect the rows that are selected. Thus the projection operator is monotone. Selection If we add a tuple to the arguments of the selection operator, we will get all of the tuples of the original result and maybe the added tuple. If the added tuple satisfies the select condition, then it will be added to the new result. The original tuples are included in the new result because they still satisfy the select con dition. Thus the selection operator is monotone. Cartesian Product If we add a tuple to the arguments of the Cartesian product operator, we will get all of the tuples of the original result and possibly additional tuples. The Cartesian product pairs the tuples of one relation with the tuples of another relation. Suppose that we are calculating R x S where R has m tuples and S has n tuples. If we add a tuple to R that is not already in R, then we expect the result of R x S to have ( m + 1) * n tuples. Thus t he Cartesian product operator is monotone. Natural Joins If we add a tuple to the arguments of a natural join operator, we will get all of the tuples of the original result and possibly additional tuples. The new tuple can only create additional successfu l joins , not less . If, however, the added tuple cannot successfully join with any of the exis ting tuples, then we will have zero additional successful joins. Thus the natural join operator is monotone. Theta Joins If we add a tuple to the arguments of a t heta join operator, we will get all of the tuples of the original result and possibly additional tuples. The theta join can be modeled by a Cartesian product followed by a selection on some condition. The new tuple can only create additional tuples in the result, not less. If, however, the added tuple does not satisfy the select condition, then no additional tuples will be added to the result. Thus the theta join operator is monotone. Renaming If we add a tuple to the arguments of a renaming operator, we w ill get all of the tuples of the original result and the added tuple. The renaming operator does not have any effect on whether a tuple is selected or not. In fact, the renaming operator will always return as many tuples as its argument. Thus the renaming operator is monotone. Exercise 2.4.7a If all the tuples of R and S are different, then the union has n + m tuples, and this number is the maximum possible. The minimum number of tuples that can appear in the result occurs if every tuple of one relation also appears in the other. Then the union has max( m , n) tuples. Exercise 2.4.7b If all the tuples in one relation can pair successfully with all the tuples in the other relation, then the natural join has n * m tuples. This number would be the maximum po ssible. The minimum number of tuples that can appear in the result occurs if none of the tuples of one relation can pair successfully with all the tuples in the other relation. Then the natural join has zero tuples. Exercise 2.4.7c If the condition C br ings back all the tuples of R, then the cross product will contain n * m tuples. This number would be the maximum possible. The minimum number of tuples that can appear in the result occurs if the condition C brings back none of the tuples of R. T hen the cross product has zero tuples. Exercise 2.4.7d Assuming that the list of attributes L makes the resulting relation π L(R) and relation S schema compatible, then the maximum possible tuples is n. This happens when all of the tuples of π L(R) are not in S. The minimum number of tuples that can appear in the result occurs when all of the tuples in πL(R) appear in S. Then the difference has max( n – m , 0) tuples. Exercise 2.4.8 Defining r as the schema of R and s as the schema of S: 1. πr(R S) 2. R δ(π r∩s(S)) where δ is the duplicate -elimination operator in Section 5.2 pg. 213 3. R – (R – πr(R S)) Exercise 2.4.9 Defining r as the schema of R 1. R - πr(R S) Exercise 2.4.10 πA1,A2…An (R S) Exercise 2.5.1 a σspeed < 2.00 AND price > 500 (PC) = ø Model 1011 violates this constraint. Exercise 2.5.1b σscreen < 15.4 AND hd < 100 AND price ≥ 1000 (Laptop) = ø Model 2004 violates the constraint. Exercise 2.5.1c πmaker(σtype = laptop (Product)) ∩ π maker(σtype = pc (Product)) = ø Manufacturers A,B,E vio late the constraint. Exercise 2.5.1d This complex expression is best seen as a sequence of steps in which we define temporary relations R1 through R4 that stand for nodes of expression trees. Here is the sequence: R1(maker, model, speed) := πmaker,m odel,speed (Product PC) R2(maker, speed) := πmaker,speed (Product Laptop) R3(model) := π model(R1 R1.maker = R2.maker AND R1.speed ≤ R2.speed R2) R4(model) := πmodel(PC) The constraint is R4 ⊆ R3 Manufacturers B,C,D violate the constrain t. Exercise 2.5.1e πmodel(σLaptop.ram > PC.ram AND Laptop.price ≤ PC.price (PC × Laptop) ) = ø Models 2002,2006,2008 violate the constraint. Exercise 2.5.2 a πclass(σbore > 16 (Classes)) = ø The Yamato class violates the constraint. Exercise 2.5.2b πclass(σnumGuns > 9 AND bore > 14 (Classes)) = ø No violations to the constraint. Exercise 2.5.2c This complex expression is best seen as a sequence of steps in which we define t emporary relations R1 through R5 that stand for nodes of expression trees. Here is the sequence: R1(class,name) := π class,name (Classes Ships) R2(class2,name2) := ρ R2(class2,name2) (R1) R3(class3,name3) := ρ R3(class3,name3) (R1) R4(class,name,class2,name2) := R1 (class = class2 AND name <> name2) R2 R5(class,nam e,class2,name2,class3,name3) := R4 (class=class3 AND name <> name3 AND name2 <> name3) R3 The constraint is R5 = ø The Kongo, Iowa and Revenge classes violate the constraint. Exercise 2.5.2d πcountry (σtype = bb (Classes)) ∩ π country (σtype = bc (Classes) ) = ø Japan and Gt. Britain violate the constraint. Exercise 2.5.2e