Projektion - Bei der Projektion werden alle Spalten außer den angegebenen ausgeblendet. Als Funktionszeichen wird das große Pi verwendet.
Selektion - Die Selektion wählt jene Datensätze aus, die der Selektionsbedingung entsprechen.
Das SQL-Statement SELECT entspricht der Kombination aus Projektion und Selektion. Z.B.:
SELECT Projektionsspalten FROM Relation WHERE Projektionsbedingung
Schnittmenge und Vereinigung
Differenzmenge
Kreuzprodukt

Conditional Join - Es wird ein Kreuzprodukt der Datensätze zweier Relationen gebildet, das jene Datensätze enthält, auf die die join condition zutrifft.
Equi-Join - Ist ein Conditional Join, dessen Bedingung stets die Äquivalenz zwischen zwei Werten ist. Es werden also jede Kombinationen ausgewählt, deren Attributwerte in den angegebenen Feldern gleich sind.
Natural Join - Ist ein Equi-Join über alle gleichbenannten Attribute der beiden Relationen.
OUTER JOIN

Relationsalgebraische Optimierung

High Level Optimierung

Selektionen und Projektionen sollten möglichst weit unten im Baum stehen

Die Selektionen mit den restriktivsten Bedingungen sollten noch weiter unten und auf gleicher Ebene links stehen (da die Bäume i.d.R. von links nach rechts ausgewertet werden).
Die Laufzeit einer Operation im Einzelnen hängt von der Anzahl der Datensätze in der Relation ab, auf der sie ausgeführt wird. Außerdem können gleiche Operation unterschiedlich implementiert sein, es stehen oft sogar unterschiedliche Implementationen zur Verfügung, von denen die günstigste zu wählen ist.

Sonstige Optimierungen:

Low-Level-Optimierungen

Simple Nested Loops Join, page-at-a-time: Bei einem Join sind A und B zu vergleichen. A kann jedesmal so gewählt werden, dass B möglichst in der gleichen Speicherseite liegt. Reduziert Festplattenzugriffe.
Block Nested Loops Join: Join-Relation A als Hashtable über Hashkey des Joinattributes im Hauptspeicher ablegen.
Sort Merge Join: Relationen A und B erstmal sortieren (gemäß Joinkey). Dann vermischen.
Hash Join: Partitionierung von A und B mit gemeinsamer Hashfunktion.

ANSI/SPARC Schemata
Die drei Abstraktionsebenen des ANSI/SPARC - Schichtenmodells. Physische und logische Datenunabhängigkeit.
Physische und logische Datenstruktur sind - weil Bestandteil unterschiedlicher Abstraktionsebenen - voneinander unabhängig.

Konzeptionelles Schema - Tabellenstruktur, Primärschlüsselfestlegung
Internes Schema - physikalische Datenorganisation v.a. auf dem Datenträger
Externes Schema - Angepasste Benutzersichten auf die Tabellen (View, Report) ermöglichen Komplexitätsreduktion (information hiding)
Oft ergeben sich Effizienzprobleme damit, den View per Laufzeit zu berechnen, da er bei jeder Änderung der Datensätze, von denen er Ausschnitte zeigt, angepasst werden muss.

Praktisch entspricht das konzeptuelle Schema der CREATE TABLE - Anweisung, mit der eine Relation erstellt wurde (wobei natürlich auch ggf. nachfolgende ALTER TABLE - Anweisungen zu beachten sind). Das externe Schema wird in SQL durch CREATE VIEW beschrieben. Jedoch unterstützen viele Datenbanksysteme keine Views.

Integritätsbedingungen
Integritätsbedingungen müssen zu jedem Zeitpunkt auf den Zustand der Datenbank zutreffen. Sie heißen auch integrity constraints oder domain constraints. Die Integritätsbedingungen werden unabhängig von der die Datenbank anwendenden Applikation betrachtet. Die Bedingungen sind Teil der Definition des konzeptuellen Schemas.
Bei der Modifikation von Tabellen müssen die Integritätsbedingungen geprüft werden. Operationen, die Zustände herbeiführen, die nicht den Integritätsbedingungen entsprechen, sollten durch das Datenbanksystem verhindert werden (faithful representation).

