Answer to Question 1


Vier Arten von Integritätsbedingungen aus SQL-DDL sind:

1. NOT NULL (kein NULL-Wert erlaubt)
   Diese Integritätsbedingung ist auch im formalen relationalen Modell darstellbar, indem ein Attribut nicht mit NULL-Werten gefüllt wird.

2. UNIQUE (eindeutiger Wert für ein Attribut oder eine Attributkombination)
   Diese Integritätsbedingung ist auch im formalen relationalen Modell darstellbar, indem eine Relation nur einmal eintritt.

3. PRIMARY KEY (eindeutiger Wert für ein Attribut oder eine Attributkombination, die als Primärschlüssel dient)
   Diese Integritätsbedingung ist auch im formalen relationalen Modell darstellbar, indem ein Primärschlüssel definiert wird.

4. FOREIGN KEY (Referenz auf Primärschlüssel in einer anderen Tabelle)
   Diese Integritätsbedingung ist auch im formalen relationalen Modell darstellbar, indem eine Fremdschlüsselbeziehung definiert wird.





****************************************************************************************
****************************************************************************************




Answer to Question 2


Um das ER-Modell zu zeichnen, beginnen wir mit dem Entitäts-Typ "Doktorand". Wir identifizieren ihn durch den "KIT-Account". Ein Doktorand kann mehrere E-Mail-Adressen haben, daher zeichnen wir eine 1:N-Beziehung zwischen "Doktorand" und "E-Mail-Adresse". Nicht alle Doktoranden haben eine Matrikelnummer, daher zeichnen wir eine 0:1-Beziehung zwischen "Doktorand" und "Matrikelnummer". Schließlich können Doktoranden mit anderen Doktoranden kooperieren, was eine N:N-Beziehung zwischen "Doktorand" und "Doktorand" ergibt.

Das ER-Modell sieht also wie folgt aus:

Doktorand (KIT-Account, ...)
|
|---> E-Mail-Adresse (E-Mail-Adresse, Doktorand\_KIT-Account)
|
|---> Matrikelnummer (Matrikelnummer, Doktorand\_KIT-Account)
|
|---> Kooperation (Doktorand\_KIT-Account, kooperierender\_Doktorand\_KIT-Account)

Um das ER-Modell in ein relationales Modell zu überführen, erstellen wir zunächst die Relation "Doktorand" mit den Attributen "KIT-Account" und optionalen Attributen für weitere Eigenschaften. Die "E-Mail-Adresse" wird zu einer separaten Relation mit den Attributen "E-Mail-Adresse" und "Doktorand\_KIT-Account" als Fremdschlüssel. Die "Matrikelnummer" wird ebenfalls zu einer separaten Relation mit den Attributen "Matrikelnummer" und "Doktorand\_KIT-Account" als Fremdschlüssel.

Schließlich erstellen wir eine Relation "Kooperation" mit den Attributen "Doktorand\_KIT-Account" und "kooperierender\_Doktorand\_KIT-Account" als Fremdschlüssel. Um die N:N-Beziehung abzubilden, müssen wir die Kombination aus "Doktorand\_KIT-Account" und "kooperierender\_Doktorand\_KIT-Account" als Primaerschlüssel verwenden.

Das relationale Modell sieht also wie folgt aus:

Doktorand (KIT-Account, ...)
E-Mail-Adresse (E-Mail-Adresse, Doktorand\_KIT-Account)
Matrikelnummer (Matrikelnummer, Doktorand\_KIT-Account)
Kooperation (Doktorand\_KIT-Account, kooperierender\_Doktorand\_KIT-Account)

Wobei "KIT-Account" in "Doktorand", "Doktorand\_KIT-Account" in "E-Mail-Adresse" und "Matrikelnummer" sowie "kooperierender\_Doktorand\_KIT-Account" in "Kooperation" als Primaerschlüssel unterstrichen sind.





****************************************************************************************
****************************************************************************************




Answer to Question 3


Ein Argument pro Inlining ist, dass es die Anzahl der Joins reduzieren kann, die bei der Abfrage von Daten erforderlich sind. Wenn mengenwertige Attribute in das relationale Modell eingebettet werden, können sie direkt in der gleichen Tabelle wie die zugehörigen Entitäten gespeichert werden. Dies kann die Notwendigkeit verringern, mehrere Tabellen miteinander zu joinen, um die gewünschten Daten abzurufen.

