Reads-From
Reads-From
正式にはReads-From Relationship.
Bernstein 83では，Reads-x-Fromと書かれている．つまりA Reads x From B...という関係性のこと． Ref: Weikum p78
Definition 3.7 Reads-From Relation: Useful, Alive, and Dead Steps
Let $ s be a schedule.
1. Let $ t_j \in trans(s), and let $ r_j(x) be a read operation of $ t_j.$ r_j(x)reads $ x in $ s from $ w_i(x), $ i \neq j, if $ w_i(x)is the last write operation on $ x such that $ w_i(x) <_s r_j(x)
2. The reads-from relation of $ sis defined by
$ RF(s):= \{(t_i, x, t_j) |\ an\ r_j(x)\ reads\ x\ from\ a\ w_i(x)\}
3. A step $ p is directly useful for a step $ q, denoted $ p \to q, if $ qreads from $ p, or if $ p is a read step and $ q a subsequent write step from the same transaction.
Let $ \stackrel{*}{\to}("useful") denote the reflexive and transitive closure of $ \to.
4. A step $ p is alive in $ s if it is useful for some step from $ t_\infty, i.e.,
$ (\exists q \in t_\infty) p \stackrel{*}{\to} q
and dead otherwise.
5. The live reads-from relation of $ s is defined by
$ LRF(s):= \{(t_i, x, t_j) |\ an\ alive\ r_j(x)\ reads\ x\ from\ a\ w_i(x)\}.
定義の1. より，Multiversion Scheduleで単純にReads Fromを調べることはできない．