1. Definicja dziedziny systemu informacyjnego.

2. Niezależność danych.

3. Rola administratora danych.

4. Etapy rozwoju baz danych.

5. Rola redundancji w bazach danych.

6. Typy powiązań między danymi (poprzeć przykładami).

7. Zasady projektowania baz danych.

8. Definicja dziedziny hierarchicznej.

9. Problem redundancji i związków wieloznacznych w modelu hierarchicznym.

10. Aktualizacja w modelu hierarchicznym.

11. Realizacja prostych i złożonych struktur sieciowych.

12. Optymalizacja kolekcji dla modelu sieciowego.

13. Zależności wykorzystywane w modelu relacyjnym.

14. Etapy normalizacji w modelu relacyjnym.

15. Operacje algebry relacji dla modelu relacyjnego.

16. Typy języków stosowanych w modelu relacyjnym.

17. Weryfikacja odwracalności rozkładu relacji.

18. Różnice i podobieństwa między modelem hierarchicznym, sieciowym i relacyjnym.

19. Tożsamość obiektów w modelu obiektowym.

20. Klasy i enkapsulacja.

21. Struktura i działanie metod

22. Zagadnienie dziedziczenia w modelu obiektowym.

23. Problem wielowersyjności obiektów.

24. Obiekty wielotypowe.

25. Wpływ obiektów kompozytowych na strukturę bazy danych (typy wskazań).

26. Reguły utrzymania poprawności schematu bazy danych w strukturze obiektowej.

27. Model relacyjno-obiektowy bazy danych.

28. Etapy pracy SZBD.

29. Porównanie systemów OLTP i MIS.

30. Zarządzanie transakcjami.

31. Problematyka współbieżności w systemach baz danych.

32. Technologia klient-server.

33. Systemy rozproszone - ocena systemu.

34. Systemy rozproszone - algorytm dekompozycji.

35. Zasady projektowania zabezpieczeń.

36. Techniczne środki bezpieczeństwa baz danych.

37. Szacowanie długości hasła.

38. Metody uwierzytelniania za pomocą haseł.

39. Uwierzytelnianie oparte nie na metodach haseł.

40. Uwierzytelnianie w systemie UNIX.

41. Sposoby badania upoważnień.

42. Poziomy upoważnień.

43. Szyfrowanie - metody klasyczne.

44. Szyfrowanie - zasady metod programowych.

45. Szyfrowanie zbiorów o dostępie bezpośrednim.

46. Szyfry symetryczne - szyfry asymetryczne.

47. Szyfry blokowe - szyfry strumieniowe.

48. Techniki szyfrowania danych.

49. Szyfr DES.

50. Metoda RSA.

51. Metoda Merklego-Hellmana.

52. Szyfrowanie - metody sprzętowe.

53. Bezpieczeństwo systemów kryptograficznych.

54. Zastosowania funkcji jednokierunkowych.

55. Realizacja podpisów cyfrowych.

56. Pozyskiwanie danych z baz danych statystycznych.

57. Ochrona baz danych statystycznych.

1. Dziedzina systemu informacyjnego.

d = <T,{X_t}_tT,A,{V_a}_aA,AA>; gdzie T - zbiór typów, X_t - zbiór obiektów możliwych do opisania zgodnie z typem t; A obejmuje: 1) A_t,t  zbiór nazw atrybutów unarnych, 2) dla każdej (t₁,t₂,...,t_n)  Tⁿ zbiór A_t1, A_t2,...,A_tn - zbiór atrybutów enarnych

2. PROBLEM NIEZALEŻNOŚCI DANYCH

Podstawowym celem baz danych jest zapewnienie niezależności danych, czyli: odporność programów użytkowych na zmiany struktury pamięci i strategii dostępu. Rozróżniamy 2 typy niezależności danych:

1. Fizyczna niezależność danych oznacza, że rozmieszczenie fizyczne i organizacja danych mogą być zmieniane bez zmiany programów użytkowych jak i globalnej struktury logicznej danych.

2. Logiczna niezależność danych oznacza, że globalna struktura logiczna danych może być zmieniana bez zmiany programów użytkowych (zmiany nie mogą oczywiście usunąć danych, z których te programy korzystają).

Niezależność fizyczna wyraża się w tym, że w wyniku zmian struktury pamięci zmienia się jedynie definicja odwzorowania między poziomem pojęciowym a poziomem fizycznym.

Niezależność logiczna wyraża się tym, że w wyniku zmian na poziomie pojęciowym zmienia się tylko definicja odwzorowania między poziomem pojęciowym a poziomem zewnętrznym - umożliwia zachowanie programów użytkowych w nie zmienionej postaci.

odwzorowanie zewnętrzno - pojęciowe

odwzorowanie pojęciowo - fizyczne

Reprezentacja danych:

- poziom pojęciowy - jest on abstrakcyjnym, lecz wiernym opisem pewnego wycinka rzeczywistości.

- poziom wewnętrzny - określa sposoby organizacji danych w pamięci zewnętrznej.

- poziom zewnętrzny - odnosi się do sposobu w jaki dane są widziane przez poszczególne grupy użytkowników.

W strukturę logiczną programu użytkowego władowuje się informacje dotyczące organizacji danych w pamięciach zewnętrznych. Jeżeli jakiś zbiór będzie pamiętany w postaci indeksowo - sekwencyjnej, to układając program użytkowy należy uwzględnić istnienie indeksu (a nawet w pewnych momentach od niego zależeć). Zmiana zbioru indeksowo-sekwencyjnego na zbiór o adresowaniu metodą mieszającą może okazać się niewykonalna w programie użytkowym. Różne programy użytkowe wymagają różnego spojrzenia na te same dane. Np. jeżeli istniały programy użytkowe A i B i każdy z nich miał własny zbiór danych zawierających pole „konto”, ale w programie A zapisuje się je w postaci dwójkowej, a w programie B w postaci dziesiętnej, to zintegrowanie tych zbiorów będzie możliwe wtedy i tylko wtedy, gdy oprogramowanie baz danych wykona wszystkie niezbędne przekształcenia wybranej postaci pamiętania danych do postaci wymaganej przez każdy z programów użytkowych A i B. Jest to przykład istniejącej w bazach danych różnicy między spojrzeniem autora programu użytkowego na dane, a sposobem ich fizycznego zapisu. Musi istnieć możliwość zmiany struktury pamięci (lub strategii dostępu) w wyniku udostępnienia nowych typów nośników pamięciowych, wprowadzania nowych standardów itp. bez konieczności modyfikowania istniejących programów użytkowych. Zmiany w nich pochłaniają dużo czasu (ok. 25% czasu pracy), a jest to strata szczególnie wartościowych zasobów przedsiębiorstwa. (Można by go przeznaczyć na pisanie nowych programów). Niezależność danych jest podstawowym składnikiem cechującym bazy danych, a mianowicie „sprzężeniem z przyszłością”, ponieważ nie można dokładnie określić kierunku rozwoju zastosowań pamiętanych danych.

Schemat kanoniczny jest próbą opisu wewnętrznych właściwości danych. Jeżeli system zarządzania BD korzysta z niego, który nie zmienia się bez względu na rodzaj zastosowanego sprzętu, oprogramowania czy fizycznej struktury danych, to można mówić o prawdziwej niezależności danych. W praktyce nie stosuje się go. Schemat kanoniczny ........................ jest jako model danych, przedstawiający wewnętrzną strukturę danych. Tym samym niezależny jest od poszczególnych dziedzin stosowania danych, jak również od mechanizmów związanych z oprogramowaniem lub sprzętem, które to wykorzystywane są do reprezentowania oraz zachowywania danych.

Statyczna i dynamiczna niezależność danych: o wiązaniu dynamicznym mówimy, gdy wiązanie występuje w momencie wyszukiwania danych. Schemat lub fizyczna organizacja może być wtedy modyfikowana w dowolnym momencie - daje ono dynamiczną niezależność danych. Statyczna niezależność danych wymaga, aby przeprowadzenie zmian w schemacie ogólnym, podschemacie lub fizycznej reprezentacji, zakończyło się zanim dowolny program użytkowy używający tych danych zostanie wykonany. Mamy 3 rodzaje danych:

1. Dane zagregowane? - treść danej mającej nazwę definiuje się tylko raz . Każdy programista odwołujący się do określonej danej musi zakładać tę samą treść tej danej.

2. Dane elementarne - definiuje się tylko raz. Programista odwołujący się do tych danych musi zakładać tę samą ich treść. Z tego samego zbioru danych elementarnych mogą być utworzone różne rekordy lub segmenty.

3. Dane subelementarne - treści tych danych, mających nazwę, mogą być różne w różnych programach użytkowych. I tak np. jeden program może odwoływać się do siedmiocyfrowych, a inny do ośmiocyfrowych danych elementarnych (patrz przykład wyżej).

SCHEMAT - wskazanie wszystkich danych wraz z ich powiązaniami w bazie danych.

PODSCHEMAT - fragment, który interesuje dane osoby operujące na danych np. księgowy, personalny.

3. rOLA ADMINISTRATORA BAZ DANYCH.

Administrator BD odpowiada za:

1. stworzenie pierwotnego opisu BD i odwzorowanie na fizyczną pamięć.

2. udzielanie zezwoleń na różne użytkowanie dla różnych użytkowników.

3. modyfikacje w sensie fizycznej BD i jej organizacji i w sensie powiązań.

4. wykonanie kopii archiwalnych, odtworzenie stanu BD z przed awarii.

Administrator musi biegle znać organizację BD, ale nie musi znać zawartości BD.

4. ETAPY ROZWOJU BAZ DANYCH

ETAP 1: Oprogramowanie obsługuje (wykonuje) tylko proste operacje we/wy. Fizyczna struktura danych taka sama jak logiczna struktura pliku. W programach użytkowych uwzględniono organizację danych w postaci prostych plików seryjnych. Nie istnieje niezależność danych. Zmiana struktury danych lub urządzeń pamięciowych stwarza konieczność ponownego pisania, kompilowania i testowania programów użytkowych. Aktualizacja pliku polega na utworzeniu nowego pliku zawierającego zaktualizowane dane. Jest jednocześnie zachowany plik stary, a także jego poprzednik itd. Prowadzi to do powstania kilku generacji tego samego pliku. Większość plików używano tylko raz. Bardzo wysoki poziom redundancji.

ETAP 2: Możliwy jest bezpośredni dostęp do rekordów (ale nie pól). Logiczna organizacja pliku różni się od fizycznej, ale zależności między nimi są proste. Jednostki pamięci mogą się zmieniać bez konieczności zmieniania programów użytkowych. Struktury danych najczęściej seryjne indeksowo-sekwencyjne lub o prostym dostępie bezpośrednim. Nie korzysta się z wyszukiwania wielokluczowego. Można używać środków zabezpieczania danych. Duża redundancja między innymi dlatego że istnieje tendencja organizowania i optymalizacji danych dla jednego zastosowania. Oprogramowanie umożliwiło zmianę fizycznego rozmieszczenia danych bez potrzeby zmiany ich obrazu logicznego, pod warunkiem, że zostaną w tej samej postaci zawartości rekordów i ogólnej struktury pliku.

ETAP 3: Z tych samych plików fizycznych (danych) otrzymać można wiele różnych plików logicznych a dostęp do jednej i tej samej danej ze strony różnych zastosowań może odbywać się w różny sposób. Prowadzi to do skomplikowania struktur danych. Oprogramowanie umożliwia zmniejszenie redundancji. Elementy danych są wspólne dla wielu zastosowań. Wyeliminowanie redundancji ułatwia zachowanie zgodności danych. Fizyczna organizacja pamięci jest niezależna od programów użytkowych. Można ją zmieniać w celu zwiększenia efektywności BD (baz danych) bez konieczności modyfikacji programów użytkowych. Dane adresowane są na poziomie pól lub grup. Można stosować wyszukiwanie wielokluczowe.

ETAP 4: Oprogramowanie zapewnia logiczną i fizyczną niezależność danych, dopuszczając istnienie globalnego opisu logicznego danych niezależnie od pewnych zmian w obrazie danych programisty, zastosowań lub ich rozmieszczenia fizycznego. Przewidziane są środki zapewnienia niezależności danych. BD może rozwijać się bez większych kosztów. Środki przewidziane dla administratora BD pozwalają mu pełnić funkcję kontrolera i strażnika danych oraz zapewnić taką ich organizację, która będzie najlepsza dla wszystkich użytkowników. Zapewnione są zachowania tajności, bezpieczeństwa i integralności danych. W niektórych systemach są pliki odwrócone umożliwiające szybkie wyszukiwanie danych z bazy. BD konstruowana jest z myślą o zapewnieniu odpowiedzi na nieprzewidziane rodzaje pytań. Oprogramowanie dostarcza język opisu danych administratorowi BD, język komend programiście i język zapytań użytkownikowi.

5. Rola redundancji w bazach danych.

Redundancja to powielanie się danych, zwiększa zajętość pamięci, utrudnia aktualizację, zwiększa koszty, grozi utratą integralności bazy danych

6. TYPY POWIĄZAŃ MIĘDZY DANYMI POPRZEĆ PRZYKŁADAMI DANYCH

Powiązania są to związki między danymi charakteryzującymi środowisko, w którym te dane są.

I. Powiązania proste -> np.:

II. Powiązania złożone ->> , <-> , <<-

np.: 1 kobieta 2 mężczyzn

2 kobiety 1 mężczyzna

Małżeństwo grupowe

np.:

III. Powiązania warunkowe ( c warunek)

np.: c = pod warunkiem, że jest żonaty, mężatką.

IV. Powiązania wielokrotne: (dwa typy danych mogą być powiązane ze sobą na wiele sposobów).

a) Powiązanie "1-1". Dana elementarna A determinuje daną elementarną B tzn. w dowolnej chwili każda wartość A ma 1 i tylko 1 związaną z nią wartość B. (Powiązanie proste)

b) Powiązanie typu "1-wiele" - jednej wartości A odpowiada 0,1 lub wiele wartości B. (Powiązanie złożone)

c) Powiązanie warunkowe od A do B (c). Wartości A odpowiada jedna lub kilka związanych z nią B , pod jakimś warunkiem. (Powiązanie warunkowe)

Powiązanie - odwzorowanie (połączenie) pomiędzy danymi elementami ( lub rekordami ) dostarczające informacji dotyczącej związków między danymi elementarnymi, nie występujące w sposób bezpośredni.

Odwzorowania proste - pomiędzy danymi elementarnymi istnieje tylko 1 połączenie - A identyfikuje B.

Odwzorowanie złożone - pomiędzy danymi elementarnymi istnieje wiele połączeń - A nie identyfikuje B. Zachodzi odwzorowanie w 2 kierunkach więc mamy 4 powiązania: 1:1, 1:wiele, wiele:1, wiele : wiele.

1:1 nazwisko <-> nr pesel , 1:wiele nazwisko <->> marki samochodów

wiele:1 nazwisko <<-> nazwa zakładu pracy , wiele : wiele nazwiska <<->> adresy sklepów

d) Powiązania wielokrotne - pomiędzy danymi zachodzi więcej niż jedno powiązanie. W takim przypadku należy je etykietować, np.:

Dana elementarna - dana niosąca najbardziej elementarną porcję informacji, która nie da się podzielić na mniejsze dane. Można je grupować w rekordy.

7. ZASADY PROJEKTOWANIA BAZ DANYCH.

W projektowaniu BD należy szczególną uwagę na takie ich zorganizowanie, by mogły mieć jak największe zastosowanie oraz by sposób wykorzystania mógł być zwrócić zmieniony szybko i łatwo. Aby zapewnić elastyczność w używaniu danych trzeba mieć na uwadze :

1) dane powinny być niezależne od programów, które z nich korzystają.

Powinno być możliwe zadawanie pytań i przeszukiwanie BD z pisania programów, które z nich korzystają. W innych językach programowania (język zapytań-wymagane zastosowanie). Niekiedy zdarza się zoptymalizować BD. Programista projektujący BD powinien Bardzo dobrze znać zastosowanie bazy i znać środowisko dla której tworzy bazę danych. Przy projektowaniu BD należy uwzględnić wszystkie cechy BD opisane w pytaniu 3.

Schematy przyszłościowe-które korzystając ze słownika danych opisywałyby struktury danych nie występujące jeszcze w systemie. Schematy inteligentne-tak potrafią wykorzystać powiązania między danymi, że wiedzą wszystko na temat znaczenia lub treści danego powiązania. Musimy wiedzieć jaki model BD wybrać: relacyjny, hierarchiczny czy sieciowy. Aby dobrze zrobić BD należy wyspecyfikować wszystkie dane jakimi operujemy i dokonać powiązań między nimi-jest to najważniejsze. Należy się dobrze orientować w powiązaniach danych. W systemie 3 kryteria zabezpieczeń powinny być zaimplementowane -patrz pytanie 22.

Projektant systemu powinien przy projektowaniu systemu spełnić następujące zasady:

1. projektant systemu BD powinien być jawny. Powinny być nawet ujawnione rodzaje ubezpieczeń, ale bez odpowiednich kluczy, algorytmów rozwiązujących.

