Adatbázisok - Relációs lekérdezések gyakorlat

Sor- és oszlopkalkulus példák megoldása

• Ezen a helyen volt linkelve a(z) megold3.pdf nevű fájl ("megold3.pdf" link szöveggel) a régi wiki http://wiki-old.sch.bme.hu/bin/view/Infoalap/AdatBazisokGyakorlat3 oldaláról. (Ha szükséged lenne a fájlra, akkor a pontos oldalmegnevezéssel együtt küldd el a wiki

  Hiba a bélyegkép létrehozásakor: Nem lehet a bélyegképet a célhelyre menteni

  @NO-SPAM.sch.bme.hu címre a kérésedet)

Engedy Balázs gyakorlatvezető megoldása a sor- és oszlopkalkulust használó feladatokra.

Relációk

M(unkahelyek) reláció:

1:név	2:foglalkozás	3:munkahely	4:kereset
Aladár	asztalos	OBI	1001
Béla	rendőr	BRFK	1002
Cecil	fogorvos	Rendelő	1003
Dezső	tanár	BME	1004
Elemér	tanár	ELTE	1005
Judit	fodrász	BjutiSzalon	1006
Kata	tanár	ELTE	1007
Lilla	igazgató	BjutiSzalon	1008
Mariann	rendőr	ORFK	1009
Nóra	műkörmös	BjutiSzalon	1010

N(ők) reláció:

1:név

Judit

Kata

Lilla

Mariann

Nóra

H(ázasságok) reláció:

1:férj	2:feleség
Aladár	Judit
Béla	Mariann
Elemér	Nóra

Az alábbi kérdéseket fogalmazzuk meg relációalgebra segítségével!

• Kik a relációkban szereplő férfiak?
  • Először kinyerjük az első relációból az összes ember listáját projekcióval, majd ebből kivonjuk a nők listáját: [math] (\pi_{\text{nev}}M)\setminus N [/math]
• Kik az egyedülálló nők?
  • Előállítjuk a házasságban élő nők listáját projekcióval a harmadik relációból, ezt kivonjuk az összes nő listájából: [math] N\setminus (\pi_\text{feleseg}H) [/math]
• Mely házaspárokban keres a nő jobban?
  • Ehhez először elő kell állítanunk az összes fizetéspár tábláját, nevekkel együtt, ezt M önmagával való szorzásával tesszük. Ezt szorozzuk még H-val is, hogy a házasságokra vonatkozó információ benne legyen, majd szelektáljuk azokat a sorokat, ahol az első M neve megegyezik a férjével, a második M neve megegyezik a feleségével, és az első H-ban lévő kereset kisebb, végül vetítjük, hogy csak a házaspár nevei maradjanak. [math] \pi_{H} (\sigma_{((M1.\text{nev}=H.\text{ferj}) \wedge (M2.\text{nev}=H.\text{feleseg}) \wedge (M1.\text{kereset} \lt M2.\text{kereset}))}(M\times M\times H)) [/math]
• Mely foglalkozásokat űzi mindkét nem?
  • Előállítjuk a nők foglalkozásait M és N szorzatából szelektálással és projekcióval, a férfiakét hasonlóan (a férfiak listáját az első feladathoz hasonlóan előállítva), majd a kettőnek vesszük a metszetét. [math] (\pi_\text{foglalkozas}(\sigma_{M.\text{nev}=N.\text{nev}}(N\times M)))\cap(\pi_\text{foglalkozas}(\sigma_{M.\text{nev}=\text{nev}}(((\pi_\text{nev}M)\setminus N)\times M))) [/math]
• Kik a házasságokban élő tanárok?
  • Vesszük M és H szorzatát, és kiválasztjuk azokat a sorokat, ahol a név az vagy a feleség vagy a férj nevével megegyezik, és a foglalkozás tanár, majd vetítéssel a nevet hagyjuk meg. [math] \pi_\text{nev}(\sigma_{(((\text{nev}=\text{feleseg})\vee(\text{nev}=\text{ferj}))\wedge(\text{foglalkozas}=\text{'tanar'}))}(M\times H)) [/math]
• Kik a BjutiSzalonban dolgozó nők férjei?
  • M és H szorzatából azokat szelektáljuk, ahol a név a feleség neve, és a munkahely a BjutiSzalon, majd vetítjük a férj attribútumra. [math] \pi_{ferj}(\sigma_{((\text{nev}=\text{feleseg})\wedge(\text{munkahely}=\text{'BjutiSzalon'}))}(M\times H)) [/math]
• Melyek azok a foglalkozások, amiket csak egy-egy ember űz?
  • Ezt legegyszerűbb a következő feladat megoldásából levezetni. A foglalkozások (M vetítve fogl.-ra) listájából kivonjuk azokat, amiket legalább ketten űznek. [math] (\pi_\text{foglalkozas}M)\setminus(\pi_{M1.\text{foglalkozas}}(\sigma_{((M1.\text{nev}\neq M2.\text{nev})\wedge(M1.\text{foglalkozas}=M2.\text{foglalkozas}))}(M\times M))) [/math]
• Melyek azok a foglalkozások, amiket legalább ketten űznek?
  • M-et magával szorozzuk, így meglesz az összes emberekből alkotott pár. Ebből szelektáljuk azokat a sorokat, amikben különböző nevek, de azonos foglalkozások vannak, így kapjuk azokat a foglalkozásokat, amikhez van két különböző ember, aki csinálja, majd ezt vetítjük a foglalkozásra. [math] \pi_{M1.\text{foglalkozas}}(\sigma_{((M1.\text{nev}\neq M2.\text{nev})\wedge(M1.\text{foglalkozas}=M2.\text{foglalkozas}))}(M\times M)) [/math]

Az előző problémákat fogalmazzuk meg sor- és/vagy oszlopkalkulus segítségével!

• Megjegyzés: a kettő teljesen ekvivalens, itt kevés attribútumú táblák vannak, és általában egy egyattribútumú tábla a válasz, ezért az oszlopkalkulus kicsit tömörebb.
• Kik a relációkban szereplő férfiak?
  • Azon x-ek halmaza, akik nem szerepelnek a nők közt, de van hozzájuk y, z, w, akikkel együtt egy sort alkotva szerepelnek a dolgozók közt. [math] \{x \mid (\neg N(x)) \wedge (\exists y, z, w: M(x, y, z, w))\} [/math]
• Kik az egyedülálló nők?
  • Azon x-ek halmaza, akik szerepelnek a nők közt (igaz rájuk az N reláció), de nincs hozzájuk y, akivel házaspárt alkotnának. [math] \{x \mid (N(x)) \wedge (\neg\exists y: H(y, x))\} [/math]
• Mely házaspárokban keres a nő jobban?
  • Azon x, y párok halmaza, akik házaspárok, és létezik hozzájuk olyan z, w, t, s, u, v, hogy velük együtt egy-egy sort alkotnak a dolgozók közt, és az x-hez tartozó fizetés kisebb az y-hoz tartozónál. [math] \{(x, y) \mid (H(x, y)) \wedge (\exists z, w, t, s, u, v: (M(x, z, w, t)\wedge M(y, s, u, v) \wedge (t\lt v)))\} [/math]
• Mely foglalkozásokat űzi mindkét nem?
  • Azon x-ek halmaza, amikhez van y és z (egy nő és egy férfi), akikre igaz, hogy y szerepel a nők közt, z nem, és létezik hozzájuk w, t, s, u, hogy ezekkel, és x-szel mint foglalkozással együtt sort alkotva szerepelnek a dolgozók közt. [math] \{x \mid \exists y, z: (N(y)\wedge\neg N(z)\wedge(\exists w, t, s, u: (M(y, x, w, t) \wedge M(z, x, s, u))))\} [/math]
