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 (*)
Koordynatorzy przedmiotu
W cyklu 2026Z: | W cyklu 2025Z: |
Rodzaj przedmiotu
Wymagania (lista przedmiotów)
Założenia (lista przedmiotów)
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
Ocena końcowa jest oparta o prace domowe (10 zadań po 2 punkty), klasówkę (3 zadania po 20 punktów) oraz egzamin ustny z 3 pytań teoretycznych po 10 punktów. Progi na poszczególne oceny: 50 dst, 60 dst+, 70 db, 80 db+, 90 bdb, 100 bdb+.
W drugim terminie ocenę uzyskuje się wyłącznie na podstawie poprawkowego egzaminu ustnego, który obejmuje zarówno zadania jak i pytania teoretyczne. Do tego egzaminu może przystąpić każdy. Nowa ocena jest uwzględniana jedynie jeśli jest wyższa niż ocena w pierwszym terminie.
Forma zaliczenia dla doktorantów: opracowanie materiałów dydaktycznych do przeprowadzenia jednego wykładu oraz jednych zajęć laboratoryjnych na wybrany temat związany z modelowaniem w biologii obliczeniowej.
W drugim terminie ocenę uzyskuje się wyłącznie na podstawie poprawkowego egzaminu ustnego, który obejmuje zarówno zadania jak i pytania teoretyczne. Do tego egzaminu może przystąpić każdy. Nowa ocena jest uwzględniana jedynie jeśli jest wyższa niż ocena w pierwszym terminie.
Dla doktorantów dodatkowym wymaganiem zaliczenia jest przygotowanie i przeprowadzenie jednych zajęć dla pozostałych uczestników na podstawie wskazanej przez wykładowców literatury.
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: