34

Databázové systémy Ostatní typy spojení Vilém Vychodil KMI/DATA1, Přednáška 5

Databázové systémy

V. Vychodil (KMI/DATA1, Přednáška 5)

Ostatní typy spojení


1 / 34

Přednáška 5: Přehled 1

Vlastnosti přirozeného spojení: úplné spojení a bezeztrátová dekompozice, vztah přirozeného spojení a dalších operací, θ-spojení, spojení na rovnost.

2

Související problémy: kompozice a tranzitivní uzávěr, rekurzivní dotazy.

3

Problematika vnějších spojení: definice, úskalí, vztah k relačnímu modelu, formalizace pomocí tříhodnotových logik, jiné možnosti přístupu k problému.




2 / 34

Věta (Další vlastnosti přirozeného spojení) Mějme D1 , D2 a D3 na schématech R1 , R2 a R3 = R2 . Pak platí: 1 ./ je isotonní; 2 σy=d (D1 ./ D2 ) = σy=d (D1 ) ./ σy=d (D2 ) pokud y ∈ R1 ∩ R2 ; 3 σy=d (D1 ./ D2 ) = σy=d (D1 ) ./ D2 pokud y ∈ R1 a y 6∈ R2 ; 4 D1 ./ (D2 ∪ D3 ) = (D1 ./ D2 ) ∪ (D1 ./ D3 ); 5 D1 ./ (D2 ∩ D3 ) = (D1 ./ D2 ) ∩ (D1 ./ D3 ) = D1 ./ D2 ./ D3 ; 6 D1 ./ (D2 \ D3 ) = (D1 ./ D2 ) \ (D1 ./ D3 ).

Důkaz. plyne z isotonie konjunkce; 2 je zřejmé; 3 plyne analogicky jako předchozí bod; 4 je důsledkem distributivity konjunkce a disjunkce; 5 plyne z idempotence konjunkce; 6 platí, protože rst ∈ D1 ./ (D2 \ D3 ) p. k. rs ∈ D1 a st ∈ D2 \ D3 p. k. rs ∈ D1 , st ∈ D2 a st 6∈ D3 p. k. rs ∈ D1 , st ∈ D2 a rs ∈ D1 , st 6∈ D3 p. k. rst ∈ D1 ./ D2 a rst 6∈ D1 ./ D3 p. k. rst ∈ (D1 ./ D2 ) \ (D1 ./ D3 ). 1




3 / 34

Úplné spojení motivace: V některých spojeních jsou všechny n-tice z výchozích tabulek spojitelné s některými n-ticemi z ostatních tabulek – vede na pojem úplné spojení

nespojitelná n-tice, angl.: dangling tuple Mějme relace D1 , . . . , D2 na schématech R1 , . . . , Rn . Pak n-tice ri ∈ Di se nazývá nespojitelná vzhledem k ./ni=1 Di pokud neexistují žádné rj ∈ Dj (j 6= i) tak, že r1 ∪ · · · ∪ rn ∈ ./ni=1 Di .

úplné spojení, angl.: complete join Relace D1 , . . . , D2 na schématech R1 , . . . , Rn mají úplné spojení, pokud žádná Di neobsahuje nespojitelnou n-tici vzhledem k ./ni=1 Di . poznámka: D1 a D2 mají úplné spojení p. k. D1 n D2 = D1 a D2 n D1 = D2 . V. Vychodil (KMI/DATA1, Přednáška 5)



4 / 34

Věta (Charakterizace úplných spojení) Mějme relace D1 , . . . , Dn na schématech R1 , . . . , Rn . Pak platí: 1 πRj ./ni=1 Di ⊆ Dj pro každé j = 1, . . . , n; 2 πRj ./ni=1 Di = Dj pro každé j = 1, . . . , n p. k. D1 , . . . , Dn lze úplně spojit; 3 ./ni=1 Di = ./nj=1 πRj ./ni=1 Di pro každé j = 1, . . . , n; 4 πRj ./nk=1 πRk ./ni=1 Di = πRj ./ni=1 Di pro každé j = 1, . . . , n.

Důkaz. Bod 1 plyne z toho, že pokud r ∈ ./ni=1 Di , pak r(Rj ) ∈ Dj . V případě 2 ukážeme obměnou: D1 , . . . , Dn nelze úplně spojit pokud existuje rj ∈ Dj , která je nespojitelná vzhledem k ./ni=1 D r ∈ ./ni=1 Di a to je p. k. i ; to je p. k. r(Rj ) 6= rj pro každou rj 6∈ πRj ./ni=1 Di p. k. existuje j tak, že πRj ./ni=1 Di ⊂ Dj . Pro dokázání inkluze „⊆ÿ bodu 3 vyjdeme z toho, že pokud r ∈ ./ni=1 Di , pak r = r1 ∪ · · · ∪ rn , kde r(Rj ) = rj pro každé j. To jest rj ∈ πRj (./ni=1 Di ) a tedy r ∈ ./nj=1 πRj ./ni=1 Di . Opačná inkluze plyne z 1 a isotonie ./. Bod 4 je triviální důsledek 3 . V. Vychodil (KMI/DATA1, Přednáška 5)



5 / 34

Příklad (Úplné spojení) relace, které nemají úplné spojení: D1

D2

D1 ./ D2

D1 n D2

D2 n D1

FOO BAR BAZ

BAR BAZ QUX

FOO BAR BAZ QUX

FOO BAR BAZ

BAR BAZ QUX

444 555 555 666

abc def def ghX ghi ghi ghi

444 444 444 555 555 555 555 555

444 ghi 103 555 def 102 555 ghi 103

def def ghi ghi ghi

ghi def ghi abc

103 102 103 101

111 102 102 103 103 103 103

zzz www yyy xxx ttt uuu vvv

ghi ghi ghi def def ghi ghi ghi

103 103 103 102 102 103 103 103

ttt uuu vvv www yyy ttt uuu vvv

102 102 103 103 103

www yyy ttt uuu vvv

dle předchozího tvrzení: relace D3 = D1 n D2 a D4 = D2 n D1 mají úplné spojení D1 ./ D2 = D3 ./ D4 V. Vychodil (KMI/DATA1, Přednáška 5)



6 / 34

Bezeztrátová dekompozice relace motivace: Duální pojem k pojmu úplné spojení: Je možné vyjádřit výchozí relace pomocí spojení některých jejich projekcí?

bezeztrátová dekompozice, angl.: nonloss decomposition Relace D na schématu R1 ∪ · · · ∪ Rn má bezeztrátovou dekompozici vzhledem k množině schémat {R1 , . . . , Rn } pokud D = ./ni=1 πRi (D). existence dekompozic: každá D na R má (jednoprvkovou) bezeztrátovou dekompozici vzhledem k {R} (triviální případ; hledáme dekompozice vzhledem k větším množinám schémat) další typy dekompozic: horizontální/vertikální typy dekompozic, faktorové dekompozice, . . . V. Vychodil (KMI/DATA1, Přednáška 5)



7 / 34

Věta (Vlastnosti bezeztrátových dekompozic) Mějme relaci D na schématu R1 ∪ · · · ∪ Rn . Pak platí 1 D ⊆ ./ni=1 πRi (D); 2 ./ni=1 πRi (D) = ./nj=1 πRj ./ni=1 πRi (D) .

Důkaz. Pro dokázání 1 vezměme r ∈ D. Vzhledem ke schématům R1 , . . . , Rn lze r chápat jako n-tici ve tvaru r1 ∪ · · · ∪ rn , kde ri = r(Ri ) pro každé i = 1, . . . , n. Zřejmě tedy ri ∈ πRi (D) pro každé i = 1, . . . , n a tím pádem r ∈ ./ni=1 πRi (D). Tvrzení 2 je speciálním případem bodu 3 předchozí věty pro Di = πRi (D). důsledek: ./ni=1 πRi (D) má bezeztrátovou dekompozici vzhledem k {R1 , . . . , Rn }




8 / 34

Příklad (Bezeztrátová dekompozice) D

π{FOO,BAR,BAZ} (D)

π{BAZ,QUX} (D)

π{BAR,QUX} (D)

π{FOO,BAR} (D)

FOO BAR BAZ QUX

FOO BAR BAZ

BAZ QUX

BAR QUX

FOO BAR

100 100 200 300

