Kapitel 5 - Codd Vollständige relationale Sprachen
- Allgemeines zur Relationenalgebra
- Unterschiede zum Relationenkalkül
- SQL als relationale Sprache
- Details zu SQL und Implementierungen
- Wie kann intern die Anfrage optimiert werden?
- Was wird bei Ausführung einer Anfrage alles getan?
- Wie können Datenbanken optimiert werden?
Welche zwei Schnittstellen zu Datenbanken gibt es?
Prozedurale Sprachen
- Sie erlauben leichte Abbildung der DML-Befehle auf interne Satzoperationen
des DBMS
-
Verantwortung für die Zugriffspfadauswahl liegt beim
Programmierer
- er bestimmt die Art und Reihenfolge der Zugriffe durch Navigation
- Bei der Übersetzung sind lediglich Namensauflösung und Formatkonversionen
erforderlich
Deskriptive Sprachen
erfordern:
- Überprüfung auf syntaktische Korrektheit durch einen Parser(komplexere
Syntax)
- Überprüfung von Zugriffsberechtigung und Integritätsbedingungen
- Anfrageoptimierung zur Erzeugung einer effizient ausführbaren Folge interner
DBMS-Operationen
Somit ist bei deskriptiven Anfragesystemem im wesentlichen der
Anfrageübersetzer und Optimierer des DBMS für eine effiziente Abarbeitung
verantwortlich und nicht der Programmierer, wie bei prozeduraler Anfrage.
Hohe Komplexität der Übersetzung, da die Auswahlmächtigkeit
- an der Prädikatenlogik erster Stufe orientiert ist
- durch zusätzliche Prädikate wie EXISTS, MATCHES, NULL, LIKE u. a. wird diese
sogar deutlich übertroffen
- nicht auf einen Satztyp beschränkt ist
- unabhängige oder korrelierte Teilanfragen zur Bestimmung von Suchargumenten
in beliebiger Schachtelungstiefe zuläßt
- zusätzlich den Einsatz von Built-in- und Sortier-Funktionen auf Partitionen
der Satzmenge gestattet
Beispiel für prozeduralen Anfragen
Ein typische Beispiel für prozedurale Anfragen beschreibt das Netzwerkmodell:
- FIND ANY PERS bezieht sich auf die (vorausgesetzte) Klausel LOCATION MODE IS
CALC des Satztyps PERS
- FIND NEXT PERS WITHIN BESCHÄFTIGT SET bezieht sich auf eine relative Position
(Currency) in einer Setstruktur
- FIND OWNER WITHIN BESCHÄFTIGT SET stellt den OWNERSatz der ‘current’
Set-Ausprägung zur Verfügung.
Erklären sie das Prinzip der Relationenalgebra!
Es wird unterschieden zwischen prozeduraler Algebra und deskriptiven
Kalkülen.
Ein Ausdruck einer prozeduralen Sprache gibt indirekt immer mit an, wie d.h. durch
Ausführung welcher Operationen das Ergebnis berechnet werden kann.
Mengenorientiert
Aus einer oder mehreren Tupelmengen werden neue erzeugt. Anfragen werden in Form
formaler Ausdrücke (der Relationenalgebra bzw. des Relationenkalküls)
übermittelt.
Relationenalgebra ist niedrig polynomiell.
Optimieren kann man die Relationenalgebra indem man die Anfragebäume optimiert.
Selektion und Projektion werden in Richtung Blätter verschoben, um schon anfangs
kleine Zwischenergebnisse zu erhalten.
Relationenalgebra ist stets in Maßstab für die Ausdrucksstärke einer Sprache. Falls
eine Sprache so Ausdrucksstark ( d.h. es gibt zu jedem Ausdruck in der einen
Sprache einen äquivalenten in der anderen) wie die Relationenalgebra ist, so ist
diese Codd-Vollständig. SQL ist bspw. nicht-prozedural, d.h. der Fragesteller
stellt eine Frage, gibt aber keinen Algorithmus zur Lösung vor. Dieser ist in der
Sprache selbst enthalten.
Erklären sie das Prinzip der Relationenkalküle!
Geben im Gegensatz zu prozeduralen Sprachen keine Berechnungsprozedur mit auf
dem Weg, sondern nur eine Beschreibung der betroffenen Tupel der
Ergebnisrelation.
Sie sind unter bestimmten Umständen Codd-Vollständig!
Wozo SQL - Structured Query Language?
SQL ist eine nicht-prozedurale, mengenorientierte Sprache für Relationale
Datenbanksysteme. SQL kann Relationen als Einheiten verarbeiten, verfügt aber z.Z.
noch nicht über Steuerstrukturen wie Schleifen oder Case-Anweisungen. SQL kann
interaktiv eingesetzt werden oder in einer Programmiersprache eingebettet sein.
(embedded SQL)
SQL-Anweisungen teilen sich in zwei Sprachen:
Datendefinitionsprache, zum Vereinbaren von Datenstrukturen, wie
Relationen, Zugriffspfade etc..
Datenmanipulationssprache, zum Verarbeiten der Daten durch
Einfügen, Löschen oder Updates.
Wichtige SQL-Anweisungen
Select-Anweisung
SELECT * FROM relation [WHERE Bedingung];
Bedinung ist durch Vergleichsoperatoren und den Anweisungen BETWEEN, IN, ANY und ALL
definierbar.
Join
SELECT name.attribut {,...}
FROM relation [Korrelation], relation [Korrelation]
WHERE bedingung
Durch die Korrelation ist es möglich Joins mit ein und der selben Tabelle durchzuführen.
Korrelation heißt nix anderes als zwei Variablen einzuführen, um die Tabellen unterscheiden zu
können. Um doppelte Tabellenzeilen zu Vermeiden verwende man SELECT DISTINCT!
Gruppenverarbeitung
Um Tupel herauszufiltern, welche auf gemeinsamen Eigenschaften basieren, bietet SQL
einige Möglichkeiten:
SELECT attribut, {...} FROM relation GROUP BY gruppenattribut {,...}
[HAVING bedingung]
Gruppenauswertungsfunktionen:
AVG(A), COUNG(A),COUNT(*),MAX(A),MIN(A),SUM(A)
Sortieren
ORDER BY [ASC|DESC]
Wie stellt man den Join in SQL dar?
Seien R(A1,.....,An) und S(B1,....,Bm) Relationen.
In Relationenalgebra:
R[Ai=Bj]S
In SQL:
SELECT A1,.....,An,B1,....,Bm FROM R, S WHERE Ai=Bj
Wie kann man den Natural Join in SQL und in Relationenalgebra darstellen?
Seien S(s1,..,sn,a1,..,am) und R(r1,..,rk,a1..am) Relationen mit gleichen
Attributennamen a1..am die sowohl in S als auch in R vorkommen. SQL:
Select S.s1,...,S.sn,S.a1..S.am,R.r1,..,R.rk
Where S.a1=R.a1,..,A.am=R.am
Relationenalgebra:
R NATJOIN S:=(RxS)[S.a1=R.a1,..,A.am=R.am]
[S.s1,...,S.sn,S.a1..S.am,R.r1,..,R.rk]
Wie stellt man einen Join zwischen einer Relation mit sich selbst dar?
Diese Auto-Join genannte Operation gelingt mit Hilfe der Verwendung von
Tupelvariablen: Relationenkalkül:
RANGE ANGEST X
RANGE ANGEST Y
{Y.Name| (X.Gehalt > Y.Gehalt) (X.Name = Y.Vorgesetzter)}
Relationenalgebra:
Y[Y.Gehalt > X.Gehalt][X.Name = Y.Vorgesetzter]X [Y.Name]
SQL:
SELECT Y.Name FROM Angest X, Angest Y WHERE X.Name
= Y.Vorgesetzter AND Y.Gehalt > X.Gehalt
Wozu benötigt man Tupelvariablen?
Tupelvariablen sind immer dann nötig , wenn der Verbund einer Relation mit
sich selbst gebildet werden soll oder dann, wenn bei einem Join von zwei
verschiedenen Tabellen Attribute mit gleichen Namen auftreten.
Anders ausgedrückt: Immer dann wenn innerhalb einer Abfrage verschiedene Tupel
derselben Relation betrachtet werden, braucht man Tupelvariable.
Wohin wird SQL übersetzt?
SQL wird direkt vom Datenmanager interpretiert.
Was geschieht bei einer SQL-Query an ein DBMS?
- Prüfung der Syntax und Zugriffsrechte
- Wahl einer geeigneten Methode zur Ausführung der Operation
- Feststellen, wie die Operanden gespeichert sind und wie effektiv auf diese
Datenstrukturen zugegriffen werden kann (Zugriffspfade)
- Generieren von Ausführbaren Code, welcher
- die beteiligten Daten aus der DB in den Datenbank-Puffer transferiert
- die oben gewählte Methode integriert
- das Ergebnis ausgibt
- Ausführen des Erstellten Codes
Um nun mehreren Benutzern ein gleichzeitiges Arbeiten zu garantieren, sind
alle Schritte bis 5 reentrant. D.h. sie können parallel ablaufen. Jeder Auftrag
bekommt einen Platz im Buffer und wird abgearbeitet, wenn es an der Reihe ist. Hier
kann es zur Synchronisationsproblemen kommen. Man kann den Buffer als Cache sehen.
Schreibt der Prozess geänderte Daten in die DB zurück, muss womöglich ein Update
eines anderen Pufferbereiches ausgeführt werden, da dieser sonst noch das falsche
Datum trägt. Dies wird meist, wie aus Rechnerarchitektur bekannt, über
Dirty-Bits in den einzelnen Seiten des Buffers geregelt. Wird eine
Seite benötigt, wird das Dirty-Bit interpretiert und gegebenenfalls die Seite neu
von der Platte in den Puffer geladen.
Wie erfolgt die Optimierung von Abfragen? Was ist bei Projektionen zu beachten?
- Selektionen möglichst früh ausführen, um die Ergebnismenge klein zu halten
- Zusammenfassung von Selektionen zu komplexen Selektionen, da dies die Zahl
der Zugriffe auf die Daten minimal hält.
- Bei Projektionen zuerst diejenigen Attribute nehmen, die keine Eliminierung
von Duplikaten erfordern
dann möglichst früh (also wenn mindestens ein Schlüssel des Relationenschemas
erhalten bleibt), sonst möglichst spät.
- Suche nach gemeinsamen Teilbäumen im Operatorbaum und Vereinigung dieser
Bäume (Blätter: Relationen, innere Knoten Operationen, Selektion, Join,
Projektion)
- Joins möglichst spät
- Optimierung auf physischer Ebene: Ausnutzung von Sekundärindizes
(Invertierung), Sortierung, Speicherstruktur der Datenbanktabellen
Wie wird ein Join ausgeführt?
Beispiel: R(A,D), S(B,C); Gesucht R[A=B]S
- einfach und ineffizient: für jedes Tupel in R mit A=a wird S durchsucht nach
B=a
- mit Sekundärindex: Index weist jedem a die Tupelmenge in S mit B=a zu
- mit Sortierung: R und S werden sortiert (bezgl. A bzw. B), dann werden R und
S parallel durchlaufen.
Was macht die Anfrage-Optimierung?
Durch algebraische Optimierung, kann vor Ausführung des Codes schon optimiert
werden, in dem Umformungen auf Basis der Relationenalgebra vorgenommen werden.
Join-Operationen sind in der Regel sehr teuer. Dagegen sind Selektion und
Projektion relativ billige Operationen.
Man unterscheidet das naive Vorgehen (einfach laut Klammerung auflösen) und
das optimierte Vorgehen, indem die Anfrage so umformuliert wird, dass wenig
aufwendige Operationen bevorzugt werden, um teuere Operationen mit kleinen
Relationen ausführen zu können.
Anfrage > Parsen > Validierung > View-Resolution
> Optimierung > QEP > Code > Ausführung > Ausgabe
High Level Optimierung: Auf Grund von Rechenregeln wird die Anfrage optimiert. Ist
somit unabhängig vom DBMS.
- Ausnutzen von Kommutativität von Selektion, Projektion und natural Join.
- Ausnutzen von Distributivität der Selektion bzgl. Des Verbundes
- Ausnutzen von Distributivität der Projektion bzgl. Des Verbundes
- Assoziativität des Verbundes, Vereinigung und Durchschnitt...
Folgende Optimierungskriterien sind zu beachten:
- optimierte Anfrage muss äquivalent zu Originalanfrage sein
- statische Daten, wie die Anzahl von Tupeln pro Relation einbeziehen
- eventuelle Sortierung der Tupel innerhalb einer Relation beachten
- eventuell existierende Zugriffspfade, wie Sekundärindexe o.ä. nutzen
Low Level Optimierung: QEP Erstellung und Optimierung der
Datenorganisation und Implementierung.
- Suche einer suboptimalen QEP mit Hilfe von Heuristiken oder Greedy Verfahren
- Vollständige Strategien zu aufwendig
- Falls Unterschiedliche QEPs für eine Anfrage möglich wird eine Kostenfunktion
einbezogen (z.B. Anzahl notwendiger Plattenzugriffe)
- Verbundimplementierung
Wie werden Anfragen dargestellt und intern weitergegeben?
Anfragen werden in Form von Operatorbäumen dargestellt. Er zeigt die zu
bearbeitenden Relationen, die auszuführenden Operationen und die Präzedenzen
(Aufrufreihenfolge) zwischen den Operatoren an.
Was ist der Nested-Loop-Join?
sucht nach gleichen Werten der gemeinsamen Attribute in den zu verbindenden
Relationen. Dabei muss für jedes Tupel der Relation A jedes Tupel der Relation B
verglichen werden. Optimiert wird hier durch blockweißes Lesen der Daten. Somit
entsteht quadratischer Aufwand.
Wie arbeitet Sort-Merge-Join?
Sortiert erst die Operanden anhand der Verbund-Attribute aufsteigend und
mischt anschliessend die gleichwertigen Attribute zur Ergebnisrelation.
Falls die Operanden-Relation schon sortiert ist, weil z.B. für Attribut A ein Index
existiert, ist das Verfahren dem Nested-Loop Join in jedem Fall vorzuziehen, da
dann der Aufwand nur noch linear ist...
Wie arbeitet der Hash-Join?
Ist eine Einteilung der Relationen in Partitionen über eine Hashfunktion.
Danach kann jede Partition einzeln betrachtet werden.
Was muß man bei der Ausführung von SQL-Anfragen tun?
- Optimierung der Anfrage
- Transformation in konzeptuelles und internes Schema
- Beschaffen der benötigten Sätze und Transformation in externes Schema;
Realisierung durch Datenmanager (Mengenschnittstelle)
Zugriffsmanager (Ein-Tupel-Schnittstelle)
Systempuffer(Cache)Manager (Seitenschnittstelle)
Wie kann man Datenbanken Tunen?
Es gibt vier grundlegende Prinzipien.
- Lokale Optimierung zur Erreichung globaler Effekte (Hardwareausnutzung
überwachen)
- Partitionierung zur Vermeidung von Bottlenecks ( Transaktionen in Lange und
Kurze)
- Intitiale Kosten > Laufende kosten (Leseoperationen sind beim Starten
teurer - dann billig)
- Angemessene Aufgabenverteilung zwischen Systemkomponenten
Systemkomponenten
- Concurrency Controll
- Recovery- und Logging-System
- Umgebendes OS (Puffer, Disk-Scheduling etc.)
- Zugrunde liegende Hardware (RAM, Anzahl Prozessoren)
Tuning kann auch durch Denormalisierung vorgenommen werden, wenn z.B. extrem
viele Verbund-Operationen auf die normalisierte Relation angewendet werden müssen.
|
|
Normalformen