Datenbanken - Wintersemester PDF

Preview

Summary

1 Konzeptuelle Modellierung Datenbankentwurf Abstraktionen des Datenbankentwurfs Konzeptuelle Ebene Implementationsebene Physische Ebene Phasen Anforderungsanalyse Identifikation von Organisationseinheiten Identifikation der zu Aufgaben Filterung Satzklassifikationen Formalisierung Entity (Gegenstan...

Description

1 Konzeptuelle Modellierung Datenbankentwurf  Abstraktionen des Datenbankentwurfs - Konzeptuelle Ebene - Implementationsebene - Physische Ebene  Phasen

Anforderungsanalyse  Identifikation von Organisationseinheiten  Identifikation der zu unterstützenden Aufgaben  Anforderungs-Sammelplan  Anforderungs-Sammlung  Filterung  Satzklassifikationen  Formalisierung Entity/Relationship-Modellierung  Entity (Gegenstandstyp)  Relationship (Beziehungstyp)  Attribut (Eigenschaft)  Schlüssel (Identifikation)  Rolle

Funktionalitäten

2

Bei n-stelligen Beziehungen:

Beispiel-Beziehung: betreuen

  

betreuen: Professoren x Studenten  Seminarthemen  Student darf bei selbem Professor nur ein Seminarthema ableisten betreuen: Seminarthemen x Studenten  Professoren  Studenten dürfen dasselbe Thema nur einmal bearbeiten Möglich: Professoren können dasselbe Thema an mehrere Studenten verteilen; Thema kann von mehreren Professoren vergeben werden (an unterschiedliche Studenten)

(min, max)-Notation

3



Beispiel: Universitätsschema

Schwache, existenzabhängige Entities

 

Beziehung zwischen stark und schwach immer 1:N (selten: 1:1) Schlüssel ist PrüfTeil und MatrNr (PrüfTeil alleine bringt nix, keine Zuordnung)

Aggregation

Relationales Datenmodell

4

Grundlagen D 1 , D 2 ,…, D n Domänen (~Wertebereiche)  D1 x D2 x … x Dn (Teilmenge des  Relation: R ⊆ Kreuzprodukts)  Bsp.: Telefonbuch ⊆ string x string x integer  Tupel: t ⊆ R  Schema: legt Struktur der gespeicherten Daten fest  Ausprägung: aktueller Zustand der Datenbasis  Schlüssel: minimale Menge von Attribute, deren Werte Tupel eindeutig identifizieren  Primärschlüssel (unterstrichen): besondere Bedeutung bei Reformierung von Tupeln

Relationale Darstellung von Entitytypen  R: {[SchlüsselE1, SchlüsselE2, …, AttributeR]}

hören: {[MatrNr: integer, VorlNr: integer]}  N:M-Beziehung  alle Schlüssel  lesen: {[PersNr: integer, VorlNr: integer]}  1:N-Beziehung  Schlüssel da wo N steht  voraussetzen: {[Vorgänger: integer, Nachfolger: integer]}  Rollen verwenden  prüfen: {[MatrNr: integer, VorlNr: integer, PersNr: integer, Note: decimal]}  Note als Attribut dazufügen  Unterscheidung zwischen Schlüssel in Relation Studenten/Vorlesungen und hören  Ausprägung der Beziehung hören 

Verfeinerung des relationales Schemas

5 

Bei 1:N-Beziehung (binäre Beziehung) kann man Relationen mit gleichem Schlüssel zusammenfassen  Da wo N steht hinzufügen



Vorlesungen: {[VorlNr, Titel, SWS]} Professoren: {[PersNr, Name, Rang, Raum]} lesen: {[VorlNr, PersNr]} Vorlesungen: {[VorlNr, Titel, SWS, gelesenVon]}  lesen als Fremdschlüssel in Entity-Relation Professoren Professoren: {[PersNr, Name, Rang, Raum]}



Relationale Mdodellierung schwacher Entitytypen

Prüfungen: {[MatrNr: integer, PrüfTeil:string, Note: integer]} umfassen: {[MatrNr: integer, PrüfTeil:string, VorlN: integer]} abhalten: {[MatrNr: integer, PrüfTeil:string, PersNr: integer]}

  

Relationale Algebra  Selektion  Zeile aus Tabelle (mit allen Studenten die mindestens im 10. Semester sind) wird rausgenommen Projektion



 Spalte Rang wird aus Tabelle Professoren rausgenommen (gleiche Einträge werden dabei zusammengefasst) 

Kartesisches Produkt hören x Vorlesungen  Jeder Zeile aus hören mit jeder Zeile aus VL (heißt jeder Student hört jede Vorlesung)



Umbenennung umbenannt

 Relation (Tabelle) voraussetzen wird in V2

 Attribut (hier Vorgänger) aus Tabelle voraussetzen wird in Voraussetzung umbenannt  -

Join Allgemeiner Join

6

 Bedingung kann hingeschrieben werden, zB. VL.gelesenVon = Prof.PersNr Natürlicher Join

-

 Zwei Tabellen müssen mindestens ein Spaltennamen gemeinsam haben  Einträge dieser Spalte die in beiden vorkommen werden genommen und dann die restl. Spalten dieser Zeilen ergänzt

-

Linker äußerer Join

 Analog rechter äußerer Join -

Äußerer Join

-

Semi-Join von L mit R:

 Analog linker äußerer Join -

Anti-Semi-Join von L mit R:

7 

Division

alle/jeder Anderer Ausdruck:

 Meist bei Angabe



Mengendurchschnitt R ∩ S  Müssen wieder einen Spaltennamen gemeinsam haben Anderer Ausdruck: R ∩ S = R – (R – S)



Gruppierung/ Aggregation  Count zählt die Vorlesungen die vom jeweilige Prof gelesen werden, sum summiert die SWS

Relationenkalkül  Anfrage hat Form {t | P(t)} mit P(t) Formel  Beispiel: Studenten mit mindestens einer VL bei Curie





Allquantor: Wer hat alle vierstündigen VL gehört

Definition Tupelkalkül Atome - s ϵ R mit s Tupelvariable und R Relationenname - s.A ϕ t.B mit s und t Tupelvariablen, A und B Attributnamen und ϕ Vergleichsoperator (=, ≤ , …) - s.A ϕ c mit c Konstante Formeln - Alle Atome sind Formeln - Ist P Formel, so auch ¬ P und (P) - Sind P1 und P1 Formeln, so auch P1 ∧ P2, P1 ∨ P2 und P1  P2 - Ist P(t) Formel mit freier Variable t, so auch ∀ t ϵ R(P(t)) und ∃ t ϵ R(P(t))

8 

Sicherheit Einschränkung auf Anfrage mit endlichem Ergebnis Bedingung: Ergebnis des Ausdrucks muss Teilmenge der Domäne der Formel sein - Domäne einer Formel enthält: Alle in Formel vorkommenden Konstanten und alle Attributwerte von Relationen, die in Formel referenziert werden

-

Domänenkalkül  Ausdruck hat Form {[v1, v2,…vn] | P(v1,…vn)} mit v1,…vn Domänenvariablen und P Formel  Beispiel: MatrNr und Namen der Prüflinge von Curie  -

Sicherheit Analog zum Tupelkalkül Ausdruck ist sicher wenn Ergebnis endlich ist UND in endlicher Zeit erreichbar

Relationale Anfragesprache SQL Datendefinition  character (n), char (n)  character varying (n), varchar (n)  numeric (p,s), integer, decimal  clob (sehr große String-Attribute)  date (Datumsangaben), money (Währung)  xml (XML-Dokumente)  Anlegen von Tabellen create table Professoren (PersNr integer not null, Name varchar (30) not null, Rang character (2) ); Veränderungen am Datenbestand  Einfügen von Tupeln insert into hoeren select MatrNr, VorlNr from Studenten, Vorlesungen where Titel = 'Logik; insert into Studenten (MatrNr, Name) values (2811, 'Fichte'); 

Löschen von Tupeln delete Studenten where Semester > 13;



Verändern von Tupeln update Studenten

9 set Semester = Semester+1; Einfache SQL Anfragen 





Duplikateleminierung select distinct Rang from Professoren

Anfragen über mehrere Relationen  Welcher Prof liest Mäeutik? select p.Name, v.Titel from Professoren p, Vorlesungen v where p.PersNr = v.gelesenVon and v.Titel = 'Mäeutik'; Entspricht: 



Übersetzung in relationale Algebra - Allgemeine SQL-Form: select A1,…An from R1,…Rk where P; - In RA: Welche Stundeten kennen sich aus Vorlesungen?

 Hier würde zB sowohl Fichte, Carnap als auch Carnap, Fichte vorkommen  Hier würde jeder auch sich selbst kennen  and h1.MatrNr < h2.MatrNr vermeidet das Mengenoperationen  Mengenoperationen union, intersect, minus/except  (select Name from Assistenten) union (select Name from Professoren); Existenzquantor exists

10 Welche Profs halten keine VL?

Mengenvergleich

 Unkorrelierte Unteranfrage meist effizienter, da nur einmal ausgewertet Vergleich mit all  Kein vollwertiger Allquantor! select s.Name from Studenten s where s.Semester >= all (select a.Semester from Studenten a); Aggregatfunktionen und Gruppierung  Aggregatifunktionen avg, min, max, count, sum 



Besonderheiten: SQL erzeugt pro Gruppe in Ergebnistupel Alle in select aufgeführten Attribute (außer den aggregierten) müssen auch in group-by aufgeführt werden - Nur so kann SQL sicherstellen dass sich Attribut nicht innerhalb der Gruppe ändert

-

Geschachtelte Anfrage  Unteranfrage in where

11  -



Unteranfrage in select Für jede Ergebnistupel wird Unteranfrage ausgeführt Unteranfrage ist korreliert (greift auf Attribute der umschließenden Anfrage zu)

Korreliert vs. unkorreliert

 Vorteil UK: Unteranfrageergebnis kann materialisiert werden und Unteranfrage muss nur einmal ausgewertet werden Verwertung der Ergebnismenge einer Unteranfrage

Modularisierung mit with

Allquantifizierung

12  

SQL hat keinen Allquantor  Muss umgeformt werden Wer hat alle vierstündigen Vorlesungen gehört?



Durch Umformung:



SQL-Umsetzung



Durch count-Aggregation select h.MatrNr from hoeren h, Vorlesungen v where h.VorlNr = v.VorlNr and SWS=4 group by h.MatrNr having count(*) = (select count(*) from Vorlesungen where SWS=4)

Nullwerte  Sobald ein Operand null ist, wird auch Ergebnis null (zB null + 1 = null; null * 0 = null)  SQL kennt nicht nur true und false sondern auch unknown (liefern Vergleichsoperationen zurück, wenn mind. eines ihrer Argumente null ist)  In where- Bedingung werden nur Tupel weitergereicht, für die die Bedingung true ist (Tupel, für die die Bedingung unknown auswertet werden nicht ins Ergebnis aufgenommen)  Bei Gruppierung wird null als eigenständiger Wert aufgefasst und in eigene Gruppe eingeordnet

13 

Logische Ausdrücke:

Case-Konstrukt



Geht von oben nach unten  erste passende when-Klausel wird ausgeführt

Joins  Cross join: Kreuzprodukt

   

Natural join: natürlicher Join Join oder innerer Join: Theta-Join Left, right oder full outer join: äußerer Join Äußerer Join

Rekursion  Welche direkten und indirekten Vorgänger hat Wiener Kreis with recursive TransVorl(Vorg,Nachf) as (select * from voraussetzen union all select t.Vorg, v.Nachfolger

14 from TransVorl t, voraussetzen v where t.Nachf=v.Vorgänger) select Titel from Vorlesungen where VorlNr in (select Vorg from TransVorl where Nachf in (select VorlNr from Vorlesungen where Titel='Wiener Kreis'))  Temporär definierte Sicht TransVorl ist rekursiv, da sie selbst in der Definition vorkommt 

Vor-Vorgänger von Wiener Kreis



Vorgänger des Wiener Kreis der Tiefe n

Connect by

Sichten  Für Datenschutz

15 

Statische Sicht



Vereinfachung von Anfragen



Modellierung von Generalisierung

 Untertypen als Sicht

 Obertypen als Sicht Datenintegrität

16

Integritätsbedingungen Schlüssel Beziehungkardinalitäten Inklusion bei Generalisierung  Statische IB - Bedingungen an Zustand der Datenbasis  Dynamisch IB - Bedingungen an Zustandsübergänge 

-

Referentielle Integrität  Fremdschlüssel: Verweisen auf Tupel in einer Relation (zB gelesenVon in VL verweist auf Tupel in Professoren)  Referentielle Integrität: Fremdschlüssel müssen auf existierenden Tupel verweisen oder Nullwert erhalten  SQL - Kandidatenschlüssel: unique - Primärschlüssel: primary key - Fremdschlüssel: foreign key



Einhaltung referentieller Integrität Änderung von referenzierten Daten 1. Default: Zurückweisen der Änderungsoperation

17 2. Propagieren der Änderungen: cascade

3. Verweise auf Nullwert setzen: set null



Kaskadierendes Löschen

Einfache statische Integritätsbedingungen  Wertebereichseinschränkungen ...check Semester between 1 and 13  Aufzählungstypen ...check Rang in ('C2', 'C3', 'C4')...

Uni-Schema mit Integritätsbedingungen

18

Datenbank-Trigger

19

Besteht aus: - create trigger Anweisung gefolgt von Namen - Definition des Auslösers, hier bevor eine Änderungsoperation (before update on) auf einer Zeile (for each row) der Tabelle Professoren ausgeführt werden kann - Einschränkende Bedingung (when) - Prozedurdefinition in Oracle-proprietären Syntax  old bezieht sich auf noch unveränderte Tupel, new enthält bereits Veränderungen durch Operation Temporale Daten



Normale SQL-Anfragen beziehen sich auf derzeit gültigen Tupel



 Gibt den Wert 0 zurück Um nicht aktuellen Wert zu bekommen:



Über system_time between...and... möglich, auf während bestimmten Zeitperiode gültigen Tupel zuzugreifen

20 

Temporale Daten nach Anwendungszeit



Automatische Erzeugung der Zeitintervalle

 -

Erweiterte SQL Syntax für Anfragen gegen Zeitintervalle Contains Precedes Succeeds Immediately precedes Immediately succeeds Overlaps

Relationale Entwurfstheorie Ziele  Bewertung der Qualität eines Relationenschemas (Redundanz; Einhaltung von Konsistenzbedingungen)  Normalformen als Gütekriterium  Verbesserung eines Relationenschemas (durch Synthesealgorithmus oder Dekomposition) Funktionale Abhängigkeiten  Schema: R = {A, B, C, D}  besteht aus Menge von Attributen  Ausprägung R  α⊆ R , β⊆ R α  β genau dann wenn ∀ r, s ϵ R mit r. α = s. α => r. β = s. β  Beispiel

21

Schlüssel  α ⊆ R ist Super-Schlüssel wenn α → R  β ist voll funktional abhängig von α wenn

 

Notation für volle funktionale Abhängigkeit: α ⊆ R ist Kandidaten-Schlüssel wenn



Beispiel

Kandidaten-Schlüssel von Städte: {Name, BLand} {Name, Vorwahl} Bestimmung funktionaler Abhängigkeiten

Herleitung funktionaler Abhängigkeiten

22

Bestimmung der Hülle einer Attributmenge

Kanonische Überdeckung

Berechnung kanonische Überdeckung

23

Zerlegung (Dekomposition) von Relationen Gibt zwei Korrektheitskriterien für Zerlegung von Relationenschemata:  Verlustlosigkeit: Die in ursprünglichen Relationenausprägung R des Schemas R enthaltenen Infos müssen aus den Ausprägungen R1, …Rn der neuen Relationenschemata R 1, … R n rekonstruierbar sein  Abhängigkeitserhaltung: Die für R geltenden funktionalen Abhängigkeiten müssen auf Schemata R 1… R n übertragbar sein Kriterien für Verlustlosigkeit einer Zerlegung

Beispiel verlustfreie Zerlegung

Abhängigkeitsbewahrung

24

Erste Normalform

Zweite Normalform

Dritte Normalform

25

Synthesealgorithmus  Zerlegung eines Relationenschemas, die folgende drei Kriterien erfüllt  R 1, … , Rn ist verlustlose Zerlegung von R  Zerlegung R 1, … R n ist abhängigkeitserhaltend  Alle R 1, … , R n sind in dritter Normalform



Beispiel:

Boyce-Codd-Normalform (BCNF)  Verschärfung der 3 NF

26

 

Man kann jede Relation verlustlos in BCNF zerlegen Manchmal Abhängigkeitserhaltung nicht erzielbar

Städte ist in 3 NF aber nicht in BCNF

Dekomposition  Man kann jedes Relationenschema in zerlegen, so dass die Zerlegung verlustlos ist und alle in BCNF sind (abhängigkeitserhaltend muss dabei nicht sein)  Algorithmus



Bsp Städte

27 Mehrwertige Abhängigkeiten





{PersNr}   {Sprache} {PersNr}   {ProgSprache} Verlustlose Zerlegung bei MVDs



Interferenzregeln für MVDs

Beispiel

28 

Triviale MVDs: Solche, die von jeder Relationenausprägung erfüllt werden

Vierte Normalform



Dekomposition in 4 NF



Beispiel

Physische Datenorganisation

29

Überblick: Speicherhierarchie

Magnetplattenspeicher  Mehrere gleichförmig rotierende Platten, für jede Plattenoberfläche ein Schreib-/ Lesekopf  Jede Plattenoberfläche eingeteilt in Spuren (formatiert als Sektoren fester Größe [Slots], kleinste Schreib-/ Leseeinheit auf einer Platte)  Adressierung - Zylindernummer, Spurnummer, Sektornummer - Jeder Sektor speichert selbstkorrigierende Fehlercodes; bei nicht behebbaren Fehlern erfolgt automatische Abbildung auf Ersatzsektoren

Lesen von Daten von der Platte  Seek Time: Arm positionieren (5ms)  Latenzzeit: ½ Plattenumdrehung (im Durchschnitte) (3ms)  Transfer von Platte zum Hauptspeicher Random vs. Chained IO  1000 Blöcke a 4KB sind zu lesen  Random I/O - Jedes mal Arm positionieren - Jedes mal Latenzzeit  Chained I/O - Einmal positionieren, dann "von Platte kratzen"  Chained ist ein bis zwei Größenordnungen schneller

30 RAID 0: Striping

Lastbalancierung wenn alle Blöcke mit gleicher Häufigkeit gelesen/geschrieben werden  Doppelte Bandbreite beim sequentiellen Lesen der Datei bestehend aus Blöcken ABCD...  Aber: Datenverlust wir immer wahrscheinlicher, je mehr Platten (Stripingbreite = Anzahl der Platten) 

RAID 1:Spiegelung (mirroring)

Datensicherheit: durch Redundanz aller Daten Doppelter Speicherbedarf Lastbalancierung beim Lesen: zB kann Block A von linken oder rechten Platte gelesen werden  Aber beim Scheiben müssen beide Kopien geschrieben werden - Kann parallel geschehen - Dauert somit nicht doppelt so lange wie das Schreiben nur eines Blocks

  

RAID 0+1: Striping und Spiegelung

  

Immer noch doppelter Speicherbedarf Zusätzlich zu RAID 1 hier höhere Bandbreite beim Lesen der gesamten Datei Beim Schreiben immer noch mehrere Kopien

RAID 2: Striping auf Bit-Ebene  Anstatt ganzer Blöcke: Auf Bit-Ebene

31

   

Zusätzlich au einer Platte noch Fehlererkennungs- und Korrekturcodes gespeichert In Praxis nicht eingesetzt, da Platten sowieso schon Fehlererkennungscodes verwalten Lesen der Datei geht sehr schnell Nachteil: Bei L&S müssen sich Arme immer vollständig parallel bewegen

RAID 3: Striping auf BIT-Ebene, zusätzliche Platte für Paritätsinfo

  

Auf einer Platte wird Parität der anderen Platte gespeichert Ausfall einer Platte ist zu kompensieren Lesen eines Blocks erfordert Zugriff auf alle Platten - Verschwendung von Schreib-/Leseköpfen - Alle marschieren synchron

RAID 4: Striping von Blöcken

  

Bessere Lastbalancierung wie bei RAID 3 Flaschenhals bildet Paritätsplatte Bei jedem Schreiben muss darauf zugegriffen werden

 Bei Änderung von Block A muss alte Zustand von A und der alte Paritätsblock und der neue Block A' geschrieben werden

RAID 5: Striping von Blöcken, Verteilung der Pritätsblöcke

32

  

Bessere Lastbalancierung als bei RAID 4 Paritätsplatte bildet keinen Flaschenhals mehr Guter Ausgleich zwischen Platzbedarf und Leistungsfähigkeit

Systempufferverwaltung

  

Systempuffer ist in Seitenrahmen gleicher Größe aufgeteilt Rahmen kann Seite aufnehmen Überzählige Seiten werden auf Platte ausgelagert



Adressierung von Tupeln auf dem Hintergrundspeicher

33 

Verschiebung von einer Seite auf eine andere

B-Bäume  Balancierte Mehrwege-Suchbäume für den Hintergrundspeicher



B-Baum von Grad k:

34 

Einfügen eines neuen Objekts (Datensatz)

B+-Baum