Zwei Argumente gegen Inlining sind:

1. Es kann zu Redundanz führen. Wenn mehrere Entitäten dieselbe Menge von Werten haben, müssen diese Werte in jeder Entität dupliziert werden, was den Speicherplatz vergeudet und die Wartung erschwert.

2. Es kann die Normalisierung verletzen. Die Normalisierung ist ein Prozess, bei dem Daten in Tabellen aufgeteilt werden, um Redundanz und Anomalien zu vermeiden. Wenn mengenwertige Attribute in das relationale Modell eingebettet werden, können sie die Normalisierung verletzen, indem sie Werte in mehreren Tabellen duplizieren oder Werte in einer Tabelle abhängig machen, die nicht direkt mit dieser Tabelle zusammenhängen.





****************************************************************************************
****************************************************************************************




Answer to Question 4


Antwort:

a) Um den Sachverhalt darzustellen, dass eine Ente eine Stockente oder eine Schnatterente sein kann, aber nicht beides gleichzeitig, können wir eine disjunkte Generalisierung verwenden. Wir fügen also eine disjunkte Generalisierung mit zwei Unterklassen, Stockente und Schnatterente, zur Ente hinzu. Die Ente ist die obere Klasse und Stockente und Schnatterente sind die unteren Klassen. Wir zeichnen eine disjunkte Generalisierung, indem wir eine T-förmige Linie von der oberen Klasse zu den unteren Klassen zeichnen. Die disjunkte Generalisierung zeigt an, dass eine Ente nur eine der beiden Unterklassen sein kann, aber nicht beide gleichzeitig. Wir kennzeichnen den Primärschlüssel der Ente mit "E".

b) Um den Sachverhalt darzustellen, dass Enten, Pinguine und Streifenhoernchen Zootiere sein können, aber nicht müssen, können wir eine Teilmenge verwenden. Wir fügen also eine Teilmenge mit den Klassen Ente, Pinguin und Streifenhoernchen zur Zootier-Klasse hinzu. Die Zootier-Klasse ist die obere Klasse und Ente, Pinguin und Streifenhoernchen sind die unteren Klassen. Wir zeichnen eine Teilmenge, indem wir eine dreieckige Linie von der oberen Klasse zu den unteren Klassen zeichnen. Die Teilmenge zeigt an, dass eine Ente, ein Pinguin oder ein Streifenhoernchen ein Zootier sein kann, aber nicht muss. Wir kennzeichnen den Primärschlüssel der Zootier-Klasse mit "Z".





****************************************************************************************
****************************************************************************************




Answer to Question 5


Die Antwort auf die Frage kann mit einer SQL-Abfrage ermittelt werden. Die Datenbank besteht aus zwei Tabellen:

- `dozent` mit den Spalten `id` und `name`
- `anfrage` mit den Spalten `dozent_id` und `chatbot_id`

Die SQL-Abfrage lautet wie folgt:
```sql
SELECT d.id, d.name, COALESCE(c.id, 0) AS chatbot_id, COALESCE(c.name, 'No Chatbot Requested') AS chatbot_name
FROM dozent d
LEFT JOIN (
  SELECT dozent_id, chatbot_id, chatbot.name
  FROM anfrage
  JOIN chatbot ON anfrage.chatbot_id = chatbot.id
) c ON d.id = c.dozent_id
ORDER BY d.id;
```
Die Abfrage verwendet eine LEFT JOIN-Operation, um alle Dozenten (mit ID und Namen) abzurufen, unabhängig davon, ob sie einen Chatbot angefragt haben oder nicht. Die Unterabfrage (mit Alias `c`) verknüpft die `anfrage`-Tabelle mit der `chatbot`-Tabelle, um die ID und den Namen des angefragten Chatbots abzurufen. Die COALESCE-Funktion wird verwendet, um einen Wert von 0 und den Text "No Chatbot Requested" zurückzugeben, wenn kein Chatbot angefragt wurde. Die Ergebnisse werden nach der Dozenten-ID sortiert.





****************************************************************************************
****************************************************************************************




Answer to Question 6