Kein Datensatz darf mit einem anderen der gleichen Tabelle in allen Attributwerten übereinstimmen (unique row rule).
jeder Attributwert muss eindeutig bestimmt sein (heißt auch 1. Normalform)
Schlüsselbedingung: Ein Datensatz kann durch einen Schlüssel eindeutig identifiziert werden. Der Schlüssel kann sich aus den Werten einer Menge von Attributen eines Datensatzes zusammensetzen. Dann gilt: Es darf nur einen einzigen Datensatz geben, der diesen Schlüsselwert enthält. Durch die Angabe solcher Schlüssel-Bedingungen im konzeptionellen Schema lassen sich bestimmte Kombinationen ausschließen. z.B.
CREATE TABLE Autos (Herstellername CHAR(20), Modellname CHAR(20), Ps INTEGER NOT NULL, Kennzeichen CHAR(6), PRIMARY KEY (Herstellername, Modellname), UNIQUE (Kennzeichen))
Hierbei wird festgelegt, dass der Datensatz eindeutig über die Kombination aus Modell- und Herstellername identifiziert wird. Deshalb dürfen keine zwei Fahrzeuge gleichen Hersteller- und Modellnamen tragen (wegen der Schlüsselbedingung). Jedoch können unterschiedliche Hersteller ihren Autos gleiche Modellbezeichnungen geben.
Für weitere Attributwerte kann angegeben werden, dass Sie in der Relation nur in einem Datensatz vorkommen dürfen. Dafür ist das Attribut mit UNIQUE zu bezeichnen. Solche Attribute (es können auch Attributmengen sein) nennt man dann Schlüsselkandidaten, da sie ebenfalls zur eindeutigen Identifikation des Datensatz verwandt werden könnten. Aus technischer Sicht genügt jedoch der angegebene Primärschlüssel.
Auch die Festlegung, ob ein Attributwert NULL - also nicht definiert - sein darf, ist eine im konzeptionellen Schema zu treffende Integritätsbedingung.
In SQL können mit der CHECK-Klausel weitere Integritätsbedingungen festgelegt werden:
CREATE TABLE Leute (Name CHAR(20), Age INTEGER CHECK(AGE >= 0), PRIMARY KEY(Name))
Zur Vermeidung von Anomalien (unter "Normalformen" beschrieben), sollten Fremdschlüssel in der Relation mit FOREIGN KEY ... REFERENCES ... als solche gekennzeichnet werden:
CREATE TABLE Leute (Name CHAR(20), Age INTEGER, Adresse CHAR(20), PRIMARY KEY(Name), FOREIGN KEY (Adresse) REFERENCES TabelleAdresse (AdressenId))
Zusätzlich gibt es die Möglichkeit des kaskadierenden Löschens.
CREATE TABLE Leute (Name CHAR(20), Age INTEGER, Adresse CHAR(20), PRIMARY KEY(Name), FOREIGN KEY (Adresse) REFERENCES TabelleAdresse (AdressenId) ON DELETE CASCADE)
Diese Definition zieht mit sich, dass das Löschen eines Datensatz aus TabelleAdresse, auf den von einem Leute-Datensatz verwiesen wird, den Leute-Datensatz ebenfalls löscht.
Es können auch Trigger vereinbahrt werden, Eventhandler, die vor oder nach einer Operation selbst Anweisungen ausführen oder die geplante Aktion auf Zulässigkeit hinsichtlich der Integrität überprüfen:
ON event IF condition THEN action

(Anm: CHECK und REFERENCES funktionieren unter mySql anders)

Serialisierbarkeit

