Logo Uni Logo FMFI Comenius University > Faculty of Mathematics, Physics and Informatics > Department of Computer Science

Dr. Tomas Plachetka


Research
Teaching
Publications
Contact

Uvod do databazovych systemov 2008/2009 Zima

Oznamy

  • Skuska prebieha formou dvoch pisomnych testov, "zapoctoveho" (temy z cviceni) a "skuskoveho" (temy z prednasky a cviceni). Podmienkou prihlasenia sa na "skuskovy" test je uspesne absolvovanie "zapoctoveho" testu (aspon 40%). Na test (okrem 16.12.2008) sa treba vopred elektronicky prihlasit. Ak sa Vam z nejakeho dovodu nedari prihlasit, obratte sa prosim cez email na spravcu systemu a kopiu spravy (CC) poslite mne. Prihlasenie na test je zavazne. Termin, na ktory ste prihlaseny, sa Vam pocita aj ked ten test nepisete. Ak viete ze na termin nepridete, prosim odhlaste sa z neho (ak je uz po uzavierke a system Vam nedovoli sa odhlasit, dajte mi vediet cim skor cez email).
  • Na test treba priniest index, ISIC kartu, dostatok cistych papierov a pero. Ziadne ine pomocky nie su dovolene. Vsetky elektronicke zariadenia, vratane mobilnych telefonov, budu pocas testu vypnute. Opisovanie, akakolvek komunikacia pocas testu alebo iny pokus o podvod znamena neuspesne absolvovanie kurzu (Fx). Jedinou vynimkou je komunikacia s ucitelom za ucelom upresnenia zadania ulohy.
  • Formula pre vypocet znamky ma 2 parametre, pz (percentualna uspesnost v zapoctovom teste) a ps (percentualna uspesnost v skuskovom teste) je implementovana ako program v jazyku C. Na ziskanie hodnotenia aspon E musi platit
    (pz >= 40) && (ps >= 40) && (pz + ps >= 100).
  • Planovane terminy testov:
  • Pri celkovom hodnoteni sa beru do uvahy len bodove zisky z posledneho zapoctoveho resp. skuskoveho testu.
  • Dohromady je mozne pisat maximalne 4 testy. Prirodzene, nie je nutne vycerpat vsetky pokusy - zapoctovy aj skuskovy test staci pisat len raz (oba dostatocne dobre).
  • Zverejnene vysledky mozu byt este mierne korigovane, ale nikdy nie v neprospech studenta - s vynimkou reklamacie. Ak ma niekto pocit, ze jeho test bol ohodnoteny nekorektne (t.j. niekto ziskal menej bodov ako mal), moze poziadat o opatovnu korekciu svojho testu (poslat mi email). Pri reklamacii sa zabudne a znovu vyhodnoti cely reklamovany test (t.j. nielen jeden reklamovany priklad). Zbytocna reklamacia moze viest k miernemu znizeniu vysledku testu (aktualneho, pripadne aj nasledujuceho). Naopak, odhalenie chyby vo vzorovom rieseni niektoreho z testov (z 2008/2009) moze byt mierne honorovane.

Prednaska