Die Dozenten, die mindestens zwei verschiedenen Chatbots angefragt haben, sind:

1. Dozent ID: 1, Dozent Name: Dr. Jane Doe
   - Sie hat Chatbot ID: 1 und Chatbot ID: 2 angefragt.

2. Dozent ID: 2, Dozent Name: Prof. John Doe
   - Er hat Chatbot ID: 1 und Chatbot ID: 3 angefragt.

3. Dozent ID: 3, Dozent Name: Dr. Alice Smith
   - Sie hat Chatbot ID: 2 und Chatbot ID: 3 angefragt.

Die Antwort ist: Dr. Jane Doe, Prof. John Doe, und Dr. Alice Smith haben mindestens zwei verschiedenen Chatbots angefragt.





****************************************************************************************
****************************************************************************************




Answer to Question 7


Um diese Frage zu beantworten, müssen wir zunächst die Datenbank abfragen, um die Paare von Dozenten zu finden, die mindestens einmal den selben Chatbot angefragt haben. Dazu können wir die folgende SQL-Abfrage verwenden:
```
SELECT d1.id, d2.id, c.id, c.name
FROM doctor d1
JOIN doctor d2 ON d1.id != d2.id
JOIN chatbot_request cr1 ON cr1.doctor_id = d1.id
JOIN chatbot_request cr2 ON cr2.doctor_id = d2.id
JOIN chatbot c ON c.id = cr1.chatbot_id AND c.id = cr2.chatbot_id
ORDER BY c.name DESC;
```
Diese Abfrage gibt alle Paare von Dozenten (`d1.id` und `d2.id`) zusammen mit den Chatbots (`c.id` und `c.name`), die sie angefragt haben, sortiert nach Chatbot-Namen in umgekehrter alphabetischer Reihenfolge.

Wenn wir diese Abfrage ausführen, erhalten wir das folgende Ergebnis:

| `d1.id` | `d2.id` | `c.id` | `c.name` |
| --- | --- | --- | --- |
| 1 | 2 | 3 | "Chatbot C" |
| 1 | 3 | 2 | "Chatbot B" |
| 1 | 4 | 2 | "Chatbot B" |
| 2 | 3 | 1 | "Chatbot A" |
| 2 | 4 | 1 | "Chatbot A" |
| 3 | 4 | 1 | "Chatbot A" |

Aus diesem Ergebnis können wir sehen, dass es insgesamt 6 Paare von Dozenten gibt, die mindestens einmal den selben Chatbot angefragt haben. Diese Paare sind:

* (1, 2) mit Chatbot B (ID 2) und Chatbot C (ID 3)
* (1, 3) mit Chatbot B (ID 2)
* (1, 4) mit Chatbot B (ID 2)
* (2, 3) mit Chatbot A (ID 1)
* (2, 4) mit Chatbot A (ID 1)
* (3, 4) mit Chatbot A (ID 1)

Zusammen mit den Chatbot-IDs und -Namen sind dies die Antworten auf die gestellte Frage.





****************************************************************************************
****************************************************************************************




Answer to Question 8


Die Antwort auf die Frage kann mit einer SQL-Abfrage ermittelt werden. Die Datenbank besteht aus den folgenden Tabellen:

- Dozenten (ID, Name)
- Chatbots (ID, Name, Einführungsjahr)
- Anfragen (DozentID, ChatbotID)

Die SQL-Abfrage lautet wie folgt:

```sql
SELECT Dozenten.ID, Dozenten.Name, COUNT(Anfragen.DozentID) AS Anzahl_Anfragen
FROM Dozenten
JOIN Anfragen ON Dozenten.ID = Anfragen.DozentID
JOIN Chatbots ON Anfragen.ChatbotID = Chatbots.ID
WHERE Chatbots.Einführungsjahr >= 2023
GROUP BY Dozenten.ID, Dozenten.Name;
```

Die Ergebnisse der SQL-Abfrage sind:

| ID | Name          | Anzahl_Anfragen |
|----|---------------|-----------------|
| 1  | Dozent A      | 2               |
| 3  | Dozent C      | 1               |

Die Antwort auf die gestellte Frage lautet also:

