DBS Flashcards

Question

CROSS JOIN

Answer 1

CROSS JOIN Udělá kartézský součin: spojí každý řádek z tabulky1 se všemi řádky tabulky2. Výsledná tabulka má počet řádků = počet řádků t1 × počet řádků t2. Příklad: t1: [a], [b], [c] (3 řádky) t2: [1], [2] (2 řádky) Výsledná t3: (a,1), (a,2), (b,1), (b,2), (c,1), (c,2)

Answer 2

NATURAL JOIN Spojí řádky z t1 a t2 jen tam, kde mají stejné hodnoty ve společných sloupcích (automaticky podle názvů sloupců). Výsledná tabulka obsahuje pouze společné řádky. Příklad: t1: (id=1, jmeno='A') t2: (id=1, vek=20) Výsledná t3: (id=1, jmeno='A', vek=20)

Answer 3

INNER JOIN Všechny shody podle podmínky. SELECT * FROM t1 INNER JOIN t2 ON t1.id = t2.id; Příklad: t1: (id=1, jmeno='A'), (id=2, jmeno='B') t2: (id=2, vek=30) Výsledek: (id=2, jmeno='B', vek=30)

Answer 4

Všechny řádky a sloupce z t1 a pokud existuje schodna hodnota ve spolecnem sloupci, tak se rozsiri o hodnoty sloupcu t2, jinak NULL Tedy vezme to celou tabulku t1 (ZLEVA) a zprava na ni nalepi t2 a rozsiri ji o rozmery t1. Schodne sloupce se doplni o hodnoty t2, jinak jsou tam vsude NULL. SELECT * FROM t1 LEFT JOIN t2 ON t1.id = t2.id; Příklad: t1: (id=1, jmeno='A'), (id=2, jmeno='B') t2: (id=2, vek=30) Výsledek: t3: (id=1, jmeno='A', vek=NULL) (id=2, jmeno='B', vek=30) Tedy obecne rozsirim t1 o sloupce t2 a pokud je schoda tak dobry, pokud neni schoda tak rozsirim o NULL

Answer 5

jenom spoji t1 a t2 UPLNE DOHROMADY - nejdriv da celou t1 (jako sloupce a radky) a rozsiri je o NULL sloupce t2 - pak prida NULL radky t2 a zaplni je hodnotami sloupcu t2 t3 tedy ma t1+t2 radku a t1+t2 sloupcu. Je to jaksi krizem t1 | NULL NULL | t2

Answer 6

SELECT _ FROM _ WHERE - mi vybere tmp tabulku vsech odpovidajicich hodnot GROUP BY - ji rozdeli na skupiny (groups) podle stejnosti nejakych hodnot - treba podle nejakych poctu HAVING - filtrace jiz uskupenych zaznamu How many flights does each company have scheduled? ▪ However, we are not interested in flights to Stuttgart and Munich ▪ As well as we do not want companies with just one flight or less SELECT Company, COUNT(*) AS Flights FROM Flights WHERE (Destination NOT IN ('Stuttgart', 'Munich')) GROUP BY Company HAVING (Flights > 1)

Answer 7

Find basic characteristics for all the scheduled flights ▪ I.e. return the overall number of flights, the overall number of the involved companies, the sum of all the passengers, the average / minimal / maximal number of passengers SELECT COUNT(*) AS Flights, COUNT(DISTINCT Company) AS Companies, SUM(Passengers) AS PSum, AVG(Passengers) AS PAvg, MIN(Passengers) AS PMin, MAX(Passengers) AS PMax FROM Flights

Answer 8

UNION - sjednoceni dvou tabulek bez dupliaktu UNION ALL - sjednoceni dvou tabulek s duplikaty INTERSECT - prunik tabulek EXCEPT - rozdil tabuelk

Answer 9

Razeni navracene tabulky podle urciteho sloupce ASC nebo DESC

Answer 10

Pouziti jako mezi-vysledek pro pomocny vypocet, kdy neni treba uchovavat informaci, protoze se k ni umime dostat vnorenym querym Ulehcuje uchovavani mezi-vypoctu Find all the scheduled flights which have higher than average number of passengers. SELECT * FROM Flights WHERE (Passengers > (SELECT AVG(Passengers) FROM Flights)) SELECT Flights.*, ( SELECT COUNT(*) FROM Aircrafts AS A WHERE (A.Company = F.Company) AND (A.Capacity >= F.Passengers) ) AS Aircrafts FROM Flights AS F Tedy vybery vsechno z tabulky Flights A NAVIC K TOMU PRIDAM POCET, ten pocet ale musim ziskat jako pomocny vypocet - query

