УПОРЯДОЧІВАЕМОСТЬ

Вище в цьому розділі була закладена основа для вивчення вкрай важливого поняття упорядочіваемості, до чого ми тепер приступаємо Упорядочіваемость – це загальноприйнятий критерій правильної організації чергується виконання безлічі транзакцій іншими словами, така організація виконання вважається правильною тоді і тільки тоді, коли вона є упорядочіваемой3 Будь конкретна процедура організації виконання заданої множини транзакцій є впорядковують (а отже, правильною) тоді і тільки тоді, коли вона еквівалентна деякій процедурі послідовного виконання тих же транзакцій (тобто гарантує досягнення таких

3 У літературі фактично можна знайти визначення двох видів упорядочіваемості – упорядочіваемость з конфліктів (conflict serializability) і упорядочіваемость по перегляду (view serializability) Але поняття упорядочіваемості по перегляду майже не має практичного значення і тому термін упорядочіваемость застосовується як позначення саме упорядочіваемості з конфліктів Додаткову інформацію з цієї теми можна, наприклад, знайти в [1621]

ж результатів) Пояснення до деяким термінам, які використовувалися в даному визначенні, наведені нижче

■&nbsp&nbsp&nbsp&nbsp Послідовним виконанням транзакцій називається така організація їх вико нання, при якій транзакції виконуються одна за одною в деякій по послідовності

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

Нижче дано додаткове обгрунтування застосовуваного визначення впорядковує безлічі транзакцій

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

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

3 Тому має сенс ввести визначення правильної організації чергуються ся виконання операцій окремих транзакцій, причому тільки такий організує ції виконання, яка еквівалентна деякій послідовної організації виконання окремих транзакцій (тобто організація виконання може бути правильною тоді і тільки тоді, коли вона є впорядкує) У цьому формулюванні заслуговує особливої ​​уваги вираз тоді і тільки тоді! Справа в тому, що деякий варіант організації чергується виконання мо же бути неупорядочіваемим і при цьому все одно призводити до результату, кото рий виявиться правильним у деякому певному початковому стані бази даних (див упр 163), але цього недостатньо, оскільки правильна організація чергується виконання має гарантуватися (Тобто бути незалежною від конкретних станів бази даних), а не виникати лише за збігом обставин нізацією

