Dateiorganisation Flashcards
Primärspeicher
- Cache, Ram
- teuerer (als Sek.)
- schneller (als sek)
- flüchtig (nicht-persistent)
- Zugriffsgranularität: fein, Zugriff auf Byteebene
Sekundärspeicher
- Festplatte, Magnetbänder
- günstig ((er) als Prim.)
- langsam ((er) als Prim)
- persistent
- Zugriff auf Blockebene (oft 512 Byte pro Block)
Mittlere Zugriffszeit
- Seek time => Zugriffsarm (Schreib-Lese-Kopf) positionieren
- Latenzzeit (latency) => Warten bis richtiger Sektor Kopf passiert (Umdrehungszeit)
- Transferzeit => Übertragungszeit von Platte in Hauptspeicher
Record Defintion
Sammlung von Feldern die in einer Beziehung zueinander stehen (logischer Datensatz)
Record Speicherverfahren
Fixlängenspeicherung => für jedes Feld fixe Anzahl Bytes
Speicherung variabler Längen (Trennzeichen) ==> Zwischen var Feldern spezielles Trennzeichen - weniger Speicherplatz verbraucht, langsamerer Zugriff als Fixlänge
Speicherung var Längen (Key-Value-Paare) ==> Key = Value, Nicht gesetzte Felder nicht gepeichert (Sparsam)
Bsp Name=Smith, John/usw.
Auslesen schwieriger, nicht angegegebene Felder werden nicht mehr explizit gespeichert
Hash-Kollision
Bei einer Hash Kollision ergibt die Hash Funktion für 2 Schlüsselwerte den gleichen Wert, womit beide Schlüsselwerte am selben Speicherplatz gespeichert werden müssten.
Hash Kollisionen lassen sich nicht vermeiden, da die Schlüsselmenge in den meisten Fällen größer ist als die Menge an Speicherplätzen (Wertemenge).
Warum wird sequentieller Zugriff im Vergleich zu Wahlfreiem Zugriff immer Schneller verhältnismäßig immer schneller?
Transferraten wachsen verhältnismäßig schneller als Rotations und Positionierungszeiten.
Was ist Heap, Sequenziele, und Hash-Organisation?
Heap Organisation -unsortierte Speicherung von internen Tuplen
Sequenzielle Organisation - sortierte Speicherung von internen Tupeln
Hash Organisation - gestreute Speicherung von internen Tupeln
In einer unspanned Heap-Datei wird der i-te fixe Record in den Festplattenblock (i/bfr) an der Position (i mod bfr) gespeichert. Erläutern Sie, warum dieses Wissen im operativen Datenbankbetrieb
faktisch nicht vorteilhaft ausgenutzt werden kann
Der Zugriff auf den i-ten Record in einer unsortierten Datei beschleunigt lediglich das Suchen nach dem i-ten Eintrag der Datei, nicht aber die Suche anhand
konkreter Felder in den Records
Heap vs. sotierte Datei? Kategorien (Suchoperationen, Einfügen löschen, sotierte Ausgabe)
Suche: Aufwändig da alle Records gelesen werden müssen Durschnitt n/2. Binäre Suche effizienter
Einfügen: Einfach weil einfach am ende eingefügt werden kann. Aufwändig da Dateien ggf. umorganisiert werden müssen
Löschen: Aufwändig da gesucht werden muss und Reorganisation zur Lücke gemacht werden muss. Nur günstiger wenn Sotierfeld ansonsten genauso aufwendig
Sotierte Ausgabe: Sehr schwer, einfach weil bereits sotiert vorliegen
REihenfolge der Blockspeicherung 3. Varianten Contiguous Allocation Linked Allocation Clustered Allocation
1.Contiguous Allocation
Alle Blöcke werden konsekutiv hintereinander geschrieben
-Hohe Lesegeschwindigkeit
-Teure Einfügeoperationen
2.Linked Allocation
Am Ende jedes Blocks befindet sich ein Pointer auf den nächsten Block
-Teure Leseoperationen
-Einfügeoperationen problemlos realisierbar
3.Clustered Allocation
Konsekutive Block-Cluster werden untereinander verlinkt Kompromisslösung
Unterschied B und B+ Baum
Daten sind nur in Blätter daher auch als hohler Baum bezeichnet (B+).
Was sollte bei einem B baum nicht getan werden und warum?
Sotierte Zahlen sollten nicht in ein B-Baum eingefügt werden da dies zu einer schlechten Auslastung des Baums führt.
Ordnung p=5 wie viele paare können nach unten abgehen
5 Paare können abgehen, nur 4 Kästchen.
Was ist ein Index?
Ein Index ist ein sekundärer Zugriffspfad auf eine Datei, der parallel zur primäaren Dateiorganisation existiert. Er erlaubt einen direkten Zugriff auf die Daten innerhalb der Datei
Vorteile eines Indexes
Effiziente Suchverfahren können angewandt werden. Sequenzielle Suche entfällt. (Weniger Blockzugriff um Record zu finden)
Sparse und Dense Index Unterschied
Sparse Index zeigt nur auf den ersten Eintrag im Block d. h es können WErte lücken entstehen. Daher ist eine Sotierung inerhalb des Blocks entscheidend. (Primary Index)
Wie ist ein Primary Index aufgebaut?
Wird über einem eindeutigen Attribut gebildet, nach dem die Datendatei physisch organisiert ist.
Jeder Record besteht aus zwei Feldern:
Das erste Feld ist vom selben Datentyp wie das Sortierfeld der Datendatei. (Bsp. Hans Mueller)
Das zweite Feld ist ein Pointer auf einen Disk Block, in dem der Record physisch liegt.
Was für Aussagen können über den Secondary Index getroffen werden ?
Existieren für den jeweiligen Indexeintrag nur ein WErt in der Datentabelle handelt es sich um einen Dense Index.
Ist sotiert. Jeder Index ist einem Record zu gewisssen. Index kann eindeutig sein muss aber nicht zwangsläufig.
Was ist ein sogenannter clustered Index und was unterscheidet diesen?
Der Clustered Index besitzt somit die gleiche Struktur wie der Primary Index Aber: An Stelle eines Eintrages pro Disk Block enthäalt der Clustered Index nun einen Eintrag für jeden unterschiedlichen Wert des Sortierfeldes! Auch der Clustered Index ist ein sparse Index.
Wie können Hash-Kollisionen vermieden werden?
1.Lineares Sondieren
Wert rechts neben in Tabelle in freies Feld schreiben
2.Anhängen einer verketteten Liste an die Hash-Position (Overflow-Listen)
Werte unter den bereits belegten Wertschreiben -> Lücken im Wertebereich
-3.Mehrfaches Hashing, d.h. Anwendung weiterer Hash-Funktionen
Was ist mit gobaler Tiefe gemeint ? Binär System Tiefe 1: 0 und 1 Tiefe 2 01, 10
Man schaut sich die 1,2 oder 3 stellen des Hashwerts an und ordnet die Namen dann in die jeweiligen Blätter ein.
Warum sollte bei der Hash-Map nicht die binäre Schreibweise gewählt werden.
Da die Nummern sequentiell vergeben werden und erst ab 2125 beginnen, unterscheiden sie sich in der Bmardarstellung nur in den letzten Bits wesentlich. Es würde also ein unnötig großes Verzeichnis
angelegt, wenn man die Binardarstellung als Hashwert verwendet hätte
Um dies zu verhindern, nimmt man die inverse Darstellung. In der Praxis sollte man die Schlüsselwerte noch starker - z B durch Faltung -
„durcheinander wirbeln“
was macht ein Equijoin
ER übernimmt nur die Zeilen wo es in beiden Tabellen einen Match gibt
Was macht kartesisches Produkt
_Alle Zeilen der beiden Tabellen werden miteinander mal genommen und ausgegeben. X-Symbol
Erstellen sie ein semi join
Gleiche wie ein equi join nur das nur die werte der eigentlichen Tabelle ausgegeben werden die theoretisch einen Match mit der gejointen Tabelle hätten
Was ist ein natural join
- als Symbol
Erster WErt Tabelle 1 wird mit 1. Wert Tabelle 2 gejoint. Ausgabe nur der die gematcht wurden.
Was ist erweitertes Hashing
Es wird ein globales Verzeichnis von Bucket-Adressen geführt. Lokale Tiefe d bestimmt die anzahl der höherwertigen Bits.
Kann bei Bedarf wachsen oder schrumpfen (dynamisch)
Selektivität?
Gibt die Häufigkeit eines Datensatztes unter einer Selektivitätsbedingung im Verhältnis zur gesammten Anzahl an. Bsp.: wenn 100 Datensätze und 10 Name Mueller dann ist die Selektivität 10/100=0,1
Klammerschreibeweise SQL-Gleichung
Anzeigen -> PI [*] Wo (Sigma[Bedingung] JOin (EQ[Bedingung] Table (tabellenname, tabellename2)))) *natural X kartesisches Produkt ->kein join
Operatorbaum
PI an erster Stelle
dann Selektivität
dann Join
dann Tabellen
Opimiert erst join dann Selektivität auch links recht aufgeteilt dann tabaellen
Tabellen teilen sich auf links und rechts
Wann macht statisches Hashing keinen Sinn ?
Feste Anzahl an Buckets für M Datensätze. Wenn wenige Datensätze vlerwendet werden. Wird viel Speicherplatz verschwendet.
Bei vielen Datensätzen wird es durch zunehmend Hash-kollisionne unperformanter. Performance wie verkettete Liste
Schedules (Korrektheitsannahme)
Annahme wenn jede Transakion isoliert ausgeführt wird werden die Daten konsisten hinterlasssen.
Alle Transaktionen seriell ausführen
Problem-> Durch parralles ausführen von Transaktionen wird der Cache besser ausgenutzt -> Effiziensvorteile (Ausnutzung des Caches über langen Zeitraum Long transactions)
Korrekte parallele Pläne finden
Korrekt bedeutet dass diese serialisierbar sind
Schedule
„Ablaufplan“ für Transaktionen, bestehend aus Abfolge von Transaktionsoperatione
Serieller Schedule
Schedule in dem Transaktionen hintereinander ausgeführt werden
Serialisierbarer Schedule
Dessen Effekt der gleiche ist wie der eines seriell ausgeführten Schedules
Lost Update Problem
T1 read(a) T2 read(a) T1 write(a) T2 Write(a
T2 schreibt auf den gelesenen a wert der zuvor durch T1 aktualisiert worden ist, allerdings hat T2 noch den Alten wert. Daher gibt es am ende den falschen WErt in der DB.
Operatorbäume mit kartesischem Produkt und jeweils tausendne von Datensätzen
ERst die Selektion weil sonst noch größere Anzahl an Tupeln die durchsucht werden muss.
Wenn allerdings nur aus einem Record dann kann es mit einem Blockzugriff in Hauptspeicher dann nicht erst SElektieren
Was sollte für 2 Pl Protokoll erfüllt sein ?
Der Schedule widerspricht dem folgenden Prinzip: „no lock after unlock“ Wenn T1 ein read Lock setzen will, muss T2 nach der write Operation ein Unlock ausführen. Der notwendige read-Lock von T2 im dritten Schedule Schritt würde dann dem oben genannten
Prinzip widersprechen
Alle Locks vor Unlock setzten
Koservativ-> alle Lock Operationen vor ausführung der Transaktionen -nicht immer können alle write und read Operationen vor Ausführung bestimmt werden
Lock
read share
write exclusive
Was ist ein Deadlock
wenn jedes Elemnt aus einer Menge von zwei oder mehr Transaktion auf das Selbe von der vorigen Transaktion gesperrte Element zugreiffen will
Was ist eine Scan-Operation
Halloween Problem
Projektion und Selektion
Full table and index Scan z.b bei Reihenfolge “oder by”
Geht alle Tupeln der Tabelle ab bzw indizes
Wann sind spaltenorientierte Systeme Besser
- Beim Bilden von Aggregaten von nur einer Zeile z.B GEhalt oder Umsatz
- Wenn eine Spalte mit genau einem Wert aktualiert werden muss z.b:Gehalt mal 1.3
Spaltendaten haben gleichen Datentyp
-> Datenkompression Verringerung des Speicherplatzes
OLap
Wann ist zeilenorientierung bEsser
Wenn auf mehrere Attribute einer relation zugegriffen werden muss
Wenn beim hinzufügen einer Tupel alle WErte gleichzeitig eingetragen werden.
OltP
Datenbankobjekte
Bekannte Objekte
records Attribute blocks usw.
Transaktion Begriff
Beschreibt einen logischen Verarbeitungsblock, der aus einer Sequenz von Einzelbefehlen besteht
Ganz oder Garnicht ausgeführt.
ACid
Atomar
Consistency
Isolation
Durabiltiy
PL2 - Phasen
Grow aufgebaut nicht abgebaut
Shrink keinen neuen und abgebaut
Conservative locked alle aufeinmal
Strikt: locked alle verfügbaren und gibt erst wieder frei wenn Transaktion durchgeführt (commited status) oder abgebrochen
Recovery Manager, wann?
Überwacht den Statut einer Transaktion und prüft ob die DAten auf Platte geschrieben werden können. Bei Fehlern macht er die Transaktion rückgängig.
z. B Transaktionsfehler (division 0)
System-, Rechnerabsturz
Physikalische Fehler (Naturkatasrophe->Stromausfall)