Answer 11

View - pojmenovany SELECT query - tedy je to pro caste pouzivane slozite query dotazy - vytvori se jakasi virtualni tabulka, ktera fyzicky neni v db, ale muzeme ji dynamicky upravovat - bezpecnostni duvodu - mohu pracaovat s tabulkou, ktera realne neni v db - zapouzdreni proti nekterym uzivateulm treab View je tedy pomocna tmp tabulka virtualni, ktera slouzi jen jako uztecna promenna, treba: CREATE VIEW BigPlanes AS SELECT * FROM Aircrafts WHERE (Capacity > 200) WITH LOCAL CHECK OPTION WITH CHECK OPTION - modifikator upravitelnosti pohledu - tedy pohled mohu upravvovat pouze pokud to dava logicky smysl a splnuje to nejake omezeni zadani pri vytvoreni view - tady treba ze letadlo musi mit vetsi kapacitu nez 200 - LOCAL - podmink je zkontrolovana pouze lokalne v tomto view - CASCADE - podminka je zkontrolovana v tomto view a jeste ve vsech nadrazenych tabulkach ▪ Successful insertion INSERT INTO BigPlanes VALUES ('Boeing 737', 'CSA', 201); ▪ Denied insertion INSERT INTO BigPlanes VALUES ('Boeing 727', 'CSA', 100);

Answer 12

Zabudovana mnozina funkci a operaci pro praci primo v SQL - zavadi ridici struktury a opakovatelna funkce - if then, elsem, while, switch, for... - procedury - kurzory - triggers

Answer 13

Funkce je pojmenovana procedura, kterou muzeme opakovane volat. Pracuje nad vstupnimi parametry, vraci vysledek nebo nejak manipuluje s daty CREATE FUNCTION inc(x INT) RETURNS INT AS $$ BEGIN RETURN x + 1; END; $$ LANGUAGE plpgsql; SELECT inc(5);

Answer 14

Objekt pro traversovani radek navratoveho SELECT query SCROLL - modifikator, zda mohu prochazet pouze dopredu (default), nebo i zpetne traversovani Data fech pomoci CURSORU: FETCH - NEXT/PRIOR/FIRST/LAST... zaznam FROM cursor_name INTO var_name INTO var_name -> je to promenna, do ktere se mi ulozi navratova honodta fetch cursoru

Answer 15

TRIGGER - procedura, ktera je automaticky zavolana jako reakce na modifiakci hlidane tabulky, tj pri INSERT/UPDATE/DELETE udalosti nad tabulkou - slouzi pro zachovani integrity komplexnich dat - jako kontrola korektnosti - vola funkci ktera se ma provest - pokud zakladam funkci, ktera se bude sama pouzivat jako trigger, tak jeji return type je TRIGGER CREATE TRIGGER trigger_name BEFORE/AFTER // kdy se ma provest INSERT/UPDATE/DELETE/OR ON table_name FOR EACH ROW/STATMENT EXECUTE PROCEDURE function_name (parametry...) FOR EACH ROW VS STATMENT - for each row - trigger funkce se zavola pro KAZDY dotceny radek - for each statment - trigger funcke se provede POUZE JEDNOU za trigger reakci - tedy pokud samotna modifikace upravi 100 radku v tabulce, trigger funkce se provede POUZE JEDNOU (treba logovani, vypis, oznameni..)

Answer 16

Sekvence uprav/manipulaci s daty v db - komplexneji upravy, ne pouze jednoduche modifikace - treba bankonvi vypocty, poslani penez, aktualizace stavu atd... - hlavne v paralelni db - pisou se jako funkce podobne Sprava transakci: 1. Uzivatelska apliakce zahaji transakci (treba stiskne tlacitko dobit kredit) - aplikace zachyti tlacitko a nekolika vrstvami probubla pres kontroler k servise az na modelovou/db vrstvu - tato posledni aplikacni vrstva je napojena na DB a zahaji transakci 2. Transakcni manazer vykona transaki 3. Rozvrhovac - dynamicky rozvrhuje vykonavani paralelnich transakci - zaznamenava a vytvari historii transakci 4. Data Manazer - provadi castecne operace v ramci transakce nad databazi Transakce muze skoncit USPESNE: - ukonceno COMMIT prikazem v kodu tranaakce - provedene oprace jsou potvrzeny a konzistencni NEUSPESNE: - ABORT, ROLLBACK - terminace transakce, neprovedla se, uzivatel notifikovan - systemove ukoncei - poruseni podminky tabulek nebo trigger, uzivatel notifikovan pokud neni deadlock - HW errr - transakce neni dokoncena, musi se restartovat