Nutzen
Transaktionen bestehen aus Operationen (Lesen eines Attributwertes und Schreibes eines Attributwertes). Die Transaktionen mehrerer Benutzer sollen quasi gleichzeitig ausgeführt werden. Deshalb muss ein Scheduling mit den Operationen, aus denen die Transaktionen bestehen, vorgenommen werden. Dabei werden die Operationen verschiedener Transaktionen miteinander vermischt. Da alle Transaktionen auf dem gleichen Datenbereich arbeiten können, ist sicherzustellen, dass sich die Transaktionen nicht gegenseitig beeinflussen. So könnte es zu inkonsistenten Datenbankzuständen kommen, die zu vermeiden sind. Deshalb haben Transaktionen die ACID-Eigenschaften (Atomarität, Konsistenz, Isolation, Dauerhauftigkeit).
- atomicity - Jede Transaktion wird komplett ausgeführt oder gar nicht (abort).
- consistency - Nach der Transaktion besteht immer noch ein konsistenter Datenbankzustand.
- isolation - Gleichzeitig ausgeführte Transaktionen beeinflussen sich nicht gegenseitig.
- durability - Ist die Transaktion erfolgreich abgeschlossen (commit), werden nachfolgende Fehler sie nicht mehr beeinflussen.
Einige Probleme können durch das Scheduling auftreten, wenn die Transaktionen nicht die ACID-Eigenschaft besitzen:
- lost update - für zwei Transaktionen A und B: Die Folge A_read(X), B_read(X), A_write(X), B_write(X) lässt die Änderung, die A an X vorgenommen haben könnte, verschwinden / überschreibt sie. (fehlende Isolation)
- inconsitent read - tritt auf bei B_read(X), B_write(X), A_read(X), A_read(Y), B_read(Y), B_write(Y), A_write(X,Y). In Worten: Transaktion B hatte den Auftrag, die Werte X und Y zu aktualisieren. Mittendrin hat Transaktion A eine Berechnung durchgeführt mit dem aktualisierten Wert X und dem noch nicht aktualisierten Wert Y. Das Ergebnis von A ist also wahrscheinlich falsch - ein inkonsistenter Datenbankzustand die Folge. (fehlende Isolation, Consistency)
- dirty read - Aufgrund von A_read(X), A_write(X), B_read(X), A_abort, B_write(X) bekommt X einen ungültigen Wert, denn der Abbruch von A hat sich nicht in der Transaktion B niedergeschlagen. (fehlende Durability)
Der Ablauf der Transaktionsverwaltung ist der folgende: Der Transaktionsmanager gibt die aus read, write, commit und abort bestehenden Operationen an den Scheduler weiter. Der Scheduler soll die Operationen möglichst fair mischen, aber so, dass die Isolation (ACID) zwischen den Transaktion weiterhin besteht. Den fertigen Schedule leitet er an den DataManager weiter, der die Operationen auf der Datenbank ausführt.
Um die Zulässigkeit eines Schedules festzustellen, wird er mit dem seriellen Schedule verglichen. Der serielle Schedule ist einfach die Aneinanderreihen der einzelnen Transaktionen ohne Vermischung. Liefert ein Schedule das gleiche Ergebnis, wie der serielle Scheduler, heißt er serialisierbar. Die Aufgabe des Schedulers ist somit die Concurrency Control.
Ein Schedule ist eine Temporalordnung aus Operationen der Menge read(Wert), write(Wert), abort und commit.

