===Sémantika SQL===
{{zarovka|1=
tabulka s RČ zákazníků a počtem jejich výpůjček,
:přičemž zákazníci jsou z Prahy a mají vypůjčeny aspoň dvě kopie,
:tabulka je setřízená sestupně):
<pre>SELECT rod_č, COUNT(č_kopie) AS počet_kopií
FROM Výpůjčky V, zákazníci Z
WHERE V.rod_č = Z.rod_č AND Z.adresa LIKE ‘%Praha%‘
GROUP BY V.rod_č
HAVING COUNT(č_kopie) > 2
ORDER BY počet_kopií DESC
</pre>
|2=Příklad}}'''S'''tructured '''Q'''uery '''L'''anguage je standardní neprocedurální jazyk pro přístup k relačním databázím. Jeho syntaxe odráží snahu o co nejpřirozenější formulace požadavků -- je podobná anglickým větám.
Praci s nim lze rozdelit na dve hlavni pouziti:
[[Soubor:Klastr.png|thumb|575x575px|Klastrovaný vs. obyčejný index]]
{| width="800"
| style="vertical-align:top; border-right: 1px solid black; padding-right: 10px" width="50%" |
; DDL - data definition language''' (jazyk pro definici dat)'''
* CREATE/ALTER/DROP TABLE/INDEX/TRIGGER/SEQUENCE/VIEW
* Př.: Oracle DDL syntaxe:
create table testovaci_tabulka (
cislo number(5,1) primary key,
retezec varchar2(123),
datum date not null);
: vytvori tabulku testovaci_tabulka
: obsahujici 3 sloupecky - cislo,
: do ktereho se vejdou cisla se ctyrmi cislicemi pred a
: jednou za desetinnou carkou. Sloupecek cislo je PK tabulky.
: Dale retezec pro ulozeni az 123 znaku dlouheho retezce a
: datum, ktere nemuze byt prazdne.
:* indexy
:* integritní omezení - CREATE DOMAIN/CONSTRAINT
:* ref.integrita - FOREIGN KEY/ON DELETE/ON UPDATE
| style="vertical-align:top; padding-left: 10px" width="50%" |
; DML - data manipulation language (manipulace s daty)
* INSERT/UPDATE/DELETE/SELECT
* insert into testovaci_tabulka (cislo, retezec, datum) values (4.3, 'ahoj svete!', to_date('17.1.2007', 'dd.mm.yyyy'));
* SELECT A₁,...,Aⱼ FROM R₁,...,Rₖ WHERE φ
** ≅ (R₁×...×Rₖ)(φ)[A₁,...,Aⱼ]
* aggregační fce: COUNT/MAX/AVG/SUM
* hodnotové výrazy CASE-WHEN-THEN
** COALESCE(vypujcky.cena, "vypiš tohle pokud cena IS NULL")
** NULLIF
* prefikáty LIKE/MATCH/UNIQUE/ANY/ALL/SOME
* kvantifikátory EXISTS
* množinové operace UNION/INTERSECT/EXCEPT
* pohledy
|}
==== JOINy (od SQL92) ====
'''INNER''' - pouze od. řádky z obou tabulek
'''FULL OUTER JOIN''' - všechny řádky z obou tabulek, pokud chybí odpovídající na levé/pravé straně doplní se null
'''LEFT OUTER JOIN''' - všechny řádky z levé tabulky, pokud chybí odpovídající na pravé straně doplní se null
* analogicky RIGHT
'''CROSS JOIN''' - všechno se vším, kartézský součin
* vysvetleni joinů: http://blog.codinghorror.com/a-visual-explanation-of-sql-joins/
=== SQL a jeho standardy (🎓🎓🎓) ===
{{Zkazky|* '''SELECT - srovnani SQL-89 a SQL-92 (2014, Skopal)''' - Az ve standardu SQL-92 pribyly prikazy spojeni, do te doby se musel pouzivat kartezsky soucin jako SELECT * FROM table1, table2 Pomoci klicovych slov definovanych standardem SQL-89 neslo ziskat vysledek ekvivalentni vysledku, kde je pouzit OUTER JOIN. Vnejsi spojovani muze do vysledku zahrnout null hodnoty, ale kartezskym soucinem to neudelame.
* '''SQL standardy (2011, Pokorny)''' - pohoda, rikam si. Nejak jsem to tam vypsal, co se ktery rok udalo. Projizdel to a pak se zarazil u rekurzivniho SQL - to byla zasadni chyba, ze jsem zminil! Hned se v tom zacal hrabat a padala slova jako Minimalni pevny bod, Tranzitivni uzaver a jine sproste vyrazy. Docela jsem si zaplaval, ptz hledat Min PB v SQL vyrazech neni zrovna moje kazdodenni hobby. Neco jsem tam nakonec vzdy vymyslel, zkousejici byl hodny a trpelivy. Nakonec se tvaril v pohode. Ne horsi nez 2, vypadal spokojene
* '''SQL SELECT (2009, Skopal)''' - Mal to byt popis syntaxe. Teda co vsetko sa da selectom zapisat. Kolko ma casti, co robia, opytal sa ako sa vyhodnocuju, popisal som rozne spojenia a pokracovali sme pokecom nad vnorenymi dotazmi a fungovanim IN, ALL, EXIST. Tiez sme niekde po ceste chvilu kecali o agregovani riadkov, agregacnych funkciach. Tiez celkom v pohode.
}}
SQL je neproceduralni jazyk slouzici pro praci se SRBD. Nerika jak se to, co chceme, ma udelat, ale jen co se ma udelat. Implementacni detaily nechava na databazi. Jednotlive databaze (ORACLE, MS-SQL, MySQL, ...) maji mirne odlisne dialekty SQL, i kdyz existuji standardy (sql86, sql89, sql92, sql1999, sql2003, sql2006). V zakladnich vecech se krome nazvu datovych typu ovsem moc nelisi.
==== Standardy SQL ====
SQL je standard podle norem ANSI/ISO a existuje v několika (zpětně kompatibilních) verzích (označovaných podle roku uvedení):
* SQL-86 - první nástřel, průnik implementací SQL firmy IBM
*SQL-89 ('''SQL1''') - malá revize motivovaná komerční sférou, mnoho detailů ponecháno implementaci
** 💡 spojení je možné pouze přes SELECT ... FROM A1,A2 WHERE... což umožňuje pouze vnitřní spojení (INNER) a kart.součin (CROSS) - tj. klíč.slovo JOIN ještě není
* '''[http://en.wikipedia.org/wiki/SQL-92 SQL-92]''' ('''SQL2''') významná revize
** přidán '''JOIN''' - a jeho další druhy, hlavně OUTER JOIN, ktery standardem SQL-89 neslo provest (kartezskym soucinem nelze ziskat NULL hodnoty) - viz [http://cs.wikipedia.org/wiki/JOIN info o JOIN]
** nove datove typy (DATE, TIME, VARCHAR, ...)
** INFORMATION_SCHEMA.TABLES - metadata tabulek jako tabulka
** množ.operace
**kaskádové mazání/aktualizace podle cizích klíčů, kurzory, výjimky
** Definovany urovne izolace transakci: READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ a SERIALIZABLE
* '''[http://en.wikipedia.org/wiki/SQL:1999 SQL:1999]''' ('''SQL3''') - regulární výrazy, rekurzivní dotazy, triggery, booleovské typy, ...
** procedurální rozšíření SQL - některé '''objektově orientované''' rysy
** nové datové typy -- reference, '''pole''', full-text, boolean
** '''rekurze (CTE)''' - konečně můžeme udělat tranzitivní uzávěr
** podpora pro externí datové soubory, multimédia
* '''[http://en.wikipedia.org/wiki/SQL:2003 SQL:2003]''' (některé XML rysy, generátor sekvencí, MERGE, CREATE TABLE LIKE, ...)
** '''větší ARRAY, SET, MULTISET'''
* '''SQL:2006''' – definuje širší využití XML, integrace XQuery, ...
* [http://en.wikipedia.org/wiki/SQL:2008 SQL:2008]
* [http://en.wikipedia.org/wiki/SQL:2011 SQL:2011]
Komerční systémy implementují SQL podle různých norem, někdy jenom SQL-92 Entry, dnes nejčastěji SQL-99, ale nikdy úplně striktně. Některé věci chybí a naopak mají všechny spoustu nepřenositelných rozšíření -- např. specifická rozšíření pro procedurální, transakční a další funkcionalitu (T-SQL (Microsoft SQL Server), PL-SQL (Oracle) ). S novými verzemi se kompatibilita zlepšuje, často je možné používat obojí syntax. Přenos aplikace za běhu na jinou platformu je ale stále velice náročný -- a to tím náročnější, čím víc věcí mimo SQL-92 Entry obsahuje.Pro otestování, zda je špatně syntax SQL, nebo zda jen daná databázová platforma nepodporuje některý prvek, slouží SQL validátory (které testují SQL podle norem).
=== Rekurze v SQL. (🎓) ===
{{Zkazky|
* '''Rekurzivní SQL (Pokorny?)''' - Hned se v tom zacal hrabat a padala slova jako Minimalni pevny bod, Tranzitivni uzaver a jine sproste vyrazy. Docela jsem si zaplaval, ptz hledat Min PB v SQL vyrazech neni zrovna moje kazdodenni hobby. Neco jsem tam nakonec vzdy vymyslel, zkousejici byl hodny a trpelivy. Nakonec se tvaril v pohode. Ne horsi nez 2, vypadal spokojene
}}
{{TODO| projít a doplnit}}
{{zarovka|
:+ vše jedním dotazem
:+ lze využít velkou část výsledku
:- časté využití pouze malé části výsledku
:- možnost zacyklení rekurze
|vyhody/nevyhody}}
* SQL před standardem SQL:99 neobsahoval možnost konstrukce rekurzívních dotazů
{{collapse|podpora v reálných DB|2=
* ktere DB systemy podporuji rekurzi ( http://stackoverflow.com/questions/324935/mysql-with-clause )
** MS SQL podporuje od verze MS SQL Server 2005
** Orace od 9i release 2
*** Oracle pro rekurzi obsahuje také proprietární řešení (s omezenějšími možnostmi) s pomocí speciálních klauzulí START WITH a CONNECT BY příkazu SELECT
** MySQL ne (feature request od 2006: http://bugs.mysql.com/bug.php?id=16244)
** SQLite podporuje az od 2014-02-03 (3.8.3) ( http://www.sqlite.org/changes.html )
* online vyzkouseni: http://data.stackexchange.com/stackoverflow/query/new
** priklad s konstrukty bez smyspluplne rekurze:
WITH UsersAndPosts (CreationDate, DisplayName)
AS
(
SELECT p.CreationDate, u.DisplayName
FROM Posts AS p INNER JOIN Users AS u ON p.OwnerUserId = u.Id
[UNION ALL] // nepovinne
rekurzívní člen // nepovinne
)
SELECT * FROM UsersAndPosts
}}
====Common Table Expression (CTE)====
* deklaruje se klíčovým slovem ''WITH RECURSIVE jméno_CTE[(jméno_sl[,jméno_sl]…)] AS (CTE_definice_dotazu)''
* V CTE pro tabulku R se lze odkazovat na R
* vytvoří se dočasná tabulka (existuje pouze v době vyhodnocování dotazu)
<pre>
WITH RECURSIVE
ukotvení (inicializační poddotaz) - spouští se jednou
UNION ALL
rekurzívní člen - opakovaně
•rekurze běží pokud není přidán žádný další záznam anebo není překročený limit rekurze (MAXRECURSION)
•pozor na zacyklení rekurzívního členu
INNER JOIN - spojení s minulým krokem
SELECT
•Vnější SELECT - dá výsledek dotazu(výstup)
</pre>
'''Příklad:''' Najdi všechny nadřízené Nového (včetně něho sama)
<pre>
WITH RECURSIVE Nadřízení(jméno, č_nad, č_zam) AS
(SELECT jméno, č_nad, č_zam
FROM Zaměstnanci
WHERE jméno = 'Nový'
UNION ALL
SELECT Z.jméno, Z.č_nad, Z.č_zam
FROM Zaměstnanci AS Z
INNER JOIN
Nadřízení AS N
ON N.č_nad = Z.č_zam)
SELECT * FROM Nadřízení
</pre>
{{Collapse|Příklady|
;Příklad z přednášky:
Tabulka: Zaměstnanci(č_zam, jméno, funkce, č_nad)
Najdi všechny nadřízené Nového (včetně něho sama)
<pre>
WITH RECURSIVE Nadřízení(jméno, č_nad, č_zam) AS
(SELECT jméno, č_nad, č_zam
FROM Zaměstnanci
WHERE jméno = 'Nový'
UNION ALL
SELECT Z.jméno, Z.č_nad, Z.č_zam
FROM Zaměstnanci AS Z
INNER JOIN
Nadřízení AS N
ON N.č_nad = Z.č_zam)
SELECT * FROM Nadřízení
</pre>
;Příklad:
Mame tabulku Zamestnanci(jmeno, plat, vedouci). Najdete pomoci rekurzivniho dotazu vsechny zamestnance s platem nad 100 000, kteri jsou (i neprimi) podrizeni Ryby.
<pre>
WITH RECURSIVE PodRybou(jméno) AS
(SELECT jméno
FROM Zamestnanci
WHERE vedouci = “Ryba”
UNION ALL
SELECT jméno
FROM Zaměstnanci Z, PodRybou P
WHERE Z.vedouci = P.jmeno
)
SELECT * FROM PodRybou
WHERE plat > 100 000
</pre>
}}
{{Zdroje|
* [http://www.ksi.mff.cuni.cz/~pokorny/dj-new/DJ2-3-rekurze.pdf http://www.ksi.mff.cuni.cz/~pokorny/dj-new/DJ2-3-rekurze.pdf]
}}
=== Algoritmy implementace relacních operací. Vyhodnocování a optimalizace dotazů (🎓) ===
{{Zkazky|
* '''SQL + vyhodnocovanie a optimalizácia dotazov (Richta)''' - bol super, dokonca mu nevadilo, že som zabudol popísať optimalizáciu, stačilo len 3 vetami vysvetliť, o čo ide
* '''Implementace operací relační algebry (JOIN)'''
}}
{{TODO| doplnit z wordu}}
==== Vyhodnocování (Algoritmy implementace relacních operací) ====
CPU je rychle a levne, RAM je taky relativne dost, dulezity je pocet pristupu na disk
indexace je delana b+ stromy s vysokym poctem nasledniku (50-100), ale tak, aby se jeden uzel vesel do jedne stranky na disku a byla nizka uroven (pocet pater) indexu
:'''p<sub>R</sub>''' – počet stránek potřebných k uložení relace R (záleží na velikosti jednoho záznamu relace a velikosti jedné stránky, tzn. na blokovacím faktoru)
:'''b<sub>R</sub>''' – blokovací faktor pro relaci R (počet záznamů dané relace, které se vejdou do jedné stránky)
:'''I(A)''' – hloubka indexu (resp. výška B+ stromu indexu pro atribut A)
===== 1. selekce =====
SELECT * FROM R WHERE A = 'a'
ruzne vysledky podle toho, zda A je PK (unique), sekundarni klic (nemusí být unique), A je hasovany klic. Předpokládáme rovnoměrné rozložení hodnoty A v záznamech relace.
* '''sekvencni vyhledavani''' - v nejhorsim pripade je potreba prohledat celou R, v průměrném případě, je- li A PK stač í prohledat půlku (PK zarucuje unikatnost, v okamžiku, kdy naleznu první záznam, nemusím pokračovat)
* '''binarni vyhledavani''' (je-li R usporadana podle A) - log2(p_R) pro PK, pripadne plus nacteni dalsich bloků se shodnou hodnotou, neni-li to PK
* '''existuje-li index'''
** I(A) + 1 (pro PK)
** I(A) + n<sub>R</sub>(A='a') / b_R – je-li clusterovany index (tabulka je ulozena na disku setridene, index na bloky - stejne usporadani jako indexsekvencni soubor)
** I(A) + n<sub>R</sub>(A='a') – pro normalni neclusterovaný index (index ukazuje na n<sub>R</sub>(A='a') adres)
* '''vyhledani s hasovanim''' – přibližně jeden pristup (záleží na hašovací funkci).
===== 2. vypocet spojeni =====
SELECT * FROM R, S WHERE R.A = S.A
dva typy implementace
* nezávislé relace
* s ukazateli (záznamy jedné relace mají ukazatele na odpovídající prvky druhé relace)
spojovaci atribut A, p<sub>R</sub> ≤ p<sub>S</sub>
binarni spojeni - zakladni metody hnizdene cykly, trideni- slevani, hasovane spojeni, kartezsky soucin (spec. případ spojení)
====== a) hnízděné cykly ======
* a1) naivne ∀ r in R do ∀ s ∈ S do jestlize spojeni techto dvou radku patri do vysledku, tak ho zapis
* a2) lepe po strankach (mensi relaci dej jako vnejsi, vetsi vnitrni se budou cachovat) - mensi relaci jako vnejsi for (vnitrni prectu p<sub>R</sub>*p<sub>S</sub>/(pocet stranek p<sub>R</sub>, ktere muzu cacheovat (pro velke M)) krat, vnejsi p<sub>R</sub>krat, takze je lepsi, kdyz je p<sub>R</sub> mensi); pokud se mi cele R vejde do pameti, tak staci jen p<sub>R</sub>+p<sub>S</sub> cteni
* a3) se selekci - nejdrive selekci a pak spojeni (najdu selektovany prvek, pak odpovidajici v druhe tabulce, dotazy do indexu +2)
* a4) spojeni vice relaci:
** heuristika: Srovnej n relaci do cyklu algoritmu tak, aby mensi byly vnejsi.
** Pro R<sub>n</sub> (nejvnitrnejsi) alokuj jednu stranku, zbytek rozdel rovnomerne. Kdyz to nejde, tak vetsi M<sub>i</sub> pridel vnejsim relacim
====== b) setrideni-slevani ======
* zvlaste vhodne, pokud jsou R, S setridene, jinak je treba je setridit(potrebujeme pomocny prostor). Vysledek spojeni bude taky setrideny podle A
* b1) klasicke trideni na vnejsi pameti, pak slevani. Pokud M > sqrt(pS), tak lze 2 behy setridit - 3(pS + pR) cteni a 2(pS+pR) + pSR zapisu.
* b2) varianta s ukazateli (prvky R obsahuji ukazatele na prvky S) - setridit R podle ukazatelu a pak jen cist S (nemusi byt setrizena) - 3pR + pS cteni + zapis vysledku
* Porovnani s hnízděnými cykly:
** |pS - pR| male - lepsi je trizeni slevani
** |pS - pR| velke - lepsi jsou hnízděné cykly
====== c) hasovani ======
* nejsou-li indexy pro R.A a s.A, nemusi-li byt vysledek setrizen (jde taky vyrobit vysledek a pak ho dodatecne setridit)
* c1) klasicke hasovani (predpokladame, ze se R vejde do pameti) - zahesuj R do pameti, prochazej S, hasuj s.A a primym pristupem najdi patricne r \in R. Pokud patri do vysledku, tak ho uloz do vystupniho bufferu.
** (predpokladame, ze se 1. tabulka vejde do pameti. Celou 1. tabulku
zahasujeme do pameti. Sekvencne prochazime 2. tabulku, hasujeme dany
prvek a kdyz se rovna jiz nahasovanemu prvku z 1. tabulky, tak zname spojeni z vysledku)
* c2)spojeni s rozdelovanim relaci (R se nevejde cele do pameti, jen jeho cast)- jako c1, ale na nekolikrat, na kolikrat se nam R vejde do pameti - pR + pS*x (pocet cyklu) cteni
** rekurzivní rozdělení relací
*** predpokladame, ze se zadna tabulka nevejde do pameti. Jako Klasické hašování, ale na nekolikrat.
* c3)GRACE algoritmus - rozdel pomoci hashovaci funkce R i S do kapes ukazatelu (skupiny ukazatelu na prvky se stejnym hashem). Pro kazdou kapsu zvlast nacti do pameti a otestuj R.A = S.A a pripadne zapis do vystupniho bufferu. Vhodne, pokud se mi jednotlive kapsy vejdou do pameti.
** rozdel pomoci hashovaci funkce obe tabulky (vsimneme si rozdilu
oproti klasickemu hasovani) do kapes ukazatelu (skupiny ukazatelu na
prvky se stejnym hashem). Kazdou kapsu zvlast nacti do pameti a otestuj
R.A = S.A a pripadne zapis do vystupniho bufferu. Vhodne, pokud se mi
jednotlive kapsy vejdou do pameti.
{{collapse|GRACE algoritmus (grace hash join)|2=
This algorithm avoids rescanning the entire S relation by first partitioning both R and S via a hash function, and writing these partitions out to disk. The algorithm then loads pairs of partitions into memory, builds a hash table for the smaller partitioned relation, and probes the other relation for matches with the current hash table. Because the partitions were formed by hashing on the join key, it must be the case that any join output tuples must belong to the same partition.
It is possible that one or more of the partitions still does not fit into the available memory, in which case the algorithm is recursively applied: an additional orthogonal hash function is chosen to hash the large partition into sub-partitions, which are then processed as before. Since this is expensive, the algorithm tries to reduce the chance that it will occur by forming as many partitions as possible during the initial partitioning phase.
*„školní“ verze
Datové struktury: n-tice R a S, kapsy ukazatelů HRi, HSi,
i ∈ {0,1,…,m-1}
hašovací funkce h: dom(A) → <0,m-1>
Algoritmus:
<pre>for k:=1 to nR do begin i :=h(R[k].A); HRi := HRi ∪ {k} end
for k:=1 to nS do begin i :=h(S[k].A); HSi := HSi ∪ {k} end
for i:=0 to m-1 do
begin POMR := ∅; POMS := ∅;
foreach j ∈ HRi do begin r:=R[j]; POMR:=POMR∪{r} end;
foreach j ∈ HSi do begin s:=S[j]; POMS:=POMS∪{s} end;
foreach s ∈ POMS do /* ve vnitřní paměti */
begin foreach r ∈ POMR do
begin if s.A = r.A then begin u:= r * s; WRITE(u)
end
end
end
end</pre>
⇒ pR + pS + nR + nS čtení
vhodnost: když pR /m + pS/m < M
;GRACE s ukládáním rozdělených relací
•M ≥ √(pR*F)
# Zvol h tak, že R lze rozdělit do m = √(pR*F) částí;
# Čti R a hašuj do (výstupních) bufferi, (0 ≤ i ≤ m-1);
#:if bufferi je plný then WRITE(bufferi);
# Proveď (2) pro S;
# for i :=0 to m-1 do begin
## Čti Ri a hašuj do paměti velikosti √(pR*F);
## Čti s ∈ Si a hašuj s.A.
:Existuje-li r ∈ Ri a s.A = r.A, generuj výsledek.
end
Zdůvodnění 4.1: předpoklad - Ri ≈ stejné velké
pR/m = pR/ √(pR*F) = √(pR/F)
Ri vyžaduje prostor F√(pR/F) = √(pR*F)
⇒ 3(pR + pS) I/O operací
:vhodnost: když pR /m + pS/m < M
:poznámky:
*Si mohou být libovolně velké. Vyžadují 1 stránku paměti;
*problém, když V(A,R) je malý;
*vhodné v situacích, když R(K,…), S(K1,K,…);
*nevejde-li se Ri resp. Si do M-2 stránek ⇒ rekurze
tj. Ri se rozdělí na Ri0, Ri1,...,Ri(k-1) stránek;
}}
* c4) jednoduche hasovani - spec. pripad GRACE - zvol h() tak, aby rozdelila R na R1, ktera se vejde do pameti (M-2) a R2, kterou budu ukladat na disk. Cti a hasuj S. Pokud h(s.A) = h(R1.A), pak porovnej v pameti a vysledek zapis. Pokud ne, uloz na disk do S2. Po projiti celeho S se z R2 stava R a z S2 se stava S.
** předpokladame, ze se zadna tabulka nevejde do pameti a A (atribut) je UNIQUE
** zvol funkci h() tak, aby rozdelila tabulku R na R1, ktera se vejde
do pameti, a R2, kterou budu ukladat na disk. Cti a hasuj tabulku S.
Pokud h(s.A) = h(R1.A), pak porovnej v pameti a vysledek zapis. Pokud
ne, uloz na disk do S2. Po projiti celeho S se z R2 stava R a z S2 se
stava S. Opakuje se dokud R neni prazdne
* c5) hybridni - kombinace C3) a C4). Zvolime h tak, ze R0 se vejde do pameti cela a pro Ri nam tam zbyde jedna stranka. Hasujeme a Ri ukladame na disk. Hasujeme S a pokud padne do prostoru R0, tak porovname a zapiseme, pokud ne, tak ulozime na disk do prislusne "kapsy" Si. Po projiti pokracujeme stejne jako GRACE (v prvnim kole jsme rovnou vyresili prvni skupinu)
** kombinace GRACE a jednoduchého hašování (dava nejlepsi vysledky)
** Zvolime h tak, ze R0 se vejde do pameti cela a pro Ri nam tam zbyde
jedna stranka. Hasujeme a Ri ukladame na disk. Hasujeme S a pokud padne
do prostoru R0, tak porovname a zapiseme, pokud ne, tak ulozime na disk
do prislusne "kapsy" Si. Po projiti pokracujeme stejne jako GRACE (v
prvnim kole jsme rovnou vyresili prvni skupinu)
* Porovnani:
** C5 nejlepsi
** C4 lepsi nez C3 pro vetsi M
** C3, C4, C5 lepsi nez setrideni-slevani
dalsi operace - GROUP BY, DISTINCT se resi pres hasovani, nebo rozdelenim pomoci indexu (pokud je), pripadne trizenim
====Optimalizace====
pozn. cast s algebraickou opt. vs plan vyhodnoceni je zmatena, protoze nerozumim tomu, v jakem vzajemnem vztahu ty dve veci jsou.
je treba rozumet optimalizaci a danemu SRBD obecne pro optimalni navrh schematu a dotazu (napr. problem implicitnich konverzi versus indexy (dotaz select * from tabulka where sloup = 1234. pokud je sloupecek typu string (varchar2), tak se musi pred porovnanim bud hodnota sloupecku 'sloup' prevest na cislo nebo hodnotu 1234 prevest na string. Jeden z techto prevodu bude ignorovat pripadny index nad sloupeckem 'sloup' a je na danem SRBD, ktery pouzije. Lze obejit explicitnim prevodem (to_string(1234)), ke kteremu ovsem potrebujeme prakticke zkusenosti :)))
'''Faze zpracovani dotazu:'''
* 1. prevod do vnitrni formy (typicky nejaka relacni algebra)
* 2. konverze do kanonickeho tvaru
* ''3. algebraicka optimalizace''
* ''4. Plan vyhodnoceni''
* 5. Generovani kodu
pro optimalizaci jsou dulezite kroky 3 a 4
'''3. algebraicka optimalizace''' - přerovnání selekcí, projekcí, spojení
Heuristiky:
* selekce co nejdrive
* projekce co nejdrive
* sjednotit vice operaci selekce (projekce) do jedne
* transformace <math>\times</math> na *
* přeskupení relací ve stromu dotazu tak, aby selekce produkující menší relace byly volány dříve
statisticky řízená
* katalogy
* redukční faktor
* histogramy - rozdělení dat
Plan vyhodnoceni - strom dotazu + algoritmus pro kazdou operaci
Pro vsechny uvazovane plany se spocita odhadovana cena dotazu. To se udela s vyuzitim statistik o tabulce(tabulkach) a znalosti existence a typu indexu. Plan s nejmensi cenou se vybere.
Priklady ruznych planu a jejich cen (selekce prvni, selekce druha)
Dotazy nad vice tabulkami se resi vybranim nejlepsiho reseni pro jednu kazdou tabulku a pak vybranim nejlepsiho spojeni. spojuje se vzdy s jednou tabulkou (1 s 1, 2 s 1, ... n-1 s 1)
Slozitejsi dotaz je rozlozen na bloky (treba hlavni cast dotazu a vhnizdeny dotaz), ktere se optimalizuji zvlast.
'''Cost-based optimalizace''' – z předmětu DB klient-server (Rubač)
* databáze spočítá pro všechny možné plány vyhodnocení dotazu jeho odhadovanou cenu (na základě statistik, které si ukládá – např velikost jednotlivých tabulek, blokovací faktor, poměr mezi rychlostí paměti a disku, historgram sloupců – pro rozhodnutí, zda se vyplatí použít index nebo ne, apod.) a následně vybere nejlevnější možnost, může se ukázat, že odhady nebyly správné, v průběhu prvního spuštění dotazu se počítá doba jednotlivých kroků a nakonec se přepočítá volba algoritmu s aktuálními hodnotami - při dalším spuštění již dotaz běží optimálně
* analytik musí vědět, jak pracuje optimalizátor, aby tomu mohl přizpůsobit zápis dotazu, zároveň má v řadě databází analytik možnost napovídat optimalizátoru (např. A.ID = B.ID nastává v 15% případů, nebo u B použij index)
'''Cost-based optimalizace''' – databáze spočítá pro všechny možné plány vyhodnocení dotazu jeho odhadovanou cenu (na základě statistik, které si ukládá – např velikost jednotlivých tabulek, blokovací faktor, poměr mezi rychlostí paměti a disku, historgram sloupců – pro rozhodnutí, zda se vyplatí použít index nebo ne, apod.) a následně vybere nejlevnější možnost, může se ukázat, že odhady nebyly správné, v průběhu prvního spuštění dotazu se počítá doba jednotlivých kroků a nakonec se přepočítá volba algoritmu s aktuálními hodnotami - při dalším spuštění již dotaz běží optimálně.
A '''rule based''' optimizer is an optimizer that just applies a set of rules to a SQL statement instead of looking at cost estimates in order to determine what the best way is to execute that SQL statement. Oracle actually allows you to use either the rule based or cost based optimizer, although Oracle says that rule based optimization will be deprecated in a future release, so it highly recommends the use of cost based optimization.
* http://kocour.ms.mff.cuni.cz/~pokorny/vyuka/dj1/DJ1-vyhodnoceni.pdf
* http://kocour.ms.mff.cuni.cz/~pokorny/vyuka/dj1/DJ1-optimalizace.pdf
=== Objektové rozšíření relačního modelu dat (🎓) ===
{{:Databázové_modely_a_jazyky/OODB}}