Answer 17

ACID vlastnosti, maximalni vykonost ACID: Atomicity - proede se vsechno nebo nic, transakce tedy nemuze byt castecne provedena po kouscich, pokud se provede neco, tak bud se provede i zbytek, nebo se rolbackne provedena akce Consistency - kazda transakce prevede konzistentni db do jineho konzstentniho stavu, tedy ji neprevede do chyboveho stavu Isolation - transakce se paralelni nevidi navzajem a nevidi svoje nasledky dokud nejsiu COMMITOVANy Durability - pokud je transakce COMMITla, tak takova i zustane v pripade vypadku elektriny, nebo chybovych stavu, erroru atd, je to nutna podminka pro zurnalovani, je na tom zalozeno

Answer 18

Je to sekvence prikazu/operaci nad daty v db zakoncena COMMIT/ABORT Vsechny SELECT, INSERT, UPDATE... query mohou byt vnimany jako jednoduche transace se zakladnimi operacemi Zakladni transakce uvazujeme: - read(a), write(a), abort, commit Tedy treba transakce "DEKREMENTUJ A POKUD JE VETSI NEZ 5 O 5: Subtract 5 from A (some attribute), such that A>0. T = // action 3

Answer 19

Program - nebezici kod, ktery je spusten az v moment potreby transakce nad databazi - tedy je to zapsana funkce transakce, doslova kod programatora, funkce Planovac /rozvh - usporadany seznam akci prichazejicich od ruznych transakci - tedy je to casovy chronologicky zaznam akci jednotlivych transakci. Treba T1: read(a), write(a), abort T2: read(b), read(c), commit T3: write(a), commit Pokud je spustime paralelne, tak se planovac snaz je prolnout mezi sebe, takze datbazova rozvrh pak muze vypadat nasledovne: rozvhr: read(a), write(a), read(b), write(a) PREPISOVANI, read(c), commit, abort, commit Tedy je to chronologicka posloupnost jak byly operace vykonany za sebou. Slouzi to k rozeznani konfilktu (treba T1 prepise pred tim zapsanou hodnotu T3), nebo k urceni serializovatelnosti (zda je to ekvivalentni k seeriovemu vykonavani T1->T2->T3, urceni uzamykani mutexu, pokud transakce chteji zapisovat na stejne misto zaroven

Answer 20

Takovy planovani transakci, ze se vubec neprolinaji, tedy vykona se zcela T1, pak zcela treba T3, pak cela T2 atd... Muzeme vytvorit az N! rozvrhu z N transakci (jejich promichavani). Dle vlastnosti ACID by nemelo zalezet na poradi serioveho rozvrhovani. Pokud zalezi, tak jsou transakce na sobe zavisle a mely by byt spojeny do jedne. Pokud teda T1 pracuje s hodnotu A, a pak po ni T2 prepisuje hodnotu A, tak zalezi na poradi -> nejsou nezavisle -> mely by se sloucit do jedne transakce..

Answer 21

1. Muzeme zrychlit vypocty na non-db objektech, treba aritmetiku, logovani, vypisovani - neblokuje to, tedy jedna transakce nam nezahltni cely system a nebudeme furt cekat jen na jednu 2. Interaktivitu a responsivita apliakce - rychlejsi casti transakce se provedou rychleji a necekame na jednu blokujici operaci, vetsi pruchod transakci

Answer 22

Schedule (plán) je serializovatelný, pokud jeho výsledek odpovídá nějakému sériovému plánu. Tedy: jako by se transakce provedly jedna po druhé, bez prokládání. Zajišťuje, že se databáze po vykonání transakcí dostane do konzistentního stavu. 🔷 Podmínky: Uvažujeme pouze potvrzené (committed) transakce. Databáze je statická – nemění se zvenčí během plánování. Nedatabázové operace (např. výstup na konzoli) se nepočítají do konzistence. Zajistuje to Izolaci a Konzistenci z ACID vlastnosti Je to vlastnost plánu transakcí, který zajišťuje, že výsledek odpovídá nějakému sériovému (neprokládanému) provedení. Chrání konzistenci a izolaci podle ACID. V praxi se používá jednodušší konfliktní serializovatelnost, protože úplné testování je výpočetně složité. - spolu se zamykacimi nastroji a zjistovani deadlocku

Answer 23

1. read-read - ok 2. wirte-read - T2 cteni necomittovanych dat, tedy T2 cte tzv "dirty-read", precetlo data, ktera nebyly commitovany, tedy databaze je v nekonzistentnim stavu a pokud T2 commitne svoje zmeny - nekonzistentni stav db 3. read-write - T1 ma tzv "neopakovatelny read", jeho data nejsou aktualni 4. write-write - prepisovani dat

Answer 24

Pokud maji stejne konfliktni pary ve stejnem poradi

Answer 25

Plán je konfliktně serializovatelný, pokud se dá uspořádat jako sériový plán bez změny pořadí konfliktních operací. To se testuje pomocí tzv. precedence graphu (graf závislostí transakcí) – pokud nemá cyklus, plán je konfliktně serializovatelný. T1: READ(A) T2: WRITE(A) T1: WRITE(A) Konflikt: T2 zapisuje do A pred A - nekonzistence Oprava: prevedu na seriovy plan, ale zachovam poradi konfliktu: T2: WRITE(A) T1: READ(A) T1: WRITE(A) - zachoval jsem poradi konfliktu, ale uz je to konzistentni stav. Konfliktne seriolizovatelny plan mi tedy prohodi poradi na seriovy plan tak, aby zachoval chronologii konfliktu a tak predejde nekonzistentnim stavum (uz ale nereseni ihned prepisovani hodnot treba). Toto ale funguje pouze nezrusene transakce, pro staticke databaze bez dynamickeho pridavani

Answer 26

1. Postavim precedencni graf - uzly jsou transakce - hrany jsou konfilkty vuci jinym transakcim (wr, rw, ww) - tzn jakakoliv oeprace nad spolecnymi dat, kde alespon jedna transakci ma read 2. Pokud je graf acyklicky -> je konfliktne serializovatelny

Answer 27

Unrecoverable schedule nastane, když transakce čte data od jiné transakce, která později abortuje – změny nelze vrátit u již potvrzené (committed) transakce → porušení durability. Recoverable schedule zaručuje, že transakce commitne až po commitnutí všech transakcí, od kterých četla změny → databáze zůstává konzistentní. Tedy pokud T1 upravuje nejak data, pak T2 je cte (a commitne), ale T1 abortuje - musi dojit ke kaskadovemu abortu - ale to uz nejde, protoze T2 mezitim commitla uz upravene zmeny. recoverable zaruci to, ze pokud Ti pracuje s daty, ktere byly pred tim modifikovany Tj, tak Ti muze commitnout AZ PO COMMITU Tj. ➡️ Pokud umožníme čtení jen z commited transakcí, vyhneme se kaskádovým abortům (cascade aborts).

Answer 28

A: Protokoly řídí pořadí operací tak, aby byla zajištěna ACID vlastnosti a vysoký výkon. Transakční plánovač pracuje dynamicky (nezná celý plán dopředu) a v reálném čase na základě větvení v kódu. 📌 Typy protokolů: PESIMISTICKÉ řízení (pro vysoce souběžné systémy): Zámky (locking protocols) – např. dvoufázové zamykání (2PL) Časová razítka (timestamp protocols) OPTIMISTICKÉ řízení (pro méně souběžné systémy): transakce se provádějí bez omezení, testují se až před commitem ➡️ Bez protokolu by transakce mohly porušit izolaci, způsobit konflikty a nekonzistenci

Answer 29

Predchazeji konfliktum paralelniho ctenu a zapisu jednoho zdroje pomoci uzamykani tohoto zdroje, dokud se na nem neprovede konzistentni uprava, az pote k nemu muze pristoupit jina transakce, ktera mezitim musela cekat na uvolneni zdroje. Exclusive Lock X(A) - zamek pouze pro jednoho pouzivatele Shared Lock S(A) - zamek pro vice uzivatelu ale pouze na cteni Unlock U(A) 1PL - One phase locking protocol - viz vyse - pouze jedna akce na uzamceni/uvolneni zamku - nezarucuje konfliktni serializovatelnost, protoze se uvolneni muze provest prilis brzo a dojit k nekonzistencim, proste se prohodi poradi - treba deadlock asi - negarantuje recoverable plan 2PL - Two Phase Locking Protocol - aplikuej 2 pravidla na sestaveni uzamykaciho protokolu 1. Pro praci s objektem A si nejdriv transakce vyzada a dostane zamek na A 2. Pokud transakce uvolnila zamek, uz nemuze zazadat o novy/jiny - tedy 2PL nejdriv pouze hromadi zamky, pak nad objekty provadi operace, pak jakmile uvolni jeden zamek - uz nesmi dostat zadny jiny, tedy postupne pouze uvolnuje zamky - dve faze - rust zamku - uvolnovani zamku - na konci transakce NEMUSI UVOLNOVAT ZAMEK 2PL zarucuje acyklicnost grafu precedence - ale porad negarantuje recoverable plan STRIKTNI 2PL- 2. podminka je upresnena, ze pri terminaci tranakce (commit nebo abort) UVOLNI VSECHNY SVOJE ZAMKY - zarucuje konfliktne seriolizovatelnost, recoverable plan a dokonce i zamzeuje kaskadovym abortum

Answer 30

1PL: Zámky lze libovolně získávat a uvolňovat kdykoliv během transakce → ❌ žádná záruka serializovatelnosti ani obnovitelnosti. 2PL: Transakce může získávat zámky, dokud neuvolní první – pak už může jen uvolňovat → ✅ zaručuje konfliktní serializovatelnost. Strict 2PL: Zámky se uvolňují až po commitu nebo abortu → ✅ zaručuje konfliktní serializovatelnost i ✅ obnovitelnost (recoverability, bez kaskádových abortů).

Answer 31

Transakce cekaji na uvolneni zamku kazdy nejak cyklicky... Ani striktni 2PL nepredejde deadlocku Detekce pomoci: - wait-for graph - dynamicka struktura pro urceni cekajicich transakci na vzajmene zamky - uzly jsou transakce - hrany jsou cekajici zamky na jine transakce - cyklus -> deadlock Detekce pomoci opakovane kontroly cyklu v tomto grafu Reseni - kontrola grafu opakovana a v pripade nalezu - restart nejmin prioritni transakce (treba co drzi nejmin zamku neo provedla nejmin operaci...) Predejiti - pomoci priority transakci Tedy: Pokud T1 chce zamek od T2, tak spravce zamku si vybere podle dvou strategii: 1. Wait-die: jestli T1 ma vyssi prioritu, tak ceka na uvolneni od T2. Pokud T2 ma ale vyssi prioritu, tak T1 je aborted a restaartovano 2. Wound-wait: jestli T1 ma vyssi prioritu, tak T2 je aborted, jinak T1 je aborted Predejde to deadlocku, protoze najednou jedna transakce ma "pravo" abortvoat tu druhou, takze muze nasilne odebrat zamek

Answer 32

Phantom nastane, když transakce T1 zamkne řádky dle podmínky (např. salary > 5000), ale jiná transakce T2 mezitím vloží nový řádek, který by tam patřil (např. Anna s platem 6000). T1 pak pracuje s neúplnými daty, což vede k nekonzistenci výsledků a porušení izolace. - treba T1 si vybrala nejake radky podle podminky a MYSLI SI ze ma VSECHNA DATA - meztim T2 tam ale neco prida, co by spadalo pod oblast zajmu T1 - T1 treba provadi nejakou statistickou analyzu vyberu a nova hodnota od T2 by ji ovlivnila, ale T1 o ni nevi nic, pribyla bokem, takze poruseni konzistence pravidel a radku tabulky. 🔐 Prevence: Zamknutí celé tabulky Používá se, když nejsou indexy. Zámek celé tabulky zabrání přidávání nových řádků. ➤ Nevýhoda: velmi omezuje paralelismus – ostatní transakce musí čekat. Index locking Funguje, pokud existuje index na sloupci z podmínky (např. salary). Zamknou se jen příslušné části indexu (např. pro salary > 5000), tedy zamykam uz logickou jednotku, ale jednu ➤ Jemnější přístup, zachovává výkon a izolaci, ale platí jen pro jednoduché podmínky. Predicate locking Zamyká logické množiny (např. „všichni s platy > 5000“)., tedy zamykam logickou jednotku ale uz vic ➤ Teoreticky ideální, ale prakticky téměř nepoužitelné kvůli náročnosti implementace.

Answer 33

🧠 Kdy použít? Používají se, když se transakce málokdy dostávají do konfliktu, a zámky by jen zbytečně zpomalovaly systém. 🔄 3 fáze optimistického protokolu: Read fáze Transakce čte z databáze, ale zápisy ukládá jen lokálně (do svého workspace). Validation fáze Při požadavku na commit požádá transakce správce o ověření. Kontrola konfliktů s jinými transakcemi: Pokud konflikt existuje ➝ transakce je zrušena a restartována. Pokud není ➝ pokračuje dál. Write fáze Lokální změny jsou zapsány do databáze.

Answer 34

Selection - obycejna iterace pres vsechny radky a jejich kontrola Projkce - to samy, ale jeste odstraneni duplikatu Distinct - sesortit vsechno a pak odstranit duplikaty Joins - iterace pres vsechny mozne kombinace tabulek jako inner loop Sorting - quicksort, heap sort, bubble... Problemy - atomicita pristupu - musela by se zamykat cela tabulka pri obecejnem selectu - pomale disky - prohledavani je pomale bez cache - omezena pamet => potrebujeme vylepsovat

Answer 35

Techniky, jak co nejefektivneji provest dany dotaz na databazi vzdy se musi znat kontext: - pamet - algoritmus - operace - cena - znat topologiie tabulek, relaci, datovych typu - integreujiich podminek - klice - organizaace dat fyzicky - heap, sorted, hasd - indexovaci struktury B+-stromy...

Answer 36

Kolik bloku budu muset nacist do pameti. Pokud prochazim tabulku sekvencne, tak nacitam kazdy radek za sebou jako blok nejakych dat z disku -> tedy nactu VSECHNY zaznamy tabulky a porovnam je -> treba 5000 nactenych bloku -> 5000 cteni z disku. Indexovani - vytvorim usporadany rejstrik na urcity sloupce a hodim ho vedle do B-stromu. Ten ma logaritmickou hloubku, a treba kdyz hledam podle mesta, tak mesto praha najdu za 3 sestupy (tedy nasel jsem uz blok dat, ktery je Praha a odkazuje na vsechny zaznamy z tabulky z Prahy jako listy, treba 50 lidi), tzn jsem precetl pouze 3 az 50 bloku misto 5000.

Answer 37

✅ Vybrat takový evaluační plán, který minimalizuje náklady (obvykle počet čtení z disku). Databáze porovnává možné způsoby provedení dotazu a vybírá ten nejefektivnější podle dostupných statistik.

Answer 38

n_R – počet řádků s_R – velikost jednoho řádku b_R = ⌊B / s_R⌋ – blokovací faktor (kolik řádků vejde do bloku) p_R = ⌈n_R / b_R⌉ – počet bloků v tabulce V_{R.A} – počet různých hodnot ve sloupci A

Answer 39

✅ Čte se každý blok tabulky jeden po druhém. Náklad = p_R čtení z disku. Používá se, když není k dispozici vhodný index, nebo dotaz vrací hodně dat.

Answer 40

✅ Index je pomocná struktura mimo tabulku, která zrychluje hledání podle určitého sloupce. Je seřazený (např. podle city) a obsahuje ukazatele na odpovídající řádky v tabulce. B+-strom je běžný typ indexu.

Answer 41

✅ Projde se cesta stromem k listům (např. 2–3 bloky) V listech najdeme ukazatele na řádky s hledanou hodnotou Načteme jen ty bloky, kde tyto řádky jsou (např. 30 bloků) → Místo 5000 bloků stačí načíst třeba jen 33

Answer 42

Vyplatí se, když hledám málo řádků (vysoká selektivita) Nevyplatí se, když dotaz vrací velkou část tabulky Při rozsáhlém dotazu může být sekvenční scan rychlejší

Answer 43

Pres vsechny radky T1: nacti radek t1 Pres vsechny radky T2: nacti radek t2 pro kazdy sloupce t1: pro kazdy sloupec t2: porovnej podminku t1 = t2: pokud ano => pridej do join vysledku Mensi tabulka by mela byt vzdy outer loop Vylepseni metody podle znalosti struktury a ulozeni tabulky T1 a T2: ✅ 🔹 Optimalizace JOIN podle struktury tabulek: 1 .Index Nested Loop Join Pokud má T2 index na spojovací atribut A Místo procházení celé T2: pro t1.A se jen hledá v indexu T2 Odhad: n1 * (hloubka indexu + 1) → Rychlejší než full scan 2. Sort-Merge Join Obě tabulky se seřadí podle A (nebo už jsou) Prochází se současně a párují se odpovídající hodnoty O(n log n) kvůli řazení, ale výhodné pro velké tabulky 3. Hash Join Načte se menší tabulka do paměti jako hash tabulka podle A Druhá tabulka se prochází a hledá se odpovídající řádky přes hash Efektivní pro rovnostní spojení (t1.A = t2.A) 4. Zig-zag Join (index join) Obě tabulky mají index / jsou seřazené Při spojení se skáče mezi strukturami podle spojovací hodnoty → Vhodné, pokud je malý počet různých hodnot (VRA)

Answer 44

Vyhodnocujici plan se zvoli podle 1. Stromu dotazu 2. Algoritmu kazdeho korku stromu - volba podle kontextu, pameti a struktury souboru - vypocte se celkova cena dotazu - hlavne pocet cteni (pomoci statistik) Treba query: Movie ( id, Ɵtle, year, … ) Actor ( movie, actor, character, … ) FK: ( movie ) ⊆ Movie ( id ) Actors and characters they played in movies created in 2020 SQL: SELECT title, actor, character FROM Movie JOIN Actor ON (id = movie) WHERE year = 2020 Strom: listy - tabulky vnitrni uzly - operace listy - movie, actor 1. vnitrni uzel - join podle movie id 2. selection - year = 2000 3. projection - vyber sloupcu vysledku - title, actor, character Pote se spocita "globalni statistika" kazdeho kroku - tedy treba tabulka movie je sorted file, + jeji statistika, a ma treba B+-strom index na year + jeho statistika - to samy se urci treba pro tabulku actor - treba heap file Potom se urci kazdy vnitrni uzel podle jeho algoritmu a narocnosti - spocita se na konci celkova narocnost - pro optimalizaci muzeme preusporadat operace, nebo zavest pipelining (tedy vysledek uzlu je rovnou posilan do dalsiho uzlu bez zapisu na disk) - tim muzeme zmensit vyrazne narovnost a cenu dotazu Nejde nejdriv najit vsechny mozne kombinace provedeni dotazu - prilis casove narovne - zvoli se spis heuristika a optimalizace: 1. Algebraicka - na zakaldae stromovych algoritmu a algebraickych vlastnosti operaci - komutativita, asociativita atd... 2. Statisticka optimalizace - vypocet ceny ze statistikc a histogramu 3. Syntakticka optimalizace - jestli dotaz nejde provest jinym dotazem

Answer 45

1. data redundancy - neco se opakuje a zabira misto 2. data jsou na sobe zavisla mezi sloupci - treba pozice urcuje plat, to komplikuje modifikaci, protoze pokud smazeme jednu pozici tak prijdeme o informaci i platu - zavislost, pripadne uprava se musi provest ne na jednom miste ale vsude 3. zbytecne null hodnoty

Answer 46

Funkcni zavislsot je omezeni integrity mezi atributy, rika to: Hodnota jednoho nebo vice sloupcu X JEDNOZNACNE URCUJE hodnoty sloupcu Y X->Y Typy: 1. Elementratni - vpravo je jen jeden atribut, vlevo muze byt vic - treba sloupecA, sloupecB -> sloupecC 2. Slozita - vpravo vice atributu 3. Ekvivalence plati Klic je specialni druh funkcni zavislosti - jeden klic urci VSECHNY OSTATNI atributy Funkcni zavislosti slouzi jako omezeni dat (neco jako CHECK OPTION pri vkladani). Tedy pokud mi pozice urcuje plat, tak nemohu vlozit stejnou pozici ale s jinym platem, je to poruseni omezeni funkcni zavislosti

Answer 47

Pravidla ktera popisuji logicke odvozovoani novych funkcnich zavislosti ze zadane mnoziny zavislosti. Dulezite pro praci s normalnimi formami, optimalizaci databaze a kontrolu integrity K čemu Armstrongovy axiomy slouží? - Testování platnosti funkčních závislostí - Odvozování nových FDs z existujících - Minimalizace množiny FDs (tzv. pokrytí) - Zjištění klíčů a superklíčů - Normalizace tabulek (3. NF, BCNF...) 1) Trivialita Pokud Y ⊆ X, pak X → Y (např. ABC → A) 2) Transitivita Pokud X → Y a Y → Z, pak X → Z 3) Kompozice Pokud X → Y a X → Z, pak X → YZ (zavedeni sjednoceni) 4) Dekonstrukce Pokud X → YZ, pak X → Y a X → Z (rozbiti sjednoceni) F = {ab → c, ac → d, cd → ed, e → f} We could derive, e.g.,: ab → a (trivial) ab → ac (composition with ab → c) ab → d (transitivity with ac → d) ab → cd (composition with ab → c) ab → ed (transitivity with cd → ed) ab → e (decomposition) ab → f (transitivity)

