FSI Informatik/pruefungen/bachelor/idb/braindump-2016-02-19

Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » idb » IDB Braindump 19.Februar 2014 (Übersicht)
Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
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. Cross und Sel zusammenfassen zu  JOIN
  - 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. 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. 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.Transaktionsstart
  - 2.Kontonummer über Benutzereingabe abfragen
  - 3.Über Konten scannen und Kontostand bilden
  - 4.Zielkonto und Betrag über Benutzereingabe abfragen
  - 5.Abbruch, falls Kontostand zu gering
  - 6.Geld überweisen
  - 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.