2. System powinien być łatwy w obsłudze tzn. akceptowalność.

3. Ekonomiczność.

4. Projekt powinien w pełni uczestniczyć w całkowitym pośrednictwie między danymi, a użytkownikiem.

5. Administrator (problem projektant) powinien przydzielić jak najmniejsze przywileje użytkownikom.

Projekt powinien zakładać udzielanie użytkownikom przywilejów i dokładać ich, a nie odejmować.

,mimo to system musi umieć sprawnie reagować na żądania nieprzewidziane. Powinien być otwarty na modyfikacje tj. aktualizację, dopisywanie nowych danych jak i mechanizmy rozbudowy do BD. Projektowanie BD rozpoczyna się od stworzenia schematów zewnętrznych dla poszczególnych użytkowników. Powstałe schematy łączymy następnie tworząc model konceptualny BD. Musimy dokonać wyboru co do typu organizacji danych pomiędzy modelem: sieciowym, hierarchicznym i relacyjnym. Należy zaprojektować system zarządzania BD, który będzie pośredniczył w dialogu człowiek-nabywca. System zarządzania powinien tworzyć proste i przejrzyste schematy dla poszczególnych programistów oraz powinien zapewniać niezależność fizyczną i logiczną danych i programów. W systemie powinna być minimalna redundancja. System powinien zapewniać integralność i poufność danych. BD musi być dogodna pod aktualizacją informacji, który by nie zakłócał jej pracy. System musi zapewniać użytkowanie programistom możliwość korzystania z danych poprzez dogodny w obsłudze czyli manipulowania danymi. Systemy powinny przyjmować dane wprowadzone jeszcze przed ich instalacją tzn. sprzężenie z przeszłością i przyszłością. schematu danych:

1. Łączenie danych elementarnych w grupy powinno być przejrzyste.

1. Z schematu powinno wynikać, które nazwy są nazwami danych element., zagregowancych, subelementarnych, segmentów, pól itd.

1. Nie wolno duplikować nazw.

1. Należy wyróżnić klucze główne.

1. klucze wtórne są ważnym elementem schematu należy je wyróżnić.

1. Ze schematu powinno wynikać, które powiązania są proste, a które złożone.

1. Jeśli powiązania mają należy je przedstawić w schemacie.

1. Klucz główny-jednoznacznie identyfikuje rekord.

9. Klucz - jednoznacznie identyfikuje grupy rekordów: - identyfikator złożony z kilku pól rekordu, - dana będąca kluczem rekordu w innym pliku.

8. DZIEDZINA MODELU HIERARCHICZNEGO.

D = <T,{X_t}_tT,A,{V_a}_aA,AA> jest dziedzina hierarchiczną wtedy i tylko wtedy, gdy : 1) A są atrybutami unarnymi, 2) wszystkie typy są rozłączne, czyli t₁,t₂ X_t1  X_t2  0, 3) dla dowolnego węzła AA atrybutu nieterminalnego dochodzi jedna krawędź, 4) dla żadnego z węzłów określającego typy w grafie nie zachodzi relacja t *~> t, tT; gdzie *~> - tranzytywne domknięcie węzła t.

9. PROBLEM REDUNDANCJI I ZWIĄZKÓW WIELOZNACZNYCH W MODELU HIERARCHICZNYM

Hierarchia jest siecią, której powiązania tworzą las. Każde powiązanie jest związkiem jednoznacznym między następnikiem, a poprzednikiem. Przekształcając sieć w strukturę drzewiastą mamy 2 podejścia :

1. Wprowadzić redundancję dla zobrazowania związków wieloznacznych, np.

jaja mąka sól x y z

1,2 3,10 2,5 1,2 3,10 2,5

Nadmiarowa postać hierarchii, brak połączenia TOWARY-CZŁONKOWIE eliminuje pytanie o to , jakie towary chcą konkretni członkowie.

2.Wprowadzić do struktury rekordy wirtualne, które pozwalają na jawne powielanie rekordów bez redundancji.

Wirtualny typ(?) rekordu jest interpretowany jako wskaźnik do fizycznego rekordu T. Powiązania w hierarchii są jednokierunkowe, pociąga to za sobą utratę pewnych informacji, których mogłyby dostarczyć powiązania niedozwolone w tym modelu. Problem ten w pewien sposób rozwiązują rekordy wirtualne, np.:

Związki wieloznaczne można przedstawić w następujący sposób:

Możliwa jest również implementacja wprowadzająca rekordy wirtualne wskazujące na poprzedniki.(nie jest to już struktura drzewa, zakłóca się kierunek poruszania). Przy tej implementacji możliwe jest ujęcie wszystkich powiązań między danymi, z czego musielibyśmy zrezygnować w strukturze drzewiastej.

Podstawowymi elementami modelu hierarchicznego są rekordy logiczne, powiązane ze sobą tworzą drzewo rek. Drzewo jest szczególnym przypadkiem grafów, w którym do każdego z wierzchołków może dochodzić co najwyżej 1 krawędź, z każdego wierzchołka może wychodzić dowolna ilość gałęzi. Zbiór drzew rekordów tworzy las. Wygodnie jest połączyć wszystkie drzewa w jedno posługując się korzeniem pomocniczym.

10. AKTUALIZACJA W MODELU HIERARCHICZNYM

Model hierarchiczny charakteryzuje się tym, iż rekordy logiczne są przechowywane w węzłach drzewa. Ze względu na to, że model hierarchiczny wymaga, aby następnik miał tylko 1 poprzednika, przy czym poprzednik może mieć wielu następników. Przy aktualizacji w takim modelu pojawia się problem usuwania rekordów logicznych bez utraty informacji. (usuwając węzeł tracimy informacje zawarte w poddrzewie). Również przy wstawianiu rekordu do struktury pojawia się problem odszukania właściwego miejsca w strukturze drzewa.(problem odszukania miejsca).Gdy w drzewie mamy problem z redundancją (wywołaną związkami wieloznacznymi) wówczas przy aktualizacji pojawia się problem zachowania integralności danych. (zmiany należy dokonać we wszystkich wystąpieniach aktualizowanego rekordu). Gdy w drzewie usunięta jest redundancja poprzez zastosowanie rekordów wirtualnych, aktualizacja nie zagraża integralności danych, gdyż zmian dokonujemy tylko w 1 miejscu - rzeczywistego wystąpienia rekordu; pozostałe wystąpienia tego rekordu są reprezentowane w postaci wskaźników. W implementacjach aktualizację polegającą na usunięciu rekordu realizuje się wprowadzając do rekordu tzw. bit usunięcia, którego wartość decyduje o tym czy rekord jest usunięty czy też nie (jest to związane z możliwością utraty danych - następników usuwanego rekordu). Z poziomu programisty zastosowań aktualizację przeprowadza się za pomocą języka manipulowania danymi. Dla modelu hierarchicznego przykładem języka jest DL/I.

Przykłady komend aktualizacji:

INSERT s - wstawienie rekordu s jako potomka bieżącego rekordu.

DELETE s - usunięcie bieżącego rekordu.

REPLACE - zastąpienie bieżącego rekordu rekordem z obszaru roboczego.

11. Realizacja prostych i złożonych struktur sieciowych.

PROJEKTOWANIE STRUKTURY LOGICZNEJ BD DLA MODELU SIECIOWEGO

Model sieciowy-korzystając z modelu sieciowego, przedstawiamy schemat pojęciowy w postaci grafu uogólnionego, którego węzły odpowiadają klasom obiektów, a łuk między 2 węzłami reprezentuje. Może to być dowolny graf, a nie jak w przypadku modelu hierarchicznego wyłącznie struktura drzewiasta.

Zasady projektowania schematu (CODASYL): jeżeli mamy dane 2 typy rekordów S i R to:

1. rekordu typu R może wychodzić dowolna liczba wiązań,

1. do rekordu typu S może dochodzić dowolna liczba wiązań,

1. między 2 rekordami typu R i S może istnieć wiele różnych wiązań od R do S i od S do R. W modelu sieciowym rekord może mieć dowolną liczbę rekordów bezpośrednio podrzędnych i nadrzędnych (wiązanie M : M)

1. wyklucza się wiązanie dla rekordów typu R do rekordu typu R (pętla) - ograniczenie to można rozwiązać (wynika to z nadrzędności i podrzędności rekordów).

Podstawowymi konstrukcjami w modelu sieciowym są: rekord logiczny-zgrupowane dane elementarne, każdy rekord logiczny należy do klasy rekordów zwanej typem rekordów.

wiązanie-reprezentacja powiązania, jest to mechanizm dostępu w modelu sieciowym. Wiązanie określa się między 2 typami rekordów R i S w wybranym kierunku.

Wnioski z zasad tworzenia: w modelu sieciowym wszystkie związki między danymi muszą być binarne i jednoznaczne. Związek binarny -zw. charakteryzujący się tym, że albo zachodzi między 2 rekordami albo nie ma innej możliwości, Związek jednoznaczny -z każdym rekordem S i określonego typu S skojarzony jest co najwyżej 1 rekord r typu R, przy czym z rekordem r typu R może być skojarzonych wiele rekordów typu S. Te cechy związków między danymi pozwalają zastosować prosty graf zorientowany jako model danych (sieć). Wierzchołki odp. typom rekordów, jeśli istnieje powiązanie między 2 typami rekordów oraz powiązanie to jest jednoznaczne z R w S to rysujemy krawędź z R do S i mówimy, że powiązanie jest z R do S. Wierzchołki i krawędzie powinny być zaetykietowane: np.

Struktura sieciowa złożona:

(związki M : M)

Struktura sieciowa prosta:

(bez M : M związków)

12. Optymalizacja kolekcji dla modelu sieciowego.

13. zależności wykorzystywane w modelu relacyjnym.

Postulaty Codd'a:

1. Każdy element tablicy reprezentuje sobą jedną elementarną daną.

1. Elementy jednej kolumny należą do jednego ze zbiorów wartości prostych.

1. Każdej kolumnie przyporządkowana jest nazwa zwana atrybutem.

1. W tablicy nie mogą występować dwa identyczne wiersze.

1. Kolejność występowania kolumn i wierszy jest dowolna.

Model relacyjny - opiera się na matematyczny pojęciu relacji. Relacja stanowi zbiór krotek o ustalonej długości n.

1/zależność funkcyjna,

2/pełna zależność funkcyjna,

3/przechodnia zależność funkcyjna,

4/wielowartościowa zależność funkcyjna,

5/połączeniowa zależność funkcyjna.

Wyjściem do tworzenia BD jest wyróżnienie rodzajów danych, które mają być w niej zawarte. Rodzaje w relacyjnych BD to atrybuty. Z każdym atrybutem związany jest zbiór wartości. Zbiór wszystkich możliwych wartości atrybutu A nazywamy jego dziedziną i oznaczony (A) np. (wiek)={0…110}. Zbiór wybranych atrybutów, których używaliśmy do budowy BD A1,A2,…An nazywamy schematem relacji i oznaczamy przez R(A1,A2,…,An). Dla danego schematu relacji ciąg wartości jego atrybutów nazywamy krotkę i oznaczamy przez t np. dla R(A1,…,An) krotką jest t=<a₁,…,a_n>, gdzie a1∈dom(A1), a2∈dom(A2),…, an∈dom(An). Relacją określoną na danym schemacie nazywamy skończony zbiór krotek. Relację oznaczamy r(A1,…,An); gdzie (A1,…,An) = {<a1,…,an>:a1∈dom(A1)…an∈dom(An)}.

Relację najczęściej reprezentuje się za pomocą tablicy, której odp. krotkę, a kolumny atrybutom.

1. Atrybut B relacji r jest funkcjonalnie zależny od atrybutu tej relacji, jeśli zawsze każdej wartości a atrybutu A odpowiada nie więcej niż 1 wartość b atrybutu B. Mówimy, że A identyfikuje (determinuje) B. A → B.

Zbiór identyfikujący relacji - zb. atrybutów tej relacji, których kombinacje wartości jednoznacznie identyfikują każdą krotkę tej relacji.

Klucz - zbiór identyfikujący relacji, którego żaden podzbiór nie jest zbiorem identyfikującym relację. Klucz prosty-jednoelementowy. Klucz złożony-wieloelementowy. Klucz główny - minimalny zestaw atrybutów dający możliwości jednoznacznej identyfikacji obiektu.

Klucz wtórny - każdy z atrybutów, za pomocą którego selekcjonuje się obiekty systemu.

2.Atrybut B relacji r jest w pełni funkcjonalnie zależny od zbioru atrybutów X, jeżeli jest funkcjonalnie zależny od niego, ale nie jest funkcjonalnie zależny od żadnego podzbioru zbioru X (zbiór X jest zbiorem min, od którego zależny jest atr. B)

3. Niech X,Y,Z będą trzema rozłącznymi podzbiorami atrybutów danej relacji. Podzbiór atrybutów Z jest przechodnio - funkcjonalnie zależny od podzbioru zbioru atrybutów X, jeżeli podzbiór atrybutów Z jest funkcjonalnie zależny od podzbioru atrybutów Y, podzbiór atryb. Y jest funkcjonalnie zależny od podzbioru atryb. X, natomiast podzbiór atryb. X nie jest funkcjonalnie zależny od podzbioru atryb. Yi podzbiór atryb. Y jest funkcjonalnie zależny od Z. np.

Z przechodnio funkcjonalnie zależne od X.

4. Mówimy, że podzbiór atryb. Y, jest wielowartościowo zależny od podzbioru X w schemacie R, jeżeli w dowolnej relacji r w schemacie R i dowolnej pary krotek t1 i t2 z relacji r, takich że t1[x]=t2[x] istnieje taka para krotek s1 i s2 w relacji r, że: s1[x]=s2[x]=t1[x]=t2[x] oraz s1[y]=t1[y] i s1[R-X-Y]=t2[R-X-Y], oraz s2[y]=t2[y] i s2[R-X-Y]=t1[R-X-Y].

Jeżeli dla dowolnej pary kotek t1 i t2 z relacji r, takich że wartości tych krotek dla atrybut. z podzbioru X są sobie równe (t1(x)=t2(x)) zamieniamy wartości w tych krotkach atrybutów z podzbioru Y, to otrzymane w taki sposób krotki S1 iS2 też należą do relacji r, np. Relacja : Języki X=<Nazwisko>, Y=<Język progr.>, X-Y=<Język Obcy>, t1=<Nowak, C, Angielski >, t2=<Nowak,Pascal,Francuski> odpowiada para krotek S1=<Nowak, C, Francuski >, S2=<Nowak, Pascal, Angielski >

5. Mówimy, że w schemacie relacji: R(A1,…,An) występuje połączeniowa zależność funkcjonalna co zapisujemy [R1, R2,… ,Rm] <=> dla dowolnej relacji r schematu R zachodzi r=_R1(r) |X| _R2(r) |X|...|X| _Rm(r). Relację r można zdekomponować na zbiór podrelacji r₁…r_m przez wykorzystanie sekwencji operacji funkcji _R1(r),…, _Rm(r), a następnie można zrekonstruować relację pierwotną przez wykonanie sekwencji połączenia relacji r₁…r_m. Wielowartościowa zależność funkcjonalna stanowi szczelny przypadek połączeniowej zależności funkcjonalnej dla m=2.

14. ETAPY NORMALIZACJI W MODELU RELACYJNYM

I Postać normalna

Wymagania: dziedziną atrybutów muszą być wartości elementarne (nierozkładalne).

np.: nie są relacją dane zapisane w postaci:

relacja sprowadzona do I postaci normalnej:

II Postać normalna - Boyce'a

Relacja jest w drugiej postaci normalnej jeżeli dla każdej zależności X->Y, w kórej Y nie zawiera się w X , zbiór X zawiera klucz (tzn. X jest nadkluczem). Relacja w drugiej postaci normalnej nie zawiera redundancji i anomalii.

Aby doprowadzić relację do II postaci normalnej można przeprowadzić operację rozkładu schematu relacji.

Dowolną relację można przekształcić do postaci normalnej Boyce'a dokonując jej rozkładu na kilka innych relacji. Z relacji tych można zawsze otrzymać relację pierwotną w wyniku ich naturalnego złączenia.

np.: <nazwisko, ulica, miasto, województwo, data, wielkość>

zależności: nazwisko -> ulica,miasto,województwo

nazwisko,data -> wielkość

miasto -> województwo

klucz : {nazwisko, data}

Podział 1: R1 <nazwisko, ulica, miasto, województwo>

R2 <nazwisko, data, wielkość>

Podział 2: R3 <nazwisko, ulica>

R4 <miasto,województwo>

R!, R2, R3, R4 są drugiej postaci normalnej.

15. OPERACJE ALGEBRY RELACJI DLA MODELU RELACYJNEGO.

Algebra relacji jest zbiorem operacji wysokiego poziomu wykonywana na relacjach. Język oparty o algebrę relacji, to język, którego elementami są relacje i wynik też jest relacją. Każdy z tych elementów definiuje się przy pomocy specjalnych operatorów. Relacja jest pełnym zbiorem.

