Informatika szigorlat 11-es t´etel: Lek´erdez˝o nyelvek
1.
Rel´ aci´ os algebra
A rel´aci´os algebra egy speci´alis algebra, amely n´eh´ any egyszer˝ u, de hathat´os m´odszert ad arra n´ezve, hogy mik´ent ´ep´ıthet¨ unk u ´j rel´aci´ okat a r´egi rel´aci´okb´ol. A rel´aci´os algebrai kifejez´esek alapjait k´epezik a rel´aci´ ok, mint operandusok. Egy rel´aci´o megadhat´o a nev´evel vagy k¨ozvetlen¨ ul, sorainak egy list´aj´aval. Ezut´an, alkalmazva az oper´atorokat a rel´aci´ okra vagy egyszer˝ ubb rel´aci´os algebrai kifejez´esekre, fokozatosan egyre bonyolultabb kifejez´eseket ´ep´ıthet¨ unk fel. Egy lek´erdez´es tulajdonk´eppen egy rel´aci´ os algebrai kifejez´es. Ilyenform´an a rel´aci´ os algebra az els˝o konkr´et p´eld´ ank lek´erdez˝onyelvre. A rel´aci´os algebr´aban kev´es alapm˝ uvelet van, amelyek egyszer˝ uek (implement´alhat´ok). Mind a m´eretek ´es a kisz´am´ıt´ as becs¨ ulhet˝ o, emiatt j´ol lehet optimaliz´alni. A rel´aci´os algebr´anak nagy kifejez˝oereje van. R(A1 , A2 , . . . , An ), ahol R a rel´aci´ o neve, ´es Ai az attrib´ utum neve.
1.1.
Alapm˝ uveletek
• Uni´o: R1 (A1 , . . . , An ) r1 R2 (A1 , . . . , An ) r2 ⇒ r1 ∪ r2 − R(A1 , . . . , An ) • Kivon´as: R1 (A1 , . . . , An ) r1 R2 (A1 , . . . , An ) r2 ⇒ r1 − r2 − R(A1 , . . . , An ) Azok a sorok, amelyek r1 -ben benne vannak, de r2 -ben nincsenek. • Szorz´as: R1 (A1 , . . . , An ) r1 R2 (B1 , . . . , Bl ) r2 ⇒ r1 × r2 R(A1 , . . . , An , B1 , . . . , Bl ) sorok sz´ama szorz´odik: |r1 × r2 | = |r1 | · |r2 | • Vet´ıt´es: R(A1 , . . . , An ) r ´es B1 , . . . , Bk ∈ {A1 , . . . , An } πB1 ,...,Bk (r) = {t[B1 . . . Bk ] | t ∈ r} • Kiv´alaszt´as: Atomi felt´etel: – AΘc 1
– cΘA – Ai ΘAj ahol c konstans, ´es Θ ∈ {=, 6=, <, >, ≤, ≥} ¨ Osszetett felt´etel: Atomi felt´etel +{∧, ∨, ¬} R(A1 , . . . , An ) r : σF (r) = {t ∈ r|F (t) = igaz} ´ • Atnevez´ es: %A→B (r)
1.2.
Levezethet˝ o m˝ uveletek
• Metszet: R ∩ S = (R ∪ S) − ((R − S) ∪ (S − R)) = R − (R − S) • Hivatkoz´as: R.Ai • Term´eszetes ¨osszekapcsol´as: R(A, B) ./ S(B, C) = = πR.A,R.B,S.C (σR.B=S.B (r × s)) • H´anyados: R(A1 , . . . , An , B1 , . . . , Bm ) r S(B1 , . . . , Bm ) s ⇒ r ÷ s → (A1 , . . . , An ) ´es (r ÷ s) × s ⊆ r r ÷ s a legnagyobb olyan t´abla, aminek (A1 , . . . , An ) a s´em´ aja, ´es s-sel visszaszorozva ⊆ r. r ÷ s = πA (r) − (πA (πA (r) × s − r)) • F´elig ¨osszekapcsol´as (semi join): r n s = πR (r ./ s) • Th´eta ¨osszekapcsol´as r ./θ s = σθ (r × s), ahol θ tetsz˝ oleges logikai kifejez´es.
1.3.
M˝ uveletek tulajdons´ agai
Def.:f monoton n¨oveked˝o kifejez´es, ha ∀ri ⊆ ri0 eset´en f (r1 , . . . , rk ) ⊆ f (r10 , . . . , rk0 ) ´ All.: ∪,×,π,σ,./ monoton. A − nem monoton. ´ All.: ./, ×, ∩ ´es a ∪ m˝ uveletek asszociat´ıvak ´es kommutat´ıvak. 1. πA (πB (E)) = πA (E),ha A ⊆ B 2. σF2 (σF1 (E)) = σF2 ∧F1 (E) = σF1 (σF2 (E)) 3. Ha attr(F ) = A∪B ´es A∩B = ∅, akkor πA (σF (E)) = πA (σF (πAB (E)) 4. Ha F = F1 × F2 ´es attr(Fi ) ⊆ attr(Ei ), akkor σF (E1 × E2 ) = σF (E1 ) × σF (E2 ) 2
5. Ha F = F1 × F2 ´es attr(Fi ) ⊆ attr(Ei ), akkor πF (E1 × E2 ) = πF (E1 ) × πF (E2 ) 6. σF (E1 ∪ E2 ) = σF (E1 ) ∪ σF (E2 ) 7. πF (E1 ∪ E2 ) = πF (E1 ) ∪ πF (E2 ) 8. σF (E1 − E2 ) = σF (E1 ) − σF (E2 ) 9. Ha attr(F ) ⊆ attr(E1 ) ∩ attr(E2 ) akkor σF (E1 ./ E2 ) = σF (E1 ) ./ σF (E2 ) 10. πA (E1 ∪ E2 ) = πA (E1 ) ∪ πA (E2 ) 11. Ha A = B ∪ C ´es B ⊆ attr(E1 ) ´es C ⊆ attr(E2 ), akkor πA (E1 × E2 ) = πB (E1 ) × πC (E2 )
Rel´ aci´ os komponenskalkulus(DRC)1
2. Q={
x , x , . . . , xn | 1 2{z }
|F (x1 , x2 , . . . , xn )} – ez egy DRC lek´erdez´es
az F ¨ osszes szabad v´ altoz´ oja
F itt egy formul´at jel¨ol.
2.1.
Formul´ ak
• Atomi formula: p(t1 , . . . , tk ) ahol ti szabad el˝ofordul´ as´ u v´altoz´ o vagy konstans. p(c1 , . . . , ck ) ←→ (c1 , . . . , ck ) ∈ P (t´ abla) • xΘy, ahol x ´es y szabad el˝ofordul´ as´ uak ´es Θ ∈ {=, 6=, <, >, ≤, ≥} • F1 ´es F2 formula ⇒ (F1 ∧ F2 ),(F1 ∨ F2 ) ´es ¬F1 is formul´ ak • Ha F formula, akkor (∀x)F ´es (∃x)F is formula, de ezekben x-nek m´ar nincs szabad el˝ofordul´asa. Def.: Egy v´altoz´o szabad el˝ofordul´ as´ u, ha nem hat r´a kvantor. Def.: Egy formul´anak x szabad v´altoz´ oja, ha van minimum egy szabad el˝ofordul´asa. Csak szabad v´altoz´okkal ´ep´ıtj¨ uk fel a formul´ akat!! 1
Ezt szok´ as tartom´ anykalkulusnak is nevezni
3
2.2.
M˝ uveletek
• E1 ∪ E2 ←→ {x1 , . . . , xn |F1 (x1 , . . . , xn ) ∨ F2 (x1 , . . . , xn )} • E1 − E2 ←→ {x1 , . . . , xn |F1 (x1 , . . . , xn ) ∧ ¬F2 (x1 , . . . , xn )} • E1 × E2 ←→ {x1 , . . . , xn , y1 , . . . , yn |F1 (x1 , . . . , xn ) ∧ F2 (y1 , . . . , yn )} • σ$i θ$j (E1 ) ←→ {x1 , . . . , xn |F1 (x1 , . . . , xn ) ∧ xi θxj } • π$1 ,...,$k (E1 ) ←→ {x1 , . . . , xk |∃y1 , . . . , yn−k : F1 (x1 , . . . , xk , y1 , . . . , yn−k )}
3.
Tartom´ anyf¨ uggetlens´ eg, biztons´ agoss´ ag
Def.: dom(F ) = {F konstansai } ∪ {F rel. predik´atumainak megfelel˝o t´abl´akban szerepl˝o ´ert´ekei} Def.: F tartom´anyf¨ uggetlen formula, ha ∀D ⊇ dom(F ) eset´en R(F, D) = R(F, dom(F )). T´etel : Nincsen olyan algoritmus, amely tetsz˝oleges F -r˝ol eld¨onten´e, hogy tartom´anyf¨ uggetlen-e. A biztons´agos DRC lek´erdez´esek olyan bizonyos szintaktikai felt´eteleket kiel´eg´ıt˝o k´erd´esek, melyek biztosan tartom´anyf¨ uggetlenek, ´es ezek a szintaktikai felt´etelek k¨onnyen ellen˝orizhet˝ oek, szemben a tartom´anyf¨ uggetlens´eggel. Megszor´ıt´asok a k¨ovetkez˝oek: • A kifejez´esben nem szerepel a ∀ kvantor. • F1 ∨ F2 eset´en F1 ´es F2 szabad v´altoz´ oi ugyanazok. • F1 ∧. . .∧Fn maxim´alis konjunkci´ os l´anc eset´en a formul´ akban szerepl˝o v´altoz´o korl´atozott, azaz – valamelyik Fi egy p predik´ atum, amelyben szerepel az x v´ altoz´ o, vagy – x = c, ahol c konstans, vagy – x = y, ahol y korl´atozott v´altoz´ o, vagy – valamelyik Fi ∃F alak´ u, ahol az x az F -ben korl´ atozott vagy – valamelyik Fi F 1 ∨ F 2 alak´ u, ahol x F 1 -ben vagy F 2 -ben korl´ atozott. • ¬F csak olyan maxim´alis konjunkci´ os l´ancban szerepelhet, amelyben van pozit´ıv tag is. Egy adott F formula eset´en a biztons´agoss´ agot a k¨ovetkez˝ ok´eppen ellen˝orizhetj¨ uk: az els˝o l´ep´esben F ¨ osszes r´eszformul´ aj´ ara megvizsg´aljuk az els˝o k´et felt´etel teljes¨ ul´es´et, ha minden r´eszformula megfelel a k¨ovetelm´enyeknek, akkor az F -hez tartoz´o logikai kifejez´esf´ aban alulr´ol felfel´e haladva 4
vessz¨ uk a maxim´alis konjunkci´ os l´ancokat, ´es ellen˝orizz¨ uk a harmadik ´es negyedik tulajdons´agokat.
4.
Rel´ aci´ os sorkalkulus(TRC)
Ebben az esetben egy sort tekint¨ unk v´altoz´ onak. Q = {t(n) | F (t(n) )}, ahol F formula ´es t az egyetlen szabad sorv´altoz´ oja.
4.1.
Formul´ ak
• Atomi formula: p(t(n) ), ahol p egy n dimenzi´ os predik´atum szimb´ olum, ´es t szabad el˝ofordul´as´ u sorv´altoz´ o. • t[i]Θkonst konstΘt[i] t[i]Θt0 [j] is formul´ak,ahol t ´es t0 szabad el˝ofordul´ as´ u. • F1 ´es F2 formul´ak ⇒ F1 ∨ F2 , F1 ∧ F2 ´es ¬F1 is formul´ ak. • F -nek t szabad el˝ofordul´ as´ u sorv´altoz´ oja, akkor ∀t F ´es ∃t F nem lesznek formul´ak.
4.2.
M˝ uveletek
• E1 ∪ E2 ←→ {t |F1 (t) ∨ F2 (t)} • E1 − E2 ←→ {t |F1 (t) ∧ ¬F2 (t)} • E1 × E2 ←→ {t(n+m) |∃u(n) ∃v (m) : (F1 (u) ∧ F2 (v) ∧ t[1] = u[1]∧ ∧ . . . ∧ t[n] = u[n] ∧ t[n + 1] = v[1] ∧ . . . ∧ t[n + m] = v[m])} • π$1,...,$k (E) ←→ {t(k) |∃u(F (u) ∧ u[1] = t[1] ∧ . . . ∧ u[k] = t[k])} • σ$i θ$j (E) ←→ {t |F (t) ∧ t[i]θt[j]}
5.
SQL
Az SQL a rel´aci´os adatb´azisok programnyelve. Az SQL-t (Structured Query Language) a 70-es ´evekben az IBM-n´el fejlesztett´ek ki. Az SQL utas´ıt´asait oszt´alyozz´ ak: • Adatdefini´al´as (Data Definition Language – DDL): azok az utas´ıt´ asok tartoznak ide, amelyekkel a s´em´ akat ´es a benn¨ uk tal´alhat´ o objektumokat hat´arozhatjuk meg, p´eld´ aul: create table, create schema, create view stb.
5
• Adatm´odos´ıt´as (Data Manipulation Language – DML): az ide tartoz´o parancsok adatok t´arol´ as´ ara, m´odos´ıt´ as´ ara szolg´alnak, p´eld´ aul: insert, update, delete. • Lek´erdez´es (Query Language – QL). No comment, select... • Adatszab´alyoz´as (Data Control Language – DCL): ide a jogokkal kapcsolatos utas´ıt´asok tartoznak, p´eld´ aul: grant – jog ad´asa ´es revoke – visszavon´asa. Ezek csak a legfontosabb oszt´alyok, t¨obb is van m´eg, mint p´eld´ aul munkameneti utas´ıt´asok oszt´alya vagy hibakeres´esi utas´ıt´ asok oszt´alya.
5.1.
Parancsok
select ... from ... where... select distinct : duplik´atum elt´avol´ıt´ asa create table n´ ev(mezot´ ıpus); insert into n´ ev values(´ ert´ ek); select a a’ from r:csoport ´atnevez´ese a fejl´ecben select a*2+1 from r:aritmetika select a from r where a+4
Ebb˝ol az els˝o kett˝ot k¨otelez˝ o megadni, a t¨obbi opcion´alis. A where-rel lehet lek´erdez´es felt´eteleit megadni. A group by-t csoport k´epz´esre lehet alkalmazni. A having z´arad´ekkal az ¨osszes´ıt˝ o f¨ uggv´enyek ´ert´ekei alapj´an sz˝ urhet¨ unk. Az order by z´ arad´ekkal az eredm´eny rendezhet˝o, ´es asc ´es desc kifejez´esek hat´arozz´ak meg a rendez´es n¨ovekv˝ o ill. cs¨okken˝ o sorrendj´et.
5.2.
Programoz´ as
Gyakran kell az SQL parancsokat valamilyen szoftverfejleszt˝ o eszk¨ozzel elk´esz´ıtett (al)programok r´eszek´ent felhaszn´alni. Teh´ at adott egy befogad´o nyelv (p´eld´aul C), amiben a program k´esz¨ ul. A program k¨ ul¨ onb¨ oz˝ o r´eszeiben SQL utas´ıt´asokat helyeznek el az adatb´azisban t´arolt inform´aci´ ok el´er´es´ere. Ebben az esetben a programoz´o feladata az adatfeldolgoz´o algoritmusnak a befogad´o nyelven val´o megfogalmaz´asa, ´es a t´enyleges adatmanipul´aci´ o´ert felel˝os be´agyazott SQL utas´ıt´ asok programba szerkeszt´ese. A v´altoz´ok deklar´aci´oj´at k´et be´agyazott SQL utas´ıt´ as k¨oz´e kell tenni: EXEC SQL BEGIN DECLARE SECTION; ... EXEC SQL END DECLARE SECTION; Adatb´azishoz csatlakoz´as utas´ıt´ asa: EXEC SQL CONNECT. SQL utas´ıt´as v´egrehajt´as´ara k´et lehet˝os´eg van: el˝ok´esz´ıtett ´es az immediate utas´ıt´as: Az els˝o k´et utas´ıt´ asb´ ol ´all: EXEC SQL PREPARE n´ ev FROM: k´ erd´ es; EXEC SQL EXECUTE n´ ev (USING A1,...Ak); Akkor c´elszer˝ u ezt alkalmazni, ha SQL utas´ıt´ ast t¨obbsz¨ or is v´egre kell hajtani. A m´asik megold´as: EXEC SQL EXECUTE IMMEDIATE <mit hajtson v´ egre>; Ebben az esetben csak DML utas´ıt´asokat lehet v´egrehajtani.
7
