數(shù)據(jù)庫(kù)系統(tǒng)概念課后習(xí)題答案--實(shí)踐習(xí)題部分

CHAPTER 1IntroductionSolutions to Practice Exercises1.1 Two disadvantages associated with database systems are listed below.a. Setup of the database system requires more knowledge, money, skills, andtime.b. The complexity of the database may result in poor performance.1.2 Programming language classification: Procedural: C, C+, Java, Basic, Fortran, Cobol, Pascal Non-procedural: Lisp and PrologNote: Lisp and Prolog support some procedural constructs, but the core of boththese languages is non-procedural.In theory, non-procedural languages are easier to learn, because they let theprogrammer concentrate on what needs to be done, rather than how to do it. Thisis not always true in practice, especially if procedural languages are learnedfirst.1.3 Six major steps in setting up a database for a particular enterprise are: Define the high level requirements of the enterprise (this step generates adocument known as the system requirements specification.) Define a model containing all appropriate types of data and data relation-ships. 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 becarried out by clerks or Web users) define a user interface to carry out thetask, and write the necessary application programs to implement the userinterface.12 Chapter 1 Introduction Create/initialize the database.1.4 Let tgrid be a two-dimensional integer array of size n m.a. The physical level would simply be m n(probably consecutive) stor-age 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 in-teger, which is n boxes high by m boxes wide. There are 2mnpossible views. For example, a view might be the entirearray, or particular row of the array, or all n rows but only columns 1through i.b. Consider the following Pascal declarations:type tgrid = array1.n,1.m of integer；var vgrid1, vgrid2 : tgridThen tgrid is a schema, whereas the value of variables vgrid1 and vgrid2are instances. To illustrate further, consider the schema array1.2, 1.2 of integer.Twoinstancesofthisschemeare:1 16 17 907 89 412 8CHAPTER 2Relational ModelSolutions to Practice Exercises2.1 a. person name(employee a49 manages)a49(manager name=employee2.person nameemployee.street=employee2.streetemployee.city =employee2.city)(employee2(employee)b. The following solutions assume that all people work for exactly one com-pany. If one allows people to appear in the database (e.g. in employee)butnot appear in works, the problem is more complicated. We give solutions forthis more realistic case later.person name(company name negationslash= “First Bank Corporation”(works)If people may not work for any company:person name(employee) person name(company name = “First Bank Corporation”)(works)c. person name(works) (works.person name(worksa49(works.salary pany name=“Small Bank Corporation”)works2(works)2.2 a. The left outer theta join of r(R)ands(S) (r a49s) can be defined as(r a49s) (r R(r a49s) (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)ands(S) (r a49s) can be defined as(r a49s) (null,null,.,null) (s S(r a49s)The tuple of nulls is of size equal to the number of attributes in R.34 Chapter 2 Relational Modelc. The full outer theta join of r(R)ands(S) (r a49s) can be defined as(r a49s) (null,null,.,null) (s S(r a49s)(r R(r a49s) (null,null,.,null)The first tuple of nulls is of size equal to the number of attributes in R,andthe second one is of size equal to the number of attributes in S.2.3 a. employee person name,street,primeprimeNewtownprimeprime(person name=“Jones”(employee) (employee person name=“Jones”(employee)b. The update syntax allows reference to a single relation only. Since this up-date requires access to both the relation to be updated (works)andtheman-ages relation, we must use several steps. First we identify the tuples of worksto be updated and store them in a temporary relation (t1). Then we createa temporary relation containing the new tuples (t2). Finally, we delete thetuples in t1,fromworks and insert the tuples of t2.t1 works.person name,company name,salary(works.person name=manager name(worksmanages)t2 person name,company name,1.1salary(t1)works (works t1) t2CHAPTER 3SQLSolutions to Practice Exercises3.1 Note: The participated relation relates drivers, cars, and accidents.a. Note: this is not the same as the total number of accidents in 1989. We mustcount people with several accidents only once.select count (distinct name)from accident, participated, personwhere accident.report number = participated.report numberand participated.driver id = person.driver idand date between date 1989-00-00 and date 1989-12-31b. 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 thegiven car. Then the participated and accident relations must be updated in or-der 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 report numberand 3000 for damage amount.insert into accidentvalues (4007, 2001-09-01, Berkeley)insert into participatedselect o.driver id, c.license, 4007, 3000from person p, owns o, car cwhere =Jonesand p.driver id = o.driver id ando.license = c.license and c.model =Toyotac. Since model is not a key of the car relation, we can either assume that onlyone of John Smiths cars is a Mazda, or delete all of John Smiths Mazdas(the query is the same). Again assume name is a key for person.56 Chapter 3 SQLdelete carwhere model = Mazda and license in(select licensefrom person p, owns owhere = John Smith and p.driver id = o.driver id)Note: The owns, accident and participated records associated with the Mazdastill exist.3.2 a. Query:select e.employee name, cityfrom employee e, works wwhere pany name = First Bank Corporation andw.employee name = e.employee nameb. If people may work for several companies, the following solution will onlylist those who earn more than $10,000 per annum from “First Bank Corpo-ration” alone.select *from employeewhere employee name in(select employee namefrom workswhere company name = First Bank Corporation and salary 10000)As in the solution to the previous query, we can use a join to solve this onealso.c. The following solution assumes that all people work for exactly one com-pany.select employee namefrom workswhere company name negationslash= First Bank CorporationIf one allows people to appear in the database (e.g. in employee)butnotappear in works, or if people may have jobs with more than one company,the solution is slightly more complicated.select employee namefrom employeewhere employee name not in(select employee namefrom workswhere company name = First Bank Corporation)d. The following solution assumes that all people work for at most one com-pany.Exercises 7select employee namefrom workswhere salary all(select salaryfrom workswhere company name = Small Bank Corporation)If people may work for several companies and we wish to consider thetotal earnings of each person, the problem is more complex. It can be solvedby using a nested subquery, but we illustrate below how to solve it usingthe with clause.with emp total salary as(select employee name, sum(salary) as total salaryfrom worksgroup by employee name)select employee namefrom emp total salarywhere total salary all(select total salaryfrom emp total salary, workswhere pany name = Small Bank Corporation andemp total salary.employee name = works.employee name)e. The simplest solution uses the contains comparison which was included inthe original System R Sequel language but is not present in the subsequentSQL versions.select T.company namefrom company Twhere (select R.cityfrom company Rwhere R.company name = T.company name)contains(select S.cityfrom company Swhere S.company name = Small Bank Corporation)Below is a solution using standard SQL.8 Chapter 3 SQLselect S.company namefrom company Swhere not exists (select cityfrom companywhere company name = Small Bank Corporation)except(select cityfrom company Twhere S.company name = T.company name)f. Query:select company namefrom worksgroup by company namehaving count (distinct employee name) = all(select count (distinct employee name)from worksgroup by company name)g. Query:select company namefrom worksgroup by company namehaving avg (salary) (select avg (salary)from workswhere company name = First Bank Corporation)3.3 a. The solution assumes that each person has only one tuple in the employeerelation.update employeeset city =Newtonwhere person name =Jonesb. Query:Exercises 9update works Tset T.salary = T.salary * 1.03where T.employee name in (select manager namefrom manages)and T.salary * 1.1 100000and T.company name = First Bank Corporationupdate works Tset T.salary = T.salary * 1.1where T.employee name in (select manager namefrom manages)and T.salary * 1.1 100000) then 1.03else 1.1)where T.employee name in (select manager namefrom manages) andT.company name = First Bank Corporation3.4 Query:select coalesce(, ) as name,coalesce(a.address, b.address) as address,a.title,b.salaryfrom a full outer join b on = anda.address = b.address3.5 We use the case operation provided by SQL-92:a. To display the grade for each student:select student id,(casewhen score 40 then F,when score 60 then C,when score 80 then B,else Aend) as gradefrom marks10 Chapter 3 SQLb. 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 gradesgroup by grade3.6 The query selects those values of p.a1 that are equal to some value of r1.a1 orr2.a1 if and only if both r1 and r2 are non-empty. If one or both of r1 and r2are empty, the cartesian product of p, r1 and r2 is empty, hence the result of thequery is empty. Of course if p itself is empty, the result is as expected, i.e. empty.3.7 To insert the tuple (“Johnson”, 1900) into the view loan info,wecandothefol-lowing:borrower (“Johnson”,k) borrowerloan (k,1900) loansuch that kis a new marked null not already existing in the database.CHAPTER 4Advanced SQLSolutions to Practice Exercises4.1 Query: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)Declaringthepaircustomer name, loan numberofrelationborrowerasprimarykeyensures that the relation does not contain duplicates.4.2 Query:1112 Chapter 4 Advanced SQLcreate table employee(person name char(20),street char(30),city char(30),primary key (person name)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)ppcreate 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 at-tributes may be acceptable.a. check condition for the works table:check(employee name, company name) in(select e.employee name, pany namefrom employee e, company cwhere e.city = c.city)b. check condition for the works table:Exercises 13check(salaryall(select manager salaryfrom (select manager name, manages.employee name as emp name,salary as manager salaryfrom works, manageswhere works.employee name = manages.manager name)where employee name = emp name)The solution is slightly complicated because of the fact that inside the se-lect expressions scope, the outer works relation into which the insertion isbeing performed is inaccessible. Hence the renaming of the employee nameattribute to emp name. Under these circumstances, it is more natural to useassertions.4.3 Thetuplesofallemployeesofthemanager,at all levels,get deletedaswell! Thishappens in a series of steps. The initial deletion will trigger deletion of all thetuples corresponding to direct employees of the manager. These deletions willin turn cause deletions of second level employee tuples, and so on, till all directand indirect employee tuples are deleted.4.4 The assertion name is arbitrary. We have chosen the name perry.Notethatsincethe assertion applies only to the Perryridge branch we must restrict attention toonly the Perryridge tuple of the branch relation rather than writing a constrainton the entire relation.create assertion perry check(not exists (select *from branchwhere branch name = Perryridge andassets negationslash=(select sum (amount)from loanwhere branch name = Perryridge)4.5 WritingqueriesinSQL istypicallymucheasierthancodingthesamequeriesinageneral-purpose programming language. However not all kinds of queries canbe written in SQL. Also nondeclarative actions such as printing a report, inter-acting with a user, or sending the results of a query to a graphical user interfacecannot be done from within SQL. Under circumstances in which we want thebest of both worlds, we can choose embedded SQL or dynamic SQL, rather thanusing SQL alone or using only a general-purpose programming language.EmbeddedSQL hastheadvantageofprogramsbeinglesscomplicatedsinceitavoids the clutter of the ODBC or JDBC function calls, but requires a specializedpreprocessor.CHAPTER 5OtherRelationalLanguagesSolutions to Practice Exercises5.1 a. t |q r (qA=tA)b. t | t r tB=17c. t|p r q s (tA=pA tB=pB tC=pC tD=qD tE=qE tF=qF)d. t |p r q s (tA=pA tF=qF pC=qD5.2 a. |p, q ( r1)b. | r1 b =17c. | r1 r2d. | r1 r2e. | r1 negationslash r2f. |p, q ( r1 r2)5.3 a. |b ( r b =7)i.ABP. 17rii. query (X) :- r (X, 17)1516 Chapter 5 Other Relational Languagesb. | r si.ABrAC _a _c _a _bsP.result BAC _a _b _cii. query(X, Y, Z) :- r(X, Y), s(X, Z)c. |c ( s b1,b2( r r b1b2)i.ABrAC P._a _c _a _s _c _ssii. query (X) :- s (X, Y ),r(X, Z),r(Y, W),Z W5.4 a. Query:query (X) :- p (X)p (X) :- manages (X, “Jones”)p (X) :- manages (X, Y ),p(Y )b. Query:query(X, C) :- p(X), employee(X, S, C)p(X) :- manages(X, “Jones”)p(X) :- manages(X, Y), p(Y)c. Query: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. Query:Exercises 17query(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.5 A Datalog rule has two parts, the head and the body. The body is a comma sep-arated list of literals.Apositive literal has the form p(t1,t2,., tn)wherep isthe name of a relation with n attributes, and t1,t2,., tnare either constantsor variables. A negative literal has the form p(t1,t2,., tn) where p has n at-tributes. In the case of arithmetic literals, p will be an arithmetic operator like ,= etc.We consider only safe rules； see Section 5.4.4 for the definition of safety ofDatalog rules. Further, we assume that every variable that occurs in an arith-metic literal also occurs in a positive non-arithmetic literal.Consider first a rule without any negative literals. To express the rule as an ex-tended relational-algebra view, we write it as a join of all the relations referred toin the (positive) non-arithmetic literals in the body, followed by a selection. Theselection condition is a conjunction obtained as follows. If p1(X, Y ),p2(Y, Z)occur in the body, where p1is of the schema (A, B) and p2is of the schema(C, D),thenp1.B = p2.C should belong to the conjunction. The arithmeticliterals can then be added to the condition.As an example, the Datalog queryquery(X, Y) :- works(X, C, S1), works(Y,C,S2),S1 S2, manages(X, Y)becomes the following relational-algebra expression:E1= (pany name=pany name w1.salaryw2.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 areno constants in the negative literals； recall that all variables in a negative literalmust also occur in a positive literal. Let q(X,Y ) be the first negative literal,and let it be of the schema (E, F).LetEibe the relational algebra expressionobtained after all positive and arithmetic literals have been handled. To handlethis negative literal, we generate the expressionEj= Eia49 (A1,A2(Ei) q)where A1and A2are the attribute names of two columns in Eiwhich corre-spond to X and Y respectively.Now let us consider constants occurring in a negative literal. Consider a neg-ative literal of the form q(a, b, Y ) where a and b are constants. Then, in theabove expression defining Ejwe replace q by A1=aA2=b(q).Proceeding in a similar fashion, the remaining negative literals are processed,finally resulting in an expression Ew.18 Chapter 5 Other Relational LanguagesFinally the desired attributes are projected out of the expression. The at-tributes in Ewcorresponding to the variables in the head of the rule becomethe projection attributes.Thus our example rule finally becomes the view:create view query asw1.personname,w2.personname(E2)If there are multiple rules for the same predicate, the relational-algebra ex-pression defining the view is the union of the expressions corresponding to theindividual rules.Theaboveconversioncanbeextendedtohandlerulesthatsatisfysomeweakerforms of the safety conditions, and where some restricted cases where the vari-ables in arithmetic predicates do not appear in a positive non-arithmetic literal.CHAPTER 6Database Design andthe E-R ModelSolutions to Practice Exercises6.1 See Figure 6.16.2 See Figure 6.2.In the answer given here, the main entity sets are student, course, course offering,and instructor. The entity set course offering is a weak entity set dependent oncourse. The assumptions made are :a. A class meets only at one particular place and time. This E-R diagram cannotmodel a class meeting at different places at different times.b. There is no guarantee that the database does not have two classes meetingat the same place and time.person owns carparticipatedaccidentaddressdamage_amountmodelyearlicensenamereport_numberdatelocationdriver_iddriverFigure6.1 E-R diagram for a car insurance company.1920 Chapter 6 Database Design and the E-R Modelprogramcourse offerings depttitlecoursecoursenotitlecreditssyllabusprerequisitemaincourserequiressecnois offeredstudentnamegradeteachesyearsemesterroomtimeenrols instructornameiidsidFigure6.2 E-R diagram for a university.6.3 a. See Figure 6.3b. See Figure 6.46.4 See Figure 6.5course offeringssecnocoursenoexamnameplacetimemarksprogrameidstudentnameyearsemesterroomtimetakessidFigure6.3 E-R diagram for marks database.Exercises 21course offeringssecnocoursenoprogramexamname placetimeexamofmarksstudentnameyearsemesterroomtimetakessidFigure6.4 Another E-R diagram for marks database.6.5 By using one entity set many times we are missing relationships in the model.For example, in the E-R diagram in Figure 6.6: the students taking classes arethe same students who are athletes, but this model will not show that.6.6 a. See Figure 6.7b. The additional entity sets are useful if we wish to store their attributes aspart of the database. For the course entity set, we have chosen to includethree attributes. If only the primary key (c number) were included, and ifcourses have only one section, then it would be appropriate to replace thecourse (and section) entity sets by an attribute (c number)ofexam.Thereasonit is undesirable to have multiple attributes of course as attributes of exam isthat it would then be difficult to maintain data on the courses, particularlyif a course has no exam or several exams. Similar remarks apply to the roomentity set.stadiummatchiddatematch playername ageplayedseason_scoreopponentown_score opp_score scoreFigure6.5 E-R diagram for favourite team statistics.22 Chapter 6 Database Design and the E-R Modelnamess#takesnamess#deptstudentstudentplays sportcoursenoteamnameclassFigure6.6 E-R diagram with entity duplication.6.7 a. The criteria to use are intuitive design, accurate expression of the real-worldconcept and efficiency. A model which clearly outlines the objects and rela-tionships in an intuitive manner is better than one which does not, becauseit is easier to use and easier to change. Deciding between an attribute andan entity set to represent an object, and deciding between an entity set andrelationship set, influence the accuracy with which the real-world conceptis expressed. If the right design choice is not made, inconsistency and/orloss of information will result. A model which can be implemented in anefficient manner is to be preferred for obvious reasons.b. Consider three different alternatives for the problem in Exercise 6.2. See Figure 6.8 See Figure 6.9 See Figure 6.10Each alternative has merits, depending on the intended use of the database.Scheme 6.8 has been seen earlier. Scheme 6.10 does not require a separateentity for prerequisites. However, it will be difficult to store all the prerequi-namesectionfortimec-numbersection ofs-numbercourseexaminroomr-number capacity buildingexam_iddepartment enrollmentFigure6.7 E-R diagram for exam scheduling.Exercises 23programcourse offeringsdept titlecoursecoursenotitlecreditssyllabusprerequisitemaincourserequiressecnostudentnameteachesyearsemesterroomtimeenrolssidinstructornameiidis offeredgradeFigure6.8 E-R diagram for University(a) .sites(being a multi-valued attribute). Scheme 6.9 treats prerequisites as wellas classrooms as separate entities, making it useful for gathering data aboutprerequisites and room usage. Scheme 6.8 is in between the others, in thatit treats prerequisites as separate entities but not classrooms. Since a regis-trars office probably has to answer general questions about the number ofclasses a student is taking or what are all the prerequisites of a course, orwhere a specific class meets, scheme 6.9 is probably the best choice.6.8 a. If a pair of entity sets are connected by a path in an E-R diagram, the en-tity sets are related, though perhaps indirectly. A disconnected graph im-plies that there are pairs of entity sets that are unrelated to each other. If wesplit the graph into connected components, we have, in effect, a separatedatabase corresponding to each connected component.b. As indicated in the answer to the previous part, a path in the graph betweena pair of entity sets indicates a (possibly indirect) relationship between thetwo entity sets. If there is a cycle in the graph then every pair of entity setson the cycle are related to each other in at least two distinct ways. If the E-Rdiagram is acyclic then there is a unique path between every pair of entitysets and, thus, a unique relationship between every pair of entity sets.6.9 a. Let E = e1,e2, A = a1,a2, B = b1, C = c1, RA= (e1,a1),(e2,a2),RB= (e1,b1),andRC= (e1,c1). We see that because of the tuple(e2,a2), no instance of R exists which corresponds to E, RA, RBand RC.b. See Figure 6.11. The idea is to introduce total participation constraints be-tween E and the relationships RA, RB, RCso that every tuple in E has arelationship with A, B and C.24 Chapter 6 Database Design and the E-R Modelprogramcourse offerings dept titlecoursecoursenotitlecreditssyllabusprerequisitemaincourserequiressecnoisofferedmeetsingroom_no buildingiss#instructornamestudentnamess#gradeteachesyear semestertimeenrolsroomFigure6.9 E-R diagram for University(b).programcourse offeringsdept titlecoursecoursenotitlesyllabussecnois offeredprerequisiteiss#instructornamestudentnamess#gradeteachesyearsemesterroomtimeenrolscreditsFigure6.10 E-R diagram for University(c).Exercises 25AECBRBRARCFigure6.11 E-R diagram to Exercise 6.9b.c. Suppose A totally participates in the relationhip R, then introduce a totalparticipation constraint between A and RA.d. Consider E asaweakentitysetandRA, RBand RCas its identifying rela-tionship sets. See Figure 0 The primary key of a weak entity set can be inferred from its relationship withthe 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 haveto be the same. Hence there will be redundancy.6.11 A inherits all the attributes of X plus it may define its own attributes. SimilarlyC inherits all the attributes of Y plus its own attributes. B inherits the attributesof 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.6.12 In this example, we assume that both banks have the shared identifiers for cus-tomers, such as the social security number. We see the general solution in thenext exercise.Each of the problems mentioned does have potential for difficulties.a. branch name istheprimary-keyofthebranchentityset.Thereforewhilemerg-ing the two banks entity sets, if both banks have a branch with the samename, one of them will be lost.b. customers participate in the relationship sets cust banker, borrower and de-positor. While merging the two banks customer entity sets, duplicate tuplesBECACRBRARFigure6.12 E-R diagram to Exercise 6.9d.26 Chapter 6 Database Design and the E-R Modelof the same customer will be deleted. Therefore those relations in the threementioned relationship sets which involved these deleted tuples will haveto be updated. Note that if the tabular representation of a relationship set isobtained by taking a union of the primary keys of the participating entitysets, no modification to these relationship sets is required.c. The problem caused by loans or accounts with the same number in both thebanks is similar to the problem caused by branches in both the banks withthe 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 nameto the branch name attributeineachtuple.Theemployee entity sets can be mergeddirectly, and so can the payment entity sets. No duplicate removal should beperformed. Before merging the loan and account entity sets, whenever there is anumber common in both the banks, the old number is replaced by a new uniquenumber, in one of the banks.Next the relationship sets can be merged. Any relation in any relationshipset 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 loannumber common in both the banks prior to the merger, and let it be replaced bya new unique number 2611 in one of the banks, say bank 2. Now all the relationsin borrower, loan branch and loan payment of bank 2 which refer to loan number1611 will have to be modified to refer to 2611. Then the merger with bank 1scorresponding relationship sets can take place.6.13 Thisisacaseinwhichtheschemasofthetwobanksdiffer,sothemergerbe-comes more difficult. The identifying attribute for persons in the US is social-security, and in Canada it is social-insurance. Therefore the merged schema can-not use either of these. Instead we introduce a new attribute person id,andusethis uniformly for everybody in the merged schema. No other change to theschema is required. The values for the person id attribute may be obtained byseveral ways. One way would be to prepend a country code to the old social-security or social-insurance values (“U” and “C” respectively, for instance), toget the corresponding person id values. Another way would be to assign freshnumbers starting from 1 upwards, one number to each social-security and social-insurance value in the old databases.Once this has been done, the actual merger can proceed as according to theanswer to the previous question. If a particular relationship set, say borrower,in-volves only US customers, this can be expressed in the merged database by spe-cializing the entity-set customer into us customer and canada customer,andmak-ing only us customer participate in the merged borrower. Similarly employee canbe specialized if needed.CHAPTER 7Relational-DatabaseDesignSolutions to Practice Exercises7.1 A decomposition R1,R2 is a lossless-join decomposition if R1 R2 R1or R1 R2 R2.LetR1=(A, B, C),R2=(A, D, E), and R1 R2= A.Since A is a candidate key (see Practice Exercise 7.6), Therefore R1 R2 R1.7.2 The nontrivial functional dependencies are: A B and C B,andade-pendency they logically imply: AC B. There are 19 trivial functional depen-dencies of the form ,where . C does not functionally determineA because the first and third tuples have the same C but different A values. Thesame tuples also show B does not functionally determine A. Likewise, A doesnot functionally determine C because the first two tuples have the same A valueand different C values. The same tuples also show B does not functionally de-termine C.7.3 Let Pk(r) denote the primary key attribute of relation r. The functional dependencies Pk(account)Pk(customer)andPk(customer) Pk(account) indicate a one-to-one relationship because any two tupleswith the same value for account must have the same value for customer,and any two tuples agreeing on customer must have the same value foraccount. The functional dependency Pk(account) Pk(customer) indicates a many-to-one relationship since any account value which is repeated will have thesame customer value, but many account values may have the same cus-tomer value.7.4 To prove that:if and then 2728 Chapter 7 Relational-Database DesignFollowing the hint, we derive: given augmentation rule union of identical sets given augmentation rule transitivity rule and set union commutativity7.5 Proof using Armstrongs axioms of the Pseudotransitivity Rule:if and ,then . given augmentation rule and set union commutativity given transitivity rule7.6 Note: It is not reasonable to expect students to enumerate all of F+.Someshort-hand representation of the result should be acceptable as long as the nontrivialmembers of F+are found.Starting with A BC,wecanconclude:A B and A C.Since A B and B D, A D (decomposition, transitive)Since A CD and CD E, A E (union, decomposition, transitive)Since A A,wehave (reflexive)A ABCDE from the above steps (union)Since E A, E ABCDE (transitive)Since CD E, CD ABCDE (transitive)Since B D and BC CD, BC ABCDE (augmentative, transitive)Also, C C, D D, BD D,etc.Therefore, any functional dependency with A, E, BC,orCDon the left handside of the arrow is in F+, no matter which other attributes appear in the FD.Allow * to represent any set of attributes in R,thenF+is BD B, BD D,C C, D D, BD BD, B D, B B, B BD,andallFDsofthe form A , BC , CD, E where is any subset ofA, B, C, D, E. The candidate keys are A, BC, CD, and E.7.7 The given set of FDs F is:A BCCD EB DE AThe left side of each FD in F is unique. Also none of the attributes in the leftside or right side of any of the FDs is extraneous. Therefore the canonical coverFcis equal to F.Exercises 297.8 The algorithm is correct because: If A is added to result then there is a proof that A. To see this, observethat trivially so is correctly part of result.IfA negationslash is added toresult theremustbesomeFD such that A and is already asubset of result.(Otherwisefdcountwould be nonzero and the if conditionwould be false.) A full proof can be given by induction on the depth ofrecursion for an execution of addin, but such a proof can be expected onlyfrom students with a good mathematical background. If A +,thenA is eventually added to result. We prove this by inductionon the length of the proof of A using Armstrongs axioms. First observethat if procedure addin is called with some argument , all the attributes in will be added to result. Also if a particular FDs fdcount becomes 0, allthe attributes in its tail will definitely be added to result. The base case ofthe proof, A A +, is obviously true because the first call toaddin has the argument . The inductive hypotheses is that if A canbe proved in n steps or less then A result. If there is a proof in n +1steps 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)ststep, A must havebeen in result by the end of the nthstep itself. Otherwise, by the inductivehypothesis result. Therefore the dependency used in proving ,A will have fdcount set to 0 by the end of the nthstep. Hence A willbe added to result.To see that this algorithm is more efficient than the one presented in the chap-ter note that we scan each FD once in the main program. The resulting arrayappears has size proportional to the size of the given FDs. The recursive calls toaddin result in processing linear in the size of appears. Hence the algorithm hastime 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 performthe loop as many times as the number of FDs, in each loop scanning all of themonce.7.9 a. The query is given below. Its result is non-empty if and only if b c doesnot hold on r.select bfrom rgroup by bhaving count(distinct c) 1b.30 Chapter 7 Relational-Database Designcreate assertion b-to-c check(not exists(select bfrom rgroup by bhaving count(distinct c) 1)7.10 Consider some tuple t in u.Note that ri=Ri(u) implies that tRi ri, 1 i n.Thus,tR1 a49 tR2 a49 . a49 tRn r1a49 r2a49 . a49 rnBy the definition of natural join,tR1 a49 tR2 a49 . a49 tRn=(tR1 tR2 . tRn)where the condition is satisfied if values of attributes with the same namein a tuple are equal and where = U. The cartesian product of single tuplesgenerates one tuple. The selection process is satisfied because all attributes withthe same name must have the same value since they are projections from thesame tuple. Finally, the projection clause removes duplicate attribute names.By the definition of decomposition, U = R1R2.Rn, which means thatall attributes of t are in tR1 a49 tR2 a49 .a49 tRn.Thatis,t is equal to the resultof this join.Since t is any arbitrary tuple in u,u r1a49 r2a49 . a49 rn7.11 The dependency B D is not preserved. F1,therestrictionofF 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,therestrictionofF to (C, D, E)isA 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 Dsince the only FD in F1 F2with B as the left side is B B, a trivial FD.Weshall see in Practice Exercise 7.13 that B D is indeed in F+.ThusB D isnot preserved. Note that CD ABCDE is also not preserved.A simpler argument is as follows: F1contains no dependencies with D on theright side of the arrow. F2contains no dependencies with B on the left side ofthe arrow. Therefore for B D to be preserved there must be an FD B in F+1and D in F+2(so B D would follow by transitivity). Since theintersection of the two schemes is A, = A. Observe that B A is not in F+1since B+= BD.Exercises 317.12 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.LetXbe a candidate key for R.Consider a legal instance r of R.Letj =X(r) a49 R1(r) a49 R2(r) . a49Rn(r). We want to prove that r = j.We claim that if t1and t2are two tuples in j such that t1X=t2X,thent1= t2. To prove this claim, we use the following inductive argument Let Fprime= F1 F2 . Fn,whereeachFiis the restriction of F to the schemaRiin . Consider the use of the algorithm given in Figure 7.9 to compute theclosure of X under Fprime. We use induction on the number of times that the forloop in this algorithm is executed. Basis : In the first step of the algorithm, result is assigned to X, and hencegiven that t1X=t2X, we know that t1result=t2result is true. Induction Step :Lett1result=t2result be true at the end of the k th exe-cution of the forloop.Suppose the functional dependency considered in the k +1th executionof the for loop is ,andthat result. result implies thatt1=t2 is true. The facts that holds for some attribute set Riin ,andthatt1Ri and t2Ri are in Ri(r) imply that t1=t2 isalso true. Since is now added to result by the algorithm, we know thatt1result=t2result is true at the end of the k +1th execution of the forloop.Since is dependency-preserving and X is a key for R, all attributes in R are inresult when the algorithm terminates. Thus, t1R=t2R 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.Notealsothat X(j)=X(r)=r (since X is a key for R). Thus we have proved that thesize of j equals that of r.UsingtheresultofPracticeExercise7.10,weknowthatr j. Hence we conclude that r = j.Note that since X is trivially in 3NF, X is a dependency-preservinglossless-join decomposition into 3NF.7.13 Given the relation Rprime=(A, B, C, D) the set of functional dependencies Fprime=A B, C D, B C allows three distinct BCNF decompositions.R1= (A, B), (C, D), (B, C)is in BCNF as isR2= (A, B), (C, D), (A, C)R2= (A, B), (C, D), (A, C)R3= (B, C), (A, D), (A, B)7.14 Suppose R is in 3NF according to the textbook definition. We show that it is in3NF according to the definition in the exercise. Let A be a nonprime attribute in32 Chapter 7 Relational-Database DesignR that is transitively dependent on a key for R. Then there exists R suchthat A, , A negationslash , A negationslash , and does not hold. But then A violates the textbook definition of 3NF since A negationslash implies A is nontrivial Since does not hold, is not a superkey A is not any candidate key, since A is nonprimeNowweshowthatifR is in 3NF according to the exercise definition, it is in 3NFaccording to the textbook definition. Suppose R is not in 3NF according the thetextbook 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 negationslash ,andA negationslash (since A is nonprime). Thus A is transitively dependent on , violatingthe exercise definition.7.15 Referring to the definitions in Practice Exercise 7.14, a relation schema R is saidto be in 3NF if there is no non-prime attribute A in R for which A is transitivelydependent on a key for R.We can also rewrite the definition of 2NF given here as :“Arelationschema R is in 2NF if nonon-primeattribute A ispartially dependenton any candidate key for R.”To prove that every 3NF schema is in 2NF, it suffices to show that if a non-prime attribute A is partially dependent on a candidate key ,thenA is alsotransitively dependent on the key .Let A be a non-prime attribute in R.Let be a candidate key for R. SupposeA is partially dependent on . From the definition of a partial dependency, we know that for some propersubset of , A. Since , .Also, does not hold, since is a candidate key. Finally, since A is non-prime, it cannot be in either or .Thuswe concludethat A is a transitive dependency.Hencewe haveprovedthat every 3NF schema is also in 2NF.7.16 The relation schema R =(A, B, C, D, E) and the set of dependenciesA BCB CDE ADconstitute a BCNF decomposition, however it is clearly not in 4NF.(ItisBCNFbecause all FDs are trivial).CHAPTER 8Application Designand DevelopmentSolutions to Practice Exercises8.1 The CGI interfacestarts anew processto service eachrequest,which has a signif-icant operating system overhead.On the other hand, servelets are run as threadsof an existing process, avoiding this overhead. Further, the process runningthreads could be the Web server process itself, avoiding interprocess commu-nication which can be expensive. Thus, for small to moderate sized tasks, theoverhead of Java is less than the overheads saved by avoiding process creatingand communication.For tasks involving a lot of CPU activity, this may not be the case, and usingCGI with a C or C+ program may give better performance.8.2 Most computers have limits on the number of simultaneous connections theycan accept. With connectionless protocols, connections are broken as soon asthe request is satisfied, and therefore other clients can open connections. Thusmore clients can be served at the same time. A request can be routed to any oneof a number of different servers to balance load, and if a server crashes anothercan take over without the client noticing any problem.Thedrawbackofconnectionlessprotocolsisthataconnectionhasto bereestab-lished every time a request is sent. Also, session information has to be sent eachtime in form of cookies or hidden fields. This makes them slower than the pro-tocols which maintain connections in case state information is required.8.3 Caching can be used to improve performance by exploiting the commonalitiesbetween transactions.a. If the application code for servicing each request needs to open a connectionto the database, which is time consuming, then a pool of open connectionsmay be created before hand, and each request uses one from those.3334 Chapter 8 Application Design and Developmentb. The results of a query generated by a request can be cached. If same requestcomesagian, or generatesthe same query,thenthe cachedresult can beusedinstead of connecting to database again.c. The final webpage generated in response to a request can be cached. If thesame request comes again, then the cached page can be outputed.8.4 For inserting into the materialized view branch cust we must set a database trig-ger on an insert into depositor and account. We assume that the database systemuses immediate binding for rule execution. Further, assume that the current ver-sion of a relation is denoted by the relation name itself, while the set of newlyinserted tuples is denoted by qualifying the relation name with the prefix in-serted.The active rules for this insertion are given below define trigger insert into branch cust via depositorafter insert on depositorreferencing new table as inserted for each statementinsert into branch custselect branch name, customer namefrom inserted, accountwhere inserted.account number = account.account numberdefine trigger insert into branch cust via accountafter insert on accountreferencing new table as inserted for each statementinsert into branch custselect branch name, customer namefrom depositor, insertedwhere depositor.account number = inserted.account numberNote that if the execution binding was deferred (instead of immediate), thenthe result of the join of the set of new tuples of account with the set of new tuplesof depositor would have been inserted by both active rules, leading to duplicationof the corresponding tuples in branch cust.The deletion of a tuple from branch cust is similar to insertion, except thata deletion from either depositor or account will cause the natural join of theserelations to have a lesser number of tuples. We denote the newly deleted set oftuples by qualifying the relation name with the keyword deleted.define trigger delete from branch cust via depositorafter delete on depositorreferencing old table as deleted for each statementdelete from branch custselect branch name, customer namefrom deleted, accountwhere deleted.account number = account.account numberExercises 35define trigger delete from branch cust via accountafter delete on accountreferencing old table as deleted for each statementdelete from branch custselect branch name, customer namefrom depositor, deletedwhere depositor.account number = deleted.account number8.5 Query:create trigger check-delete-trigger after delete on accountreferencing old row as orowfor each rowdelete from depositorwhere depositor.customer name not in( select customer name from depositorwhere account number orow.account number )end8.6 The key problem with digital certificates (when used offline, without contactingthe certificate issuer) is that there is no way to withdraw them.For instance (this actually happened, but names of the parties have beenchanged) person C claims to be an employee of company X and get a newpublic key certified by the certifying authorityA. Suppose the authorityAincor-rectly believed thatC was acting on behalf of companyX, it givesC acertificatecert.Now,C can communicate with person Y , who checks the certificate certpresenetd by C, and believes the public key contained in cert really belongs toX.NowC would communicate with Y using the public key, and Y trusts thecommunication is from company X.Person Y may now reveal confidential information to C, or accept purchaseorderfromC, or executeprogramscertified byC, based on the public key, think-ing he is actually communicating with company X. In each case there is poten-tial for harm to Y .Even if A detects the impersonation, as long as Y does not check with A (theprotocol does not require this check), there is no way for Y to find out that thecertificate is forged.If X was a certification authority itself, further levels of fake certificates canbe created. But certificates that are not part of this chain would not be affected.8.7 A scheme for storing passwords would be to encrypt each password, and thenuse a hash index on the user-id. The user-id can be used to easily access theencrypted password. The password being used in a login attempt is then en-crypted and compared with the stored encryption of the correct password. Anadvantage of this scheme is that passwords are not stored in clear text and thecode for decryption need not even exist!CHAPTER 9Object-Based DatabasesSolutions to Practice Exercises9.1 For this problem, we use table inheritance. We assume that MyDate, Color andDriveTrainType are pre-defined types.create type Vehicle(vehicle id integer,license number char(15),manufacturer char(30),model char(30),purchase date MyDate,color Color)create table vehicle of type Vehiclecreate table truck(cargo capacity integer)under vehiclecreate table sportsCar(horsepower integerrenter age requirement integer)under vehiclecreate table van(num passengers integer)under vehicle3738 Chapter 9 Object-Based Databasescreate table offRoadVehicle(ground clearance realdriveTrain DriveTrainType)under vehicle9.2 a. No Answer.b. Queries in SQL:1999.i. Program:select enamefrom emp as e, e.ChildrenSet as cwhere March in(select birthday.monthfrom c)ii. Program:select e.enamefrom emp as e, e.SkillSet as s, s.ExamSet as xwhere s.type =typingand x.city =Daytoniii. Program:select distinct s.typefrom emp as e, e.SkillSet as s9.3 a. The corresponding SQL:1999 schema definition is given below. Note that thederived attribute age has been translated into a method.create type Name(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) array10,dob date)Exercises 39method integer age()b. create function Name (f varchar(15), m char, l varchar(15)returns Namebeginset first name = f；set middle initial = m；set last name = l；endcreate function Street (sname varchar(15), sno varchar(4), ano varchar(7)returns Streetbeginset street name = sname；set street number = sno；set apartment number =ano；endcreate function Address (s Street, c varchar(15), sta varchar(15), zip varchar(6)returns Addressbeginset street = s；set city = c；set state =sta；set zip code =zip；end9.4 a. The schema definition is given below. Note that backward references canbe addedbut they are not so important as in OODBS because queries can bewritten in SQL and joins can take care of integrity constraints.create type Employee(person name varchar(30),street varchar(15),city varchar(15)create type Company(company name varchar(15),(city varchar(15)create table employee of Employeecreate table company of Companycreate type Works(person ref(Employee) scope employee,comp ref(Company) scope company,salary int)create table works of Workscreate type Manages(person ref(Employee) scope employee,(manager ref(Employee) scope employee)40 Chapter 9 Object-Based Databasescreate table manages of Managesb. i. select compnamefrom worksgroup by comphaving count(person)all(select count(person)from worksgroup by comp)ii. select compnamefrom worksgroup by comphaving sum(salary)all(select sum(salary)from worksgroup by comp)iii. select compnamefrom worksgroup by comphaving avg(salary)(select avg(salary)from workswhere compcompany name=”First Bank Corporation”)9.5 a. A computer-aided design system for a manufacturer of airplanes:An OODB system would be suitable for this. That is because CAD requirescomplex data types, and being computation oriented, CAD tools are typi-cally used in a programming language environment needing to access thedatabase.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 tobe 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 datatypes. But queries are probably simple, and thus an object relational systemis suitable.9.6 An entity is simply a collection of variables or data items. An object is an encap-sulation of data as well as the methods (code) to operate on the data. The datamembers of an object are directly visible only to its methods. The outside worldcan gain access to the objects data only by passing pre-defined messages to it,and these messages are implemented by the methods.CHAPTER 10XMLSolutions to Practice Exercises10.1 a. The XML representation of data using attributes is shown in Figure 10.1.b. The DTD for the bank is shown in Figure Query:!DOCTYPE db 10.3 Code:/db/emp/skills/type4142 Chapter 10 XMLFigure10.1 XML representation.!DOCTYPE bank Figure10.2 The DTD for the bank.Exercises 4310.4 Query:for $b in distinct (/bank/account/branch-name)return $b/text() let $s := sum (/bank/accountbranch-name=$b/balance)return $s 10.5 Query:for $b in /bank/account,$c in /bank/customer,$d in /bank/depositorwhere $a/account-number = $d/account-numberand $c/customer-name = $d/customer-namereturn $c $a |for $c in /bank/customer,where every $d in /bank/depositor satisfies(not ($c/customer-name=$d/customer-name)return $c 10.6 The answer in XQuery isfor $c in /bank/customerreturn $c/* for $a in $c/id(accounts)return $a10.7 Realtion schema:book (bid, title, year, publisher, place)article (artid, title, journal, year, number, volume, pages)book author (bid,firstname,last name, order)article author (artid,firstname,last name, order)10.8 The answer is shwn in Figure 10.3.44 Chapter 10 XMLnodes(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)Figure10.3 Relational Representation of XML Data as Trees.Exercises 4510.9 a. The answer is shown in Figure 10.4.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.c. No answer46 Chapter 10 XML bicycle wheel rim 1 spokes 40 tire 1 2 brake 2 gear 3 frame 1 Figure10.4 Example Parts Data in XML.CHAPTER 11Storage and File StructureSolutions to Practice Exercises11.1 This arrangement has the problem that Piand B4i3are on the same disk. Soif that disk fails, reconstruction of B4i3is not possible, since data and parityare both lost.11.2 a. To ensure atomicity, a block write operation is carried out as follows:i. Write the information onto the first physical block.ii. Whenthe firstwrite completessuccessfully, write thesame informationonto the second physical block.iii. Theoutputis declaredcompletedonlyafterthe secondwrite completessuccessfully.During recovery, each pair of physical blocks is examined. If both areidentical and there is no detectable partial-write, then no further actionsare necessary. If one block has been partially rewritten, then we replace itscontents with the contents of the other block. If there has been no partial-write, but they differ in content, then we replace the contents of the firstblock with the contents of the second, or vice versa. This recovery proce-dure ensures that a write to stable storage either succeeds completely (thatis, updates both copies) or results in no change.The requirement of comparing every corresponding pair of blocks dur-ing recovery is expensive to meet. We can reduce the cost greatly by keep-ing track of block writes that are in progress, using a small amount of non-volatile RAM. On recovery, only blocks for which writes were in progressneed to be compared.b. The idea is similar here. For any block write, the information block iswritten first f