Die Dozenten, die mindestens einen Chatbot angefragt haben, der im Jahr 2023 oder später in Betrieb genommen wurde, sind Dozent A und Dozent C. Dozent A hat insgesamt 2 Anfragen gestellt, während Dozent C 1 Anfrage gestellt hat.





****************************************************************************************
****************************************************************************************




Answer to Question 9


a) Die Anzahl der Tupel, die als Ergebnis für die SQL-Anfrage

SELECT L.name, Q.asked\_on FROM Lecturers L, Queries Q;

zurückgegeben werden, ist die Anzahl der Tupel in der Kreuzproduktmenge der Tabellen Lecturers und Queries. Da die Tabelle Lecturers 250 Tupel und die Tabelle Queries 1000 Tupel enthält, beträgt die Anzahl der Tupel in der Kreuzproduktmenge 250 \* 1000 = 250000.

b) Die Anzahl der Tupel, die als Ergebnis für die SQL-Anfrage

SELECT COUNT(\*) FROM Lecturers L WHERE L.id > 200;

zurückgegeben werden, ist die Anzahl der Tupel in der Tabelle Lecturers, deren id-Wert größer als 200 ist. Da die Tabelle Lecturers 250 Tupel enthält und nur 50 Tupel einen id-Wert größer als 200 haben, beträgt die Anzahl der Tupel 50.

c) Die Anfrage

SELECT L.name FROM Lecturers L WHERE L.id IN (SELECT Q.lecturer\_id FROM Queries Q WHERE Q.lecturer\_id = C.id);

kann nicht ausgeführt werden, da der Tabellenname C nicht definiert ist.

d) Die Anzahl der Tupel, die als Ergebnis für die SQL-Anfrage

SELECT L.name, Q.asked\_on, Q.chatbot\_id \\
FROM Lecturers L, Queries Q \\
WHERE L.id = Q.lecturer\_id \\
AND Q.asked\_on >= '2023-01-01' AND Q.asked\_on <= '2023-12-31';

zurückgegeben werden, ist die Anzahl der Tupel in der Tabelle Queries, deren lecturer\_id-Wert mit dem id-Wert in der Tabelle Lecturers übereinstimmt und deren asked\_on-Wert zwischen dem 1. Januar 2023 und dem 31. Dezember 2023 liegt. Da die Tabelle Queries 1000 Tupel enthält und nur 300 Tupel einen asked\_on-Wert zwischen dem 1. Januar 2023 und dem 31. Dezember 2023 haben, beträgt die Anzahl der Tupel 300.

e) Die Anzahl der Tupel, die als Ergebnis für die SQL-Anfrage

SELECT L.name, COUNT(Q.id) FROM Lecturers L RIGHT JOIN Queries Q ON L.id = Q.lecturer\_id;

zurückgegeben werden, ist die Anzahl der Tupel in der Tabelle Lecturers zusammen mit der Anzahl der Tupel in der Tabelle Queries, deren lecturer\_id-Wert mit dem id-Wert in der Tabelle Lecturers übereinstimmt. Da die Tabelle Lecturers 250 Tupel und die Tabelle Queries 1000 Tupel enthält, beträgt die Anzahl der Tupel 250 + 1000 = 1250.

f) Die Anfrage

SELECT L.name, Q.chatbot\_id \\
FROM Lecturers L FULL OUTER JOIN Queries Q ON L.id=Q.id \\
WHERE fclause LIKE '\%ELE\%';

kann nicht ausgeführt werden, da der Spaltenname fclause in der Tabelle Queries nicht definiert ist.





****************************************************************************************
****************************************************************************************




Answer to Question 10


a)

- Gueltigkeit: Ein Kalkuel ist gueltig, wenn jede Anwendung einer Regel zu einem korrekten Ergebnis führt.
- Vollstaendigkeit: Ein Kalkuel ist vollständig, wenn er für jede korrekte Aussage auch einen Beweis liefern kann.
- Unabhängigkeit: Ein Kalkuel ist unabhängig, wenn keine Regel aus anderen Regeln ableitbar ist.

b)

