Dotazovací jazyky I

Dotazovací jazyky I

Kód předmětu: NDBI001 Přednáší: Jaroslav Pokorný

Dotazovací jazyky, povídání o SQL.

• zkouška: písemná – příklady
• zápočet: referát na semináři (po dvojicích, PowerPointová prezentace), jinak psané (Word)

Odkazy

• info u Pokorného
• neoficiální sbírka příkladů

Zkoušky

Je dobré si úlohy skúsiť vyriešiť najprv samostatne, pre niektoré úlohy boli zverejnené aj riešenia.

26. 1. 2012

Nebylo tam nic, co neni na tady, velká část se kryla s písemkou co je na wiki z 10.2.2009, nebylo tam ale vůbec nic z optimalizace a na DIS tam byla tabulka věcí a rozhodnout, jestli zvyšuje P nebo R.

Bodování úloh docela mírný (třeba v OR stačí přibližná syntaxe, hlavně když je tam myšlenka), známkování naopak trošku přísnější - 22-19: 1, 18,17: 2, 16,15 (nejsem si úplně jistej): 3, 14-0: 4.

Takže umět pořádně SQL, počítat přístupy v nested loops a alespoň navrhnout OR model a je to solidní základ na projití.

10.2.2009

• 1) Dotazovanie nad zadanou schemou (boldom su kluce)

Pobocka(meno_pivovaru, meno_pobocky, adresa)

Vari(meno_pivovaru, meno_pobocky, znacka, stupen)

Odobera(hospoda, znacka, stupen, meno_pivovaru, cena) (kluc si nepamatam)

* Q1: Pivovary, kt. pivo nikto neodobera. (cez having to ide velmi jednoducho)
* Q2: Pivovary, kt. nejaku znacku (piva) nikto neodobera.

• 2) previest schemu do OR s pouzitim REF, kolekcii (napisat dotazy pre CREATE TYPE a odpovedajuce CREATE TABLE, pozor v SQL1999 je iba ARRAY)... Nad danou schemou spravit dotaz:

Vsetky hospody, vsetky znacky a stupne, ktore sa v nich varia? (neviem, ci je to presne ono)

• 3) Vysvetlit, kedy je v RA mozne spravit: (E1 x E2) (selekcia) = E1(selekcia) x E2

• 4) Pocitanie pristupov na stranky: p_R = 200, b_R = 10, p_S = 500, b_S = 5, M = 42, spojenie R[A=B]S, max 5 n-tic z S spojitelnych s kazdou n-ticou z R
  • a) nested loops, pocet pristupov

iba vzorec pR + (pR*pS)/(M-2) = 2700

• • b) nested loops, 2-urovnovy klastrovany B+ index nad B v S, pricom vsetky spojitelne n-tice z S pre vybranu n-ticu z R sa nachadzaju v 1 stranke

pR + nR(2+1) = pR + 3*nR = 200 + 6000 = 6200

Vysvetlenie: Relaciu R musim nacitat celu (p_R) a pre kazdy zaznam (celkovo ich je n_R = p_R * b_R = 2000) potrebujem 2 pristupy v indexe na najdenie pozadovanej stranky (v ktorej su vsetky zaznamy spojitelne s aktualnou n-ticou z R) + 1 pristup na nacitanie tejto stranky.

• • c) nested loops, 2-urovnovy NEklastrovany B+ index nad B v S

pR + nR(2+5) = pR + 7*nR = 200 + 14000 = 14200

Vysvetlenie: Relaciu R musim nacitat celu (p_R) a pre kazdy zaznam (celkovo ich je n_R = p_R * b_R = 2000) potrebujem 2 pristupy v indexe na najdenie pozadovanej stranky + max. 5 roznych stranok najst (pretoze max. 5 n-tic je spojitelnych a kedze ide o neklastrovany index, mozu byt kdekolvek)

• • d) spocitat pripad c), ak vieme, ze A bude zotriedena a pocet listov indexu je 16:

tusim, ze: pR + 1 + nR * ( 1/16 + 5)
myslim, že je to spíš takhle: pR + 1 + 16 + nR * 5, zdůvodnění mi připadá v pořádku, možná drobné doplnění:
když načítam další stránku R, ponechávám si aktuální stránku indexu a pokračuji z toho místa, není třeba procházet stránky indexu víc jak 1x, tzn 16 přístupů. Jookyn

