Bazy danych

obowiązkowe

Podstawy matematyki 1000-211bPM
Programowanie obiektowe 1000-212bPO
Wstęp do programowania 1000-211bWPI

zdalnie

Funkcje i struktury systemów baz danych oraz przegląd modeli danych. Relacyjne bazy danych. Języki zapytań do relacyjnych baz danych (algebra relacji, logika pierwszego rzędu, SQL i Datalog). Projektowanie baz danych: modelowanie pojęciowe i przejście do poziomu logicznego. Fizyczne aspekty składowania danych i wykonywania zapytań, metody optymalizacji zapytań, przetwarzanie transakcji.

Co to jest baza danych? O czym będzie?

1.modelowanie danych: tabele, drzewa, grafy

2. języki zapytań: pisanie zapytań, siła wyrazu, ewaluacja

3. meta-dane: więzy i zależności

4. wykorzystywanie i utrzymywanie perspektyw

5. transakcje

Języki zapytań dla relacyjnych baz danych.

1. logika pierwszego rzędu (FO)

2. algebra relacji (RA)

3. SQL

4. równoważność jezyków

Specyfika SQLa: agregacja i nulle.

1. semantyka multizbiorowa, agregacja

2. różne role wartości NULL

3. semantyka wartości NULL w SQLu

4. semantyka pewnych odpowiedzi (*)

5. różne złączenia

Rekurencja (*)

1. czego się nie da wyrazić w FO: osiągalność

2. Datalog

3. RA z iteracją (while, inflationary while)

4. porównanie z klasami złożoności i rozszerzeniami FO

5. ograniczona rekurencja w SQLu

Pojęciowy model danych

1. modelowanie dziedziny jako analiza rzeczywistości

2. obiektowe modelowanie dziedziny

3. elementy języka UML

Logiczny model danych

1. do modelu dziedziny do projektu bazy danych

2. od obiektów do relacji (reprezentacja hierarchii dziedziczenia)

3. rola metadanych (więzy)

4. zależności funkcyjne, klucze (PRIMARY KEY, UNIQUE)

5. zależności inkluzji (REFERENCES)

6. inne więzy (CONSTRAINT)

7. krótko o anomaliach, redundancji i postaci BCNF

Normalizacja (*)

1. anomalie; co to jest redundancja?

2. wyprowadzanie zależności funkcyjnych

3. dekompozycja z rzutowaniem zależności

4. BCNF i algorytm dekompozycji

5. odzyskiwanie informacji (lossless join)

6. utrata zależności przy dekompozycji i 3NF

7. dekompozycja do 3NF

Perspektywy i wyzwalacze

1. perspektywy

2. autoryzacja (grant, revoke)

3. wyzwalacze i operacje na perspektywach

4. materializowane perspektywy i ich utrzymywanie (*)

5. utrzymywanie domknięcia przechodniego bez rekurencji (*)

XML (*)

1. jak modelować dane o hierarchicznej strukturze?

2. drzewa i dokumenty XML

3. języki definiowania schematu: DTD, XML Schema, RelaxNG.

4. jezyki zapytań: FO vs. XPath, Xquery

Grafowe bazy danych (*)

1. grafy i języki z rekurencją: RPQ

2. RDF i SPARQL

3. LPG i Cypher

Ewaluacja zapytań

1. algorytmy dla operacji RA (w modelu RAM)

a. suma, rzutowanie, selekcja przez full-scan (liniowo)

b. złączenie, różnica, eliminacja duplikatow i grupowanie przez sortowanie (liniowo-logarytmicznie + rozmiar wyniku), lub przez haszowanie

2. optymalizacja planów zapytań przez minimalizację rozmiaru pośrednich wyników: proste heurystyki (przepisywanie, SIP)

3. twierdzenie o homomorfizmie i minimalizacja zapytań koniunkcyjnych (*)

4. ewaluacja zapytań XPath bez porównań (*)

5. ograniczenie AGM i pesymistycznie optymalne algorytmy obliczania złączeń (*)

Algorytmy w modelu I/O (*)

1. model I/O: pamiec z ewnetrzna, strony i ramki

2. trzy podstawowe “operacje”: skanowanie, sortowanie i wyszukiwanie

3. skanowanie: blokowanie odczytów

4. sortowanie w pamięci zewnętrznej

5. realizacja słownika (indeksu): B+ drzewa, hash-table

Transakcje

1. realistyczny model: wielu klientów, awarie systemu

2. ACID

3. poziomy izolacji

4. implementacja poziomu serializable: “conflict-serializable” i 2PL (*)

5. wykrywanie zakleszczenia (*)

Rozproszone bazy danych (*)