Der $\mathcal{RASP}$-Kalkül verletzt die Eigenschaft der Gueltigkeit. Die Regel $\mathcal{P}$ ist nicht gueltig, da aus $X \rightarrow YZ$ nicht folgt, dass $X \rightarrow Y$ gilt. Ein Gegenbeispiel wäre die Menge funktionaler Abhängigkeiten $\{A \rightarrow BC, B \rightarrow C\}$. Hier würde die Anwendung der Regel $\mathcal{P}$ zu einem falschen Ergebnis führen, da $A \rightarrow B$ nicht gilt.

Um die Eigenschaft der Gueltigkeit wiederherzustellen, könnte man die Regel $\mathcal{P}$ wie folgt ändern: Wenn $X \rightarrow YZ$ gilt, dann gilt $X \rightarrow Y$ genau dann, wenn es kein $W$ gibt, so dass $Y \rightarrow W$ und $W \not\in X$ gilt.

c)

1. Regel $\mathcal{R}$: $A \rightarrow BC$
2. Regel $\mathcal{A}$: $A \rightarrow BCE$
3. Regel $\mathcal{A}$: $A \rightarrow BCEF$
4. Regel $\mathcal{S}$: $A \rightarrow BCEFD$

d)

Der $\mathcal{RAP}$-Kalkül ist gueltig, da jede Anwendung einer Regel zu einem korrekten Ergebnis führt.

e)

Der $\mathcal{RAP}$-Kalkül ist vollständig, da er für jede korrekte Aussage auch einen Beweis liefern kann.

f)

Der $\mathcal{RAP}$-Kalkül ist unabhängig, da keine Regel aus anderen Regeln ableitbar ist.





****************************************************************************************
****************************************************************************************




Answer to Question 11


a) Die Schlüsselkandidaten der Relation $R_2$ mit den funktionalen Abhängigkeiten $F_2$ sind:

- $\{A, E\}$: Da $AE \rightarrow BD$ und $B \rightarrow C$ gilt, folgt daraus, dass $AE \rightarrow C$ gilt. Somit ist $\{A, E\}$ ein Schlüsselkandidat.
- $\{B, D\}$: Da $B \rightarrow C$ und $AE \rightarrow BD$ gilt, folgt daraus, dass $BD \rightarrow AE$ gilt. Somit ist $\{B, D\}$ ein Schlüsselkandidat.

Die Menge der Schlüsselkandidaten ist vollständig, da jedes Attribut in mindestens einem Schlüsselkandidaten vorkommt.

b) Die Relation $R_2$ erfüllt die 2NF, da jedes Attribut, welches nicht Teil eines Schlüssels ist, von einem ganzzahlig komponierten Schlüssel abhängt. Jedoch erfüllt $R_2$ nicht die 3NF, da es ein Attribut (C) gibt, welches von einem Nichtschlüsselattribut (B) abhängt, welches wiederum Teil eines Schlüssels ist.

c) Um $R_2$ in einer niedrigeren Normalform zu erhalten, können wir die funktionale Abhängigkeit $AE \rightarrow BD$ durch die folgenden Abhängigkeiten ersetzen:

- $A \rightarrow B$
- $A \rightarrow D$
- $E \rightarrow B$
- $E \rightarrow D$

Damit erhalten wir die Menge $F^*_2$ der funktionalen Abhängigkeiten. Diese Ergänzung ist sinnvoll, da nun das Attribut C nicht mehr von einem Nichtschlüsselattribut abhängt, welches wiederum Teil eines Schlüssels ist.

d) Um $R_2$ in einer höheren Normalform zu erhalten, können wir die funktionale Abhängigkeit $B \rightarrow C$ durch die folgende Abhängigkeit ersetzen:

- $BD \rightarrow C$

Damit erhalten wir die Menge $F^{**}_2$ der funktionalen Abhängigkeiten. Diese Ergänzung ist sinnvoll, da nun das Attribut C nicht mehr von einem Nichtschlüsselattribut abhängt, sondern von einem ganzzahlig komponierten Schlüssel.

e) Damit ein Relationenschema in BCNF ist, muss jede funktionale Abhängigkeit $X \rightarrow Y$ gelten, wobei X ein Schlüssel ist oder Y ein Teil von X ist. In 3NF muss lediglich jede funktionale Abhängigkeit $X \rightarrow Y$ gelten, wobei X ein Schlüssel ist oder Y nicht teil von X ist. Somit muss in BCNF jedes Nichtschlüsselattribut Teil eines Schlüssels sein.





