CoboCards App FAQ & Wishes Feedback
Language: English Language
Sign up for free  Login

Get these flashcards, study & pass exams. For free! Even on iPhone/Android!

Enter your e-mail address and import flashcard set for free.  
Go!
All main topics / Datenbanken / Datenbanktechnik

DB-Technik (92 Cards)

Say thanks
1
Cardlink
0
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.




2
Cardlink
0
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
3
Cardlink
0
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
4
Cardlink
0
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?
(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
5
Cardlink
0
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?
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)
6
Cardlink
0
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)
7
Cardlink
0
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 ?? 
8
Cardlink
0
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
9
Cardlink
0
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:
10
Cardlink
0
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
11
Cardlink
0
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.
12
Cardlink
0
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
13
Cardlink
0
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
14
Cardlink
0
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.
15
Cardlink
0
Unter welchen Voraussetzungen kann auf ein After-Image verzichtet werden?
Nie! Sonst Datenverluste bei Plattenausfall.
16
Cardlink
0
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.
17
Cardlink
0
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).
18
Cardlink
0
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)
19
Cardlink
0
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.
20
Cardlink
0
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.
21
Cardlink
0
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.
22
Cardlink
0
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.
23
Cardlink
0
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.
24
Cardlink
0
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.
25
Cardlink
0
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.
26
Cardlink
0
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
27
Cardlink
0
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
28
Cardlink
0
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
29
Cardlink
0
Erklären Sie Transitive Abhängigkeit
Transitive Abhängigkeit: (indirekte Abhängigkeit vom PS) Verletzung der 3NF durch Abhängigkeit zwischen Nichtschlüsselattribut
30
Cardlink
0
Erklären Sie After Image
After Image: Speicher(Abbild) Zustand im permanenten Speicher (Logdatei ungleich DB!) nach erfolgreicher Beendigung der TA ( commit).
31
Cardlink
0
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!).
32
Cardlink
0
Erklären Sie globales Attribut
Globales Attribut: Attribut, dass in mind. Einer Tabelle Schlüsselattribut ist.
33
Cardlink
0
Erklären Sie Invertierte Liste
Invertierte Listen: Sekundärer Zugriffspfad bei den die Zugriffsstruktur getrennt von den eigentlichen Daten gespeichert wird.
34
Cardlink
0
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
35
Cardlink
0
Erkläre Primärorganisation indexsequentieller Art
Sätze werden gemäß PS sortiert gespeichert
für PS wird ein Index aufgebaut



36
Cardlink
0
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
37
Cardlink
0
Erkläre Primärorganisation nach Hash-Verfahren
Speicheradresse wird durch Umrechnung aus dem PS errechnet
(Hash-Algo)
38
Cardlink
0
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
39
Cardlink
0
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
40
Cardlink
0
Vorteil von Clustering
Clustering, ist die Fähigkeit, die ausgefallene Serverhardware und ausgefallene Software wiederherzustellen.
41
Cardlink
0
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
42
Cardlink
0
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
43
Cardlink
0
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
44
Cardlink
0
Wann invertierte Liste
Lohnt sich bei hoher Selektivität (qualifizierte Tupel < 10% der DB)

-> sonst sequentieller Durchlauf
45
Cardlink
0
Wann Bitliste?
geringe Selektivität
nur bei Gleichheits-Abfragen
46
Cardlink
0
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
47
Cardlink
0
Sequentieller Zugriff:
Sequentieller (sortierter) Zugriff auf eine indizierte Datei über einen
Suchschlüssel wie z.B. auf eine Angestelltendatei mit Hilfe des Namens.
48
Cardlink
0
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.
49
Cardlink
0
Bereichszugriff:
Bereichsanfragen (match queries) finden dann z.B. alle Angestellten mit
Nummern zwischen 10815 und 14711.
50
Cardlink
0
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.
51
Cardlink
0
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
52
Cardlink
0
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
53
Cardlink
0
Was ist ein dünner Index?
Ein dünner Index enthält einen Eintrag für
jede Seite von Datensätzen der indizierten Datei.
54
Cardlink
0
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.
55
Cardlink
0
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
56
Cardlink
0
Was ist ein Primärindex?
Ein Index, der über einen Primärschlüssel definiert und geordnet ist, wird
Primärindex genannt.
57
Cardlink
0
Was ist ein Sekundärindex?
Ein Index, der für einen Sekundärschlüssel angelegt wird, wird
als Sekundärindex bezeichnet.
58
Cardlink
0
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)
59
Cardlink
0
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.
60
Cardlink
0
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)
61
Cardlink
0
Was ist Clusterung?
Das Bestreben, logisch zusammengehörige
Datensätze physisch benachbart auf Seiten abzuspeichern
62
Cardlink
0
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
63
Cardlink
0
Was ist das Problem bei geclusterten Indexen?
extrem hoher Aufwand für das
Verschieben der Datensätze beim Einfügen und Löschen
64
Cardlink
0
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).
65
Cardlink
0
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
66
Cardlink
0
Was ist ein zusammengesetzter Suchschlüssel
Ein Suchschlüssel für einen Index der mehrere Felder enthält
67
Cardlink
0
Was ist ein einfachen Suchschlüsseln
besteht nur aus einem Feld
68
Cardlink
0
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
69
Cardlink
0
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
70
Cardlink
0
Eindimensionale Indexstrukturen:
Auf der Menge der Suchschlüsselwerte wird eine lineare Ordnung definiert, bezüglich der die Indexeinträge sortiert sind.
71
Cardlink
0
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.
72
Cardlink
0
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.
73
Cardlink
0
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.
74
Cardlink
0
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.
75
Cardlink
0
Wie sucht man bei einem einstufigen
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
76
Cardlink
0
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
77
Cardlink
0
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.
78
Cardlink
0
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
79
Cardlink
0
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
80
Cardlink
0
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
81
Cardlink
0
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
82
Cardlink
0
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
83
Cardlink
0
Nachteil der index-sequentiellen Methode ist, dass...
Performance drastisch sinkt, wenn die Datei wächst und gleichzeitig lange Ketten
von Überlaufseiten entstehen
84
Cardlink
0
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
85
Cardlink
0
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.
86
Cardlink
0
Wichtiges zu B*-Bäume
Füllungsgrad eines jeden Knotens muss nicht zwischen 50% und 100% liegt.

Benutzerdefinierter Füllungsgrad möglich
87
Cardlink
0
Nachteil von baumbasierten Indexstrukturen
bei jedem Zugriff muss ein bestimmter Pfad durchlaufen werden
88
Cardlink
0
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
89
Cardlink
0
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

90
Cardlink
0
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
91
Cardlink
0
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.
92
Cardlink
0
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

Flashcard set info:
Author: Der Kurssprecher
Main topic: Datenbanken
Topic: Datenbanktechnik
Published: 14.04.2016
 
Card tags:
All cards (92)
no tags
Report abuse

Cancel
Email

Password

Login    

Forgot password?
Deutsch  English