Algebra relacji składa się z dwóch grup operacji:

1. tradycyjne działania na zbiorach (suma, przecięcie, różnica);

2. specjalne operacje relacyjne (wyboru, rzutu, łączenia i dzielenia).

Ad b)

1* SELECT (wybór) - polega na wyborze tych krotek relacji, które spełniają określoną własność. Własność tę zapisuje się w postaci formuły logicznej używając operatorów logicznych: ∧ koniunkcja, ∨ alternatywa, ¬ negacja oraz operatorów porównania: = równy, <, >, ≤, ≥, ≠.

Operacje selekcji R:W, której argumentem jest relacja R, a warunkiem wyboru krotek wartość W, definiujemy następująco:

|| R:W(x) || = || R(x) ∧ W(x) albo Koziołka σ_{E = warunek}(R)

Np.: Relacja uczeń

KLASA	IMIĘ	MIASTO	SPORT	DATA_UR
2 3 2	P H E	G K B	S1 S2 S3	1.10.86 2.12.85 3.3.87

Na podstawie następujących warunków wyboru:

W1:Miasto=”G” ∧ Data_ur ≤12.11.86.

dokonuje się wyboru określonych krotek relacji Uczeń.

albo Koziołka: σ_MIASTO=G (UCZEŃ), σ_SPORT=S1 (UCZEŃ)

lub

σ_{MIASTO=G ∨ SPORT=S1}(R)

2* PROJECT Π_R(A,B …) (projekcja)

Dana jest relacja R(X,Y), w której wyróżniono atrybut X przyjmuje wartości z dziedziny D oraz atrybut Y. W wyniku projekcji relacji R względem atrybutu Y zapisujemy w postaci R(X,Y) {Y}, uzyskujemy relacje o atrybucie Y.

NP.: Relacja R(Część, Dostawca, Projekt)

CZĘŚĆ	DOSTAWCA	PROJEKT
a d a	Jan Piotr Jan	1 2 1

Π_R(Dostawca, Projekt) ⇒ wynik ↓

DOSTAWCA	PROJEKT
Jan Piotr	1 2

Dzięki operacji projekcji można skonstruować relację, która zawiera informacje o tym, jaki dostawca dostarcza (daną część) w danego projektu.

3* JOIN - łączenie relacji R1 IXI R2 —> jest to suma logiczna relacji standardowych
tu IXI

R1

A	B
1 2	4 5

R2

C	D
7 8	9 10

R1 IXI R2

A	B	C	D
1 2	4 5	7 8	9 10

5 - zależność normalna (join zależność połączeniowa)

W relacji R o schemacie R(A₁, …, A_n) występuje join zależność N(R₁, …, R_m) wtedy dla dowolnej relacji R w tym schemacie zachodzi, że

r = Π_R1(v) IXI Π_R2(v) IXI … IXI Π_Rn(v)

Oznacza to, że join - zależność występuje jeżeli po rozbiciu tej relacji przez PROJECT i wykonaniu na tym JOIN uzyskamy tożsamość.

W danej relacji R występuje piąta zależność normalna, gdy :

— występuje w niej 4-ta zależność normalna

— jest tu join zależność zależna od klucza JD IXI (R₁, …, R_m)

PROJECT

Oper. projekcji umożliwia utworzenie „ pionowego” podzbioru relacji przez wybór określonych atrybutów.

SELECT

Oper. selekcji umożliwia utworzenie „poziomego” podzbioru relacji przez wybór krotek spełniających określony warunek.

JOIN

Oper. połączenia polega na scaleniu odpowiednich krotek dwóch różnych relacji pod warunkiem spełnienia warunku logicznego Θ nałożonego na atrybuty połączeniowe.

R1 × R2 - relacje

A1 — atr. ∈AR1 (zb. atrybutów R1) ⇒ R1 IXI R2

A2 — atr. ∈AR2 (zb. atrybutów R2) Θ

gdzie warunek Θ ma postać A1 = A2

16 TYPY JĘZYKÓW (SZTUCZNYCH) STOSOWANYCH W MODELU RELACYJNYM

W modelu relacyjnym stosuje się dwa typy języków sztucznych. Mianowicie : język algebraiczny oraz języki predykatowe.

JĘZYK ALGEBRAICZNY : Podstawę języka algebraicznego stanowi założenie mówiące o tym, że informacja, którą chcemy wybrać z bazy danych, daje się wyrazić w postaci relacji powstałej w wy- -niku wykonania szeregu operacji jedna po drugiej, których argumentami są relacje istniejące w BD.

Operacje języka algebraicznego - patrz pytania nr.18.

W języku algebraicznym w składni operacji, które zdefiniowaliśmy, uwzględnialiśmy zawsze nazwy atrybutów relacji. Można przyporządkować poszczególnym nazwą atryb.relacji numery kolumn w tablicy relacji, przy założeniu, że jest to przyporządkowanie wzajemnie jednoznaczne. Nie wszystkie operatory są proste tzn. dają się przedstawić za pomocą innych operatorów. Jest to zamierzone, gdyż chodzi o ułatwienie użytkownikowi formuowania żądań kierowanych do systemu BD.

JĘZYKI PREDYKATOWE opierają się na rachunku predykatów pierwszego rzędu.

Predykat definiuje się opierającna pojęciach zbioru X i zmiennej x przyjmującej wartości z X. Predykat P(x) jest funkcją zdaniową, która staje się zdaniem, gdy w miejsce zmiennej x podstawimy dowolną wartość ze zbioru X. Określenie wartości logicznej predykatu polega na przyporządkowa- -niu mu jednej z dwóch wartości: prawda lub fałsz. 1-argumentowy predykat P(x).

Wieloargumentowy P(x₁,x₂,...,x_n) x₁∈X₁, x₂∈X₂ , ... , x_n∈X_n.

• JĘZYK PRZEDMIOTOWY : → def.predykatu. Zmienna wolna tzn. nie związana żadnym kwantyfikatorem. Zmienna zamknięta to związana kwantyfikatorem. Pytanie zamknięte odpo-

-wiada formule zamkniętej. Pytanie otwarte odpowiada formule otwartej. Jeśli P jest symbolem

predykatu n-argumentowego,a t₁,t₂,..,t_n są termami, to P(t₁,t₂,...,t_n) jest formułą atomową.

• RACHUNEK PREDYKATÓW O ZMIENNYCH KROTKOWYCH (też języki predykato- -we-odmiana) : zmienne odpowiadają krotkom relacji.

• RACHUNEK PREDYKATÓW O ZMIENNYCH ATRYBUTOWYCH : zasady zgodne jak przy konstruowaniu formuły. Wyjątek : zmienne wyrażeń przyjmują wartości z dziedzin związa- -nych z poszczególnymi atrybutami relacji..

Języki te są językami kwerend stanowiących podstawę określonych języków manipulowania danymi opracowanych dla konkretnych systemów relacyjnych.

Ad1. Przykładem języka opartego na algebrze relacji jest język ISBL. W języku tym podajemy kolejność operacji, a więc mówimy w jaki sposób uzyskać daną informacje. Jest to język procedu- -ralny. Odpowiedniość operatorów i argumentów alg.relacji jest następująca : R∪S → R+S; R−S → R−S; R∩S → R•S; R S → R.S; δ_F(R) → R:F; Π_A1,...,An(R) → R % A₁,...,A_n

DEFINICJA RELACJI

Relacją n-członową nazywamy podzbiór iloczynu kartezjańskiego D₁× D₂×...×D_n i elementami takiej relacji o n-członach są krotki. Relację n-członową definiuje się na gruncieteorii modeli relacyjnych przez (1) podanie atrybutów zbioru relacji X={X₁,X₂,...,X_n}.(2) przypisanie każdemu z atrybutów X_i odpowiedniej dziedziny D_i.(3) określenie predykatu relacji.

Intensja relacji odpowiada znaczeniu relacji, można powiedzieć, że predykat związany z relacją stanowi element jej intensji. Ekstensja relacji - zbiór krotek spełniających własności, które stanowią intensję relacji (pojęcie równoważne relacja).

Klucz relacji stanowi najmniejszy zbiór atrybutów relacji, których wartości pozwalają wskazać każdą z krotek relacji.

Zależność funkcyjna Y od X jest pełną , jeżeli dla żadnego podzbioru właściwego X' zbioru atrybutów X nie jest spełniona zależność X'→Y.

X jest kluczem relacji R(X,Y,Z), jeżeli zależność funkcyjna Y od X jest pełną zależnością funkcyjną.

17 WERYFIKACJA ODWRACALNOŚCI ROZKŁADU RELACJI (algorytm)

Dane : schemat relacji : R = A₁,...,A_n ; zbiór zależności funkcyjnych F; rozkład ρ(R₁,...,R_k)

Wynik : stwierdzenie, czy ρ jest rozkładem odwracalnym.

Metoda : Konstruujemy tablicę o n kolumnach i k wierszach. j-ta kolumna odpowiada atrybutowi A_j, a i-ty wiersz odpowiada schematowi relacji R_i. Jeśli A_j jest atrybutem R_i to na przecięciu i-tego wiersza i j-tej kolumny wstawiamy symbol a_j. Jeżeli nie wstawiamy tam b_ij. Każdą z zależności X→Y z F ”rozważamy wielokrotnie” - dopóki w tablicy nie można dokonać żadnej zmiany. Za każdym razem, gdy rozważamy X→Y szukamy wierszy zgodnych we wszystkich kolumnach i odpowiadającym atrybutom X. Jeśli znajdziemy dwa takie wiersze zamieniamy w nich symbole odpow.atrybut.Y.(jeśli jednym jest a_j to drugi staje się też a_j lub jeśli jednym jest b_ij, a drugi b_ij to oba stają się b_ij).

Gdy po zmodyfikowaniu wierszy tablicy odkryjemy, że jeden wiersz przybrał postać a₁,...,a_n to rozkład jest odwracalny, jeżeli nie to rozkład jest nieodwracalny.

Rozkładem schematu relacji R ={A₁,...,A_n}nazywamy układ ρ = (R₁,...,R_k) złożony z podzbiorów R, takich że R = R₁ ∪ R₂ ∪...∪ R_k. Jednym z motywów dokonywania rozkładów jest to, że można wyeliminować : a) redundancję; b) potencjalną niespójność czyli anomalia przy aktualizacji; c) anomalia przy wyszukiwaniu (nie można wstawiać tylko 1 wartości - trzeba wypełnić całe pola); d) anomalia przy usuwaniu.

Przykład : Relacja R = ABCDE A→C C→D R₁= AD R₂= AB R₃= BE R₄= CDE R₅= AE

B→C DE→C

CE→A

Macierz : A B C D E Mamy : A B C D E

R₁ a₁ b₁₂ b₁₃ a₄ b₁₅ Zastosowano R₁ a₁ b₁₂ b₁₃ a₄ b₁₅ Stosuję

R₂ a₁ a₂ b₂₃ b₂₄ b₂₅ zależność : R₂ a₁ a₂ b₁₃ b₂₃ b₂₅ zależność:

R₃ b₃₁ a₂ b₃₃ b₃₄ a₅ A→C R₃ b₃₁ a₂ b₁₃ b₃₄ a₅ C→D

R₄ b₄₁ b₄₂ a₃ a₄ a₅ B→C R₄ b₄₁ b₄₂ a₃ a₄ a₅

R₅ a₁ b₅₂ b₅₃ b₅₄ a₅ R₅ a₁ b₅₂ b₁₃ b₅₄ a₅

A B C D E Ostatecznie : A B C D E

R₁ a₁ b₁₂ b₁₃ a₄ b₁₅ Zależność R₁ a₁ b₁₂ b₁₃ a₄ b₁₅

R₂ a₁ a₂ b₁₃ a₄ b₂₅ DE→C R₂ a₁ a₂ b₂₃ a₄ b₂₅ Rozkład jest

R₃ b₃₁ a₂ b₁₂ a₄ a₅ CE→A R₃ a₁ a₂ a₃ a₄ a₅ odwracalny

R₄ b₄₁ b₄₂ a₃ a₄ a₅ R₄ a₁ b₄₂ a₃ a₄ a₅

R₅ a₁ b₅₂ b₁₃ a₄ a₅ R₅ a₁ b₅₂ a₃ a₄ a₅

18 RÓŻNICE I PODOBIEŃSTWA MIĘDZY MODELEM HIERARCHICZNYM, SIECIOWYM I RELACYJNYM

Model relacyjny : WADA-mała wydajność maszynowa. ZALETY-prostota, elastyczność, dokładność, zabezpieczenie-można łatwiej implementować kontrolę zabezpieczeń dla każdej relacji można określić upoważnienia do dostępu,możliwość powiązań, łatwość implementacji, niezależność danych, język manipulowania danymi, przejrzystość logicznej bazy danej przy użyciu strzałek.

Relację można uważać za szczególny przypadek hierarchii, składającej się tylko z rekordu nadrzędnego. Natomiast hierarchię można uważać zaszczególny przypadek sieci, w której rekord podrzędny ma dokładnie jeden rekord nadrzędny.

Porównanie modeli :

Konstrukcja :

• w schemacie relacyjnym cała zawartość BD jest przedstawiona za pomocą relacji n-członowej(1 konstrukcja).

• w schemacie sieciowym mamy co najmniej 2 konstrukcje danych istotnych, zbiór bazowy (rekordy logiczne), zbiór .......(powiązania).

• w hierarchicznym mamy porządek rzeczywisty czyli hierarchiczny, struktura drzewiasta.

Redundancja i integralność danych:

• w schem.relacyjnym nie występuje redundancja co zapewnia normalizacja.!!!

• w schem.sieciowym nie występuje redundancja co zapewnia normalizacja.

• w schem.hierarchicznym dla przedstawienia niektórych odwzorowań musimy pozostawić redundancję, co zakłóca integralność danych.

Aktualizacja i operowanie danymi :

• w modelu relacyjnym aktualizacja ogranicza się do operowania na krotkach, dodanie lub usunięcie inform. charakteryzowanej nast. nie poprzez wszystkie atrybuty lecz wiąże się z dodaniem lub usunięciem odpow. krotki relacji. Operowanie danymi tj. wyszukiwanie, wykorzystuje działania na zbiorach.

• w modelu sieciowym aktualizacja wymaga prawidłowej nawigacji, co pociąga za sobą znajomość powiązań między danymi, również operowanie danymi wymaga tej znajomości.

• w modelu hierarchicznym oprócz ograniczeń występujących w modelu sieciowym mamy przy aktual. dodatkowy problem, że rekord podrzędny możemy umieścić w strukturze dopiero w momencie, gdy mamy rekord nadrzędny, również przy usuwaniu. Usunięcie rekordu nadrzędnego powoduje utratę informacji zawartej w poddrzewie. Aktualizacja musi zapewniać integralność danych.

Projektowanie BD :

• w modelu relacyjnym projektowanie odbywa się o zasady normalizacji (CODA)

• w modelu sieciowym projektowanie odbywa się w zależności od żądanych przez użytkownika odpowiedzi-konstruowanie odpowiedzi na podstawie powiązań.

• w modelu hierarchicznym w powiązaniu z modelem sieciowym należy dodatkowo dbać o zapewnienie odwzorowań jednoznacznych (1 poprzednik - wielu następników) co utrudnia konstruowanie schematu i prowadzi do redundancji.

Niezależność danych :

Pełnej niezależności danych nie można osiągnąć w żadnym z w/w modeli, przy czym w relacyjnym modelu ze względu na elastyczną konstrukcję jest ona na wyższym poziomie. Ma też minimalną zajętość pamięci. Modele sieciowy i hierarchiczny ze względu na bardziej sztywną stukturę nakładają na programistę zastosowań większe ograniczenia.

Model relacyjny

Każda wartość w relacji , tj. każda wartość atrybutu w każdej krotce jest wartością atomową (wartością nierozkładalną) tzn. każdemu elementowi tablicy znajdującemu się na przecięciu dowolnego wiersza i dowolnej kolumny odpowiada pojedyńcza wartość nie zaś zbiór wartości. Relację spełniającą ten warunek nazywamy znormalizowaną.

Model relacyjny :

• reprezentowany przy pomocy tablic

• rekord = krotka; pole rekordu = atrybut w tej tablicy

• dziedzina - jest zbiorem wartości, z którego wybiera się aktualnie wartości występujące w danej kolumnie. Dziedzinę należy określić w schemacie pojęciowym i nadać jej odpowiednią nazwę.

• związki między krotkami (wierszami) są reprezentowane tylko przez wartości danych w kolumnach, pochodzących ze wspólnej dziedziny.

• zaleta : prostota reprezentacji

Subjęzyk - zbiór danych wykonywanych na danych zapisanych w postaci np. relacyjnej.

• jednolita reprezentacja danych w modelu relacyjnym prowadzi do unifikacji zbioru operatorów tzn. dla każdej podstawowej czynności (np.wprowadzanie,usunięcie itp.) można dlatego określić po jednym operatorze. W systemach sieciowych definiuje się np. 2 operatory dla wprowadznia danych : STORE i CONNECT.