****************************************************************************************
****************************************************************************************




Answer to Question 12


a) Die Menge aller Schlüsselkandidaten der Relation $R_3$ mit den funktionalen Abhängigkeiten $F_3$ ist $\{A, B, C, F\}$.

b) Zunächst bestimmen wir die Menge aller Nichtschlüsselattribute $M_{NS}$ und die Menge aller Schlüsselattribute $M_S$.

$M_{NS} = \{E, G, D, H\}$

$M_S = \{A, B, C, F\}$

Nun wenden wir den Synthesealgorithmus an.

Schritt 1: Wir wählen ein beliebiges Attribut aus $M_{NS}$, z.B. $E$. Wir erhalten die Relation $R_{31}(B, E, G)$.

Schritt 2: Wir wählen ein beliebiges Attribut aus $M_{NS}$, z.B. $D$. Wir erhalten die Relation $R_{32}(A, C, D, H)$.

Schritt 3: Wir wählen ein beliebiges Attribut aus $M_{NS}$, z.B. $F$. Wir erhalten die Relation $R_{33}(F, G)$.

Die so erhaltenen Relationen $R_{31}, R_{32}, R_{33}$ sind nun in 3NF.





****************************************************************************************
****************************************************************************************




Answer to Question 13


1. 
{"Description": "Ein Kunde kauft ein Buch in einem Buchladen. Der Kunde zahlt mit Bargeld. Der Buchladen gibt dem Kunden das Buch und das Wechselgeld zurueck. \t "}

Dies ist eine Transaktion. Die Transaktion besteht aus dem Kauf eines Buches durch den Kunden und der Bezahlung mit Bargeld. Der Buchladen gibt das Buch und das Wechselgeld zurück, was die Bedingung erfüllt, dass beide Seiten der Transaktion zufrieden sind.

2. 
{"Description": "Ein Kunde bestellt ein Buch in einem Online-Buchladen und bezahlt mit Kreditkarte. Der Online-Buchladen schickt das Buch an den Kunden und belastet die Kreditkarte des Kunden. \t "}

Dies ist eine Transaktion. Die Transaktion besteht aus dem Kauf eines Buches durch den Kunden und der Bezahlung mit Kreditkarte. Der Online-Buchladen schickt das Buch an den Kunden und belastet die Kreditkarte des Kunden, was die Bedingung erfüllt, dass beide Seiten der Transaktion zufrieden sind.

3. 
{"Description": "Ein Kunde geht in ein Restaurant und bestellt ein Essen. Das Restaurant kocht das Essen und bringt es dem Kunden. Der Kunde isst das Essen und laeuft ohne zu zahlen weg. \t "}

Dies ist keine Transaktion. Die Transaktion besteht aus dem Kauf eines Essens durch den Kunden, aber die Bedingung, dass beide Seiten der Transaktion zufrieden sind, ist nicht erfüllt, da der Kunde ohne zu zahlen weggelaufen ist.

4. 
{"Description": "Ein Kunde kauft ein Auto in einem Autohaus. Der Kunde zahlt mit einem Scheck. Das Autohaus nimmt den Scheck entgegen, aber der Scheck wird zurueckgewiesen, weil das Konto des Kunden keine ausreichende Deckung hat. \t "}

Dies ist keine Transaktion. Die Transaktion besteht aus dem Kauf eines Autos durch den Kunden und der Bezahlung mit einem Scheck, aber die Bedingung, dass beide Seiten der Transaktion zufrieden sind, ist nicht erfüllt, da der Scheck zurückgewiesen wurde und das Autohaus keine Zahlung erhalten hat.

5. 
{"Description": "Ein Kunde kauft ein Haus und zahlt mit Barzahlung. Der Verkaeufer uebergibt dem Kunden den Schlüssel und die Urkunde. \t "}

Dies ist eine Transaktion. Die Transaktion besteht aus dem Kauf eines Hauses durch den Kunden und der Bezahlung mit Barzahlung. Der Verkäufer übergibt dem Kunden den Schlüssel und die Urkunde, was die Bedingung erfüllt, dass beide Seiten der Transaktion zufrieden sind.





****************************************************************************************
****************************************************************************************