Vysvetlenie: Relaciu R musim nacitat celu (p_R), 1 stranka na pristup do 1.urovne indexu nad B a pre kazdy zaznam v A hladam n-tice z S, ale vyuzivam to, ze A je zotriedena a index je B+ - teda nemusim vzdy pristupovat na 1.uroven indexu, ale posuvam sa iba po listoch, tych je 16. No a este pristup na stranky, kde su n-tice z S (tych je max. 5))

• 5) Sim(Q,Di) zadana skalarnym sucinom, kde q1, q2 a q3 su nenulove. Ako to bude vyzerat v boolskom modeli?

Odpoved: t₁ OR t₂ OR t₃ (kde t₁, t₂, t₃ su prislusne termy)

Ak tam su nejake nejasnosti, sorry, snazil som sa napisat vsetko, co som si zapamatal.

3.2.2009

Tak co se objevilo v dnešní zkoušce, jedná se jen o doplnění předchozích příkladů:

• 1) máme počty stránek p_R, p_S a blokovací faktory b_R b_S a počet stránek paměti M, spojení je R[A=B]S, přičemž ke každé n-tici z R je max. 5 n-tic z S
  • a) spočtěte počet čtení přes hnízděné cykly (2 body)
    • řešení: p_R + p_R*p_S/(M-2)
  • b) spočtěte počet čtení přes hnízděné cykly když nad B je 2-úrovňový klastrovaný index, a ke každé n-ticy z R jsou n-tice z S uloženy v jedné stránce (3 body)
    • řešení: p_R + n_R*I(B,S)*1 (za správnost neručím)
    • řešení: p_R + n_R*(I(B,S)+1) ... a neni to spis takhle? Lukas
  • c) spočtěte počet čtení přes hnízděné cykly když nad B je 2-úrovňový obyčejný index (3 body)
    • řešení: p_R + n_R*I(B,S)*5, kde n_R = p_R*b_R (za správnost neručím)
    • řešení: p_R + n_R*(I(B,S)+5) ... a neni to spis takhle? Lukas
  • upozornění: spočtěte znamená napsat číslo, ne jen vzoreček;
• 2) DIS - jaké bude q_k (viz. vzoreček ze slajdů) když v dotazu budou pouze klíčová slova
  • řešení: q_k = IDF_k protože TF_k = 1 a maxTF_k = 1
• 3) DIS - spočítat vektor D = TF_k*IDF_k, když TF_k,m a DF_k byly zadány
• 4) Schéma: viz to schema nize s tabulkami Herec, Hraje_v a Film
  • vybrat všetkých hercov, ktorí hrali vo vsech filmoch režírovaných Formanom (3b)

• 5) Upravit schéma ze 4) na OR model s tim, že do databáze pribudou i jiné osoby. Narozdil od kteresi minule pisemky se tu pozadovalo ponechani HerecId a FilmId a pouziti typu kolekce. Ve výsledku mely byt 2 relace (3b).
  • Napísať v tomto novom shémate dotaz D3: Pre každého herca zistiť počet Formanových filmov (režírovaných Formanom) do ktorých boli obsadení.

28.1.2009

Jen doplnění věcí:

• Spojení relací R * S pomocou hnízděných cyklů: p_R = 2000, b_R = 20, p_S = 5000, b_S = 50, počet bufferů M = 402.
  • Pozn. k řešení: Jen naházet do vzorečku p_R + p_R * p_S / (M - 2).
• Byla tam tabulka a pro každý řádek určit, zda zvyšuje či snižuje P (přesnost) a R (úplnost)
  • P R
  • +  -     AND
  • -  +     OR
  • -  +     zástupné znaky
  • -  +     tezaurus (myslím)
  • -  +     lemmatizace (myslím)
  • +  -     rozlišování velkých a malých písmen
  • +  -     rozlišování frází
  • ... nějaké další
• V otázce udělat dotaz nad OO modelem byl dotaz: Vyberte všechny herce a k nim počet Formanových filmů, ve kterých měli roli.

21.1.2009

Většinou se příklady opakují z minulých roků.