Operacje :

Wprowad* - w obszarze roboczym W (obszar roboczy jest obszarem przyjmowania i transmisji danych przenoszonych pomiędzy użytkownikiem i b.d.)znajduje się informacja określająca nowy rekord / pole.

- wprowadż krotkę z obszaru W do odpowiedniej relacji

Usuń - usuń krotkę z odpowiedniej relacji

Aktualizuj - zmień krotkę odpowiedniej relacji wprowadzjąc odpowiednią wartość pola.

19. Tożsamość obiektów w modelu obiektowym.

Obiekt to pewien byt, encja charakteryzowana przez swój stan i zachowanie

20. Klasy i enkapsulacja.

Klasa to coś utożsamianego z pewną implementacją obiektu (charakterystyka i sposób wystąpienia obiektu) Klasa może być:

1. traktowana mniej więcej jako typ

2. interpretowana jako reprezentacja pewnej grupy obiektów

3. widziana jako obiekt

własności opisujące klasy obiektów to ATRYBUTY. Standardowy opis klasy składa się z:

• nazwy klasy

• atrybutów klasy

• opisu struktury statycznej obiektów należących do klasy

• opisu struktur dynamicznych w klasie

atrybuty klasy są to takie własności, które dotyczą wszystkich obiektów klasy: atrybuty wyliczalne i domyślne.

21. Struktura i działanie metod.

METODA

DEKLARACJA I TREŚĆ (BODY)

DEKLARACJA (SIGNATURE) - określa nazwę metody, nazwy i klasy argumentów i klasę rezultatów jeśli takie potrzeby są

CIAŁO METODY - określa treść metody i jest to ciąg instrukcji

WYWOŁANIE METODY - komunikat zawierający nazwę metody, określenie obiektu docelowego i argumenty metody, następuje podstawienie i wyliczenie metody.

22. zagadnienie dziedziczenia w modelu obiektowym

Dziedziczenie: 1) zstępujące, 2) zawierające, 3) związane, 4) specjalizowane.

Polimorfizm - te same metody maja inne znaczenie w różnych obiektach. Problemy podczas dziedziczenia: 1) nakładanie się więzów z obiektu z obiektu podczas dziedziczenia, 2) nakładanie się więzów podczas wystąpień obiektu w wielu klasach, 3) nakładanie się więzów na definiowanie podklas.

Zasada zachowania spójności powinna zapewniać: 1) spójność hierarchii dziedziczenia, 2) zasada rozróżnialności nazwy, 3) zasada pojedynczego pochodzenia, 4) zasada pełnego dziedziczenia. Dziedziczenie wielokrotne i redefiniowanie atrybutów obiektów w podklasach: 1) zasada pierwszeństwa podklas do nadklas, 2) zasada pierwszeństwa między nadklasami różnego pochodzenia, 3) zasada pierwszeństwa między nadklasami o tym samym pochodzeniu. Propagowanie zmian do podklas: 1) zasada propagacji i modyfikacji, 2) zasada propagacji zmian w przypadkach wystąpienia konfliktu, 3) zasada modyfikacji dziedzin. Agregacja i usuwanie zależności dziedziczenia: 1) wprowadzania nadklas, 2) zasada usuwania nadklas, 3) zasada wprowadzania klasy do schematu.

23. Problem wielowersyjności obiektów.

Ma na celu odwzorowanie poszczególnych cykli powstawania programu. W sensie historycznym oznacza, że po wykonaniu czegoś można wracać do poszczególnych wersji, każda z nich jakoś się zazębia. W sensie odmiany (np. Polonez osobowy, pick-up), każda wersja jest odmianą tego samego obiektu, nie ma zawierania się.

24. Obiekty wielotypowe.

25. Wpływ obiektów kompozytowych na strukturę bazy danych (typy wskazań).

Wskazania kompozycyjne:

1. zależne: jest wskazaniem na obiekt, który nie może istnieć samodzielnie, obiekt może być utworzony jedynie wtedy gdy istnieje obiekt złożony, którego jest komponentem. Usunięcie obiektu zależnego powoduje automatycznie usunięcie jego komponentów

2. niezależne: jest wskazaniem na obiekt, który może istnieć samodzielnie, jeżeli obiekt ten jest komponentem jakiegoś obiektu złożonego to usunięcie tego obiektu złożonego nie powoduje usunięcia obiektu-komponenta

3. wyłączne: jest wskazaniem unikalnym w bazie danych, obiekt wskazany w sposób wyłączny jest komponentem dokładnie jednego obiektu złożonego

4. współdzielone: jest wskazaniem wielokrotnym, obiekt wskazany w sposób współdzielony może być jednocześnie komponentem wielu obiektów złożonych

linia cienka - powiązanie współdzielone

linia przerywana - powiązanie słabe

linia ciągła - powiązanie kompozycyjne

linia gruba - powiązanie zależne

26. Reguły utrzymywania poprawności schematu bazy danych w strukturze obiektowej.

Nadzór nad modyfikacją bazy danych: (a,b,c - dotyczą wszystkich b.d, d,e,f - dotyczą obiektowej b.d)

1. zachowanie poprawności danych jednostkowych

2. zachowanie właściwych relacji pomiędzy atrybutami danej klasy

3. zachowanie spójności związków między różnymi obiektami należącymi do różnych klas

4. nakładanie więzów na przechodzenie obiektów z jednej klasy do drugiej

5. więzy nakładane na równoczesną przynależność obiektów do wielu klas

6. wizy nakładane na definiowanie podklas

mechanizmy zmian:

• statyczne: wszystko co związane ze schematem, zawartością treści

• dynamiczne: związane z implementacją, dotyczące metod

Niezmienniki schematu:

1. zasada zachowania poprawności hierarchii dziedziczenia: całą hierarchię można przedstawić w postaci grafu, każdy węzeł musi posiadać unikalną nazwę i być z czymś związany

2. zasada zachowania rozróżnialności nazw: atrybuty i metody klas muszą być rozróżnialne

3. zasada pojedynczego pochodzenia: klasa nie może posiadać 2 różnych atrybutów/metod pochodzących od tej samej klasy lub nadklasy

4. zasada pełnego dziedziczenia: dana klasa dziedziczy wszystkie atrybuty i metody jej nadklas z wyjątkiem tych, które powodowałyby konflikty w postaci naruszenia zasady rozróżnialności nazw i zasady pojedynczego pochodzenia

5. zasada zachowania poprawności dziedziny: jeśli atrybut A jest w klasie C i dziedziczy od A' klasy C' to dziedzina A musi być taka jak A' lub być poddziedziną A'. Nie może być większa

6. W bazie po zmianie schematu nie nastąpi utrata informacji.

W trakcie realizacji tych punktów mogą wystąpić konflikty:

• dziedziczenie wielokrotne lub rozwiązanie atrybutów

• zasada podklas w stosunku do nadklas: jeśli atrybut C zdefiniowano w pod i nadklasie to definicja z podklasy jest ważniejsza

• pierwszeństwa wobec nadklas równorzędnych: jeśli kilka nadklas ma mmetody/atrybuty z tą samą nazwą ale różnym pochodzeniem, wtedy dziedziczony jest atrybut z pierwszej nadklasy

27. Model relacyjno-obiektowy bazy danych.

Struktury danych definiowane są w postaci klas, natomiast pytania formułowane są za pomocą języka SQL (zamiast metod)

28. Etapy pracy zarządzania bazą danych (Delobel str. 24,25,26)

Oprogramowanie umożliwiające współpracę użytkownika z bazą danych jest nazywane systemem zarządzania bazą danych (SZBD). Zarządza on przede wszystkim organizacją danych w pamięci zewnętrznej oraz umożliwia wyszukiwanie i wybieranie danych. Posługując się językiem abstrakcyjnym, użytkownik określa operacje, jakie mają zostać wykonane na danych , następnie zaś SZBD realizuje wyszukiwanie danych, uwzględniając sposób ich reprezentacji i organizacji na nośnikach fizycznych. SZBD interpretuje instrukcje programu sformułowane przy użyciu pojęć z poziomu schematu zewnętrznego, przekształca je do postaci zgodnej ze schematem pojęciowym, a w końcu sprowadza do postaci rozkazów adresowanych do fizycznej BD. Rozkazy są przekazywane z poziomu zewnętrznego na poziom fizyczny, a wybieranie z bazy dane - z poziomu fizycznego na poziom zewnętrzny.

przepływ rozkazów przepływ danych

Etapy wykonania rozkazu (odczyt danej lub grupy danych)

1. żądanie odczytu jest przesłane do SZBD

2. SZBD analizuje to żądanie na podstawie schematu zewnętrznego po to, by sprawdzić, czy użytkownik, który zgłosił żądanie ma prawo dostępu do interesującej do danej, a także po to, aby pobrać informację o tej danej ze słownika danych związanego ze schematem zewnętrznym

3. SZBD bada schemat pojęciowy i na jego podstawie określa typ logiczny danej, która ma być odczytana

4. SZBD bada schemat wewnętrzny (fizyczny) i na jego podstawie określa rekord fizyczny do odczytania

5. SZBD wysyła do systemu operacyjnego rozkaz odczytu

6. system operacyjny odbiera instrukcję odczytu i analizuje ją, korzystając z niektórych parametrów schematu fizycznego, następnie zaś wysyła rozkaz odczytu do kontrolera urządzeń zewnętrznych zarządzającego dostępem do BD

7. pobrane z bazy dane są przesyłane do wyróżnionego obszaru pamięci, zwanego buforem systemowym

8. SZBD spośród zbioru danych znajdujących się w buforze systemowym wybiera te, które są potrzebne programowi użytkowemu. Dokonuje on następnie odpowiedniego przekształcenia, opierając się na definicji odwzorowania : schemat zewnętrzny - schemat pojęciowy, po czym przekazuje dane do bufora programu użytkowego

9. w przypadku wystąpienia błędu SZBD informuje program użytkowy a nienormalnym przebiegu operacji czytania, w wyniku tego program użytkowy może zareagować na błąd w określony sposób

10. program użytkowy dysponuje już daną o którą prosił, rozpoczyna się więc wykonanie następnej instrukcji programu.

Wykonanie rozkazu zapisu danej lub rozkazu aktualizacji przebiega zgodnie z takimi samymi zasadami, jak przedstawione powyżej wykonanie rozkazu odczytu.

Przeważnie mamy do czynienia z równoległym wykonaniem wielu programów użytkowych.

SZBD steruje ich wykonaniem, a zwłaszcza wykrywa przypadki równoczesnego zgłoszenia kilku żądań do tej samej danej.

29. OLTP i MIS

Systemy OLTP są to systemy wsadowe. Charakteryzują się szybkim przetwarzaniem i modyfikacją danych. Ważna jest integralność BD.

Systemy MIS są to systemy wspomagania - celem jest dokonanie pewnych manipulacji w BD w celu wyszukania informacji. Ważne jest efektywne wyszukiwanie danych i udostępnianie użytkownikowi.

30. Zarządzanie transakcjami.

Transakcja posiada pewne cechy, które muszą być spełnione.

Transakcje muszą być izolowane , co oznacza nierozróżnialność skutków ich wykonania niezależnie od tego , czy były wykonywane w tym samym czasie , czy też osobno ( np. pięciu kierowców stojących przy pięciu dystrybutorach opróżnia zbiornik tak samo , jak byłoby to w przypadku konieczności oczekiwania w kolejce do jednego dystrybutora).

Skutki wykonania transakcji powinny być nienaruszalne ( trwałe).

Transakcje muszą być operacjami ,,zero- jedynkowymi''wykonującymi się w całości albo nie wykonujące się wcale.

System obsługujący transakcje:

Menedżer transakcji za pośrednictwem protokołu 2PC nadzoruje wszystkie wykonane w bazie danych zmiany. Jego zadaniem jest zapewnienie poprawności przeprowadzania wszystkich transakcji.

Menadżer prezentacji (PM) oraz Klient mają za zadanie umożliwić użytkownikowi dostęp do zgromadzonych danych. Menedżer komunikacji(CM) umożliwia dostęp do innych DBMS ( systemy zarządzania bazami danych ). Pracę całego układu nadzoruje Monitor transakcji.

31. Współbieżność

Z danej BD korzysta wielu użytkowników. Ze względu na wydajność systemu jest ważne, aby kilka transakcji było wykorzystanych współbieżnie. System zarządzania BD musi więc sprawować kontrolę nad przebiegiem transakcji, nie dopuszczając do wzajemnej blokady poszczególnych transakcji lub do stanu niezgodnego BD. Każdy z programów użytkowych wykonuje operację odczytu, zapisując w odpowiednich obszarach pamięci operacyjnej wartości pobrane z BD. W przypadku operacji zapisu określona wartość z pamięci operacyjnej jest przepisywana do BD, w miejsce nieaktualnej wartości z BD. Sytuacje konfliktowe pojawiają się, kiedy dwie transakcje T₁ i T₂ aby dokonać operacji zapisu będą ... na tym samym obiekcie.

Konflikty powstają przy operacjach:

1. zapis-zapis -> utrata aktualizacji

Utrata aktualizacji wystąpi, gdy transakcja T₂ dokona zmiany wartości pewnej danej przed zakończeniem transakcji T₁, nie uwzględniając aktualizacji dokonanej przez T₁.

2. zapis-odczyt -> odczyt niewłaściwy

Sytuacja taka zdarza się, gdy transakcja T₂ odczytuje wartość zmienioną przez transakcję T₁, po czym transakcja zostaje anulowana z dowolnego powodu. Transakcja T₂ odczytała wartość niewłaściwą, niepotwierdzoną, wszystkie modyfikacje dokonane przez transakcje T₁ będą bowiem anulowane. Wcześniej jednak transakcja T₂ dokonała odczytu wartości A zmienionej przez T₁.

3. zapis-odczyt -> zapis niepowtarzalny

Jeśli między dwoma kolejnymi odczytami wartości A inna transakcja dokona zmiany tej wartości, w wyniku następujących po sobie odczytów transakcja T₂ uzyska dwie różne wartości A.

Rozwiązania problemów:

1. utrata aktualizacji nie wystąpi, gdy przestrzega się następującej reguły:

* transakcja T₁ nie powinna dokonywać zapisu wartości obiektu modyfikowanej przez inną transakcję T₂, która nie osiągnęła jeszcze punktu potwierdzenia.

2. utrata aktualizacji i niewłaściwy odczyt nie wystąpią, przestrzega się reguły z pkt 1 oraz reguły

* transakcja T nie powinna dokonywać odczytu wartości niepotwierdzonych, którymi w tym czasie manipulują inne transakcje

3. konflikty z a,b,c nie wystąpią, gdy przestrzegane są reguły z pkt 1 i 2 oraz

* żadna z transakcji nie powinna modyfikować wartości odczytywanej przez inną transakcję zanim ta ostatnia nie osiągnęła punktu potwierdzenia.

Metody:

1. wzajemne wykluczanie : przyznawanie prawa wyłączności do danego obiektu określonej transakcji. Każda z transakcji może uzyskać prawo wyłączności do danego obiektu, żądając blokady tego obiektu tzn. Jeśli dany obiekt jest zablokowany przez pewną transakcję to oznacza to, że żadna inna transakcja nie uzyska dostępu do tego obiektu do chwili odblokowania obiektu. Odblokowanie obiektu jest równoznaczne z utratą wyłączności dostępu do tego obiektu. Transakcje oczekujące na dostęp do zablokowanego obiektu można umieszczać w kolejce transakcji obsługiwanych zgodnie z kolejką zgłoszeń. Dzięki temu rozwiązaniu można uniknąć utraty aktualizacji, ale czasami prowadzi do zjawiska impasu.

1. impas - zjawisko powodowane dzieleniem danych zgodnie z zasadą wzajemnego wykluczania:

np.:

	T1	T2
t1	zablokuj (A)	-
t2	-	zablokuj (B)
t3	zablokuj (B)	-
t4	oczekiwanie	zablokuj (A)
t5	-	oczekiwanie
t6	-	-

Są dwie metody uniknięcia impasu:

1. zapobieganie powstawania impasów - kiedy żądanie przyznania blokady nie może być spełnione, system wykonuje pewien test dotyczący dwóch transakcji: tej, która żąda blokady (T_i) i tej która dysponuje blokadą w danej chwili (T_k). Jeżeli wynik testu jest pozytywny, zezwala się transakcji T_i oczekiwać na odblokowanie interesującego ją obiektu, w przeciwnym przypadku jedna z dwóch transakcji jest anulowana, jej wykonanie zostaje powtórne rozpoczęte. Transakcja taka nie jest usuwana z systemu zarządzania BD, lecz jest jedynie cofana ( anulowanie transakcji oznacza usunięcie zmian wprowadzonych przez nią bez usunięcia jej z systemu). Test: każdej transakcji przyporządkowuje się określony priorytet, wartość tę zapisujemy w postaci priorytetu (T_i). Transakcja T_i może oczekiwać na odwołanie blokady przez transakcję T_k wtedy i tylko wtedy gdy priorytet T_i < priorytetu T_k. Stosując tę metodę można spowodować, że pewna transakcja jest anulowana wielokrotnie, jej wykonanie system odkłada ciągle na później. Aby uniknąć tej sytuacji stosuje się metodę znaczników transakcji. W chwili pojawienia się danej transakcji przypisuje się jej pewien unikalny numer porządkowy - znacznik. Może to być np. wartość z zegara systemowego. Chodzi o to, aby transakcje wcześniejsze miały pierwszeństwo przed transakcjami późniejszymi. Wraz z metodą znaczników możemy stosować równocześnie technikę wywłaszczania lub technikę bez wywłaszczania:

*) bez wywłaszczenia: kiedy transakcja T_i żąda blokady obiektu zablokowanego przez T_k (T_i była

wcześniej), to T_i może czekać na odblokowanie obiektu, w przeciwnym przypadku T_i jest

anulowana (jej znacznik nie zmienia się)

*) wywłaszczenie: jeśli T_i jest późniejsza niż T_k , to oczekuje na odblokowanie obiektu, jeśli nie to

T_i jest anulowana.

2. wykrywanie powstałych impasów - dopuszcza się, by transakcje oczekiwały na odblokowanie interesujących je danych. Pewną transakcję anuluje się dopiero wtedy, gdy wystąpi impas. Przeważnie anuluje się transakcję, która wprowadziła .... .... lub tę, która rozpoczęła się najpóźniej. Zjawisko impasu występuje bardzo rzadko (1 na 1000 transakcji), dlatego bardziej ekonomiczne jest stosowanie wykrywania impasów.

3. Blokowanie dwufazowe - blokada wyłączności nie jest konieczna w przypadku kilku

równoczesnych operacji odczytu. Blokowanie dwufazowe jest wersją operacji blokowania

umożliwiającą synchronizację operacji odczytu i zapisu. W przypadku każdej transakcji, wszystkie

operacje żądania blokad powinny poprzedzać wszystkie operacje odwołania blokad. Wewnątrz

transakcji można wyróżnić fazę uzyskiwania i odwoływania blokad. Metoda ta nie wykrywa

pojawienia się impasu. Metoda ta opiera się na dwóch blokadach: dzielonej - umożliwiającej

równoczesny odczyt danych i blokady wyłączności

• zanim transakcja dokona odczytu wartości obiektu x, musi uzyskać blokadę dzieloną obiektu x

• zanim transakcja dokona zapisu wartości obiektu x, musi uzyskać blokadę wyłączności obiektu x

• po zakończeniu transakcji żaden z obiektów nie zostaje zablokowany

Transakcja dwufazowa:

1. faza rozwijania: transakcja żąda poszczególnych blokad, które są jej potrzebne, wykonuje pewne obliczenia, modyfikuje dane z bazy, po czym rozpoczyna się faza zwalniania

2. faza zwalniania: transakcja odwołuje poszczególne blokady

32. Technologia klient-serwer.

Zastosowanie architektury klient - serwer powinno się rozpatrzyć gdy nastąpi jakakolwiek kombinacja następujących sytuacji:

• Wiele osób zgłasza chęć dostępu do przetwarzanych danych

• Terminale są wykorzystywane po to aby ułatwić wymianę informacji między wieloma użytkownikami a centralnym komputerem

• Dostęp do danych musi być natychmiastowy , gdyż bardzo często warunkuje to poprawne wykonanie aplikacji

• Występuje konieczność swobodnego dostępu do ogólnej bazy danych , która może być bazą rozproszoną

• Występuje konieczność stworzenia centralnej bazy danych

• Występuje konieczność stworzenia mniejszej , lokalnej bazy danych , która będzie tworzona na bieżąco , lecz nie będzie to kopia centralnej bazy danych z ostatniej doby

• Użytkownicy tworzą własną bazę danych używaną przez nich i zadowalają się tylko utrzymaniem niezbędnej łączności z centralną bazą danych

• Przedsiębiorstwo rozwija się , stwarza to konieczność lepszego wykorzystania sprzętu komputerowego

System klient - serwer składa się z następujących zespołów:

• Stacji roboczej

• Sprzętu serwera

• Urządzeń służących do przekazywania danych

• Sprzętu sieciowego

Głównym założeniem systemu klient - serwer jest odseparowanie zadań prezentacji danych od ich przetwarzania. Role te są właśnie przydzielane klientowi i serwerowi . Klient formułuje zapytania do bazy danych ( najczęściej w języku SQL ) , serwer zaś zapytanie interpretuje znajduje właściwe dane i wysyła do klienta odpowiednie rekordy bazy. Podobnie rzecz się ma z wprowadzaniem nowych informacji. Z punktu widzenia programu klient- serwer nie jest więc przetwarzana cała baza , a tylko jej fragmenty. W idealnym przypadku program serwera zajmuje się wyłącznie obróbka danych , oraz za pomocą systemu kont kontrolą uprawnień użytkowników. Dzięki tej funkcji łatwo można dodać do systemu nowych użytkowników. Architektura klient - serwer nie sprawdza się gdy system zarządzania bazą danych obsługuje instytucje , które są rozproszone na dużym terenie.

Ulepszone systemy klient-serwer, jako niezależne od systemów baz danych, mogą być stosowane do zarządzania środowiskiem klient-serwer w najbardziej efektywny sposób. Ich możliwości można zwiększyć dzięki współpracy z serwerami baz danych. Systemy współpracujące z serwerami baz danych są naturalnym środowiskiem, w którym procesy aplikacyjne mogą być podzielone na programy typu klient oraz serwer. Programy typu serwer mogą być następnie przesyłane przez sieć. Oprogramowanie ulepszonych systemów klient-serwer wykonuje następujące zadania.

1. Zarządza dwufazowym zobowiązaniem między wieloma menadżerami zasobów,

2. Automatycznie wybiera drogę żądania usługi do właściwego serwera aplikacji,

3. Automatycznie rozkłada obciążenie między klika serwerów aplikacji, którym przydzielono wspólne zadanie,

4. Ponownie wybiera serwer w razie wystąpienia częściowej awarii systemu,

5. Automatycznie wznawia pracę serwerów po awarii,

6. Przenosi serwery i/lub grupy serwerów na platformy zastępcze w razie awarii części sytemu.

Wszystkie te możliwości są dostępne w sposób administracyjny podczas pracy systemu i w żaden sposób nie wpływają na programowanie aplikacji. Ulepszona technologia klient-serwer pozwala na takie programowanie i sterowanie techniką projektowania systemu, które w sposób bardzo znaczący zmniejsza obciążenie sieci oraz koszty przesyłania danych z jednego serwera na drugi. Technologia ta pozwala także na całkowitą rekonfigurację sieci.

Prawie wszystkie systemy klient-serwer są oparte na architekturze serwerów baz danych. W serwerach baz danych zastosowano architekturę żądania danych, dającą prawo żądania usługi od serwera. Serwery tego typu mogą jedynie odpowiadać na pytanie, nie mogą zainicjować interakcji z klientem. Usługa, jakiej żąda klient od serwera, może polegać na zleceniu wykonaniu usług przez inne serwery. Wówczas ta pierwsza usługa jest klientem żądającym dalszych usług. Baza danych ma interfejs zdalnie dostępnej bazy danych między programem aplikacyjnym a siecią. Interfejs formatuje żądania dostępu do bazy danych tak, aby mogły one być przesłane w sieci. Po sformatowaniu, żądanie jest przesyłane do interfejsu sieciowego, który umieszcza je w sieci. W serwerze interfejs sieciowy rozpoznaje komunikat i wysyła go do serwera baz danych, który wykonuje żądane działania oraz przesyła aplikacji rezultat za pomocą sieci i interfejsu zdalnie dostępnej bazy danych.

33. SYSTEMY ROZPROSZONE.

1) Definicja zależności - serwer wydaje polecenia dla innych użytkowników, 2) Replikacja: a) synchroniczna - serwer blokuje dostęp do danych do momentu zakończenia transakcji - duży stopień bezpieczeństwa, b) asynchroniczna - serwer nie blokuje zasobów na czas transakcji, 3) Współdziałanie wieloplatformowe, 4) monitorowanie systemu. W wielodostępie istnieje problem rozproszenia danych....

System Offera????: 1) Analiza potrzeb i zainteresowań użytkownika: a) języki żądań użytkownika, b) częstość żądań kierowanych od użytkownika.

Rozproszenie stosuje się po to, by średni koszt uzyskania odpowiedzi był niższy od kosztu bez rozproszenia. Koszt uzyskania odpowiedzi jest bardzo zależny od czasu reakcji na odpowiedź. Wiąże się to również z redundancją, która musi być redukowana. Rozproszenie stosuje się wg jakiegoś klucza. Potrzebne jest również narzędzie do porównania systemu rozproszonego. Na to kryterium składają się: 1) U₁,...,U_k - użytkownicy 2) L₁,L₂,...,L_k - języki, 3) S=<X,A,V,ρ> - system. Patrząc na zbiór języków L zbiór A można podzielić logicznie na B₁,B₂,...,B_n takich, że B_jA. Uzyskujemy w ten sposób system rozproszony S_D = {S₁,S₂,...,S_K} o atrybutach A = {A₁,A₂,...,A_K}; A_jA. Użytkownicy posługują się tu jednym językiem i wtedy np. dwóch użytkowników traktuje się jako jednego użytkownika ze zdwojoną częstością dostępu do danych.

Wskaźnikiem dekompozycji systemu rozproszonego jest średni czas odpowiedzi w systemie rozproszonym do czasu odpowiedzi w systemie nierozproszonym: dla rozproszonego:
, dla systemu nierozproszonego:
,

a więc współczynnik czasu odpowiedzi:
; gdzie: p_i - częstotliwość pytań i -tego użytkownika, t_p - czas przetwarzania bloków, t_w - czas przetwarzania zależny od specyfikacji danego systemu.  - zbiór częstotliwości p_i. Współczynnik zajętości pamięci:
. Współczynnik jakości rozproszenia: (S_D,L_n,) = c₁*γ(S_D,L_n,) + c₂*(S_D); gdzie: 0c₁,c₂1 oraz c₁+c₂=1; c₁,c₂ - współczynniki wagowe, do sterowania typem podziału systemu.

34. SYSTEMY ROZPROSZONE - ALGORYTM DEKOMPOZYCJI.

1. Utworzenie zbioru A' = A-A_g a-priori;

2. Utworzenie aktualnego zbioru E par postaci E: e=(a,
   (a)) dla aA';

3. Wybranie elementu max: max e; eE;

4. Ustalenie atrybutów podobnych do atrybutu a, występujących w A, na podstawie M.(a,b);

5. Utworzenie nowego zbioru E poprzez wyeliminowanie par utworzonych w kroku 4;

