Revision for Midterm 3 Part 3Slide 2Set OperatorsUnion Compatible RelationsExampleCartesian ProductRenaming in Cartesian ProductRenaming OperatorExampleDerived Operation: JoinTheta Join – ExampleRelational AlgebraEquijoin Join - ExampleNatural JoinNatural Join (cont’d)Natural Join ExampleExample Data InstanceNatural Join and IntersectionDivisionDivision Using Our Existing OperatorsDivision: R1 ¸ R2Slide 22Division (cont’d)Division - ExampleRelational CalculusTuple Relational CalculusGeneric FormSimple example 1Simple example 2Elements of a tuple calculusMore Example:Q0Formal Specification of tuple Relational CalculusElements of formulaExample Queries Using the Existential QuantifierMore ExampleCont.Logical EquivalencesNormalizationSlide 39Functional Dependencies1. ClosureArmstrong’s AxiomsAdditional rulesSlide 442. Closure of an attribute setComputing the closure for ASlide 47Uses of attribute set closuresSlide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70BCNFSlide 72Achieving BCNF SchemasExample 1Example 2-1Example 2-2Example 3Revision for Midterm 3 Part 3Prof. Sin-Min LeeDepartment of Computer ScienceSet Operators•Relation is a set of tuples, so set operations should apply: , , (set difference)•Result of combining two relations with a set operator is a relation; hence all its elements must be tuples having the same structure•Hence, scope of set operations limited to union compatible relationsunion compatible relationsUnion Compatible Relations•Two relations are union compatibleunion compatible if–Both have same number of columns–Names of attributes are the same in both–Attributes with the same name in both relations have the same domain•Union compatible relations can be combined using unionunion, intersectionintersection, and setset differencedifferenceExampleTables: PersonPerson (SSN, Name, Address, Hobby) ProfessorProfessor (Id, Name, Office, Phone)are not union compatible. But Name (PersonPerson) and Name (ProfessorProfessor)are union compatible so Name (PersonPerson) - Name (ProfessorProfessor)makes sense.Cartesian Product•If RR and SS are two relations, RR SS is the set of all concatenated tuples <x,y>, where x is a tuple in RR and y is a tuple in S S (but see naming problem next)(but see naming problem next)•RR SS is expensive to compute:–Factor of two in the size of each row–Quadratic in the number of rows A B C D A B C D x1 x2 y1 y2 x1 x2 y1 y2 x3 x4 y3 y4 x1 x2 y3 y4 x3 x4 y1 y2 RR SS x3 x4 y3 y4 RR SSRenaming in Cartesian ProductResult of expression evaluation is a relation.Attributes of relation must have distinct names. So what do we do if they don’t?E.g., suppose R(A,B) and S(A,C) and we wish to compute RR SS .One solution is to rename the attributes of the answer:RR S( R.A, R.B, S.A, S.C)S( R.A, R.B, S.A, S.C)Although onlyAlthough only A A needs to be renamed, it is“cleaner” to needs to be renamed, it is“cleaner” to rename them all.rename them all.Renaming Operator•Previous solution is used whenever possible but it won’t work when R is the same as S.•Renaming operator resolves this. It allows to assign any desired names, say A1, A2,… An , to the attributes of the n column relation produced by expression expr with the syntax expr [A1, A2, … An]Example This is a relation with 4 attributes: StudId, CrsCode1, ProfId, CrsCode2TranscriptTranscript (StudId, CrsCode, Semester, Grade)TeachingTeaching (ProfId, CrsCode, Semester) StudId, CrsCode (TranscriptTranscript)[StudId, CrsCode1] ProfId, CrsCode(TeachingTeaching) [ProfId, CrsCode2]Derived Operation: JoinA (generalgeneral or thetatheta) join join of R and S is the expression R join-condition Swhere join-condition is a conjunction of terms: Ai oper Biin which Ai is an attribute of R; Bi is an attribute of S; and oper is one of =, <, >, , . The meaning is: join-condition´ (R S) where join-condition and join-condition´ are the same, except for possible renamings of attributes caused by the Cartesian product.Theta Join – Example Employee(Employee(Name,Id,MngrId,SalaryName,Id,MngrId,Salary) Manager(Manager(Name,Id,SalaryName,Id,Salary)Output the names of all employees that earnmore than their managers.EmployeeEmployee.Name (EmployeeEmployee MngrId=Id AND Salary>Salary ManagerManager)The join yields a table with attributes: EmployeeEmployee.Name, EmployeeEmployee.Id, EmployeeEmployee.Salary, Employee.MngrIdManagerManager.Name, ManagerManager.Id, ManagerManager.SalaryRelational Algebra•Relational algebra operations operate on relations and produce relations (“closure”)f: Relation -> Relation f: Relation x Relation -> Relation•Six basic operations: –Projection (R)–Selection (R)–Union R1 [ R2–Difference R1 – R2–Product R1 £ R2–(Rename) (R)Equijoin Join - Example Name,CrsCode(StudentStudent Id=StudId Grade=‘A’ (TranscriptTranscript))Id Name Addr Status111 John ….. …..222 Mary ….. …..333 Bill ….. …..444 Joe ….. …..StudId CrsCode Sem Grade 111 CSE305 S00 B 222 CSE306 S99 A 333 CSE304 F99 AMary CSE306Bill CSE304The equijoin is used veryfrequently since it combinesrelated data in different relations.StudentStudentTranscriptTranscriptEquijoinEquijoin: Join condition is a conjunction of equalities.Natural Join•Special case of equijoin + a special projection –join condition equates all and only those attributes with the same name (condition doesn’t have to be explicitly stated)–duplicate columns eliminated (projected out) from the resultTranscriptTranscript (StudId, CrsCode, Sem, Grade)Teaching (Teaching (ProfId, CrsCode, Sem)TranscriptTranscript TeachingTeaching = StudId, Transcript.CrsCode, Transcript.Sem, Grade, ProfId ( TranscriptTranscript CrsCode=CrsCode AND Sem=Sem Sem Teaching Teaching ) [StudId, CrsCode, Sem, Grade, ProfId ]Natural Join (cont’d)•More generally:RRSS = attr-list (join-cond (RR × SS) )where attr-list = attributes (RR) attributes (SS)(duplicates are eliminated) and join-cond has the form: A1 = A1 AND … AND An
View Full Document
Unlocking...