RELATIONAL ALGEBRA (III)Slide 2Slide 3Unary Relational Operations: SELECT and PROJECTRelational Algebra Operations from Set TheoryBinary Relational Operations: JOIN and DIVISIONAdditional Relational OperationsSPECIAL RELATIONAL OPERATORSJOIN OPERATORSSlide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Functional DependencyFunctional DependenciesA®C, but not C®AMinimal cover: AB, DB {A, B, C, D} is a candidate keySlide 25Slide 26ClosureSlide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Minimal coverSlide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Candidate Keys… candidate keykeys and dependenciesSlide 48Trivial Functional DependencyRELATIONAL ALGEBRA RELATIONAL ALGEBRA (III)(III)Prof. Sin-Min LEEProf. Sin-Min LEEDepartment of Computer Department of Computer ScienceScienceUnary Relational Operations: SELECT and Unary Relational Operations: SELECT and PROJECTPROJECTThe PROJECT OperationThe PROJECT OperationSequences of Operations and the Sequences of Operations and the RENAME OperationRENAME OperationThe SELECT OperationThe SELECT OperationRelational Algebra Operations from Set Relational Algebra Operations from Set TheoryTheoryThe UNION, INTERSECTION, and The UNION, INTERSECTION, and MINUS OperationsMINUS OperationsThe CARTESIAN PRODUCT (or CROSS The CARTESIAN PRODUCT (or CROSS PRODUCT) OperationPRODUCT) OperationBinary Relational Operations: JOIN and Binary Relational Operations: JOIN and DIVISIONDIVISIONThe JOIN OperationThe JOIN OperationThe EQUIJOIN and NATURAL JOIN The EQUIJOIN and NATURAL JOIN Variations of JOINVariations of JOINA Complete Set of Relational Algebra A Complete Set of Relational Algebra OperationsOperationsThe DIVISION OperationThe DIVISION OperationAdditional Relational OperationsAdditional Relational OperationsAggregate Functions and GroupingAggregate Functions and GroupingRecursive Closure OperationsRecursive Closure OperationsOUTER JOIN OperationsOUTER JOIN OperationsThe OUTER JOIN OperationThe OUTER JOIN OperationSPECIAL RELATIONAL OPERATORSSPECIAL RELATIONAL OPERATORSThe following operators are peculiar to relations:The following operators are peculiar to relations:- - Join operatorsJoin operatorsThere are several kind of join operators. We only consider There are several kind of join operators. We only consider three of these here (others will be considered when we three of these here (others will be considered when we discuss null values):discuss null values):- (1) Condition Joins- (1) Condition Joins- (2) Equijoins- (2) Equijoins- (3) Natural Joins- (3) Natural Joins- - DivisionDivisionJOIN OPERATORSJOIN OPERATORS Condition Joins: Condition Joins: - Defined as a cross-product followed by a selection:- Defined as a cross-product followed by a selection: R R ⋈⋈cc S = S = σσcc(R (R S) ( S) ( is called the ⋈ is called the ⋈bow-tie)bow-tie)where c is the condition.where c is the condition.- - Example:Example:Given the sample relational instances S1 and R1Given the sample relational instances S1 and R1The condition join S ⋈S1.sid<R1.sid R1 yieldsJOIN OPERATORSJOIN OPERATORS Condition Joins: Condition Joins: - Defined as a cross-product followed by a selection:- Defined as a cross-product followed by a selection: R R ⋈⋈cc S = S = σσcc(R (R S) ( S) ( is called the ⋈ is called the ⋈bow-tie)bow-tie)where c is the condition.where c is the condition.- - Example:Example:Given the sample relational instances S1 and R1Given the sample relational instances S1 and R1The condition join S ⋈S1.sid<R1.sid R1 yieldsEquijoinEquijoin::Special case of the condition join where the join condition consists solely Special case of the condition join where the join condition consists solely of equalities between two fields in R and S connected by the logical of equalities between two fields in R and S connected by the logical AND operator (AND operator ().∧).∧ExampleExample: Given the two sample relational instances S1 and R1: Given the two sample relational instances S1 and R1The operator S1 R.sid=Ssid R1 yieldsNatural JoinNatural Join- Special case of equijoin where equalities are implicitly - Special case of equijoin where equalities are implicitly specified on specified on all all fields having the same name in R and S.fields having the same name in R and S.- The condition c is now left out, so that the “bow tie” - The condition c is now left out, so that the “bow tie” operator by itself signifies a natural join.operator by itself signifies a natural join.- - N. B.N. B. If the two relations have no attributes in common, the If the two relations have no attributes in common, the natural join is simply the cross-product.natural join is simply the cross-product.Functional DependencyFunctional Dependency holds on schema R if, in any holds on schema R if, in any legal relation r(R), for all pairs of legal relation r(R), for all pairs of tuples ttuples t11 and t and t22 in r such that t in r such that t11[[] ] = t= t22[[], it is also the case that t], it is also the case that t11 [[] = t] = t22 [ [].].Functional DependenciesFunctional DependenciesFDs defined over two FDs defined over two sets of attributes: X, sets of attributes: X, Y Y R RNotation: X Notation: X Y reads Y reads as “X determines Y”as “X determines Y”If X If X Y, then all tuples Y, then all tuples that agree on X must that agree on X must also agree on Yalso agree on YX Y Z1 2 32 4 51 2 41 2 72 4 83 7 9RAAC, but not CC, but not CAAAABBCCDDtt00aa11bb11cc11dd11tt11aa11bb22cc11dd22tt22aa22bb22cc22dd22tt33aa22bb22cc22dd33tt44aa33bb33cc33dd44tt55aa44bb33cc33dd44Minimal cover: AMinimal cover: AB, DB, DBB{A, B, C, D} is a candidate key{A, B, C, D} is a candidate keyRR(A(ABBCCD)D)1122112222331133112233113322113311223322X Y Z1 2 32 4 51 2 41 2 72 4 83 7 9X Y ZFunctional Dependencies Functional Dependencies GraphGraph(example)(example)ClosureClosureLet F be a set of functional Let F be a set of functional dependencies.dependencies.The closure of F, denoted by FThe closure of F, denoted by F++, is the , is the set of all functional dependencies set of all functional dependencies logically implied by F.logically implied by F.Minimal coverMinimal coverThe concept of minimal cover of F
View Full Document
Unlocking...