100 aaa 444 200 bbb 555 300 ccc 555

444 GGG 444 HHH 555 III

aaa aaa bbb ccc

100 aaa 200 bbb 300 ccc

aaa aaa bbb ccc

444 444 555 555

platí například:

GGG HHH III III

GGG HHH III III

D = π{FOO,BAR,BAZ} (D) ./ π{BAZ,QUX} (D) D = π{FOO,BAR,BAZ} (D) ./ π{BAR,QUX} (D) D = π{FOO,BAR,BAZ} (D) ./ π{FOO,BAR} (D)

ale například: D = 6 π{FOO,BAR} (D) ./ π{BAZ,QUX} (D) poznámky (k tomtuto konkrétnímu příkladu): neexistuje dekompozice na dvě dvouprvková schémata celkem 60, 672 možných dekompozic (složených z vzájemně různých schémat) V. Vychodil (KMI/DATA1, Přednáška 5)



9 / 34

Odvozené operace: θ-spojení motivace: Chceme spojovat data ze dvou tabulek tak, aby kritérium spojitelnosti nebylo dáno pouze rovností na určitých hodnotách, ale obecnou podmínkou vztahující se na hodnoty n-tic z obou tabulek.

Definice (θ-spojení, angl.: θ-join) Mějme relace D1 a D2 na schématech R a T takových, že R ∩ T = ∅ a nechť θ je skalární výraz typu „pravdivostní hodnotaÿ, který může obsahovat jména atributů z R ∪ T . Pak θ-spojení D1 a D2 splňující θ je relace σθ (D1 ./ D2 ) a označujeme ji D1 ./θ D2 . poznámky: ./θ je definováno jako restrikce z kartézského součinu podle definice σθ a ./: D1 ./θ D2 = {rt | r ∈ D1 a r ∈ D2 tak, že rt splňuje θ}. V. Vychodil (KMI/DATA1, Přednáška 5)



10 / 34

Odvozené operace: Spojení na rovnost motivace: Speciální případ θ-spojení, ve kterém je podmínka θ formulována jako konjunkce podmínek vyjadřující rovnost hodnot atributů stejných typů.

Definice (spojení na rovnost, angl.: equijoin) Mějme relace D1 a D2 na schématech R a T takových, že R ∩ T = ∅ a nechť {y1 , . . . , yn } ⊆ R, {y10 , . . . , yn0 } ⊆ T tak, že atributy mají yi a yi0 stejný typ. Pak θ-spojení D1 a D2 , kde θ je va tvaru y1 = y10 c · · · c yn = yn0 nazýváme spojení D1 a D2 na rovnost (atributů y1 , y10 až yn , yn0 ) a označujeme jej D1 ./y1 =y10 ,...,yn =yn0 D2 . Tutorial D: (hrelační-výraz 1 i JOIN hrelační-výraz 2 i) WHERE hpodmínkai SQL: SELECT * FROM hjméno 1 i, hjméno 2 i WHERE hpodmínkai V. Vychodil (KMI/DATA1, Přednáška 5)



11 / 34

Vzájemná zastupitelnost operací pozorování: Spojení na rovnost lze vyjádřit pomocí přirozeného spojení a restrikce, protože na disjunktních schématech přechází přirozené spojení v kartézský součin. otázka: Lze naopak vyjádřit přirozené spojení pomocí spojení na rovnost? úvaha: Přirozené spojení lze chápat jako spojení na rovnost, ve kterém nejprve vhodně přejmenujeme atributy a provedeme dodatečnou projekci. Pro relace D1 a D2 nad schématy R ∪ S a S ∪ T tak, že R ∩ T = ∅ a S = {y1 , . . . , yk }, s použitím přejměnování y1 , . . . , yk na y10 , . . . , yk0 máme: D1 ./ D2 = πR∪S∪T D1 ./y1 =y10 ,...,yk =yk0 ρy10 ←y1 ,...,yk0 ←yk (D2 ) = πR∪S∪T σy1 =y10 ,...,yk =yk0 D1 ./ ρy10 ←y1 ,...,yk0 ←yk (D2 ) . V. Vychodil (KMI/DATA1, Přednáška 5)



12 / 34

