Вариант решения к домашнему заданию 6.
Задача 1 (25 очков)
Используем знак ‘<’ для указания предшествования действий, La < Lb ознаяает, что La происходит раньше Lb.
Для краткости обозначим Lx = Log(X) и Wx = Write(X), где X=A, B,C, D.
Первое условие определяет порядок действий в протоколе Log :
<START>; La < Lb < Lc < Ld ; <COMMIT T>
второе, что Wa может быть в двух местах: между La и Lb, или между Lb и Lc, последнее условие - что Wb может быть в двух местах: между Lb и Lc и между Lc и Ld. Ясно, что Wd может стоять только между Ld и COMMIT, и Wc может быть между Lc и Ld или между Ld и COMMIT. В силу протокола-возврата все Ws должны быть раньше COMMIT.
Перечислим все последовательности, помещая их вначале в самое левое возможное место и меняя чаще место для Wc, затем - для Wb, и наконец - для Wa (всего 17 последовательностей):
<START>; La < Wa < Lb < Wb < Lc < Wc < Ld < Wd ; <COMMIT T>
<START>; La < Wa < Lb < Wb < Lc < Ld < Wc < Wd ; <COMMIT T>
<START>; La < Wa < Lb < Wb < Lc < Ld < Wd < Wc ; <COMMIT T>
<START>; La < Wa < Lb < Lc < Wc <Wb < Ld < Wd ; <COMMIT T>
<START>; La < Wa < Lb < Lc < Wb <Wc < Ld < Wd ; <COMMIT T>
<START>; La < Wa < Lb < Lc < Wb < Ld < Wc < Wd ; <COMMIT T>
<START>; La < Wa < Lb < Lc < Wb < Ld < Wd < Wc ; <COMMIT T>
<START>; La < Lb < Wb < Wa < Lc < Wc < Ld < Wd ; <COMMIT T>
<START>; La < Lb < Wb < Wa < Lc < Ld < Wc < Wd ; <COMMIT T>
<START>; La < Lb < Wb < Wa < Lc < Ld < Wd < Wc; <COMMIT T>
<START>; La < Lb < Wa < Wb < Lc < Wc < Ld < Wd ; <COMMIT T>
<START>; La < Lb < Wa < Wb < Lc < Ld < Wc < Wd ; <COMMIT T>
<START>; La < Lb < Wa < Wb < Lc < Ld < Wd < Wc; <COMMIT T>
<START>; La < Lb < Wa < Lc < Wc < Wb < Ld < Wd ; <COMMIT T>
<START>; La < Lb < Wa < Lc < Wb < Wc < Ld < Wd ; <COMMIT T>
<START>; La < Lb < Wa < Lc < Wb < Ld < Wc < Wd ; <COMMIT T>
<START>; La < Lb < Wa < Lc < Wb < Ld < Wd < Wc ; <COMMIT T>
Задача 2 (30 очков)
a). Идем от коца протокола. Первая запись <START U>. Поскольку не было <COMMIT U>, это – незавершенная транзакция, мы должны записать <ABORT U> в протокол и обновить его на диске. Така как для этой транзакции не было изменения значений, для нее больше ничего не нужно. Затем мы встречаем запись <T, A, 10>. Така как не было записи <COMMIT T>, T – незавершенная транзакция. Мы должны изменить значение атрибута A на 10 в БД. Последняя запись для просмотра <START T>. Это незавершенная транзакция. Мы должны записать в протокол <ABORT T> и обновить его на диске.
b). Начинаем с записи <T, E, 50>. Поскольку не было <COMMIT T>, это – незавершенная транзакция. Мы должны изменить значение атрибута Е на 50 в БД. Следующая запись <COMMIT U>. U – завершенная транзакция, никаких действий не требуется. Следующая запись <U, D, 40>. U – завершенная транзакция, никаких действий не требуется. Следующая запись <T, C, 30>. T – незавершенная транзакция. Мы должны изменить значение атрибута С на 30 в БД. Следующая запись <U, B, 20>. U – завершенная транзакция, никаких действий не требуется, то же и для следующей записи <START U>. Следующая запись <T, A, 10>. T – незавершенная транзакция. Мы должны изменить значение атрибута А на 10 в БД. Последняя запись для просмотра <START T>. Это незавершенная транзакция. Мы должны записать в протокол <ABORT T> и обновить его на диске.
c). Первая запись <COMMIT T>. Т – завершенная транзакция, все другие записи для этой транзакции могут быть проигнорированы. Следующая запись <T, E, 50> - игнорируется. Следующая запись - <COMMIT U>. U – завершенная транзакция, все другие записи для этой транзакции могут быть проигнорированы. До начала протокола мы видим только записи для транзакций T и U, которые могут быть проигнорированы. Нет необходимости в изменениях БД.
Задача 3 (25 очков)
Используем те же обозначения, что и в задаче 1.
Первое условие определяет порядок действий в протоколе Log:
<START>; La < Lb < Lc < Ld ; <COMMIT T>
Второе условие требует, чтобы Wa было раньше Wc. Третье условие выполняется из-за первого. Пскольку используется протокол-повтора, все Ws должны быть позже COMMIT.
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wa < Wc < Wb < Wd
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wa < Wc < Wd < Wb
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wa < Wb < Wc < Wd
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wa < Wd < Wc < Wb
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wa < Wb < Wd < Wc
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wa < Wd < Wb < Wb
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wb < Wa < Wc < Wd
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wd < Wa < Wc < Wb
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wb < Wa < Wd < Wc
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wd < Wa < Wb < Wc
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wb < Wd < Wa < Wc
<START>; La < Lb < Lc < Ld ; <COMMIT T>; < Wd < Wb < Wa < Wc
Задача 4 (20 очков)
a). T1 – завершенная транзакция, мы должны повторить ее, записав новые значения в следующей последовательности A=50(соответствует записи 2), B=130(запись 4) и A=70(запись 5) на диск.
T2 - незавершенная транзакция, мы должны отменить ее, записав старые значения в следующей последовательности D=10(запись 7), C=10 (запись 6) на диск, мы также должны записать <ABORT T2> в протокол и обновить его на диске.
T3 - незавершенная транзакция. Так как нет записей обновления, мы только должны записать <ABORT T3> в протокол и обновить его на диске.
b). Поскольку контрольная точка не завершена, мыдолжны просмотреть протокол перед <START CKPT (T2,T3)>.
T1 – завершенная транзакция, мы должны повторить ее, записав новые значения в следующей последовательности A=50(соответствует записи 2), B=130(запись 4) и A=70(запись 5) на диск.
T2 – завершенная транзакция, мы должны повторить ее, записав новые значения в следующей последовательности C=20(запись 6), D=30(запись 7), D=40(запись 11), C=70 (запись 13) на диск.
T3 - незавершенная транзакция, мы должны отменить ее, записав старое значение E=10(запись 10). Мы также должны записать <ABORT T3> в протокол и обновить его на диске.
c). То же, что в b) плюс
T4 - незавершенная транзакция. Так как нет записей обновления, мы только должны записать <ABORT T4> в протокол и обновить его на диске.
d). Поскольку контрольная точка не завершена, мы должны просмотреть протокол перед <START CKPT (T2,T3)>.
T1 – завершенная транзакция, мы должны повторить ее, записав новые значения в следующей последовательности A=50(соответствует записи 2), B=130(запись 4) и A=70(запись 5) на диск.
T2 – завершенная транзакция, мы должны повторить ее, записав новые значения в следующей последовательности C=20(запись 6), D=30(запись 7), D=40(запись 11), C=70 (запись 13) на диск.
Т3 - завершенная транзакция, мы должны повторить ее, записав новое значение E=60 (запись 10).
T4 - незавершенная транзакция, мы должны отменить ее, записав старые значения в следующей последовательности G=10 (запись 17), F=10 (запись 16). Мы также должны записать <ABORT T4> в протокол и обновить его на диске.
e). Поскольку контрольная точка завершена, и T1 была завершена перед ее началом, мы не должны ничего делать с T1. Мы должны повторить T2 и T3 но не должны просматривать протокол перед <START CKPT (T2,T3)> для T2 поскольку все обновления T2 перед началом контрольной точки были помещены на диск до ее окончания (контр. точки).
T2 завершенная транзакция, мы должны повторить ее, записав новые значения в следующей последовательности D=40(запись 11), C=70 (запись 13) на диск.
Т3 - завершенная транзакция, мы должны повторить ее, записав новое значение E=60 (запись 10).
T4 незавершенная транзакция, мы должны отменить ее, записав старые значения в следующей последовательности F=150 (запись 21), F=100 (запись 19), G=10 (запись 17), F=10 запись 16). Мы также должны записать <ABORT T4> в протокол и обновить его на диске.
f). Поскольку контрольная точка завершена, и T1 была завершена перед ее началом, мы не должны ничего делать с T1. Мы должны повторить T2,Т3 и T4 но не должны просматривать протокол перед <START CKPT (T2,T3)> для T2 поскольку все обновления T2 перед началом контрольной точки были помещены на диск до окончания контр. точки.
T2 - завершенная транзакция, мы должны повторить ее, записав новые значения в следующей последовательности D=40(запись 11), C=70 (запись 13) на диск.
Т3 - завершенная транзакция, мы должны повторить ее, записав новое значение E=60 (запись 10).
T4 - завершенная транзакция, мы должны повторить ее, записав новые значения в следующей последовательности F=100 (запись 16), G=110 (запись 17), F=150 (запись 19), F=140 (запись 21).
Результаты могут быть сведены в таблицу
A B C D E F G
a 10 10
b 10 10
c 10 10
d 10 10
e 10 10
f
