Erklären Sie die Primärorganisation nach indexsequentieller Art und nach dem Hash-Verfahren und nennen dabei je zwei Vor- und Nachteile dieser Organisationsform
Index Sequentiell: Sätze werden gemäß Primärorganisation gespeichert, zugleich wird für den Primärschlüssel ein Index aufgebaut.
Hash Verfahren: Die Speicheradresse wird durch Umrechnungsformen aus dem Primärschlüssel errechnet.
Hash Verfahren: Die Speicheradresse wird durch Umrechnungsformen aus dem Primärschlüssel errechnet.
Was sind Hot Spots beim Transaktionsbetrieb und wie kann man das Problem beseitigen?
Hotspots sind Blöcke die ständig gelesen & geschrieben werden und somit nie in die permanente DB zurückgeschrieben werden. Es sammelt sich einiges an, was im Fehlerfall zu aufwändigen Recovery Führt
Lösung: Checkpoints: Zeitpunkte an denen zwangsweise Blöcke in die DB geschrieben werden --> Hoher E/A-Verkehr, temporäre Inkonsistenz, aber verbesserte Recovery im Fehlerfall
Lösung: Checkpoints: Zeitpunkte an denen zwangsweise Blöcke in die DB geschrieben werden --> Hoher E/A-Verkehr, temporäre Inkonsistenz, aber verbesserte Recovery im Fehlerfall
Unterscheiden Sie die Begriffe Sicherheit und Integrität
Für Sicherheit wird jeder Benutzer überprüft, ob er berechtigt ist, die Dinge zu tun, die er gerade versucht
Für Integrität wird überprüft, ob die Dinge die gerade versucht werden, auch korrekt ablaufen
Berechtigt, Korrekt müssen genannt werden
Für Integrität wird überprüft, ob die Dinge die gerade versucht werden, auch korrekt ablaufen
Berechtigt, Korrekt müssen genannt werden
Sei ein Knoten eines B-Baums in einem Block gespeichert und sei die Blockgröße x=512 Bytes. Außerdem habe ein Schlüsselfeld die Länge k=9 Bytes und ein Blockzeiger die Länge z=6 Bytes sowie jeder Indexeintrag k* ein Paar (k,v)
Von welcher Ordnung m kann der B-Baum höchstens sein?
Von welcher Ordnung m kann der B-Baum höchstens sein?
(2m+1)*z+2m(k+z) <= 512
2m+1 Blockzeiger auf Sohnkoten
2m Suchschlüsselfelder zu Indexeinträgen
k=9, z=6
(2m+1)*6+2m(9+6) <= 512
m<=12
2m+1 Blockzeiger auf Sohnkoten
2m Suchschlüsselfelder zu Indexeinträgen
k=9, z=6
(2m+1)*6+2m(9+6) <= 512
m<=12
Gegeben sei eine sequentielle Datei mit n = 100.000 Datensätzen, die auf einer Festplatte mit Blockgröße s=1024 Bytes gespeichert sind. Es darf angenommen werden, dass alle Datensätze fester Läge l=100 Bytes sind und Seitengrenzen nicht überschreiten.
Angenommen, dass das Suchschlüsselfeld (Sortierfeld) die Länge k=9 Bytes besitzt und dass ein Zeiger vom Index auf einen Block der Datei z=6 Bytes benötigt.
Wie viele Blockzugriffe benötigt eine binäre Suche auf diese Datei?
Wie viele Blockzugriffe werden zum Auffinden eines Datensatzes benötigt, wenn für die Datei ein dichter bzw. dünner Primärindex erzeugt wird?
Angenommen, dass das Suchschlüsselfeld (Sortierfeld) die Länge k=9 Bytes besitzt und dass ein Zeiger vom Index auf einen Block der Datei z=6 Bytes benötigt.
Wie viele Blockzugriffe benötigt eine binäre Suche auf diese Datei?
Wie viele Blockzugriffe werden zum Auffinden eines Datensatzes benötigt, wenn für die Datei ein dichter bzw. dünner Primärindex erzeugt wird?
Binär:
r=s/l (abgerundet) = 10 Datensätze pro Block
Anzahl der benötigten Blöcke ist b = n/r (aufgerundet) = 100.000/10 = 10.000
Eine binäre Suche benötigt log2(b) (aufgerundet) Zugriffe
log2(10.000) 14 Zugriffe
Dichter Index:
Größe eines Indexeintrages: 9+6 = 15
Indexeinträge 1024/15 = 68 Indexeinträge pro Block
Benötigte Blöcke = 100.000/68 (aufgerundet) = 1.471
log2(1.471) = 11 Zugriffe (aufgerundet)
Dünner Index:
100.000 Blöcke durch 68 Einträge (aufgerundet)
100.000/68 = 148
log2(148) = 8 Zugriffe (aufgerundet)
r=s/l (abgerundet) = 10 Datensätze pro Block
Anzahl der benötigten Blöcke ist b = n/r (aufgerundet) = 100.000/10 = 10.000
Eine binäre Suche benötigt log2(b) (aufgerundet) Zugriffe
log2(10.000) 14 Zugriffe
Dichter Index:
Größe eines Indexeintrages: 9+6 = 15
Indexeinträge 1024/15 = 68 Indexeinträge pro Block
Benötigte Blöcke = 100.000/68 (aufgerundet) = 1.471
log2(1.471) = 11 Zugriffe (aufgerundet)
Dünner Index:
100.000 Blöcke durch 68 Einträge (aufgerundet)
100.000/68 = 148
log2(148) = 8 Zugriffe (aufgerundet)
Vergleichen Sie invertierte Listen und Multiliststrukturen als Möglichkeiten zur Sekundärorganisation für eine Datenbank bezüglich Ihrer Grundstruktur sowie den 3 Kriterien Speicherbedarf, Zugriffsverhalten beim Lesen sowie dem Aufwand beim Einfügen und Ändern (Aufwand bei hoher Fluktuation des Datenbestands)
Worin liegt die Besonderheit eines B*-Baumes gegenüber einem B-Baum und wo liegen die jeweiligen Einsatzgebiete dieser Datenstrukturen
B*-Baum hat eine Höhe h-1 für die Suchstruktur B*-Baum Index, die nicht alle Schlüssel enthält und eine B*-Baum Datei.
Schnellerer wahlfreier Zugriff als B-Baum (höhere Ordnung m-->kleineres h)
B*-Baum Datei enthält auch schnellen logisch fortlaufend ??
Schnellerer wahlfreier Zugriff als B-Baum (höhere Ordnung m-->kleineres h)
B*-Baum Datei enthält auch schnellen logisch fortlaufend ??
Was ist ein Zwei-Phasen-Commit, wie verläuft er und welches Problem ergibt sich daraus?
Ein Zwei-Phase-Commit ist nötig bei dem Zugriff einer Transaktion auf mehrere Datenbanken.
Problem des hohen Kommunikationsaufwands durch lokale und globale Koordination (Verzehnfachung der Antwortzeit)
a)lokales Abarbeiten der Transaktion
b)Melden des Transaktionsendes
c)Globales Transaktionsende
d)endgültiges lokales Transaktionsende
Problem des hohen Kommunikationsaufwands durch lokale und globale Koordination (Verzehnfachung der Antwortzeit)
a)lokales Abarbeiten der Transaktion
b)Melden des Transaktionsendes
c)Globales Transaktionsende
d)endgültiges lokales Transaktionsende
Nennen Sie 6 Regeln aus dem fundamentalen Prinzip von Date für verteilte Datenbanken
Lokale Eigenständigkeit jedes Rechners
Keine zentrale Verwaltungsinstanz
Ständige Verfügbarkeit
Lokale Unabhängigkeit
Unabhängigkeit gegenüber Fragmentierung
Unabhängigkeit gegenüber Datenreplikation
Wer Bock auf mehr hat:
Keine zentrale Verwaltungsinstanz
Ständige Verfügbarkeit
Lokale Unabhängigkeit
Unabhängigkeit gegenüber Fragmentierung
Unabhängigkeit gegenüber Datenreplikation
Wer Bock auf mehr hat:
In einem sicheren DB-Betrieb wurde gerade das Transaktionsende in die Logdatei geschrieben. Noch vor der Rückmeldung der Transaktion an den Benutzer stürzt das System ab. Wird beim nächsten Hochfahren die Transaktion deshalb zurückgesetzt?
Die Transaktion ist gültig, da nur die Information aus der Logdatei zählt
Was sind Checkpoints? Beschreiben Sie den Nachteil, wenn eine DB ohne Checkpoints arbeiten würde.
Checkpoints sind Zeitpunkte an denen alle Datenbankdateien im Arbeitsspeicher auf das nichtflüchtige externe Medium geschrieben werden. Ohne C würden häufig angefasste Daten (Hot Spots) immer in ASP stehen bleiben und nie extern aktualisiert werden. Im Fehlerfall müsste dann immer die gesamte Logdatei durchsucht werden, was sehr zeitaufwendig ist.
In nicht wenigen DB-Anwendungen ist die Recovery-Unterstützung deaktiviert oder zumindest stark eingeschränkt. Woran mag das liegen?
Recovery senkt wegen des zusätzlichen Overheads den Durchsatz und die mittleren Antwortzeiten deutlich ab. Entsprechend schnellere Rechner und Speichermedien sind wesentlich teurer. Abwägung: Zuverlässiger DB-Betrieb oder niedrige Betriebskosten
Welche Schritte müssen vom Systemadministrator bzw. vom DBMS durchgeführt werden, wenn eine einzelne Transaktion wegen eines Softwarefehlers abstürzt?
Rücksetzen dieser TA mittels Rollback inkl. Der Freigabe von gehaltenen Sperren. Fehlermeldungen an den Besitzer
Ein DBA merkt, dass die Magnetplatte der DB nicht mehr fehlerfrei arbeitet. Welche Maßnahmen müssen ergriffen werden, um mögliche fehlerbehaftete Schreibvorgänge seit der letzten Sicherung zu eliminieren?
Anhalten des gesamten DB-Betriebs.
Rücksetzen aller noch nicht abgeschlossenen TA mittels Rollback. Abklemmen der Platte, montieren einer neuen Festplatte. Kopieren der letzten Sicherung, nachfahren der Änderungen seit der letzten Sicherung mittels Logdateiinformationen.
Starten des DB-Betriebs.
Rücksetzen aller noch nicht abgeschlossenen TA mittels Rollback. Abklemmen der Platte, montieren einer neuen Festplatte. Kopieren der letzten Sicherung, nachfahren der Änderungen seit der letzten Sicherung mittels Logdateiinformationen.
Starten des DB-Betriebs.
Unter welchen Voraussetzungen kann auf ein After-Image verzichtet werden?
Nie! Sonst Datenverluste bei Plattenausfall.
Was macht einen Zwei-Phasen-Commit so zeitintensiv?
Je Datenbank muss ein Log geführt werden, zusätzlich ist ein globaler Log erforderlich. Hauptaufwand ist der hohe Kommunikation-overhead.
Wie erkennt man Deadlocks und wie beseitigt man sie?
In der Praxis werden Deadlocks meist mittels Wartegrafen(WFG) erkannt. Die betroffenen TA werden zurückgesetzt (genauer die TA mit geringstem Ressourcenbedarf, also Rücksetzungsaufwand).
Im Parallelbetrieb kann man auch ohne Sperrmechanismen auskommen. Worum handelt es sich und warum wird das Verfahren kaum eingesetzt?
Optimistisches Verfahren: steigt die Konfliktwahrscheinlichkeit auf über 10% so schaukelt sich das System katastrophal auf. (Rücksetzungsaufwand höher als eingesparte Wartezeit)
Was wird unter Unabhängigkeit gegenüber Fragmentierung und gegenüber Replikation verstanden?
Fragmentierung: Verteilung einer Relation auf mehrere Rechner (horizontal/vertikal)
Replikation: Dieselben Daten können auf mehreren Rechnern gleichzeitig gehalten werden
Unabhängigkeit bedeutet dann, dass sich das System an der Benutzerschnittstelle nicht anders verhält, ob mit oder ohne Frag./Rep.
Replikation: Dieselben Daten können auf mehreren Rechnern gleichzeitig gehalten werden
Unabhängigkeit bedeutet dann, dass sich das System an der Benutzerschnittstelle nicht anders verhält, ob mit oder ohne Frag./Rep.
Wie kann das Problem des erhöhten Datenaustauschs in verteilten Systemen minimiert werden?
Durch Replikatverwaltung auf einem „Heimatrechner”, geschickte Abfragestrategien, optimale Verteilung, und optimierte Protokolle.
Definieren Sie den Begriff „Verteilte Datenbanken“
DB heißt verteilt, wenn die zusammengehörigen Daten einer DB auf mind. 2 Rechnern verteilt sind und in einem gemeinsamen DB Management System verwaltet werden.
In verteilten Sytemen kann es globale Deadlocks geben, können auch lokale Deadlocks auftreten?
Es können wie üblich auch lokale Deadlocks auftreten, wenn eine Transaktion nur lokale zugriffe ausführt.
Ist unter Verwendung eines Zwei-Phasen-Commit-Protokolls die Regel 2 erfüllbar, obwohl dafür ein zentraler Koordinator benötigt wird?
Regel zwei ist dann erfüllbar, wenn der Koordinator nicht zentral auf einen Rechner gehalten wird. Übernimmt der Rechner die Koordination, der die globale Transaktion startete, ist Regel 2 nicht verletzt.
In einem Parallelbetrieb ist es nicht immer leicht zu sagen, ob eine Transaktion A vor oder nach einer Transaktion B ablief. Kann dieses Problem immer entschieden werden, wenn wir mit Sperrmechanismen arbeiten?
Nur teilweise: Transaktionen, die auf gemeinsame Daten zugreifen, werden serialisiert, die Reihenfolge kann angegeben werden. Für alle anderen TA, die gleichzeitig laufen, gilt dies nicht.
Welcher Nachteil kann sich beim Baumaufbau beim häufigen Ein- und Ausfügen in Bäumen einstellen? Wie kann man den Nachteil beseitigen? Welcher neue Nachteil stellt sich dann ein?
Bäume können schieflastig werden, entarten (=> Hohe Zugriffszeit). Mit ausgeglichenen Bäumen ( B-Bäume, B*-Bäume, AVL-Bäume). Kann dies verändert werden, aber dann hoher Aufwand bei häufigen Einfügen oder Entfernen.
Wie unterscheidet sich eine relationale DB von nicht relationalen DB?
Relationale DB bestehen ausschließlich aus Tabellen und auch der Zugriff erfolgt über diese Tabellen. Beziehungen durch Verknüpfung der Tabellen aufgrund gemeinsamer Attribute (Fremdschlüssel-Primärschlüssel).Nicht durch seq. 1:N (-Beziehung) Väter - Söhne (seq. Speicherung) oder Navigation mit Adressverweisen bei OWNER und MEMBER
Wo liegen die Stärken und Schwächen eines hierarchischen DB- Systems?
Stärken: Minimaler Speicherbedarf, hoher Durchsatz sehr gute Antwortzeiten bei 1:N Realität.
Schwächen: Nur geeignet bei hierarchischer Situation sonst Zugriff sehr komplex, phys. Struktur muss Anwender bekannt sein
Schwächen: Nur geeignet bei hierarchischer Situation sonst Zugriff sehr komplex, phys. Struktur muss Anwender bekannt sein
Erklären Sie den Begriff Refenzielle Integrität
Korrektheit der Beziehung wird erzielt durch Prüfung in der Detailtabelle ob der Fremdschlüssel beim Einfügen eines neuen Datensatzes auch als Primärschlüssel in der Mastertabelle existiert.
Optimal: Löschweitergabe, Aktualisierungsweitergabe
Optimal: Löschweitergabe, Aktualisierungsweitergabe
Erklären Sie Transitive Abhängigkeit
Transitive Abhängigkeit: (indirekte Abhängigkeit vom PS) Verletzung der 3NF durch Abhängigkeit zwischen Nichtschlüsselattribut
Erklären Sie After Image
After Image: Speicher(Abbild) Zustand im permanenten Speicher (Logdatei ungleich DB!) nach erfolgreicher Beendigung der TA ( commit).
Erklären Sie S2PL
S2PL: (strict two phase locking protocoll) Ist ein dynamisches pessimistisches Synchronisationsverfahren, das gegenüber C2PL wegen geringerer Wartezeiten favorisiert wird (Deadlocks!).
Erklären Sie globales Attribut
Globales Attribut: Attribut, dass in mind. Einer Tabelle Schlüsselattribut ist.
Erklären Sie Invertierte Liste
Invertierte Listen: Sekundärer Zugriffspfad bei den die Zugriffsstruktur getrennt von den eigentlichen Daten gespeichert wird.
Erklären Sie B*-Baum
B*-Baum: Primär-Organisation bei dem der B*-Baum Index (Höhe h-1) die Suchstruktur auf die Daten der B*-Baum Datei darstellt (seq. Durchlauf in Sortierfolge möglich!). Max. Zugriff vorhersagbar
Erkläre Primärorganisation indexsequentieller Art
Sätze werden gemäß PS sortiert gespeichert
für PS wird ein Index aufgebaut
für PS wird ein Index aufgebaut
Vor und Nachteile von Primärorganisation nach index sequentieller Art
V:Lesezugriff: Schneller sortierter Zugriff, Binärsuche für wahlfreien Zugriff möglich
N:Speicherbedarf: Zusatzaufwand für Indexstruktur und ggf. Überlaufbereiche
N:Einfügen/löschen: Behandelung der Überlaufbereiche, Reorganisation der Indexstrukturen
N:Speicherbedarf: Zusatzaufwand für Indexstruktur und ggf. Überlaufbereiche
N:Einfügen/löschen: Behandelung der Überlaufbereiche, Reorganisation der Indexstrukturen
Erkläre Primärorganisation nach Hash-Verfahren
Speicheradresse wird durch Umrechnung aus dem PS errechnet
(Hash-Algo)
(Hash-Algo)
Vor und Nachteile Primärorganistion nach Hash-Verfahren
V:Speicherbedarf: kein Index nötig,
V:Lesezugriff: schneller Zugriff bei direkter Adresse
V:Einfügen/Löschen: einfacher Algo für suchen&updaten
N:Speicherbedarf:ggf nicht belegte Speicherplätze; reservierte Überlaufbereiche
N:Einfügen/Löschen: ggf neuer Algo oder Speicherbereich nötig
V:Lesezugriff: schneller Zugriff bei direkter Adresse
V:Einfügen/Löschen: einfacher Algo für suchen&updaten
N:Speicherbedarf:ggf nicht belegte Speicherplätze; reservierte Überlaufbereiche
N:Einfügen/Löschen: ggf neuer Algo oder Speicherbereich nötig
Welche Arten von Clustern bei Datenbanken?
Indexcluster: Jeder Wert des Clusterattributs nur einmal gespeichert. Alle Tupel mit gleichem Attributwert auch
Hashcluster: Jedes Tupel mit gleichem Hashwert wird auf gleicher Seite oder bei Überlauf auf phys. benachbarten Seiten gespeichert
Hashcluster: Jedes Tupel mit gleichem Hashwert wird auf gleicher Seite oder bei Überlauf auf phys. benachbarten Seiten gespeichert
Vorteil von Clustering
Clustering, ist die Fähigkeit, die ausgefallene Serverhardware und ausgefallene Software wiederherzustellen.
Unterschied: Sicherheit/Integrität und wann?
Sicherheit: prüft nach Berechtigung, bei Nutzern,
-> Vor Zugriff
Integrität: prüft Korrektheit der Abläufe
-> Während Zugriff
-> Vor Zugriff
Integrität: prüft Korrektheit der Abläufe
-> Während Zugriff
Nenne Attribute zur Multilist
Grundstruktur: Einbettung der Zugriffpfade in Sätze (Listenkopf und Zeiger in Daten
Speicherbedarf: Gering, da nur Listenkopf und Zeiger zusätzlich nötig
Lesezugriff: Erstzugriff auf Listenköpfe, dann verkettete Liste schnell durchlaufbar
Einfügen/Löschen: Zeiger setzen, löschen -> geringer Aufwand
Speicherbedarf: Gering, da nur Listenkopf und Zeiger zusätzlich nötig
Lesezugriff: Erstzugriff auf Listenköpfe, dann verkettete Liste schnell durchlaufbar
Einfügen/Löschen: Zeiger setzen, löschen -> geringer Aufwand
Nenne Attribute zur Invertierte Liste
Grundstruktur: Trennung von Sätzen und Zugriffpfaden (Aufbau je einer Indexdatei pro Sekundärschlüssel)
Speicherbedarf: hoch aufgrund der Indexdatei pro Attribut
Lesezugriff: Zugriff auf sortierten Index über Zeiger auf Sätze, schnell und wahlfrei
Einfügen/Löschen: hoher Verwaltungsaufwand, ggf mehrer Indexdateien zureorganisieren
Speicherbedarf: hoch aufgrund der Indexdatei pro Attribut
Lesezugriff: Zugriff auf sortierten Index über Zeiger auf Sätze, schnell und wahlfrei
Einfügen/Löschen: hoher Verwaltungsaufwand, ggf mehrer Indexdateien zureorganisieren
Wann invertierte Liste
Lohnt sich bei hoher Selektivität (qualifizierte Tupel < 10% der DB)
-> sonst sequentieller Durchlauf
-> sonst sequentieller Durchlauf
Welche Daten soll eine IST/SOLLanalyse eines DB-Entwurfs enthalten?
Analyse der Datenmenge, Änderungstendenzen
BSP:
max, min durchschnittliche Tupel/Relation
Fluktuation Tupelanzahl
Analyse Datenbenutzung
BSP:
welche Zugriffe werden benötigt
Häufigkeit der Transaktion pro Stunde/Tag..
Anzahl parallerer Transaktionen
Antwortzeiten
BSP:
max, min durchschnittliche Tupel/Relation
Fluktuation Tupelanzahl
Analyse Datenbenutzung
BSP:
welche Zugriffe werden benötigt
Häufigkeit der Transaktion pro Stunde/Tag..
Anzahl parallerer Transaktionen
Antwortzeiten
Sequentieller Zugriff:
Sequentieller (sortierter) Zugriff auf eine indizierte Datei über einen
Suchschlüssel wie z.B. auf eine Angestelltendatei mit Hilfe des Namens.
Suchschlüssel wie z.B. auf eine Angestelltendatei mit Hilfe des Namens.
Direkter Zugriff:
Auf einzelne (Punktanfrage; exact match query) oder mehrere Datensätze kann
über einen Suchschlüssel direkt zugegriffen werden wie z.B. auf den Angestellten
mit der Nummer 12345.
über einen Suchschlüssel direkt zugegriffen werden wie z.B. auf den Angestellten
mit der Nummer 12345.
Bereichszugriff:
Bereichsanfragen (match queries) finden dann z.B. alle Angestellten mit
Nummern zwischen 10815 und 14711.
Nummern zwischen 10815 und 14711.
Existenztests:
Solche Fragen können dann sogar ohne Zugriff auf den eigentlichen
Datenbestand auch schon über die Indexstruktur beantwortet werden wie z.B. ob
es einen Angestellten gibt, der die Nummer 12345 hat.
Datenbestand auch schon über die Indexstruktur beantwortet werden wie z.B. ob
es einen Angestellten gibt, der die Nummer 12345 hat.
Klassifikationen von Indexstrukturen:
Dichte und dünne Indexe
Primär- und Sekundärindexe
Geclusterte und nicht geclusterte Indexe
Indexe mit einfachen und zusammengesetzten Suchschlüsseln
Ein- und mehrstufige Indexe
Primär- und Sekundärindexe
Geclusterte und nicht geclusterte Indexe
Indexe mit einfachen und zusammengesetzten Suchschlüsseln
Ein- und mehrstufige Indexe
Was ist ein dichter Index?
Ein Index wird als dichter Index bezeichnet, wenn er (wenigstens) einen
Indexeintrag für jeden Suchschlüsselwert, der in einem Datensatz der indizierten
Datei auftritt, enthält
Indexeintrag für jeden Suchschlüsselwert, der in einem Datensatz der indizierten
Datei auftritt, enthält
Was ist ein dünner Index?
Ein dünner Index enthält einen Eintrag für
jede Seite von Datensätzen der indizierten Datei.
jede Seite von Datensätzen der indizierten Datei.
Wie wird ein Datensatz über dünne Indexe gefunden?
1.Indexeintrag mit dem
größten Suchschlüsselwert, der kleiner oder gleich dem gesuchten
Suchschlüsselwert ist, ermittelen
2.Man beginnt dann bei dem Datensatz auf
den dieser Indexeintrag zeigt und sucht sequentiell auf der entsprechenden Seite
bis der gewünschte Datensatz gefunden ist.
größten Suchschlüsselwert, der kleiner oder gleich dem gesuchten
Suchschlüsselwert ist, ermittelen
2.Man beginnt dann bei dem Datensatz auf
den dieser Indexeintrag zeigt und sucht sequentiell auf der entsprechenden Seite
bis der gewünschte Datensatz gefunden ist.
Nenne Vor-und Nachteile von dünnen Indexen.
V: kleiner als dichter Index
N:
muss sortiert sein
höchstens ein dünner Index möglich
Existenztest brauchen länger als bei dichten Indexen
N:
muss sortiert sein
höchstens ein dünner Index möglich
Existenztest brauchen länger als bei dichten Indexen
Was ist ein Primärindex?
Ein Index, der über einen Primärschlüssel definiert und geordnet ist, wird
Primärindex genannt.
Primärindex genannt.
Was ist ein Sekundärindex?
Ein Index, der für einen Sekundärschlüssel angelegt wird, wird
als Sekundärindex bezeichnet.
als Sekundärindex bezeichnet.
Wichtiges zum Sekundärschlüssel:
enthält Duplikate: mehrere unterschiedliche Attributkombinationen für eine Datei möglich -> mehrere Sekundärindexe
häufig eingesetzt bei:
direkten und sequentiellen Zugriff auf die Daten
Da sortiert -> Binärsuche
Da Datensätze der indizierten Datei nicht physisch auf dem Sekundärschlüssel sortiert sind -> kann nur als dichter Index auftreten
benötigt mehr Platz als ein Primärindex da größeren Anzahl von Einträgen (Duplikate)
Suchzeit schneller durch Sekundärschlüssel (keine lineare Suche)
häufig eingesetzt bei:
direkten und sequentiellen Zugriff auf die Daten
Da sortiert -> Binärsuche
Da Datensätze der indizierten Datei nicht physisch auf dem Sekundärschlüssel sortiert sind -> kann nur als dichter Index auftreten
benötigt mehr Platz als ein Primärindex da größeren Anzahl von Einträgen (Duplikate)
Suchzeit schneller durch Sekundärschlüssel (keine lineare Suche)
Nenne den unterschied zwischen invertiert und vollständig invertiert
Eine Datei, die einen dichten Sekundärindex bezüglich eines Attributs besitzt, wird auch invertierte Datei bezüglich dieses Attributs genannt.
Eine Datei, die
einen dichten Sekundärindex bezüglich jeden Attributs besitzt, das nicht gleich dem Primärschlüssel ist, wird vollständig invertierte Datei genannt.
Eine Datei, die
einen dichten Sekundärindex bezüglich jeden Attributs besitzt, das nicht gleich dem Primärschlüssel ist, wird vollständig invertierte Datei genannt.
Wichtiges zum Primärindex:
nur einen Primärschlüssel -> nur einen Primärindex
keine Duplikate, d.h. nicht mehrere Suchschlüssel mit gleichem Werten.
Hauptproblem(wie bei sequentiell): Einfügen und Löschen von Datensätzen. (Neben dem Einfügen des
Datensatzes in die indizierte Datei muss auch ein Eintrag in den Index erfolgen)
keine Duplikate, d.h. nicht mehrere Suchschlüssel mit gleichem Werten.
Hauptproblem(wie bei sequentiell): Einfügen und Löschen von Datensätzen. (Neben dem Einfügen des
Datensatzes in die indizierte Datei muss auch ein Eintrag in den Index erfolgen)
Was ist Clusterung?
Das Bestreben, logisch zusammengehörige
Datensätze physisch benachbart auf Seiten abzuspeichern
Datensätze physisch benachbart auf Seiten abzuspeichern
Was ist ein geclusterter Index
Wenn eine Datei so
organisiert ist, dass die Ordnung der Datensätze gleich oder beinahe gleich der
Ordnung der Einträge in einem Index ist
organisiert ist, dass die Ordnung der Datensätze gleich oder beinahe gleich der
Ordnung der Einträge in einem Index ist
Was ist das Problem bei geclusterten Indexen?
extrem hoher Aufwand für das
Verschieben der Datensätze beim Einfügen und Löschen
Verschieben der Datensätze beim Einfügen und Löschen
Wie kann das Problem bei geclusterten Indexen gelöst werden?
anfangs sortiert, und jeder Seite wird ein gewisser freier Speicherplatzbereich für zukünftige Einfügungen zugesprochen.
Ist dieser freie Platz durch weitere Einfügungen aufgebraucht, werden weitere Einfügungen auf Überlaufseiten ausgelagert.
Nach einiger Zeit wird die Datei dann reorganisiert
(d.h. neu sortiert).
Ist dieser freie Platz durch weitere Einfügungen aufgebraucht, werden weitere Einfügungen auf Überlaufseiten ausgelagert.
Nach einiger Zeit wird die Datei dann reorganisiert
(d.h. neu sortiert).
Vorteile Nachteile Clusterung
N:teuer
N:Datei kann nur nach einem Suchschlüssel geclustert sein
V:die Indexeinträge zeigen auf eine zusammenhängende Folge von Datensätzen und es müssen nur wenige Seiten gelesen werden
N:Datei kann nur nach einem Suchschlüssel geclustert sein
V:die Indexeinträge zeigen auf eine zusammenhängende Folge von Datensätzen und es müssen nur wenige Seiten gelesen werden
Was ist ein zusammengesetzter Suchschlüssel
Ein Suchschlüssel für einen Index der mehrere Felder enthält
Was ist eine Gleichheitsanfrage
Anfragetyp, wo jedes Feld eines Suchschlüssels mit dem Gleichheitsprädikat verknüpft ist
z.B. Name = „Kunze, Karl“ und Gehalt = 5000 fragen.
auch als Punktabfrage bezeichnet
z.B. Name = „Kunze, Karl“ und Gehalt = 5000 fragen.
auch als Punktabfrage bezeichnet
Was ist eine Bereichsanfrage
bindet nicht jedes Feld des Suchschlüssels an ein Gleichheitsprädikat.
So bedeutet die Anfrage nach Einträgen mit Name =
„Kunze, Karl“, dass für das Gehalt-Feld jeder vorhandener Wert akzeptabel ist
Man kann aber auch z.B. Name < „Meyer, Alfons“ und Gehalt >
4700 fragen
So bedeutet die Anfrage nach Einträgen mit Name =
„Kunze, Karl“, dass für das Gehalt-Feld jeder vorhandener Wert akzeptabel ist
Man kann aber auch z.B. Name < „Meyer, Alfons“ und Gehalt >
4700 fragen
Eindimensionale Indexstrukturen:
Auf der Menge der Suchschlüsselwerte wird eine lineare Ordnung definiert, bezüglich der die Indexeinträge sortiert sind.
Mehrdimensionale Indexstrukturen:
keine lineare Ordnung
Organisation der Indexeinträge erfolgt häufig anhand räumlicher Beziehungen
Jeder Wert eines zusammengesetzten Suchschlüssels mit k Feldern wird dabei als ein Punkt im k-dimensionalen Raum aufgefasst, d.h. jeder der k Feldtypen spannt
eine Dimension auf.
Organisation der Indexeinträge erfolgt häufig anhand räumlicher Beziehungen
Jeder Wert eines zusammengesetzten Suchschlüssels mit k Feldern wird dabei als ein Punkt im k-dimensionalen Raum aufgefasst, d.h. jeder der k Feldtypen spannt
eine Dimension auf.
Nenne ein Beispiel für eindimensionale Indexstrukturen
Standarddaten wie alphanumerische Daten.
Position eines Feldes im Suchschlüssel gibt Priorität beim Sortieren an, d.h. ein Feld an i-ter Position wird in i-ter Priorität sortiert
Bereichsanfragen auf dem jeweils ersten Feld können aufgrund der Nähe sehr effizient beantwortet werden, während eine Bereichsanfrage auf dem zweiten Feld eine lineare Suche auf dem gesamten Index
erfordert.
Position eines Feldes im Suchschlüssel gibt Priorität beim Sortieren an, d.h. ein Feld an i-ter Position wird in i-ter Priorität sortiert
Bereichsanfragen auf dem jeweils ersten Feld können aufgrund der Nähe sehr effizient beantwortet werden, während eine Bereichsanfrage auf dem zweiten Feld eine lineare Suche auf dem gesamten Index
erfordert.
Nenne Beispiele für mehrdimensionale Indexstrukturen
sind geometrische Indexstrukturen
wesentlich komplexer als eine eindimensionale Indexstruktur
Einträge werden gemäß Ihrer Nähe im zugrundeliegenden k-dimensionalen Raum abgespeichert.
Alle Felder im Suchschlüssel werden also mit gleicher (!) Priorität behandelt.
Bereichsanfragen können dann sehr effizient ausgewertet werden.
wesentlich komplexer als eine eindimensionale Indexstruktur
Einträge werden gemäß Ihrer Nähe im zugrundeliegenden k-dimensionalen Raum abgespeichert.
Alle Felder im Suchschlüssel werden also mit gleicher (!) Priorität behandelt.
Bereichsanfragen können dann sehr effizient ausgewertet werden.
Nachteil der mehrdimensionalen Indexstruktur
Suchen auf ausschließlich einem Feld bei einer mehrdimensionalen Indexstruktur in den meisten Fällen langsamer sind
als bei einer eindimensionalen Indexstruktur, wo dieses Feld das erste im Suchschlüssel ist.
als bei einer eindimensionalen Indexstruktur, wo dieses Feld das erste im Suchschlüssel ist.
Wie sucht man bei einem einstufigen
Index?
Index?
ein Index besteht aus einer einzigen geordneten Datei besteh
binäre Suche wird auf dem Index angewendet
Binäre Suche erfordert für einen Index mit b Seiten 1+ ld b Seitenzugriffe.
Bei Überlaufseiten : keine binäre Suche möglich -> sequentielle Suche mit b Seitenzugriffen
-> -> kostenintensiv
binäre Suche wird auf dem Index angewendet
Binäre Suche erfordert für einen Index mit b Seiten 1+ ld b Seitenzugriffe.
Bei Überlaufseiten : keine binäre Suche möglich -> sequentielle Suche mit b Seitenzugriffen
-> -> kostenintensiv
Wie wird bei mehrstufigen Indexen gesucht?
erfordert 1+ logr b Seitenzugriffe was schneller als binäre Suche ist, falls r > 2
Ein mehrstufiger Index mit n Einträgen in der ersten Stufe besitzt ungefähr k Stufen, wobei k = logr n1
Bedingung: die Suchschlüssel der ersten Stufe sind voneinander verschieden und die Einträge haben eine fixe Länge
Ein mehrstufiger Index mit n Einträgen in der ersten Stufe besitzt ungefähr k Stufen, wobei k = logr n1
Bedingung: die Suchschlüssel der ersten Stufe sind voneinander verschieden und die Einträge haben eine fixe Länge
Vor-und Nachteile mehrstufiger Index? Und nennen sie die Lösung für das Problem
V: Reduktion der benötigten Anzahl an Seitenzugriffen anhand eines Suchschlüssels,
N:
Probleme des Einfügens und Löschens, da alle
Stufen des Index physisch sequentielle Dateien sind
Lösung: ein mehrstufiger Index kann benutzt werden, der die Seiten nicht vollständig mit Einträgen füllt, sondern auf jeder
Seite Platz für neue Einträge lässt.
-> dynamischen, mehrstufigen Indexen, zu deren bekanntesten Vertretern der B-Baum und der B+-Baum zählen.
N:
Probleme des Einfügens und Löschens, da alle
Stufen des Index physisch sequentielle Dateien sind
Lösung: ein mehrstufiger Index kann benutzt werden, der die Seiten nicht vollständig mit Einträgen füllt, sondern auf jeder
Seite Platz für neue Einträge lässt.
-> dynamischen, mehrstufigen Indexen, zu deren bekanntesten Vertretern der B-Baum und der B+-Baum zählen.
Nenne Numerische Datentypen! Welche Indexstrukturen bieten sich für alphanumerische Daten an?
numerischen Datentypen: integer real, String-Datentypen, sowie Boolesche Datentypen
-> einfache Struktur ( im Gegensatz zu den geometrischen Datentypen)
-> -> eindimensionale Strukturen, umfassen
indexsequentielle Zugriffsmethode, die B-Baum-Familie und hashbasierte Indexstrukturen
-> einfache Struktur ( im Gegensatz zu den geometrischen Datentypen)
-> -> eindimensionale Strukturen, umfassen
indexsequentielle Zugriffsmethode, die B-Baum-Familie und hashbasierte Indexstrukturen
Was ist eine indexsequentiellen Zugriffsmethode und wie funktioniert sie? Welche Zugriffsmöglichkeiten bietet dies?
ein mehrstufiger, dünner Primärindex
diese Struktur (mit Ausnahme von Überlaufseiten) ist statisch
d.h. sie wird zu Beginn einmal angelegt und (ausgenommen bei
Reorganisationen) danach nie wieder geändert
Datensätze werden dabei als sequentielle Datei organisiert, worüber dann ein mehrstufiger, dünner Primärindex aufgebaut wird
Möglichkeiten für zwei Zugriffsmethoden:
1. der Zugriff kann auf Daten unter Ausnutzung der
sortierten Speicherung, d.h. der sequentiellen Organisation erfolgen
2. unter Verwendung des Index mittels binärer Suche
diese Struktur (mit Ausnahme von Überlaufseiten) ist statisch
d.h. sie wird zu Beginn einmal angelegt und (ausgenommen bei
Reorganisationen) danach nie wieder geändert
Datensätze werden dabei als sequentielle Datei organisiert, worüber dann ein mehrstufiger, dünner Primärindex aufgebaut wird
Möglichkeiten für zwei Zugriffsmethoden:
1. der Zugriff kann auf Daten unter Ausnutzung der
sortierten Speicherung, d.h. der sequentiellen Organisation erfolgen
2. unter Verwendung des Index mittels binärer Suche
Wie wird index-sequentielle Zugriffsstruktur in einem Baum umgesetzt?
statische Baumstruktur
Knoten: entspricht einer Seite der Indexstruktur
Kante von einem Vaterknoten zu einem Sohnknoten: entspricht einem Zeiger des Index von einer Seite der Stufe i zu einer Seite der Stufe i+1
Schlüsselwerte eines Knotens (Primärschlüsselwert): aufsteigend sortiert
Blattseiten: enthalten entweder die Datensätze oder aber
die Indexeinträge auf die Datensätze, die in einer separaten Datei abgelegt sind.
Nichtblattseiten: nur Suchschlüssel, die als Separatoren zum
schnellen Auffinden der richtigen Blattseite dienen
Knoten: entspricht einer Seite der Indexstruktur
Kante von einem Vaterknoten zu einem Sohnknoten: entspricht einem Zeiger des Index von einer Seite der Stufe i zu einer Seite der Stufe i+1
Schlüsselwerte eines Knotens (Primärschlüsselwert): aufsteigend sortiert
Blattseiten: enthalten entweder die Datensätze oder aber
die Indexeinträge auf die Datensätze, die in einer separaten Datei abgelegt sind.
Nichtblattseiten: nur Suchschlüssel, die als Separatoren zum
schnellen Auffinden der richtigen Blattseite dienen
Wie funktionieren Einfüge- und Löschoperationen bei einer statische Baumstruktur?
nur in den Blattseiten durchgeführt, nicht bei Nichtblattseiten
setzen das Suchen und Finden der richtigen Blattseite voraus
soll eingefügt werden aber Blattseite voll:
zusätzliche Seite (Überlaufseite) die den Eintrag aufnimmt
setzen das Suchen und Finden der richtigen Blattseite voraus
soll eingefügt werden aber Blattseite voll:
zusätzliche Seite (Überlaufseite) die den Eintrag aufnimmt
Was ist das Problem bei zu vielen Überlaufseiten und wie wird es gelöst?
Suchzeit entscheidend verschlechtert, da auch die Überlaufseiten durchsucht werden müssen
Lösung:
bei der Erzeugung der statischen Baumstruktur wird die Seitenauslastung auf ungefähr 80% reduziert
Lösung:
bei der Erzeugung der statischen Baumstruktur wird die Seitenauslastung auf ungefähr 80% reduziert
Nachteil der index-sequentiellen Methode ist, dass...
Performance drastisch sinkt, wenn die Datei wächst und gleichzeitig lange Ketten
von Überlaufseiten entstehen
von Überlaufseiten entstehen
Wichtiges zum B-Baum
spezielle Variante eines Vielweg Suchbaums
Jeder Knoten mit Ausnahme der Wurzel besitzt zwischen m und 2m Suchschlüssel.
Alle Pfade von der Wurzel zu einem Blatt sind gleich lang -> balanciert
Jeder innere Knoten mit n Suchschlüsseln hat genau n+1 Söhne
Jeder Knoten mit Ausnahme der Wurzel besitzt zwischen m und 2m Suchschlüssel.
Alle Pfade von der Wurzel zu einem Blatt sind gleich lang -> balanciert
Jeder innere Knoten mit n Suchschlüsseln hat genau n+1 Söhne
Wichtiges zu B+Bäume
Indexeinträge k* ausschließlich in den Blattknoten enthalten
die Nichtblattknoten enthalten nur Suchschlüssel k und Verweise auf die Wurzeln von Teilbäumen.
Blattseiten in doppelt verketteten Liste-> kann in beiden Richtungen durchlaufen werden ->Bereichsanfragen
Jeder innerer Knoten mit n Suchschlüsseln hat genau n + 1 Söhne.
Wichtiges zu B*-Bäume
Füllungsgrad eines jeden Knotens muss nicht zwischen 50% und 100% liegt.
Benutzerdefinierter Füllungsgrad möglich
Benutzerdefinierter Füllungsgrad möglich
Nachteil von baumbasierten Indexstrukturen
bei jedem Zugriff muss ein bestimmter Pfad durchlaufen werden
Was ist das Hash-Verfahren
Verwendung einer Hash-Funktion, die den Wert eines Suchschlüssels in einen Bereich von Behälternummern
abbildet, um diejenige Seite zu finden, die den zugehörigen Indexeintrag enthält
abbildet, um diejenige Seite zu finden, die den zugehörigen Indexeintrag enthält
Welche verschiedenen Hash-Verfahren gibt es?
statisch: Problem: lange Ketten von Überlaufseiten, die die Performance negativ beeinflussen
dynamisch: flexible Anpassung der Anzahl der Überlaufseiten an den jeweiligen Speicherplatzbedarf
erweiterbare: benutzt Verzeichnisstruktur, um Einfügen und Löschen effizient ohne irgendwelche Überlaufseiten zu unterstützen
linear: intelligente Strategie, um neue Behälter zu erzeugen. Einfügen und Löschen werden effizient ohne Einsatz einer Verzeichnisstruktur unterstützt
dynamisch: flexible Anpassung der Anzahl der Überlaufseiten an den jeweiligen Speicherplatzbedarf
erweiterbare: benutzt Verzeichnisstruktur, um Einfügen und Löschen effizient ohne irgendwelche Überlaufseiten zu unterstützen
linear: intelligente Strategie, um neue Behälter zu erzeugen. Einfügen und Löschen werden effizient ohne Einsatz einer Verzeichnisstruktur unterstützt
Vorteile Nachteile Hash-basierte Indexstruktur
N: Bereichssuchen nicht unterstützt
N: kommerzielle Datenbanksysteme unterstützen nur baumbasierte Indexe.
->hash-basierte Techniken bei der erweisen sich bei Implementierung relationaler Operationen (wie z.B. Joins) als sehr nützlich
N: kommerzielle Datenbanksysteme unterstützen nur baumbasierte Indexe.
->hash-basierte Techniken bei der erweisen sich bei Implementierung relationaler Operationen (wie z.B. Joins) als sehr nützlich
Wie viele Zugriffe benötigt das Hashverfahren für Tranksaktionen?
n/2rN Zugriffe für eine erfolgreiche Suche
n/rN+1 Zugriffe für ein erfolgreiches Einfügen mit Rückschreiben der Seite
n/2rN +1 Zugriffe für das Löschen eines existierenden Indexeintrags oder das Ändern eines existierenden Indexeintrags sowie das Zurückschreiben der Seite
n/rN Zugriffe für eine erfolglose Suche oder das Überprüfen, dass eine Indexeintrag nicht in der Datei vorhanden ist.
n/rN+1 Zugriffe für ein erfolgreiches Einfügen mit Rückschreiben der Seite
n/2rN +1 Zugriffe für das Löschen eines existierenden Indexeintrags oder das Ändern eines existierenden Indexeintrags sowie das Zurückschreiben der Seite
n/rN Zugriffe für eine erfolglose Suche oder das Überprüfen, dass eine Indexeintrag nicht in der Datei vorhanden ist.
Nachteil des statischen Hashings und Lösung
N:Anzahl der Behälter und die Hash-Funktion fest vorgegeben und schwerlich veränderbar
->Rehashing, benötigt Zeit in der keine Zugriffe möglich sind
->Rehashing, benötigt Zeit in der keine Zugriffe möglich sind
Kartensatzinfo:
Autor: Der Kurssprecher
Oberthema: Datenbanken
Thema: Datenbanktechnik
Veröffentlicht: 14.04.2016
Schlagwörter Karten:
Alle Karten (92)
keine Schlagwörter
