搜索
Chp5AlgebraicandLogicalQueryLanguagesInthischapter,weextendtheset-basedalgebratobags,whichbetterreflectthewaytherelationalmodelisimplementedinpractice.Wealsoextendthealgebrasoitcanhandleseveralmoreoperations.Contents2Whatisabag(包)?Abagmeansarelationthatmay(ormaynot)haveduplicatetuples.Asetmeansarelationwithoutduplicatetuples.Whybags?SQL,themostimportantquerylanguageforrelationaldatabases,isactuallyabaglanguage.Someoperations,likeprojectionandunion,aremuchmoreefficientonbagsthansets.5.1RelationalOperationsonBags3SupposethatRandSarebags,andthattupletappearsntimesinRandmtimesinS.BagUnion（并）InthebagunionR∪S,tupletappearsn+mtimes.Example:{1,2,1}∪{1,1,2,3,1}={1,1,1,1,1,2,2,3}5.1.2Union,Intersection,andDifferenceofBags4BagIntersection（交）InthebagintersectionR∩S,tupletappearsmin(n,m)times.Example:{1,2,1,1}∩{1,2,1,3}={1,1,2}5.1.2Union,Intersection,andDifferenceofBags5BagDifference（差）InthebagDifferenceR–S,tupletappearsmax(0,n-m)times.Example:{1,2,1,1}–{1,2,3}={1,1}{1,2,3}–{1,2,1,1}={3}5.1.2Union,Intersection,andDifferenceofBags6AlgebraicLawsforBagsSome,butnotallalgebraiclawsthatholdforsetsalsoholdforbags.Example:R∪S=S∪R.However,thereareanumberofotherlawsthatholdwhenrelationalalgebraisappliedtosetsbutthatdonotholdwhenrelationsareinterpretedasbags.Example:S∪S=S(R∪S)–T=(R–T)∪(S–T)5.1.2Union,Intersection,andDifferenceofBags7RAB125612πA(R)=A151Projectionappliestoeachtuple,butasabagoperator,wedonoteliminate(消除)duplicates.Example:5.1.3ProjectionofBags8RAB125612σA+B5(R)=AB1212Selectionappliestoeachtuple,soitseffectonbagsislikeitseffectonsets.Example:5.1.4SelectiononBags9Eachtupleofonerelationispairedwitheachtupleoftheother,regardlessofwhetheritisaduplicateornot.IfatuplerappearsinarelationRmtimes,andtuplesappearsntimesinrelationS,thenintheproductR×S,thetuplerswillappearm×ntimes.5.1.5ProductofBags10Example:5.1.5ProductofBagsRABSBC1234567812R×S=AR.BS.BC12341278563456781234127811Wecompareeachtupleofonerelationwitheachtupleoftheother,decidewhetherornotthispairoftuplesjoinssuccessfully,andifsoweputtheresultingtupleintheanswer.Whenconstructingtheanswer,wedonoteliminateduplicatetuples.5.1.6JoinsofBags125.1.6JoinsofBagsRABSBC1234567812RR.BS.BS=AR.BS.BC1234127856781234127813Duplicate-eliminationoperator:δ(R)Turnsabagintoaset.Aggregations(聚合)operators:SUM,AVG,MIN,MAX,COUNT.Groupingoperator:γA,SUM(B)→SB(R)Sortingoperator:τA,B(R)Turnsarelationintoalistoftuples,sortedaccordingtooneormoreattributes.Extendedprojection:πA,B+C→X(R)Outerjoinoperator.5.2ExtendedOperatorsofRelationalAlgebra14Example:5.2ExtendedOperatorsofRelationalAlgebraRAB1245141143γA,SUM(B)→SB(R)=ASB174815Groupingoperator:γA,SUM(B)→SB(R)Example:5.2ExtendedOperatorsofRelationalAlgebraRAB1245141143τA,B(R)=16Sortingoperator:τA,B(R)AB1112144345Example:5.2ExtendedOperatorsofRelationalAlgebraRABCa23b21a14c15d34πA,B+C→X(R)=17Extendedprojection:πA,B+C→X(R)AXa5b3a5c6d7SupposewejoinRS.AtupleofRthatfailtomatchanytupleofSinthecommonattributesissaidtobedangling.SimilarlyforatupleofS.Outerjoinpreservesdanglingtuplesbypadding(填充)themwithaspecialNULLsymbol,⊥,intheresult.ROS、ROLS、RORSOuterjoins(外连接)18Example:5.2ExtendedOperatorsofRelationalAlgebraRABSBC12234567先计算两个关系的自然连接再加入右边关系中的悬挂元组用空值填充来自左面关系的属性RORS=ABC12367⊥19Example:5.2ExtendedOperatorsofRelationalAlgebraRABSBC12234567先计算两个关系的自然连接再加入左右关系中的悬挂元组用空值填充来自另一关系的属性ROS=ABC1234567⊥⊥20