• 1.) Schéma:

+---------+    +-------------+    +----------+
|  Agent  |    |     Dum     |    | Vybaveni |
+---------+    +-------------+    +----------+
| A_Id    | -  | Adresa      | -- | Adresa   |
| A_Jmeno |  \ | Vlastnik_jm |    | Rys      |
+---------+   -| A_Id        |    +----------+
               +-------------+

• • Napsat dotaz, který vypíše jména těch vlastníků domů, jejichž domy spravuje pouze jeden agent (přes having to jde hezky)
• 2.) Vytvořit OO model, nesmí se ztratit žádná informace, mělo se využít systémově generovaných OID.
• 3.) Dotaz nad vzniklých OO schématem.
• 4.) TFxIDF na dvou větách, pouze s podstatnými jmény.
• 5.) Spočítat Similarity pro dva dotazy a seřadit je podle relevantnosti (dotazem se tady myslí nějaká věta, podle toho jestli obsahuje slovo nebo ne se dává váha 0 nebo 1)
• 6.) Nakreslit strom dotazu viz písemka z 17.1.2008 př. 8a)
• 7.) Pro schéma nahoře spočítat IO operací.
  • • Agent: 200 záznamů, blokovací faktor 10, jednoúrovňový index nad A_ID
    • Dům: 1000 záznamů, blokovací faktor 4, klastrovaný dvouúrovňový index nad Adresou => 250 stránek
    • Rys: 10 000 záznamů, blokovací faktor 10, klastrovaný dvouúrovňový index nad Adresou
  • Pozn. k řešení: Protože agentů je 200 a domů 1000, tak připadá na agenta cca 5 domů. Protože domů je 1000 a vybavení 10 000, tak na dům připadá cca 10 rysů. Agenta 007 lze si vyhledat na (1 + 1) přístupů (jeden za zalezení do indexu a pak načtení jednoho agenta). Pak lze projít domy a vybrat ty, které mají agenta 007 (nad A_ID nebyl u domů index) -je tedy potřeba načíst 250 stránek. Při tom k nim jde lepit zároveň agenty. Na výsledek joinu agentů s domy provedeme join, který veme 5*(2 + 2) IO operací (po joinu nám zbylo cca 5 domů - záznamů, které měli agenta 007; pro každý dům musíme načíst vybavení, tzn. 2 IO pro zalezení do indexu a pak ještě načíst cca 10 záznamů vybavení - protože jsou kvůli klastrovanému indexu záznamy jedné adresy u sebe, stačí je sekvenčně načíst ... 10 záznamů veme max 2 stránky - blokovací faktor je totiž 10 a na jeden se asi netrefíme). Výsledek teda mohl být: (1 + 1) + 250 + 5 * (2 + 2) = 272. (Toto bylo moje řešení, které prošlo - když tak mě opravte, jestli je něco špatně).
• 8.) Nakreslit optimalizovaný strom.
• 9.) Kolik bude potřeba IO operací, když u domů bude klastrovaný index i nad A_Id.
  • Pozn. k řešení: V tomto případě načteme domy agenta 007 rychleji ... místo 250 stačí (2 + 2) IO operací (dvě na zalezení do indexu a pak načtení cca 5 domů - ty se při blokovacím faktoru 4 vlezou do 2 stránek).

17.1.2008

Stupnica 24-21 - 1; 20-19 - 2; 18-17 - 3

• 1.) Schéma:

+---------+    +---------+    +---------+
|  Herec  |    | Hraje_v |    |  Film   |
+---------+    +---------+    +---------+
| HerecId | -- | HerecId |  / | FilmId  |
| Jméno   |    | FilmId  | /  | Titul   |
| Adresa  |    +---------+    | Režisér |
+---------+                   +---------+

 - vybrat všetkých hercov, ktorí hrali vo vsech filmoch režírovaných Formanom (3b)
 - vybrat všetkých režisérov, kteří nehrali v žiadnom svojom filme (3b)

• 2.) Upraviť schéma z 1.) na OR model s tým, že do databáze pribudneú aj iné osoby. Bolo potreba použiť typy a referencie s cieľom odstrániť FilmId a HerecId a vo výsledku mali byť 3 relácie (3b).
  • Napísať v tomto novom shémate dotaz D3: Pre každého herca zistiť počet Formanových filmov (režírovaných Formanom) do ktorých boli obsadení.

