Algorytmika przetwarzania zapytań 1000-2M25APZ
1. Podstawowe własności algebry relacji: złożoność i siła wyrazu.
2. Paradygmaty ewaluacji zapytań: sprawdzanie, wyznaczanie, zliczanie,
agregowanie, wyliczanie i próbkowanie odpowiedzi
3. Modele kosztu algorytmów, klasyczne metody optymalizacji zapytań w
silnikach bazodanowych
4. Algorytm Yannakakisa dla zapytań acyklicznych
5. Algorytmy oparte o dekompozycję zapytań (szerokość drzewiasta, itp.)
6. Obliczanie złączeń: ograniczenie AGM, algorytm leapfrog trie-join
7. Algorytm Fagina (FA) i algorytm progów (TA)
8. Model MPC i algorytm HyperCube
9. Metody ewaluacji zapytań rekurencyjnych: rekurencja w SQLu, ewaluacja
Datalogu (naive, seminaive, top-down, magic set)
10. Analiza statyczna: spełnialność, równoważność, inkluzja, nierozstrzygalność
dla algebry relacji, minimalizacja zapytań koniunkcyjnych (*)
11. Inne architektury: kolumnowe, faktoryzowane (*)
12. Inne modele danych: grafowe i semistrukturalne bazy danych (*)
Rodzaj przedmiotu
Wymagania (lista przedmiotów)
Założenia (lista przedmiotów)
Koordynatorzy przedmiotu
Efekty kształcenia
Wiedza
Student zna i rozumie specyfikę modeli efektywności stosowanych w przetwarzaniu
danych w różnych modelach obliczeń. (S_W04, S_W09, K_W01, K_W04)
Student zna i rozumie wyzwania algorytmiczne przetwarzania danych w dużej skali.
(S_W09, K_W01, K_W05)
Student zna i rozumie wybrane paradygmaty ewaluacji zapytań i przyczyny ich
wyodrębnienia. (S_W02, K_W01)
Student zna i rozumie zaawansowane algorytmy stosowane w przetwarzaniu
zapytań bazodanowych. (S_W04, S_W09, S_W10, K_W01, K_W05)
Umiejętności
Student potrafi dostosować poznane metody algorytmiczne do różnorodnych
wariantów rozważanych zagadnień. (S_U03, K_U01, K_U02)
Student potrafi dobrać najlepsze rozwiązanie algorytmiczne zależnie od
charakterystyki praktycznych instancji rozważanego zagadnienia ( K_U01, K_U02).
Student potrafi wyodrębniać problemy algorytmiczne z konkretnych zagadnień
przetwarzania zapytań. (K_U03)
Student potrafi uzasadnić poprawność zaproponowanego rozwiązania
algorytmicznego i ocenić jego efektywność. (K_U02, K_U03)
Kompetencje
Student jest gotów do wykorzystywania własnej wiedzy i umiejętności oraz opinii
ekspertów do rozwiązywania problemów, w tym problemów badawczych. (K_K02)
Student jest gotów do stosowania twórczego i innowacyjnego podejścia do
rozwiązywania problemów. (K_K03)
Kryteria oceniania
Końcowa ocena oparta jest o łączną sumę punktów z prac domowych, klasówki i
egzaminu.
Literatura
S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases (dostępna online).
M. Arenas, P. Barcelo, L. Libkin, W. Martens, A. Pieris, Database Theory: Querying
Data (wczesna wersja dostępna online).
Wybrane artykuły naukowe.
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: