4. gyakorlat – emlékeztető, feladatok

Sidló Csaba

2004. október 6.

1. Fogalmak

1.1. Tartományfüggetlenség

1.1. Definíció (formulák tartománya). Legyen F egy DRC formula, P_{1} ... P_{n} predikátumokkal és c_{1} ... c_{n} konstansokkal. Legyen DOM(F) az F formula predikátumainak megfelelő táblákban szereplő attribútum-értékek és az F -ben szereplő konstansok halmaza, tehát

DOM(F) := ∏_{$1}(P_{1}) ∪ ∏_{$2}(P_{1}) ∪ ... ∏_{$n_{1}}(P_{1})... ∪ ∏_{$1}(P_{k}) ∪ ∏_{$n_{k}}(P_{k}) ∪ {c_{1}, ..., c_{n}}

1.2. Definíció (formula által meghatározott reláció adott értéktartományon). Legyen adott egy F formula x_{1}, ..., x_{n} szabad változókkal és egy D ⊆ DOM(F) halmaz. Ekkor az F által meghatározott reláció D-n

R(F, D) := {(x_{1}, ...x_{n})|F (x_{1}, ..., x_{n}) ∧ (x_{1}, ..., x_{n}) ∈ D^{n}},

ami mint látjuk a DRC kifejezés definíciójánál az értékkészlet megkötésével több.

1.3. Definíció (tartományfüggetlen formulák). Egy adott F formula tartományfüggetlen, ha

∀D ⊇ DOM(F) : R(F, D) = R(F, DOM(F))

A tartomány-függetlenség jogos elvárás egy lekérdező nyelvvel szemben. Sajnos azonban nem létezik olyan algoritmus, aminek segítségével el tudnánk dönteni, hogy egy formula tartomány-független-e. Tudunk azonban olyan formai megszorításokat alkalmazni, amik biztosan tartomány-független formulákhoz vezetnek, ezek lesznek a biztonságossági szabályok. A dolog hátulütője, hogy a biztonságos DRC kifejezésekkel felírható relációk halmaza szűkebb, mint a tartományfüggetlen DRC kifejezésekkel leírható relációk halmaza. A biztonságos DRC kifejezések azonban még mindig jól használhatók, kifejező erejük ugyanis megegyezik a relációs algebrával.

1.4. Definíció (biztonságos DRC). Biztonságosnak nevezünk egy DRC formulát, ha

1. nem szerepel benne ∀ kvantor,

2. minden F_{1} ∨ F_{2} részformulára F_{1} és F_{2} szabad változói megegyeznek, 3. a formula minden F_{1} ∧ ... ∧ F_{n} maximális konjukciós láncának minden

szabad változója korlátozott:

(a) ha F_{i} x = c alakú ahol c konstans, akkor x korlátozott,

(b) ha F_{i} x = y alakú és y korlátozott, akkor x is korlátozott,

(c) ha F_{i} nem negációval kezdődik és nem aritmetikai összehasonlítás, x pedig szabad változója, akkor x korlátos,

4. negáció (¬) csak olyan maximális konjukciós láncban szerepelhet, amelyben van nem negált tag, tehát F_{1} ∧ ... ∧ ¬G ∧ ... ∧ F_{n} maximális konjukciós láncban legalább egy F_{i} nem kezdődik negációval.

1.2. Relációs tartomány kalkulus vs. relációs algebra

A relációs algebrai kifejezéseknek megfeleltethetők DRC kifejezések, ennek segítségével láttuk be a "Relációs algebra⊆ DRC" tartalmazást. A megfeleltetések segítségével tetszőleges relációs algebrai kifejezés átírható DRC kifejezéssé.

Fontos eredmény a relációs algebra és a biztonságos DRC kifejező erejének egyenlősége. Ennek bizonyításához beláttuk a "relációs algebra ⊆ biztonságos DRC" tartalmazást. Ehhez felírtunk olyan szabályokat, melyek segítségével relációs algebrai kifejezéseket biztonságos DRC kifejezésekké alakíthatunk.

A másik irány, a "biztonságos DRC ⊆ relációs algebra" bizonyítása során olyan átalakításokat végeztünk, melyek segítségével a biztonságos DRC formulák maximális konjukciós láncainak meg tudunk feleltetni egy-egy relációs algebra kifejezést, így biztonságos DRC kifejezéseket szintén át tudunk alakítani relációs algebrai kifejezésekké.

A szabályokat lásd az előadásjegyzetben.

2. Feladatok

2.1. Tartományfüggetlenség

Tartományfüggetlenek-e a következő DRC formulák? Bizonyítsunk.

1. x = y

2. x = y ∧ p(x, y)

3. F (x) = ¬p(x)

4. F (x) = ∃y : q(x, y) ∧ ¬p(x)

5. F (x, z) = ∃y : (p(x, y) ∨ q(y, z))

6. F (x, z) = ∃y : (p(x, y) ∧ q(y, z))

2.2. Biztonságos DRC formulák

Bontsuk fel részformulákra, ábrázoljuk fában és határozzuk meg a maximális konjukciós láncokat:

1. (∃y′′r(x, y′′)) ∧ ¬(∃y((∃y′r(x, y′)) ∧ s(y) ∧ ¬r(x, y)))

2.3. Biztonságos DRC kifejezések

Írjunk fel biztonságos DRC kifejezéseket a következő kérdésekhez. Adott az Sz : Szeret(név, gyümölcs) tábla.

1. Milyen gyümölcsöket szeret Malac?

2. Milyen gyümölcsöket nem szeret Malac?

3. Kik szeretnek minden gyümölcsöt?

4. Kik szeretnek legalább / legfeljebb / pontosan két féle gyümölcsöt?

5. Kik szeretik legalább azokat a gyümölcsöket, mint Mic?

6. Kik szeretik legfeljebb azokat a gyümölcsöket, mint Mic? Egy videokölcsönző a következő relációkat használja nyilvántartáshoz:

V : Vevő(vevőID, név, életkor),
F : Film(filmID, cím, év, rendező),
K : Kölcsönöz(vevőID, filmID, dátum).

V -ben tartják nyilván az ügyfeleiket, F -ben a kölcsönözhető filmek alapvető adatait, K-ban pedig a kölcsönzéseket. Írjunk fel biztonságos DRC kifejezéseket a következő kérdésekhez:

7. Mely rendezők filmjeit kölcsönözte ki ’Kovács Ibolya’?

8. Milyen filmek vannak ugyanabból az évből, mint az ’Idő van’?

9. Ki kölcsönözte ki leghamarabb az ’Idő van’-t?

10. Kik kölcsönöztek minden nyilvántartott hónapban filmet?