Bazy danych 1000-213bBAD
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
Rodzaj przedmiotu
Tryb prowadzenia
Wymagania (lista przedmiotów)
Efekty kształcenia
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).
Kryteria oceniania
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.
Literatura
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.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: