Datenbanksysteme I Übung: Normalformen undRelationale Algebra · Nachbereitung Aufgabenblatt 2: Lösungen und Probleme Vorbereitung Aufgabenblatt 3: Funktionale Abhängigkeiten Normalformen

Datenbanksysteme IÜbung:

Normalformen und Relationale Algebra

29.11.2007

Jana Bauckmann

Felix Naumann | Datenbanksysteme I | WS 06/07

2

Organisatorisches

■ Zur Abgabe:

□ Eine Aufgabe pro Blatt – sonst -1Punkt

□ Namen auf jedes Blatt – sonst -1Punkt

■ Übungstermine nächste Woche

□ MO, 3.12., 13:30 Uhr (wie gehabt)

□ MI, 5.12., 13:30 Uhr Übung und 17:00 Uhr Vorlesung


3

Überblick

■ Nachbereitung Aufgabenblatt 2: Lösungen und Probleme

■ Vorbereitung Aufgabenblatt 3:

□ Funktionale Abhängigkeiten

□ Normalformen

□ Relationale Algebra

■ Besprechen von Aufgabenblatt 3


4

PunktePunkte für Übung 1

0

5

10

15

20

25

30

35

40

1 9 17 25 33 41 49 57 65 73 81 89 97 105 113

Student

Punk

te

100%

50%

25%

Punkte für Übung 2

0

5

10

15

20

25

30

35

40

1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 113

Student

Punk

te

100%

50%


5

Aufgabe: FD Ableitung

Gegeben:

■ R(A, B, C, D)

■ AB → C

■ C → D

■ D → A

Fragen

■ Suche alle nicht-trivialen FDs (mit nur einem Attribut rechts).

□ Wieviele vermutest du?

■ Welches sind die Schlüssel von R?


6

Aufgabe: Projektion

Gegeben R(A, B, C, D, E) mit FDs

■ AB → DE

■ C → E

■ D → C

■ E → A

Gesucht: FDs auf der Projektion S(A, B, C)


7

Aufgabe: BCNF und Dekomposition

Gegeben R(A, B, C, D) mit FDs

■ AB → C

■ C → D

■ D → A

Gesucht

■ Alle FDs, die BCNF verletzen

■ Dekomponierte Relationen in BCNF


8

Lösung: BCNF und Dekomposition

■ FDs (aus Aufgabe FD Ableitung):

□ C → D, C → A, D → A, AB → CD, BC → AD, BD → AC, AC → D

■ ⇒ Schlüssel {AB}, {B,C}, {B,D}

■ Reminder: R ist in BCNF ⇔ die linke Seite jeder nicht-trivialen FD ist Schlüssel oder Superschlüssel

■ ⇒ FDs, die BCNF verletzen: C → D, C → A, D → A, AC → D

■ ⇒ Zerlegen nach einer dieser FDs, alle Varianten auf folgenden Folien


9

Lösung: BCNF und DekompositionZerlegung nach C → D

■ Erweitern der rechten Seite per D → A (oder per C → A; liefert gleiches Ergebnis): C → AD

■ ⇒ Zerlegen in

□ R1(C,A,D) – = alle Attribute der FD– FDs (per Projektion ermittelt): C → AD, D → A, AC → D

□ R2(C,B) – = linke Seite der FD und „restliche“ Attribute aus R– FDs (per Projektion ermittelt): keine

■ D → A verletzt BCNF in R1, also weiter Zerlegen in

□ R3(D,A) mit FD D → A

□ R4(D,C) mit FD C → D

■ Hinweis: Schlüssel in den zerlegten Relationen werden anhand der FDs bestimmt.


10

Lösung: BCNF und DekompositionZerlegung nach C → A

■ Erweitern der rechten Seite per C → D zu C → AD

■ Analog weiter wie auf vorheriger Folie


11

Lösung: BCNF und DekompositionZerlegung nach D → A

■ Erweitern der rechten Seite: nichts zu Erweitern

■ ⇒ Zerlegen in

□ R1(D,A) mit FD D → A

□ R2(D,B,C) mit FDs BC → D, BD → C, C → D

