Information Technology Reference
In-Depth Information
transaction identifiers in data-item versions when they are first needed in subsequent
accesses to the versions. Elaborate on these ideas. What changes would be needed
in the algorithms outlined in Sect.
12.8
?
Bibliographical Notes
POSTGRES
was the first transaction-time database management system imple-
mented. The system maintains the entire history of data items, and its query
language,
POSTQUEL
, provides for historical “as of” queries [Stonebraker and
Rowe,
1986
, Stonebraker,
1987
, Stonebraker et al.
1990
]. The system combines
the use of historical database states with the force buffering policy to obtain
instantaneous recovery from system crashes, while strict two-phase locking is used
for concurrency control [Stonebraker,
1987
].
In
POSTGRES
, when a transaction updates a data item, the transaction's identifier
is associated with the new version of the item, and when the transaction commits,
its commit time is stored in the persistent commit-time table, as explained in
Sect.
12.1
. The new data-item versions may later be revisited and the commit times
be substituted for the transaction identifiers (cf. Problem
12.11
). This revisitation is
done lazily or not at all [Stonebraker,
1987
].
To achieve a transaction-consistent view of historical database states, it is neces-
sary to use the same timestamp for all data-item versions created by a transaction,
and these timestamps must respect the serialization order of the transactions, as
do the commit timestamps [Salzberg,
1994
]. However,
SQL
statements within a
transaction may request “current time.” To address this problem, Jensen and Lomet
[
2001
]andLometetal.[
2005b
] present methods for earlier choice of transaction
timestamps while respecting the serialization order.
The theory of multiversion concurrency control was developed by Bayer et al.
[
1980
] and by Bernstein and Goodman [
1983
], among others. Algorithms can
be found in the textbooks by Bernstein et al. [
1987
], Papadimitriou [
1986
], and
Weikum and Vossen [
2002
], to name a few. Mohan et al. [
1992b
] present an algo-
rithm that uses transient versioning of data items to permit read-only transactions
to run without acquiring locks. Snapshot isolation was defined and analyzed by
Berenson et al. [
1995
].
The isolation anomalies possible at snapshot isolation are discussed by Berenson
et al. [
1995
], Fekete et al. [
2005
], Kifer et al. [
2006
], and Cahill et al. [
2009
],
among others. Cahill et al. [
2009
] present a concurrency-control algorithm based
on snapshot isolation that permits only serializable histories. This algorithm has
been implemented in the
B
ERKELEY
DB
embedded database management system
and in the
I
NNO
DB
transactional backend for
M
Y
SQL
[Cahill et al.
2009
]andalso
in
P
OSTGRE
SQL
[Ports and Grittner,
2012
].
The
I
MMORTAL
DB
system provides both snapshot isolation and full transaction-
time functionality, with permanently stored versions, built into the
SQL
Server
database engine [Lomet et al.
2005a
,
2006
, Lomet and Li,
2009
]. Transactions