Napredne baze podataka

Cilj i ishod predmeta

Upoznavanje studenata sa principima, elementima i načinom rada savremenih sistema za upravljanje bazama podataka. Nakon ovog kursa studenti će biti u stanju da razumeju internu funkcionalnost sistema za upravljanje bazama podataka. Biće u stanju da analiziraju osnovne algoritme za evaluaciju upita i kontrolu konkurentnosti. Moći će da implementiraju ili modifikuju postojeće module sistema za upravljanje bazama podataka i da ocenjuju njihove performanse.

Teorijska nastava

Fizička arhitektura sistema za upravljanje bazama podataka. Upravljanje memorijskim prostorom. Upravljanje datotekama. Fizička organizacija baza podataka. Baze u memoriji. Indeksiranje na bazi stabla. Indexed Sequential Access Method (ISAM). Pretraživanje, umetanje, brisanje i duplikati. Kompresija ključa. Masovno učitavanje B+ stabla. Indeksiranje na bazi heširanja. Statičko, proširivo i linearno heširanje. Evaluacija upita. Sistemski katalog. Algoritmi za relacione operacije. Eksterno sortiranje. Eksterni Merge Sort. Upotreba B+ stabala za sortiranje. Evaluacija relacionih operatora. Operacija selekcije (bez indeksa – nesortirani i sortirani podaci, sa indeksom – indeks sa B+ stablom, heš indeks). CNF i podudaranje indeksa. Selekcije sa disjunkcijom. Operacija projekcije. Operacija Join. Operacije nad skupovima. Operacija agregacije. Optimizacija upita. Prevođenje SQL upita u algebru. Ekvivalencije relacione algebre (selekcije, projekcije, preseci i unije). Upiti sa više relacija. Ugnježdeni podupiti. Optimizacije na bazi cene i na bazi pravila. Upravljanje transakcijama. ACID skup osobina. Transakcije i raspoređivanje. Konkurentno izvršavanje transakcija. Kontrola konkurentnosti na bazi ključeva. Podrška transakcijama u SQL-u. Oporavak od otkaza. Atomičnost i rollback implementacija. Implementacija distribuiranih baza podataka. Evaluacija paralelnih upita. Particionisanje podataka. Nerelacione i NoSQL baze podataka. Deduktivne, temporalne i prostorne baze podataka.

Praktična nastava

Sistem otvorenog koda za upravljanje bazama podataka MySQL. Analiza arhitekture i eksperimentalna modifikacija sledećih modula: Connection Manager, Thread Manager, Connection Thread, User Authentication, Access Control, Parser, Command Dispatcher, Query Cache, Optimizer, Table Manager, Table Modification, Table Maintenance, Status Reporting, Abstracted Storage Engine Interface, Storage Engine Implementations (MyISAM, InnoDB, MEMORY, Berkeley DB), Logging, Replication Master, Replication Slave, Client/Server Protocol API.