6. Jeżeli nowy zbiór E  { powrót do 3.

35. ZASADY PROJEKTOWANIA ZABEZPIECZEŃ (łączność danych)

Mamy trzy kryteria zabezpieczeń:

1. bezpieczeństwo danych - zabezpieczenie danych przed umyślnym bądź przypadkowym zniszczeniem, kradzieżą lub modyfikacją

2. tajność danych - udostępnienie danych osobie, która ma odpowiednie upoważnienie do tej informacji

3. poufność danych - możliwość wymiany danych tzn. komuś dać te dane a innemu inne, czyli kontrola nad tym kto i z czego korzysta

Jest kilka ważnych zasad bezpieczeństwa, które powinne być przestrzegane przy projektowaniu systemów komputerowych:

1. domniemywana odmowa udzielania dostępu - jeżeli sytuacją domniemywaną jest brak dostępu można zmusić użytkownika do uzasadnienia potrzeby uzyskania dostępu przed udzieleniem mu go, błędy w projekcie i we wdrożeniu powodują odmowę udzielenia dostępu, co zapewnia sytuację bezpieczną

2. jawny projekt - ukazanie słabych stron projektu jeszcze w toku planowania ułatwi zdolnym krytykom wprowadzenie poprawek przed wdrożeniem go, za nim inne systemy zaczną polegać na jego działaniu; jeżeli projekt jest dobry, można go w całości opublikować, poza parametrami uzbrajającymi

3. akceptowalność - system zabezpieczeń musi być akceptowany przez użytkowników, gdyż w przeciwnym razie znajdą się sposoby na to, aby go obejść

4. całkowite pośredniczenie - upoważnienie musi być sprawdzane przy każdym żądaniu uzyskania dostępu do każdego obiektu. Zasada ta wymaga, by w razie ewentualnej zmiany poziomu upoważnienia nie mogły być wykorzystane zapamiętane wyniki badania upoważnień, lecz by trzeba było ponownie takie badanie przeprowadzić

5. najmniejsze uprzywilejowanie - każdy użytkownik, program, terminal lub inny zasób powinien korzystać tylko z tych przywilejów (fragmentów), które są niezbędne do wykonania zadania

6. ekonomiczność mechanizmu - projekt powinien być tak prosty i mały jak to tylko możliwe

7. oddzielenie przywilejów - dwa oddzielne zamki stanowią znacznie lepszą i elastyczniejszą ochronę niż jeden. Kiedy mechanizm jest zamknięty, dwa klucze do niego mogą być fizycznie oddzielone i oddane pod opiekę różnym programom, organizacją lub ludziom

8. najmniejszy wspólny mechanizm - każdy wspólny mechanizm reprezentuje potencjalną ścieżkę przepływu informacji między użytkownikami, a więc wielo dostępność powinna być minimalizowana

Trzymanie się tych zasad zredukuje liczbę i wagę błędów występujących w systemach komputerowych

36. Techniczne środki bezpieczeństwa baz danych.

Fizyczne metody uwierzytelniania - inne metody uwierzytelniania niż programowe sprawdzają czy użytkownik posiada jakiś przedmiot lub czy charakteryzuje się jakąś cechą fizyczną np. odciski palców, siatkówka oka, brzmienie głosu, karty magnetyczne, zamki z kluczami itp.

37.SZACOWANIE DŁUGOŚCI HASŁA.

Szacowanie długości hasła i jego dobór oraz czas bezpiecznego używania.

Hasło nie może być za proste ani za trudne. Powinno nie nastręczać trudności użytkownikowi. Im dłuższe hasło tym bezpieczniejszy system, ponieważ wraz z wydłużaniem się hasła rośnie wysiłek potrzebny na to by je złamać. Można tu rozumować w kategoriach przewidywalnego czasu potrzebnego na złamanie hasła, inaczej: przewidywanego czasu bezpiecznego czasu. Jest to połowa iloczynu liczby możliwych haseł i czasu potrzebnego na wypróbowanie każdego z nich.

R-prędkość przesyłania linii komunikacyjnej (z znakach na sekundę)

E-liczba znaków wymienianych przy próbie włączenia się do systemu

S-długość hasła „i”

A-wielkość alfabetu, z którego tworzone jest hasło „i”

P-pożądane prawdopodobieństwo znalezienia przez intruza hasła „i”

M-czas dokonywania systematycznych prób w miesiącach całodobowego

działania

P ma kres dolny P₀ gdzie:

P₀=

N₁ =

N₁ =

N₂ = A^S

P₀ =

, ponieważ P
P₀

P

co zapisane inaczej stanowi wzór ANDERSONA:

4,32*10⁴ *
A^S

Jeżeli wartości R, E, M, A będą stałe, to każda wartość S daje inne prawdopodobieństwo P odgadnięcia hasła. Gdy chcemy stworzyć system, w którym intruz może odgadnąć hasło z prawdopodobieństwem nie większym niż P, musimy wybrać takie S spełniające nierówność ze wzoru Andersona.

38. Metody uwierzytelniania za pomocą haseł.

Identyfikator to niepowtarzalna nazwa lub numer nadany obiektowi. Uwierzytelnianie to sprawdzenie, czy osoba lub obiekt jest tym, za kogo się podaje; procedura upoważniania bada, czy osoba ta lub obiekt ma prawo do chronionego zasobu. Wszystko to jest brane pod uwagę w celu podjęcia decyzji o udzieleniu dostępu. Identyfikator podaje tylko niepotwierdzoną tożsamość. Numery identyfikacyjne powinny w miarę możliwości używać cyfr kontrolnych lub stosować inne metody samokontroli, by zminimalizować szansę błędnej identyfikacji. Identyfikatory są niezbędne dla rozliczeń i upoważniania, ale nie mogą być używane bez dodatkowego uwierzytelniania, jeśli jest potrzebny w systemie stopień bezpieczeństwa. Uwierzytelnienie zwykle jest dokonywane jednorazowo, ale w instalacjach o dużym stopniu bezpieczeństwa może być wymagana okresowa lub stała weryfikacja. Dla uwierzytelniania tożsamości użytkowników komputery używają haseł lub innych metod dialogowych. Z punktu widzenia użytkownika znacznie ważniejsze są czynniki takie jak: liczba znaków do wprowadzenia, wysiłek umysłowy i sposób postępowania w wypadku popełnienia błędu przy wpisywaniu.

Hasło to ciąg znaków wprowadzonych przez użytkownika i sprawdzanych przez komputer. Hasła mogą być wykorzystywane niezależnie od użytkownika dla ochrony zbiorów, rekordów, pól w rekordach itp.

Metoda prostych haseł - użytkownik wprowadza hasło, które może sam wybrać.

Wariacje metody prostych haseł - pewne wariacje metody prostych haseł zapewniają lepsze bezpieczeństwo za cenę bardzie skomplikowanego oprogramowania i zwiększonej trudności dla użytkownika.

Wybrane znaki - komputer może zażądać od użytkownika wchodzącego do systemu podania pewnych znaków. Numery znaków mogą być naliczane np. na podstawie zegara wewnętrznego komputera.

Hasła jednorazowe - użytkownik ma listę n-haseł i komputer je pamięta. Trzeba podać hasła w odpowiedniej kolejności. Hasła podaje się także na zakończenie sesji i uwierzytelniania terminali.

Wady haseł: użytkownik musi pamiętać listę haseł i znać aktualne. W przypadku błędu nie wiemy czy mamy wpisać to samo hasło czy nowe.

Ogólne ostrzeżenia dotyczące haseł i ich używania:

• Hasła nie powinny nigdy być przechowywane w jawnej postaci;

• Hasła nie powinny być drukowane na drukarkach;

• Powinny być często zmieniane;

• Użytkownikowi nie wolno podawać nowego hasła po zakończeniu sesji;

39. Uwierzytelnianie oparte nie na metodach haseł.

Identyfikator to niepowtarzalna nazwa lub numer nadany obiektowi. Uwierzytelnianie to sprawdzenie, czy osoba lub obiekt jest tym, za kogo się podaje; procedura upoważniania bada, czy osoba ta lub obiekt ma prawo do chronionego zasobu. Wszystko to jest brane pod uwagę w celu podjęcia decyzji o udzieleniu dostępu. Identyfikator podaje tylko niepotwierdzoną tożsamość. Numery identyfikacyjne powinny w miarę możliwości używać cyfr kontrolnych lub stosować inne metody samokontroli, by zminimalizować szansę błędnej identyfikacji. Identyfikatory są niezbędne dla rozliczeń i upoważniania, ale nie mogą być używane bez dodatkowego uwierzytelniania, jeśli jest potrzebny w systemie stopień bezpieczeństwa. Uwierzytelnienie zwykle jest dokonywane jednorazowo, ale w instalacjach o dużym stopniu bezpieczeństwa może być wymagana okresowa lub stała weryfikacja. Dla uwierzytelniania tożsamości użytkowników komputery używają haseł lub innych metod dialogowych. Z punktu widzenia użytkownika znacznie ważniejsze są czynniki takie jak: liczba znaków do wprowadzenia, wysiłek umysłowy i sposób postępowania w wypadku popełnienia błędu przy wpisywaniu.

Metoda pytań i odpowiedzi - system otrzymuje zbiór odpowiedzi na m.-standardowych i n-dostarczonych przez użytkownika pytań. System przy każdej próbie rozpoczęcia sesji przez użytkownika zadaje z pośród tych pytań niektóre (wybrane przypadkowo). Trzeba na nie wszystkie poprawnie odpowiedzieć. Pytania dobiera się tak, by użytkownik tylko znał odpowiedzi a nie musiał je zapisywać.

Uwierzytelnianie tożsamości systemów - hasła mogą być stosowane także do uwierzytelniania tożsamości systemów np. w sieciach. Do uwierzytelniania systemów można wykorzystywać szyfry. Użytkownik po podaniu hasła trochę czeka, gdyż terminal podaje swoje dane identyfikujące do jednostki centralnej systemu.

Procedura uwierzytelniania - system może żądać od użytkownika uwierzytelniania w postaci poprawnego wykonania jakiegoś algorytmu. Nazywane jest to często procedurą przywitania - mają wyższy stopień bezpieczeństwa, ale są bardziej czasochłonne i żmudne.

Procedury użytkownika - niektóre systemy dopuszczają wykonanie dostarczonych przez użytkownika procedur przed wejściem do systemu. Zaraz po przesłaniu pierwszego wiersza z terminalu system przekazuje sterowanie tej procedurze. Po zakończeniu tej procedury system wywołuje własną kontrolę bezpieczeństwa.

Fizyczne metody uwierzytelniania - inne metody uwierzytelniania niż programowe sprawdzają czy użytkownik posiada jakiś przedmiot lub czy charakteryzuje się jakąś cechą fizyczną np. odciski palców, karty magnetyczne, zamki z kluczami itp.

Działania w wyniku odmowy udzielenia dostępu - dziennik systemu i zwłoka czasowa przy źle wprowadzonej odpowiedzi, oraz ilość prób wejścia do systemu.

40. UWIERZYTELNIANIE W SYSTEMIE UNIX

W systemie UNIX istnieją 4 kategorie ochrony zasobów:

	Poziom bezpieczeństwa
Hasła	niski	tradycyjny	Podwyższony	Wysoki
Minimalna liczba dni między zmianą hasła	0	0	0	14
Okres stosowania			42	42
Okres życia			365	90
Czy użytkownik może wybrać własne			TAK	TAK
Max długość hasła			10	10
Min długość hasła			5	8
Sprawdzanie jakości hasła			TAK	TAK
Czy hasło jest wymagane w trybie pracy pojedynczej				

41. SPOSOBY BADANIA UPOWAŻNIEŃ

Po uwierzytelnianiu tożsamości za pomocą którejś z metod z pytania 23 można sprawdzić czy użytkownik, terminal lub inny zasób jest upoważniony do otrzymania przezeń obsługi. Jeżeli żądana operacja jest dozwolona, mówimy, że żądający ma upoważnienie na dostęp do niej. Dana może być, zbiorem, rekordem, polem, relacją lub jakąś inną strukturą. Udzielenie dostępu może zależeć od kilku czynników:

-przywilejów dostępu posiadanych przez użytkownika

-przywilejów dostępu posiadanych przez terminal

-żądane operacji

-danej

-wartości danej,

-od innego czynnika np. czasu.

System bezpieczeństwa otrzymuje zestawy informacji związane z każdym użytkownikiem, terminalem, procedurą lub innym zasobem mającym dostęp do danych. Te zestawy informacji tworzone są przez specjalny, uprzywilejowany program. Mogą one być zazwyczaj reprezentowane przez macierz upoważnień. Zależnie od wagi chronionych danych można:

-odczekać trochę przed utworzeniem i zmianą zestawu informacji

-powstrzymać się od utworzenia zmiany i zmiany do chwili, gdy jeszcze jeden

upoważniony użytkownik spróbuje wprowadzić takie same zmiany.

-odłożyć utworzenie i zmianę do chwili otrzymania sygnału od określonego

użytkownika

Macierz upoważnień - każdy element A_ij macierzy upoważnień określa prawa dostępu i-tego zasobu do j-tego zasobu. Przywileje:

00-brak przywilejów

01-przywilej czytania

10-przywilej pisania

11-przywilej czytania i pisania

Elementy macierzy dostępu zawierają zwykle bity, które reprezentują operacje, jakie terminal wykonać na danej. Można też zastosować metodę pośrednią, która wymaga więcej pamięci, ale mniej czasu procesora niż w przypadku procedur wywoływanych przy każdej próbie uzyskania dostępu. Wymaga ona zapamiętania hasła zamiast każdego bitu przywileju. Hasło jest porównywalne z hasłem podawanym wraz z żądaniem udzielenia dostępu. Macierz upoważnień jest sercem systemu ochrony i jest przechowywana oddzielnie jako zaszyfrowany zbiór, a jej wiersze są wprowadzane do pamięci operacyjnej w miarę potrzeby.

dane

użytkownik

	X1	X2	..
U1	01	10
U2	00	11
..

Wiersze mogą reprezentować użytkowników lub grupy użytkowników mogą też one odpowiadać programom lub podsystemom, którym potrzebny jest dostęp do danych, kolumny zaś mogą być typami żądań.

Zmniejszanie macierzy upoważnień - liczba kolumn i wierszy może być bardzo duża. Macierz można zmniejszyć za pomocą kilku metod:

1. zdefiniowanie grup „wirtualnych” użytkowników, z których każda reprezentuje grupę użytkowników mających identyczne upoważnienia;

2. zdefiniowanie grup „wirtualnych” terminali - podzielenie na klasy;

3. zgrupowanie elementów danych w pewną liczbę kategorii ;

4. przechowywanie listy par (element danej, pozwolenie) dla każdego terminala lub użytkownika;

5. przechowywanie listy par (użytkownik, terminal, pozwolenie) dla każdego elementu danej.

W macierzy upoważnień mogą być odsyłacze (wskaźniki) odsyłające do procedur lub funkcji zajmujących się dostępem do danych. Macierz nie może być statyczna i hermetycznie zamknięta, ponieważ upoważnienia się zmieniają. Przy projektowaniu macierzy upoważnień należy tak postąpić aby zmiany macierzy były dokonywane tylko przez administratora. Jeżeli (wymóg społeczny) kilku użytkowników chce dostać się do potrzebnej danej żeby móc dalej pracować, należy im udostępnić dane przez odpowiednie upoważnienia (priorytety).

42.POZIOMY UPOWAŻNIEŃ.

Udzielenie upoważnienia może być zależne od kategorii zasobów, użytkowników, terminali, danych i operacji, ale także od poziomu upoważnienia związanego z tymi zasobami. Odmowa udzielenia dostępu następuje zawsze, gdy poziom upoważnienia terminala i użytkownika jest niższy niż poziom upoważnienia żądanej operacji lub danych. Mamy trzy kolejne poziomy uprzywilejowania (upoważnień): poufne, tajne, ściśle tajne. Gdy terminal ma dostęp do tajnych danych, a użytkownik do ściśle tajnych to może on tylko z tego terminala uzyskać dane tylko tajne, gdyż taki poziom upoważnień ma terminal. W ten sam sposób można łączyć przywilej programu i użytkownika, po to by system dopuszczał do korzystania z możliwie najmniejszego. Tak kombinowana metoda, pozwala na jednoczesną hierarchiczną ochronę danych i na ochronę ich za pomocą jednoznacznie określonych rozłącznych kategorii. Zgodnie z zasadą „domniemywana odmowa udzielenia dostępu” za domniemywanym uprawnieniem związanym z każdym zasobem powiniwń być „zakaz dostępu”. Dostęp może być kontrolowany także na poziomie wyższym niż poziom zbioru - metoda hierarchicznej kontroli.

43. SZYFROWANIE - METODY KLASYCZNE (TRADYCYJNE)

Do szyfrowania metodami klasycznymi zaliczamy szyfry i kody tradycyjne. Różnica pomiędzy kodowaniem, a szyfrowaniem jest płynna i nie ma bezpośredniej granicy pomiędzy nimi. Do tradycyjnych metod szyfrowania zaliczamy: szyfry podstawieniowe i przestawieniowe np. szyfr Cezara oraz szyfry monoalfabetyczne i polialfabetyczne. Kryptografia pozwala znakomicie podnieść bezpieczeństwo komunikacji w sieciach i bezpieczeństwo danych w urządzeniach wymiennych pamięci zewnętrznych. Szyfrowanie jest kodowaniem danych dla ukrycia informacji. Szyfry przekształcają tekst otwarty, działają na tekście otwartym zmiennej długości. Kody działają na jednostkach lingwistycznych.

Szyfry przestawieniowe:

a) kolumnowy: dla każdej litery klucza ustalamy wagę a następnie zapisujemy pod kluczem tekst otwarty, do momentu wystąpienia litery o wadze w porządku rosnącym, np.:

P	O	L	A	K
5	4	3	1	2
p	o	c	a
ł	u	j	m	n
i	e	w
o	k
o

a następnie spisujemy kolumny, zgodnie z wagami: amncjwouekpłioo.

b) Przekątniowo - kolumnowy: dla każdej litery klucza ustalamy wagę a następnie zapisujemy pod kluczem tekst otwarty, np.:

P	O	L	A	K
5	4	3	1	2
P	o	c	a	ł
U	j	m	n	i
E	w	c	z	o
Ł	o	x	x	x

a następnie spisujemy po przekątnych, zgodnie z wagami: amwłłncocjexouoxpizx.

c) Permutacyjny: dzielimy tekst otwarty na części zgodnie z długością klucza, a następnie zamieniamy litery w grupach zgodnie z kolejnością cyfr w kluczu, np.: k=(4213), tekst otw. = ala ma dużą piłkę;  _laadam__żuąkipł_ęk_.

Szyfry podstawieniowe:

a) monoalfabetyczne: każdy symbol alfabetu jawnego jest zastępowany jednym znakiem z alfabetu tajnego. Ogólny wzór na podstawienie : f(a)=(a*p + k) mod n ,gdzie a-czynnik dziesiątkowania, k- czynnik przesunięcia, n- ilość znaków alfabetu, p -nr litery w alfabecie. Przykład wg Czaplowej: alfabet jawny: ABCDEFGHIJKLMNOP.... i alfabet tajny: DELOBACFGHIJK.... (klucz: DELOBEL); chcemy zaszyfrować: EGZAMIN  BC_DKGL.

Szyfr CEZARA: szczególny przypadek szyfru podstawienia monoalfabetycznego. Każdą literę szyfruje się za pomocą funkcji f(a)=(a+k) mod n.

Alfabety PRZERZEDZONE: f(a)=(a*k) mod n; przekształcenie AFINICZNE: f(a)=(ak₁+k₀) mod n; przekształcenie wielomianowe: f(a)=(a­^tk_t+a ^t-1k_t-1+...+a¹k₁+k₀) mod n.

b) polialfabetyczne: występuje wiele alfabetów, tzn. istnieje klucz, którego długość >= 2, i pod każdy znak tekstu otwartego podstawia się odpowiedni znak z alfabetu tajnego, wg wzoru f(a)=( a_j + a_t) mod n, gdzie a_j - litera alfabetu jawnego, a_t - litera alfabetu tajnego, np.:

m	o	j	a	m	o	w	a	J	e	s	t
P.	O	U	F	N	E	P	O	U	F	N	E
b	c	d	g		t	l	p	D	k	f	y

c) homofoniczne są to polialfabetyczne szyfry podstawieniowe, w których jednemu znakowi alfabetu jawnego odpowiada wiele znaków alfabetu tajnego, w zależności od częstości występowania liter w alfabecie. Nie można go złamać za pomocą analizy częstości!!!

d) Wiżenera: stosuje się tu klucz i tablicę (w kolumnach - alfabet jawny, w wierszach - znaki klucza):

	A	B	C	D	E	F
A	a	b	c	d	e	f
B	b	c	d	e	f	g
C	c	d	e	f	g	h
D	d	e	f	g	h	i
E	e	f	g	h	i	j
F	f	g	h	i	j	k

Szyfry złożone: wiadomo o co chodzi.

Łamanie szyfru:

1. Rzetelna ocena częstości występowania znaków w alfabecie

2. Analiza częstości: współczynnik koincydencji

f_i - lb wystąpień i-tej litery w tekscie zaszyfr.

N- lb liter tekstu zaszyfrowanego.

Szyfry ,dla których IC przekracza 0,066 dla angielskiego są podstawieniami monoalfabetycznymi. Gdy 0,052<=IC<=0,066 to 2 alfabetyczne podstawienie. Analiza częstości jest liczbowym przedstawieniem występowania danej litery w tekście danego języka .

3. Dalsza analiza tekstu (analiza blokowa).

Metoda deszyfracji Kasińskiego:

1. Wyznaczenie ciągu znaków powtarzających się i obliczenie odległości wystąpień. Powtórzenia występują wówczas, gdy fragment tekstu jawnego powtarza się w równej wielokrotności długości kluza. Okresem szyfru jest liczba będąca podzielnikiem większości wystąpień tych odstępów.

2. Wyznaczanie wskaźnika koincydencji w celu potwierdzenia wcześniejszych obliczeń. Następnie rozbijamy tekst na grupy o długości okresu i liczymy wskaźnik koincydencji dla każdej grupy. Wskaźnik ten powinien być bliski 0,066.

44. SZYFROWANIE - METODY PROGRAMOWE

Generatory liczb pseudolosowych - Liczby pseudolosowe są odtwarzalne, a losowe nie np. można zacząć od czterocyfrowej liczby początkowej T_i i otrzymać następną liczbę pseudolosową T_i+1 przez podniesienie do kwadratu dwóch środkowych cyfr T_i . Stworzone generatory oparte na podstawach matematycznych. Najbardziej popularne to generatory kongruencyjne, dzięki nim można podawać matematycznie poprawne stwierdzenia o rodzaju liczb wyjściowych tych generatorów w sensie długości okresów i stopnia losowości. Jednym z generatorów kongruencyjnych jest generator liniowy, który pokazuje ciąg liczb pseudolosowych T₁ ,T₂ ,...,T_n za pomocą wzoru: T_i+1=(aT_i+c) mod m, gdzie a,c to stałe, T₀ jest wart. początkową. Zwykle m = 2^b, gdzie b - długość słowa komputera w bitach.

