ppt

 Documents

 67 views
of 23
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Kapitel 11: Relationale Entwurfstheorie 11.1 Funktionalabhängigkeiten 11.2 Normalformen 11.3 Relationendekomposition 11.4 Relationensynthese 11.5 Ergänzungen…
Share
Transcript
Kapitel 11: Relationale Entwurfstheorie 11.1 Funktionalabhängigkeiten 11.2 Normalformen 11.3 Relationendekomposition 11.4 Relationensynthese 11.5 Ergänzungen zum algorithmischen Ansatz Informationssysteme SS2004 11-1 Problem Bestellungen (Datum, KNr, PNr, Bez, Preis, Gewicht, Menge) "Typische" Ausprägung: Datum KNr PNr Bez Preis Gewicht Menge 16.7. 1 1 Papier 20.00 2.000 100 21.7. 1 1 Papier 20.00 2.000 200 26.10. 2 1 Papier 20.00 2.000 100 26.10. 2 5 Disketten 20.00 0.500 50 Informationssysteme SS2004 11-2 11.1 Funktionalabhängigkeiten (FAs, FDs) Definition: Für X = {X1, ..., Xm}  sch(R) und Y = {Y1, ..., Yn}  sch(R) gilt die Funktionalabhängigkeit X Y, wenn jederzeit für je zwei Tupel r, s  val(R) gelten muß: (r.X1=s.X1  ...  r.Xm=s.Xm)  (r.Y1=s.Y1  ...  r.Yn=s.Yn) Beispiel: Bestellungen (Datum, KNr, PNr, Bez, Preis, Gewicht, Menge) Es gelten: Datum, KNr, PNR  Menge PNr  Bez, Preis, Gewicht Es gelten nicht: KNr, PNR  Menge PNr  Datum Entwurfsziel: Alle FAs in Primärschlüsselbedingungen ausdrücken Informationssysteme SS2004 11-3 Ableitungsregeln für Funktionalabhängigkeiten Definition: Sei F eine Menge von FAs über sch(R). Die transitive Hülle F+ ist die Menge der aus F logisch ableitbaren FAs. Ableitungskalkül (Armstrong-Regeln): Seien X  sch(R), Y  sch(R), Z  sch(R). Regel 1 (Reflexivität): Wenn Y  X, dann gilt: X  Y. Regel 2 (Erweiterung): Wenn X  Y, dann gilt: XZ  YZ Regel 3 (Transitivität): Wenn X  Y und Y  Z, dann gilt: X  Z. Weitere Ableitungsregeln: Regel 4 (Vereinigung): Wenn X  Y und X  Z, dann gilt: X  YZ. Regel 5 (Pseudotrans.): Wenn X  Y und WY  Z mit W  sch(R), dann gilt: XW  Z. Regel 6 (Zerlegung): Wenn X  Y und Z  Y, dann gilt: X  Z. Satz: Die Armstrong-Regeln bilden einen korrekten und vollständigen Ableitungskalkül für F+. Informationssysteme SS2004 11-4 Beispiel: Ableitung von Funktionalabhängigkeiten Bestellungen (Datum, KNr, PNr, Bez, Preis, Gewicht, Menge) F = { Datum, KNr, PNR  Menge, PNr  Bez, Preis, Gewicht }. Es folgen: Datum, KNr, PNR  PNr nach der Reflexivitätsregel, Bez, Preis, Gewicht  Bez nach der Reflexivitätsregel, PNr  Bez nach der Transitivitätsregel, Datum, KNr, PNr  Bez nach der Transitivitätsregel Informationssysteme SS2004 11-5 Ableitbarkeitstest für FAs: Xplus-Algorithmus Definition: Sei R eine Relation mit sch(R) und FA-Menge F, und sei X  sch(R). Die Hülle X+ von X ist die Menge aller A  sch(R) mit X  A  F+. Xplus-Algorithmus: procedure xplus (X: set of attribute): set of attribute; var H: set of attribute; newattr: Boolean; begin H := X; newattr := true; while newattr do (* Invariante: X  H *) newattr := false; for each Y  Z  F do if Y  H then if not (Z  H) then H := H  Z; newattr := true; fi; fi; od od return H; end xplus; Informationssysteme SS2004 11-6 Beispiel: Xplus-Algorithmus sch(R) = {A, B, C, D, E, G} F = {AB  C, ACD  B, BC  D, BE  C, C  A, CG  BD, CE  AG, D  EG} X = {B, D} Informationssysteme SS2004 11-7 Bestimmung aller Schlüsselkandidaten Definition: Sei R eine Relation mit sch(R) und FA-Menge F, und sei X  sch(R). X  sch(R) ist ein Schlüsselkandidat, wenn X  sch(R)  F+ gilt und es keine echte Teilmenge von X gibt, die diese Eigenschaft hat. A  sch(R) ist Schl.attribut, wenn es in einem Schl.kandidaten vorkommt. procedure findkeys: set of set of attribute; var K: set of set of attribute; iskey: Boolean; K := ; for each S  2sch(R) do iskey := true; if xplus (S)  sch(R) then iskey := false fi; for each A  S while iskey do if xplus (S - {A}) = sch(R) then iskey := false fi od; if iskey then K := K  {S} fi od; return K; Informationssysteme SS2004 11-8 11.2 Relationale Normalformen Definition: Sei R eine Relation mit sch(R) und FA-Menge F. R ist in Boyce-Codd-Normalform (BCNF), wenn für jede FA X  A  F+ mit X  sch(R), A  sch(R) und A  X gilt, daß X einen Schlüsselkandidaten enthält. Definition: Sei R eine Relation mit sch(R) und FA-Menge F. R ist in 3. Normalform (3NF), wenn für jede FA X  A  F+ mit X  sch(R), A  sch(R) und A  X gilt, daß X einen Schlüsselkandidaten enthält oder A ein Schlüsselattribut ist. Satz: Jede Relation in BCNF ist auch in 3NF. Informationssysteme SS2004 11-9 Algorithmus für BCNF-Test procedure BCNFtest: Boolean; var isbcnf: Boolean; begin isbcnf := true; for each X  A  F while isbcnf do if A  X then if XPlus(X)  sch(R) then isbcnf := false fi fi; od return isbcnf; end BCNFtest; Informationssysteme SS2004 11-10 Beispiele: Normalformen 1) Best (Datum, KNr, PNr, Menge) mit F = {Datum, KNr, PNr  Menge} und Prod (PNr, Bez, Preis, Gewicht) mit F = {PNr  Bez, Preis, Gewicht} 2) Vorlesungen (Titel, Zeit, Raum) mit F = {Titel  Raum, Zeit, Raum  Titel} Beispielausprägung: Titel Zeit Raum Datenbanken Di 9-11 HS 2 Datenbanken Do 9-11 HS 2 Compiler Di 9-11 HS 3 Compiler Mi 13-15 HS 3 Betriebssysteme Mi 13-15 HS 2 Informationssysteme SS2004 11-11 11.3 Relationendekomposition Definition: Sei R eine Relation mit sch(R) und FA-Menge F. Eine Zerlegung von R in R1 (X1), ..., Rk (Xk) mit Xi  sch(R) und X1  ..  Xk = sch(R) heißt abhängigkeitsbewahrend, wenn gilt: ( F      | X1 )  ...  ( F | Xk )   F Definition: Sei R eine Relation mit sch(R) und FA-Menge F. Eine Zerlegung von R in R1 (X1), ..., Rk (Xk) mit Xi  sch(R) und X1  ...  Xk = sch(R) heißt (projektion-join-) verlustfrei, wenn für alle möglichen Ausprägungen, die F erfüllen, gilt: [X1](R) || ... || [Xk](R) = R. Informationssysteme SS2004 11-12 Beispiele: Abhängigkeitsbewahrung 1) Bestellungen (Datum, KNr, PNr, Bez, Preis, Gewicht, Menge}mit F = {Datum, KNr, PNR  Menge, PNr  Bez, Preis, Gewicht} Zerlegung in Best (Datum, KNr, PNr, Menge) mit F1 = {Datum, KNr, PNR  Menge} und Prod (PNr, Bez, Preis, Gewicht) mit F2 = {PNr  Bez, Preis, Gewicht} 2) Vorlesungen (Titel, Zeit, Raum) mit F = {Titel  Raum, Zeit, Raum  Titel} Zerlegung in Vorlesungsräume (Titel, Raum) mit F1 = {Titel  Raum} und Vorlesungszeiten (Titel, Zeit) mit F2 =  Informationssysteme SS2004 11-13 Beispiele: Verlustfreiheit Bestellungen (Datum, KNr, PNr, Bez, Preis, Gewicht, Menge) mit F = {Datum, PNr, KNr  Menge, PNr  Bez, Preis, Gewicht} Datum KNr PNr Bez Preis Ge- Menge wicht 16.7. 1 1 Papier 20.00 2.000 100 16.7. 1 5 Disketten 20.00 0.500 50 Zerlegung in: Datum KNr PNr Menge und Datum Bez Preis Gewicht 16.7. 1 1 100 16.7. Papier 20.00 2.000 16.7. 1 5 50 16.7. Disket- 20.00 0.500 ten Informationssysteme SS2004 11-14 Verlustfreie BCNF-Dekomposition Satz: Zu jeder Relation R gibt es eine abhängigkeitsbewahrende und verlustfreie Zerlegung von R in 3NF-Relationen. Satz: Zu jeder Relation R gibt es eine verlustfreie Zerlegung von R in BCNF-Relationen.. Satz: Sei R eine Relation mit sch(R) und einer FA-Menge F. Sei X  Y  F+ mit X  Y = . Die Zerlegung von R in R' (X, Y) und R'' (X, sch(R) - Y) ist verlustfrei. Algorithmus: Teste, ob R in BCNF ist Falls R nicht in BCNF ist (* es gibt eine Funktionalabhängigkeit X  Y  F+ mit X  Y =  und X  sch(R)  F+ *) dann zerlege R in R' (X, Y) und R'' (X, sch(R) - Y) wiederhole den Zerlegungsalgorithmus für R' und R'' Informationssysteme SS2004 11-15 Beispiel: Relationendekomposition R (FlugNr, Datum, Abflugzeit, FSNr, SitzNr, TicketNr, Name, Adresse, GNr, Gewicht) F = {FlugNr, Datum  Abflugzeit, FSNr, FlugNr, Datum, TicketNr  SitzNr, TicketNr  Name, Adresse, Schlüsselkandidat: GNr  Gewicht } FlugNr, Datum, TicketNr, GNr Zerlegungsschritte: 1. Zerlegung von R entlang von FlugNr, Datum  Abflugzeit, FSNr: R1 (FlugNr, Datum, Abflugzeit, FSNr) und R2 (FlugNr, Datum, SitzNr, TicketNr, Name, Adresse, GNr, Gewicht) 2. Zerlegung von R2 entlang von FlugNr, Datum, TicketNr  SitzNr: R21 (FlugNr, Datum, TicketNr, SitzNr) und R22 (FlugNr, Datum, TicketNr, Name, Adresse, GNr, Gewicht) 3. Zerlegung von R22 entlang von TicketNr  Name, Adresse: R221 (TicketNr, Name, Adresse) und R222 (TicketNr, FlugNr, Datum, GNr, Gewicht) 4. Zerlegung von R222 entlang von GNr  Gewicht: R2221 (GNr, Gewicht) und R2222 (GNr, FlugNr, Datum, TicketNr) Informationssysteme SS2004 11-16 11.4 Relationensynthese Definition: Sei eine Relation mit sch(R) und FA-Menge F. Eine FA-Menge F' heißt Überdeckung (engl. cover) von F, wenn gilt: (F')+ = F+. Definition: Eine Überdeckung F' von F heißt minimal, wenn gilt: 1) In jeder FA von F' hat die rechte Seite ein Attribut. 2) Keine echte Teilmenge von F' ist eine Überdeckung von F. 3) Für jede FA X  A  F' und jede echte Teilmenge X' von X F'' := F' - { X  A}  {X'  A} keine Überdeckung mehr von F. Informationssysteme SS2004 11-17 Beispiel: minimale Überdeckung sch(R) = {Ang(estellten)Nr, Name, Gehalt, Leistung(sbeurteilung), Tarif(klasse), Abt(eilungs)Nr, ProjektNr, Projektleiter, Abt(eilungs)leiter} F = { AngNr  Name, Schritt 1:  { AngNr  Name, AngNr  Gehalt, AngNr  Gehalt, AngNr  Tarif, AngNr  Tarif, AngNr  AbtNr, AngNr  AbtNr, AngNr  Abtleiter, AngNr  Abtleiter, ProjektNr  Projektleiter, ProjektNr  Projektleiter, AbtNr  Abtleiter, AbtNr  Abtleiter, AngNr, Abtleiter  Leistung, AngNr  Leistung, Tarif, Leistung  Gehalt} Tarif, Leistung  Gehalt} Schritt 2:  { AngNr  Name, AngNr  Tarif, AngNr  AbtNr, ProjektNr  Projektleiter, AbtNr  Abtleiter, AngNr  Leistung, Tarif, Leistung  Gehalt} = F' Informationssysteme SS2004 11-18 Algorithmus zur Berechnung der Min-Cover procedure mincover: set of FDs; var G: set of FDs; procedure xplus (arg1: set of FDs, arg2: set of attribute): set of attribute; procedure reduce (arg: set of FDs): set of FDs; var H: set of FDs; H := arg; for each XAH do for each CX do Hred := H - { XA}  {(X-{C})A}; if A  xplus (H, X-{C})) then H := Hred fi; od; od; return H; G := reduce(F); for each XAG do G := G - { XA}; if not (A  xplus (G, X)) then G := G  { XA} fi; od; return G; Informationssysteme SS2004 11-19 Algorithmus zur Relationensynthese Schritt 1: Bereche eine minimale Überdeckung F' von F. Schritt 2: Partitioniere die FAs in F' nach gleichen linken Seiten, d.h. für jedes Xi fasse alle XiA1, ..., XiAki zusammen Schritt 3: Bilde für jede Partition von Schritt 2 eine Relation Ri mit sch(Ri) = Xi  {Ai, ..., Aki}. Schritt 4: Falls sch(R) - ( i sch(Ri) ) nichtleer ist, bilde eine weitere Relation R' mit sch(R') = sch(R) - ( i sch(Ri) ). Schritt 5: Falls keine der Relationen Ri, R' einen Schlüssel von R enthält, erzeuge eine Relation R'', deren Schema ein Schlüssel von R ist. Satz: Der Algorithmus zur Relationensynthese erzeugt eine abhängigkeitsbewahrende und verlustfreie 3NF-Zerlegung von R. Informationssysteme SS2004 11-20 Beispiel: Relationensynthese sch(R) = {Ang(estellten)Nr, Name, Gehalt, Leistung(sbeurteilung), Tarif(klasse), Abt(eilungs)Nr, ProjektNr, Projektleiter, Abt(eilungs)leiter} F' = { AngNr  Name, AngNr  Tarif, AngNr  AbtNr, ProjektNr  Projektleiter, AbtNr  Abtleiter, AngNr  Leistung, Tarif, Leistung  Gehalt} Ergebnis der Relationensynthese: Angestellte (AngNr, Name, Tarif, Leistung, AbtNr) Projekte (ProjektNr, Projektleiter) Abteilungen (AbtNr, Abtleiter) Lohn (Tarif, Leistung, Gehalt) Projektmitarbeit (AngNr, ProjektNr) Informationssysteme SS2004 11-21 11.5 Ergänzungen (1) 1) weitere Zerlegung von BCNF-Relationen: Angestellte (ANr, Informatikkenntnisse, Kinder) mit F =  ANr Informatikkenntnisse Kinder 1 Leda Sabrina 1 Oracle Sabrina 2 Leda Pierre 2 Leda Sabrina sollte weiter zerlegt werden in AngInfKenntnisse (ANr, Informatikkenntnisse) und AngKinder (ANR, Kinder) 2) unnötig feine Zerlegungen: Produkte (PNr, Bez, Preis) mit F = {PNr  Bez, PNr  Preis} sollte nicht zerlegt werden in Produktbez (PNr, Bez) und Produktpreise (PNr, Preis) Informationssysteme SS2004 11-22 11.5 Ergänzungen (2) 3) Zerlegung aufgrund irrelevanter Funktionalabhängigkeiten: Bestellungen (Datum, KNr, PNr, Bez, Preis, Gewicht, Menge, Summe) mit F = {Datum, KNr, PNr  Menge, PNr  Bez, Preis, Gewicht, Preis, Menge  Summe} sollte nicht zur Relatione führen Preise (Preis, Menge, Summe) 4) Nicht-BCNF-Relationen, die unproblematisch sind: Kunden (KNr, Name, Postleitzahl, Stadt, Strasse) mit F = {KNr  Name, Postleitzahl, Stadt, Strasse, Postleitzahl  Stadt } muß nicht notwendigerweise zerlegt werden in Kundenadressen (KNr, Name, Postleitzahl, Strasse) und Postleitzahlenverzeichnis (Postleitzahl, Stadt) 5) M:N-Relationships ohne Attribute: Sitze (FlugNr, Datum, SitzNr) muß bei der Relationendekomposition ggf. hinzugefügt werden Informationssysteme SS2004 11-23
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks