Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » idb » IDB Braindump 19.Februar 2014   (Übersicht)

Implementierung von Datenbanksystemen

IDB Braindump 19.Februar 2014

1 Wissensfragen 14 Punkte

1.1 Definition 1,5 Punkte

Wann ist eine Anwendung datenunabhängig?

Speichern und Wiedergewinnen von persistenten Daten ohne Kenntnis der Details der Speicherung.

1.2 Richtig oder falsch 7 Punkte

Angeben,ob Behauptungen richtig oder falsch mit Begründung:

  • Datenbank ist nur für Ablage von Daten da, nicht zum Zugriff
  • TID bleibt gleich, solange der Satz existiert
  • Seite im Puffer muss dieselbe Größe haben wie Seite im Betriebssystem
  • Mit dem TID-Konzept kommt es zu höchstens einer Indirektionbeim Zugriff auf nicht fragmentierte Sätze
  • Datenbanksystem kann die Blockgröße frei wählen
  • Hashverbund kann nur gemacht werden, wenn ein Hashindex existiert
  • Primärorganisation einer Relation ist nach dem Primärschlüssel sortiert
  • Falsch
  • Richtig (hier bin ich mir auch nicht sicher, also bei stabilen TID's ist das so, aber TID's müssen ja nicht stabil sein -ich hoffe die Fragen in der Klausur sind genauer gestellt)
  • Richtig (theoretisch müsste das wahrscheinlich nicht sein, aber es macht keinen Sinn die Seite in anderen größen zu verwenden, oder?)ja so stimmt das müsste nicht eine Seite im Puffer so groß wie ein Block sein?
  • Richtig
  • Falsch
  • Falsch
  • Falsch (siehe Vorlesung 5 - Folie 39)

1.3 Schichtenmodell 5,5 Punkte

Am besten das ding Auswendig lernen - siehe Vorlesung 9 - Folien 3 und 4, bzw. 15 - 3 und 4

2Puffer

2.1 Indirekte Seitenzuordnung

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)

2.2 Verdrängung

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.

2.3 Nachteil

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

2.4 Belady-Optimalität

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.

3. B*-Baum 8 Punkte

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!

4 Indizes 10 Punkte

4.1 Lineares Hashing 7 Punkte

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

4.2 Bitmap-Index 3 Punkte

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?

5Speicherung

5.1Variable Felder

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

5.2 C-Store

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

5.3Arten der Komprimierung bei C-Store

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

5.4 Zusammensetzen

Wie kann man die Tupel in C-Store wieder zusammensetzen? Rekonstruktion über Verbund-Indizes.

5.5 Min / Max

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.

6 Anfrageoptimierung

6.1 Anfragebaum

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!

6.2 Optimierung

Zwei Möglichkeiten zur Optimierung des obigen Baums nennen.

  1. 1. Cross und Sel zusammenfassen zu JOIN
  2. 2. Zweiten Teil von der zweiten SEL runterziehen direkt vor R

6.3 Operatoren

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

6.4Sort-Merge-Verbund

Wie funktioniert Sort-Merge-Join ohne Index? Ausgehend von zwei Relationen:

  1. 1. Beide (R, S) werden nach R.VA und S.VA sortiert, dabei Ignorieren von - nicht benötigten Tupeln anhand von P(R.SA) und P(S.SA)
  2. 2. Schritthaltende Scans über R und S mit Durchführung des Verbundes bei R.VA = S.VA (jeweils Scan-Zeiger für R und S)

Sortiere beide der Tabellen nach Verbund-Attribut und Schritthaltens des Scans in beiden TabellenReisverschlussverfahren ähnlich merge sort / priority queue

6.5 Laufzeitverhalten

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.

6.6 Grenztrefferrate

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

7 Recovery 6 Punkte

7.1 Konsistenz 2 Punkte

Unterschiedzwischen logischer und physischer Konsistenz?

Logische Konsistenz = physische Konsistenz + Shemata und Konstraints erfüllt

Physische Konsistenz = Speicherstrukturen sind konsistent, TID’s richtig

7.2Durchführung 4 Punkte

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

8 Transaktionen

8.1 Atomarität

Warum muss eine Transaktion atomar sein? Damit Daten Integer Konsistente Zustände gewährleistet

8.2Abhängikeitsgraph

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

https://pl.vc/1k5bx

Ist der Ablauf serialisierbar? Nein, T1 und T3 bilden über A einen Zyklus.

8.3 Anfrage mit Transaktion

  1. 1.Transaktionsstart
  2. 2.Kontonummer über Benutzereingabe abfragen
  3. 3.Über Konten scannen und Kontostand bilden
  4. 4.Zielkonto und Betrag über Benutzereingabe abfragen
  5. 5.Abbruch, falls Kontostand zu gering
  6. 6.Geld überweisen
  7. 7.Transaktionsende

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

8.4 Problemlösung 1 Punkt

Wie könnte man das Problem von oben lösen? Benutzereingaben vor Transaktionsstart abfragen

8.5 Sperren

Sinn und Funktionsweise von Serialisierung mittels Sperren erklären.

9 Programmzugriff

9.1SQL-Anfrage in Java mit JDBC

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

9.2 Prepared statements

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

9.3 Stored procedures

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.