Generator liczb pseudolosowych mają zastosowanie w szyfrowaniu zbiorów sekwencyjnych i przesyłanych komunikatów. Anderson opracował metodę szyfrowania zbiorów o dostępie swobodnym, w którym są generowane dwie tablice z hasła, bądź nazwy użytkownika, każda o długości pierwiastka kwadratowego z długości zbioru wyrażona w rekordach. Tablice te zawierają wartości T₀ i c. Adres logiczny rekordu lub jego numer jest przekształcany w dwie liczby, które wybierają spośród tych wartości niepowtarzalne T₀ i c dla każdego rekordu, co zapewnia niepowtarzalny ciąg kluczy dla wszystkich rekordów. Można odczytać dane z jednego rekordu, ale nie ze wszystkich, ponieważ zostały zaszyfrowane innymi ciągami kluczy. Szyfrowanie i rozszyfrowanie przebiega dla każdego rekordu tak samo jak dla zbiorów sekwencyjnych. Wybranie wartości początkowej T₀ zależy od programisty szyfrującego. W gener. po max okresie m ciąg się powtarza i zależy od m i jest max gdy : m=2^k gdzie k>2 i całkowite oraz c - nieparzyste, a mod 4=1.

Szyfr z nieskończonym kluczem - bezpieczeństwo szyfru wzrasta wraz z długością hasła . Można użyć do tego dwu stopniowy gener liniowy kongruencyjny. 1) Tworzymy ciąg S₀,S₁,S₂,...,S_L używając znanego wzoru dla GLP liniowego począwszy od liczby początkowej S₀, gdzie L ma wartość sześciu ostatnich bitów z S₀ zwiększonych o 16. 2) Następnie obliczamy klucz T₁,T₂,... w następujący sposób: ustalamy K=12 lub K=18 odpowiednio dla średniego lub wyższego zabezpieczenia; następnie definiujemy N=2^K+K mniej znaczący bitów z S_L. Ustalamy klucz T₁,T₂,...,T_N : T_J = S_J dla J=1,2,...,L, T_J = (T_J-1 + T_J-1-L) mod m., dla L<J=<N. Następnie generujemy nowy ciąg początkowy: S_N = S_L; S_N+1 = (aS_N + c) mod m.;...;S_N+L = (aS_N+L-1+c) mod m. Ustalamy klucz: T₁,T₂,...,T_N : T_J = S_J dla J=N+1,N+ 2,...,N+L, T_J = (T_J-1 + T_J-1-L) mod m., dla N+L<J=<2N.

Szyfr o „nieskończonym” kluczu: Frendberg połączy polialfabetowe podstawienie z generatorem liczb pseudolosowych, dający szyfr podstawieniowy o cechach „nieskończonego” klucza. A oto jego metoda: 1) Ustawienie GLP z daną liczbą początkową. Ustalenie listy podstawień. 2) Czy są jakieś znaki tekstu otwartego? Jeśli nie - to koniec. 3) Znajdź następny znak w miejscu a w alfabecie tekstu otwartego i zamień go na odpowiedni znak z listy podstawień. 4) Wygeneruj liczbę pseudolosową R z przedziału 1 do n. 5) Zamień miejscami znaki R i a w liście podstawień. Idź do 2).

Zalety : niemożliwość rozszyfrowania za pomocą analizy częstotliwości. 6000 spacji daje tekst o równomiernym rozkładzie różnych liter.

Metody kompresji - oszczędzają pamięć, ale mają bardzo niski poziom bezpieczeństwa - kodowanie Huffmana. Dla zaoszczędzenia miejsca zajmowanego przez ciąg znaków można najczęściej używanym znakom przypisać krótkie kody.

Koszt szyfrowania programowego: współczynnik czasu szyfrowania - stosunek czasu potrzebny na ściągnięcie danych, zaszyfrowanie ich i ponowne przesłanie do pamięci, do czasu potrzebnego na ściągnięcie danych i przesłanie ich do pamięci bez żadnej modyfikacji. Różne komputery szyfrują tekst z różną szybkością dla tej samej metody.

Przykład: dla met tradycyjnej

szyfr: sz - to dwie osobne litery s i z . Bazuje na syntaktyce znaku ( budowa )

kod : sz - jest pojedynczym znakiem . Bazuje na semantyce znaku ( znaczenie )

Metoda RSA należy do metod wykładniczych. Algorytm: Na wejściu przyjmuje się dwie losowo wybrane duże liczby pierwsze p i q. Mnożymy je przez siebie n=p*q. Obliczamy funkcję Eulera od n (n). Wybieramy liczbę e losową między 1 do (n) ;e=<1, (n)>. Liczba e musi być względnie pierwszą z (n). Znajdujemy liczę odwrotna do e : d=e^-1 mod (n). Szyfrowanie: f(P)=P^e mod n. Deszyfrowanie: f ^-1(C)=C^d mod n. Uwagi: 1) p i q - co najmniej 100 - cyfrowe i nie mogą być blisko siebie. 2) (n) = n+1-p-q. 3) Klucz szyfrujący: K_e=(n,e), Klucz deszyfrujący: K_d=(n,d).

Przykład: Szyfruj słowo „YES”:

1. 24*26²+4*26¹+18*26⁰ = 16346 = P

2. f(P) = 16346³⁹⁴²³ mod 46927 = 21166

3. 21166 = 1*26³ + 5*26² + 8*26¹ + 2*26⁰ = „BFIC”

Metoda Maklego - Hermana: Bazuje na problemie „upakowanego plecaka”: istnieje zbiór I=(i₁,i₂,...,i_n): i_j  C oraz liczba b; Udowodnić, czy istnieje taki zbiór X=(x₁,x₂,...,x_n):
; x  I.

Algorytm: Na wejściu mamy super rosnący ciąg liczb naturalnych A=(a₁,a₂,...,a_n). Wybieramy a_r liczb naturalnych takich, że (r,w): 1<w<r oraz r>
NWD(r,w)=1. For i=1 to n do k_i = w*a_i mod r. Klucz szyfr.: K_e=(k₁,k₂,...,k_n) - może być jawny, Klucz deszyfr.: K_d=(a₁,a₂,...,a_n,w ^-1,r) - ściśle tajny.

Dla deszyfracji: 1) S' = S*w ^-1 2) if S' >= a_n then m_n = 1 else m_n = 0. 3) For i = n-1 downto 1 do if
then m_i=1 else m_i=0. 4) m = (m₁,m₂,...,m_n)

Szyfrowanie zborów o dostępie swobodnym: Stosuje się tu GLP. Anderson opracował metodę szyfrowania zbiorów o dostępie swobodnym, w którym są generowane dwie tablice z hasła bądź nazwy użytkownika, każda o długości pierwiastka kwadratowego z długości zbioru wyrażona w rekordach. Tablice te zawierają wartości T₀ i c. Adres logiczny rekordu lub jego numer jest przekształcany w dwie liczby, które wybierają spośród tych wartości niepowtarzalne T₀ i c dla każdego rekordu, co zapewnia niepowtarzalny ciąg kluczy dla wszystkich rekordów. Można odczytać dane z jednego rekordu, ale nie ze wszystkich, ponieważ zostały zaszyfrowane innymi ciągami kluczy. Szyfrowanie i rozszyfrowanie przebiega dla każdego rekordu tak samo jak dla zbiorów sekwencyjnych. Algorytm: A1) Wprowadzenie nazwy zbioru użytkownika lub hasła (nazwiemy je PW), A2) Obliczenie
, A3) Generacja liczb pseudolosowych w oparciu o PW: K₁,K₂,...,K_Z, A4) Generacja liczb pseudolosowych w oparciu o PW: C₁,C₂,...,C_Z. B1) Weź adres logiczny (L) następnego rekordu do zaszyfrowania, B2) Q=L div z, R=L mod z, B3) T₀=K_Q, c=C_R, B4) j=1, B5) Generuj T_j=(aT_j-1+c) mod m., B6) Słowo_j=Słowo_j T_j, B7) Czy j=długość rekordu? Jeśli NIE: j=j+1 i Goto B5. Jeśli TAK: Czy są jeszcze jakieś rekordy? Jeśli TAK Goto B1. Jeśli NIE: Stop.

Szyfrowanie w sieciach: Wszystkie możliwe ścieżki danych od miejsca powstania komunikatu, aż do jego odbioru muszą być chronione. Danym nie wolno nigdy pojawić się w czytelnej postaci w sieci. Rozpoczęcie lub zatrzymanie operacji w jakimkolwiek momencie przez użytkownika lub komputer obsługujący nie może mieć trwałego wpływu na sieć . Dla uzyskania dostępu do sieci wszyscy użytkownicy ,terminale muszą być jednoznacznie identyfikowane. Całe szyfrowanie i rozszyfrowanie odbywa się w terminalu, a nie w komputerze głównym, gdyż przesyła się wtedy tekst otwarty, a nie zaszyfrowany. Można łatwo dopiąć się do linii transmisji danych i stracić dane.

SZYFROWANIE PROGRAMOWE - podsumowanie:

• generatory liczb pseudolosowych

• szyfrowanie z nieskończonym kluczem

• met Andersena dla zbiorów o dostępie swobodnym

• met Huffmana

• alg szyfrowania Frendberga

45. Szyfrowanie zbiorów o dostępie bezpośrednim.

Stosuje się tu GLP. Anderson opracował metodę szyfrowania zbiorów o dostępie swobodnym, w którym są generowane dwie tablice z hasła bądź nazwy użytkownika, każda o długości pierwiastka kwadratowego z długości zbioru wyrażona w rekordach. Tablice te zawierają wartości T₀ i c. Adres logiczny rekordu lub jego numer jest przekształcany w dwie liczby, które wybierają spośród tych wartości niepowtarzalne T₀ i c dla każdego rekordu, co zapewnia niepowtarzalny ciąg kluczy dla wszystkich rekordów. Można odczytać dane z jednego rekordu, ale nie ze wszystkich, ponieważ zostały zaszyfrowane innymi ciągami kluczy. Szyfrowanie i rozszyfrowanie przebiega dla każdego rekordu tak samo jak dla zbiorów sekwencyjnych. Algorytm: A1) Wprowadzenie nazwy zbioru użytkownika lub hasła (nazwiemy je PW), A2) Obliczenie
, A3) Generacja liczb pseudolosowych w oparciu o PW: K₁,K₂,...,K_Z, A4) Generacja liczb pseudolosowych w oparciu o PW: C₁,C₂,...,C_Z. B1) Weź adres logiczny (L) następnego rekordu do zaszyfrowania, B2) Q=L div z, R=L mod z, B3) T₀=K_Q, c=C_R, B4) j=1, B5) Generuj T_j=(aT_j-1+c) mod m., B6) Słowo_j=Słowo_j T_j, B7) Czy j=długość rekordu? Jeśli NIE: j=j+1 i Goto B5. Jeśli TAK: Czy są jeszcze jakieś rekordy? Jeśli TAK Goto B1. Jeśli NIE: Stop.

46. Szyfry symetryczne - szyfry asymetryczne.

Algorytmy są symetryczne jeśli klucze są takie same d_k(e_k(m))=m. Klucz deszyfrujący wyznacza się z klucza szyfrującego. Cała sprawa polega na utajnieniu klucza. Algorytmy te nazywane są też: algorytmami z pojedynczym kluczem, z tajnym kluczem. Wymagają uzgodnienia między adresatami wiadomości.

Algorytmy są asymetryczne jeżeli klucze są różne d_k2(e_k1(m))=m; e_k1(m)=c; d_k2(c)=m oraz k1≠k2. Klucz deszyfrujący wcale nie musi być wyprowadzalny z algorytmu szyfrującego.

Algorytmy te można podzielić na strumieniowe (jednostka podlegająca przekształceniu to bit) i blokowe (grupy bitów).

47. Szyfry blokowe - szyfry strumieniowe.

Szyfry strumieniowe - m-wiadmość dzielimy na n części m₁,m₂,...,m_n i każdy jest szyfrowany kluczem k_i=k₁,k₂,...; e_k(m)=e_k1(m₁) e_k2(m₂)... Szyfry strumieniowe są okresowe i nieokresowe oraz synchroniczne i samosynchronizujące się. W synchronicznych klucze są generowane w zależności od długości transmisji. W samosynchronizujących się, klucz szyfrujący zależy od poprzednich bloków już zaszyfrowanych.

Szyfry blokowe - m-wiadomość dzieli na bloki m₁,m₂,...,m_n; e_k(m)=e_k(m₁)e_k(m₂)...e_k(m_n)

W szyfrach tych stosuje się sumę symetryczną: c_i=e_k(m)=m⊕k_i; m=d_ki(c_i)=c_i⊕k_i=(m_i⊕k_i) ⊕k_i=m

ECB - (electronic codeblock) - elektronicznej cząstki bloku: każdy tekst jest dzielony na bloki, każdy blok szyfrowany. Bloki można szyfrować niezależnie.

CBC - (cipher block changing) - każdy blok łączy się operacją XOR z blokiem deszyfrującym. Mała propagacja błędu. c_i=e_i(m_i⊕c_i)

CFB - (cipher feedback mode) - tryb sprzężenia zwrotnego zaszyfrowanego tekstu. Można przekształcać mniejsze bloki (nawet bity). To co zostało zaszyfrowane zmienia zawartość rejestru przesuwającego na n-najstarszych bitach. Wynik szyfrowania jest sumowany modulo 2 z bitami, rezultat ten jest umieszczany na n-najniższych bitach. Blok ten jest modułem sprawdzającym szyfrogramu.

OFM - (output block feedback mode) - sprzężenie zwrotne bloków wyjściowych zamiast operacji XOR na najmłodszej pozycji rejestru to kierowany jest ten wynik do najstarszych bitów rejestru.

48. Techniki szyfrowania danych.

1. Metody klasyczne:

• podstawieniowe (momo i polialfabetyczne)

• przestawieniowe (szyfr cezara)

• złożone

2. metody programowe

• RSA

• ElGamala

• Generator liczby pseudolosowej

• Szyfr z nieskończonym kluczem

• Metoda hoffmana

• alg szyfrowania Frendberga

• metoda Merklego_Hellmana

3. metody sprzętowe

• rejestry przesuwające

• skrzynka podstawień

• skrzynka permutacji

• szyfr DESS

• system LUCIFER

• metoda bazująca na układzie CLIPPER CHIP

49. Szyfr DESS.

Metoda sprzętowa - dokonuje się tu podziału informacji wejściowej na bloki. Blok dzielimy na dwie części. Wykonujemy permutację na blokach wejściowych, następnie 16 razy funkcję przekształcającą dla każdego bloku, potem na wyjściu permutację.

50. Metoda RSA.

należy do metod wykładniczych. Algorytm: Na wejściu przyjmuje się dwie losowo wybrane duże liczby pierwsze p i q. Mnożymy je przez siebie n=p*q. Obliczamy funkcję Eulera od n (n). Wybieramy liczbę e losową między 1 do (n) ;e=<1, (n)>. Liczba e musi być względnie pierwszą z (n). Znajdujemy liczę odwrotna do e : d=e^-1 mod (n). Szyfrowanie: f(P)=P^e mod n. Deszyfrowanie: f ^-1(C)=C^d mod n. Uwagi: 1) p i q - co najmniej 100 - cyfrowe i nie mogą być blisko siebie. 2) (n) = n+1-p-q. 3) Klucz szyfrujący: K_e=(n,e), Klucz deszyfrujący: K_d=(n,d).

Przykład: Szyfruj słowo „YES”:

24*26²+4*26¹+18*26⁰ = 16346 = P

f(P) = 16346³⁹⁴²³ mod 46927 = 21166

21166 = 1*26³ + 5*26² + 8*26¹ + 2*26⁰ = „BFIC”

51. Metoda Merklego-Hellmana.

Bazuje na problemie „upakowanego plecaka”: istnieje zbiór I=(i₁,i₂,...,i_n): i_j  C oraz liczba b; Udowodnić, czy istnieje taki zbiór X=(x₁,x₂,...,x_n):
; x  I.

Algorytm: Na wejściu mamy super rosnący ciąg liczb naturalnych A=(a₁,a₂,...,a_n). Wybieramy a_r liczb naturalnych takich, że (r,w): 1<w<r oraz r>
NWD(r,w)=1. For i=1 to n do k_i = w*a_i mod r. Klucz szyfr.: K_e=(k₁,k₂,...,k_n) - może być jawny, Klucz deszyfr.: K_d=(a₁,a₂,...,a_n,w ^-1,r) - ściśle tajny.

Dla deszyfracji: 1) S' = S*w ^-1 2) if S' >= a_n then m_n = 1 else m_n = 0. 3) For i = n-1 downto 1 do if
then m_i=1 else m_i=0. 4) m = (m₁,m₂,...,m_n)

52. SZYFROWANIE - METODY SPRZĘTOWE