• Kik a házasságokban élő tanárok?
  • Azon x-ek halmaza, akikhez létezik y, akivel ((x, y) vagy (y, x) sorrendben) sort alkotnak H-ban, és létezik z, w, amikkel, és a 'tanár' konstanssal mint foglalkozással, sort alkotnak az M táblában: [math] \{x \mid (\exists y: (H(x, y)\vee H(y, x)))\wedge(\exists z, w: M(x, \text{'tanar'}, z, w))\} [/math]
• Kik a BjutiSzalonban dolgozó nők férjei?
  • Azon x-ek halmaza, akikhez van y, hogy (y, x) házaspár, és van z, w, amik x-szel és a 'BjutiSzalon' konstanssal szerepelnek M-ben. [math] \{x \mid (\exists y: H(y, x))\wedge(\exists z, w: M(x, z, \text{'BjutiSzalon'}, w))\} [/math]
• Melyek azok a foglalkozások, amiket csak egy-egy ember űz?
  • Azon x-ek halmaza, amikhez létezik y, z, w, akikkel sort alkot M-ben (vagyis van ilyen foglalkozás), de nem létezik két különböző hármas (y, z, w, t, s, u), amikkel sort alkot (és a két sorban a nevek különböznek). [math] \{x \mid (\exists y, z, w: M(y, x, z, w))\wedge(\neg\exists y, z, w, t, s, u: (M(y, x, z, w)\wedge M(t, x, s, u)\wedge(y\neq t)))\} [/math]
• Melyek azok a foglalkozások, amiket legalább ketten űznek?
  • Azon x-ek halmaza, amikhez létezik két különböző hármas (y, z, w, t, s, u), akikkel sort alkot M-ben. [math] \{x \mid \exists y, z, w, t, s, u: (M(y, x, z, w)\wedge M(t, x, s, u)\wedge(y\neq t))\} [/math]

Biztonságosak-e az alábbi kifejezések? A választ indokoljuk!

• A biztonságos sorkalkulust azért találták ki, mert a sorkalkulust nem mindig lehet véges sok lépésben kiértékelni. Pl. egy olyan kifejezést, hogy [math] s^{(m)}[1] < 3 [/math] végtelen sokféle sor kielégíthet, ezért előfordulhat, hogy nem fog véges sok lépésben lefutni a kiértékelése. Ezt úgy küszöbölték ki a biztonságos változatban, hogy tettek két megkötést. Ezeknek az egyszerű megfogalmazásához két dolog:
  • Egy formula domainje értékek egy halmaza. Két dologból áll össze: a formulában szereplő konstansok, illetve a formulában szereplő relációk összes sorának összes értéke. Nevezzünk "ismeretlen" sornak olyan sorokat, amiknek van domainen kívüli értéke.
  • Független változó olyan változó, amit "kívülről kap" a kifejezés, pl. [math] \exists y^{(m)}: (R^{(m)}(y^{(m)}) \wedge y^{(m)}[1]=x^{(n)}[2]) [/math]-ban x-et "kívülről" kapja a kifejezés, és ehhez keres olyan y-t, amire teljesül a feltétel.
• Így a két feltétel:
  • Egy kvantor nélküli kifejezés csak akkor biztonságos, ha garantáltan csak olyan sor elégítheti ki, aminek minden eleme egy véges halmazból (a formula domainjéből) származik.
  • Egy [math] \exists u: \omega(u) [/math] kifejezés csak akkor biztonságos, ha a független változók bármely értéke mellett [math] \omega(u) [/math] biztonságos.