Answer 48

je F+ = Mnozina vsech odvoditelnych funk. zavislsoti ze zadane mnoziny - exponencialne mnoho

Answer 49

Mejme dve mnoziny funkcnich zavislosti: F a G. Rekneme, ze G je cover F p.t.k maji stejne uzavery, tedy maji stejna odvoditelna pravidla, neboli rikaji totez z pohledu funkc, zaviuslosti: F+ = G+ Cover muze byt i redundantni, rozsireni F, nebo naopak byt redukovany a vynechat odvoditelna pravidla z F. Kanonicke pokryti - co nejjednodussi verze bez redundanci, a bez slozitych uprav, tedy pouze elementarni zavislosti, pomoci dekompozice

Answer 50

Staci tedy pomoci pravidel F dojit do G a naopak. (delam jakousi syntaktickou ekvivalenci dvou mnozin formuli, ale ne pomoci pravidel vyrokove logiky ale Armstrongovych axiomu) Tedy F+=G+ p.t.k z F se dostanu do G a z G se dostanu do F: R1(A,F), R2(A,G), A = {a,b,c,d}, F = {a → c, b → ac, d → abc}, G = {a → c, b → a, d → b} For checking that G+ = F+ we do not have to establish the whole covers, it is sufficient to derive F from G, and vice versa, i.e., F’ = {a → c, b → a, d → b} – decomposition G’ = {a → c, b → ac, d → abc } – transitivity and composition  G+ = F+ Schemas R1 and R2 are equivalent because G is cover of F, while they share the attribute set A.