Um die Serialisierbarkeit festzustellen, gibt es verschiedene Methoden.
Reads-From Relation
Life Reads-From
Serialisierbarkeitsäquivalenz
View-Serialisierbarkeit ist nicht effizient zu berechnen.
Konflikt-Serialisierbarkeit
Konfliktgraphen
Herbrand Semantics: Für einen Schedule S aus der Transaktion T(n) mit den Operationen read(Wert), write(Wert) sind die Herbrand Semantics wie folgt definiert:
H(S, T1.read(X)) = H(S, Ti.write(X)) , wobei Ti.write(X) das letzt write vor read(X) ist.
H(S,T1.write(X)) = f ( H(S,T1.read(Y), H(S,T2.read(Y), ... , H(S,Tn.read(Y) ) , wobei f(Herbrand Semantics) eine beliebige nichtdefinierte Interpretation aller vor dem Schreibvorgang gelesener Werte ist. Ein Schreibvorgang kann also von allen möglichen vorher gelesenen Werten abhängen, die auch beliebig interpretiert werden können.
H(S, X) = H(S, Ti.write(X)) , wobei Ti.write(X) die letzte Schreiboperation auf allen Attributfeldern X war.
final state equivalence - Endzustandsserialisierbarkeit FSR: Ein Schedule ist seriell, wenn er endzustandsäquivalent zum seriellen Schedule ist. Ein Schedule ist endzustandsäquivalent zu einem anderen, wenn beide die gleiche Herbrand-Semantik haben und die gleiche Menge an Operation enthalten (ggf. aber in unterschiedlicher Reihenfolge).
Ein Schedule ist außerdem auch dann Element von FSR, wenn er die gleiche Operationsmenge wie der serielle Schedule enthält und die gleiche LRF-Relationsmenge erzeugt.

Normalformen
Es empfiehlt sich, Datenbanken in der 3. Normalform zu halten. Die Normalformen helfen, Redundanzen zu vermeiden und Anomalien zu vermeiden.
Update Anormalie: Wird ein Datensatz modifiziert, müssen aufgrund redundanter Speicherung andere Datensätze ebenfalls modifiziert werden, um Inkonsistenz (widersprüchliche mehrfach gespeicherte Information) zu vermeiden.
Insertion Anormalie: Es ist nicht möglich, einen Datensatz hinzuzüfgen, wenn nicht andere in Relation stehende Datensätze gleichzeitig mit eingefügt werden.
Deletion Anormalie: Das Löschen eines Datensatzes erstreckt sich auf Informationen, die nicht dazu gehören und nicht gelöscht werden sollten. Oder: Zur Gewährleistung der Konsistenz müssten andere Datensätze ebenfalls gelöscht werden.
Funktionale Abhängigkeiten (FD): Eine funktionale Abhängigkeit besteht, wenn für alle Datensätze einer Relation gilt: Wenn das Attribut X in Datensätzen den gleichen Wert hat, dann hat auch das Attribut Y den gleichen Wert. Dann besteht eine funktionale Abhängigkeit zwischen X und Y, oder: FD(X,Y). Insbesondere gibt es immer die FD vom Primärschlüssel auf die übrigen Werte der Relation. Denn ein gleicher Primärschlüssel zieht gleiche Attributswerte nach sich, denn dann handelt es sich auch um den gleichen Datensatz. Die FD vom Primärschlüssel auf die übrigen Attribute des Datensatzes ist die triviale funktionale Abhängigkeit. FD ist eine transitive Relation.

Zur Vermeidung der oben beschriebenen Anomalien gibt es die Normalformen. Befindet sich eine Datenbank in einer Normalform, dann befinden sich auch all ihre Relationen in der Normalform und umgekehrt. Das Einhalten einer bestimmten Normalform garantiert, dass bestimmte Anomalien nicht auftreten.
- 1. Normalform ist durch relationale Datenbank immer erfüllt (Primärschlüssel und grundlegende Integritätsbedingungen).
- 2. Normalform: Jedes Schlüsselattribut (auch: NSA) ist funktional abhängig vom Primärschlüssel.
- 3. Normalform: Es gibt ausschließlich funktionale Abhängigkeiten zwischen Primärschlüssel oder seinen Schlüsselbestandteilen auf Nichtschlüsselattribute. (Es gibt nur die triviale FD).
- Boyce-Codd Normalform (BCNF) ist eine Untermenge zu Relationen der 3. NF.
- Außerdem gibt es noch die 4. und 5. NF, die in der Praxis aber kaum angewandt werden.
physikalische Grundlagen der Datenspeicherung und CLOCK-Seitenersetzung
Next-Block-Concept : Zur Minimierung der Zugriffszeit sollten die Datensätze in einem zusammenhängenden File gespeichert werden, wobei benachbarte Datensätze auf benachbarten Sektoren unterzubringen sind.

Pufferverwaltung spielt eine Rolle zur Beschleunigung der Festplattenzugriffe:

Es wird eine Zuordnungstabelle aus Speicherseite und Festplattensektor gehalten. Bei Leseanforderungen auf einen Festplattensektor, der noch nicht im Puffer ist, muss über einen Replacement-Algorithmus entschieden werden, welche Seite im Puffer zu ersetzen ist.
Die üblichen Algorithmen sind MRU, Clock und LRU. MRU und LRU nicht komplex zu implementieren. Für den Clock-Seitenersetzungsalgorithmus werden die Varialben pin_count und references für jeden Zuordnungstabelleneintrag gehalten:
references zählt die Referenzen aus der Datenbank auf eine Speicherseite. Die Anforderung an eine Speicherseite erhöht den Referenzzähler um 1, die Freigabe der Seite dekrementiert ihn um 1.
Die Liste der Zuordnungseinträge wird zyklisch abgearbeitet, wobei nach nichtreferenzierten Seiten mit references=0 gesucht wird.
pin_count ist initial 0. Wurde eine Seite mit references=0 gefunden, wird pin_count=1 gesetzt.
Eine Seite mit pin_count=1 und references=0 wird ersetzt!
So sichert pin_count, das eine Speicherseite vor ihrer Ersetzung eine "Extrarunde" drehen darf. Falls dann doch noch ein Zugriff auf die Seite erfolgt, ist sie ja noch im Hauptspeicher, und eine andere Seite wird ausgelagert werden.
Bei Erhöhung von references muss pin_count=0 sein

Bereichsanfragen sind Anfragen, bei denen mehrere Datensätze durch eine Selektion zurückgeliefert werden sollen.

Jeder Datensatz einer Relation hat die gleiche Länge, die durch die Tabellendefinition bekannt ist. Daher können alle Datensätze innerhalb einer sequentiellen Datei adressiert werden. Es gibt jedoch unterschiedliche Formen der Dateiorganisation:

Heapfiles sind ungeordnet. Sie wachsen durch zusätzliche Alloziierung von Speicherseiten. Heapfiles können entweder als verkettete Liste oder per Verzeichnis verwaltet werden. Verwaltungsinformationen sind die Zuordnung einer Speicherseite zu einem Datensatz und Fragmentierungsinformationen (durch Dealloziierung erzeugte Speicherlöcher geben Auskunft über freien nutzbaren Speicherplatz). Wird als verkettete Liste gespeichert, dann sind die Speicherseiten die Listenelement, die außer Datensätzen auch Verweise auf das folgende und vorhergehende Listenelement enthalten. Es gibt dann zusätzlich eine Liste freier Speicherseiten. Das Speicherung mit einem Verzeichnis benötigt weniger Speicherplatz als die verkettete Liste (weil jeweils ein Zeiger pro Seite genügt).

Effizienz von Heapfiles
Operation	Methode	Aufwand
Scan	Es muss auf jede einzelne Seite zugegriffen werden. Das geht sequentiell (über die Liste oder das Verzeichnis).	B(D+RC)
Gleichheitssuche	Bei der Suche nach einem UNIQUE - Attribut (insb. Primärschlüssel) muss durchschnittlich die Hälfte aller Datensätze durchsucht werden. Kann das Attribut mehrfach vorkommen, müssen alle Datensätze durchsucht werden.	0.5 * Scan
Bereichsanfrage	Alle Datensätze müssen gelesen werden.	Scan
Einfügen	Der neue Datensatz wird einfach am Ende der Datei gespeichert. Es muss nur auf den letzten Datensatz zugeriffen werden, um den neuen dort anzuhängen.	2D+C
Löschen	Falls die Position des Datensatzes bekannt ist, kann er direkt gelöscht werden. (Aus Verzeichnis entfernen, bzw. Listenzeiger ändern wird vernachlässigt). Muss die Position erst gesucht werden, muss Gleichheitssuche vorher durchgeführt werden.	Einfügen

Hashfiles organisieren die Datensätze, indem eine Hashfunktion aus dem Primärschlüssel die Adresse der Speicherseite zurückliefert, in der der Datensatz mit dem Primärschlüssel gespeichert ist. Da man aber nicht zwangsläufig davon ausgehen kann, dass es genauso viele oder mehr Speicherseiten wie Datensätze gibt, kann man auch nicht davon ausgehen, dass die Hashfunktion injektiv ist, also jedem Datensatz eine unterschiedliche Speicheradresse zuordnet. Deshalb kann es vorkommen, dass mehrere Datensätze in der gleiche Speicherseite abgelegt sind ("Kollision"). Um dann trotzdem die richtige Adresse für den gesuchten Datensatz zu bestimmen, wird der Inhalt der Speicherseite in primary bucket und overflow bucket unterteilt. Im primary bucket befindet sich genau ein Datensatz. Das overflow bucket ist i.d.R. eine verkettete Liste mit (möglichst wenigen) weiteren Datensätzen, die eben in der gleichen Speicherseite (gleicher Hashwert) abgelegt wurden. Gibt es nur wenige Hashwerte, die durch unterschiedliche Primärschlüssel zurückgeliefert werden, entstehen sehr lange Überlauflisten (overflow buckets). Dann ist das Verfahren ineffizient.

Effizienz von Hashfiles
Operation	Methode	Operationsperformance
Scan	Dateidurchlaufen, Hashfunktion	1.25*B(D+RC)
Gleichheitssuche	Effizient, falls Suche nach Hashattribut	H+D+(RC/2)
Bereichsanfrage	Alle Datensätze müssen gelesen werden. Hashfunktion entsprechend oft.	Scan
Einfügen	Nur Schreiben und Hashfunktion	H+2D+C
Löschen	Nur Suchen und Löschen	Suche + C + D

Sorted, die Datensätze werden in einer Binärbaumstruktur verwaltet, in der sie der Ordnung nach einem bestimmten Sortierungsattribut unterliegen. Benachbarte Seite lassen sich schnell erreichen. Suche nach Datensatz über das Sortierungsattribut benötigt log2(#Datensätze) Schritte (binärbaumtypisch).

Effizienz von sorted Files
Operation	Methode	Aufwand
Scan	Es muss auf jede einzelne Seite zugegriffen werden. Das geht sequentiell (über die Baumstruktur).	B(D+RC)
Gleichheitssuche	Falls das Suchkriterium Sortierattribut war, kann über den binäre Baum gesucht werden. Dann werden auch alle anderen Datensätze, die das Suchkriterium erfüllen, mitgefunden, da sie sich in direkter Nachbarschaft im Suchbaum befinden. Falls nicht nach dem Sortierkriterium gesucht werden soll, muss jeder Datensatz durchsucht werden (Scan).	D * log2(B) + C*log2(R)
Bereichsanfrage	wie Gleichheitssuche	Gleichheitssuche
Einfügen	Nachdem die Einfügeposition gefunden wurde, muss die Baumhälfte rechts davon um einen Datensatz nach rechts verschoben werden.	Suche + B(D+RC)
Löschen	Das zu löschende Tupel muss lokalisiert werden, und dann wird die Baumhälfte rechts davon um einen Schritt nach links verschoben. Falls mehrere Tupel gelöscht werden sollen (Löschen per Bereichsanfrage, also nicht über einen Primärschlüssel), muss der gesamte Vorgang für jeden gefundenen Tupel wiederholt werden.	Einfügen

Spezialisierungen von sorted files sind Indexstrukturen wie B(+) Baumstrukturen und ISAM.

Effizienzvergleich (Suche nach Hashkey, Sortkey)
Methode	Scan	Gleichheitssuche	Bereich	Insert	Delete
Heap	-	0	0	++	++
Hash	--	+	-	+	+
Sorted	-	++	+	0	0

Indexstruktur
Indexe müssen aktualisiert werden und verbrauchen Speicherplatz. Deshalb kann es wichtig sein, den Index klein zu halten (z.B. sparse unique index).
Eine Indexstruktur verbindet eines Schlüsselwert mit einem Datensatz. Dabei kann entweder das gesamte Tupel als Schlüssel abgelegt werden (dabei entsteht jedoch wieder soetwas wie ein Heapfile) oder nur ein Teil der Attributwerte mit einem Verweis auf den Speicherplatz des Datensatzes.

Primärindex ist ein Index, dessen Indexattribut der Primärschlüssel einer Relation ist.
Unique Index ist ein Index, dessen Indexattribut Schlüsselkandidat (UNIQUE) der Relation ist.
Alles anderen Indexe heißen Sekundärindex.
Ein clustered index verweist auf eine gemäß der Indexeinträge sortierten Menge an Speicherstellen.
Zeigen die Speicherplatzverweise der Indexeinträge auf eine unsortierte Anordnung von Datensätzen auf dem Speichermedium, spricht man von einem unclustered index. (Vor allem bei der Indexierung eines Heapfiles zutreffend.)
dense index heißt ein Index, der Einträge für alle Datensätze der Relation enthält.

sparse index heißt ein Index, der nicht dense ist, und jeweils nur den ersten Datensatz jeder Speicherseite adressiert. Somit ist ein sparse index immer clustered, die Sortierung ergibt sich jedoch nicht aus Attributwerten, sondern aus der (zufälligen) Anordnung der Datensätze auf dem Speichermedium.

CREATE INDEX Indexname ON Tablename (Attribut1, Attribut2)

Baumstrukurierte Indexe

ISAM heißt index sequential access method. Es handelt sich dabei um eine bei der Indexerzeugung statisch erzeugte Baumstruktur aus mehreren Indexebenen. Da die sich im nachhinein nicht mehr ändern lässt, empfiehlt sich ISAM für Datenbankanwendungen, in denen größtenteils Lese-Operationen und Selektionen ablaufen. Insert, Update und Delete machen nachfolgende Abfragen über die Indexstruktur weniger effizient.
Für einen ISAM-Baum werden zunächst die Datensätze gemäß Indexschlüssel sortiert. Dann wird ein Indexbaum aufgebaut. Sollen Datensätze eingefügt werden, müssen dazu neue overflow pages an die Terminale des Index angehangen werden. Ein ISAM-Index-Knoten besteht aus N Schlüsseln und N+1 Zeigern auf nachfolgende Knoten. Die Zeiger links vom Schlüsselwert S verweisen auf Knoten mit kleineren Schlüsselwerten, die rechts davon auf eine Verzweigung mit Schlüsselwerten, die größer oder gleich S sind.
B+ Bäume verändern sich dynamisch entsprechend der aufzunehmenden Daten. Damit werden die Schreibprobleme in ISAM-Strukturen überwunden. Bei Löschen und Einfügen von Datensätzen verändert sich die Baumstruktur. Der Baum bleibt stehts höhenbalanciert. Die Reorganisation erfordert jedoch Ressourcen, sodass für Readonly-Datenbanken ISAM-Indexe zu empfehlen sind.
Die Datensätze müssen sequentiell aufeinander verweisen (Vorgänger und Nachfolger). Der B+Baum hat eine Ordnung d. Es gilt: Außer der Wurzel muss jeder Baumknoten mindestens d und höchstens 2*d viele Indexeinträge haben. Jeder Indexeintrag ist von Zeigern umgeben, die nach unten links (kleinere Wert) oder unten recht (gleiche oder größere Werte) in der Baumstruktur zeigen.
Mit Fanout bezeichnet man die Breite des B+Baumes. Die Anzahl der Blätter ist N.

Effizienz B+Baum
Insert Delete
logF(N) Insert

SQL-Statements zu den relationsalgebraischen Ausdrücken

SELECT	DISTINCT filtert doppelte Einträge aus der Ergebnisliste heraus.
INSERT INTO	zum Einfügen von Tupeln in die Relation
CREATE TABLE	konzeptionelles Schema für eine neue Relation
CREATE VIEW

Trigger sind in SQL formulierte Prozeduren, die wie ein Eventhandler oder ein Aspect bei der Ausführung bestimmter definierter Operationen anspringen und ihrerseits Operationen auf Datensätzen ausführen können.

GROUP BY und HAVING

GROUP BY an einer SELECT - Anweisung zerlegt im mathematischen Sinn die Ergebnismenge. Dabei ist ein Attribut anzugeben, dessen Wert die Äquivalenzklasse identifiziert und nach dem die Zerlegung erfolgt.

Relation Leute
ID	Name	Wert
abcd-1234-fgh	Werner	3
abcd-1235-fgh	Hans	8
abcd-1234-xgh	Peter	4
abcd-1234-kgh	Jürgen	8
abcd-12565h	Alex	3
abcd-1234-jj	Otto	4

SELECT Wert FROM Leute GROUP BY Wert

Wert

Die Anfrage wirkt also zunächst wie SELECT DISTINCT Wert FROM Leute. Benutzet man statt SELECT Attribut ein SELECT* werden jene Zeilen ausgelassen, deren GROUP-BY-Wert bereits in der Ergebnisliste vorkam (das sie hinsichtlich der Group-By-condition äquivalent sind).

Das Entscheidende ist, das sich mit Group-By die sogenannten Aggregatfunktion (Funktionen, die auf der Ergebnismenge ausgeführt werden) mit Bezug auf die erzeugten Äquivalenzklassen ausführen lassen.

Relation Leute
ID	Name	Alter
abcd-1234-fgh	Werner	3
abcd-1235-fgh	Hans	8
abcd-1234-xgh	Peter	4
abcd-1234-kgh	Jürgen	8
abcd-12565h	Alex	3
abcd-1234-jj	Otto	4

*SELECT Name, COUNT(Age) AS Altersgenossen FROM `leute` GROUP BY Age*
Name	Altersgenossen
Hans	2
Werner	2
Peter	2

Hierbei wird also gezählt, wieviele Tupel es in einer Age-Äquivalenzklasse gibt. Zusätzlich lässt sich noch eine HAVING-Klausel angeben. Hier lässt sich eine Selektionsbedingung angeben. Die dort benannte Bedingung wird ebenfalls im Kontext der Äquivalenzklasse jeden Tupels ausgewertet.

*SELECT Name, COUNT(Age) AS Altersgenossen FROM `leute` GROUP BY Age HAVING COUNT(Age)>2*
Name	Altersgenossen

Bleibt leer, der ja alle nur 2 Altersgenossen haben.

Statement Level Interface und Call Level Interface
Es gibt zwei Möglichkeiten, um Anfragesprachen - inbesondere SQL - aus einer Programmierumgebung heraus für Datenbankabfragen zu Nutzen.
Grundsätzlich stellt die Programmierumgebung dann ResultSets zur Verfügung, Objekte, in denen die Elemente der Ergebnismenge nach dem Cursor-Prinzip (Index-Navigierbarkeit) adressiert werden können. Hinzu kommt die Möglichkeit von ORDER BY-Statements nach SELECT-Anweisungen. Die Ergebnisliste wird dann nach einem anzugebenen Kriterium sortiert (Textattribut, Zahlengröße, etc).

Call Level Interface - Die Programmierumgebung stellt Schnittstellenobjekte zur Datenbank zur Verfügung. Denen werden per String-Argument Abfragen übergeben, die an die Datenbank weitergeleitet und dort ausgewertet werden. Beispiele sind ODBC und JDBC.

Exemplarischer Ablauf einer Datenbankanfrage und der Verbindungsverwaltung mit JDBC:
Class.forName("JDBCDriver");
Connection oCon = DriverManager.getConnection(Servername, Databasename, Username, Password);
Statement oStat = oCon.createStatement();
ResultSet oErgebnis = oState.executeQuery("SELECT * FROM Tablename");
System.out.println(oErgebnis.getString(1));
oErgebnis.close();
oCon.close();
Das Paket java.sql ist zu importieren. DriverManager ist eine statische Klasse zur Datenbanktreiberverwaltung aus dem java.sql-Paket.

Über das Statement Level Interface können Anfrageoperationen genutzt werden, indem sie direkt in die Wirtssprache integriert wurden. I.d.R. werden SQL-Anweisungen mit einem Precompiler auf CLI-Ebene übersetzt. SLI gibt es für viele Programmierumgebungen, u.a. für C und Pascal. Es sind syntaktische Erweiterungen nötig, um die programmiersprachlichen Anweisungen bzgl. ihrer Interpretation als SQL oder Wirtssprache zu unterscheiden.

exec sql connect to ConnectionString
exec sql select count(*) into :var from tablename
exec sql commit release
Variablennamen mit führendem Doppelpunkt sind Variablen aus der umgebenden Programmierumgebung. Exec-Sql weist den Precompiler zur Textersetzung an.

ERM nach Chen und Transformationsregeln

Attribute sind rund, Entitäten (die Gegenstände, über die Aussagen getroffen werden sollen) sind als Vierecke dargestellt. Ein einfacher Strich zeigt eine einfach Beziehung - ein so verbundenes Attribut kommt einer Tabellenspalte gleich. Doppelte Striche zeige mehrwertige Attribute. Da (1. Normalform) alle Attributewerte eindeutig sein müssen, müssen mehrwertige Attribute in eigene Relationen überführt werden.
Die Raute zeigt eine Relation zwischen Entitäten und kann selbst auch eigene Attribute aufweisen. Diese Entitätsrelationen sind somit ebenfalls als eigene Tabellen darzustellen. Rekursive Beziehungen erfordern Rollenbezeichnungen. Die Entitätsrelationen können wahlweise zusätzlich mit Kardinalitäten ergänzt werden. Jede Rolle kann eine Kardinalitätsangabe haben. Es gibt 1:1 - jedes Element auf der linken Seiten steht genau mit einem Element auf der rechten Seite in Relation. Bei einer 1:n Relation stehen beliebig viele rechtsseitige Elemente mit dem Element auf der linken Seite in Relation. Bei M:n stehen beliebige viele linke Element mit beliebig vielen rechten Elemente in Beziehung.

Transformationsregel 1: Entitätsname wird Relationstitel
Transformationsregel 2: Die Bestandteile zusammengesetzter Attribute (hier: Name) werden zu eigenen Spalten. Mehrwertige Attribute (hier: Nachrichten) werden zu eigener Relation.
Transformationsregel 3: Eine M:N Entitätsrelation muss in einer eigenen Tabelle abgebildet werden, die alle Primärschlüssel der einbezogenen Entitäten enthält (hier: Freunde). Der Primärschlüssel der Relationsrelation besteht aus diesen beiden Fremdschlüsseln.
Transformationsregel 4: Die Relationen 1:N oder 0:N können so abgebildet werden: Die Relation der variablen Anzahl (N, rechte Seite) erhält eine zusätzliche Fremdschlüsselspalte mit den Primärschlüssel der linksseitigen Relation.
Transformationsregel 5: Relationen der Art 0:1 müssen als zusätzliche Spalte in beiden beteiligten Relationen angegeben werden. Diese Spalte enthält den jeweils anderen Primärschlüssel als Fremdschlüssel, und ihr Wert darf NULL sein.
Transformationsregel 6: Relationen 1:1 werden in einer Tabelle zusammengefasst, die beide Entitäten komplett enthält.

Relation Person
Kennziffer	Vorname	Nachname
abcd-1234-fgh	Werner	Müller
bbcd-1234-fgh	Ingo	Schmidt
cbcd-1234-fgh	Hans	Schulz

Relation NachrichtenPerson
Person.Kennziffer	Nachrichten
abcd-1234-fgh	Werner, komm nach Hause!
abcd-1234-fgh	Wo sind die Socken?
bbcd-1234-fgh	Hr. Schmidt, bitte rufen Sie mich zurück!
cbcd-1234-fgh	Urlaubsgrüße an Hans!
cbcd-1234-fgh	Zahlungsaufforderung: Bitte überweisen Sie den Betrag...

Relation PersonFreundschaft
BefreundetMit1.Kennziffer	BefreundetMit2.Kennziffer
abcd-1234-fgh	abcd-1234-fgh
abcd-1234-fgh	bbcd-1234-fgh
cbcd-1234-fgh	abcd-1234-fgh

Relation PersonAdresse
Person.Kennziffer	Einzugsdatum	Adresse.AdressenId
abcd-1234-fgh	01.02.05	adr1
bbcd-1234-fgh	23.11.81	adr2
cbcd-1234-fgh	18.12.83	adr3

Relation Adresse
AdressenId	Ort	Straßenname	Postleitzahl	Hausnummer	Telefon
adr1	Neustadt	Blumenstraße	14456	15	03324-76894
adr2	Darmstadt	Landallee	26456	25	034-75234
adr3	Dietikon	Hauptstraße	4456	5	0044-31-734894

ermchenstencils.vss selbstgemachte Visio-Stencils für Chen Diagramme

v.1

ermchenstencils.vss

(22k)

Michael Leben,

08.04.2010 16:33

Relationale Datenbanken

Datenbanksysteme

Theoretische Grundlagen

Kommentare

Navigation

	Diese Site durchsuchen