Obecné formule pro restrikce na rovnost motivace: Ve spojení na rovnost je θ vyjádřená jako konjunkce atomických formulí (tzv. identit). Snadno lze úvahy rozšířit na libovolně složité formule konstruované z identit a výrokových spojek.

Definice (formule definující podmínky pro restrikce) Mějme relační schéma R obsahující atributy y ∈ R typů Dy . Pak formule pro restrikce nad R definujeme takto: 1 pokud jsou y1 , y2 ∈ R, pak y1 = y2 je (atomická) formule; 2 pokud je y ∈ R a d ∈ Dy , pak y = d je (atomická) formule; 3 pokud jsou ϕ a ψ formule, pak jsou nϕ a (ϕ i ψ) formule. přijímáme konvenci o vynechávání vnějších závorek formulí (ϕ e ψ) (ϕ c ψ), (ϕ d ψ) chápeme jako zkratky (běžným způsobem) V. Vychodil (KMI/DATA1, Přednáška 5)



13 / 34

Věta (Rozšíření spojení na rovnost) Nechť R je relační schéma a θ je formule pro restrikci nad R. Pak existuje posloupnost relačních operací zahrnující pouze restrikce na rovnost, sjednocení a rozdíl tak, že pro každou D nad R je výsledek aplikace těchto operací roven σθ (D).

Důkaz. Nejprve nahládněme, že podle předchozí definice lze θ chápat jako formuli, ve které se vyskytují pouze spojky n a i. Použitím známého faktu, že ϕ i ψ je sémanticky ekvivalentní nϕ d ψ, můžeme θ chápat jako formuli obsahující n a d jako základní spojky. Dále můžeme využít faktu, že pro každou D nad R zřejmě platí následující σnθ (D) = {r ∈ D | r nesplňuje θ} = D \ σθ (D), σθ1 dθ2 (D) = {r ∈ D | r splňuje θ1 nebo r splňuje θ2 } = σθ1 (D) ∪ σθ2 (D). To jest, σθ (D) pro libovolně složitou θ lze vyjádřit konečně mnoha aplikacemi \ a ∪ pouze za použití výchozí relace D. poznámka: spojení na rovnost je „dost obecnáÿ relační operace V. Vychodil (KMI/DATA1, Přednáška 5)



14 / 34

Intermezzo: Tranzitivní uzávěr tranzitivní uzávěr relace na množině, angl.: transitive closure Mějme binární relaci R ⊆ A × A. Pak tranzitivním uzávěrem R, rozumíme binární relací R∞ ⊆ A × A splňující následující podmínky: 1 R ⊆ R∞ , 2 R∞ je tranzitivní, 3 R∞ je nejmenší relace splňující 1 a 2 . konstruktivně lze R∞ vyjádřit jako S S∞ n R∞ = ∞ R = R ◦ ·{z · · ◦ R} , n=1 n=1 | n-krát

přitom platí: S n pokud je R konečná, pak existuje index m tak, že R∞ = m n=1 R pokud je navíc R reflexivní, pak R∞ = Rm V. Vychodil (KMI/DATA1, Přednáška 5)



15 / 34

Příklad (Tranzitivní uzávěr binární relace na konečné množině) uvažujme binární relaci R = {ha, ci, hb, di, hc, bi, hd, bi} na množině A tranzitivní uzávěr relace R nalezneme takto: R1 R2 R3 R4 R∞

= {ha, ci, hb, di, hc, bi, hd, bi} = {ha, bi, hb, bi, hc, di, hd, di} = {ha, di, hb, di, hc, bi, hd, bi} = {ha, bi, hb, bi, hc, di, hd, di} = {ha, bi, ha, ci, ha, di, hb, bi, hb, di, hc, bi, hc, di, hd, bi, hd, di}

graficky: a

b

a

b

c

d

c

d




16 / 34

Příklad (Tranzitivní uzávěr v relačním modelu) motivace: Binární relaci R na množině A z předchozího příkladu můžeme formalizovat jako relaci D nad schématem {x, y} tak, že D = {hx, ai, hy, bi} | ha, bi ∈ R . Pak můžeme vyjádřit protějšky D1 , D2 , D3 , D4 , D∞ relací R1 , R2 , R3 , R4 , R∞ : D1 D2 D3 D4 Dn D∞

