Scheme 2. However, it will be difficult to store all the prereq- uisites being a multi-valued attribute. What do the following mean in terms of the structure of an enterprise schema? The graph is disconnected. The graph is acyclic. 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 we split the graph into connected components, we have, in effect, a separate database corresponding to each connected component. As indicated in the answer to the previous part, a path in the graph between a pair of entity sets indicates a possibly indirect relationship between the two entity sets.
If there is a cycle in the graph then every pair of entity sets on the cycle are related to each other in at least two distinct ways. If the E-R diagram is acyclic then there is a unique path between every pair of entity sets and, thus, a unique relationship between every pair of entity sets.
Consider the alternative shown in Figure 2. Discuss the relative merits of these two alternative representations of a ternary relationship by binary relationships. Answer: The model of Figure 2. Consider the ABC relationship set below.
Modify the E-R diagram of Figure 2. Modify the translation above to handle total participation constraints on the ternary relationship. The above representation requires that we create a primary key attribute for E. Show how to treat E as a weak entity set so that a primary key attribute is not required. Suppose A totally participates in the relationhip R, then introduce a total participation constraint between A and RA.
Outline what sort of redundancy will result if we do so. Answer: The primary key of a weak entity set can be inferred from its relation- ship with the strong entity set. If we add primary key attributes to the weak entity set, they will be present in both the entity set and the relationship set and they have to be the same.
Hence there will be redundancy. The company sells motorcycles, passenger cars, vans, and buses. Justify your placement of attributes at each level of the hierarchy. Explain why they should not be placed at a higher or lower level. Answer: Figure 2. The generalization— specialization hierarchy for the motor-vehicle company is given in the figure. Some kinds of non-commercial vehicles attract luxury vehicle tax.
Cars alone can be of several types, such as sports-car, sedan, wagon etc. Which of these constraints can the system check automatically? Answer: In a generalization— specialization hierarchy, it must be possible to de- cide which entities are members of which lower level entity sets. In a condition- defined design constraint, membership in the lower level entity-sets is evalu- ated on the basis of whether or not an entity satisfies an explicit condition or predicate.
User-defined lower-level entity sets are not constrained by a member- ship condition; rather, entities are assigned to a given entity set by the database user. Condition-defined constraints alone can be automatically handled by the sys- tem. Whenever any tuple is inserted into the database, its membership in the various lower level entity-sets can be automatically decided by evaluating the respective membership predicates.
Similarly when a tuple is updated, its mem- bership in the various entity sets can be re-evaluated automatically. In overlapping generalizations, the same en- tity may belong to more than one lower-level entity sets. For example, in the employee-workteam example of the book, a manager may participate in more than one work-team.
Answer: In a total design constraint, each higher-level entity must belong to a lower-level entity set. The same need not be true in a partial design constraint. For instance, some employees may belong to no work-team. For entity sets A, B, and C, explain how attributes are inherited from the higher- level entity sets X and Y. Discuss how to handle a case where an attribute of X has the same name as some attribute of Y.
Answer: A inherits all the attributes of X plus it may define its own attributes. Similarly C inherits all the attributes of Y plus its own attributes. B inherits the attributes of both X and Y.
If there is some attribute name which belongs to both X and Y, it may be referred to in B by the qualified name X. Answer: See Figures 2. Assume that both banks use exactly the same E-R database schema —the one in Figure 2. Propose a solution to the problem. For your solution, explain any changes that would have to be made and describe what their effect would be on the schema and the data.
Answer: In this example, we assume that both banks have the shared identifiers for customers, such as the social security number. We see the general solution in the next exercise. Each of the problems mentioned does have potential for difficulties. Therefore those relations in the three mentioned relationship sets which involved these deleted tuples will have to be updated.
Note that if the tabular representation of a relationship set is obtained by taking a union of the primary keys of the participating entity sets, no modification to these relationship sets is required.
The problem caused by loans or accounts with the same number in both the banks is similar to the problem caused by branches in both the banks with the same branch-name. To solve the problems caused by the merger, no schema changes are required. Merge the customer entity sets removing duplicate tuples with the same social- security field.
Before merging the branch entity sets, prepend the old bank name to the branch-name attribute in each tuple. The employee entity sets can be merged directly, and so can the payment entity sets.
No duplicate removal should be performed. Before merging the loan and account entity sets, whenever there is a number common in both the banks, the old number is replaced by a new unique number, in one of the banks.
Next the relationship sets can be merged. Any relation in any relationship set which involves a tuple which has been modified earlier due to the merger, is itself modified to retain the same meaning. For example let be a loan number common in both the banks prior to the merger, and let it be replaced by a new unique number in one of the banks, say bank 2. Now all the relations in borrower, loan-branch and loan-payment of bank 2 which refer to loan number will have to be modified to refer to As before, the banks use the schema of Figure 2.
What problems be- yond those identified in Exercise 2. How would you resolve them? Be sure to consider both the scheme and the ac- tual data values in constructing your answer. Answer: This is a case in which the schemas of the two banks differ, so the merger becomes more difficult. The identifying attribute for persons in the US is social-security, and in Canada it is social-insurance. Therefore the merged schema cannot use either of these. Instead we introduce a new attribute person-id, and use this uniformly for everybody in the merged schema.
No other change to the schema is required. The values for the person-id attribute may be obtained by several ways. Another way would be to assign fresh numbers starting from 1 upwards, one number to each social-security and social- insurance value in the old databases.
Exercises 27 Once this has been done, the actual merger can proceed as according to the answer to the previous question. If a particular relationship set, say borrower, 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, and mak- ing only us-customer participate in the merged borrower.
Similarly employee can be specialized if needed. The rela- tional model Section 3. The chapter also covers the tuple relational calculus Section 3. Classes that emphasize only SQL may omit the relational calculus languages.
Our notation for the tuple relational calculus makes it easy to present the con- cept of a safe query. The concept of safety for the domain relational calculus, though identical to that for the tuple calculus, is much more cumbersome notationally and requires careful presentation.
This consideration may suggest placing somewhat less emphasis on the domain calculus for classes not planning to cover QBE. Section 3. The evolution of query languages such as SQL clearly indicates the importance of such extended operations. We have chosen not to present such extensions to the relational calculus, and instead restrict our attention to exten- sions of the algebra. E-R diagram. Exercises 3. The office main- tains data about each class, including the instructor, the number of students enrolled, and the time and place of the class meetings.
For each student— class pair, a grade is recorded. Answer: Underlined attributes indicate the primary key. Illustrate your answer by referring to your solution to Exercise 3. Answer: A relation schema is a type definition, and a relation is an instance of that schema. For example, student ss , name is a relation schema and ss name Tom Jones Joe Brown is a relation based on that schema.
Answer: The relational database schema is given below. Relational database for Exercises 3. Explain how primary keys help us to represent such relationship sets in the relational model. Then a re- lationship between the 2 sets can be represented as a tuple Ai1 , Ai2 , In a many- to-one relationship e. Give an expression in the relational algebra to express each of the fol- lowing queries: a.
Find the names of all employees who work for First Bank Corporation. Find the names and cities of residence of all employees who work for First Bank Corporation. Find the names of all employees in this database who live in the same city as the company for which they work.
Find the names of all employees who live in the same city and on the same street as do their managers. Find the names of all employees in this database who do not work for First Bank Corporation. Find the names of all employees who earn more than every employee of Small Bank Corporation. Assume the companies may be located in several cities. Find all companies located in every city in which Small Bank Corporation is located.
The following solutions assume that all people work for exactly one com- pany. If one allows people to appear in the database e. We give solutions for this more realistic case later. Note: Small Bank Corporation will be included in each answer. Observe that now customer Jackson no longer appears in the result, even though Jackson does in fact have a loan from the bank. Explain why Jackson does not appear in the result.
Suppose that you want Jackson to appear in the result. How would you modify the database to achieve this effect? Again, suppose that you want Jackson to appear in the result. Write a query using an outer join that accomplishes this desire without your having to modify the database. Although Jackson does have a loan, no address is given for Jackson in the customer relation.
Since no tuple in customer joins with the Jackson tuple of borrower, Jackson does not appear in the result. If the address is unknown, null values may be used. The special value chosen must not be a plausible name for an actual city or street. Exercises 33 c. Describe how the theta join operation can be extended so that tuples from the left, right, or both relations are not lost from the result of a theta join. Give an expression in the rela- tional algebra for each request: a.
Modify the database so that Jones now lives in Newtown. Give all employees of First Bank Corporation a 10 percent salary raise. Give all managers in this database a 10 percent salary raise. In such cases, give only a 3 percent raise. Delete all tuples in the works relation for employees of Small Bank Corpora- tion.
The update syntax allows reference to a single relation only. Since this up- date requires access to both the relation to be updated works and the man- ages relation, we must use several steps. First we identify the tuples of works to be updated and store them in a temporary relation t1.
Then we create a temporary relation containing the new tuples t2. Finally, we delete the tuples in t1 , from works and insert the tuples of t2. The same situation arises here. As before, t1 , holds the tuples to be updated and t2 holds these tuples in their updated form. Using an aggregate function.
Without using any aggregate functions. Give a relational-algebra expres- sion for each of the following queries: a. Find the company with the most employees. Find the company with the smallest payroll. Find those companies whose employees earn a higher salary, on average, than the average salary at First Bank Corporation.
Security conditions may require that the entire logical database be not visi- ble to all users. Answer: Views present significant problems if updates are expressed with them.
The difficulty is that a modification to the database expressed in terms of a view must be translated to a modification to the actual relations in the logical model of the database. Since the view may not have all the attributes of the underlying tables, in- sertion of a tuple into the view will insert tuples into the underlying tables, with those attributes not participating in the view getting null values.
This may not be desirable, especially if the attribute in question is part of the primary key of the table. If a view is a join of several underlying tables and an insertion results in tuples with nulls in the join columns, the desired effect of the insertion will not be achieved. In other words, an update to a view may not be expressible at all as updates to base relations. For an explanatory example, see the loan- info updation example in Section 3.
Give an expression in the tuple relational calculus that is equivalent to each of the following: a. Give an expression in the domain relational calculus that is equivalent to each of the following: a. Find the names of all employees who work for First Bank Corporation:- i.
Find the names and cities of residence of all employees who work for First Bank Corporation:- i. Find the names of all employees in this database who live in the same city as the company for which they work:- i. Find the names of all employees who live in the same city and on the same street as do their managers:- i.
Find the names of all employees in this database who do not work for First Bank Corporation:- If one allows people to appear in the database e. Find the names of all employees who earn more than every employee of Small Bank Corporation:- i. Using the special constant null, write tuple-relational-calculus expressions equivalent to each of the following: a. Answer: Nulls may be introduced into the database because the actual value is either unknown or does not exist.
For example, an employee whose address has changed and whose new address is not yet known should be retained with a null address. One application of marked nulls is to allow certain updates through views.
Consider the view loan-info Section 3. Extensions provided by SQL are covered later in Chapters 9 and Integrity constraint and authorization features of SQL are described in Chapter 6. SQL being a large language, many of its features are not covered here, and are not appropriate for an introductory course on databases. Standard books on SQL, such as Date and Darwen [] and Melton and Simon [], or the system manuals of the database system you use can be used as supplements for students who want to delve deeper into the intricacies of SQL.
Although it is possible to cover this chapter using only handwritten exercises, we strongly recommend providing access to an actual database system that supports SQL. A style of exercise we have used is to create a moderately large database and give students a list of queries in English to write and run using SQL. We publish the actual answers that is the result relations they should get, not the SQL they must en- ter. This approach allows students to check their own answers for correctness immediately rather than wait for grading and thereby it speeds up the learning process.
A few such example databases are available on the Web home page of this book. Exercises that pertain to database design are best deferred until after Chapter 7. Given the fact that the ODBC and JDBC protocols are fast becoming a primary means of accessing databases, we have significantly extended our coverage of these two protocols, including some examples.
However, our coverage is only introduc- tory, and omits many details that are useful in practise. Construct the following SQL queries for this relational database. Find the total number of people who owned cars that were involved in ac- cidents in Add a new accident to the database; assume any values for required at- tributes. Answer: Note: The participated relation relates drivers, cars, and accidents.
Note: this is not the same as the total number of accidents in We must count people with several accidents only once. First we must find the license of the given car. Then the participated and accident relations must be updated in order to both record the accident and tie it to the given car. Exercises 43 person driver-id, name, address car license, model, year accident report-number, date, location owns driver-id, license participated driver-id, car, report-number, damage-amount Figure 4.
Insurance database. Again assume name is a key for person. Give an expression in SQL for each of the following queries. Find all employees in the database who live in the same cities as the com- panies for which they work. Find all employees in the database who live in the same cities and on the same streets as do their managers.
Find all employees in the database who do not work for First Bank Corpo- ration. Find all employees in the database who earn more than each employee of Small Bank Corporation. Assume that the companies may be located in several cities. Find all com- panies located in every city in which Small Bank Corporation is located. Find all employees who earn more than the average salary of all employees of their company.
Find the company that has the most employees. Find the company that has the smallest payroll. Exercises 45 select e. The following solution assumes that all people work for exactly one com- pany. Find all employees in the database who earn more than every employee of Small Bank Corporation. The following solution assumes that all people work for at most one com- pany.
It can be solved by using a nested subquery, but we illustrate below how to solve it using the with clause. The simplest solution uses the contains comparison which was included in the original System R Sequel language but is not present in the subse- quent SQL versions.
Exercises 47 employee employee-name, street, city works employee-name, company-name, salary company company-name, city manages employee-name, manager-name Figure 4. Employee database. Give all employees of First Bank Corporation a 10 percent raise. Give all managers of First Bank Corporation a 10 percent raise. Answer: The solution for part 0.
The solutions to parts 0. Give all employees of First Bank Corporation a percent raise. Give all managers of First Bank Corporation a percent raise. Give an expression in SQL that is equivalent to each of the following queries. A, r2. B, r3. C from r1, r2 where r1. Write an expression in SQL for each of the queries below: a.
C from r, s where r. A and s. A and e. Thus x1 is not a member of S and must satisfy x1 not in S. Similarly, suppose there is a particular value x2 which satisfies x2 not in S.
Therefore the two expressions are equivalent. Using SQL, define a view con- sisting of manager-name and the average salary of all employees who work for that manager. Explain why the database system should not allow updates to be expressed in terms of this view. Answer: create view salinfo as select manager-name, avg salary from manages m, works w where m. Neither approach really makes sense. Examine carefully the cases where one of r1 or r2 may be empty.
Answer: The query selects those values of p. Of course if p itself is empty, the result is as expected, i. Using a nested query in the from clauser. Using a nested query in a having clause.
Answer: We output the branch names along with the total account deposit at the branch. Write SQL queries to do the following: a. Display the grade for each student, based on the marks relation. Find the number of students with each grade. Answer: We use the case operation provided by SQL a. 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.
Show how to express the coa- lesce operation using the case operation. Answer: case when A1 is not null then A1 when A2 is not null then A Show how to express a natural full outer join b using the full outer join operation with an on condition and the coalesce operation.
Make sure that the result relation does not contain two copies of the attributes name and address, and that the solution is correct even if some tuples in a and b have null values for attributes name or address.
Answer: select coalesce a. Choose an appropriate domain for each attribute and an appropriate primary key for each relation schema. Every employee works for a company located in the same city as the city in which the employee lives. No employee earns a salary higher than that of his manager. Hence the renaming of the employee-name attribute to emp-name. Under these circumstances, it is more natural to use assertions, which are introduced in Chapter 6.
Answer: Writing queries in SQL is typically much easier than coding the same queries in a general-purpose programming language. However not all kinds of queries can be written in SQL. Also nondeclarative actions such as printing a report, interacting with a user, or sending the results of a query to a graphical user interface cannot be done from within SQL.
Under circumstances in which we want the best of both worlds, we can choose embedded SQL or dynamic SQL, rather than using SQL alone or using only a general-purpose programming language.
QBE, based on the domain relational calculus, forms the basis for query languages sup- ported by a large number of database systems designed for personal computers, such as Microsoft Access, FoxPro, etc. The description here will have to be supplemented by material from the user guides of the specific database system being used. One of the points to watch out for is the precise semantics of aggregate operations, which is particularly non-standard.
The Datalog language has several similarities to Prolog, which some students may have studied in other courses. Datalog differs from Prolog in that its semantics is purely declarative, as opposed to the operational semantics of Prolog. It is important to emphasize the differences, since the declarative semantics enables the use of effi- cient query evaluation strategies. There are several implementations of Datalog avail- able in the public domain, such as the Coral system from the University of Wisconsin — Madison, and XSB from the State University of New York, Stony Brook, which can be used for programming exercises.
The Coral system also supports complex objects such as nested relations covered later in Chapter 9. Changes from 3rd edition: The syntax and semantics of QBE aggregation and update have been changed to simplify the semantics and to remove some ambiguities in the earlier semantics. Quel has been dropped. Construct the following QBE queries for this relational-database. Answer: The participated relation relates car s and accidents. ALL c.
Give expressions in QBE, and Datalog for each of the following queries: a. Find all employees who live in the same city as the company for which they work is located. Find all employees who live in the same city and on the same street as their managers. Find all employees who earn more than every employee of Small Bank Cor- poration. Find all employees who live in the city where the company for which they work is located. The following solutions assume that all people work for at most one com- pany.
Give expressions in QBE for each of the following queries: a. Give all managers in the database a 10 percent raise. Answer: The solutions assume that each person has only one tuple in the em- ployee relation.
Newtown b. Give all managers in the database a percent raise. In such cases, give only a 3-percent raise. Two separate update operations must be performed.
Each update operation has its own set of skeleton tables. First update: manages person-name manager-name x works person-name company-name salary x y U. Small Bank Co 5. Give expressions in QBE, and Datalog equiv- alent to each of the following queries: a. Give expres- sions in QBE, and Datalog equivalent to each of the following queries: a. Write expres- sions in QBE and Datalog for each of the following queries: a.
Write a Datalog program for each of the following queries: a. Find all pairs of employees who have a direct or indirect manager in com- mon. Find all pairs of employees who have a direct or indirect manager in com- mon, and are at the same number of levels of supervision below the com- mon manager.
Answer: Let us assume that q1, q2 and q3 are instances of the schema A1, A2. Answer: A Datalog rule has two parts, the head and the body. The body is a comma separated list of literals. A positive literal has the form p t1 , t2 ,. We consider only safe rules; see Section 5. 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 to in the positive non-arithmetic literals in the body, followed by a selection. The selection condition is a conjunction obtained as follows.
C should belong to the conjunction. The arithmetic literals can then be added to the condition. First suppose that there are no constants in the negative literals; recall that all variables in a negative literal must also occur in a positive literal.
Let Ei be the relational algebra expression obtained after all positive and arithmetic literals have been handled. Now let us consider constants occurring in a negative literal. Proceeding in a similar fashion, the remaining negative literals are processed, finally resulting in an expression Ew. Finally the desired attributes are projected out of the expression.
The at- tributes in Ew corresponding to the variables in the head of the rule become the projection attributes. The above conversion can be extended to handle rules that satisfy some weaker forms of the safety conditions, and where some restricted cases where the vari- ables in arithmetic predicates do not appear in a positive non-arithmetic literal.
C H A P T E R 6 Integrity and Security This chapter presents several types of integrity constraints, including domain con- straints, referential integrity constraints, assertions and triggers, as well as security and authorization. Referential integrity constraints, and domain constraints are an important aspect of the specification of a relational database design.
Assertions are seeing increasing use. Triggers are widely used, although each database supports its own syntax and semantics for triggers; triggers were standardized as part of SQL, and we can expect databases to provide support for SQL triggers. Functional dependencies are now taught as part of normalization instead of be- ing part of the integrity constraints chapter as they were in the 3rd edition.
The rea- son for the change is that they are used almost exclusively in database design, and no database system to our knowledge supports functional dependencies as integrity constraints. Covering them in the context of normalization helps motivate students to spend the effort to understand the intricacies of reasoning with functional depen- dencies.
Security is a major topic in its own right. Since any system is only as secure as its weakest component, a system builder must consider all aspects of security. This chapter focuses only on those security issues that are specific to databases. In an advanced course, this material can be supplemented by discussion of security issues in operating systems and in distributed systems.
Changes from 3rd edition: Trigger coverage is now based on the SQL standard. At the time of publica- tion of the 3rd edition, triggers had not been standardized. The notion of roles for authorization has been introduced in this edition, now that it is a part of the SQL standard. Coverage of encryption has been updated to cover recent developments. Answer: create table loan loan-number char 10 , branch-name char 15 , amount integer, primary key loan-number , foreign key branch-name references branch create table borrower customer-name char 20 , loan-number char 10 , primary key customer-name, loan-number , foreign key customer-name references customer, foreign key loan-number references loan Declaring the pair customer-name, loan-number of relation borrower as primary key ensures that the relation does not contain duplicates.
Identify referential-integrity con- straints that should hold, and include them in the DDL definition. Other choices for not null at- tributes may be acceptable. Consider a database that includes the following relations: salaried-worker name, office, phone, salary hourly-worker name, hourly-wage address name, street, city Suppose that we wish to require that every name that appears in address appear in either salaried-worker or hourly-worker, but not necessarily in both.
Propose a syntax for expressing such constraints. Discuss the actions that the system must take to enforce a constraint of this form. For simplicity, we present a variant of the SQL syntax. As part of the create table expression for address we include foreign key name references salaried-worker or hourly-worker b. Navathe, Ramez Elmasri. This pdf of DBMS introduces the fundamental concepts necessary for designing, using, and implementing database systems and database applications.
The PDF is written so that it is possible to cover topics in various sequences. The chapter dependency chart below shows the major dependencies among chapters. As the diagram illustrates, it is possible to start with several different topics following the first two introductory chapters.
Although the chart may seem complex, it is important to note that if the chapters are covered in order, the dependencies are not lost. You can get the link to download this from here:.
Database system concepts by Henry F. This text is intended for a first course in databases at the junior or senior undergraduate, or first-year graduate, level. In addition to basic material for a first course, the text contains advanced material that can be used for course supplements, or as introductory material for an advanced course.
The fundamental concepts and algorithms covered in the PDF are often based on those used in existing commercial or experimental database systems. This PDF is intended as a textbook for a one- or two-semester course in database management or database design in an introductory undergraduate course, a graduate or advanced undergraduate course.
The PDF is intended as a reference book for IT professionals, such as systems analysts or designers, application programmers, systems programmers, database practitioners, and independent self-teachers. Important theoretical results are covered, but formal proofs are omitted. In place of proofs, figures and examples are used to suggest why a result is true. Your email address will not be published. Save my name, email, and website in this browser for the next time I comment.
0コメント