close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Flyer - Bethesda

EinbettenHerunterladen
Datenbanksysteme WS 2014/2015
Dr. Edgar Korthauer
Daniel Pasler, Henrik Sie
13. Oktober 2014
Übungsblatt 1
Aufgabe 1.1 (4 Punkte)
Gegeben sei eine zu Anfang leere ISAM-Struktur, für die zu jedem Index-Eintrag ein Block für
drei Schlüsselwerte existiert.
a) Fügen Sie die Werte 25, 5, 8, 18, 11, 42, 24 in dieser Reihenfolge in diese ISAM-Struktur ein
und zeichnen Sie das Resultat nach jedem Schritt. Dabei soll folgende Konvention gelten:
Wenn ein Element e in einen bereits vollen Block eingefügt werden müsste, so wird e in
einen neu angelegten Block eingefügt.
Hinweis: Achten Sie darauf, dass die Eigenschaften der ISAM–Struktur erhalten bleiben.
b) Erläutern Sie die Suche nach x1 = 8 und x2 = 42 gemäß ISAM–Verfahren, indem Sie alle
durchzuführenden Vergleiche angeben.
Aufgabe 1.2 (4 Punkte)
a) Geben Sie den 2-3-Baum an (d.h. B-Baum mit d = 2), der durch das Einfügen der Elemente 14, 1, 19, 8, 28, 17, 35, 10, 11, 6, 2 in dieser Reihenfolge in den anfangs leeren 2-3-Baum
entsteht. Geben Sie den resultierenden Baum nach jedem Schritt an.
b) Entfernen Sie die Elemente 1, 8, 2, 6, 14 in dieser Reihenfolge aus dem aus Aufgabenteil a)
resultierenden 2-3-Baum. Geben Sie auch hier den Baum nach jedem Schritt an.
Aufgabe 1.3 (4 Punkte)
Gegeben seien die Wörter w1 = ’knospe’,w2 =’ordnaa’,w3 =’frucht’,w4 =’edgark’,
w5 =’daniel’,w6 =’henrik’. Sie sollen in eine anfangs leere Hash-Struktur eingefügt werden.
a) Fügen Sie w1 , . . . , w6 mittels Open-Hashing in die Hash-Struktur ein. Nutzen Sie dazu die
Hashfunktion h(w) = 6i=1 i2 code(ai ) mod 5, wobei w = a1 . . . a6 und
code(ai ) :=


1



 2




 26
für ai = ’a’
für ai = ’b’
..
.
für ai = ’z’
Jeder Block kann bis zu zwei Schlüsselwörter aufnehmen. Zeichnen Sie die resultierende
Hash-Struktur.
b) Wie viele Festplattenzugriffe werden bei der Suche nach einem beliebigen Schlüssel maximal benötigt? Der Index liegt dabei nicht auf der Festplatte.
Abgabe: Lösungen können jeweils bis zum folgenden Montag um 14:00 Uhr in die entsprechend
gekennzeichneten Kästen (Datenbanksysteme) auf NA 02 (Nähe Rechenzentrum Servicecenter)
eingeworfen werden. Geben Sie bitte auf jedem abgegebenen Zettel Ihren Namen, Ihre Matrikelnummer und Ihre Gruppe an. Auf jedem abgegebenen Aufgabenzettel dürfen bis zu drei Namen
stehen.
Document
Kategorie
Sport
Seitenansichten
8
Dateigröße
131 KB
Tags
1/--Seiten
melden