• 3.) Čosi z DIS - ako sa budú meniť ( - znižovať, + zvyšovať) P a R ak sa použije:
  • Boolean operátor AND
  • Boolean operátor OR
  • zástupné znaky
  • (spolu asi 11 vecí)

• 4.) Definovať inverznú frekvenciu dokumentu (IDF)

• 5.) Počítací príklad na spojenie relácií R * S pomocou hniezdených cyklov: p_R = 2000, b_R = 20, p_S = 5000, b_S = 50 (1b)

• 7.) (3b) Napísať postup ako z:

((R[B=C]S)[D=E]T)[A] 

pomocou aspoň troch krokov vznikne:

((T[E][E=D]S[ACD])[C=B]R)[A]

• 8.) Boli dané relácie:

+----------+    +----------+    +----------+
|  Agent   |    |  Dum_id  |    | Vybaveni |
+----------+    +----------+    +----------+
| Agent_id | \  | Dun_id   | -- | Dum_id   |
| Jmeno    |  \ | Agent_id |    | Rys      |
+----------+    +----------+    +----------+

domov je 1000, agentov 2000, vybaveni 10 000, sú známe blokovacie faktory na tabuľke domov je klastrovany index cez ??, na vybaveni je B+ normalni index cez ??

a) Nakreslite strom dotazu

SELECT nazev, vybaveni_id 
  FROM dum, vybaveni, agent
 WHERE dum.dum_id = agent.dum_id 
   AND vybaveni.rys = '5+1'
   AND agent.id='007' 
   AND vybaveni.dum_id = dum_id

b) dotaz optimalizujte a spočítajte IO.

c) nakreslite strom optimalizovaného dotazu (ak je rozdielny od Vášho prvého stromu)

31.1.2007

• 1) Tri relacie, urobit nad nimi dva dotazy v SQL92. (3+2 body)
• 2) V SQL:1999 napisat pre dve z tych relacii ADT a na zaklade nich vytvorit tabulky, s vazbou medzi nimi. (3)
• 3) Nad tymito dvomi tabulkami urobit dotaz. (2)
• 4) Dva texty, vektory model.
  • 4a) Vytvorit maticu podla TF*IDF. (2)
  • 4b) Definovat kosinusovu mieru. (1)
  • 4c) Pre dva dotazy urcit Sim (klasicke) a zoradit dokumenty podla relevancie. (2)
• 5) Pre relacie z otazky 1 su dane indexy (klastrovane a klasicke B+-stromy), ich vyska, statistiky poctu riadkov a blokovaci faktor
  • 5a) Nakreslit strom dotazu (akykolvek). (1)
  • 5b) Navrhnut optimalny plan a spocitat pocet I/O operacii. (3)
  • 5c) Pre tento optimalizovany dotaz nakreslit strom. (1)
  • 5d) Navrhnut novy optimalizovany plan, ak sa zmenia indexy. (3)

Celkom bolo 23 bodov, hodnotenie 20-23 za 1, 18-19 za 2, 16-17 za 3. Cas 90 minut.

19.1.2006

• 1. v sql92 vyjadrite v definicii tabulky FILM ze reziser byva tam co kino, + otazka co sa stane ak je reziser bezdomovec
• 2. kina v ktorych davaju len tie filmy ktorych reziser byva na rovnakej adrese
• 3. v xml-ql najst nejake podelementy zo zadanaeho xml, xml bolo zadane :)
• 4. kina kde davaju len jeden film
• 5. kina ktore davaju vsetko co dava kino blanik
• 6. uvazujem Sim(Q,D_i)=suma(q_k*w_ik) ---> taky ten vzorecek zo slejdov potom vyjadrite nenulovy Sim pomocou bool modelu ak je vektorovy model binarny
• 7. definujte koef. uplnosti a presnosti
• 8. co su datove typy list, bag, set v sql99
• 9. uvazujte typy entit osoba(atributy meno, adresa*), hviezdicka znaci ze adresa je viac hodnotovy atribut a ukol(atributy cislo_ukolu, nazov). kazda osoba riesi niekolko ukolov, kazdy z nich v nejakej kapacite poc_h. navrhnite v sql99 odpovedajuce uzivatelske typy dat a na zaklade tychto typov definujte prislusne tabulky. a este tam potom bol jeden dotaz na ale ten si napametam :)
• este tam boli nejake otazky na xml ...

