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 2011/2012 Zima

Oznamy (tie najviac aktualne su na prvych miestach)

  • Terminy pisomnych testov (na termin sa treba vopred elektronicky prihlasit):
  • V stredu 14.12. je posledna prednaska v tomto semestri.
  • V pondelok 12.12. o 14:00 v poslucharni A je zapoctovy test, ktory je povinny pre vsetkych. Nemusite sa nan prihlasovat, - ale treba mi dat cez email vediet, ak z nejakych dovodov test pisat nemozete.
    • Viacej nez 84% znamena znamku A bez dalsieho skusania.
    • 40%-84% znamena, ze nemusite pisat opravny zapoctovy test v januari a mate teda narok na 3 skuskove testy (ktore doporucujem nevycerpat vsetky).
    • Menej nez 40% znamena, ze vysledok tohto testu sa ignoruje a platia bezne pravidla (t.j. mate narok na max. 4 terminy, z toho max. 2 zapoctove, pricom tento decembrovy test sa medzi ne nepocita). Ale pozor, v januari budu uz len 2 zapoctove terminy (v prvej polovici januara).
    • Vopred nezdovodnena neucast na teste 12.12. znamena stratu jedneho terminu.
  • 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.
  • 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 sa treba vopred elektronicky prihlasit. Ak sa Vam z nejakeho dovodu nedari prihlasit, poslite mi email. 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 mate problem s odhlasenim, dajte mi vediet cim skor cez email).
  • Pri celkovom hodnoteni sa beru do uvahy len bodove zisky z posledneho zapoctoveho resp. skuskoveho testu. 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).
  • Maximalne je mozne pisat 4 testy, z toho maximalne 2 zapoctove. 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.
  • V tyzdni 17.-21. 10. pobezia (len) prakticke cvicenia v terminalkach M217 a M218. Tip: ak mate vlastny pocitac, instalujte si SWI-Prolog, vytvorte nejaku EDB a vyskusajte napisat a zbehnut par dotazov.
  • Ak ste studentom tohto kurzu, prihlaste sa do rozvrhovacieho systemu cviceni, zmente svoje heslo (zvolte si heslo, ktore nezabudnete) a najdite svoj rozvrh pre teoreticke a prakticke cvicenia. Ak ste spokojny so zaradenim do skupiny, nerobte nic. Ked je to nutne, tak skupinu zmente. Prihlasovacie meno (login) je Vase priezvisko (ASCII), vsetky pismena male; pociatocne heslo je zhodne s prihlasovacim menom. Ak neviete ako sa prihlasit, alebo ak sa Vam to nedari, dajte mi vediet cez email. Tiez mi prosim dajte vediet, ak v systeme objavite nejaku chybu.

Prednaska

T. Plachetka: Streda 11:30, 2h, B

  • Uvodna prednaska 21/9/2011
    • 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)
    • Relacie a predikaty
    • Dotazy
    • Relacny kalkul
    • Datalog
    • SQL ("kanonicka" forma vznikajuca prekladom z Datalogu)
  • Viac o SQL
    • 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
    • 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
    • Grupovanie a agregacia v SQL, relacnej algebre, relacnom kalkule a Datalogu
    • Rekurzia v SQL, relacnej algebre, relacnom kalkule a Datalogu
    • Vypocet dotazov: iteracia (naivna a seminaivna evaluacia)
    • Magicka transformacia
    • Stratifikovana negacia
    • Vypoctova sila dotazovacich jazykov
    • Simulacia rekurzie s fixnou hlbkou v SQL bez WITH RECURSIVE
  • Navrhovanie databaz
    • 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
    • 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
    • Algoritmus testovania bezstratovosti dekompozicie do 2 relacii
    • Algoritmus testovania bezstratovosti dekompozicie do 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
    • 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
    • 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
    • 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
    • B stromy a B+ stromy
    • Rozsiritelne hashovanie, rozsiritelne hashovanie
    • Cena reorganizacie indexov

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

Cvicenia

M. Pastorova, T. Plachetka, M. Sladek

Teoria

DB1 Str 14:50 M-VI (TP), DB2 Str 17:20 M-VI (MS), DB3 Stv 8:10 M-VII (MP), DB4 Stv 9:50 M-VII (MP). Viacej informacii o rozvrhu: rozvrhovaci system cviceni.

