Einsatz und Realisierung von Datenbanksystemen (IN2031) -Endterm SS21 PDF

Preview

Summary

Lehrstuhl für Datenbanksysteme Fakultät für Informatik Technische Universität MünchenSPersönlicher StickerBestätigung der Verhaltensregeln Hiermit versichere ich, dass ich diese Klausur ausschließlich unter Verwendung der unten aufgeführten Hilfsmittel selbst löse und unter meinem Namen abgebe. Weit...

Description

Lehrstuhl für Datenbanksysteme Fakultät für Informatik Technische Universität München

Persönlicher Sticker S0303

Bestätigung der Verhaltensregeln Hiermit versichere ich, dass ich diese Klausur ausschließlich unter Verwendung der unten aufgeführten Hilfsmittel selbst löse und unter meinem Namen abgebe. Weiterhin erkläre ich, dass ich auf das Ergebnis der Prüfungsleistung anderer Studierender keinen Einfluss nehme (beispielsweise durch Weitergabe meiner Lösungsvorschläge). Ebenso bestätige ich hiermit, davon in Kenntnis gesetzt worden zu sein, dass die Klausur dem Urheberrecht unterliegt und die Weitergabe oder das Veröffentlichen dieser sowie Teilen daraus striktens untersagt ist.

Unterschrift oder vollständiger Name, falls keine Stifteingabe verfügbar

Einsatz und Realisierung von Datenbanksystemen Klausur: Prüfer:

IN2031 / Finalklausur Prof. Dr. Alfons Kemper

Datum: Uhrzeit:

Mittwoch, 21. Juli 2021 14:15 – 15:45

Bearbeitungshinweise • Diese Klausur umfasst 12 Seiten mit insgesamt 10 Aufgaben. Bitte kontrollieren Sie jetzt, dass Sie eine vollständige Angabe erhalten haben. • Die Gesamtpunktzahl in dieser Prüfung beträgt 90 Punkte. • Das Heraustrennen von Seiten aus der Prüfung ist untersagt. • Als Hilfsmittel sind zugelassen: – offenes Buch (Open-Book) • Mit * gekennzeichnete Teilaufgaben sind ohne Kenntnis der Ergebnisse vorheriger Teilaufgaben lösbar. • Es werden nur solche Ergebnisse gewertet, bei denen der Lösungsweg erkennbar ist. Auch Textaufgaben sind grundsätzlich zu begründen , sofern es in der jeweiligen Teilaufgabe nicht ausdrücklich anders vermerkt ist. • Schreiben Sie weder mit roter / grüner Farbe noch mit Bleistift. • Schalten Sie alle mitgeführten elektronischen Geräte vollständig aus, verstauen Sie diese in Ihrer Tasche und verschließen Sie diese.

Klausur leer

– Seite 1 / 12 –

IN-erdb-1-20210721-E0303-01

Aufgabe 1

Recovery (7 Punkte)

In der folgenden Tabelle ist die verzahnte Ausführung der drei TransaktionenT1 , T2 und T3 sowie das zugehörige Log auf der Basis logischer Protokollierung gezeigt. Initialwerte: A = 500; B = 700; C = 200 Schritt 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.

0

T1 BOT r(A , a1 )

T2

T3

Log [#1, T1 , BOT , 0]

BOT r(B, b3 ) r(C, c3 ) b3 := b3 − 10 w(B, b3 ) c3 := c3 + 20 w(C, c3 )

commit BOT

[#2, T3 , BOT , 0]

[#3, T3 , PB , B −= 10, B += 10, #2] [#4, T3 , PC , C += 20, C −= 20, #3] [#5, T3 , commit, #4] [#6, T2 , BOT , 0]

r(C, c2 ) a1 := a1 − 80 c2 := c2 + 90 w(A , a1 )

[#7, T1 , PA , A −= 80, A += 80, #1] [#8, T2 , PC , C += 90, C −= 90, #6] [#9, T2 , commit, #6] [#10, T1 , commit, #7]

w(C, c2 )

commit commit

a)* Das Log soll nun in die Form der physischen Protokollierung überführt werden. Geben Sie hierzu chronologisch geordnet alle geänderten Logeinträge an.

1 2 3 4

0

b)* Geben Sie alle Winner an, wenn das Datenbanksystem nach Ausführen von Schritt 14 abstürzt.

1

0

c)* Das Datenbanksystem stürzt nach Ausführen von Schritt 14 ab. Geben Sie die im Rahmen des Wiederanlaufs erzeugten CLRs (compensation log records) auf Basis logischer Protokollierung an.

1 2

IN-erdb-1-20210721-E0303-02

– Seite 2 / 12 –

Seite leer

Aufgabe 2

Historien (7 Punkte)

Gegeben sei die folgende Historie: r2 (x), w2 (x), r1 (z), w1 (z), c1 , r2 (x), w2 (x), c2 , r3 (z), w3 (z), r3 (x), w3 (x), c3

Geben Sie für jede Eigenschaft an, ob sie von der Historie erfüllt wird, und begründen Sie kurz. a)* Serialisierbar (SR)

