Implementierung von Datenbanksystemen
Wann ist eine Anwendung datenunabhängig?
Speichern und Wiedergewinnen von persistenten Daten ohne Kenntnis der Details der Speicherung.
Angeben,ob Behauptungen richtig oder falsch mit Begründung:
Am besten das ding Auswendig lernen - siehe Vorlesung 9 - Folien 3 und 4, bzw. 15 - 3 und 4
Welche Hilfsstrukturen braucht man für indirekte Seitenzuordnung und was wird darin gespeichert?
Array mit Blocknummer zu jeder Seite, Seitentabelle (für jede Seite ein Eintrag mit aktueller Blockzuordnung), Bitmap für Dateien (gibt für jeden Block an, ob er Seite enthält)
Welche Seite wird bei LFU/LRU/ FIFO verdrängt?
LFU - auf die am wenigsten häufig zugegriffen wurde
LRU - auf die am längsten nichtmehr zugegriffen wurde (clock macht eigentlich das gleiche)
FIFO - die als erster reingekommen ist.
Welchen Nachteil hat LFU bei Direktzugriff?
Wenn eine Seite mal viele Zugriffe hatte, aber später nicht mehr gebraucht wird, dann bleibt sie im Speicher, obwohl sie nicht (mehr) gebraucht wird
Wie muss eine Seitenersetzungsstrategie sein, damit sie Belady-optimal ist? Was muss man dafür wissen?
Es wird die Seite entfernt, auf die am längsten in der Zukunft nicht zugegriffen wird.
Was muss man dafür wissen? : Welche Seite wird am wahrscheinlichsten in der Zukunft nicht referenziert. (eigentlich eine redundante Aussage ….) ist belady optimal nicht sogar der Anspruch, dass man genau weiß welche Seite in Zukunft nicht mehr refernziert wird? Eigentlich schon, Belady-Optimalität ist in der Realität nicht gegeben. Aber vermutlich wird das durch das wort „wahrscheinlich“ klar, deswegen stimmts eigentlich schon.
Mehrere Key-Value-Paare in leeren B*-Baum einfügen, Baum nach jeder Strukturänderung neuzeichnen.
Nachbarknoten sollten bei Überlauf nicht gemischt werden. k = 1 für Blätter und k* = 2 für innere Knoten.
Einzufügende Tupel: (1,i), (2,d), (3,b), (5,e), (6,b), (4,u)
Keine Ahnung, ob das stimmt… Die Aussage nicht mischen hat etwas verwirrt
https://pl.vc/4ppua - Stimmt, aber du hast vergessen die „2“ mit Daten in das Blatt zu schreiben. Ups, danke!
LinearesHashing durchführen mit Split immer dann, wenn ein Überlauf auftritt. Mit Überlaufbuckets, Bucketgröße 2, Hashfunktion f(x) = x mod (2 · 2j), Beginn mit zwei Buckets(j = 0). (Verschiedene Zustände der Hashmap geben
Bitmap-Index nach Attribut „Geschlecht“ angeben für:
PNr Name Geschlecht 5 Kurt m 21 Eloise w 42 Manni m 2 Carl m 30 Albert m 88 Ulf m 59 Manuela w 100 Abelad m'
Bitmap Index müsste irgendwie so aussehen:
M F 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 Spielt es dabei eine Rolle, wie sortiert ist? Wäre PNr der Primärschlüssel, müsste man dann nicht nach diesem erst sortieren?
Speicherung eines solchen Satzes schematisch darstellen bei Feldern variabler Länge mit Pointern: Personalnummer Fest Vorname Variabel Nachname Variabel Abteilung Fest
Gesamtlänge Länge FesterTeil Personalnummer Pointer Vorname (Zeigt auf Länge Vorname) Pointer Nachname (Zeigt auf Länge Nachname) Abteilung Länge Vorname Vorname Länge Nachname Nachname
Grundsätzlicher Aufbau von C-Store und Unterschied zur üblichen Speicherung in relationalen Datenbanken. - Data-Warehouse, analytische Auswertungen - Join + Einfügen schwierig - Mehrere Spalten nach einem Attribut sortiert - Tuple Mover: läuft wenn wenig los (Nachts)langsamer Hintergrundprozess - Input: normales SQL - Keine Distinct bei verbindungen - Normalerweise aufsteigend sortiert - Segmentierung Mölgich sid > 0 (horizontale Partitionierung) - Tupel nur Spaltenweise gespeichert ⇒: o Jedes Attribut mind. Einen Platz o Speicherschlüssel (auf dem Verbund Indizesbasieren) ergibt sich aus phys. Position o Rekonstruktion von Tupel über Verbundindizes dereinzelnen Projektionen möglich
Tabellebefüllen:
Wenigverschiedene Werte Viele verschiedene Werte
Sortiert Typ 1: B-Baum, Tripel(v,f,n) Typ 3: Delta-Kodierung, B-Baum
Unsortiert Lauflängencodierung mit Bitmaps, Paare (v,b) Unkomprimiert, B-Baum
Wie kann man die Tupel in C-Store wieder zusammensetzen? Rekonstruktion über Verbund-Indizes.
Wie werden Min- / Max-Anfragen in C-Store gemacht? Wann und warum ist das effizient? Nur über einen Satz gehenWenn sortiert, da Anfang Satz = min, Ende Satz = max.
Unoptimierten Anfragebaum erstellen für diese Anfrage:
SELECT
ST.x, R.z
FROM
R, (
SELECT (S.a, T.e)
FROM S JOIN T ON S.d = T.e
WHERE S.b > T.f
) as ST
WHERE
ST.x = R.x AND (R.a = 42 OR R.a = 21);
https://pl.vc/orf7 Fehlt da nicht eine Projektion für SELECT (S.a, T.e) bei einer unoptimierten Anfrage - jop, thx!
Zwei Möglichkeiten zur Optimierung des obigen Baums nennen.
Unterschied logischer Operator zu Planoperator?
Relationale, logische Operatoren = interne Darstellung der Anfrage, erlaubt Reihenfolge festzulegen (prozedural)
Planoperatoren = Ausführbares Unterprogramm – konkrete Umsetzung der logischen Operatoren
Wie funktioniert Sort-Merge-Join ohne Index? Ausgehend von zwei Relationen:
Sortiere beide der Tabellen nach Verbund-Attribut und Schritthaltens des Scans in beiden TabellenReisverschlussverfahren ähnlich merge sort / priority queue
Laufzeitverhaltendes Sort-Merge-Verbunds ohne Index in O-Notation.
O(n*log(n)) für die jeweiligen Sortierungen (abhängig vom Algorithmus). + O(n) für merge fällt anhand der O-Notationsregeln weg.
Wiewirkt sich die Grenztrefferrate auf die Wahl der Planoperatoren aus? Warum?
Wenn über 5% lohnt sich eine Index-Scan nicht
Kleine Trefferate = hohe Selektivität
Unterschiedzwischen logischer und physischer Konsistenz?
Logische Konsistenz = physische Konsistenz + Shemata und Konstraints erfüllt
Physische Konsistenz = Speicherstrukturen sind konsistent, TID’s richtig
Die drei Schritte bei Recovery angeben. Wie laufen sie ab und welche Operationen finden jeweils statt?
Analyselauf: Bestimmung Gewinner/Verlierer Transaktionen
Undo-Lauf: Rücksetzen Verlierer
Redo-Lauf: Vorwärtslesen Log – Gewinner wiederholen
Warum muss eine Transaktion atomar sein? Damit Daten Integer Konsistente Zustände gewährleistet
Abhängigkeitsgraphzeichnen zu folgendem Ablauf:
r2(A), r2(B), r3(B), w3(A), r1(A),w1(A), c1, w2(C), c2, r3(C), w3(A), c3
Ist der Ablauf serialisierbar? Nein, T1 und T3 bilden über A einen Zyklus.
Wasist das Problem mit dieser Transaktion? Problem: es wird in der Transaktion nach einer Benutzereingabe gefragt ⇒ kann beliebig lange dauer ⇒ das ganze System wir deswegen aufgehalten
Wie könnte man das Problem von oben lösen? Benutzereingaben vor Transaktionsstart abfragen
Sinn und Funktionsweise von Serialisierung mittels Sperren erklären.
Relation Person: (Vorname, Nachname, Geburtsjahr) Programm schreiben, dass alle Leute auf der Konsole ausgibt, die vor 1970 geboren wurden.
Die genauen Bezeichner der API waren ausdrücklich nicht gefordert; es ging eherdarum, die richtigen Konzepte der Schnittstelle zu benutzen. Folgendes Code-Skelett war vorgegeben:
public static void main ( String [] args ){ try { Connection con = // Verbindungsaufbau gegeben Statement stat = con.createStatement(); ResultSet resSet = stat.executeQuery("SELECT Vorname, Nachname FROM Person WHERE Geburtsjahr < 1970"); while(resSet.next()) { System.out.println(rs.getString("Vorname") + " " + rs.getString("Nachname")); } } catch ( Exception e) { //Fehlerbehandlung gegeben } }
Kein schöner Stil, zu viel Schreibarbeit und * statt direkte Projektionen etwas unperformant. stimmt - habs weggenommen
Vorteile von Prepared statements gegenüber Abfrage zur Laufzeit nennen.
Werden bereits zur Übersetzungszeit geprüft , analysiert, optimiert und in Zwischencode überführt ⇒Bessere Performance zur Laufzeit
Vorteil von Stored procedures zu Prepared statements? Muss nur ein mal erstellt werden. Modularisiereung. Da die Module in der DB sind, können auch andere Programme diese verwenden.
Stored procedures sind nochmal performanter als prepared statements, da diese vom DBVS verwaltet werden und vom Programm nur aufgerufen werden müssen. Analyse und Optimierung muss dann nurnoch einmalig durchgeführt werden.