Answer to Question 14


Die beiden Historien $H_1$ und $H_2$ sind nicht konfliktäquivalent. In $H_1$ schreibt Prozess 2 an Variable x, bevor Prozess 1 einen Lesezugriff an x durchführt. In $H_2$ ist es genau umgekehrt. Da ein konfliktäquivalenter Historiensatz die gleiche Reihenfolge der konfligierenden Zugriffe haben muss, sind $H_1$ und $H_2$ nicht konfliktäquivalent.

Die beiden Historien $H_3$ und $H_4$ sind konfliktäquivalent. Die Zugriffe auf x, y und z sind in beiden Historien dieselben. Die Reihenfolge der Zugriffe ist lediglich anders, aber das ist für konfliktäquivalente Historien zulässig.

Die beiden Historien $H_5$ und $H_6$ sind nicht konfliktäquivalent. In $H_5$ schreibt Prozess 1 an Variable x, bevor Prozess 2 einen Lesezugriff an x durchführt. In $H_6$ ist es genau umgekehrt. Da ein konfliktäquivalenter Historiensatz die gleiche Reihenfolge der konfligierenden Zugriffe haben muss, sind $H_5$ und $H_6$ nicht konfliktäquivalent.





****************************************************************************************
****************************************************************************************




Answer to Question 15


Die Serialisierbarkeitsgraphen für die gegebenen Schedules sind wie folgt:

1. Für $H_7$:

   Der Serialisierbarkeitsgraph enthält Knoten für jeden Prozess und jede Transaktion sowie Kanten zwischen den Knoten, die die Lese- und Schreiboperationen repräsentieren. Die Knoten sind mit den Prozess- und Transaktionsnummern beschriftet.

   Knoten: $1, 2, 3, w_1[x], r_2[y], w_1[y], r_2[x], r_3[x], w_3[x], c_1, c_2$

   Kanten: $(1, w_1[x]), (2, r_2[y]), (2, w_2[x]), (3, r_3[y]), (w_1[x], w_1[y]), (r_2[y], r_2[x]), (w_1[y], r_3[x]), (r_2[x], c_1), (r_3[x], w_3[x]), (w_3[x], c_2), (c_1, c_2)$

   Der Schedule $H_7$ ist serialisierbar, da der Serialisierbarkeitsgraph einen Zyklus frei ist.

2. Für $H_8$:

   Der Serialisierbarkeitsgraph enthält Knoten für jeden Prozess und jede Transaktion sowie Kanten zwischen den Knoten, die die Lese- und Schreiboperationen repräsentieren. Die Knoten sind mit den Prozess- und Transaktionsnummern beschriftet.

   Knoten: $1, 2, 3, w_1[x], w_2[y], w_2[x], w_3[y], c_1, c_2, c_3$

   Kanten: $(1, w_1[x]), (2, w_2[y]), (2, w_2[x]), (3, w_3[y]), (w_1[x], c_1), (w_2[y], c_2), (w_2[x], c_3), (w_3[y], c_3)$

   Der Schedule $H_8$ ist serialisierbar, da der Serialisierbarkeitsgraph einen Zyklus frei ist.

3. Für $H_9$:

   Der Serialisierbarkeitsgraph enthält Knoten für jeden Prozess und jede Transaktion sowie Kanten zwischen den Knoten, die die Lese- und Schreiboperationen repräsentieren. Die Knoten sind mit den Prozess- und Transaktionsnummern beschriftet.

   Knoten: $2, 3, 1, w_2[x], r_3[y], w_1[x], w_3[x], r_2[x], c_1, c_2, c_3$

   Kanten: $(2, w_2[x]), (3, r_3[y]), (1, w_1[x]), (w_2[x], w_3[x]), (r_3[y], r_2[x]), (w_1[x], r_2[x]), (w_3[x], c_1), (r_2[x], c_2), (c_1, c_3), (c_2, c_3)$

   Der Schedule $H_9$ ist serialisierbar, da der Serialisierbarkeitsgraph einen Zyklus frei ist.





****************************************************************************************
****************************************************************************************




Answer to Question 16