0 1

b)* Rücksetzbar (RC)

0 1

c)* Vermeidet kaskadierendes Zurücksetzen (ACA)

0 1

d)* Strikt (ST)

0 1

e)* Kann die Historie von einem 2PL-Scheduler erzeugt worden sein?

0 1

f)* Kreuzen Sie alle äquivalenten seriellen Reihenfolgen der Transaktionen an. T3 |T1 |T2 T2 |T3 |T1 T3 |T2 |T1

keine serielle Reihenfolge möglich T1 |T2 |T3 T2 |T1 |T3 T1 |T3 |T2

Seite leer

– Seite 3 / 12 –

IN-erdb-1-20210721-E0303-03

Aufgabe 3

Sicherheit (9 Punkte)

Sie fangen die folgende, mit RSA verschlüsselte Nachricht ab: C=6. Sie kennen den öffentlichen Schlüssel (e,N)=(5,15). Eine Auswahl an Formeln zur Erinnerung: N =p·q

φ(N) = (p − 1) · (q − 1) e ·d ≡1 K =C

0

(mod φ(N)) d

mod N.

a) Wie lauten p und q?

1 2

0

b) Berechnen Sie φ(N) (phi(N))!

1 2

0

c) Wie lautet der private Schlüssel (d,N)?

1 2

0

d) Wie lautet die Nachricht im Klartext? Geben Sie die komplette Herleitung an.

1 2

0

e)* Wieso ist es Ihnen in c) möglich, den öffentlichen Schlüssel einfach zu berechnen. Wieso ist RSA in diesem Beispiel nicht sicher? (Kurzer Satz, maximal 15 Worte)

1

IN-erdb-1-20210721-E0303-04

– Seite 4 / 12 –

Seite leer

Aufgabe 4

Datalog (11 Punkte)

Gegeben sei die Faktentabellepaarung eines Spielplans (hier als Beispiel die Bundesliga nur in Ausschnitten dargestellt). Die Kombination aus beiden Mannschaften und Spieltag identifiziert eine Paarung eindeutig. %%paarung( H ei mMa nn sch aft , G as tM an ns cha ft , To reH eim , To reG as t , S pi el ta g ) paarung( ba yern , sch alk e , 8 ,0 , 1). paarung( do rtm un d , gl adb ach ,3 , 0 ,1) . paarung( l eipz ig , ma in z ,3 ,1) . paarung( wo lfs bu rg , le ve rk us en ,0 ,0 ,1) . ... paarung( ba ye rn , au gs bur g ,5 ,2 , 34). paarung( dor tmu nd , le ve rk use n ,3 ,1 ,3 4) . Schreiben Sie Datalog-Ausdrücke für folgende Prädikate. Sie können die Prädikate aus den vorigen Teilaufgaben zur Lösung der weiteren Aufgaben verwenden: a)* tDifferenz(Mannschaft,Gegner,Spieltag,Differenz). Gibt die Tordifferenz für jedes Spiel aus Sicht der Mannschaft aus (Bei Sieg positiv, bei Niederlage negativ).

0 1 2 3

b)* gewonnen(Gegner). Geben Sie alle Siege von augsburg aus.

0 1 2 3

c)* bestesTeam(Mannschaft). Geben Sie aus, welche Mannschaft den höchsten Sieg hatte.

0 1 2 3 4 5

Seite leer

– Seite 5 / 12 –

IN-erdb-1-20210721-E0303-05

Aufgabe 5

Quorum-Consensus (10 Punkte)

Um Ausfallsicherheit zu garantieren ist ein Datenwert A ’ ’ auf vier Rechnern verteilt. Jeder Rechner hält dabei eine vollständige Kopie von ’A ’ mit einem zugehörigen Wert und einer aufsteigend vergebenen Versionsnummer. Um Konsistenz zu garantieren wird das Quorum-Consensus-Verfahren eingesetzt. Dabei ist jedem Rechner ein Gewicht wi (A ) wie folgt zugewiesen: Rechner R1 R2 R3 0

Kopie A1 A2 A3

Gewicht wi (A ) 2 3 2

Wert 1303 1303 1303

Version 1 1 1

a) * Das Lesequorum ist Qr (A ) = 3 . Wie ist das minimale Schreibquorum Qw (A )? Begründen Sie kurz (Rechenweg)!

1

b)* Kreuzen Sie alle Lesemöglichkeiten für eine Transaktion auf dem Datum A ’ ’ nach dem Quorum-ConsensusProtokoll an.