Знову звернувшись до прикладів, наведених у розділі 162 (рис 161-164), можна переконатися, що в кожному з розглянутих випадків проблема полягала саме в тому, що застосовувана процедура організації чергується виконання транзакцій була впорядковувати Це означає, що в цих варіантах виконання спочатку А, потім В або спочатку в, потім А не приводить до отримання однакових результатів Крім того, аналіз матеріалу, викладеного в розділі 164, під цим новим кутом зору показує, що дія суворого протоколу двофазної блокування зводиться саме до того, що він у кожному випадку забезпечує дотримання принципів упорядочіваемості На рис 167 і 168 прийнята організація чергується виконання транзакцій еквівалентна варіанту спочатку в, потім А. На рис 166 і 169 показано, що відбувається взаімоблокіровка, а це означає, що для однієї з двох транзакцій повинен бути виконаний відкат (і, імовірно, повторний запуск на виконання в якийсь подальший

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

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

Слід зазначити, що два різних послідовних графіка, в яких беруть участь одні й ті ж транзакції, цілком можуть виробляти різні результати, і це при тому, що обидва графіка є правильними Це означає, що два різних чергуються правильних графіка, в яких беруть участь одні й ті ж транзакції, також можуть виробляти різні результати Як приклад розглянемо транзакцію А, сенс якої зводиться до того, щоб скласти 1 з х, і транзакцію в, яка має своєю метою подвоїти х (Де х – деякий елемент в базі даних) Припустимо також, що початкове значення х дорівнює 10 У такому випадку послідовний графік А, потім в призводить до отримання результату х = 22, а послідовний графік спочатку в, потім А призводить до отримання результатах = 21 Обидва ці результату в рівній мірі є правильними, і тому будь-який графік, який гарантує еквівалентність послідовним графіками спочатку А, потім В або спочатку в, потім А , також є правильним

Поняття впорядковує ™ було вперше введено (хоча і не під такою назвою)

Есвараном (Eswaran) та ін в [166] Крім того, в тій же статті була доведена важлива теорема, звана теоремою двухфазной блокування, яку ми будемо розглядати у наведеній нижче формуліровке4

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

Протокол двофазної блокування, в свою чергу, формулюється таким чином:

■ перш ніж виконати операцію з будь-яким обєктом (наприклад, кортежем бази даних), транзакція повинна придбати блокування на цей обєкт

■ після звільнення будь блокування транзакція більше не повинна приобре тать небудь додаткові блокування

Таким чином, будь-яка транзакція, яка підпорядковується цьому протоколу, має дві фази: фаза придбання блокувань (або фаза розширення) і фаза звільнення блокувань (або фаза звуження)

4 Двофазна блокування не має нічого спільного з двофазної фіксацією просто ці два терміни мають зовнішню подібність

Примітка На практиці фаза звуження часто зводиться до єдиної операції COMMIT або ROLLBACK, виконуваної в кінці транзакції (до цієї теми ми повернемося в розділах 167 і 168) Якщо дотримується така умова, то даний протокол стає рівносильним суворої версії, яка була описана в розділі 163

Розглянуте тут поняття упорядочіваемості надає значну допомогу в аналізі цієї області, яка може стати джерелом багатьох труднощів, тому в цьому розділі наведено ще кілька додаткових зауважень на цю тему Припустимо, що I – чергується графік, який охоплює деякий безліч транзакцій Т1, Т2, , Тп Якщо графік I є впорядковує, то існує щонайменше один послідовний графік S, який включає безліч транзакцій Т1, Т2, , Тп, такий що I еквівалентний S Графік s називається упорядкуванням графіка I

Тепер припустимо, що Ti і Тj – дві будь різні транзакції в безлічі Т1, Т2, , Тп Припустимо, що Ti передує Tj в упорядкуванні S Тому в чергується графіку I досягнутий ефект організації чергується виконання повинен бути таким, як якби транзакція Ti дійсно виконувалася перед Tj Іншими словами, неформальної, але дуже зручною характеристикою упорядочіваемості є дотримання того вимоги, що якщо А і в – будь-які дві транзакції, які беруть участь в деякому впорядковує графіку, то в цьому графіку або А логічно передує в, або в логічно передує А це означає, що або в може скористатися результатами виконання А, або А – результатами виконання в (Якщо А виробляє вихідні результати х, у, .., z і в отримує в якості вхідних будь-які з даних х, у, .., z, то в в будь-якому випадку отримує ці дані або так, як якби всі вони були виведені транзакцією А, або всі вони були такими, як перед виведенням з транзакції А (тобто перед її виконанням), а не у вигляді суміші результатів цих двох типів) І навпаки, якщо ефект дії чергується графіка не зводиться до такої ситуації, як якби А виконувалася перед в або В виконувалася перед А, то цей графік не можна вважати впорядковує і правильним

Нарешті, необхідно підкреслити таку думку, що якщо деяка транзакція А не є двофазної (тобто не підпорядковується протоколу двофазної блокування), то завжди можна сформувати деяку іншу транзакцію в, яка може виконуватися, чергуючись з А таким чином, що в результаті буде отримано загальний графік, який не є впорядковує і правильним Відзначимо, що з метою зменшення конкуренції за ресурси і підвищення за рахунок цього продуктивності і пропускної здатності, в системах, застосовуваних на практиці, зазвичай дозволено формування транзакцій, що не які є двофазними це означає, що транзакції можуть передчасно звільняти блокування (До виконання оператора COMMIT), а потім купувати інші блокування Але має бути цілком очевидно, що пропозиція використовувати такі транзакції є досить ризикованим при цьому, допускаючи застосування транзакція А, що не є двофазної, можна лише сподіватися на те, що в системі не буде виконуватися одночасно з А транзакція в, яка звертається до тих же даних (оскільки при виникненні зазначеної ситуації система стає здатною виробляти неправильні відповіді)

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


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

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*