UVA DEPARTMENT OF COMPUTER SCIENCETO-1Timestamp OrderingUsing timestamps- any conflicting read/write operations are executedin their timestamp order- simple and aggressive: schedule immediately andreject requests that arrive too late- each data object maintains read-timestamp (rts) andwrite-timestamp (wts)Timestamp ordering ruleif pi(x) and qj(x) are conflicting operationsthen pi(x) is processed before qj(x) iff ts(Ti) < ts(Tj)Theorem: If TO rule is enforced, then all the executionsgenerated by the scheduler is serializableProof: If T1... TnT1exists in SG(H)then ts(T1) < ... < ts(Tn) < ts(T1) due to TO rule.A contradiction.UVA DEPARTMENT OF COMPUTER SCIENCETO-2Timestamp Ordering ProtocolBasic timestamp ordering protocol1) ri(x): if ts(Ti) < wts(x) then reject itotherwise (ts(Ti) wts(x)), schedule ri(x)and set rts(x) = max (rts(x), ts(Ti))2) wi(x): if ts(Ti) < rts(x) then reject itif ts(Ti) < wts(x) then reject itotherwise, schedule wi(x)and set wts(x) = max (wts(x), ts(Ti))- when retarted, Tiis assigned a new timestampThomas write rule (TWR)if ts(Ti) < wts(x) for wi(x) and ts(Ti) rts(x)then wi(x) can be ignored, instead of being rejected--- delete obsolete writeUVA DEPARTMENT OF COMPUTER SCIENCETO-3Strict Timestamp OrderingSR but not RC- basic timestamp ordering is SR but not necessarily RCw1(x) r2(x) w2(y) c2Strict timestamp ordering- does not schedule any operation conflicting withwi(x) until Titerminates--- same as 2PL?Non-equivalence of 2PL and timestamp orderingH1= r2(x) w3(x) c3w1(y) c1r2(y) w2(y) c2- is this possible with timestamp ordering? with 2PL?- T2must release lock on x for T3to access, but thengets lock on y --- violation of two-phaseness- it is legal in strict timestamp ordering, equivalent toa serial schedule T1T2T3UVA DEPARTMENT OF COMPUTER SCIENCETO-4Relationship between 2PL and TOSchedules generated by 2PL and timestamp ordering- they are all correct (i.e., serializable)- they are not the same sets: H1shows it- is the relationship inclusive?{S 2PL} {S TO}?{S TO} {S 2PL}?w3(x) c3w2(x) c2r1(x)--- legal in 2PL, not possible using timestamp orderingRelationship between the two sets of schedulesSR2PLTimestamp orderingUVA DEPARTMENT OF COMPUTER SCIENCETO-5Certifier ApproachOptimistic approach- aggressive scheduling- three phases: read, validation, write phase- conflict resolution during validation phase- when cicomes from Ti, checkRS(Ti) WS(Tj) =WS(Ti) RS(Tj) =WS(Ti) WS(Tj) =Validation: forward or backward- forward: validating transaction against active ones- backward: validating transaction against committed onesNon-blocking approach- abort and restart instead of blocking (deadlock-free)- problems of wasted resources and wasted abortsUVA DEPARTMENT OF COMPUTER SCIENCETO-6Hybrid ApproachObjectivepractical concurrency control protocols that allowtransactions to meet the deadlines without reducingthe concurrency level of the systemCombine pessimistic and optimistic approaches- effective control of blocking and aborting- avoid unnecessary blocking and abortingApproach- adjust the serialization order of active transactionsdynamically in favor of high priority transactions- relax the relationship between the serializationorder and the past execution historyUVA DEPARTMENT OF COMPUTER SCIENCETO-7Multiversion Data ObjectsObjectives- improved system responsiveness by providing multipleversions (increased degree of concurrency)- reduce the probability of conflicts and rejection oftardy transactions by successive views of data objectsMaintenance of multiple versions- each write creates a new version- system selects an appropriate version to readPotential problems- coordination for consistency- storage and processing overheadUVA DEPARTMENT OF COMPUTER SCIENCETO-8Multiversion Timeestamp OrderingMVTO scheduler translates operations on data objects intoversion operations to make it appear as if operations areprocessed in timestamp order on a single-version database1) ri(x) ri(xk)where xkis the version of x with largest timestampnot greater than ts(Ti): ts(Tk) ts(Ti)2) wi(x):case 1: if rj(xk) such that ts(Tk) < ts(Ti) < ts(Tj)is already processed, reject wi(x)case 2: otherwise, translate wi(x) into wi(xi)and send it to data manager3) ci:delay processing of cifor recoverability until cjof all Tjthat wrote versions read by Tihas processedUVA DEPARTMENT OF COMPUTER SCIENCEReview-1Database Systems: ReviewObjectives of database systems- convenience and efficiency- name of the game: data abstractionData models- object-based: ER model, OO model- record-based: relational, network, hierarchicalRelational model- DML: relational algebra and calculus (tuple/domain)- query languages: SQL, QUEL, QBE- properties of good/bad design- functional dependencies and normal forms- MVD and higher normal formsUVA DEPARTMENT OF COMPUTER SCIENCEReview-2Database Systems: ReviewPhysical organization- file organization and disk configuration (RAID)- indexing by B-tree and B+-tree- hashing function (static and extendible)System issues- transaction: atomicity, serializability, recoverability- scheduling and concurrency control- two-phase locking and timestamp ordering- optimistic (certifier or validation) approach- recovery- undo/redo- log and checkpointOther models: object-oriented, network,