Databases Reference
In-Depth Information
way as a regular transaction performing a set of updates. Because execut-
ing regular transactions will never compromise Durability, executing cleaning
transactions (to do damage recovery) will never compromise Durability.
The Spectrum of DQR Schemes
The concept of DQR histories allows us to see the differences between the
ones on the “spectrum” of DQR schemes. (a) On one end of the spectrum,
a
static
DQR scheme will stop processing new transactions until every cor-
rupted data object is
repaired
or cleaned. (A corrupted data object is
repaired
if its value is restored to the latest clean version before corruption.) So since
the
time of detection
, which is also the time when the recovery starts, the
corresponding DQR history will proceed with only cleaning transactions until
the repair is completed. In addition, affected transactions should be reexe-
cuted; otherwise, DoS is caused. (b) On the other end, an optimistic,
dynamic
DQR scheme may do dependency analysis (a.k.a. damage assessment), exe-
cute cleaning transactions, execute to-be-reexecuted transactions, and execute
new transactions
concurrently
. (c) Semi-dynamic DQR schemes may certainly
stay on the spectrum between the two ends. For example, in [69, 70], there is
a dedicated
scan
phase during which dependency analysis is performed, but
no
new transactions can be executed.
Section organization
In the rest of this section, without losing generality,
we will focus on the two “ends” of the spectrum of DQR schemes, that is, we
will review static DQR solutions and dynamic DQR solutions in Section 4.2
and Section 4.3, respectively.
4.2 Static DQR Solutions
Static DQR solutions “halt” the database (service) before the repair is com-
pleted. Since no new transactions can be executed during static DQR, the
damage will not spread unless there are incorrect repair operations. Hence,
damage quarantine is not an issue in static DQR. As a result, static DQR has
two aspects:
damage assessment
, which identifies every corrupted data object,
and
damage repair
, which restores the value of each corrupted data object to
its pre-corruption version.
In terms of how damage assessment and repair can be done, existing
static DQR methods are either
data-oriented
[71] or
transaction-oriented
[68].
Transaction-oriented methods assess and repair the damage by identifying and
backing out affected transactions. In particular, they work as follows.
•
Damage Assessment
Build the dependency graph defined in Definition
4.1 for the set of malicious transactions detected. Based on Lemma 4.1, the
dependency graph consists of all and only the affected transactions that
have “contributed” to damage propagation. Assuming that read opera-
tions are logged together with write operations, it is not di
cult to build