Answer 51

Je to takove pokryti, ktere nema redundantni pravidla Tedy pravidlo je redundantni, pokud jeho vyhozeniim nezmenime UZAVER, tedy to pravbidlo je odvoditelny ze zbytku Non-redundant pokryti je takkove, kde odstranenim libovolneho dalsiho pravidla uz ziskame mensi UZAVER R(A,F) A = {a,b,c,d}, F = {a → c, b → a, b → c, d → a, d → b, d → c} FDs b → c, d → a, d → c are redundant after their removal F + is not changed, i.e., they could be derived from the remaining FDs b → c derived using transitivity a → c, b → a d → a derived using transitivity d → b, b → a d → c derived using transitivity d → b, b → a, a → c

Answer 52

atributy odvodidelne z X pomoci pravidel F - pokud X je cela mnozina abecedy => X je superklic (vsechny atributy) Superklic - mnozina atributu X, pro kterou plati X+=A (urci vsechny atributy) Klic = minimalni superklic (zadny atribut uz nejde vyhodt) Redundantni atribut: - takovy, jehoz odebranim nezmenime odvoditelnost nejakeho atributu - tedy aX -> Y, a pokud X->Y (bez a) => pak a je reduntnantni Redukovane pokryti atributu - nema redudnantni atributy Muze exisotvat vice klicu, klicovy atribut = atribut v nejakem klici Example – attribute closure R(A,F), A = {a,b,c,d}, F = {a → c, cd → b, ad → c} {a}+ = {a,c} it holds a → c (+ trivial a → a) {b}+ = {b} (trivial b → b) {c}+ = {c} (trivial c → c) {d}+ = {d} (trivial d → d) {a,b}+ = {a,b,c} a → c (+ trivial) {a,d}+ = {a,b,c,d} ad → c, cd → b (+ trivial) {c,d}+ = {b,c,d} cd → b (+ trivial)