Rejestry przesuwające- generują duże nie powtarzające się rekurencje bitów, które mogą być użyte jako klucze szyfrów. Istnieje liniowa zależność pomiędzy komunikatem, a jego zaszyfrowaną wersją. Wskaźniki : nie szyfrować tekstu, gdy składa się z samych zer lub jedynek. Często zmieniać sprzężenia zwrotne , ukrywać brak aktywności lini. Szyfr produktowy to połączenie metod szyfrowania: permutacja i podstawienie.

SYS. LUCIFER - firmy IBM. Skrzynki podstawień S są urządzeniami, które zmieniają N bitów tekstu otwartego na N bitów tekstu zaszyfrowanego. Bardzo kosztowna, niż skrzynki permutacji - liniowe przekształcenie. Skrzynki permutacji są urządzeniami, które zmieniają N bitów tekstu otwartego na N bitów tekstu zaszyfrowanego. W odróżnieniu od skrzynek podstawień tasują tylko cyfry i nie wykonują nieliniowych przekształceń. Są tanie i łatwo je złamać(P).LUCIFER opiera się na rozwiązaniu, w którym użyto warstw skrzynek P. i małych skrzynek S. Dane te przechodzą przez naprzemienne warstwy tych skrzynek. Każda skrzynka S ma dwa stany S1 lub S2 . Wzorzec ustawiony jest za pomocą dwójkowego klucza. Dł. klucza jest dostatecznie wielka by istniała ilość niepowtarzalnych kluczy, służących jako klucze uniwersalne w różnych instalacjach. Lucyfer jest wyposażony w generator haseł działający automatycznie po obydwu stronach łącza telekomunikacyjnego. Komunikaty są automatycznie dzielone na bloki o stałej długości D cyfr danych. Wynikowy kod bloku 2D cyfr jest kodowany przez przepuszczenie go przez warstwy skrzynek S i P, co dokładnie miesza cyfry hasła z cyframi danych. Dla rozkodowania musi być drugie urządzenie w odbiorniku ustawione z odpowiednim kluczem dla skrzynek S , a odebrane hasło musi być tożsame z hasłem lokalnie wygenerowanym przez zegar binarny. Lucyfer jest bardzo skomplikowany.

SZYFROWANIE W SIECIACH : Wszystkie możliwe ścieżki danych od miejsca powstania komunikatu, aż do jego odbioru muszą być chronione. Danym nie wolno nigdy pojawić się w czytelnej postaci w sieci. Rozpoczęcie lub zatrzymanie operacji w jakimkolwiek momencie przez użytkownika lub komputer obsługujący nie może mieć trwałego wpływu na sieć . Dla uzyskania dostępu do sieci wszyscy użytkownicy ,terminale muszą być jednoznacznie identyfikowane. Całe szyfrowanie i rozszyfrowanie odbywa się w terminalu, a nie w komputerze głównym, gdyż przesyła się wtedy tekst otwarty, a nie zaszyfrowany. Można łatwo dopiąć się do linii transmisji danych i stracić dane.

53. Bezpieczeństwo systemów kryptograficznych.

Stosuje się kryteria Skannonna

1. ilość tajności zaoferowanej (ocenienie wewnętrznej mocy algorytmu)

2. rozmiar klucza (jak najmniejszy zapewniający bezpieczeństwo)

3. łatwość (prostota procesu)

4. propagacja błędów (powinna być zminimalizowana)

5. powiększanie się wiadomości zaszyfrowanej

Często spełnienie wszystkich kryteriów jest niemożliwe, bo są one sprzeczne ze sobą, stosuje się dwa algorytmy:

• konfuzja: działanie aby jak najbardziej różnił się tekst zaszyfrowany od szyfrowanego

• dyfuzja: działanie mające na celu zagubienie wiadomości statystycznych wiadomości podlegającej szyfrowaniu.

Łamanie brutalne - wypróbowanie wszystkich możliwych kluczy, które mogą wystąpić. Decyduje tu długość klucza (dla 8 bitów jest 256 możliwości i można to zrobić w ciągu dnia samemu, przy 64 bitach aby złamać szyfr w jeden dzień trzeba około miliona procesorów i każdy musi wykonywać około miliona szyfrowań na sekundę).

Łamanie słownikowe - słowa, które właściciel mógł zastosować

54. Zastosowanie funkcji jednokierunkowych.

55. Realizacja podpisów cyfrowych.

56. Pozyskiwanie danych z baz danych statystycznych.

Statystyczne BD są to takie systemy BD, w których bezpośrednio przechowuje się dane statystyczne oraz dane indywidualne. Np. dla GUS istnieją 3 BD będące w różnych częściach kraju i tworzące 1 całość. W 1- tylko adresy respondentów i ich nr identyfikacyjne pierwsze ; w 2- nr identyfikacyjne pierwsze i nowe nr bezimienne; w 3- nr bezimienne + dane statystyczne.

Mamy kilka metod na odkrycie danych ukrytych w danych statystycznych na dane indywidualne:

1. należy znać cechy indywidualne danej osoby , które są reprezentowane w BD

2. charakteryzuje się tym, że nie da się określić zbioru cech, które opisują obiekt w systemie. Można dowiedzieć się poprzez potwierdzenie danej teorii poprzez zakwalifikowanie osoby do danej grupy.

Niepodawanie liczb - należy przekłamywać wyniki uzyskane z wyniku cech np. 0,1- nie podawać.

Zakładamy : nie podawać małych liczb poniżej progu T_min, tylko zamiast nich : 0, kilka, T_min

3. polega na tym, że można spróbować złamać to co wynika ze statystyki w BD, że zadamy pytanie o obiekty , które cechują się cechami odwrotnymi.

4. możemy zastosować algebrę , z cech możemy ułożyć układ równań i wyliczyć wartości interesującej nas cechy.

5. zneutralizowanie skrótów niepodawania małych liczb poprzez dodanie sztucznych rekordów. Jeżeli system pozwala użytkownikowi zadawać nie tylko pytania ale także wprowadzać dane to wówczas wystarczy dodać m-1 fikcyjnych rekordów, gdzie m.- najmniejsza lb całkowita większa od kilka, o atrybutach P₀ ,P₁, ...,P_n. P₀- to jeden z atrybutów. To pozwala posłużyć się met 2.

Zdarza się, że odkrycie pewnych zbiorów informacji jest obojętne w skutkach podczas gdy szczegółowe podanie tych informacji może być bardzo szkodliwe.

57. BAZY DANYCH STATYSTYCZNE

Statystyczne BD są to takie systemy BD, w których bezpośrednio przechowuje się dane ststystyczne oraz dane indywidualne. Np. dla GUS istnieją 3 BD będące w różnych częściach kraju i tworzące 1 całość. W 1- tylko adresy respondentów i ich nr identyfikacyjne pierwsze ; w 2- nr identyfikacyjne pierwsze i nowe nr bezimienne; w 3- nr bezimienne + dane statystyczne.

Mamy kilka metod na odkrycie danych ukrytych w danych ststystycznych na dane indywidualne:

1. należy znać cechy indywidualne danej osoby , które są reprezentowane w BD

1. charakteryzuje się tym, że nie da się określić zbioru cech, które opisują obiekt w systemie. Można dowiedzieć się poprzez potwierdzenie danej teorii poprzez zakwalifikowanie osoby do danej grupy.

Niepodawanie liczb - należy przekłamywać wyniki uzyskane z wynikucech np. 0,1- nie podawać.

Zakładamy : nie podawać małych liczb poniżej progu T_min, tylko zamiast nich : 0, kilka, T_min

1. polega na tym, że można spróbować złamać to co wynika ze statystyki w BD, że zadamy pytanie o obiekty , które cechują się cechami odwrotnymi.

1. możemy zastosować algebrę , z cech możemy ułożyć układ równań i wyliczyć wartości interesującej nas cechy.

1. zneutralizowanie skrótów niepodawania małych liczb poprzez dodanie sztucznych rekordów.Jeżeli system pozwalaużytkownikowi zadawać nie tylko pytania ale także wprowadzać dane to wówczas wystarczy dodać m-1 fikcyjnych rekordów, gdzie m.- najmniejsza lb całkowita większa od kilka, o atrybutach P₀ ,P₁, ...,P_n. P₀- to jeden z atrybutów. To pozwala posłużyć się met 2.

Zdarza się, że odkrycie pewnych zbiorów informacji jest obojętne w skutkach podczas gdy szczegółowepodanie tych informacji może być bardzo szkodliwe.

Środki ochrony statystycznych BD :

• prowadzenie dziennika

• szczepienia- wprowadzenie do danych przypadkowych błędów , które nieprawidłowo podają wyniki dla indywidualnych osób, a dla ogólnej liczby statystycznej jest podany wynik dobrze. To rozwiązanie nie daje się zastosować do zbiorów, które muszą zawierać dokładne dane.

• zbiory łączące - rozbijamy BD na podbazy tak jak przykład z GUS.

Metody złamania bezpieczeństwa SBD :

• wyizolowanie osobnika w bd na podstawie cech indywidualnych

• umieszczenie osobnika w grupie charakteryzującej się pewną cechą

• umieszczenie osobnika poza grupą charakteryzującą się pewną cechą

• zneutralizowanie skutków niepodawania małych liczb przez dodanie sztucznych rekordów

• układ równań

57. Ochrona baz danych statystycznych.

Środki ochrony statystycznych BD :

• prowadzenie dziennika

• szczepienia- wprowadzenie do danych przypadkowych błędów , które nieprawidłowo podają wyniki dla indywidualnych osób, a dla ogólnej liczby statystycznej jest podany wynik dobrze. To rozwiązanie nie daje się zastosować do zbiorów, które muszą zawierać dokładne dane.

• zbiory łączące - rozbijamy BD na podbazy tak jak przykład z GUS.

Metody złamania bezpieczeństwa SBD :

• wyizolowanie osobnika w bd na podstawie cech indywidualnych

• umieszczenie osobnika w grupie charakteryzującej się pewną cechą

• umieszczenie osobnika poza grupą charakteryzującą się pewną cechą

• zneutralizowanie skutków niepodawania małych liczb przez dodanie sztucznych rekordów

• układ równań

I Postać normalna - Relacja R jest w pierwszej postaci normalnej (1NF) wtedy i tylko wtedy, gdy wszystkie dziedziny podstawowe zawierają jedynie wartości atomowe.

II Postać normalna - gdy relacja jest w INF i każdy jej atrybut niekluczowy jest w pełni funkcjonalnie zależny od klucza głównego.

Relacja jest w drugiej postaci normalnej jeżeli dla każdej zależności X->Y, w której Y nie zawiera się w X , zbiór X zawiera klucz (tzn. X jest nadkluczem). Relacja w drugiej postaci normalnej nie zawiera redundancji i anomalii. Aby doprowadzić relację do II postaci normalnej można przeprowadzić operację rozkładu schematu relacji. Dowolną relację można przekształcić do postaci normalnej Boyce'a dokonując jej rozkładu na kilka innych relacji. Z relacji tych można zawsze otrzymać relację pierwotną w wyniku ich naturalnego złączenia.

np.: <nazwisko, ulica, miasto, województwo, data, wielkość>

zależności: nazwisko -> ulica,miasto,województwo

nazwisko,data -> wielkość

miasto -> województwo

klucz : {nazwisko, data}

Podział 1: R1 <nazwisko, ulica, miasto, województwo>

R2 <nazwisko, data, wielkość>

Podział 2: R3 <nazwisko, ulica>

R4 <miasto,województwo>

R1, R2, R3, R4 są drugiej postaci normalnej.

III POSTAĆ NORMALNA - gdy relacja jest w IINF i każdy atrybut niekluczowy jest nietranzytywnie zależny od klucza głównego.

Boyce'a: Relacja R jest w III postaci normalnej, jeżeli dla każdej zależności X->A (A jest funkcjonalnie zależny od X), w której A nie zawiera się w X albo X zawiera klucz, albo A jest atrybutem głównym. Atrybut główny to taki, który należy do każdego klucza relacji R. Inaczej mówiąc relacja jest w III postaci normalnej, jeżeli żaden niegłówny atrybut A nie jest funkcyjnie zależny od zbioru atrybutów X, które nie zawierają klucza i atrybutu A.

Dowolną relację można przekształcić do trzeciej postaci normalnej korzystając z metody Bernstelna.

1. Stosując regułę X->Y:Y->Z=>X->Z przekształcić każdą zależność w ten sposób, aby po prawej stronie zależności był tylko jeden atrybut

1. Wyeliminuj powtarzające się zależności

1. Przekształć zależności tak, by żaden podzbiór atrybutów stojący po lewej stronie zależności nie określał prawej strony zależności

1. Połącz zależności z takimi samymi lewymi stronami stosując regułę X->Y i X->Z=>X->Y∪Z. Gdy X->Y jest na liście zależności, dokonaj projekcji na zbiór X atrybutami X∪Y (krok ten zapewnia zachowani zależności).

1. Znajdź klucz do relacji pierwotnej. Jeżeli żaden z kluczy nie jest zawarty w projekcjach utworzonych w kroku [4], to utwórz nowy zbiór z atrybutami klucza. Krok ten gwarantuje powrót do relacji pierwotnej przez naturalne złączenie. Atrybut, który nie występuje w jakiejkolwiek zależności musi być w każdym kluczu.

1. Jeżeli jakiś z nowo utworzonych zbiorów jest projekcja innego, to wyeliminuj mniejszy zbiór.

Magazyn <nr, mistrz, wydział, materiał, ilość, cena>

zależność: nr->mistrz

mistrz->wydział

mistrz,materiał->ilość

materiał->cena

1.nr->mistrz

mistrz->wydział

mistrz,materiał->ilość

materiał->cena

2. Brak zależności redundancyjnych

3. Lewe strony zależności są minimalne, tzn. żaden podzbiór atrybutów z lewej strony nie określa prawej strony zależności.

4,5. Otrzymujemy 5 relacji

a1<nr, mistrz>

a2<mistrz,wydział>

a3<mistrz, materiał, ilość>

a4<materiał, cena>

a5<nr, materiał>

6.Żadna z powyższych relacji nie zawiera się w innej relacji.

IV POSTAĆ NORMALNA

Czwartą postać normalną stosuje się do relacji z zależnościami wielowartościowymi. Zależności wielowartościowe definiujemy:

Niech relacja R zawiera zbiory atrybutów X,Y,Z. Zbiór x wyznacza wieloznacznie(X →→Y), jeżeli w relacji R istnieją krotki(x,y,z) i (x',y',z') to stąd wynika, że istnieją również krotki (x,y',z) i (x,y,z'). Z symetryczności definicji wynika również, że X→→Z.

Relacja jest w czwartej postaci normalnej, jeżeli zawsze, gdy zbiór atrybutów X określa wielowartościowo Y, to zachodzi jeden z następujących warunków :

1. Y jest puste lub zawiera się w X.

1. Suma zbiorów X i Y jest kompletnym zbiorem atrybutów dla danej relacji.

1. X zawiera klucz.

W celu rozłożenia relacji z zależnościami wielokrotnymi na relację w czwartej postaci normalnej należy określić zależności X→Y i X→Z przez dokonanie projekcji na relację z atrybutami X∪Y i X∪Z gdzie Z = S - Y - X.

PIĄTA POSTAĆ NORMALNA

R' R” jeżeli → łączenie dwóch relacji

jeżeli zależność → zależność połączeniowa

W relacji R o schemacie R(A₁,..., A_n ) występuje join- zależność N(R₁,R₂,...,R_n), gdy dla dowolnej relacji R w tym schemacie zachodzi :

r = Π _R1 (r) Π _R2 (r) Π _Rn (r)

Oznacza to, że join - zależność występuje wówczas, jeżeli po rozbiciu tej relacji przez project i złączeniu przez join to samo.

W danej relacji R występuje 5NF, jeśli występuje w niej 4 zależność normalna, jest tu join - zależność zależna od klucza.

JD (R₁,..., R_m)

poziom zewnętrzny

poziom pojęciowy

poziom fizyczny

A

B

nazwisko

nr pesel

mąż

mężatka (żona)

nazwisko współmałżonka

nazwisko pracownika

c

mężczyzna

kobieta

małżeństwo

rodzeństwo

TOWARY

CZŁONKOWIE

ZAMÓWIENIA

ZAMÓWIENIA

TOWARY

CZŁONKOWIE

ZAMÓWIENIA

Wirtualne zamówienia

A

B

Wirt.A

Wirt.B

TOWARY

Wirt. członkowie

ZAMÓWIENIA

CZŁONKOWIE

Wirt.TOWARY

Wirt.ZAMÓWIENIA

maszyna

podzespół

część

drużyna

zawodnicy

sponsor

użytkownik

program

użytkowy

poziom

zewnętrzny

poziom

fizyczny

poziom

pojęciowy

X

Y

Z

Monitor transakcji

Menedżer prezentacji PM

Klient C

Menedżer transakcji TM

Menedżer komunikacji CM

Świat

DBMS

Dane

Program

aplikacyjny

Pamięć

dzielona

KLIENT

SERWER

Interfejs

sieci

Interfejs

sieci

SIEĆ

Serwer

Bazy danych

Zdalnie dostępny

Interfejs b.d.

---