A2 + A3

A2

A1 + A3

A1

A3

A1 + A2 + A3

A1 + A2

c)* Kreuzen Sie alle Schreibmöglichkeiten für eine Transaktion auf dem Datum A ’ ’ nach dem Quorum-ConsensusProtokoll an.

A1

A2

A2 + A3

A1 + A3

A1 + A2

A1 + A2 + A3

A3 0 1

d) Skizieren Sie das Schreiben des Werts 1909. Verändern Sie minimal viele Kopien. Es reicht, wenn Sie den neuen Zustand als drei Dreier-Tupel (Rechner, Wert, Version) angeben. Nehmen Sie (1,1303,1),(2,1303,1),(3,1303,1) aus obiger Tabelle als Initialzustand.

2 3

0 1

e) Wir fügen einen weiteren Rechner R4 für Kopie A4 mit Gewicht 6 hinzu. Berechnen Sie an, wie groß das Schreibquorum Qw′ (A ) ohne Berücksichtigung des Lesequorums mindestens sein muss. Begründen Sie kurz (Rechenweg reicht aus)!

IN-erdb-1-20210721-E0303-06

– Seite 6 / 12 –

Seite leer

Aufgabe 6

Skyline (9 Punkte)

Gegeben sei die Relation Torjaeger mit Primärschlüssel Name: Name Alice Chris Dominik Christoph Michael Per Andre Andi Josef Philipp

Spiele 6 7 5 4 2 2 5 4 6 3

Spielzeit 625 396 284 223 110 537 284 537 396 225

Tore 6 3 5 3 1 2 4 4 6 2

Wir betrachten nun die Skyline über diese Relation, wobei jene Spieler, welche die meisten Tore in kürzester Zeit erzielten, in der Skyline enthalten sein sollen. a)* Kreuzen Sie die Primärschlüssel derjenigen Tupel an, welche in der Skyline enthalten sind.

Chris

Dominik

Andre

Alice

Josef

Christoph

Philipp

Andi

Michael

Per

b)* Fügen Sie nun mittels SQL-92 ein neues Tupel ein, welches das Tupel mit PrimärschlüsselDominik bei gleicher Toranzahl dominiert. Alle weiteren Zuordnungen zur Skyline sollen allerdings unverändert bleiben.

0 1 2 3

c)* Betrachten wir zusätzlich noch das AttributSpiele. Formulieren Sie nun eine SQL-92 Anfrage (ohne SkylineOperator), welche zusätzlich zu den bisherigen Optimalitätsbedingungen noch die geringste Anzahl an Spielen berücksichtigt.

0 1 2 3 4

Seite leer

– Seite 7 / 12 –

IN-erdb-1-20210721-E0303-07

Aufgabe 7 0

Window-Functions (8 Punkte)

Rekonstruieren Sie den Inhalt der nachfolgenden Relation gehaltslisteORF, sodass die untenstehenden Ergebnisse mit den SQL-Anfragen übereinstimmen.

1 2

create table gehaltslisteORF (name text not null, gehalt int not null, sendung text not null); insert into gehaltslisteORF values

3 4 5 6 7 8

; select rank, name from ( select *, rank() over (order by gehalt desc) from gehaltslisteORF ) where rank < 6; rank 1 2 3 4 5 5

name Armin Assinger Dirk Stermann Christoph Grissemann Nadja Bernhard Susanne Höggerl Tarek Leitner

select name, avg(gehalt) over (order by gehalt range between 4000 preceding and 4000 following) as avg_gehalt from gehaltslisteORF order by avg_gehalt desc; name Armin Assinger Dirk Stermann Christoph Grissemann Nadja Bernhard Susanne Höggerl Tarek Leitner

avg_gehalt 89072 81036 81036 81036 61036 61036

select name, sendung, avg(gehalt) over (partition by sendung) as avg_gehalt from gehaltslisteORF order by avg_gehalt desc; name Armin Assinger Dirk Stermann Christoph Grissemann Nadja Bernhard Susanne Höggerl Tarek Leitner

IN-erdb-1-20210721-E0303-08

sendung Millionenshow Keine Chance Keine Chance ZIB ZIB ZIB

– Seite 8 / 12 –

avg_gehalt 89072 82036 82036 67036 67036 67036

Seite leer

Aufgabe 8

ART (9 Punkte)

Gegeben sei nachfolgender ART, welcher ausschließlich aus Node4 Knoten besteht. Ein Node4 speichert sortiert die Bytes der Schlüssel und die zugehörige Payload. Beachten Sie, dass die Knoten hierbei nicht notwendigerweise konsekutiv im Speicher abgelegt sind. Weiterhin verzichten wir auf Pfadkompression im Rahmen dieser Aufgabe. Die in der ersten Spalte gezeigten Adressen dienen als Synonyme für tatsächliche Hauptspeicheradressen.

