Relalg Optimalizációs Tulajdonságok/Tételek

$E, E_n$ relációk és $F, F_n$ logikai függvények...

1. Kommutativitás

Descartes ($\times$), Natural and Theta Join ($\Join,\;\Join_\Theta$)

(alternatively $\cup$ and $\cap$ too)

\[\Large\begin{array}{rcl}E_1 \times E_2 &\cong& E_2 \times E_1 \\ E_1 \Join E_2 &\cong& E_2 \Join E_1 \\ E_1 \Join_\Theta E_2 &\cong& E_2 \Join_\Theta E_1\end{array}\]

??? tip "Help, Az összekapcsolásoknál a sorrend irreleváns

2. Asszociativitás

Descartes ($\times$), Natural and Theta Join ($\Join,\;\Join_\Theta$)

(alternatively $\cup$ and $\cap$ too)

\[\Large\begin{array}{rcl} (E_1 \times E_2) \times E_3 &\cong& E_1 \times (E_2 \times E_3) \\ (E_1 \Join E_2) \Join E_3 &\cong& E_1 \Join (E_2 \Join E_3) \\ (E_1 \Join_\Theta E_2) \Join_\Theta E_3 &\cong& E_1 \Join_\Theta (E_2 \Join_\Theta E_3) \end{array}\]

Help

A csoportosítás ugyanazt eredményezi, mintha csak sorba haladnánk

3. Vetítések összevonása, bővítése

Projection ($\Pi$)

$ A, B \in E;\quad A \subseteq B: $

\[ \Large\Pi_A(\Pi_B(E)) \cong \Pi_A(E) \]

Help

Szigorúan szűkebbre vetítés esetén az általános elhagyható (hiszen a szigorú szűrés elvégzi ugyanezt)

4. Kiválasztások felcserélhetősége, felbontása

Selection ($\sigma$)

$ F_1,F_2 \in \text{dom}(E): $

\[ \Large\sigma_{F_1\land F_2}(E) \cong \sigma_{F_1}(\sigma_{F_2}(E)) \cong \sigma_{F_2}(\sigma_{F_1}(E)) \]

Help

Egy összetett szűrés alkotóelemeinként is végrehajtható, vagy összevonható logikailag

5. Kiválasztás és vetítés felcserélhetősége

Projection ($\Pi$) and Selection ($\sigma$)

$ A \in E,\quad F\in \text{dom}(A):$

\[ \Large\Pi_A(\sigma_F(E)) \cong \sigma_F(\Pi_A(E)) \]

Általánosan:

$ A,B\in E, A\cap B = \emptyset, F\in \text{dom}(A\cup B):$

\[ \Large \Pi_A(\sigma_F(E)) \cong \Pi_A(\sigma_F(\Pi_{A\cup B}(E))) \]

Help

Ha a szűrés csak a vetítés elemeire vonatozik, akkor plussz oszlopok nem befolyásolhatják az eredményt (hiszen nem veszi figyelembe)

A második eset arra tér ki, hogy ha a szűrés feltétele és a vetítés oszlopai nem teljesen egyeznek, akkor a szűrés oszlopait még fel kell belül venni, hogy értelmes maradjon

6. Kiválasztás és szorzás felcserélhetősége

Selection ($\sigma$) and Descartes ($\times$)

$ F\in \text{dom}(E_1): $

\[ \Large \sigma_F(E_1 \times E_2) \cong \sigma_F(E_1)\times E_2 \]

$ F = F_1\land F_2,\quad F_1\in \text{dom}(E_1),\;F_2\in \text{dom}(E_2): $

\[ \Large \sigma_F(E_1 \times E_2) \cong \sigma_{F_1}(E_1) \times \sigma_{F_2}(E_2) \]

$ F = F_1 \land F_2,\quad F_1\in\text{dom}(E_1),\; F_2 \in\text{dom}(E_1 \cup E_2), F_2 \not\in \text{dom}(E_1 \setminus E_2) \land F_2 \not\in \text{dom}(E_2 \setminus E_1): $

\[ \Large \sigma_F(E_1 \times E_2) \cong \sigma_{F_2}(\sigma_{F_1}(E_1)\times E_2) \]

Help

6.1: Ha csak az első relációra szűr a feltétel, az elég csak azon elvégezni, nem kell előbb összevonni
6.2: 6.1-et kibővítve egy összetettebb szűrés szétbontható az adott relációra vontatkozó feltételre (ha elkülöníthető)
6.3: Amit ki akar mondani, hogy ha a feltétel úgy bontható szét, hogy van csak az egyikre igaz rész, de a másik csak mind a kettővel értelmes, akkor eszerint bonts szét
- Igen, itt $F_2$ lényegében mind a két relációból tartalmaz legalább egy oszlopot, ezért kell kívül hagyni

7. Kiválasztás és egyesítés felcserélhetősége

Selection ($\sigma$) over Union ($\cup$)

$\text{dom}(E_1) = \text{dom}(E_2), F \in \text{dom}(E_{1,2}):$

\[ \Large \sigma_F(E_1 \cup E_2) \cong \sigma_F(E_1)\cup\sigma_F(E_2) \]

??? tip "Help, Az egyesítés előtt is szűrhető a két reláció külön (duh)

8. Kiválasztás és kivonás felcserélhetősége

Selection ($\sigma$) over Minus ($\setminus, -$)

$\text{dom}(E_1) = \text{dom}(E_2), F \in \text{dom}(E_{1,2}):$

\[ \Large \sigma_F(E_1 - E_2) \cong \sigma_F(E_1)-\sigma_F(E_2) \]

Help

A külömbség előtt is szűrhető a két reláció külön (duh*2)

9. Kiválasztás és kivonás felcserélhetősége

Selection ($\sigma$) over Join ($\Join$)

$ F \in (\text{dom}(E_1)\cap \text{dom}(E_2)):$

\[ \Large \sigma_F(E_1 \Join E_2) \cong \sigma_F(E_1)\Join\sigma_F(E_2) \]

Help

Az összekapcsolás előtt is szűrhető a két reláció külön (duh*3) (na jó, előbb azt kössük ki, hogy csak a közös oszlopai felett legyen $F$ értelmezve)

10. Vetítés és szorzás felcserélhetősége

Projection ($\Pi$) over Descartes ($\times$)

$ A = A_1 \cup A_2, A_i \in E_i (i \in {1,2})$

\[ \Large \Pi_A(E_1 \times E_2) \cong \Pi_{A_1}(E_1) \times \Pi_{A_2}(E_2) \]

Help

A megfelelő oszlopokat szétbonthatjuk, és vetíthetjük csak az adott relációban található oszlopokra (figyelj, hogy lehet overlap)

11. Vetítés és szorzás felcserélhetősége

Projection ($\Pi$) over Union ($\cup$)

$\text{dom}(E_1) = \text{dom}(E_2), A \in E_{1,2}:$

\[ \Large \Pi_A(E_1 \times E_2) \cong \Pi_{A_1}(E_1) \times \Pi_{A_2}(E_2) \]

Help

Az uniónál ugye muszály, hogy a sémák megegyezzenek, ez arra tér ki, hogy mert ugyanazokat az oszlopokat akarjuk látni, mindegy, hogy az unió előtt, vagy után vetítjük le az oszlopokat

This

Look, it's big brain time:

$E_1:$

A	B
0	0
0	1

$E_2:$

A	B
0	0

$E_1 - E_2:$

A	B
0	1

$\Pi_A(E_1 - E_2):$

A
0

$\Pi_A(E_1) - \Pi_A(E_2) = \emptyset\qquad \square$

Reductio ad absurdum 🫳🎤💥