■ C → D verletzt BCNF in R2, also weiter Zerlegen in

□ R3(C,D) mit FD C → D

□ R4(C,B) ohne FD


12

Lösung: BCNF und DekompositionZerlegung nach AC → D

■ Erweitern der rechten Seite: nichts zu Erweitern

■ ⇒ Zerlegen in

□ R1(A,C,D) mit FD AC → D

□ R2(A,C,B) mit FDs AB → C, BC → A, C → A

■ C → A verletzt BCNF in R2, also weiter Zerlegen in

□ R3(C,A) mit FD C → A

□ R4(C,B) ohne FD


13

Überblick

■ Nachbereitung Aufgabenblatt 2: Lösungen und Probleme

■ Vorbereitung Aufgabenblatt 3:

□ Funktionale Abhängigkeiten

□ Normalformen

□ Relationale Algebra

■ Besprechen von Aufgabenblatt 3


14

Anfragen der relationalen Algebra

Schema

■ Product(maker, model, type)

□ Beispieltupel: (B, 1005, pc)

■ PC(model, speed, ram, hd, rd, price)

□ Beispieltupel: (1005, 1000, 128, 20, 12xDVD, 1499)

■ Laptop(model, speed, ram, hd, screen, price)

□ Beispieltupel: (2008, 650, 64, 10, 12.1, 1249)

■ Printer(model, color, type, price)

□ Beispieltupel: (3005, true, bubble, 200)


15

RA Anfrage 1

Schema






□ Beispieltupel: (2008, 650, 64, 10, 12.1, 1249)



■ Anfrage 1: Welche PC Modelle haben eine Geschwindigkeit von mindestens 1000?


16

RA Anfrage 2

Schema






□ Beispieltupel: (2008, 650, 64, 10, 12.1, 1249)



■ Anfrage 2: Welche Hersteller bauen Laptops mit einer Harddisk von mindestens 10GB?


17

RA Anfrage 3

Schema






□ Beispieltupel: (2008, 650, 64, 10, 12.1, 1249)



■ Anfrage 3: Finden Sie Modellnummer und Preis aller Produkte (jeden Typs), die von Hersteller „B“ gebaut werden.

■ Zusätzlich: Baumdarstellung


18

RA Anfrage 4

Schema






□ Beispieltupel: (2008, 650, 64, 10, 12.1, 1249)



■ Anfrage 4: Finde die Modellnummer aller Farblaserdrucker.


19

RA Anfrage 5

Schema






□ Beispieltupel: (2008, 650, 64, 10, 12.1, 1249)



■ Anfrage 5: Finde alle Hersteller, die Laptops aber keine PCs herstellen.

■ Zusätzlich: Baumdarstellung


20

RA Anfrage 6

Schema






□ Beispieltupel: (2008, 650, 64, 10, 12.1, 1249)



■ Anfrage 6: Finde alle Harddisk-Größen, die in mehr als zwei PCs vorkommen.


21

RA Anfrage 7

Schema






□ Beispieltupel: (2008, 650, 64, 10, 12.1, 1249)



■ Anfrage 7: Finde alle Paare von PCs, die gleiche Geschwindigkeit und gleiche Hauptspeichergröße haben. Ein Paar sollte allerdings nur einmal vorkommen.


22

Aufgabe: Kardinalitäten

Gegeben

■ Relation R mit n Tupeln

■ Relation S mit m Tupel

Gesucht jeweils minimale und maximale Anzahl von Tupeln in

■ R ∪ S

■ R ⋈ S■ σC(R) × S■ πL(R)—S


23

Aufgabe: Multimengen

Gelten die folgenden Regeln für Mengen? Für Multimengen?

■ (R ∪ S) ∪ T = R ∪ (S ∪ T)

■ (R ∩ S) - T = R ∩ (S - T)

Documents

Datenbanksysteme I Übung: Normalformen undRelationale Algebra · Nachbereitung Aufgabenblatt 2: Lösungen und Probleme Vorbereitung Aufgabenblatt 3: Funktionale Abhängigkeiten Normalformen