Adresse

Knoten key bytes

payload

A

0x46

B

B

0x1c

C

C

0x23 0x42

D

E

0x01 0x30 0xbd

v0

v1

v2

0x02 0x05 0xa7

v3

v4

v5

D E

Tabelle 8.1: ART Knoten a)* Geben Sie eine obere Grenze für die Anzahl der Cache-Misses für einen Lookup nach0x46 0x1c 0x42 0x05 an. Verwenden Sie hierbei die aus der Übung bekannten Eckdaten bzgl. Knotengröße und Cacheline-Größe.

0 1

b)* Fügen Sie die beiden Schlüssel-Wert-Paare (0x46 0x1c 0x23 0xac, v6 ) und (0x46 0x1c 0xe3 0x01, v7 ) in den in Tabelle 8.1 gegebenen ART ein. Nutzen Sie hierfür die nachfolgende Vorlage für alle zu ändernden und hinzuzufügenden Knoten. Hinweis: Nicht benötigte/leere Felder können leer belassen werden.

0 1 2

Adresse

Knoten

3 4 5

c)* Listen Sie alle Schlüssel, welche im ursprünglichen ART aus Tabelle 8.1 gespeichert sind, in Hexadezimalschreibweise auf.

0 1 2 3

Seite leer

– Seite 9 / 12 –

IN-erdb-1-20210721-E0303-09

Aufgabe 9

XML und JSON (10 Punkte)

0

a)* Gegeben sei folgende XQuery-Anfrage:

1

5

for $x in (1 ,2) r et ur n < P ru ef un gs an za hl se me st er =" { $x }" > { for $s in do c (' pru efen ')/ un i / st re tu rn < st ud i nam e = "{ $s / na me / te xt ()}" > { let $p := t ok en iz e ( $s / p la n / sem [ $x ]/ @prs ," ") re tu rn c ou nt ( do c ( ' pru efen ')/ un i / prs / pr [ @PN r = $p ]) } }

6

Erstellen Sie ein passendes XML-Dokument pruefen zu folgender Ausgabe:

2 3 4

7

< P ru ef un gs an za hl se me st er ="1" > < stu di na me ="Alice" >1 < stu di na me ="Chris" >1

< P ru ef un gs an za hl se me st er ="2" > < stu di na me ="Alice" >2 < stu di na me ="Chris" >1

Alice







Chris



0 1

b)* Gegeben sei folgende SQL-Anfrage: select doc->2->>'Name' as Name, doc->2->>'MNr' as MNr from uni_json; Vervollständigen Sie die nachfolgende insert-Anfrage auf einer anfangs leeren Relationuni_json durch einen passenden JSON-Ausdruck, sodass die select-Anfrage das folgende Ergebnis liefert:

2 3

Name Alice

MNr M4034

insert into uni_json (name, doc) values ('uni','

');

IN-erdb-1-20210721-E0303-10

– Seite 10 / 12 –

Seite leer

Aufgabe 10

PageRank (10 Punkte)

Gegeben Sei der unten stehende Webgraph für ein Netzwerk aus drei Webseiten.

A

B

C

Der Startwert des Pageranks ist 1/|V | für jeden Knoten mit V = 3 und α = 0. Geben Sie die Lösung in folgender Form an: A=1/3;B=1/3;C=1/3; Der Rechenweg muss ersichtlich sein. a)* Berechnen Sie den PageRank für das Netzwerk nach der 1. Iteration.

0 1 2 3

b)* Sei nun α = 0.1. Berechnen Sie den PageRank für das Netzwerk nach der 1. Iteration unter Berücksichtung des neuen α-Wertes. Geben Sie das Ergebnis gerundet auf zwei Nachkommastellen an.

0 1 2 3

c)* Betrachten wir nun den Webgraphen, welcher durch das Entfernen der Kante von C zu B, entsteht. Damit hat C keine ausgehenden Kanten mehr. Geben Sie die PageRank-Werte der Knoten an, gegen die der PageRankAlgorithmus konvergieren wird, und erläutern Sie kurz, welches Problem hierbei entsteht.

0 1 2

d) In der Vorlesung wurde eine Lösung für diese Problematik vorgestellt. Beschreiben Sie diese kurz.

0 1 2

Seite leer

– Seite 11 / 12 –

IN-erdb-1-20210721-E0303-11

Zusätzlicher Platz für Lösungen. Markieren Sie deutlich die Zuordnung zur jeweiligen Teilaufgabe. Vergessen Sie nicht, ungültige Lösungen zu streichen.

IN-erdb-1-20210721-E0303-12

– Seite 12 / 12 –

Seite leer...