TransactionalInformation Systems まとめ 第三章 （４）

（４）An Alternative Correctness Criterion: Interleaving Specifications

単純にトランザクション単位でserialとするのではなく、もう「トランザクションの部分単位」でserialにすることを考える。

　　　この緩和を取り入れることで並行性を向上できる。

①Indivisible Units

上述の「トランザクションの部分」を定めるもの。「これ以上は分解できない（相互にinterleaveしあうことができない）」ことを基準に分割する。

Let T = {t1, . . . , tn} be a set of transactions. For ti, tj ∈ T, i = j, anindivisibleunit of ti relative to t j is a sequence of consecutive steps of ti such that

no operations of t j are allowed to be executed within this sequence.

Let IU(ti , t j ) denote the ordered sequence of indivisible units of ti relative to t j , and let IUk(ti , t j ) denote the k-th element of IU(ti , t j ).

②Relative Serializability

Relatively Serial Scheduleは不可分なoperation集合には、conflictとなる他トランザクションのオペレーションが挟み込まれないもの。

A schedule s such that trans(s) = T is relatively serial if for all transactions ti, tj ∈ T, i = j , the following holds:

if an operation q ∈ t j is interleaved with IUk(ti , t j ) for some k,

then there is no operation p ∈ IUk(ti , t j) (p ∈ ti ) such that p ∗ q or q ∗ p.

※記号に注意。「*」は、本来は「→」の曲線版に「*」が付与されたもの。

Relative Serializability

A schedule s is relatively serializable if it is conflict equivalent to somerelatively serial schedule.

③Push Forward and Pull Backward

Indivisible Unitの「先頭（Foward)」と「末尾(Backward)」を表す。interleaveの境界を示すものとして、correctnessの判定する際に使う。

「該当するIndivisible Unitにconflictするオペレーション」は、この両端の外に寄せる（追い出す）必要がある。

Let ti and t j be distinct transactions, and let IUk(ti, tj ) be an indivisible unit of ti relative to t j . For an operation pi ∈ IUk(ti , t j )(pi ∈ ti ) let

1. F (pi, tj ) be the last operation in IUk(ti, tj ),

2. B(pi, tj ) be the first operation of IUk(ti, tj ).

④RSG（Relative Serialization Graph）

「If s is relatively serial, then RSG(s) is acyclic」となる。RSGは以下のようにして作成する。

Let s be a schedule. The relative serialization graph RSG(s) = (V, E) of s is defined by V := op(s) and E ⊆ V × V containing four types of edges as follows:

1. if p and q are consecutive operations of the same transaction in s, then ( p, q) ∈ E (internal or I edge);

2. if p ∗ q for p ∈ ti , q ∈ t j , i = j , then ( p, q) ∈ E (dependency or D edge);

3. if ( p, q) is a D edge such that p ∈ ti and q ∈ t j , then (F ( p, t j ), q) ∈ E (push forward or F edge);

4. if ( p, q) is a D edge such that p ∈ ti and q ∈ t j , then ( p, B(q, ti )) ∈ E(pull backward or B edge)