T. Plachetka
  • Streda 9:50 2h B (*)
  • Uvodna prednaska 24/9/2008
    • Organizacia kurzu
    • Knihy, casopisy, konferencie
    • Ucel databaz, charakteristika DB aplikacii
    • Trojstupnova ANSI/SPARC architektura, koncepcne datove modely
    • Entitno-relacny, relacny a navigacny datovy model
  • Dotazovacie jazyky (kalkul, Datalog, SQL), 1/10/2008
    • Relacie a predikaty
    • Dotazy
    • Relacny kalkul
    • Datalog
    • SQL ("kanonicka" forma vznikajuca prekladom z Datalogu)
  • Viac o SQL, 8/10/2008
    • DDL (Data Definition Language) a DML (Data Manipulation Language)
    • DML: Syntax a semantika SELECT
    • SELECT: selekcia, projekcia, premenovanie, ORDER BY, UNION/INTERSECT/EXCEPT, INNER JOIN, OUTER JOIN, NULL hodnoty a 3-hodnotova logika, poddotazy, GROUP BY/HAVING, duplikaty v tabulkach
    • DDL: typy/DOMAIN, vytvorenie/odstranenie/modifikacia tabulky, default hodnoty, indexy, VIEW, aktualizacia cez VIEW
  • Relacna algebra, 15/10/2008
    • Zakladne operatory nad mnozinami
    • Niektore zakony relacnej algebry
    • Optimalizacia na urovni relacnej algebry
    • Multimnoziny (bags) a operatory nad multimnozinami
    • Grupovanie a agregacia
    • Semantika SELECT... FROM... WHERE... GROUP BY... HAVING
  • Agregacia a rekurzia v dotazovacich jazykoch, 22/10/2007
    • Grupovanie a agregacia v SQL, relacnej algebre, relacnom kalkule a Datalogu
    • Rekurzia v SQL, relacnej algebre, relacnom kalkule a Datalogu
    • Vypocet pevneho bodu: iteracia (naivna evaluacia, delta-optimalizacia)
    • Magicka transformacia
    • Stratifikovana negacia
    • Vypoctova sila dotazovacich jazykov
    • Simulacia rekurzie s fixnou hlbkou v SQL bez WITH RECURSIVE
  • Navrhovanie databaz, 29/10/2008
    • Ciel a metodologia navrhovania databaz
    • Entitno-relacne diagramy, pravidla dobreho navrhu, primary keys, surrogate keys, foreign keys
    • Preklad ER diagramov do SQL (DDL)
    • Identifikacia funkcnych zavislosti
  • Funkcne zavislosti, 5/11/2008
    • Motivacia normalizacie
    • Funkcne zavislosti, Armstrongove axiomy
    • Uzaver mnoziny atributov, uzaver mnoziny funkcnych zavislosti
    • Uplnost Armstrongovych axiom
    • Pokrytie a minimalne pokrytie mnoziny funkcnych zavislosti
    • Nadkluce a kluce
    • Relacne schemy, dekompozicia relacnych schem, bezstratovost dekompozicie
  • Normalne formy, 12/11/2008
    • Algoritmus testovania bezstratovosti dekompozicie do 2 relacii
    • Algoritmus testovania bezstratovosti dekompozicie pdo N relacii
    • Prva, druha a tretia normalna forma (1NF, 2NF, 3NF), BCNF
    • Naivna dekompozicia do 3NF, resp. BCNF
    • Bezstratova dekompozicia do 3NF zachovavajuca funkcne zavislosti
    • Bezstratova dekompozicia do BCNF z 3NF dekompozicie
    • Vyssie normalne formy, pravidla rozumnej dekompozicie
  • Transakcie, 19/11/2007
    • Definicia transakcie z pohladu centralizovaneho transakcneho systemu
    • Elementarne transakcne operacie
    • Poziadavky na transakcny system (ACID)
    • Architektura transakcneho databazoveho systemu
    • Rozvrhy
    • Seriove a konflikt-seriovatelne rozvrhy
    • Testovanie konflikt-seriovatelnosti, precedencny graf
    • View-seriovatelne rozvrhy
    • Generovanie seriovatelnych rozvrhov
    • Zamykanie, dvojfazove zamykanie
    • Generovanie seriovatelnych rozvrhov
  • Transakcie, 26/11/2008, 3/12/2008
    • Dvojfazove zamykanie, casove peciatky, validacia, MVCC
    • Obnova (recovery), log-file
    • Vseobecny dvojprechodovy algoritmus obnovy, algoritmy obnovy so specifickymi predpokladmi
    • Checkpointing
    • Backup
    • Triedy obnovitelnosti: recoverable, ACA, strict
    • Diagram hierarchie tried obnovitelnosti a seriovatelnosti
    • Striktne dvojfazove zamykanie
    • Deadlock, wait-for-graf, pristupy k rieseniu deadlockov
    • Konzervativne strategie riesenia deadlockov: wait-die a kill-wait
  • Fyzicka organizacia, 10/12/2008
    • Typy externych (trvacnych) medii
    • Fyzicka algebra, fyzicke plany
    • Zlozitost fyzickych operatorov
    • Vybrane operatory: Merge-sort, Nested-loop-join
    • Sekvencne indexy (ISAM)
    • Husty a riedky sekvencny index, operacie vynechavania a vkladania
  • Fyzicka organizacia, 17/12/2008
    • B stromy a B+ stromy, operacie vynechavania a vkladania
    • Rozsiritelne hashovanie, linearne hashovanie
    • Cena reorganizacie indexov

