数据库系统概念全套配套课件PPT ch25.ppt 53页

'Chapter25:AdvancedDataTypesandNewApplications Chapter25:AdvancedDataTypesandNewApplicationsTemporalDataSpatialandGeographicDatabasesMultimediaDatabasesMobilityandPersonalDatabases TimeInDatabasesWhilemostdatabasestendtomodelrealityatapointintime(atthe“current”time),temporaldatabasesmodelthestatesoftherealworldacrosstime.Factsintemporalrelationshaveassociatedtimeswhentheyarevalid,whichcanberepresentedasaunionofintervals.Thetransactiontimeforafactisthetimeintervalduringwhichthefactiscurrentwithinthedatabasesystem.Inatemporalrelation,eachtuplehasanassociatedtimewhenitistrue;thetimemaybeeithervalidtimeortransactiontime.Abi-temporalrelationstoresbothvalidandtransactiontime. TimeInDatabases(Cont.)Exampleofatemporalrelation:Temporalquerylanguageshavebeenproposedtosimplifymodelingoftimeaswellastimerelatedqueries. TimeSpecificationinSQL-92date:fourdigitsfortheyear(1--9999),twodigitsforthemonth(1--12),andtwodigitsforthedate(1--31).time:twodigitsforthehour,twodigitsfortheminute,andtwodigitsforthesecond,plusoptionalfractionaldigits.timestamp:thefieldsofdateandtime,withsixfractionaldigitsforthesecondsfield.TimesarespecifiedintheUniversalCoordinatedTime,abbreviatedUTC(fromtheFrench);supportstimewithtimezone.interval:referstoaperiodoftime(e.g.,2daysand5hours),withoutspecifyingaparticulartimewhenthisperiodstarts;couldmoreaccuratelybetermedaspan. TemporalQueryLanguagesPredicatesprecedes,overlaps,andcontainsontimeintervals.Intersectcanbeappliedontwointervals,togiveasingle(possiblyempty)interval;theunionoftwointervalsmayormaynotbeasingleinterval.Asnapshotofatemporalrelationattimetconsistsofthetuplesthatarevalidattimet,withthetime-intervalattributesprojectedout.Temporalselection:involvestimeattributesTemporalprojection:thetuplesintheprojectioninherittheirtime-intervalsfromthetuplesintheoriginalrelation.Temporaljoin:thetime-intervalofatupleintheresultistheintersectionofthetime-intervalsofthetuplesfromwhichitisderived.Itintersectionisempty,tupleisdiscardedfromjoin. TemporalQueryLanguages(Cont.)Functionaldependenciesmustbeusedwithcare:addingatimefieldmayinvalidatefunctionaldependencyAtemporalfunctionaldependencyxYholdsonarelationschemaRif,foralllegalinstancesrofR,allsnapshotsofrsatisfythefunctionaldependencyXY.SQL:1999Part7(SQL/Temporal)isaproposedextensiontoSQL:1999toimprovesupportoftemporaldata. SpatialandGeographicDatabases SpatialandGeographicDatabasesSpatialdatabasesstoreinformationrelatedtospatiallocations,andsupportefficientstorage,indexingandqueryingofspatialdata.Specialpurposeindexstructuresareimportantforaccessingspatialdata,andforprocessingspatialjoinqueries.ComputerAidedDesign(CAD)databasesstoredesigninformationabouthowobjectsareconstructedE.g.:designsofbuildings,aircraft,layoutsofintegrated-circuitsGeographicdatabasesstoregeographicinformation(e.g.,maps):oftencalledgeographicinformationsystemsorGIS. RepresentedofGeometricInformationVariousgeometricconstructscanberepresentedinadatabaseinanormalizedfashion.Representalinesegmentbythecoordinatesofitsendpoints.ApproximateacurvebypartitioningitintoasequenceofsegmentsCreatealistofverticesinorder,orRepresenteachsegmentasaseparatetuplethatalsocarrieswithittheidentifierofthecurve(2Dfeaturessuchasroads).ClosedpolygonsListofverticesinorder,startingvertexisthesameastheendingvertex,orRepresentboundaryedgesasseparatetuples,witheachcontainingidentifierofthepolygon,orUsetriangulation—dividepolygonintotrianglesNotethepolygonidentifierwitheachofitstriangles. RepresentationofGeometricConstructs RepresentationofGeometricInformation(Cont.)Representationofpointsandlinesegmentin3-Dsimilarto2-D,exceptthatpointshaveanextrazcomponentRepresentarbitrarypolyhedrabydividingthemintotetrahedrons,liketriangulatingpolygons.Alternative:Listtheirfaces,eachofwhichisapolygon,alongwithanindicationofwhichsideofthefaceisinsidethepolyhedron. DesignDatabasesRepresentdesigncomponentsasobjects(generallygeometricobjects);theconnectionsbetweentheobjectsindicatehowthedesignisstructured.Simpletwo-dimensionalobjects:points,lines,triangles,rectangles,polygons.Complextwo-dimensionalobjects:formedfromsimpleobjectsviaunion,intersection,anddifferenceoperations.Complexthree-dimensionalobjects:formedfromsimplerobjectssuchasspheres,cylinders,andcuboids,byunion,intersection,anddifferenceoperations.Wireframemodelsrepresentthree-dimensionalsurfacesasasetofsimplerobjects. RepresentationofGeometricConstructsDesigndatabasesalsostorenon-spatialinformationaboutobjects(e.g.,constructionmaterial,color,etc.)Spatialintegrityconstraintsareimportant.E.g.,pipesshouldnotintersect,wiresshouldnotbetooclosetoeachother,etc. GeographicDataRasterdataconsistofbitmapsorpixelmaps,intwoormoredimensions.Example2-Drasterimage:satelliteimageofcloudcover,whereeachpixelstoresthecloudvisibilityinaparticulararea.Additionaldimensionsmightincludethetemperatureatdifferentaltitudesatdifferentregions,ormeasurementstakenatdifferentpointsintime.Designdatabasesgenerallydonotstorerasterdata. GeographicData(Cont.)Vectordataareconstructedfrombasicgeometricobjects:points,linesegments,triangles,andotherpolygonsintwodimensions,andcylinders,spheres,cuboids,andotherpolyhedronsinthreedimensions.Vectorformatoftenusedtorepresentmapdata.Roadscanbeconsideredastwo-dimensionalandrepresentedbylinesandcurves.Somefeatures,suchasrivers,mayberepresentedeitherascomplexcurvesorascomplexpolygons,dependingonwhethertheirwidthisrelevant.Featuressuchasregionsandlakescanbedepictedaspolygons. ApplicationsofGeographicDataExamplesofgeographicdatamapdataforvehiclenavigationdistributionnetworkinformationforpower,telephones,watersupply,andsewageVehiclenavigationsystemsstoreinformationaboutroadsandservicesfortheuseofdrivers:Spatialdata:e.g.,road/restaurant/gas-stationcoordinatesNon-spatialdata:e.g.,one-waystreets,speedlimits,trafficcongestionGlobalPositioningSystem(GPS)unit-utilizesinformationbroadcastfromGPSsatellitestofindthecurrentlocationofuserwithanaccuracyoftensofmeters.increasinglyusedinvehiclenavigationsystemsaswellasutilitymaintenanceapplications. SpatialQueriesNearnessqueriesrequestobjectsthatlienearaspecifiedlocation.Nearestneighborqueries,givenapointoranobject,findthenearestobjectthatsatisfiesgivenconditions.Regionqueriesdealwithspatialregions.e.g.,askforobjectsthatliepartiallyorfullyinsideaspecifiedregion.Queriesthatcomputeintersectionsorunionsofregions.Spatialjoinoftwospatialrelationswiththelocationplayingtheroleofjoinattribute. SpatialQueries(Cont.)Spatialdataistypicallyqueriedusingagraphicalquerylanguage;resultsarealsodisplayedinagraphicalmanner.Graphicalinterfaceconstitutesthefront-endExtensionsofSQLwithabstractdatatypes,suchaslines,polygonsandbitmaps,havebeenproposedtointerfacewithback-end.allowsrelationaldatabasestostoreandretrievespatialinformationQueriescanusespatialconditions(e.g.,containsoroverlaps).queriescanmixspatialandnonspatialconditions IndexingofSpatialDatak-dtree-earlystructureusedforindexinginmultipledimensions.Eachlevelofak-dtreepartitionsthespaceintotwo.chooseonedimensionforpartitioningattherootlevelofthetree.chooseanotherdimensionsforpartitioninginnodesatthenextlevelandsoon,cyclingthroughthedimensions.Ineachnode,approximatelyhalfofthepointsstoredinthesub-treefallononesideandhalfontheother.Partitioningstopswhenanodehaslessthanagivenmaximumnumberofpoints.Thek-d-Btreeextendsthek-dtreetoallowmultiplechildnodesforeachinternalnode;well-suitedforsecondarystorage. DivisionofSpacebyak-dTreeEachlineinthefigure(otherthantheoutsidebox)correspondstoanodeinthek-dtree.Themaximumnumberofpointsinaleafnodehasbeensetto1.Thenumberingofthelinesinthefigureindicatesthelevelofthetreeatwhichthecorrespondingnodeappears. DivisionofSpacebyQuadtreesQuadtreesEachnodeofaquadtreeisassociatedwitharectangularregionofspace;thetopnodeisassociatedwiththeentiretargetspace.Eachnon-leafnodesdividesitsregionintofourequalsizedquadrantsCorrespondinglyeachsuchnodehasfourchildnodescorrespondingtothefourquadrantsandsoonLeafnodeshavebetweenzeroandsomefixedmaximumnumberofpoints(setto1inexample). Quadtrees(Cont.)PRquadtree:storespoints;spaceisdividedbasedonregions,ratherthanontheactualsetofpointsstored.Regionquadtreesstorearray(raster)information.Anodeisaleafnodeisallthearrayvaluesintheregionthatitcoversarethesame.Otherwise,itissubdividedfurtherintofourchildrenofequalarea,andisthereforeaninternalnode.Eachnodecorrespondstoasub-arrayofvalues.Thesub-arrayscorrespondingtoleaveseithercontainjustasinglearrayelement,orhavemultiplearrayelements,allofwhichhavethesamevalue.Extensionsofk-dtreesandPRquadtreeshavebeenproposedtoindexlinesegmentsandpolygonsRequiresplittingsegments/polygonsintopiecesatpartitioningboundariesSamesegment/polygonmayberepresentedatseveralleafnodes R-TreesR-treesareaN-dimensionalextensionofB+-trees,usefulforindexingsetsofrectanglesandotherpolygons.Supportedinmanymoderndatabasesystems,alongwithvariantslikeR+-treesandR*-trees.Basicidea:generalizethenotionofaone-dimensionalintervalassociatedwitheachB+-treenodetoanN-dimensionalinterval,thatis,anN-dimensionalrectangle.Willconsideronlythetwo-dimensionalcase(N=2)generalizationforN>2isstraightforward,althoughR-treesworkwellonlyforrelativelysmallN RTrees(Cont.)Arectangularboundingboxisassociatedwitheachtreenode.Boundingboxofaleafnodeisaminimumsizedrectanglethatcontainsalltherectangles/polygonsassociatedwiththeleafnode.Theboundingboxassociatedwithanon-leafnodecontainstheboundingboxassociatedwithallitschildren.Boundingboxofanodeservesasitskeyinitsparentnode(ifany)BoundingboxesofchildrenofanodeareallowedtooverlapApolygonisstoredonlyinonenode,andtheboundingboxofthenodemustcontainthepolygon.ThestorageefficiencyorR-treesisbetterthanthatofk-dtreesorquadtreessinceapolygonisstoredonlyonce. ExampleR-TreeAsetofrectangles(solidline)andtheboundingboxes(dashedline)ofthenodesofanR-treefortherectangles.TheR-treeisshownontheright. SearchinR-TreesTofinddataitems(rectangles/polygons)intersecting(overlaps)agivenquerypoint/region,dothefollowing,startingfromtherootnode:Ifthenodeisaleafnode,outputthedataitemswhosekeysintersectthegivenquerypoint/region.Else,foreachchildofthecurrentnodewhoseboundingboxoverlapsthequerypoint/region,recursivelysearchthechildCanbeveryinefficientinworstcasesincemultiplepathsmayneedtobesearchedbutworksacceptablyinpractice.Simpleextensionsofsearchproceduretohandlepredicatescontained-inandcontains InsertioninR-TreesToinsertadataitem:Findaleaftostoreit,andaddittotheleafTofindleaf,followachild(ifany)whoseboundingboxcontainsboundingboxofdataitem,elsechildwhoseoverlapwithdataitemboundingboxismaximumHandleoverflowsbysplits(asinB+-trees)Splitprocedureisdifferentthough(seebelow)AdjustboundingboxesstartingfromtheleafupwardsSplitprocedure:Goal:divideentriesofanoverfullnodeintotwosetssuchthattheboundingboxeshaveminimumtotalareaThisisaheuristic.AlternativeslikeminimumoverlaparepossibleFindingthe“best”splitisexpensive,useheuristicsinsteadSeenextslide SplittinganR-TreeNodeQuadraticsplitdividestheentriesinanodeintotwonewnodesasfollowsFindpairofentrieswith“maximumseparation”thatis,thepairsuchthattheboundingboxofthetwowouldhasthemaximumwastedspace(areaofboundingbox–sumofareasoftwoentries)PlacetheseentriesintwonewnodesRepeatedlyfindtheentrywith“maximumpreference”foroneofthetwonewnodes,andassigntheentrytothatnodePreferenceofanentrytoanodeistheincreaseinareaofboundingboxiftheentryisaddedtotheothernodeStopwhenhalftheentrieshavebeenaddedtoonenodeThenassignremainingentriestotheothernodeCheaperlinearsplitheuristicworksintimelinearinnumberofentries,Cheaperbutgeneratesslightlyworsesplits. DeletinginR-TreesDeletionofanentryinanR-treedonemuchlikeaB+-treedeletion.Incaseofunderfullnode,borrowentriesfromasiblingifpossible,elsemergingsiblingnodesAlternativeapproachremovesallentriesfromtheunderfullnode,deletesthenode,thenreinsertsallentries MultimediaDatabases MultimediaDatabasesToprovidesuchdatabasefunctionsasindexingandconsistency,itisdesirabletostoremultimediadatainadatabaseratherthanstoringthemoutsidethedatabase,inafilesystemThedatabasemusthandlelargeobjectrepresentation.Similarity-basedretrievalmustbeprovidedbyspecialindexstructures.Mustprovideguaranteedsteadyretrievalratesforcontinuous-mediadata. MultimediaDataFormatsStoreandtransmitmultimediadataincompressedformJPEGandGIFthemostwidelyusedformatsforimagedata.MPEGstandardforvideodatausecommonaltiesamongasequenceofframestoachieveagreaterdegreeofcompression.MPEG-1qualitycomparabletoVHSvideotape.storesaminuteof30-frame-per-secondvideoandaudioinapproximately12.5MBMPEG-2designedfordigitalbroadcastsystemsanddigitalvideodisks;negligiblelossofvideoquality.Compresses1minuteofaudio-videotoapproximately17MB.SeveralalternativesofaudioencodingMPEG-1Layer3(MP3),RealAudio,WindowsMediaformat,etc. Continuous-MediaDataMostimportanttypesarevideoandaudiodata.Characterizedbyhighdatavolumesandreal-timeinformation-deliveryrequirements.Datamustbedeliveredsufficientlyfastthattherearenogapsintheaudioorvideo.Datamustbedeliveredataratethatdoesnotcauseoverflowofsystembuffers.SynchronizationamongdistinctdatastreamsmustbemaintainedVideoofapersonspeakingmustshowlipsmovingsynchronouslywiththeaudio VideoServersVideo-on-demandsystemsdelivervideofromcentralvideoservers,acrossanetwork,toterminalsMustguaranteeend-to-enddeliveryratesCurrentvideo-on-demandserversarebasedonfilesystems;existingdatabasesystemsdonotmeetreal-timeresponserequirements.Multimediadataarestoredonseveraldisks(RAIDconfiguration),orontertiarystorageforlessfrequentlyaccesseddata.Head-endterminals-usedtoviewmultimediadataPCsorTVsattachedtoasmall,inexpensivecomputercalledaset-topbox. Similarity-BasedRetrievalExamplesofsimilaritybasedretrievalPictorialdata:Twopicturesorimagesthatareslightlydifferentasrepresentedinthedatabasemaybeconsideredthesamebyauser.E.g.,identifysimilardesignsforregisteringanewtrademark.Audiodata:Speech-baseduserinterfacesallowtheusertogiveacommandoridentifyadataitembyspeaking.E.g.,testuserinputagainststoredcommands.Handwrittendata:Identifyahandwrittendataitemorcommandstoredinthedatabase Mobility MobileComputingEnvironmentsAmobilecomputingenvironmentconsistsofmobilecomputers,referredtoasmobilehosts,andawirednetworkofcomputers.MobilehostmaybeabletocommunicatewithwirednetworkthroughawirelessdigitalcommunicationnetworkWirelesslocal-areanetworks(withinabuilding)E.g.,Avaya’sOrinicoWirelessLANWideareasnetworksCellulardigitalpacketnetworks3Gand2.5Gcellularnetworks MobileComputingEnvironments(Cont.)AmodelformobilecommunicationMobilehostscommunicatetothewirednetworkviacomputersreferredtoasmobilesupport(orbase)stations.Eachmobilesupportstationmanagesthosemobilehostswithinitscell.Whenmobilehostsmovebetweencells,thereisahandoffofcontrolfromonemobilesupportstationtoanother.Directcommunication,withoutgoingthroughamobilesupportstationisalsopossiblebetweennearbymobilehostsSupported,fore.g.,bytheBluetoothstandard(upto10meters,atupto721kbps) DatabaseIssuesinMobileComputingNewissuesforqueryoptimization.ConnectiontimechargesandnumberofbytestransmittedEnergy(batterypower)isascarceresourceanditsusagemustbeminimizedMobileuser’slocationsmaybeaparameterofthequeryGISqueriesTechniquestotracklocationsoflargenumbersofmobilehostsBroadcastdatacanenableanynumberofclientstoreceivethesamedataatnoextracostleadstointerestingqueryinganddatacachingissues.Usersmayneedtobeabletoperformdatabaseupdatesevenwhilethemobilecomputerisdisconnected.E.g.,mobilesalesmanrecordssaleofproductson(localcopyof)database.Canresultinconflictsdetectedonreconnection,whichmayneedtoberesolvedmanually. RoutingandQueryProcessingMustconsiderthesecompetingcosts:Usertime.CommunicationcostConnectiontime-usedtoassignmonetarychargesinsomecellularsystems.Numberofbytes,orpackets,transferred-usedtocomputechargesindigitalcellularsystemsTime-of-daybasedcharges-varybasedonpeakoroff-peakperiodsEnergy-optimizeuseofbatterypowerbyminimizingreceptionandtransmissionofdata.Receivingradiosignalsrequiresmuchlessenergythantransmittingradiosignals. BroadcastDataMobilesupportstationscanbroadcastfrequently-requesteddataAllowsmobilehoststowaitforneededdata,ratherthanhavingtoconsumeenergytransmittingarequestSupportsmobilehostswithouttransmissioncapabilityAmobilehostmayoptimizeenergycostsbydeterminingifaquerycanbeansweredusingonlycacheddataIfnotthenmusteither;WaitforthedatatobebroadcastTransmitarequestfordataandmustknowwhentherelevantdatawillbebroadcast.Broadcastdatamaybetransmittedaccordingtoafixedscheduleorachangeableschedule.Forchangeableschedule:thebroadcastschedulemustitselfbebroadcastatawell-knownradiofrequencyandatwell-knowntimeintervalsDatareceptionmaybeinterruptedbynoiseUsetechniquessimilartoRAIDtotransmitredundantdata(parity) DisconnectivityandConsistencyAmobilehostmayremaininoperationduringperiodsofdisconnection.Problemscreatediftheuserofthemobilehostissuesqueriesandupdatesondatathatresidesoriscachedlocally:Recoverability:Updatesenteredonadisconnectedmachinemaybelostifthemobilehostfails.Sincethemobilehostrepresentsasinglepointoffailure,stablestoragecannotbesimulatedwell.Consistency:Cacheddatamaybecomeoutofdate,butthemobilehostcannotdiscoverthisuntilitisreconnected. MobileUpdatesPartitioningviadisconnectionisthenormalmodeofoperationinmobilecomputing.Fordataupdatedbyonlyonemobilehost,simpletopropagateupdatewhenmobilehostreconnectsInothercasesdatamaybecomeinvalidandupdatesmayconflict.Whendataareupdatedbyothercomputers,invalidationreportsinformareconnectedmobilehostofout-of-datecacheentriesHowever,mobilehostmaymissareport.Version-numbering-basedschemesguaranteeonlythatiftwohostsindependentlyupdatethesameversionofadocument,theclashwillbedetectedeventually,whenthehostsexchangeinformationeitherdirectlyorthroughacommonhost.MoreonthisshortlyAutomaticreconciliationofinconsistentcopiesofdataisdifficultManualinterventionmaybeneeded DetectingInconsistentUpdatesVersionvectorschemeusedtodetectinconsistentupdatestodocumentsatdifferenthosts(sites).Copiesofdocumentdathostsiandjareinconsistentifthecopyofdocumentdaticontainsupdatesperformedbyhostkthathavenotbeenpropagatedtohostj(kmaybethesameasi),andthecopyofdatjcontainsupdatesperformedbyhostlthathavenotbeenpropagatedtohosti(lmaybethesameasj)Basicidea:eachhostistores,withitscopyofeachdocumentd,aversionvector-asetofversionnumbers,withanelementVd,i[k]foreveryotherhostkWhenahostiupdatesadocumentd,itincrementstheversionnumberVd,i[i]by1 DetectingInconsistentUpdates(Cont.)Whentwohostsiandjconnecttoeachothertheycheckifthecopiesofalldocumentsdthattheyshareareconsistent:Iftheversionvectorsarethesameonbothhosts(thatis,foreachk,Vd,i[k]=Vd,j[k])thenthecopiesofdareidentical.If,foreachk,Vd,i[k]Vd,j[k],andtheversionvectorsarenotidentical,thenthecopyofdocumentdathostiisolderthantheoneathostjThatis,thecopyofdocumentdathostjwasobtainedbyoneormoremodificationsofthecopyofdathosti.Hostireplacesitscopyofd,aswellasitscopyoftheversionvectorford,withthecopiesfromhostj.IfthereisapairofhostskandmsuchthatVd,i[k]Vd,j[m],thenthecopiesareinconsistentThatis,twoormoreupdateshavebeenperformedondindependently. HandlingInconsistentUpdatesDealingwithinconsistentupdatesishardingeneral.Manualinterventionoftenrequiredtomergetheupdates.Versionvectorschemesweredevelopedtodealwithfailuresinadistributedfilesystem,whereinconsistenciesarerare.areusedtomaintainaunifiedfilesystembetweenafixedhostandamobilecomputer,whereupdatesatthetwohostshavetobemergedperiodically.Alsousedforsimilarpurposesingroupwaresystems.areusedindatabasesystemswheremobileusersmayneedtoperformtransactions.Inthiscase,a“document”maybeasinglerecord.Inconsistenciesmusteitherbeveryrare,orfallinspecialcasesthatareeasytodealwithinmostcases EndofChapter Figure25.02 Figure25.03 Figure25.04 Figure25.05 Figure25.06'