![]() |
![]() | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Uspořádatelný rozvrh
Již standard SQL92 stanovuje, aby volání paralelně prováděných transakcí bylo uspořádatelné. O co se jedné, předmětem dnešní databázové abecedy. Jde vlastně o podmínku týkající se rozvrhu transakcí. Sériové rozvrhy zachovávají operace každé transakce pohromadě. Nejprve se provedou operace první transakce a potom druhé transakce. Pro dvě transakce tedy existují 2 sériové rozvrhy, pro N transakcí lze sestavit N! různých sériových rozvrhů. Pro získání korektního výsledku však můžeme použít i rozvrhu, kde jsou operace navzájem prokládány. Přirozeným požadavkem na korektnost je, aby efekt paralelního zpracování transakcí byl týž, jako by byly transakce provedeny v nějakém sériovém rozvrhu. Předpokládáme-li totiž, že každá transakce je korektní program (tj. zachovává konzistenci databáze), měl by být vést výsledek sériového zpracování ke konzistentnímu stavu. O systému zpracování transakcí (SZT), který zaručuje tuto vlastnost se říká, že zaručuje uspořádatelnost. Bohužel, lze nalézt mnoho příkladů, kdy libovolné proložení operací více transakcí nevede ke smysluplnému výsledku. Jako příklad uveďme jednoduchý rezervační systém s čítačem X, kde se přičítají či odečítají počty nových, resp. rušených rezervací. V tabulce 1 běží shora dolů paralelně 2 transakce, třetí sloupec komentuje stav souboru.
Tab. 1 Příklad rozvrhu dvou transakcí Přestože by hodnota X v databázi měla být 79, je 84. Této kolizi se tradičně říká ztráta aktualizace. Mezi další patří dočasná aktualizace, kdy transakce T1 provede aktualizaci X, T2 provede další aktualizaci X a úspěšně ukončí práci, avšak po chybě systému dále je transakce T1 zrušena. Přestože ukončená transakce T2 aktualizovala X, je tato aktualizace ztracena, protože SZT uvede X pomocí ROLLBACK do stavu před započetím T1. Další nekorektnosti objevíme v souvislosti s použitím kurzoru v SQL92. Problémem je, že všichni výrobci relačních SŘBD nezaručují vlastnost uspořádatelnosti. Pro mnoho aplikací stačí, je-li garantována stálost kurzoru, tj. provádí-li aplikace výběr či aktualizaci prostřednictvím kurzoru, je postačující garantovat, že řádky získané operací FETCH neobsahují data z nepotvrzených transakcí. Pohnul-li se kurzor k dalšímu řádku, je již předchozí k dispozici jiným transakcím. Při dodržování uspořádatelnosti toto ovšem není možné. Nějaká transakce nemůže modifikovat řádek, který byl manipulován transakcí, která právě běží (tento princip je ovšem zeslaben ve zpracování pod dvoufázovým uzamykacím protokolem - viz příští díl Databázové abecedy). Stálost kurzoru ovšem korektnost zcela nezaručuje. V SQL92 jsou navrženy tzv. úrovně izolace, které přesně definují korektnost pro jednotlivé úrovně se vztahem pro různé typy úloh. Vidíme, že libovolné prokládání operací z transakcí vede obecně k nekonzistentnímu stavu databáze. Mechanismy, které řídí paralelní zpracování transakcí musí zařídit, aby po skončení všech transakcí byly databáze v konsistentním stavu. Abychom mohli pro nějaký rozvrh určit jeho korektnost, stačí, abychom ukázali, že je v nějakém smyslu ekvivalentní nějakému sériovému rozvrhu. Teorie i praxe zavedla více způsobů, jak zavést takovou ekvivalenci. Většina z nich je založena na pojmu konfliktních operací. Přístupy se liší, jak je konflikt mezi operacemi definován. Uvedeme neformální definici takové ekvivalence založené na komutativitě operací READ a WRITE. Komutativita říká, že dvě operace jsou konfliktní, jestliže výsledky jejich různého sériového volání nejsou ekvivalentní. Neznáme-li nic o sémantice operací, pak zřejmě {READ(A), WRITE(A)}nedává stejnou hodnotu atributu A jako rozvrh {WRITE(A), READ(A)}. Operace WRITE je tedy vždy v konfliktu s operací READ nebo WRITE. Dvě operace, které nejsou konfliktní se nazývají kompatibilní. Kompatibilita a konflikty se obvykle zadávají tabulkou (zde tabulka 2). Indexy znamenají číslo transakce, + , resp. - označuje kompatibilitu, resp. konflikt.
Tab. 2 Komutativita operací READ a WRITE Máme-li rozvrhy S1 a S2 pro množinu transakcí T = {T1,...,TN}, pak S1 s S2 jsou ekvivalentní (vzhledem ke konfliktům), jsou-li splněny dvě podmínky: (1) Jestliže se v jednom rozvrhu vyskytuje READ(A) v transakci Ti a tato hodnota vznikla z WRITE(A) v transakci Tj, potom totéž musí být zachováno v druhém rozvrhu. (2) Jestliže se v jednom rozvrhu vyvolá poslední operace WRITE(A) v transakci Ti, pak totéž musí být zachováno i v druhém rozvrhu. Podmínka (1) zajišťuje, že každá operace READ čte po stejné operaci WRITE v obou rozvrzích, podmínka (2) zajišťuje, že konečný stav databáze je stejný v obou rozvrzích. Jinými slovy řečeno, relativní pořadí konfliktních operací je stejné v obou rozvrzích. Uvažujme transakce T3: {READ(A),akce1(A),WRITE(A),READ(B),akce2(B),WRITE(B)} T4: {READ(A),akce3(A),WRITE(A),READ(B),akce4(B),WRITE(B)} a sériové rozvrhy S3:{T3,T4}, S4:{T4,T3}. Další dva rozvrhy nejsou sériové: S3 S4
Symbolem º budeme značit ekvivalenci rozvrhů. Zřejmě S1 º S2, avšak S1 ù º S3. Vztah S4 k ostatním rozvrhům vyřešíme později. O rozvrhu říkáme, že je uspořádatelný, jestliže existuje sériový rozvrh s ním ekvivalentní. Testování uspořádatelnosti lze provádět algoritmicky. Spíše teoretický přístup předpokládá, že máme dva rozvrhy a zjišťujeme jejich uspořádatelnost pomocí precedenčního grafu. Tento graf má za uzly transakce a hrany jsou definovány podle toho, v jakém pořadí se v rozvrhu vyskytují konfliktní operace. Problém, zdali je rozvrh uspořádatelný je převeden na hledání cyklů v precedenčním grafu. Existuje-li cyklus, rozvrh není uspořádatelný. Např. tak lze ověřit že rozvrh S4 není uspořádatelný. Tato metoda je jednoduchá, ovšem v praxi ne příliš použitelná, protože je příliš statická. Navíc funguje v případě, že operaci WRITE(X) předchází v transakci operace READ(X), což obecně není pravda. Obecnější případ je algoritmicky příliš náročný. Užitečnější a dnes v praxi rozšířené jsou především metody založená na zámcích. Na závěr připomeňme, že se pohybujeme ve světě plochých transakcí (žádné hnízdění) s velmi jednoduchými objekty (atributy). Také pojetí uspořádatelnosti není jedním možným kritériem korektnosti. Mohou existovat rozvrhy, které nejsou ekvivalentní se žádným sériovým rozvrhem podle naší definice a přesto produkují stejný výsledek jako nějaký sériový rozvrh. Pojem konfliktu je v pokročilejších systémech založen na znalosti sémantiky operací. <seznam dílů seriálu> <COMPUTERWORLD> |