M veletek a relációs modellben • A felhasználónak szinte állandó jelleggel szüksége van az adatbázisban eltárolt adatok egy részére. • Megfogalmaz egy kérést, amelyben leírja, milyen adatokra van szüksége, az adatbázis nyelvezetében ezt lekérdezésnek nevezzük.
A relációs adatmodell m veleteire kétféle jelölést használunk: – relációs algebra, mely algebrai jelölést használ, a lekérdezéseket algebrai operátorok segítségével adja meg; – relációs kalkulus, mely matematikai logikán alapul, a lekérdezést logikai formulák segítségével adja meg. A relációs algebra és a relációs kalkulus ekvivalens: o egy relációs algebrai lekérdezés átalakítható egy relációs kalkulusbeli lekérdezéssé és fordítva (lásd [Ul89]).
Relációs algebra – A relációs algebrai m veletek operandusai a relációk. – A relációt a nevével szokták megadni, például R vagy Alkalmazottak. – Az operátorokat alkalmazva a relációkra, eredményként szintén relációkat kapunk, ezekre ismét alkalmazhatunk relációs algebrai operátorokat, így egyre bonyolultabb kifejezésekhez jutunk. – Egy lekérdezés tulajdonképpen egy relációs algebrai kifejezés.
– A relációs algebrai m veletek esetén szükségünk lesz feltételekre. – A feltételek a következ típusúak lehetnek: = <>
<
<=
> >=
IS IN
IS NOT IN
NOT
OR AND
(melynek egy attribútuma van)
Relációs algebra m veletei – Az els öt az alapvet m velet, a következ ket ki tudjuk fejezni az els öt segítségével. 1) Kiválasztás (Selection): • Az R relációra alkalmazott kiválasztás operátor f feltétellel olyan új relációt hoz létre, melynek sorai teljesítik az f feltételt. • Az eredmény reláció attribútumainak a száma megegyezik az R reláció attribútumainak a számával. • Jelölés: σf (R).
Grafikusan ábrázolva, ha az R reláció a nagy téglalap, a kiválasztás eredménye a befestett rész.
példa: Keressük a kis kereset alkalmazottakat (akinek kisebb, vagy egyenl a fizetése 500 euró-val). A lekérdezés a következ :
σFizetés <= 500 (Alkalmazottak) A lekérdezés eredménye: SzemSzám Név 111111 Nagy Éva 222222 Kiss Csaba 333333 Kovács István
RészlegID Fizetés 2 300 9 400 2 500
példa: Keressük a 9-es részleg nagy fizetés alkalmazottait (akinek 500 euró-nál nagyobb a fizetése). A lekérdezés:
σFizetés > 500 AND RészlegID = 9 (Alkalmazottak) Az eredmény: SzemSzám Név 456777 Szabó János
RészlegID 9
Fizetés 900
2) Vetítés (Projection): Adott R egy reláció A1, A2,..., An attribútumokkal. • A vetítés eredménye: reláció, mely R-nek csak bizonyos attribútumait tartalmazza. • Ha kiválasztunk k attribútumot az n-b l: Ai1 , Ai2 , , Aik -et, és ha esetleg a sorrendet is megváltoztatjuk, az eredmény reláció a kiválasztott k attribútumhoz tartozó oszlopokat fogja tartalmazni, viszont az összes sorból. • az eredmény is egy reláció, nem lehet két azonos sor a vetítés eredményében, az azonos sorokból csak egy marad az eredmény relációban. • Jelölés: π Ai , Ai , , Ai ( R) 1
2
k
Grafikusan ábrázolva, ha az R reláció a nagy téglalap, a vetítés eredménye a befestett rész.
példa: Ha az Alkalmazottak relációból csak az alkalmazott neve és fizetése érdekel, akkor a következ m velet eredménye a kért reláció:
π Név, Fizetés (Alkalmazottak) Az eredmény:
Név Nagy Éva Kiss Csaba Szabó János Szilágyi Pál Vincze Ildikó Kovács István
Fizetés (euró) 300 400 900 700 800 500
példa: CREATE TABLE Diákok ( BeiktatásiSzám INT PRIMARY KEY, Név VARCHAR(50), Cím VARCHAR(100), SzületésiDatum DATE, CsopKod CHAR(3) REFERENCES Csoportok (CsopKod), Átlag REAL ); π CsopKod (Diákok)
3) Descartes szorzat.
• adottak az R1 és R2 relációk • a két reláció Descartes szorzata (R1 × R2) azon párok halmaza, amelyeknek els eleme az R1 tetsz leges eleme, a második pedig az R2 egy eleme. • az eredményreláció sémája az R1 és R2 sémájának egyesítése.
R1
A 12 24
R2
B 33 46
B C D 20 55 80 30 67 97 40 75 99
R1 × R2 eredménye:
A R1.B R2.B 12 33 20 12 33 30 12 33 40 24 46 20 24 46 30 24 46 40
C 55 67 75 55 67 75
D 80 97 99 80 97 99
4) Egyesítés. • adottak az R1 és R2 relációk, • R1 és R2 attribútumainak a száma megegyezik, • ugyanabban a pozícióban lev attribútumnak ugyanaz értékhalmaza, • a két reláció egyesítése tartalmazni fogja R1 és R2 sorait, • az egyesítésben egy elem csak egyszer szerepel, • jelölés: R1 U R2
az
5) Különbség. • adottak az R1 és R2 relációk, • R1 és R2 attribútumainak a száma megegyezik • ugyanabban a pozícióban lev attribútumnak ugyanaz az értékhalmaza • a két reláció különbsége azon sorok halmaza, amelyek R1-ben szerepelnek és R2-ben nem • jelölés: R1 − R2
R1
R2
Szem Szám 222222 456777 234555 333333 Szem Szám 111111 456777 123444
Név Kiss Csaba Szabó János Szilágyi Pál Kovács István Név Nagy Éva Szabó János Vincze Ildikó
RészlegID 9 9 2 2 RészlegID 2 9 1
Fizetés (euró) 400 900 700 500 Fizetés (euró) 300 900 800
R1 U R2: Szem Szám 222222 456777 234555 333333 111111 123444
Név
Részleg Fizetés ID (euró) Kiss Csaba 9 400 Szabó János 9 900 Szilágyi Pál 2 700 Kovács István 2 500 Nagy Éva 2 300 Vincze Ildikó 1 800
R1 - R2: Szem Név Részleg Fizetés Szám ID (euró) 222222 Kiss Csaba 9 400 234555 Szilágyi Pál 2 700 333333 Kovács István 2 500
Még vannak hasznos m veletek: ezek az öt alapvet kifejezhet ek.
m velettel
6) Metszet: • adottak az R1 és R2 relációk, • R1 és R2 attribútumainak a száma megegyezik • ugyanabban a pozícióban lev attribútumnak ugyanaz az értékhalmaza • a két reláció metszete: R1 ∩ R2 = R1 − ( R1 − R2 ) .
7) Théta-összekapcsolás ( -Join): • adottak az R1 és R2 relációk, • R1 és R2 relációk Descartes szorzatából kiválasztjuk azon sorokat, melyek eleget tesznek a feltételnek: R2 = σ θ ( R1 × R2 ) R1
példa: számítsuk ki: R1 R1
A 11 65 97
B C 23 32 76 82 76 82
R2 B 23 23 76
R2
A R1.B 11 23 11 23 11 23 65 76 97 76
R1.C 32 32 32 82 82
C 32 32 82 R2.B 23 23 76 76 76
D 44 57 99 R2.C 32 32 82 82 82
D 44 57 99 99 99
8) Természetes összekapcsolás (Natural join): • legyenek az R1 és R2 relációk • az R1 és R2 relációknak egy vagy több közös attribútuma van. • legyen B az R1, illetve C az R2 reláció attribútumainak a halmaza, • a közös attribútumok: B ∩ C = {A1, A2, …, Ap}. A természetes összekapcsolás: R1 R2 = π B∪C ( R1 ( R1 . A1 = R2 . A1 )∧( R1 . A2 = R2 . A2 )∧ ∧( R1 . Ap = R2 . Ap ) R2 , Ri.Aj jelöli az Aj attribútumot az Ri relációból, i {1,2}, j
{1,2, …, p}.
R1
R1 R2
A 11 65 97
B C 23 32 76 82 76 82
R2
A 11 11 65 97
B 23 23 76
B 23 23 76 76
C 32 32 82
D 44 57 99
C 32 32 82 82
D 44 57 99 99
• R1 és R2 relációk természetes összekapcsolása esetén azokat a sorokat párosítjuk össze, amelyek értékei az R1 és R2 összes közös attribútumán megegyeznek, • legyen r1 az R1 egy sora és r2 az R2 egy sora, ekkor az r1 és r2 párosítása akkor sikeres, ha az r1 és r2 megfelel értékei megegyeznek az összes A1, A2, …, Ap közös attribútumon. • ha az r1 és r2 sorok párosítása sikeres, akkor a párosítás eredményét összekapcsolt sornak nevezzük, • az összekapcsolt sor megegyezik az r1 sorral az R1 összes attribútumán és r2 sorral az R2 összes attribútumán, • az R1 R2 eredményében R1 és R2 közös attribútumai csak egyszer szerepelnek.
példa: Szállít Szállítók:
Áruk:
Szállítók
Áruk
SzállID SzállNév 111 Rolicom 222 Sorex ÁruID ÁruNév 45 Milka csoki 67 Heidi csoki 56 Milky way
SzállCím A.Iancu 15 22 dec. 6 MértEgys tábla tábla rúd
Szállít:
SzállID 111 222 111 111 222 222
ÁruID 45 45 67 56 67 56
Ár 2.5 2.6 1.7 2.1 1.8 2.2
Szállít
Szállítók eredménye: SzállID 111 222 111 111 222 222
SzállNév SzállCím Rolicom A.Iancu 15 Sorex 22 dec. 6 Rolicom A.Iancu 15 Rolicom A.Iancu 15 Sorex 22 dec. 6 Sorex 22 dec. 6
ÁruID 45 45 67 56 67 56
Ár 2.5 2.6 1.7 2.1 1.8 2.2
Szállít
Szállítók
SzállID SzállNév 111 222 111 111 222 222
Rolicom Sorex Rolicom Rolicom Sorex Sorex
Áruk eredménye: SzállCím
A.Iancu 15 22 dec. 6 A.Iancu 15 A.Iancu 15 22 dec. 6 22 dec. 6
Áru ID 45 45 67 56 67 56
ÁruNév Milka csoki Milka csoki Heidi csoki Milky way Heidi csoki Milky way
Mért Egys Tábla Tábla Tábla Rúd Tábla Rúd
Ár 2.5 2.6 1.7 2.1 1.8 2.2
• relációs algebrai m veletek alkalmazásával újabb relációkat kapunk, • szükséges egy olyan operátor, amelyik átnevezi a relációkat. 9) Átnevezés: • R(A1, A2, …, An) egy reláció, • ρ S ( B1 , B2 , , Bn ) ( R) az átnevezés operátor az R relációt S relációvá nevezi át, az attribútumokat pedig balról jobbra B1, B2, …, Bn-né, • ha az attribútum neveket nem akarjuk megváltoztatni, akkor ρ S ( R) operátort használunk.
10) Hányados (Quotient): • R1 reláció sémája: {X1, X2,…, Xm, Y1,Y2,…,Yn}, • R2 reláció sémája pedig: {Y1, Y2, …, Yn}, • R1 az osztandó, R2 az osztó. Jelölés: X = {X1, X2,…, Xm}, Y = {Y1,Y2,…,Yn}. R1 (X, Y), R2 (Y) hányadosát jelöljük: R1 DIVIDE BY R2 (X)-el a hányados reláció sémája {X1, X2,…, Xm}. A hányados relációban megjelenik egy x sor, ha minden y sorra az R2b l az R1-ben megjelenik egy r1 sor, melyet az x és y sorok összeragasztásából kapunk.
példa: A = π ÁruID (Áruk) , S = π SzállID, ÁruID (Szállít) a következ sorok az S relációban:
SzállID ÁruID S1 A1 S1 A2 S1 A3 S1 A4 S1 A5 S1 A6 S2 A1 S2 A2 S3 A2 S4 A2 S4 A4 S4 A5
a) A reláció:
ÁruID A1
S DIVIDE A(SzállID) eredménye:
SzállID S1 S2
b) A reláció:
ÁruID A2 A4 S DIVIDE A(SzállID):
SzállID S1 S4
c) A reláció:
S DIVIDE A(SzállID):
ÁruID A1 A2 A3 A4 A5 A6 SzállID S1
Lekérdezések megfogalmazása relációs algebrai m veletek segítségével • relációs algebra segítségével tetsz leges bonyolultságú kifejezéseket képezhetünk. • az operátorokat alkalmazhatjuk adott relációkra, illetve más operátorok alkalmazásának eredményeként kapott relációkra. • relációs algebrai m veletek megfogalmazásakor zárójeleket használhatunk az operándusok csoportosítása érdekében. • relációs algebrai kifejezéseket megadhatunk kifejezésfával is
példa: Legyenek a Szállítók, Áruk, Szállít relációk lekérdezés: „Keressük a ’Milka csoki’-t szállító cégek nevét.” A: lépésekre felbontva: MCsokiIDk = π ÁruID (σ ÁruNév ='Milka csoki'(Áruk)) MCsokiAjánlatok = σ ÁruID IN MCsokiIDk (Szállít) MCsokiSzállítóIDk = π SzállID (MCsokiAjánlatok) McsokiSzállítóNevek = π SzállNév (σ SzállID IN MCsokiSzállítóIDk (Szállítók))
B: π SzállNév (σ ÁruNév ='Milka csoki'(Szállít
Szállítók
Áruk))
„Keressük azon szállítókat, akik nem szállítják a 67-es ID-j árut”. Száll67 = π SzállID (σ ÁruID =67 (Szállít)) NemSzáll67 = π SzállID (Szállítók) − Száll67 Nem2Száll67 =π SzállID (σ ÁruID <>67 (Szállít)) Kérdés: Mi a különbség NemSzáll67 és Nem2Száll67? Ahhoz, hogy megkapjuk a szállító nevét:
π SzállNév ( NemSzáll67
Szállítók)
példa: „Keressük azon szállítókat, kik szállítják az összes árut.”
π SzállNév ( ((π SzállID, ÁruID (Szállít) ) DIVIDE BY (π ÁruID (Áruk) ))
Szállítók)
Osztáshoz egy bináris és egy unáris relációra van szükség. • a bináris reláció: π SzállID, ÁruID (Szállít) • az unáris pedig: π ÁruID (Áruk) . Az osztás eredménye tartalmazni fogja azon szállítók ID-jét, akik az összes árut szállítják.
példa: „Keressük azon szállítókat, akik legalább azon árukat szállítják, melyeket az 111 ID-jú szállító szállít.” π SzállNév ( ((π SzállID, ÁruID (Szállít) ) DIVIDE BY (π ÁruID (σ SzállID=111 (Szállít)) ) Szállítók) 1. áru ID-k, melyeket szállít a 111-es ID-j szállító: π ÁruID (σ SzállID=111 (Szállít)) 2. az osztás segítségével meghatározzuk azon szállító ID-kat, akik szállítják legalább az el z lekérdezésben megkapott árukat.
példa: „Keressük azon szállítókat, akik csak a 67-es ID-j szállítják.” π SzállNév ( ((π SzállID (σ ÁruID=67 (Szállít)) ) − (π SzállID (σ ÁruID<>67 (Szállít)) )
árut
Szállítók)
1. szállítók, akik a 67-es ID-j árut szállítják: π SzállID (σ ÁruID=67 (Szállít)) ezek között azok is szerepelnek, akik a 67-es ID-j árun kívül még más árukat is szállítanak.
2. π SzállID (σ ÁruID<>67 (Szállít)) megadja azokat a szállítókat, akik a 67-esen kívül akármi más árut szállítanak. Ezek között a szállítók között szerepelnek azok: • akik a 67-est és mást is szállítanak • akik nem szállítják a 67-es árut, de szállítanak mást. A különbség segítségével kiküszöböljük azokat a szállítókat, akik a 67est és mást is szállítanak. Azok, akik nem szállítják a 67-est, de mást igen a különbség eredményében nem fognak szerepelni. Ebben azok a szállítók fognak szerepelni, akik csak a 67-est szállítják.
Lekérdezések optimalizálása • minden ABKR-nek van lekérdezés−feldolgozó rendszere, mely a lekérdezést relációs algebrai m veletek sorozatává alakítja, • egy lekérdezést több relációs algebrai kifejezéssé is alakíthatjuk, amelyek ugyanazt az eredményt adják, ezeket ekvivalens kifejezéseknek nevezzük, • a lekérdezés optimalizáló feladata, hogy az ekvivalens kifejezések közül kiválassza a leggyorsabban kiértékelhet kifejezést, • a relációs algebrai m veletek tulajdonságait felhasználva a kifejezéseket átalakíthatjuk.
Relációs algebrai m veletek algebrai tulajdonságai Ekvivalencia jele: ↔ R reláció sémája A = { A1 , A2 ,..., An } , S sémája B = {B1, B2, …, Bm} T sémája C = {C1, C2, …, Ck}, ahol n, m, k – Join kommutatív:
N az attribútumok száma.
R S↔S R – Bináris m veletek asszociatívak: ( R × S ) × T ↔ R × (S × T ) (R
S)
T↔R
(S
T)
– Unáris m veletek idempotensek: Ha ugyanarra a relációra több vetítést alkalmazunk, ezeket '⊆ A i A'⊆ A' ' , akkor: csoportosíthatjuk, ha A'⊆ A, A'
π A'(π A''( R)) ↔ π A'( R) Ha több kiválasztást (σ p ( A ) ) ugyanarra a relációra vonatkozik, i
i
ezeket csoportosíthatjuk, ahol pi az Ai attribútumra alkalmazott feltétel: σ p1 ( A1 ) (σ p2 ( A2 ) ( R)) ↔ σ p1 ( A1 )∧ p2 ( A2 ) ( R)
- Vetítés és kiválasztás sorrendje felcserélhet :
π A ,..., A (σ p ( A ) ( R)) ↔ π A ,..., A (σ p ( A ) (π A ,..., A , A ( R))) 1
n
p
1
n
p
1
n
p
• ha a vetítést a kiválasztás el tt akarjuk végrehajtani, akkor az Ap attribútumnak kell szerepelnie a vetítés attribútumai között. • ha Ap { A1 ,..., An }, akkor az utolsó vetítés az { A1 ,..., An } attribútumokra jobb oldalon fölösleges.
– Kiválasztás és bináris m veletek sorrendje felcserélhet : (Emlékeztet : Ai az R reláció attribútuma). σ p ( Ai ) ( R × S ) ↔ (σ p ( Ai ) ( R)) × S
σ p( A ) (R i
p ( A j , Bk )
S ) ↔ σ p ( Ai ) ( R )
p ( A j , Bk )
S
– A kiválasztás és egyesítés sorrendje felcserélhet , ha az R és T relációk sémája ugyanaz: σ p ( Ai ) ( R ∪ T ) ↔ σ p ( Ai ) ( R) ∪ σ p ( Ai ) (T )
- Vetítés és bináris m veletek sorrendje felcserélhet : Legyen A'⊆ A , B '⊆ B , C = A '∪ B ', akkor:
π C ( R × S ) ↔ π A ( R) × π B ( S ) π C ( R p ( Ai , B j ) S ) ↔ π A ( R) p ( A , B ) π B ( S ) '
'
'
ahol Ai ∈ A'és B j ∈ B ' . π C ( R ∪ S ) ↔ π C ( R) ∪ π C ( S )
i
j
'
• A gyakorlatban a Descartes szorzatot nem célszer használni, mivel ez a legköltségesebb m velet. • A természetes összekapcsolás is drága m velet, a gyakran használatosak közül a legdrágább. • Az ABKR lekérdezés optimalizálója a join-t nem úgy végzi, hogy Descartes szorzatot elkészíti és abból kiválogatja az összepárosítható sorokat. • Több algoritmus is létezik a join végrehajtására, egyik az ún. merge-join, mely a közös attribútum szerint rendezett összekapcsolandó relációt egy új relációba fésüli össze.
„Keressük a ’Milka csoki’-t szállító cégek nevét.” más megoldás: C: π SzállNév σ ÁruNév='Milka csoki' Áruk) Szállít
Szállítók)
• A relációs algebrai kifejezéseket kifejezésfával is megadhatjuk. • Az el bbi relációs algebrai kifejezés kifejezésfája a következ ábrán látható. • A lekérdezés végrehajtását, illetve optimalizálását lásd részletesebben a [MoUlWi00]-ben.
π SzállNév
Szállítók
σ AruNev='Milka csoki'
Áruk
Szállít
