FOI nastava
FOI logo

Lista kolegija iz:

ak.god:
2013/2014
semestar:
2. semestar

2013/2014

5ECTSa

Diplomski

Diplomski studij informatike v1.2

Program Obavezan
Baze podataka i baze znanja BPBZ Da
Informatika u obrazovanju IO Ne
Informacijsko i programsko inženjerstvo IPI Ne
Organizacija poslovnih sustava OPS Ne
2. semestar
1. nastavna godina

Fizičko oblikovanje baza podataka npp:93119

Engleski naziv

Physical Design of Databases

Katedra

Katedra za teorijske i primijenjene osnove informacijskih znanosti

Kategorija ("boja")

RI

Cilj kolegija

Ovaj kolegij daje znanja koja upotpunjuju znanja potrebna za cjelovito razumijevanje sustava za upravljanje bazama podataka (SUBP), njihovog rada i načina na koji su u praksi izvedeni. Ovaj kolegij koristi znanja iz mnogih drugih kolegija, kao što su Baze podataka 1, Algoritmi, Strukture podataka itd. te se prirodno nadovezuje na njih u posebnom kontekstu. Znanja koja se ovdje daju studentu upućuju ga u način rada jednog progamskog sustava koji se po zastupljenosti na računalu svrstava na drugo mjesto, odmah iza operacijskih sustava. SUBP je prilično složen sustav koji u sebi sadrži različite aspekte koji mu omogućuju efikasan rad. S mnogim od tih aspekata, koji se javljaju u većini danas poznatih SUBP, student će se upoznati tijeklom ovog kolegija. Ovaj kolegij nije korsitan samo onima koji se kane baviti razvojem SUBP, jer se pretpostavlja da je takvih ipak u populaciji studenata manje, nego svima onima koji žele kvalitetno koristiti neki od postojećih SUBP, jer im omogućuje da razumiju mogućnosti i ograničenja sustava s kojim rade, a koja su dana zbog objektivnih teorijskih poteškoća, kao i kritike sustava u kojem rade zbog neadekvatnih rješenja koja taj sustav nudi, te izbor za njihovu potrebu najboljeg SUBP. Također, kolegij ima i druge ciljeve. Studentima koji se kane baviti znanstvenim radom na polju informacijskih znanosti, a posebice na polju baza podataka, daje drugi i drugačiji uvid u svijet baza podataka, njegovu nižu, fizičku razinu, te algoritme koji omogućuju deklarativni rad koji je danas kod SUBP-a uobičajen.

Nastava

Predavanje
30sati
Vježbe (jezici, tzk)
30sati

Ishodi učenja predmeta

  • Dizajniranje efikasne baze podataka korištenjem adekvatne organizacije objekata baze podataka
  • Optimiziranje rada baze podataka izborom efikasne organizacije fizičkih objekata baze podataka
  • Optimiziranje rada baze podataka izborom efikasnog sustava zaključavanja i pisanjem transakcija koje izbjegavaju zastoja sustava zbog međusobnog zaključavanja
  • Razumijevanje tehnika i algoritama rada sustava za upravljanje bazama podataka
  • Razumijevanje tehnika zaštite baze podataka od pada sustava i oporavka baze podataka, te dizajn efikasne strategije zaštite baze podataka od pada sustava
  • Sudjelovanje u pobljšanju i izradi novih svojstava otvorenih sustava za izgradnju baza podataka

Ishodi učenja programa

  • Izgraditi i optimizirati bazu podataka i bazu znanja primjenom odgovarajućih strategija organizacije podataka i sigurnosti informacijskog sustavaIzgraditi i optimizirati bazu podataka i bazu znanja primjenom odgovarajućih strategija organizacije podataka i sigurnosti informacijskog sustava
  • Izgraditi informacijski sustav temeljen distribuiranim komponentama kao i na autonomnim i međusobno kompetitivnim izvorima znanja i razriješiti konflikte koji se javljaju među izvorima znanjaIzgraditi informacijski sustav temeljen distribuiranim komponentama kao i na autonomnim i međusobno kompetitivnim izvorima znanja i razriješiti konflikte koji se javljaju među izvorima znanja
  • Modelirati raspodjelu podataka prema mjestu korištenja podataka, izgraditi sustav replikacije baze podataka i izgraditi distribuiranu bazu podatakaModelirati raspodjelu podataka prema mjestu korištenja podataka, izgraditi sustav replikacije baze podataka i izgraditi distribuiranu bazu podataka