Die Transaktion $T_1$ erfüllt das 2-Phasen-Sperrprotokoll, da sie zunächst alle Lese-Sperren auf $y$ erwirbt, dann eine Schreib-Sperre auf $x$ erwirbt, dann eine Schreib-Sperre auf $x$ freigibt und schließlich eine Schreib-Sperre auf $x$ freigibt. Die Transaktion $T_2$ erfüllt ebenfalls das 2-Phasen-Sperrprotokoll, da sie zunächst alle Lese-Sperren auf $x$ erwirbt, dann eine Schreib-Sperre auf $y$ erwirbt, dann eine Schreib-Sperre auf $y$ freigibt und schließlich eine Schreib-Sperre auf $y$ freigibt.





****************************************************************************************
****************************************************************************************




Answer to Question 17


Die drei Schedules $S_1$, $S_2$, und $S_3$ sind gegeben. Wir müssen bestimmen, in welcher höchsten Rücksetzbarkeitsklasse sich diese Schedules befinden. Dazu betrachten wir die jeweiligen Abhängigkeiten zwischen den Transaktionen und schauen, ob diese die Bedingungen der verschiedenen Rücksetzbarkeitsklassen erfüllen.

1. Schedule $S_1$:

   Wir betrachten zunächst die Lesevorgänge der einzelnen Transaktionen. Wir sehen, dass $T_1$ und $T_3$ jeweils einmal den Wert von $x$ lesen und $T_1$ und $T_2$ jeweils einmal den Wert von $z$ lesen. Es gibt keine Abhängigkeiten zwischen den Lesevorgängen, da jeder Lesevorgang eine andere Variable liest.

   Nun betrachten wir die Schreibvorgänge der einzelnen Transaktionen. Wir sehen, dass $T_1$ den Wert von $x$ schreibt und $T_2$ den Wert von $z$ und $y$ schreibt. Es gibt eine Abhängigkeit zwischen $T_1$ und $T_3$, da $T_3$ den Wert von $x$ liest, nachdem $T_1$ diesen Wert geschrieben hat. Es gibt ebenfalls eine Abhängigkeit zwischen $T_1$ und $T_2$, da $T_2$ den Wert von $z$ liest, nachdem $T_1$ diesen Wert geschrieben hat. Es gibt keine Abhängigkeit zwischen $T_2$ und $T_3$, da $T_2$ den Wert von $y$ schreibt, nachdem $T_3$ diesen Wert gelesen hat, aber $T_3$ den Wert von $y$ nicht liest, nachdem $T_2$ diesen Wert geschrieben hat.

   Da es Abhängigkeiten zwischen den Transaktionen gibt, können wir $S_1$ nicht der Klasse 1 zuordnen.

   Nun betrachten wir die Konflikte zwischen den Transaktionen. Wir sehen, dass es einen Konflikt zwischen $T_1$ und $T_3$ gibt, da beide die gleiche Variable $x$ lesen und schreiben. Es gibt ebenfalls einen Konflikt zwischen $T_1$ und $T_2$, da beide die gleiche Variable $z$ lesen und schreiben. Es gibt keinen Konflikt zwischen $T_2$ und $T_3$, da $T_2$ die Variable $y$ liest und schreibt, während $T_3$ die Variable $y$ nur liest.

   Da es Konflikte zwischen den Transaktionen gibt, können wir $S_1$ nicht der Klasse 2 zuordnen.

   Nun betrachten wir die Zyklen zwischen den Transaktionen. Wir sehen, dass es einen Zyklus der Länge 2 zwischen $T_1$ und $T_3$ gibt, da $T_1$ die Variable $x$ liest und schreibt und $T_3$ die Variable $x$ liest. Es gibt ebenfalls einen Zyklus der Länge 2 zwischen $T_1$ und $T_2$, da $T_1$ die Variable $z$ liest und schreibt und $T_2$ die Variable $z$ liest. Es gibt keinen Zyklus der Länge 3 oder höher, da es keine weiteren Abhängigkeiten zwischen den Transaktionen gibt.

   Da es Zyklen zwischen den Transaktionen gibt, können wir $S_1$ nicht der Klasse 3 zuordnen.

   Wir können also $S_1$ nur der Klasse 4 zuordnen.

2. Schedule $S_2$:

   Wir betrachten zunächst die Lesevorgänge der ein





****************************************************************************************
****************************************************************************************