= D, = ρz←y (D) ◦ ρz←x (D) = π{x,y} (ρz←y (D) ./ ρz←x (D)), = ρz←y (D) ◦ ρz←x (D2 ) = π{x,y} (ρz←y (D) ./ ρz←x (D2 )), = ρz←y (D) ◦ ρz←x (D3 ) = π{x,y} (ρz←y (D) ./ ρz←x (D3 )), 0 ←y (D)), = π{x,y} (./ni=1 ρx0i,n ←x,yi,n Sm S m 0 ←y (D)), = n=1 Dn = n=1 π{x,y} (./ni=1 ρx0i,n ←x,yi,n

0 0 kde x01,n = x pro každé n; yn,n = y pro každé n; x0i,n = yi−1,n pro každé 2 ≤ i ≤ n.

problém: parametr m ve výrazu pro D∞ závisí na konkrétní D (!!) V. Vychodil (KMI/DATA1, Přednáška 5)



17 / 34

Tranzitivní uzávěr relací Definice (tranzitivní uzávěr relace, angl.: transitive closure) Mějme relaci D nad dvouprvkovým schématem R = {y1 , y2 }. Pak relace D∞ nad relačním schématem R splňující následující podmínky: 1 D ⊆ D∞ , 2 ρy←y1 (D∞ ) ◦ ρy←y2 (D∞ ) ⊆ D∞ , 3 D∞ je nejmenší relace splňující 1 a 2 , se nazývá tranzitivní uzávěr relace D. Tutorial D: TCLOSE (hrelační-výraz i) poznámky: SQL nepodporuje přímo jako relační operaci (ale je definovatelné) důležitý aspekt: ukázat konstruktivní předpis pro výpočet TCLOSE V. Vychodil (KMI/DATA1, Přednáška 5)



18 / 34

Lokální pojmenování výsledků dotazů v SQL WITH hjméno 1 i AS (hdotaz 1 i), . . . . . . hjméno n i AS (hdotaz n i) hdotaz-používající-jménai; WITH RECURSIVE hjméno 1 i (hatribut 1,1 i, hatribut 1,2 i, ...) AS (hnerekurzivní-výraz 1 i UNION DISTINCT hrekurzivní-výraz 1 i), . . . . . . . . . . . . hjméno n i (hatribut n,1 i, hatribut n,2 i, ...) AS (hnerekurzivní-výraz n i UNION DISTINCT hrekurzivní-výraz n i) hdotaz-používající-jménai; související pojem: „rekurzivní dotazyÿ v SQL V. Vychodil (KMI/DATA1, Přednáška 5)



19 / 34

Iterativní vyhodnocení pojmenovaných dotrazů v SQL vstup: hjméno i i (jméno pro výsledek), hatribut i,1 i, hatribut i,2 i, . . . (jména atributů) hnerekurzivní-výraz i i (dotaz) hrekurzivní-výraz i i (předpis iterace, může obsahovat hjméno i i a atributy) způsob vyhodnocení: 1 vyhodnoť hnerekurzivní-výraz i i; výsledek ulož do RESULT a WORK ; 2 dokud WORK 6= ∅, opakuj: vyhodnoť hrekurzivní-výraz i i v němž je každé hjméno i i nahrazeno obsahem tabulky WORK ; z výsledku odstraň duplicitní řádky a každý řádek, který se již nachází v RESULT ; výsledek ulož do WORK ; připoj obsah WORK na konec RESULT ; 3

navaž obsah RESULT na hjméno i i

poznámka: varianta s UNION ALL neodstraňuje duplicity V. Vychodil (KMI/DATA1, Přednáška 5)



20 / 34

Příklad (SQL: Tranzitivní uzávěr relace) využijeme faktu, že D∞ = f (D, D), kde D2 , pokud D1 = ∅, f (D1 , D2 ) = 0 0 f (D \ D2 , D ∪ D2 ), pro D0 = ρz←x (D1 ) ◦ ρz←y (D) a D1 6= ∅. CREATE TABLE r ( x NUMERIC NOT NULL, y NUMERIC NOT NULL, PRIMARY KEY (x, y)); · · · /* computing transitive closure */ WITH RECURSIVE tr (x, y) AS ( SELECT * FROM r UNION DISTINCT SELECT r.x, tr.y FROM r, tr WHERE r.y = tr.x) SELECT * FROM tr; V. Vychodil (KMI/DATA1, Přednáška 5)



21 / 34

Lokální pojmenování výsledků dotazů v Tutorial D lokální pojmenování pro skalární výrazy (analogie let* z dialektů LISPu): WITH (hproměnná 1 i := hvýraz 1 i,...,hproměnná n i := hvýraz n i): hskalární-výraz-používající-proměnné i lokální pojmenování pro n-ticové výrazy: WITH (hproměnná 1 i := hvýraz 1 i,...,hproměnná n i := hvýraz n i): hn-ticový-výraz-používající-proměnné i lokální pojmenování pro relační výrazy: WITH (hproměnná 1 i := hvýraz 1 i,...,hproměnná n i := hvýraz n i): hrelační-výraz-používající-proměnné i poznámka: pouze lokální pojmenování (neslouží k vyjadřování „rekurzivníchÿ předpisů) V. Vychodil (KMI/DATA1, Přednáška 5)



22 / 34

Příklad (Tutorial D: Použití WITH a tranzitivní uzávěr relace) WITH (r1 := r, r2 := (r RENAME {y AS z}) COMPOSE (r1 RENAME {x AS z}), r3 := (r RENAME {y AS z}) COMPOSE (r2 RENAME {x AS z}), r4 := (r RENAME {y AS z}) COMPOSE (r3 RENAME {x AS z})): UNION {r1, r2, r3, r4} WITH (r1 := r, w2 := (r RENAME {y AS z}) r2 := w2 MINUS r1, w3 := (r RENAME {y AS z}) r3 := w3 MINUS UNION {r1, w4 := (r RENAME {y AS z}) r4 := w4 MINUS UNION {r1, UNION {r1, r2, r3, r4}

COMPOSE (r1 RENAME {x AS z}), COMPOSE (r2 RENAME {x AS z}), r2}, COMPOSE (r3 RENAME {x AS z}), r2, r3}):

TCLOSE (r) V. Vychodil (KMI/DATA1, Přednáška 5)



23 / 34

Příklad (Tutorial D: Implementace tranzitivního uzávěru) OPERATOR tr (r RELATION {x INT, y INT}) RETURNS SAME_TYPE_AS (r); BEGIN; VAR result PRIVATE INIT (r) KEY {x,y}; VAR work PRIVATE INIT (r) KEY {x,y}; WHILE NOT (IS_EMPTY (work)); BEGIN; work := (r RENAME {y AS z}) COMPOSE (work RENAME {x AS z}); work := work MINUS result; result := result UNION work; END; END WHILE; RETURN result; END; END OPERATOR; V. Vychodil (KMI/DATA1, Přednáška 5)



24 / 34

Problematika nespojitelných n-tic motivace: Pokud se v relacích, které spojujeme, nacházejí nějaké nespojitelné n-tice, ve výsledky dochází ke „ztrátě informace.ÿ Jak tento problém vyřešit? převládající, ale koncepčně špatné řešení: snahy se objevují kolem roku 1979 (10 let po představení originálního modelu) zavedení vnějších spojení a konceptu nedefinovaných (chybějících) hodnot − tabulky nelze formalizovat jako relace nad relačními schématy − formální model je pochybný, postrádá logiku, velký potenciál vzniku chyb další řešení: místo nedefinovaných hodnot používat designované hodnoty z domén (např. "??" může mít význam, že řetězcová hodnota je neznámá) zavedení relační operace polorozdíl, která vyjadřuje nespojitelné n-tice plné využití RM a konceptu relace jako hodnoty atributu (Přednáška 6) V. Vychodil (KMI/DATA1, Přednáška 5)



25 / 34

Vnitřní a vnější spojení vnější přirozená a θ-spojení v SQL: SELECT * FROM hjméno 1 i NATURAL FULL OUTER JOIN hjméno 2 i SELECT * FROM hjméno 1 i NATURAL LEFT OUTER JOIN hjméno 2 i SELECT * FROM hjméno 1 i NATURAL RIGHT OUTER JOIN hjméno 2 i SELECT * FROM hjméno 1 i FULL OUTER JOIN hjméno 2 i ON hpodmínkai SELECT * FROM hjméno 1 i LEFT OUTER JOIN hjméno 2 i ON hpodmínkai SELECT * FROM hjméno 1 i RIGHT OUTER JOIN hjméno 2 i ON hpodmínkai princip vnějších spojení: ve výsledku levého (pravého/oboustranného) vnějšího spojení jsou zahrnuty i n-tice z první (druhé/obou) relace(í), které jsou nespojitelné v tabulkách se projevuje přítomností NULL (značí „absenci hodnotÿ) doposud diskutovaná spojení jsou tzv. vnitřní spojení (v SQL lze místo NATURAL JOIN psát NATURAL INNER JOIN) V. Vychodil (KMI/DATA1, Přednáška 5)



26 / 34

Příklad (Vnější přirozená spojení) D1

D2

levé

oboustranné

pravé

FOO BAR BAZ

BAR BAZ QUX

FOO BAR BAZ QUX

FOO BAR BAZ QUX

FOO BAR BAZ QUX

444 555 555 666


444 444 444 555 555 555 555 555 666

444 444 444 555 555 555 555 555 666

444 444 444 555 555 555 555 555

ghi def ghi abc

103 102 103 101

111 102 102 103 103 103 103


ghi ghi ghi def def ghi ghi ghi abc

103 103 103 102 102 103 103 103 101


ghi ghi ghi def def ghi ghi ghi abc abc ghX

103 103 103 102 102 103 103 103 101 111 103

ttt uuu vvv www yyy ttt uuu vvv zzz xxx

ghi ghi ghi def def ghi ghi ghi abc ghX

103 103 103 102 102 103 103 103 111 103


SELECT * FROM r1 NATURAL LEFT OUTER JOIN r2 SELECT * FROM r1 NATURAL FULL OUTER JOIN r2 SELECT * FROM r1 NATURAL RIGHT OUTER JOIN r2 V. Vychodil (KMI/DATA1, Přednáška 5)



27 / 34

Související problémy patologický rys: výsledek vnějšího spojení nelze formalizovat jako relaci nad schématem ({{hx, 10i, hy, 20i}, {hx, 66i}, {hy, 77i}} může být vysledkem vnějšího spojení) související otázky: Jak implementovat množinové relační operace? Jak vlastně implementovat jakékoliv relační operace? Co je výsledkem restrikce, pokud není hodnota atributu definovaná? .. .

je nutné: explicitně zavést nedefinovanou hodnotu (označení ω, v SQL NULL) uvažovat artimetické, logické a další operace, jejichž argumenty mohou být nedefinované (jaké jsou jejich výsledky?) rozšířit (zprznit) relačního modelu dat V. Vychodil (KMI/DATA1, Přednáška 5)



28 / 34

3VL v SQL přístup k „nedefinovaným hodnotámÿ v SQL: použití fragmentu Kleeneho tříhodnotové logiky (3VL) s hodnotami {0, ω, 1} a interpretací logických spojek c, d, i, e, n danou tabulkami: ∧ 0 ω 1 ∨ 0 ω 1 → 0 ω 1 ↔ 0 ω 1 ¬ 0 0 0 0 0 0 ω 1 0 1 1 1 0 1 ω 0 0 1 ω 0 ω ω ω ω ω 1 ω ω ω 1 ω ω ω ω ω ω 1 0 ω 1 1 1 1 1 1 0 ω 1 1 0 ω 1 1 0 bohužel, nedává smysl, protože: nespecifita 6= pravdivost bereme-li v úvahu nespecifitu, přestává platit princip kompozicionality, to jest pravdivost složených formulí (v daném ohodnocení) nezávisí pouze na pravdivosti podformulí (a spojkách), ale i na struktuře podformulí. (!!) například: pokud je e(ϕ) = ω a e(ψ) = ω, pak dle 3VL máme e(ϕ d ψ) = ω; ale pokud je ψ ve tvaru nϕ, musí být e(ϕ d ψ) = 1 (tertium non datur, !!) V. Vychodil (KMI/DATA1, Přednáška 5)



29 / 34

Příklad (Příklad důsledků 3VL v SQL, C. J. Date) CREATE TABLE r1 (x NUMERIC NOT NULL PRIMARY KEY, yn VARCHAR); CREATE TABLE r2 (y NUMERIC NOT NULL PRIMARY KEY, zn VARCHAR); INSERT INTO r1 VALUES (45, ’London’); INSERT INTO r2 VALUES (33, NULL); SELECT x, y FROM r1, r2 WHERE (yn <> zn OR zn <> ’Paris’); x y logický výsledek: , protože 45 33

buď zn = ’Paris’ a tím pádem yn 6= zn nebo zn 6= ’Paris’

výsledek dotazu v SQL: x y (prázdná relace), protože ω ∨ ω = ω You can never trust the answers you get from a database with nulls. — C. J. Date V. Vychodil (KMI/DATA1, Přednáška 5)



30 / 34

Alternativní přístup: designované hodnoty domén motivace: Snaha obejít problémy s 3VL a nedefinovanými hodnotami. úskalí předchozího řešení: NULL jako „pravdivostní hodnotaÿ nedává smysl další možnost: používat místo NULL speciální hodnoty domén formalizace: uvažovat domény Dy ∪ {ωy } rozšířené o ωy (nedef. hodnota domény atributu y) typicky: ωy jsou prázdné řetězce, zpeciální znaky, čísla, . . . přetrvávající nevýhody: − soudobé SŘBD přímo nepodporují (například u vnějších spojení) − problémy s použitím ω omylem jako „skutečnou hodnotuÿ (zdroj chyb) y V. Vychodil (KMI/DATA1, Přednáška 5)



31 / 34

Odvozená operace: Polorozdíl Definice (polorozdíl, angl.: semidifference) Mějme relace D1 a D2 na schématech R1 a R2 . Položme: D1 n D2 = D1 \ πR1 (D1 ./ D2 ). Relace D1 n D2 se nazývá polorozdíl D1 a D2 (v tomto pořadí). Tutorial D (zobecňuje MINUS): hrelační-výraz 1 i NOT MATCHING hrelační-výraz 2 i SQL: SELECT * FROM hjméno 1 i EXCEPT SELECT DISTINCT hjméno 1 i.* FROM hjméno 1 i NATURAL JOIN hjméno 2 i význam: r1 ∈ D1 n D2 p. k. r1 ∈ D1 není spojitelná s žádnou n-ticí z D2 V. Vychodil (KMI/DATA1, Přednáška 5)



32 / 34

Příklad (Vnější spojení a polorozdíly) D1

D2

levé

oboustranné

pravé

FOO BAR BAZ

BAR BAZ QUX

FOO BAR BAZ QUX

FOO BAR BAZ QUX

FOO BAR BAZ QUX

444 555 555 666


444 444 444 555 555 555 555 555 666

444 444 444 555 555 555 555 555 666

444 444 444 555 555 555 555 555

ghi def ghi abc

103 102 103 101

111 102 102 103 103 103 103


D1 n D2 =


ghi ghi ghi def def ghi ghi ghi abc

103 103 103 102 102 103 103 103 101

FOO BAR BAZ 666 abc 101


ghi ghi ghi def def ghi ghi ghi abc abc ghX

103 103 103 102 102 103 103 103 101 111 103


ghi ghi ghi def def ghi ghi ghi abc ghX

103 103 103 102 102 103 103 103 111 103


BAR BAZ QUX D2 n D1 = abc 111 zzz ghX 103 xxx



33 / 34

Přednáška 5: Závěr pojmy k zapamatování: úplné přirozené spojení, bezeztrátová dekompozice θ-spojení a spojení na rovnost tranzitivní uzávěr, lokální pojmenování, rekurzivní dotazy vnitřní a vnější spojení, nedefinované hodnoty, polorozdíl použité zdroje: Date C. J.: Database in Depth: Relational Theory for Practitioners O’Reilly Media 2005, ISBN 978–0596100124 Date C. J., Darwen H.: Databases, Types and the Relational Model Addison Wesley 2006, ISBN 978–0321399427 Maier D: Theory of Relational Databases Computer Science Press 1983, ISBN 978–0914894421 V. Vychodil (KMI/DATA1, Přednáška 5)



34 / 34

34

Recommend Documents