《數(shù)據(jù)庫系統(tǒng)》教學(xué)課件

《數(shù)據(jù)庫系統(tǒng)》教學(xué)課件,數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)庫,系統(tǒng),教學(xué),課件 Relational CalculusJianlin FengSchool of SoftwareSUN YAT-SEN UNIVERSITYcourtesy of Joe Hellerstein for some slidesRelational CalculusnQuery has the form:T|p(T)qT is a tuple variable.qp(T)is a formula containing T.nAnswer =tuples T for which p(T)=true.FormulaenAtomic formulae:T Relation T.a op T.bT.a op constant op is one of nA formula can be:q an atomic formulaq q q Free and Bound VariablesnQuantifiers:and nUse of or binds X.qA variable that is not bound is free.nRecall our definition of a query:qT|p(T)Important restriction:T must be the only free variable in p(T).all other variables must be bound using a quantifier.Simple QueriesnFind all sailors with rating above 7 nFind names and ages of sailors with rating above 7.qNote:S is a variable of 2 fields(i.e.S is a projection of Sailors)S|S Sailors S.rating 7S|S1 Sailors(S1.rating 7 S.sname=S1.sname S.age=S1.age)Find sailors rated 7 whove reserved boat#103 S|SSailors S.rating 7 R(RReserves R.sid=S.sid R.bid=103)JoinsJoins(continued)This may look cumbersome,but its not so different from SQL!S|SSailors S.rating 7 R(RReserves R.sid=S.sid B(BBoats B.bid=R.bid B.color=red)Find sailors rated 7 whove reserved a red boatUniversal QuantificationFind sailors whove reserved all boats S|SSailors BBoats(RReserves (S.sid=R.sid B.bid=R.bid)A trickier example S|SSailors B Boats(B.color=red R(RReserves S.sid=R.sid B.bid=R.bid)Find sailors whove reserved all Red boats S|SSailors B Boats(B.color red R(RReserves S.sid=R.sid B.bid=R.bid)Alternativelya b is the same as a baTFT FbTTTFA Remark:Unsafe Queriesn syntactically correct calculus queries that have an infinite number of answers!Unsafe queries.qe.g.,qSolution?Dont do that!Expressive PowernExpressive Power(Theorem due to Codd):qEvery query that can be expressed in relational algebra can be expressed as a safe query in relational calculus;the converse is also true.nRelational Completeness:Query language(e.g.,SQL)can express every query that is expressible in relational algebra/calculus.(actually,SQL is more powerful,as we will see)SummarynFormal query languages simple and powerful.qRelational algebra is operationalnused as internal representation for query evaluation plans.qRelational calculus is“declarative”nquery=“what you want”,not“how to compute it”qSame expressive power-relational completeness.nSeveral ways of expressing a given queryqa query optimizer should choose the most efficient version.Your turn nSchema:Movie(title,year,studioName)ActsIn(movieTitle,starName)Star(name,gender,birthdate,salary)nQueries to write in Relational Calculus:1.Find all movies by Paramount studio2.movies whose stars are all women3.movies starring Kevin Bacon4.Find stars who have been in a film w/Kevin Bacon5.Stars within six degrees of Kevin Bacon*6.Stars connected to K.Bacon via any number of films*Try two degrees for starters *Good luck with this one!Answers 1.Find all movies by Paramount studioM|MMovie M.studioName=ParamountAnswers 2.Movies whose stars are all womenM|MMovie AActsIn(A.movieTitle=M.title)SStar(S.name=A.starName S.gender=F)Answers 3.Movies starring Kevin BaconM|MMovie AActsIn(A.movieTitle=M.title A.starName=Bacon)Answers 4.Stars who have been in a film w/Kevin BaconS|SStar AActsIn(A.starName=S.name A2ActsIn(A2.movieTitle=A.movieTitle A2.starName=Bacon)moviestarA2:S:nameBaconmoviestarA:Answers 5.Stars within six degrees of Kevin BaconS|SStar AActsIn(A.starName=S.name A2ActsIn(A2.movieTitle=A.movieTitle A3ActsIn(A3.starName=A2.starName A4ActsIn(A4.movieTitle=A3.movieTitle A4.starName=Bacon)twoTwo degrees:S:nameBaconmoviestarA2:moviestarA:moviestarA4:moviestarA3:Answers 6.Stars connected to K.Bacon via any number of filmsSorry that was a trick questionNot expressible in relational calculus!What about in relational algebra?We will be able to answer this question shortly