ZSBD-2st-1.2-w3.tresc-1.1-Slajd24

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Statyczna walidacja własności stopu

Statyczna walidacja własności stopu


Jak wiadomo z teorii algorytmów formalna analiza własności stopu jest w ogólności problemem nierozwiązywalnym. W praktyce dla weryfikacji własności stopu stosuje się składniową analizę zbioru reguł. Analiza składniowa jest zachowawcza, co oznacza, że istnieją zbiory reguł posiadające własność stopu, które zostaną uznane w wyniku analizy składniowej jako niepoprawne.

Analiza składniowa opiera się na badaniu własności grafu wyzwalania. Graf ten jest konstruowany w następujący sposób. Węzłami grafu są aktywne reguły z analizowanego zbioru reguł. Krawędzie w grafie reprezentują składniowe zależności między regułami. Między węzłami, które reprezentują reguły R1 i R2 jest wstawiana krawędź skierowana od R1 do R2, jeżeli kod akcji reguły R1 zawiera operacje, które są zdarzeniem wywołującym regułę R2. Na poprzednich dwóch slajdach takie zależności zostały pokazane za pomocą strzałek. Brak cyklu w grafie wyzwalania oznacza, że badany zbiór reguł posiada własność stopu. Występowanie cyklu w grafie oznacza, że dany zbiór reguł może nie posiadać własności stopu.

Na rysunku pokazano grafy wyzwalania dla zbioru reguł „zwiększ_rangę i „zwiększ_premię oraz dla reguły „kotwica_budżetowa ”. Ze względu na zachowawczość analizy składniowej mimo, że obydwa grafy są cykliczne, jednak w praktyce tylko pierwsza para reguł nie posiada własności stopu.

Komercyjne aktywne systemy baz danych zazwyczaj dokonują składniowej analizy własności stopu tylko podczas kompilacji pojedynczych reguł. W przypadku zbioru reguł brak własności stopu jest diagnozowany przez system dopiero podczas aktywowania reguł. Dla bardziej złożonych przypadków błąd taki może być wykryty dopiero po długim okresie eksploatacji systemu.


<< Poprzedni slajd | Spis treści | Następny slajd >>