Comparison of Access Methods for Time-Evolving DataTemporal database design problemSlide 3OutlineConventional Vs. Temporal DatabasesWhat is Stored in a Temporal Database?Taxonomy of Time in a Temporal DatabaseTransaction Time DatabaseAssumptions in a Transaction Time DatabaseTransaction Time Database ExampleTransaction Time Database Access Method CharacteristicValid Time DatabaseValid Time Database Access Method CharacteristicBitemporal DatabaseBitemporal Database Access Method CharacteristicCriteria for Comparison of Access MethodsQueryQuery Type IQuery Type IIQuery Type IIIBitemporal QueriesThree-Entry Notation Query-Type RepresentationAccess Method CostsStorage SpaceUpdate Processing TimeQuery TimeIndex Pagination and Data clusteringSlide 28Migration of Past Data to Another LocationSlide 30Lower Bound on I/O ComplexitySlide 32Efficient Method Design for Transaction/Bitemporal DataSlide 34Slide 35Slide 36Slide 37Method ClassificationExamples of Method ClassesTime Index Access Method (Time Only)Slide 41Reverse chaining (Key-Only)Reverse ChainingComparison of Access Methods for time evolving dataThe End1Comparison of Access Methods for Time-Evolving DataBetty Salzberg and Vassilis TsotrasCS599, Temporal and Spatial Databases Course.Presented by:Atousa Golpayegani11/16/20002Temporal database design problemAccess MethodsDBMS SoftwareAccess Method?Temporal QueriesTime Dimension Database DesignerB+-treeR-treesnapshot-indextime-index3Temporal database design problemAccess MethodsDBMS SoftwareAccess MethodTemporal QueriesSelected Time Dimension Access MethodSelection CriteriaDatabase DesignerB+-tree R-treesnapshot-indextime-index4OutlineBrief introduction to temporal databases Criteria for comparison of access methodsEfficient method design for transaction/Bitemporal dataMethod classification and comparison5Conventional Vs. Temporal DatabasesConventional database captures only a single snapshot of the modeled reality, usually the most current.Can not support past and future data.Ex: “ the current salary of an employee”.Temporal database supports some time domain and is thus able to manage time varying data.User-defined time is excluded.Ex: “ the current and the previous salaries of an employee since hiring”.6What is Stored in a Temporal Database? Tuple-versioning Temporal model is used. In this model Database is a set of records that store the versions of the real life objects. Each record has: A time invariant key A number of time variant attributes (for simplicity just one) One or two intervals Start time End timeEx: Employee (ss#, name, salary, [t1, now) )7Taxonomy of Time in a Temporal DatabaseTransaction Time Is defined as the time when a fact is stored in the database.Valid Time Is defined as the time when a fact becomes effective (valid) in reality. Bitemporal TimeIs the combination of the above two types.Time is assumed to be discrete, and consecutive nonnegative integersAny change is assumed to occur only at an indicated time Addition of an objectDeletion of an objectValue change of an object’s attribute8Transaction Time DatabaseTime Interval shows when an object was added and deleted.An object is alive from the time it is added to the database until it is deleted.Ex. Object ‘a’ is the only one that is currently alive.No record is physically deleted (logical deletion). Therefore database has logical stateEx. Object ‘b’ is deleted.Logical state at time t consists of those records whose transaction time interval contains t. Ex. S(T4) = (‘a’ , ‘b’)T1T2T3T4T5TimeabbLogical state T49Assumptions in a Transaction Time DatabasePast states can not be changed.Linear transaction time evolutionA New database state is created by updating only the current database state.Another option is called branching transaction time evolution, where new states can be created from any past database state.Implicit updating assumptionIf an object is updated at time t, the database system will be updated at the same time. There is no delay.10Transaction Time Database ExampleT1T2T3T4T5Time(SS1,A,X1)(SS2,B,X2)(SS12B,X2)key Salary Transaction TimeSS1SS2SS2X1X2X2[ T1, now)[ T2, T3)[T4, T5)NameABB11T1T2T3T4T5TimeabbLogical state T4Transaction Time Database Access Method CharacteristicStore the past logical states.Support addition/deletion/modification changes on the objects of the current logical state.Efficiently access and query objects in any of logical states.12Valid Time DatabaseTime Interval shows the validity period of an object in reality.Ex. The period that a contract is valid.An object that is not valid anymore will be physically deleted from the database.Only the latest “snapshot” of the collection of interval-objects are kept.Valid TimeValid TimeI1I2State i-1State i13Valid Time Database Access Method CharacteristicStore the latest collection of interval-objects.Support addition/deletion/modification changes to this collection.Efficiently query the interval-objects contained in the collection.Valid TimeI214Bitemporal DatabaseSupports both transaction time and valid time.Instead of a single collection of interval-objects, there is a sequence of collections, C(ti), indexed by transaction time.Transaction time and valid time are two orthogonal time dimensions.Ex. (Contract#, amount, duration, [t1, now))t1t4t3t2C(t1)C(t4)C(t3)C(t2)15Bitemporal Database Access Method CharacteristicStore its past logical states.Support addition/deletion/modification changes on the interval-objects of its current logical state.Efficiently access and query the interval-objects on any of its states.16Criteria for Comparison of Access MethodsQueryAccess Method CostsIndex Pagination and Data ClusteringMigration of Past Data to Another LocationLower Bounds on I/O Complexity17QueryOne of the criteria for the comparison is how efficient an access method answers a query.Three general classes of queries are chosen. They can be used for both valid time and transaction time since from a query perspective, valid time and transaction time are simply collections of intervals.18Query Type IGiven a contiguous interval T, find all objects alive during this interval.Representative query for this type:Pure-timeslice query : A special case of type I when interval T is reduced to a single time
View Full Document
Unlocking...