• A biztonságosság ellenőrzése voltaképp abból áll, hogy megnézzük: kielégítheti-e a formulát olyan sor, ami ismeretlen, és véges időben (a függő változókra véges sok értéket kipróbálva) eldönthető-e, mely "ismert" sorok elégítik ki.
• Pl. egy [math] \Psi(x) \wedge \Phi(x) [/math] kifejezést akkor nem elégíthet ki ismeretlen sor, és akkor tudjuk véges időben eldönteni, hogy mely jó sorok elégítik ki, ha az egyik részkifejezés biztonságos (ekkor az őt kielégítő sorok halmazát meghatározzuk véges időben), a másikról pedig minden x-re véges időben eldönthető, hogy kielégíthető-e. Ez biztosan teljesül, ha a másik is biztonságos, illetve akkor is, ha nincs benne függő változó. VAGY-gyal összekapcsolt kifejezéseknél mindkettőnek külön-külön biztonságosnak kell lennie.
• Az egzisztenciális kvantornál meg kell nézni, hogy a független változó felvehet-e olyan értéket, hogy nem biztonságos legyen. Ehhez a kvantoron kívüli részben meg kell nézni, milyen megkötés adott a független változóra, és gondolatban minden lehetséges értékét behelyettesíteni, és úgy megvizsgálni a kvantoron belüli kifejezés biztonságosságát. Csak akkor lesz biztonságos a kvantoros kifejezés, ha a kvantoron belüli a független változó minden megengedett értékére biztonságos.
• Az univerzális kvantoros kifejezéseket egzisztenciális kvantorossá kell alakítani a [math] \forall x: \omega(x) \Leftrightarrow \neg(\exists x: (\neg \omega(x))) [/math] összefüggéssel.

Kvantor nélküli kifejezések:

• [math] s^{(m)}[1] < 3 [/math]
  • Nyilván nem csak domainbeli (itt a domain csak a 3-mat tartalmazza) elemeket tartalmazó sorok elégíthetik ki, úgyhogy nem biztonságos.
• [math] R^{(m)}(s^{(m)}) \wedge s^{(m)}[1]=3 [/math]
  • Az első tagot csak domainbeli sorok elégíthetik ki, a második nem tartalmaz kvantort, ezért biztonságos.
• [math] R^{(m)}(s^{(m)}) \wedge s^{(m)}[1] < 3 [/math]
  • Az előzőhöz hasonlóan biztonságos.
• [math] \neg R^{(m)}(s^{(m)}) \wedge s^{(m)}[1]=3 [/math]
  • Itt számít a sor hossza, vagyis az m. Ugyanis az első tag nem biztonságos, de kvantormentes, ezért a kifejezés még lehet biztonságos, ha a második tag az. A második viszont csak a sor első elemére ad megkötést. Ha m=1, akkor ezáltal az összes értéket megkötöttük, és biztonságos lesz, ha viszont m > 3, akkor a második, stb. eleme a sornak lehet domainen kívüli, tehát ekkor nem biztonságos a második tag, és az egész kifejezés sem.
• [math] R^{(m)}(s^{(m)}) \wedge \neg(s^{(m)}[1]=3) [/math]
  • VAGY-os kifejezésnél mindkét tagnak biztonságosnak kell lennie. Itt a második nyilván nem az, tehát nem biztonságos. (Ez ÉS-es kifejezés és biztonságos)

Kvantort tartalmazó kifejezések:

• Először vizsgáljuk meg biztonságosság szempontjából az alábbi három kifejezést és negáltjaikat:
• [math] \Phi(x, y)=R_1(x, y) \wedge y > 0 [/math]
• [math] \Psi(x, y)=\neg R_1(x, y) \vee y > 0 [/math]
• [math] \Omega(x, y)=R_1(x, y) \vee y > 0 [/math]
• [math] \Theta(x)=R_2(x) \wedge \exists y: \Phi(x, y) [/math]
• [math] \Theta(x)=R_2(x) \wedge \exists y: \Psi(x, y) [/math]
• [math] \Theta(x)=R_2(x) \wedge \forall y: \Phi(x, y) [/math]
• [math] \Theta(x)=R_2(x) \wedge \forall y: \Psi(x, y) [/math]
• [math] \Theta(x)=\neg R_2(x) \wedge \exists y: \Phi(x, y) [/math]
• [math] \Theta(x)=\neg R_2(x) \wedge \exists y: \Psi(x, y) [/math]
• [math] \Theta(x)=\neg R_2(x) \wedge \forall y: \Phi(x, y) [/math]
• [math] \Theta(x)=\neg R_2(x) \wedge \forall y: \Psi(x, y) [/math]
• A fentiek közül mely kifejezések negáltja biztonságos?
• A [math] \Psi [/math] vagy [math] \Phi [/math] részkifejezéseket helyettesítve [math] \Omega [/math]-val hány biztonságos kifejezést kapunk?

