07.05 division

1. DBMS Relational Algebra Division Bishal Ghimire [email protected]

2. Division Division is not essential operation ; just a useful shorthand. Also true of joins, but joins are so common that systems implement joins specially. Division is NOT implemented in SQL. Not supported as a primitive operator, but useful for many expressing queries Precondition: in A/B, the attributes in B must be included in the schema for A. Also, the result has attributes A-B. SALES( supId , prodId ); PRODUCTS( prodId ); Relations SALES and PRODUCTS must be built using projections. SALES/PRODUCTS: the ids of the suppliers supplying ALL products

3. The division is a binary operation that is written as  R  ÷  S The result consists of the restrictions of tuples in  R  to the attribute names unique to  R The header of  R  but not in the header of  S , for which it holds that all their combinations with tuples in  S  are present in  R

4. Student Task Fred Database1 Fred Database2 Fred Compiler1 Eugene Database1 Eugene Compiler1 Sarah Database1 Sarah Database2 Completed DBProject Task Database1 Database2 Completed ÷ DBProject Student Fred Sarah

5. Expressing A/B Using Basic Operators For SALES/PRODUCTS , compute all products such that there exists at least one supplier not supplying it. x value is disqualified if by attaching y value from B , we obtain an xy tuple that is not in A . The answer is  sid (Sales) - A

6. sNo pNo s1 p1 s1 p2 s1 p3 s1 p4 s2 p1 s2 p2 s3 p2 s4 p2 s4 p4 pNo p2 A B1 A/B1 sNo s1 s2 s3 s4

7. sNo pNo s1 p1 s1 p2 s1 p3 s1 p4 s2 p1 s2 p2 s3 p2 s4 p2 s4 p4 pNo p2 p4 A B2 A/B2 sNo s1 s4

8. sNo pNo s1 p1 s1 p2 s1 p3 s1 p4 s2 p1 s2 p2 s3 p2 s4 p2 s4 p4 pNo p1 p2 p4 A B3 A/B3 sNo s1

9. Query type : Find the subset of items in one set that are related to all items in another set Example : Find professors who taught courses in all departments Why does this involve division? Contains row < p,d > if professor p taught a course in department d  ProfId,DeptId (Teaching Course) /  DeptId (Department) ProfID DeptID

10. Suppose that employees of the company are assigned to some professional courses; each employee follows several courses and each course is taken by several employees Information about courses and which employee takes which course can be represented by the following relations Takes ( Emp #, Course#) Courses (Course#, Topic, Weeks)

11. Assume that these two relations have the following content Emp # Course# 7369 10 7369 20 7369 30 7782 10 7782 40 Course# Topics Weeks 20 CAD 5 10 DB 3 30 DB 2 40 OS 4 Takes Courses

12. Consider the following query: “determine the emp # of the employees taking all the courses with topic DB” (Q1) The course# of the courses relevant to the query is obtained through the following expression: R1 = ∏ Course# ( σ Topic=“DB” ) (Courses)) The result of such query is {10, 30}

13. The result of query Q1 is represented by all the employees that appear in the Takes relation with each of the course numbers retrieved by query R1 The correct result of Q1 is thus {7369} The operation that allows one to execute such query is the division