БАЗИ ДАНИХ. МОВИ ЗАПИТІВ, УПРАВЛІННЯ ТРАНЗАКЦІЯМИ,

РОЗПОДІЛЕНА ОБРОБКА ДАНИХ

2.4 Впорядкування та відновлення транзакцій

Призначення протоколів управління паралельним доступом полягає у підготовці такого графіку виконання транзакцій, який виключить можливість їх впливу на результати роботи одна одної, що дозволить уникнути проблем, розглянутих у попередньому розділі.

Одне з очевидних рішень полягає у виконанні в кожний момент часу лише однієї транзакції – попередня транзакція обов’язково повинна бути зафіксована перш, ніж буде дозволено почати виконання наступної транзакції. Однак призначення багатокористувацьких СКБД полягає у забезпеченні максимального ступеня розпаралелення транзакцій користувачів, тому ті транзакції, які не впливають на роботу одна одної, можуть виконуватись одночасно. Виявлення таких транзакцій становить суть процесу  впорядкування транзакцій.

Задачі впорядкування транзакції передбачають побудову графіків виконання транзакцій. Графік виконання транзакцій – це послідовність запуску операцій декількох паралельно виконуваних транзакцій, яка зберігає черговість виконання операцій в кожній окремо взятій транзакції.

У послідовному графіку операції кожної з транзакцій виконуються строго послідовно і не можуть чергуватись з операціями, виконуваними в інших транзакціях. Тобто, за наявності двох транзакцій Т1 і Т2, спочатку має бути виконана транзакція Т1, а після її завершення Т2, або ж навпаки. Таким чином, при послідовному виконанні взаємовплив між транзакціями відбуватись не буде, оскільки в кожний момент часу виконується лише одна транзакція.  

У непослідовному графіку чергуються операції з деякого набору одночасно виконуваних транзакцій.

Суть впорядкування полягає саме в пошуку таких непослідовних графіків, які дозволяють транзакціям виконуватись паралельно без впливу одна на одну. Непослідовний графік називають впорядковуючим, якщо він призводить до отримання таких же результатів, які досягаються при використанні деякого варіанту послідовного графіка.

Розглядаючи умови впорядкування, важливо враховувати послідовність виконання операцій читання та запису даних:

-  Якщо дві транзакції тільки зчитують деякий елемент даних, вони не будуть конфліктувати між собою і послідовність їх виконання не має значення.

-  Якщо дві транзакції зчитують або записують зовсім незалежні елементи даних, вони не будуть конфліктувати між собою і послідовність їх виконання не має значення.

-  Якщо одна з транзакцій записує елемент даних, а інша зчитує або записує цей же елемент даних, послідовність їх виконання має суттєве значення.

Приклад 2.4. Розглянемо графік S1, наведений в стовпцях Варіанта А табл. 2.4. Він встановлює послідовність операцій, що виконуються паралельно в транзакціях Т7 і Т8. Оскільки операція запису даних рахунку bal_X в транзакції Т8 не конфліктує з наступною операцією читання даних рахунку bal_Y в транзакції Т7, можна замінити послідовність виконання цих операцій і отримати еквівалентний графік S2, наведений в стовпцях Варіанту Б цієї ж таблиці. Якщо змінити порядок виконання наступних не конфліктуючих між собою операцій, то можна отримати еквівалентний послідовний графік S3 (Варіант В табл. 2.4).

Графік S3 є послідовним, а оскільки графіки S1 і S2 є еквівалентними графіку S3, вони є впорядковуючими.

Такий тип впорядкування прийнято називати конфліктним впорядкуванням. В конфліктно впорядковуючому графіку порядок виконання будь-яких конфліктуючих операцій відповідає їх розміщенню в послідовному графіку. Згідно з правилом запису, що підкоряється обмеженням (яке говорить, що транзакція повинна оновлювати елемент даних виходячи з його попереднього значення, яке було прочитано транзакцією на початку), для перевірки конфліктного впорядкування можна використовувати граф передування, або граф впорядкування.

Таблиця 2.4 – Еквівалентні графіки: Варіант  А – непослідовний графік S1;

Варіант Б – непослідовний графік S2, еквівалентний графіку S1;

Варіант В – послідовний графік S3, еквівалентний графікам S1 і S2

Для графіка S граф передування виглядає як направлений граф G=(N, E), що складається з множини вершин N, множини направлених ребер Е і формується таким чином.

1. Створюється вершина, що відповідає кожній із транзакцій.

2. Створюються направлені ребра T_i -> T_j, якщо транзакція T_j  зчитує значення елемента, записаного транзакцією T_i.

3. Створюються направлені ребра T_i -> T_j, якщо транзакція T_j  записує значення в елемент даних після того, як він був зчитаний  транзакцією T_i.

4. Створюються направлені ребра T_i -> T_j, якщо транзакція T_j  записує значення в елемент даних після того, як він був записаний транзакцією T_i.

Якщо в графі передування, що відповідає графіку S, існує ребро T_i -> T_j, то в будь-якому послідовному графіку S’, еквівалентному графіку S, транзакція T_i повинна передувати транзакції T_j. Якщо граф передування містить цикли, то відповідний йому графік не є конфліктно впрорядковуючим. 

Впорядковуючими називають такі графіки, які дозволяють зберегти узгодженість бази даних за умови, що жодна з транзакцій цього графіка не буде відмінена. Протилежний підхід дозволяє проаналізувати відновлюваність транзакцій, що входять у даний графік. У випадку відміни транзакції, властивість нерозривності вимагає, щоб були відмінені всі результати її виконання. Однак, якщо в деякому графіку S транзакція T_j використала елемент даних, записаний транзакцією T_i, і зафіксувала свої результати, то відповідно до властивості стійкості відміна транзакції T_i  не може активізувати відміну транзакції T_j (без запуска компенсуючої транзакції). Тому такий графік не володіє властивістю відновлюваності і є недопустимим.

Відновлюваним графіком називається графік, в якому для кожної пари транзакцій T_i  і T_j виконується правило: якщо транзакція T_j  зчитує елемент даних, попередньо записаний транзакцією T_i , то фіксація результатів транзакції T_i  повинна виконуватись до фіксації результатів транзакції T_j.

попередня     ЗМІСТ    наступна

Пєтух А.М., Романюк О.В., Романюк О.Н.

ВНТУ 2016