Sadržaj predavanja

  • Uvod
    Pojam SUBP. Povijesni razvoj SUBP. Fizička, konceptualna i vanjska razina SUBP. Jezici za rad s bazama podataka. Relacijski model. Tablice i atributi.
  • Diskovi i datoteke
    Upravljanje prostorom na disku. Upravljanje spremnicima. Zapisi. Zapisi fiksne i varijabilne duljine. Stranice. Stranice varijabilne i fiksne duljine. Datoteke. Indeksi. Sistemski katalozi SUBP. Sortiranje u sekundarnoj memoriji. Sortiranje spajanjem i ocjena složenosti.
  • Organizacija datoteka i objekata baze podataka
    Heap datoteke. Sortirane datoteke. Hash datoteke. Izbor sustava datoteka. Reprezentacija relacijskih objekata. Zapisi. Zapisi fiksne duljine. Zaglavlja zapisa. Blokovi. Zapisi varijabilne duljine. Promjene na zapisima.
  • Linearni indeksi
    Sekvencijalne datoteke. Gusti i rijetki indeksi. Primarni isekundarni indeksi. Kompozitni indeksi. Indeski s udvostručenim ključevima. B+-tree indeksi. Organizacija B-tree indeksa. Pretraživanje B+-tree indeksa. Dodavanje vrijednosti u B+-tree indeks. Brisanje vrijednosti iz B+-tree indeksa. Ocjena složenosti operacija u B+tree indeksu.
  • Indeski temeljeni na Hash tablicama
    Indeksi bazirani na Hash tablicama. Statičko hashiranje. Proširivo hashiranje. Dodavanje u proširivu Hash tablicu. Brisanje iz proširive Hash tablice. Ocjena složenosti operacija na proširivom Hash indeksu. Linearno hashiranje. Dodavanje elemenata u linearnu Hash tablicu. Brisanje elemenata iz linearne hash tablice. Ocjena složenosti operacija na linearnoj Hash tablici.
  • Indeksi za višedimenzionalne podatke
    Kocke podataka. Grid datoteke. Pretraživanje grid datoteka. Ubacivanje vrijednosti u Grid datoteke. Ocjena složenosti operacija na Grid datotekama. R-stabla. Operacija na R-stablima. Ocjena složenosti operacija nad R-stablima. Indeksne bitmape.
  • Upiti
    Relacijska algebra. Operatori selekcije, projekcije, prirodnog spoja, Θ-spoja. Kartezijski produkt. Skupovni operatori – unija, razlika, presjek. Eliminacija višestrukih redaka. Grupiranje i agregacija. Sortiranje. Pregledavanje tablice. Sortiranje tijekom pregledavanja. Složenost pregledavanja.
  • Upiti (cont.)
    Jednofazni algoritmi za relacijske operatore. Selekcija slučaj – bez indeksa, nesortirani podaci. Selekcija – bez indeksa, sortirani podaci. Selekcija – B+-tree indeks. Selekcija – hash indeks. Projekcija bazirana na sortiranju. Projekcija bazirana na hashiranju. Projekcija i indeksi.
  • Upiti (cont.)(2)
    Prirodni spoj – ugnježdene petlje. Spoj pomoću sortiranja spajanjem. Spoj pomoću hashiranja. Unija i razlika pomoću sortiranja. Unija i razlika pomoću hashiranja. Dvofazni algoritmi temeljeni na sortiranju. Dvofazni algoritmi temeljeni na hashiranju. Algoritmi temeljeni na indeksima. Višefazni algoritmi
  • Optimizacija i prevođenje upita
    Parsing upita. Sintaksna analiza. Stabla prijevoda. Planovi upita. Zakoni poboljšanja upita. Zakoni komutativnosti i asocijativnosti. Zakoni za selekciju. Odgurivanje selekcija. Zakoni za spojeve i produkte. Zakoni za izbacivanje duplih redaka. Zakoni vezani uz grupiranje i agregaciju.
  • Optimizacija upita (cont.)
    Unaprjeđivanje plana upita. Grupiranje asocijativnih i kumulativnih operatora. Statistika vođena od SUBP. Procjena cijene plana. Procjena veličine izlaza. Procjena veličine međurezultata. Procjena veličine projekcije. Procjena veličine selekcije. Procjena veličine spoje. Spojevi s više uvjeta. Spojevi većeg broja relacija.Procjena drugih operatora.
  • Optimizacija upita (cont.)(2)
    Heuristike za smanjenje cijene plana. Lijevi i desni argument spoja i njihova razlika. Stabla spajanja. Algoritam za optimizaciju redoslijeda spajanja temeljen na dinamičkom programiranju. Algoritam za optimizaciju redoslijeda spajanja temeljen na metodi pohlepe. Kreiranje završnog plana upita. Odabir metode selekcije. Odabir metode spajanja. Prosljeđivanje za unarne operatore. Prosljeđivanje za binarne operatore.
  • Konkurentnost u SUBP
    Koncept transakcija. Serijski i serijalizabilni planovi. Zaključavanje. Implementacija zaključavanja i otključavanja. Deadlockovi. Razrješavanje deadlockova pronalaženjem ciklusa u usmjerenom matematičkom grafu. Prevencija deadlockova. Problem livelockova. Planiranje zaključavanja. Dvofazno zaključavanje. Dijeljeni i ekskluzivni ključevi. Inkrementalni ključevi. Problem fantomskih zapisa.
  • Konkurentnost u SUBP (cont.)
    Kontrola konkurentnosti u stablastim indeksima. Osiguravanje konkurentnosti pomoću vremenskih znamki i snimaka baze podataka. Problem prljavih podataka. Povezivanje zaključavanja i vremenskih znamki. Tranaskcije koje čitaju nepotvrđene podatke. Serijalizabilnost pogleda. Razrješavanje deadlockova pomoću vremenskih znamki. Vrlo dugačke transakcije. Problemi dugačkih transakcija. Sage. Kompenzacija transakcija.
  • Oporavak od pada sustava
    Logovi. Druge strukture podataka za oporavak baze podataka. Protokol logiranja pisanjem unaprijed. Rad s kontrolnim točkama. Faza analize. Faza ponavljanja transakcija. Faza brisanja nezavršenih transakcija. Oporavak medija. Zrcaljenje medija. RAID5 diskovi.