10.2.2005

zkousene okruhy:

• SQL 92, 89 dotazy z oblasti KINO, FILM, .. celkem pohoda, jen to vymyslet
• IO pro tabulku + co kdyz reziruje bezdomovec (viz predchozi prispevky)
• UNION JOIN - stejena otazka jako tady byla (vyjde prazdna tabulka)
• SQL 99 - definovat tabulku s pouzitim typu (tez definovat) a reference + napsat zadanej dotaz nad tim
• DIS definovat miru TF*IDF (napsal jsem nejakou sumu + log a stacilo)
• DTD napsat schema (nemel jsem tam zadny hvezdicky coz je ve vetsine pripadu blbe - elementy se pak nesmely opakovat, tak pozor na to)
• XML-QL dotaz na vsechny podelementy elemetu

7.2.2005

• 1)-6) byly selecty nad danou databazi napsane prostredky SQL89:
  • databaze Studio
  • Dava(nazef_f,nazev_k);
  • Film(nazev_f,reziser);
  • Kino(nazev_k,adresa);
  • D1(1 bod) Filmy, co davaji nekde.
  • D2(3 body) Filmy, co davaji vsude.
  • D3(2 body) Filmy, co nedavaji nikde.
  • D4(3 body) Kina, kde davaji vsechny filmy.
  • D5(2 body) Kina, kde davaji jen Kolju.
  • D6(3 body) Kina, kde davaji vsechny filmy rezisera Sveraka a nic jineho.
  • D7(1 bod) vyjadrit D3 pomoci SQL92

• 8) (3 body) popiste pojeti ADT v SQL99

• 9) (2 body) vyjadrete NATURAL JOIN prostredky SQL89, konkretne mame tabulky R(A,B,C) a S(D,A,C) a mame vyjadrit pomoci sql89 prikaz "SELECT B FROM R NATURAL JOIN S"

• 10) (1+2body) uvazujeme dva texty a vektorovy model dat:
  • A Rano, rano, ranicko. Bude prset. Bude hodne prset.
  • B Rano bude prset. Kazde rano bude prset.
  • a) definujte TF a IDF
  • b) zkonstrujte matici dokumenty*termy zalozenou na TF*IDF
  • Uvazujte pouze vyznamova slova, nehledte na koncovky podstatnych jmen. Eventualne symbolicke logaritmy vyjadrete pouze symbolicky.
  • // slova rano a ranicko se daly brat jako jeden term, slovo "bude" zrejme neni vyznamove slovo

• 11) (2 body) K databazi Studio navrhnete DTD tak, aby byla zachovana referencni integrita mezi strukturou Dava a strukturami Film a Kino.

Hodnocení: 16-18 bodu 3, 19-22 bodu 2, 23-26 bodu 1

22.1.2005

• 1. Napsat SQL selecty nad nejakym zadanym DB schematem. Vetsinou se tam pouzival EXISTS, nekde GROUP BY a HAVING, jendou se dalo urychlit pomoci EXCEPT... cele to melo byt SQL92.
• 2. Dve tabulky T1(A,B,C) a T2(B,C,D), byly v nich i hodnoty a bylo treba napsat jak vypada RIGHT OUTER JOIN. (Bez ON, cili to byl asi NATURAL)
• 3. Napsat SEMIJOIN tech tabulek... tak to netusim, co je. (semijoin)
• 4. Napsat DTD definici databaze z prikladu 1. Cili <!ATTLIST>, <!ELEMENT>... bylo treba vedet celou syntax DTD.
• 5. Dva texty s podtrzenymi termami, dva DIS dotazy, udelat TF a IDF, udelat vahy D, pak na to poslat ty dotazy a spocitat (klasicky skalarni soucin).
• 6. Napsat XQL2 (v praxi je to X-Path) dotaz nad zadanym XML. Bylo potreba najit vsechna tel a fax cisla osob, cili: osoba/(tel|fax)