1. model rozproszony

2. 2PC

(*) – tematy opcjonalne, do wyboru dla prowadzącego

1. J. Ulmann, J. Widom, Podstawowy wykład z systemów baz danych, WNT 2000.

2. S. Abiteboul, R. Hull, V. Vianu, Foundations of databases , Addison - Wesley 1995

3. L. Banachowski, K. Stencel, Bazy danych. Projektowanie aplikacji na serwerze, EXIT, 2001.

Wiedza

* Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie programowania, algorytmów i złożoności, architektury systemów komputerowych, systemów operacyjnych, technologii sieciowych, języków i paradygmatów programowania, baz danych, inżynierii oprogramowania (K_W02).

* Ma wiedzę na temat zarządzania informacją, w tym dotyczącą systemów baz danych, modelowania danych, składowania i wyszukiwania informacji (K_W08), w szczególności:

1. Ma uporządkowaną wiedzę w zakresie składni i semantyki języka zapytań pierwszego rzędu.

2. Zna najważniejsze własności algebry relacji.

3. Ma pełną wiedzę w zakresie teorii zależności funkcyjnych i postaci normalnych.

4. Zna podstawowe własności języka zapytań SQL.

5. Ma ogólną wiedzę na temat zasad projektowania baz danych.

6. Dobrze rozumie rolę i znaczenie transakcji w bazach danych.

Umiejętności

* Potrafi pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie (K_U02).

* Potrafi samodzielnie planować i realizować własne uczenie się przez całe życie (K_U09).

* Potrafi tworzyć proste, bezpieczne aplikacje internetowe z wykorzystaniem baz danych oraz projektować dla nich wygodny interfejs użytkownika (K_U14),

* Potrafi budować proste systemy bazodanowe wykorzystujące przynajmniej jeden z najbardziej popularnych systemów zarządzania bazą danych; potrafi formułować zapytania do bazy danych w wybranym języku zapytań (K_U15)

* Ponadto:

1. Potrafi formułować zapytania SQL.

2. Potrafi pisać programy składowanie i wyzwalacze w co najmniej jednym języku programowania składowanego.

3. Potrafi rozpoznać anomalie w projekcie bazy danych i doprowadzić ją do odpowiedniej postaci normalnej.

4. Potrafi zaprojektować i zaimplementować relacyjną bazę danych.

5. Ma podstawowe umiejętności w zakresie strojenia relacyjnych baz danych.

Kompetencje

* Student jest gotów do krytycznej oceny posiadanej wiedzy i odbieranych treści (K_K01).

* Student jest gotów do pracy z zachowaniem uczciwości intelektualnej w działaniach własnych i innych osób; przestrzegania zasad etyki zawodowej i wymagania tego od innych oraz dbałości o dorobek i tradycje zawodu informatyka (K_K02).

* Student jest gotów do uznawania znaczenia wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz wyszukiwania informacji w literaturze oraz zasięgania opinii ekspertów (K_K03).

* Student jest gotów do wypełniania zobowiązań społecznych związanych z racjonalnym i bezpiecznym przetwarzaniem danych (K_K04).

Składniki oceny:

- mikrozadania: 10 małych prac domowych, każde warte 1 punkt = 10 punktów;

- projekt: oceniany w skali 0-20 punktów;

- klasówka z SQLa (w czasie laboratorium, 90 minut): 5 zadań po 4 punkty = 20 punktów;

- klasówka z modelowania (w czasie wykładu, 90 minut): 2 zadania po 10 punktów = 20 punktów;

- egzamin pisemny (120 minut): 3 zadania po 10 punktów = 30 punktów.

Suma punktów (0-100) decyduje o uzyskanej ocenie, zgodnie z następującymi progami: 50 na 3, 60 na 3+, 70 na 4, 80 na 4+, 90 na 5.

Istnieje możliwość zastąpienia egzaminu pisemnego egzaminem ustnym w terminie zerowym. Dopuszczenie do tego egzaminu wymaga zdobycia co najmniej 65 punktów z mikrozadań, projektu i obu klasówek (łącznie).

W drugim terminie można poprawić każdy ze składników oceny (do ostatecznej liczby punktów brany jest lepszy z dwóch wyników). Sumaryczna liczba punktów możliwa do uzyskania za każdy składnik oraz progi na poszczególne oceny w drugim terminie będą takie same, jak w pierwszym terminie. Podejście do którejś z klasówek lub egzaminu w drugim terminie polega na oddaniu rozwiązań zadań z odpowiedniego segmentu egzaminu poprawkowego (180 minut). Reguły poprawiania mikrozadań i projektu ustalają prowadzący laboratoria.