Sadržaj seminara/vježbi

  • Seminari
    Seminarski radovi iz ovog kolegija obrađuju nove metode koje se javljaju u SUBP-ovima, te nepokrivena područja vezana uz tematiku. Također, oni mogu biti vezani uz kritiku načina implementacije pojedinih teorijskih koncepata kod SUBP s kojim se studenti koriste. Ovaj samostalni rad studenata vrlo je bitan kako bi studenti stekli pojam o području, o stvarnom SUBP i o razlikama između teorijskih načela i prakse. Stoga seminarski radovi znatno utječu na studentovu krajnju ocjenu iz kolegija.
  • Vježbe
    Laboratorijske vježbe iz ovog kolegija temelje se na izgradnji pojedinih algoritama vezanih uz baze podataka u programskom jeziku

Osnovna literatura

  • Ramakrishnan, R. Database Management Systems. McGraw-Hill, 1998.
  • Garcia-Molina, H.; Ullman, J.D.; Widom, J.: Database System Implementation. Prentice-Hall, 2000.

Dopunska literatura

  • Ullman, J.D.; Widom, J. First Course in Database Systems. Prentice-Hall, 2001.
  • Atzeni, P.; De Antonellis, V. Relational Database Theory. The Benjamin/Cummings, 1993.
  • Aho, A.; Hopcroft, J.; Ullman, J.D. Algorithms and data structures. Addison-Wesley, 1983.
  • van Leeuwen, J. Handbook of Theoretical Computer science. Elsevier and MIT Press, 1990.
  • Knuth, D.E. The art of Computer programming: Searching and Sorting. Addison-Wesley, 1973.

Slični predmeti

Nastavnik Oblik nastave Tjedana Sati tjedno Grupa
Lovrenčić Alen Predavanje 15 2 1
Schatten Markus Laboratorijske vježbe 15 2 1
Nema definiranih ispitnih rokova
Predavanje Seminar Auditorne vježbe Laboratorijske vježbe Vježbe (jezici, tzk) Ispit Kolokviji Nadoknade Demonstrature
Copyright © 2015 FOI Varaždin. All Rights Reserved. Sva prava pridržana.
Povratak na vrh