Tu su zadania a riesenia niektorych "rozcvickovych" uloh.

Praktikum

DB1A Str 14:50 M-217, DB1B Str 14:50 M-218, DB2A Str 17:20 M-217, DB2B Str 17:20 M-218, DB3A Stv 8:10 M-217, DB3B Stv 8:10 M-218, DB4A Stv 9:50 M-217, DB4B Stv 9:50 M-218. Viacej informacii o rozvrhu: rozvrhovaci system cviceni.

Co treba urobit ako prve: NAKONFIGUROVAT PROSTREDIE
  • 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.dcs.fmph.uniba.sk, pod Windowsami treba pouzit putty. V tomto okne sa odohrava vsetko ostatne (a je lepsie otvorit ca. 3 take okna). Username a heslo su identicke s tymi v terminalke.
Co treba urobit ako druhe: OBOZNAMIT SA S DATABAZOU EMP
Co treba urobit ako tretie: CVICIT PISANIE DOTAZOV V DATALOGU (nad databazou EMP)
  • Na pocitaci cvika, skopirovat subory emp.pl, subtotal.pl, query.pl, queries_emp.pl do svojho home-directory:
    cp ~plachetk/pub/emp.pl ~
    cp ~plachetk/pub/subtotal.pl ~
    cp ~plachetk/pub/query.pl ~
    cp ~plachetk/pub/queries_emp.pl ~
  • Mat otvorene 3 okna (terminalove sessions) na pocitaci cvika. V OKNE1 bude stale bezat "joe emp.pl" (tento subor netreba editovat, tam je vidiet obsah databazy), v OKNE2 bude stale bezat "joe queries_emp.pl" (tam treba pisat dotazy) a v OKNE3 bude stale bezat "swipl -s queries_emp.pl". Ideou je, ze do editovaneho suboru queries_emp.pl v OKNE2 pisete Datalogove dotazy (zmeny ulozite postupnym stlacenim "CTRL+K D") a v OKNE3 ich kompilujete prikazom
    make.
    "make." skompiluje subor queries_emp.pl (ktory samozrejme treba najskor ulozit, ked v nom urobite zmeny), a potom sa za ten otaznik daju pisat dotazy ako napriklad
    ?- q(jobs(J)).
    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_emp.pl tak ako je naznacene na zaciatku.
  • Negacia sa pise ako \+, definicia sa pise ako :-.

Datalog (SWI-Prolog) si viete instalovat aj na svojom domacom pocitaci.

Co treba urobit ako stvrte: 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. Na cviceni treba vyriesit aspon jeden "lahky" a aspon jeden "tazky" dotaz:
    • 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 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 of employees together with names of their managers.
    • Print names, department names and salaries of all employees whose salaries are greater than the lowest salary in department 20.
    • 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.)
    • 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.)

Tu je instalacny script databazy EMP pre PostgreSQL, ktory si viete instalovat aj na svojom domacom pocitaci.


Co dalej: CVICIT PISANIE SUBTOTALOVYCH DOTAZOV V DATALOGU A V SQL (nad databazou EMP)
  • Skopirovat navyse subory queries_emp_sub.pl a queries_emp_sub.sql do svojho filesystemu, pisat subtotalove dotazy a testovat ich vystupy sposobom popisanym vyssie:
    • Find average salary of employees who work in Dallas.
    • For each department (including departments with no employees), find the sum of salaries of employees who work in that department.
    • Find departments (deptno) with more than 3 employees.
    • For each department, find the number of analysts who work in that department (the result consists of tuples [D, N]).
    • Find the job position(s) with the maximal standard deviation of salaries.
    • Find tuples [Deptno, Job, Sum, Average] which for each [Deptno, Job] state the sum of salaries and average salary of employees who work in department Deptno and do job Job.
    • Datalog only: For each employee, find the number of subsidiaries (direct and indirect) of that employee. Include employees with no subsidiaries. (This query is a tricky one, skip it unless you understand what precisely you are doing.)
  • Testovat (nad databazou EMP, pripadne nejakou vlastnou) dotazy, ktorych vysledkom ste si nie celkom isti.

Literatura

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


Updated by Tomas Plachetka, Feb/9/2012