Databases Reference
In-Depth Information
the dependency graph. It is shown in [68] that the log can be scanned
forward only once (i.e., one-pass) from the entry where the first malicious
transaction starts to locate every affected transaction.
•
Repair
When the damage assessment part is done, scan backward from
the end of the log to semantically revoke (or undo) the effects of all the
malicious transactions and the transactions included in the dependency
graph. Note that here the undoes should be performed in the reverse com-
mit order.
In contrast, data-oriented methods use the read and write operations of
transactions to trace the damage spreading from one data object to another,
and compose a specific piece of code to repair each damaged data object. In
particular, data-oriented methods work as follows.
•
Damage Assessment
Construct a specific damage propagation graph in
which each node is a (corrupted) data object while each directed edge
from node
x
to
y
is a transaction
T
such that
T
reads
x
and writes
y
.The
damage propagation graph can be built by one-pass scanning of the log.
•
Repair
Once the damage propagation graph is constructed, for each data
object
x
contained in the graph, search through the log to find the latest
pre-corruption version of
x
. Then repair
x
by overwriting the value of
x
with the searched version.
Comparison
Data-oriented methods are more flexible and better at han-
dling blind writes, however, composing cleaning code for each data object can
be time consuming and prone to errors. Transaction-oriented methods use a
cleaning transaction, which can be easily composed, to repair multiple data
objects at the same time, thus they are more robust and ecient.
Maintaining Read Information
Both data-oriented methods and transaction-oriented methods rely on the
read-from relationships between transactions. (Transaction
T
1
reads from T
2
if there is a data object
x
such that
T
1
reads
x
after
T
2
updates
x
,and
no other transaction updates
x
between these two operations.) However, the
read-from information is not maintained by commercial DBMSes, since such
information is not necessary for failure recovery. As a result, the transaction
log maintained by a commercial DBMS actually does not contain sucient
information for the aforementioned DQR mechanisms to succeed. Therefore,
maintaining the read-from information is an important task in engineering
practical DQR systems.
In the literature, several representative techniques are proposed to main-
tain the read-from information. In [72], read operations are extracted from
SQL statement texts. In particular, [72] assumes that each transaction belongs
to a transaction
type
, and the
profile
(or source code) for each transaction type
is known. For each transaction type
ty
i
, [72] extracts a
read set template
from