Answer 53

Minimal cover (minimální pokrytí) je ekvivalentní množina funkčních závislostí, která je: 1. Bez redundantních atributů (na levé straně FD), 2. Bez redundantních závislostí (žádná FD není zbytečná), 3. V elementárním tvaru – na pravé straně jen jeden atribut (tzv. canonical cover). Treba: abcd → e, e → d, a → b, ac → d POSTUP: 1: Rozlož složené závislosti Rozděl každou FD typu X → YZ na: X → Y X → Z 🧪 Příklad: a → bc ⇒ a → b, a → c 2: Odeber redundantní atributy z levé strany U každé FD X → A: Zkus odebrat jeden atribut z X. Spočítej closure z upravené množiny. Pokud stále platí X' → A, pak je atribut redundantní. 🧪 Příklad: abc → d Zkus ac → d ⇒ pokud ac+ obsahuje d, odeber b. 3: Odeber redundantní celé FDs Dočasně vynech FD f. Spočítej closure ostatních FDs. Pokud z nich lze f odvodit, je redundantní a můžeš ji odstranit. 🧪 Příklad: Z {a → b, b → c, a → c} Odeber a → c, zbytek ⇒ a → b → c ⇒ a → c je redundantní. ⚠️ Pozor na pořadí! Nejprve zjednodušuj atributy vlevo, Poté odebírej celé FDs. Nesprávné pořadí může vést k chybnému výsledku.