数据库系统概念课后习题答案 Solutions to Practice Exercises6s

C H A P T E R 6 Formal Relational Query Languages Practice Exercises 6.1 Write the following queries in relational algebra, using the university schema. a. Find the titles of courses in the Comp. Sci. department that have 3 credits. b. Find the IDs of all students who were taught by an instructor named Einstein; make sure there are no duplicates in the result. c. Find the highest salary of any instructor. d. Find all instructors earning the highest salary (there may be more than one with the same salary). e. Find the enrollment of each section that was offered in Autumn 2009. f. Find the maximum enrollment, across all sections, in Autumn 2009. g. Find the sections that had the maximum enrollment in Autumn 2009 Answer: a. 5ti tle(sdept name = ’Comp. Sci’ ∧ credits=3(course)) b. 5I D(sI I D = ’Einstein’(takes 1 rt1(IID, course id, section id, semester, year)teaches)) Assuming the set version of the relational algebra is used, there is no need to explicitly remove duplicates. If the multiset version is used, the grouping operator can be used without any agggregation to remove duplicates. For example given relation r (A, B) possibly containing duplicates, A,BG(r ) would return a duplicate free version of the relation. c. Gmax(salary)(instructor ) 1 2 Chapter 6 Formal Relational Query Languages d. instructor 1 (Gmax(salary) as salary (instructor )) Note that the above query renames the maximum salary as salary, so the subsequent natural join outputs only instructors with that salary. e. course id ,section idGcount(∗) as enrollment(syear=2009∧semester=Autumn(takes)) f. t1 ← course id ,section idGcount(∗) as enrollment(syear=2009∧semester=Autumn(takes)) result = Gmax(enrollment)(t1) g. t2 ← Gmax(enrollment) as enrollment(t1) where t1 is as defined in the previous part of the question. result = t1 1 t2 6.2 Consider the relational database of Figure 6.22, where the primary keys are underlined. Give an expression in the relational algebra to express each of the following queries: a. Find the names of all employees who live in the same city and on the same street as do their managers. b. Find the names of all employees in this database who do not work for “First Bank Corporation”. c. Find the names of all employees who earn more than every employee of “Small Bank Corporation”. Answer: a. 5person name ((employee 1 manages) 1(manager name = employee2.person name ∧ employee.street = employee2.street ∧ employee.city= employee2.city)(remployee2 (employee))) b. The following solutions assume that all people work for exactly one company. If one allows people to appear in the database (e.g. in employee) but not appear in works, the problem is more complicated. We give solutions for this more realistic case later. 5person name (scompany name 6= “First Bank Corporation”(works)) If people may not work for any company: 5person name (employee) − 5person name (s (company name = “First Bank Corporation”)(works)) c. 5person name (works) − (5works.person name (works 1 (works.salar y ≤works2.salar y∧works2.company name =“Small Bank Corporation”) rworks2(works))) 6.3 The natural outer-join operations extend the natural-join operation so that tuples from the participating relations are not lost in the result of the join. Exercises 3 Describe how the theta-join operation can be extended so that tuples from the left, right, or both relations are not lost from the result of a theta join. Answer: a. The left outer theta join of r(R) and s(S) (r 1u s) can be defined as (r 1u s) ∪ ((r − 5R(r 1u s)) × (null, null, . . . , null)) The tuple of nulls is of size equal to the number of attributes in S. b. The right outer theta join of r(R) and s(S) (r 1 u s) can be defined as (r 1u s) ∪ ((null, null, . . . , null) × (s − 5S(r 1u s))) The tuple of nulls is of size equal to the number of attributes in R. c. The full outer theta join of r(R) and s(S) (r 1 u s) can be defined as (r 1u s) ∪ ((null, null, . . . , null) × (s − 5S(r 1u s))) ∪ ((r − 5R(r 1u s)) × (null, null, . . . , null)) The first tuple of nulls is of size equal to the number of attributes in R, and the second one is of size equal to the number of attributes in S. 6.4 (Division operation): The division operator of relational algebra, “÷”, is defined as follows. Let r (R) and s(S) be relations, and let S ⊆ R; that is, every attribute of schema S is also in schema R. Then r ÷ s is a relation on schema R − S (that is, on the schema containing all attributes of schema R that are not in schema S). A tuple t is in r ÷ s if and only if both of two conditions hold: • t is in 5R−S(r ) • For every tuple ts in s, there is a tuple tr in r satisfying both of the following: a. tr [S] = ts[S] b. tr [R − S] = t Given the above definition: a. Write a relational algebra expression using the division operator to find the IDs of all students who have taken all Comp. Sci. courses. (Hint: project takes to just ID and course id, and generate the set of all Comp. Sci. course ids using a select expression, before doing the division.) b. Show how to write the above query in relational algebra, without using division. (By doing so, you would have shown how to define the division operation using the other relational algebra operations.) Answer: a. 5I D(5I D,course id (takes) ÷ 5course id (sdept name=’Comp. Sci’(course)) b. The required expression is as follows: r ← 5I D,course id (takes) 4 Chapter 6 Formal Relational Query Languages s ← 5course id (sdept name=’Comp. Sci’(course)) 5I D (takes) − 5I D ((5I D (takes) × s) − r ) In general, let r (R) and s(S) be given, with S ⊆ R. Then we can ex- press the division operation using basic relational algebra operations as follows: r ÷ s = 5R−S (r ) − 5R−S ((5R−S (r ) × s) − 5R−S,S(r )) To see that this expression is true, we observe that 5R−S (r ) gives us all tuples t that satisfy the first condition of the definition of division. The expression on the right side of the set difference operator 5R−S ((5R−S (r ) × s) − 5R−S,S(r )) serves to eliminate those tuples that fail to satisfy the second condition of the definition of division. Let us see how it does so. Consider 5R−S (r ) × s. This relation is on schema R, and pairs every tuple in 5R−S (r ) with every tuple in s. The expression 5R−S,S(r ) merely reorders the attributes of r . Thus, (5R−S (r ) × s) − 5R−S,S(r ) gives us those pairs of tuples from 5R−S (r ) and s that do not appear in r. If a tuple tj is in 5R−S ((5R−S (r ) × s) − 5R−S,S(r )) then there is some tuple ts in s that does not combine with tuple tj to form a tuple in r. Thus, tj holds a value for attributes R − S that does not appear in r ÷ s. It is these values that we eliminate from 5R−S (r ). 6.5 Let the following relation schemas be given: R = (A, B,C) S = (D, E, F ) Let relations r(R) and s(S) be given. Give an expression in the tuple rela- tional calculus that is equivalent to each of the following: a. 5A(r ) b. sB = 17 (r ) c. r × s d. 5A,F (sC = D(r × s)) Answer: a. {t | ∃ q ∈ r (q [A] = t[A])} b. {t | t ∈ r ∧ t[B] = 17} c. {t | ∃ p ∈ r ∃ q ∈ s (t[A] = p[A] ∧ t[B] = p[B] ∧ t[C] = p[C] ∧ t[D] = q [D] ∧ t[E] = q [E] ∧ t[F ] = q [F ])} Exercises 5 d. {t | ∃ p ∈ r ∃ q ∈ s (t[A] = p[A] ∧ t[F ] = q [F ] ∧ p[C] = q [D]} 6.6 Let R = (A, B, C), and let r1 and r2 both be relations on schema R. Give an expression in the domain relational calculus that is equivalent to each of the following: a. 5A(r1) b. sB = 17 (r1) c. r1 ∪ r2 d. r1 ∩ r2 e. r1 − r2 f. 5A,B(r1) 1 5B,C (r2) Answer: a. {< t > | ∃ p, q (< t, p, q > ∈ r1)} b. {< a , b, c > | < a , b, c > ∈ r1 ∧ b = 17} c. {< a , b, c > | < a , b, c > ∈ r1 ∨ < a , b, c > ∈ r2} d. {< a , b, c > | < a , b, c > ∈ r1 ∧ < a , b, c > ∈ r2} e. {< a , b, c > | < a , b, c > ∈ r1 ∧ < a , b, c > 6∈ r2} f. {< a , b, c > | ∃ p, q (< a , b, p > ∈ r1 ∧ < q , b, c > ∈ r2)} 6.7 Let R = (A, B) and S = (A,C), and let r (R) and s(S) be relations. Write expressions in relational algebra for each of the following queries: a. {< a > | ∃ b (< a , b > ∈ r ∧ b = 7)} b. {< a , b, c > | < a , b > ∈ r ∧ < a , c > ∈ s} c. {< a > | ∃ c (< a , c > ∈ s ∧ ∃ b1, b2 (< a , b1 > ∈ r ∧ < c, b2 > ∈ r ∧ b1 > b2))} Answer: a. 5A (sB = 17(r )) b. r 1 s c. 5A (s 1 (5r.A (sr.b= d.b( r × rd (r ))))) 6.8 Consider the relational database of Figure 6.22 where the primary keys are underlined. Give an expression in tuple relational calculus for each of the following queries: a. Find all employees who work directly for “Jones.” b. Find all cities of residence of all employees who work directly for “Jones.” 6 Chapter 6 Formal Relational Query Languages c. Find the name of the manager of the manager of “Jones.” d. Find those employees who earn more than all employees living in the city “Mumbai.” Answer: a. {t | ∃ m ∈ manages (t[person name] = m[person name] ∧ m[manager name] = ’Jones’)} b. {t | ∃ m ∈ manages ∃e ∈ employee(e[person name] = m[person name] ∧ m[manager name] = ’Jones’ ∧ t[city] = e[city])} c. {t | ∃ m1 ∈ manages ∃m2 ∈ manages(m1[manager name] = m2[person name] ∧ m1[person name] = ’Jones’ ∧ t[manager name] = m2[manager name])} d. {t | ∃ w1 ∈ works ¬∃w2 ∈ works(w1[salary] < w2[salary] ∃e2 ∈ employee (w2[person name] = e2[person name] ∧ e2[city] = ’Mumbai’))} 6.9 Describe how to translate join expressions in SQL to relational algebra. Answer: A query of the form select A1, A2, . . . , An from R1, R2, . . . , Rm where P can be translated into relational algebra as follows: 5A1,A2,...,An(sP (R1 × R2 × . . . × Rm)) An SQL join expression of the form R1 natural join R2 can be written as R1 1 R2. An SQL join expression of the form R1 join R2 on (P) can be written as R1 1P R2. Exercises 7 An SQL join expression of the form R1 join R2 using (A1, A2, . . . , An) can be written as 5S(R1 1R1.A1=R2.A1 ∧ R1.A2=R2.A2 ∧ ... R1.An=R2.An R2) where S is A1, A2, . . . , An followed by all attributes of R1 other than R1.A1, R1.A2, . . . , R1.An, followed by all attributes of R2 other than R2.A1, R2.A2, . . . , R2.An, The outer join versions of the SQL join expressions can be similarly written by using 1,1 and 1 in place of 1.1 The most direct way to handle subqueries is to extend the relational algebra. To handle where clause subqueries, we need to allow selection predicates to contain nested relational algebra expressions, which can reference correla- tion attributes from outer level relations. Scalar subqueries can be similarly translated by allowing nested relational algebra expressions to appear in scalar expressions. An alternative approach to handling such subqueries used in some database systems, such as Microsoft SQL Server, introduces a new relational algebra operator called the Apply operator; see Chapter 30, page 1230-1231 for details. Without such extensions, translating subqueries into standard relational algebra can be rather complicated. 1The case of outer joins with the using clause is a little more complicated; with a right outer join it is possible that R1.A1 is null, but R2.A1 is not, and the output should contain the non-null value. The SQL coalesce function can be used, replacing S by coalesce(R1.A1, R2.A1), coalesce(R1.A2, R2.A2), . . . coalesce(R1.An, R2.An), followed by the other attributes of R1 and R2.