Databases Reference
In-Depth Information
B
1
G
1
B
2
G
2
G
4
Fig. 3.
Dependency Graph for History
H
1
reads
o
after
T
i
has updated
o
;
T
i
does not abort before
T
j
reads
o
; and every
transaction (if any) that updates
o
between the time
T
i
updates
o
and
T
j
reads
o
is aborted before
T
j
reads
x
. In a history,
T
1
affects T
2
if the ordered pair
(
T
1
,T
2
) is in the transitive closure of the
dependent upon
relation. Finally, we
define the
dependency graph
for a (any) set of transactions
S
in a history as
DG
(
S
)=(
V,E
)inwhich
V
is the union of
S
and the set of transactions that
are affected by
S
. There is an edge,
T
i
→
T
j
,in
E
if
T
i
∈
V
,
T
j
∈
(
V
−
S
),
and
T
j
is dependent upon
T
i
.
Example
Consider the following history over (
B
1
,B
2
,G
1
,G
2
,G
3
,G
4
):
H
1
:
r
B
1
[
x
]
w
B
1
[
x
]
c
B
1
r
G
1
[
x
]
w
G
1
[
x
]
r
G
3
[
z
]
w
G
3
[
z
]
c
G
3
r
G
1
[
y
]
w
G
1
[
y
]
c
G
1
r
G
2
[
y
]
w
G
2
[
y
]
r
B
2
[
z
]
w
B
2
[
z
]
c
B
2
r
G
2
[
v
]
w
G
2
[
v
]
c
G
2
r
G
4
[
z
]
w
G
4
[
z
]
r
G
4
[
y
]
w
G
4
[
y
]
c
G
4
In
H
1
,
B
1
and
B
2
are malicious transactions while the other three are
legitimate transactions;
r
T
[
x
](
w
T
[
x
]) is a read (write) operation by transac-
tion
T
on data object
x
;
c
T
is the commit operation of
T
.Let
B
=
{
B
1
,B
2
}
,
DG
(
B
) is shown in Figure 3.
Lemma 4.1
In a DQR history, a legitimate transaction is affected
if and only if it is in dependency graph
DG
(all malicious transactions plus
all the legitimate transactions that read the original version of any Type 3
corrupted data object). Being conservative, we assume all updates done by
affected transactions may
spread
the damage.
Do We Have to Sacrifice Durability?
A main concern people may have on DQR solutions is whether they will
compromise
Durability
, a fundamental property of transaction processing and
transactional failure recovery mechanisms. In other words, do we have to sac-
rifice Durability in doing DQR? Fortunately, the answer is NO. To keep dura-
bility, DQR schemes never really need to undo a malicious or affected trans-
action; instead, they can execute cleaning transactions to
semantically
revoke
the effect of a committed transaction. By semantically revoking the effect of a
committed transaction, we can achieve the following: (a) The effect of a com-
mitted transaction will always be kept durable; we never revoke or reverse
any physical effect of a committed transaction on the persistent storage. (b)
A cleaning transaction will change the data store state in exactly the
same
