Weihnachtsknobelaufgabe WS 2019/2020

Als Gegenmaßnahme zum Klimawandel hat die Regierung beschlossen, dass ab jetzt nur noch ein Weihnachtsbaum pro Stadt ausgestellt wird. Es handelt sich dabei um ein hochmodernes 360 Grad Gebäude, in dessen Zentrum ein Weihnachtsbaum eingepflanzt wurde. Ein erster Prototyp wurde in Darmstadt errichtet. Jede der 40 Etagen mit je 12 sogenannten Weihnachtslogen bietet einen Ausblick auf den ca. 100 Meter großen Weihnachtsbaum. Um jede Familientradition zu berücksichtigen, wird der Baum partiell anders geschmückt, beschneit und beleuchtet. In sozialen Netzwerken feiert man diese Entwicklung bereits als Erfolg: #TreeSharing.

Das Buchungssystem erlaubt keine Doppelbuchungen für einen Raum. D.h. wenn ein Raum belegt ist, darf es keine weitere Buchung für diesen Raum geben. Weiterhin erlaubt der Betreiber die Buchung mehrerer Räume gleichzeitig, z.B. für große Familien oder Gruppen.

Datum:  24.12.2019...
Zeit:   10:00               12:00  12:30  ...
Raum 1: |-A-----------------|      |-B-----| |D| |--E---| |-G-| |H-| |-I---------|
Raum 2: |-A-----------------|      |-C--------------| |--F-------------|
Raum N: ... 

Problem:

Durch einen Fehler in dieser Anwendung war es bis vor Kurzem unter Umständen möglich einen Raum doppelt zu belegen. Das sorgt natürlich für Chaos an Weihnachten, und muss unbedingt verhindert werden.

Konkret könnten folgende Situationen auftreten:

Datum:  24.12.2019...
Zeit:   10:00               
Raum 1: |-A-----------------|      
Raum 1:        |-B---------------| 

Raum 2: |-C-----------------|
Raum 2:      |-D-------|

Raum 3:     |-E-----------------|
Raum 3: |-F--------|

Raum 4: |-G------|
Raum 4:  |-H---|
Raum 4:    |-I-|
Raum 4: |-J-----------|
Raum 4:           |-K-----|
Raum 4:      |-L-----|

Raum 5: |-M--------|
Raum 6: |-M--------|
Raum 6:      |-N---|

Raum N: ... 

Aufgabe:

Deshalb, und kurz vor Weihnachten, wurden Sie als Consultant beauftragt herauszufinden, ob es noch weitere Doppelbuchungen gibt. Folgende Abfragen werden benötigt:

1. Eine Liste in dem alle Buchung angezeigt werden, die mit anderen Buchungen kollidieren.
2. Eine Liste die alle Buchungen anzeigt, die mit anderen Buchungen kollidieren, und die Buchungen mit denen diese kollidieren.
3. Überprüfung, ob eine Buchung mit einer anderen kollidiert. Die Abfrage liefert nur eine Zelle mit der Anzahl der Kollisionen zurück (0=Keine Kollision).
4. Überprüfung, ob in einem gegebenen Zeitraum (Start & Ende) ein Raum verfügbar ist.

Randbedingungen:

• Das vorgegebene Schema (Spalten/Tabellen) darf nicht verändert werden
• Sie dürfen Indexe/Funktionen/Stored Procedures/etc. hinzufügen
• Die Abfragen müssen komplett in SQL ausführbar sein

Datenbanksysteme

Sie können die Aufgabe in PostgreSQL, MySQL oder Db2 lösen. Bitte verwenden Sie dabei folgende Versionen

• Postgres >= 9.6
• Db2 >= 11.1
• MySQL >= 5.6

Datenbankmodell

ER-Modell

         N            M
[Buchung]<------------>[Raum]

Datenbankschema

CREATE TABLE Statements für MySQL (für andere DBMS bitte entsprechend anpassen - statt tinytext verwenden Sie varchar(256))

• Link zu SQLFiddle: http://sqlfiddle.com/#!9/b18645

• oder hier:

CREATE TABLE IF NOT EXISTS `Buchung` (
  `EventID` int(6) unsigned NOT NULL,
  `Start` datetime NOT NULL,
  `End` datetime NOT NULL,
  `Title` tinytext COLLATE utf8mb4_unicode_520_ci NOT NULL,
  `Created` datetime NOT NULL,
  `LastModified` datetime DEFAULT NULL,
  PRIMARY KEY (`EventID`)
) DEFAULT CHARSET=utf8;

CREATE TABLE IF NOT EXISTS `Buchung_V_Raum` (
  `EventID` int(6) unsigned NOT NULL,
  `RaumID` int(6) unsigned NOT NULL,  
  PRIMARY KEY (`EventID`,`RaumID`)
) DEFAULT CHARSET=utf8;

CREATE TABLE IF NOT EXISTS `Raum` (
  `RaumID` int(6) unsigned NOT NULL,
  `Title` tinytext COLLATE utf8mb4_unicode_520_ci NOT NULL,
  `Beschreibung` tinytext COLLATE utf8mb4_unicode_520_ci NOT NULL,
  PRIMARY KEY (`RaumID`)
) DEFAULT CHARSET=utf8; 

Skalierung und Bewertung

Wir testen Ihre Lösung mit

• 20 Buchungen
• 2.000 Buchungen
• 200.000 Buchungen

Gesucht ist die Lösung, die für alle 3 Fälle im Mittel die schnellste Lösung liefert.

Einreichungen bis 13. Januar 2020

• Bitte reichen Sie Ihre Lösung bis 13. Januar 2020 per Mail ein.

Prämierung

• Für die Lösung, welche die besten Resultate (wie oben beschrieben: im Mittel für alle 3 Fälle die performanteste Lösung) erzielt, spendieren wir einen Kasten Club Mate Cola (o.ä. über das genaue Getränk lässt sich verhandeln ;)

Viel Spaß!

                Wir wünschen Ihnen
                Frohe Weihnachten
               und ein tolles Fest
       ||               ||               ||
      |--|             |--|             |--|
     |----|           |----|           |----|
    |------|         |------|         |------|    
   |--------|       |--------|       |--------|   
  |-||----||-|     |----------|     |----------|
 |------------|   |------------|   |------------|
|--------------| |--------------| |--------------|