Starsia (uplnejsia a v podstatnych veciach presnejsia) verzia tohto kurzu: RNDr. J. Sturc

Cvicenia

E. Macajova, S. Miklik, M. Pastorova, T. Plachetka

Prakticke cvicenia

Co treba urobit ako prve:
  • Prihlasit sa na PC v terminalke. Autentifikaciu robi univerzitny informacny system.
  • Urobit ssh na pocitac cvika (cvika.dcs.fmph.uniba.sk). To znamena pod Linuxom otvorit terminalove okno a urobit
    ssh username@cvika, pod Windowsami treba pouzit putty. (V tomto okne sa odohrava vsetko ostatne.) Username je identicky s username v terminalke (napr. plachetka1). Heslo vie cviciaci.
  • Zmenit svoje heslo na pocitaci cvika. To sa robi prikazom
    passwd.
  • Prihlasit sa do Postgresql. To sa robi tak, ze sa spusti (na pocitaci cvika)
    psql. Heslo vie cviciaci.
  • Zmenit svoje heslo na Postgresql. To sa robi v psql prikazom
    alter user username with encrypted password 'nove_heslo';
  • Zavriet psql (Ctrl-D). Vyrobit vo svojom home directory subor .pgpass s pravami na citanie/zapis LEN pre seba (to je dobre na to, aby psql uz nikdy nepytal password po naslednom spusteni. To sa robi (copy-paste na pocitaci cvika) takto:
    echo "*:*:*:${USER}:nove_heslo" > ~/.pgpass; chmod 600 ~/.pgpass; clear
    (kde nove_heslo je to iste heslo ako v "alter user").
Co treba urobit ako druhe:
  • Spustit znovu
    psql
    (tentokrat by psql uz nemal pytat heslo - ak pyta, treba este raz pozorne sledovat predosly navod)
  • Oboznamit sa s prostredim interpretera psql. Tu je niekolko tipov (vyskusajte):
    • \? vypise zoznam vsetkych shell-commands
    • \c vypise info o pripojeni k databaze (standardne ste pripojeni k svojej vlastnej databaze, ktora ma rovnake meno ako je vas username)
    • \d vypise zoznam tabuliek v databaze
    • \d emp vypise strukturu tabulky emp (podobne sa viete pozriet na strukturu ostatnych tabuliek)
    • \q ukonci session
  • Oboznamit sa s obsahom troch standardnych tabuliek v svojej databaze (vyskusajte):
    • select * from emp;
    • select * from dept;
    • select * from salgrade;
Co treba urobit ako tretie: CVICIT PISANIE DOTAZOV V SQL (nad databazou "emp")
  • Na pocitaci cvika, skopirovat file queries_emp.sql do svojho home-directory:
    cp ~plachetk/pub/queries_emp.sql ~
  • Otvorit 3 okna (terminalove sessions) na pocitaci cvika. V OKNE1 bude (stale) bezat psql, v OKNE2 oblubeny editor (napriklad joe) a v OKNE3 shell (bash). Ideou je, ze do editovaneho suboru queries_emp.sql v OKNE2 pisete SQL dotazy (zmeny ulozite postupnym stlacenim "CTRL+K D") a v OKNE3 ten editovany subor spustate prikazom
    psql -f queries_emp.sql
    OKNO1 sluzi na to, aby ste vedeli empiricky overit spravnost vysledkov dotazov.
  • Trenovat pisanie dotazov v SQL, t.j. pokracovat vo vyplnani queries_emp.sql tak ako je naznacene na zaciatku. Tu je zoznam uloh v queries_emp.sql (kliknutim na stranky ostatnych cviciaci ziskate dalsie). Nepovinne ulohy (ktore mozno vyzaduju studium manualu) su oznacene kurzivou. Tazsie (ale doporucene) ulohy su oznacene tucnym pismom. Pri tazsich dotazoch moze byt dobrou pomockou formulacia dotazu v Datalogu a nasledny preklad do SQL podla navodu z prednasky.
    • Print all jobs (each job once).
    • Print names and jobs of employees with salary at least 2000.
    • Print names and jobs of employees who work in department 30.
    • Print the number of department in which the president works.
    • Print names of employees who were hired between 1 September 1981 and 31 October 1981.
    • Print names and salaries of managers, sort the output in the descending order of salaries.
    • Print names, brutto incomes, national insurance contributions, income taxes and netto incomes of employees (subtract 13.4% for national insurance and 19% for income tax).
    • Print names and the number of working years (since hired) of all employees.
    • Print names of all employees with the first letters of their department names.
    • Print name and "total salary" (total salary = salary + comm) of each employee. (Warning: the column comm may contain NULL values.)
    • Print jobs of employees who work in Chicago.
    • Print tuples [Name, City, Coworker] which stand for all employees, their working places and names of their co-workers (employees who work in the same department).
    • Print names, department names and salaries of all employees whose salaries are greater than the lowest salary in department 20.
    • Print names of employees together with names of their managers.
    • Which departments contain all job positions?
    • Which departments are empty (have no employees)?
    • Which employees manage only clerks?
    • Which departments employ no salesmen?
    • Find names of all employees who are subsidiaries of Blake - both direct and indirect subsidiaries. (This query is a tricky one, skip it unless you understand what precisely you are doing.)
Tu je instalacny script databazy EMP pre PostgreSQL.

Co treba urobit ako stvrte: CVICIT PISANIE DOTAZOV V DATALOGU (nad databazou "pijani")
  • Na pocitaci cvika, skopirovat subory pijani.pl, subtotal.pl, query.pl, queries_pijani.pl do svojho home-directory:
    cp ~plachetk/pub/pijani.pl ~
    cp ~plachetk/pub/subtotal.pl ~
    cp ~plachetk/pub/query.pl ~
    cp ~plachetk/pub/queries_pijani.pl ~
  • Otvorit 3 okna (terminalove sessions) na pocitaci cvika. V OKNE1 bude stale bezat "joe pijani.pl" (tento subor netreba editovat, tam je vidiet obsah databazy), v OKNE2 bude stale bezat "joe queries_pijani.pl" (tam treba pisat dotazy) a v OKNE3 bude stale bezat "pl -s queries_pijani.pl". Ideou je, ze do editovaneho suboru queries_pijani.pl v OKNE2 pisete Datalogove dotazy (zmeny ulozite postupnym stlacenim "CTRL+K D") a v OKNE3 dotazy spustate prikazmi
    make.
    "make." skompiluje subor queries_pijani.pl (ktory samozrejme treba najskor ulozit, ked v nom urobite zmeny), a potom sa za ten otaznik daju pisat dotazy ako napriklad
    q(lubi(P, A)).
    atd.
    predikat "q(_)" sluzi na pekne formatovanie vystupu a eliminaciu "duplikatov" (ktore v skutocnosti nie su duplikatmi, len tymi istymi viacnasobne najdenymi N-ticami)
    OKNO1 sluzi na to, aby ste vedeli empiricky overit spravnost vysledkov dotazov.
  • Trenovat pisanie dotazov v Datalogu, t.j. pokracovat vo vyplnani queries_pijani.pl tak ako je naznacene na zaciatku.
Datalog (SWI-Prolog) si viete instalovat aj na svojom lokalnom pocitaci (Windows, Linux, MacOS).

Literatura

Niektore z nasledujucich knih su k dispozicii k prezencnemu studiu vo fakultnej kniznici (pavilon informatiky, budova vpravo od vchodu).


Updated by Tomas Plachetka, Jan/29/2009