Prüfungsprotokoll Praxis - Seidl Datenbanken, Indexstrukturen, Betriebssysteme

Matthias Hensler

22. April 2005

Beisitzer war Jost Enderle. Professor Seidl fragte ob ich mit der Reihenfolge Datenbanken, Indexstrukturen,

Betriebssysteme einverstanden wäre, was ich bejahte.

1 Datenbanken - 15 Minuten

Grundlage: Datenbanksysteme - Eine Einführung nach Kemper/Eickler, 4. Auflage

Vorbereitung: Buch und Folien aus der Vorlesung von Jarke

• Was ist eine Transaktion? (atomare Ausführung mehrerer Operationen)

• ACID? (Atomarität, Konsistenz, Isolation, Dauerhaftigkeit)

• Wenn man ein Datenbanksystem im Laden kauft, was liegt dem für ein Modell zugrunde? (relationales Modell, objektorientiertes Modell, erweitertes relationale Modell, deduktive Datenbanken, sowie die alten satzorientierten Datenbanken)

• Was ist bei der objektorientierten Datenbank neu? (Vererbung, Methoden und Funktionen)

• Wie können dort Tupel identifiziert werden? (Anhand eines systemweiten, eindeutigen Objektidentifier)

• Wie ist das beim relationalen Modell? (Ein Primärschlüssel je Relation)

• Wie sieht eine Abfrage in SQL aus? (SELECT ... FROM ... WHERE ...)

• Auf welcher Grundlage basiert SQL? (relationale Algebra (prozedural), relationales Kalkül (deklarativ))

• Verknüpfung, Natural Join zweier Relationen R(A,B) und S(B,C) in Domainkalkül? ({[A,B,C]|[A,B] ∈ R ∧ [B,C] ∈ S})

• Wofür GROUP BY in SQL? (Gruppierung gleicher Tupel, Aggregation)

2 Indexstrukturen - 15 Minuten

Grundlage: Vorlesung Seidl im Sommersemester 2004

Vorbereitung: Folien der Vorlesung und eigene Übungen

• Braucht man Indexstrukturen? (Hilfreich zur effizienten Suche)

• Was gibt es für Möglichkeiten? (Punktzugriff bei Hashing, hierarchische Struktur wie z.B. der B-Baum)

• Was ist mit Bitmapindexen? (je Attribut ein Index mit 1 falls gesetzt, 0 sonst)

• Wie sieht ein B-Baum aus? (Wurzel und Knoten mit Sortierung, zwischen den Elementen Zeiger auf Nachfolgebaum, kleinere Elemente links, größere rechts, Daten im Baum)

• Kann so ein Baum entarten? (Nein, da von den Blättern her wachsend, höhenbalanciert, jeder Pfad von Wurzel zum Blatt gleichlang)

• Kann man auch geometrische Objekte speichern? (Ja, im R-Baum, dort minimal umgebende Objekte, dabei Überlappungen)

• Können Überlappungen vermieden werden? (Nein, aber man versucht sie zu minimieren um die Suche zu beschleunigen)

• Was würde bei einer Punktanfrage im schlimmsten Fall passieren? (Alle Directoryknoten und Blätter besuchen)

• Wäre das immer noch linear? (Was vom Logarithmus erzählt, aber tatsächlich doch linear in Anzahl der Datensätze)

• Falls man keine Objekte mehr hat, sondern nur noch Abstände? (Metrische Räume, M-Tree, nur noch Abstände zwischen Objekten speichern)

• Pruning in Metrischen Räumen? (|d(q,p)−d(p,o)| ≤ d(q,o) ≤ d(p,q)+d(p,o) für Anfragepunkt q, Referenz p und Objekt o)

• Möglichkeiten nur wenige Dimensionen zu betrachten? (Dimensionsreduktion, Approximationen mit Filtern)

• Eigenschaften der Filter? (Effizienz, Korrektheit, möglichst wenige Objekte genau berechnen müssen)

3 Betriebssysteme - 15 Minuten

Grundlage: Moderne Betriebssysteme nach Tanenbaum, 4. Auflage

Vorbereitung: Buch

• Was ist ein Prozess? (Programm in Ausführung mit zugehörigen Parametern, wie IDs, Speicher)

• Entziehbare Betriebsmittel? (CPU durch Scheduling, Speicher durch Speicherzuteilung, nicht entziehbare Betriebsmittel wie Drucker und CD-Brenner erwähnt)

• Wenn trotzdem mehrere Leute drucken wollen? (Spooler verwenden)

• Was macht man bei der Speicherzuteilung am besten? (Speicher in Seiten aufgeteilt, falls neuer Speicher benötigt eine alte Seite frei machen, dabei am besten die die am längsten nicht mehr benötigt wird. Da Nichtdeterminismus geeignete Heuristiken verwenden)

• Wie entscheidet man welche Seite eingeladen werden soll? (Immer die, die gerade benötigt wird. Precaching möglich, aber in der Praxis nicht wirklich eingesetzt)

• Was sind Dateisysteme aus Benutzersicht? (hierarchische Ordnung zum Ablegen von Dateien, mit Dateinamen. Für das Betriebssystem nur I-Node relevant)

• Was für Flags sind mit einer Datei verknüpft? (Zugriffsrechte, Eigentümer, Modifikationszeit, Größe)

• Was ist ein Problem in Multiprozessorsystemen? (Verwaltung des gemeinsamen Speichers, Verhinderung von Race-Conditions)

• Was muß beim Einsatz von Caches beachtet werden? (Beim Lesezugriff kein Problem, beim Schreiben sicherstellen das eine Aktualisierung an allen gespeicherten Instanzen erfolgt)

• Wie kann man Deadlocks vermeiden? (In der Praxis werden sie nicht vermieden, Einsatz von Spoolern, Erkennung und Behebung, Vermeidung durch Bankersalgorithmus, aber in der Praxis nicht möglich, da benötigte Resourcen unbekannt)

4 Fazit

Dies war meine zweite Prüfung, mit etwa 2,5 Monaten Vorbereitungszeit. Betriebssysteme hatte ich ein dreiviertel Jahr vorher schonmal gelesen. Gelernt haben wir zu dritt, (bzw. Indexstrukturen zu zweit).

Die Atmosphäre war sehr locker und entspannt. Bei Problemen ging Herr Seidl schnell zu einem anderen Thema über.

Probleme hatte ich mit dem Domainkalkül, bei der ich zunächst einen Existenzquantor zuviel verwendet hatte und erst mit der Nase drauf gestoßen werden mußte. Desweiteren hatte ich die Bitmapindexe falsch verstanden was dann natürlich zu einer falschen Antwort führte.

Die Benotung erfolgte mit 1.3 sehr fair. Es sei anzumerken, daß sich Herr Seidl bemüht hat ein wenig von seinem regulären Fragenkatalog abzuweichen, so daß ein ausschließliches lernen nach Prüfungsprotokollen sicher nicht angebracht ist :-)