Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Bazy danych

Informacje ogólne

Kod przedmiotu: 1000-213bBAD Kod Erasmus / ISCED: 11.302 / (0612) Database and network design and administration
Nazwa przedmiotu: Bazy danych
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obowiązkowe dla II roku (3. semestr) JSIM - wariant 3I+4M
Przedmioty obowiązkowe dla II roku (3. semestr) JSIM - wariant 3M+4I
Przedmioty obowiązkowe dla II roku informatyki
Punkty ECTS i inne: 5.50
zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Wymagania (lista przedmiotów):

Podstawy matematyki 1000-211bPM
Programowanie obiektowe 1000-212bPO
Wstęp do programowania (podejście imperatywne) 1000-211bWPI

Skrócony opis:

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.

Pełny opis:

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

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.

Efekty uczenia się:

Wiedza

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

2. Zna najważniejsze własności algebry relacji (K_W01, K_W02).

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

4. Zna podstawowe własności języka zapytań SQL (K_W01, K_W02).

5. Ma ogólną wiedzę na temat zasad projektowania baz danych (K_W01, K_W02).

6. Dobrze rozumie rolę i znaczenie transakcji w bazach danych (K_W01, K_W02).

Umiejętności

1. Potrafi formułować zapytania SQL (K_U09).

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

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

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

(K_U10).

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

Kompetencje

1. Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia, w tym zdobywania wiedzy pozadziedzinowej (K_K01).

2. Potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania (K_K02).

Metody i kryteria oceniania:

Składniki oceny:

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

- klasówka z SQLa: 5 zadań po 4 punkty = 20 punktów;

- klasówka z modelowania: 2 zadania po 10 punktów = 20 punktów;

- egzamin: 4 zadania po 10 punktów = 40 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.

Zajęcia w cyklu "Semestr zimowy 2018/19" (zakończony)

Okres: 2018-10-01 - 2019-01-25
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Krzysztof Stencel
Prowadzący grup: Szymon Acedański, Tomasz Gogacz, Zbigniew Jurkiewicz, Paweł Kucharczyk, Filip Murlak, Barbara Poszewiecka, Krzysztof Stencel
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr zimowy 2019/20" (w trakcie)

Okres: 2019-10-01 - 2020-01-27
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Filip Murlak
Prowadzący grup: Szymon Acedański, Tomasz Gogacz, Zbigniew Jurkiewicz, Paweł Kucharczyk, Michał Kutwin, Filip Murlak
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.