Gondolkodtató kérdések

• Mi az összefüggés egy kifejezés biztonságossága és az eredményhalmaz számossága között?
  • Biztonságos kifejezés mindig véges eredményhalmazt generál. Sőt, ha n hosszú sor a kimenete, a kifejezés domainje pedig K elemből áll, akkor felső korlát az eredményhalmaz méretére K^n, hiszen legfeljebb ennyi különböző n hosszú sort lehet a domainbeli elemekből készíteni. Nem biztonságos kifejezés generálhat véges és végtelen halmazt is.
• Mi a legprimitívebb algoritmus, amit el tudsz képzelni egy biztonságos sorkalkulus kifejezés eredményhalmazának előállítására?
• Készíts reláció-algebrai kifejezést egy halmaz legkisebb, ill. második legkisebb elemének kiválasztására! Mi az ennek megfelelő sor- és oszlopkalkulus kifejezés?
  • Reláció-algebránál először vesszük a halmaz szorzatát magával, és kiszelektáljuk azokat a párokat, ahol az első kisebb, mint a második, majd projekcióval meghagyjuk a második oszlopot. Ekkor megkaptuk azon elemek halmazát, amik nagyobbak valaminél, ezt kivonva az eredetiből marad a legkisebb elem. [math] H\setminus (\pi_{2}(\sigma_{2>1}(H\times H))) [/math]
  • A második legkisebb elemet úgy kapjuk meg, hogy azon elemek halmazából, amiknél van kisebb, kivonjuk azok halmazát, amiknél legalább 2 kisebb van: [math] (\pi_{2}(\sigma_{2>1}(H\times H)))\setminus (\pi_{3}(\sigma_{(2>1)\wedge(3>2)}(H\times H\times H))) [/math]
  • Sorkalkulus: azon egyelemű sorok halmaza, amikhez nem létezik nála kisebb első elemmel rendelkező egyelemű sor. [math] \{s^{(1)}\mid H^{(1)}(s^{(1)})\wedge\neg\exists t^{(1)}:(H^{(1)}(t^{(1)})\wedge s^{(1)}[1]>t^{(1)}[1])\} [/math] Illetve a második legkisebb elem: létezik nála kisebb, de nem létezik két különböző nála kisebb. [math] \{s^{(1)}\mid H^{(1)}(s^{(1)})\wedge\exists t^{(1)}:(H^{(1)}(t^{(1)})\wedge s^{(1)}[1]>t^{(1)}[1])\wedge\neg\exists t^{(1)}, u^{(1)}:(H^{(1)}(t^{(1)})\wedge H^{(1)}(u^{(1)})\wedge s^{(1)}[1]>t^{(1)}[1]\wedge s^{(1)}[1]>u^{(1)}[1] \wedge u^{(1)}[1]\neq t^{(1)}[1])\} [/math]
  • Oszlopkalkulus: ugyanaz, mint az előbb, csak egyelemű sorváltozók első elemei helyett egy-egy oszlopváltozó szerepel: [math] \{s\mid H(s)\wedge\neg\exists t:(H(t)\wedge s>t)\} [/math] illetve [math] \{s\mid H(s)\wedge\exists t:(H(t)\wedge s>t)\wedge\neg\exists t, u:(H(t)\wedge H(u)\wedge s>t\wedge s>u \wedge u\neq t)\} [/math]
• Mondjunk minél kacifántosabb helybenhagyó műveleteket!
• Mikor kényelmesebb a sor- és mikor az oszlopkalkulus?
  • Ha rövid sorok vannak, illetve a sorok elemeihez gyakran kell egyenként hozzányúlni, akkor az oszlopkalkulus, egyébként a sor.
• Egy apa-fia relációból keresd ki azokat, akik nem nagyapák!
• Az egyes reláció-algebrai kifejezésekről állapítsuk meg, hogy az eredményül kapott reláció kisebb vagy vagyobb, mint az eredeti, illetve mikor lehet azonos méretű (azaz az eredményreláció sor- és oszlopszáma hogyan viszonyul az eredeti relációk azonos paramétereihez)!
  • A sorok száma az uniónál nyilván legalább akkora, mint a nagyobbik tábla mérete, és legfeljebb a két tábla méretének összege lehet. A különbségnél az alsó korlát a két tábla méretének különbsége, ill. ha ez negatív, akkor nulla, a felső a kisebbítendő tábla mérete. Vetítésnél nulla méretű táblából nulla méretű lesz, egyébként 1 és a tábla mérete közt lesz az eredmény mérete, szelekciónál pedig 0 és a tábla mérete közt. Szorzatnál a két méret szorzata lesz az eredményé, természetes illesztésnél nulla és a két méret szorzata közt lesz a méret.
  • Az oszlopok száma az uniónál ugyanannyi kell legyen, és az eredménynek is annyi lesz, különbségnél hasonlóan. Vetítésnél az oszlopok száma nulla (gyakorlati esetekben 1) és az eredeti oszlopszám közt lesz Szelekciónál az oszlopok száma nem változik. Szorzatnál az oszlopszámok összegződnek, természetes illesztésnél a kisebbik oszlopszám, és az oszlopszámok összege közt lehet.
• Mely relációalgebrai műveletek invertálhatók, és milyen módon az eredeti relációk felhasználása nélkül?
  • A különbségnél, az uniónál, a szelekciónál és a projekciónál általában információt veszítünk, ezért nem invertálhatóak, a szorzat viszont igen, megfelelő projekciókkal (az egyik, illetve a másik eredeti reláció attribútumaira vetítve). A természetes illesztés, a theta-illesztés és a hányados sem invertálható általában.
• Ha egy kifejezés biztonságos, akkor a negáltjáról mit mondhatunk, illetve ellenkező irányban mi a helyzet?
  • Egy kifejezés akkor biztonságos, ha garantáltan nem elégítheti ki egyetlen, nemdomainbeli elemeket tartalmazó sor sem. Tehát a negáltját mindegyik kielégíti, így az nem biztonságos. Fordítva viszont nem igaz: hiszen ha a negált alattit kielégítheti "rossz" sor, abból még nem feltétlenül következik, hogy mindegyik kielégíti, tahát nem következik, hogy a negáltják egy sem, így a negált lehet biztonságos és nem biztonságos is.
• Soroljuk fel a sor- és oszlopkalkulus közötti átírás főbb lépéseit!
• Miért szükséges a biztonságos sorkalkulus definíciójánál a két feltétel? Mondjunk példát olyan esetekre, ahol a kifejezés csak az egyiket teljesíti, mi ezekkel a probléma?

Gyakorló feladatok

1. Adott az alábbi relációs adatbázhis: GYÁRT(CÉG, TÍPUS, ÁR), SZERETI(VEVŐ,TÍPUS), DOLGOZIK(VEVŐ,CÉG,BEOSZTÁS).

• A relációk jelentése rendre: azon autóTÍPUSOK, amiket egy CÉG gyárt az azok eladási ÁRa; egy VEVŐ melyik autóTÍPUS-t szerti; a VEVŐ melyik CÉGnél dolgzik, milyen BEOSZTÁS-ban.*
• Adjon meg egy sorkalkulus kifejezést, amely azokat a vevőket tartalmazó relációt állítja elő, akik olyan cégnél dolgoznak, amelyek gyártanak olyan autótípust, amilyet a vevő szeret!
• Vizsgálja meg, hogy a fent leírt kifejezés biztonságos-e!

-- G - 2008.11.07.