Big Data & Datenbanken Tutorial für CPTS415 – OpenFlights, Normalisierung, Joins

1. Big Data und die fünf V's – Ein Beispiel aus der Luftfahrt

Stell dir vor, du arbeitest für eine Fluggesellschaft wie Lufthansa oder ein Reiseportal wie Kayak. Täglich fallen Millionen von Flugdaten an: Buchungen, Verspätungen, Routen, Wetterdaten. Das ist ein Paradebeispiel für eine Big Data Anwendung. Die fünf V's – Volume, Velocity, Variety, Veracity, Value – lassen sich hier perfekt erklären:

Volume: Die OpenFlights-Datenbank enthält über 10.000 Flughäfen und tausende Routen. Das Datenvolumen wächst stündlich.
Velocity: Flugdaten werden in Echtzeit aktualisiert – Verspätungen, Gate-Änderungen, Wetterupdates.
Variety: Strukturierte Daten (Tabellen) und unstrukturierte (Pilotberichte, Social-Media-Posts).
Veracity: Datenqualität schwankt – manche Einträge sind veraltet oder inkorrekt (z.B. fehlende IATA-Codes).
Value: Aus den Daten lassen sich Flugrouten optimieren, Treibstoff sparen und Kundenerlebnisse verbessern.

Für die Speicherung würde ich eine Mischung aus relationalen (für Buchungen, Flüge) und NoSQL-Datenbanken (für Logs) empfehlen, aber im Kern bleibt das relationale Modell für strukturierte Daten unschlagbar.

2. Relationales Datenmodell am Beispiel OpenFlights

Die OpenFlights Airport-Tabelle ist ein klassisches Beispiel für eine Relation. Jede Zeile (Tupel) repräsentiert einen Flughafen. Die Attribute sind: Airport ID, Name, City, Country, IATA, ICAO, Latitude, Longitude, Altitude, Timezone, DST, Tz_database_timezone, Type, Source.

2a. Schlüsselbegriffe verstehen

Relation Schema: Airport (Airport_ID, Name, City, Country, IATA, …)
Relational Database Schema: Menge aller Relationen (Airport, Airline, Route)
Domain: Wertebereich eines Attributs, z.B. IATA ist ein 3-stelliger String
Attribut: Spalte wie Name oder City
Attribut Domain: Z.B. Latitude ist eine Dezimalzahl zwischen -90 und 90
Relation Instance: Konkrete Tabelle mit Werten, z.B. (1, 'Los Angeles International', 'Los Angeles', 'USA', 'LAX', …)

Ein kleines Beispiel (4–5 Tupel):

Airport_ID | Name                | City        | Country | IATA | ICAO | Latitude | Longitude
1          | Los Angeles Intl    | Los Angeles | USA     | LAX  | KLAX | 33.9425  | -118.4081
2          | John F Kennedy Intl | New York    | USA     | JFK  | KJFK | 40.6398  | -73.7789
3          | Heathrow            | London      | UK      | LHR  | EGLL | 51.4700  | -0.4543
4          | Tokyo Haneda        | Tokyo       | Japan   | HND  | RJTT | 35.5523  | 139.7795

2b. Schema der drei Datenbanken

Airport: Airport_ID (PK), Name, City, Country, IATA, ICAO, Latitude, Longitude, Altitude, Timezone, DST, Tz_database_timezone, Type, Source

Airline: Airline_ID (PK), Name, Alias, IATA, ICAO, Callsign, Country, Active

Route: Airline (FK zu Airline.IATA?), Airline_ID (FK), Source_airport (FK zu Airport.IATA?), Source_airport_ID (FK), Destination_airport (FK), Destination_airport_ID (FK), Codeshare, Stops, Equipment

Funktionale Abhängigkeiten (FDs):

Airport_ID → Name, City, Country, IATA, ICAO, …
IATA → Airport_ID (falls IATA eindeutig)
Airline_ID → Name, IATA, Country
Route: (Airline_ID, Source_airport_ID, Destination_airport_ID) → Stops, Equipment

2c. FD-Inferencing mit Armstrongs Axiomen

Gegeben: FDs aus 2b: A: Airport_ID → IATA; B: IATA → Country (angenommen). Dann gilt:

Reflexivität: {Airport_ID, Name} → Airport_ID (trivial)
Transitivität: Aus A und B folgt: Airport_ID → Country

Beweis der Zerlegungsregel: Wenn X → YZ, dann gilt X → Y und X → Z. Beweis: Aus X → YZ und YZ → Y (Reflexivität) folgt X → Y (Transitivität). Analog für Z.

Pseudo-Transitivität: Wenn X → Y und YW → Z, dann XW → Z. Beweis: Aus X → Y folgt XW → YW (Augmentation). Mit YW → Z ergibt Transitivität XW → Z.

2d. Normalisierung (3NF und BCNF)

Gegeben: R(A1, A2, A3, A4) mit FDs: (A2,A3)→A4; (A3,A4)→A1; (A1,A2)→A3.

Kandidatenschlüssel: (A1,A2) und (A2,A3). Prüfung: (A1,A2)→A3 (gegeben), (A1,A2)→A4? Über (A1,A2)→A3 und (A3,A4)→A1? Nein, aber aus (A1,A2)→A3 und (A2,A3)→A4 folgt (A1,A2)→A4. Also sind (A1,A2) und (A2,A3) Schlüssel.

BCNF: Jede FD muss X→Y mit X Superschlüssel sein. (A2,A3)→A4: (A2,A3) ist Superschlüssel, ok. (A3,A4)→A1: (A3,A4) ist kein Superschlüssel? Prüfe: (A3,A4) → A1, aber nicht → A2, also kein Superschlüssel. Daher ist R nicht in BCNF. Zerlegung: R1(A3,A4,A1), R2(A1,A2,A3). In R1 ist (A3,A4) Schlüssel, in R2 (A1,A2) Schlüssel. Beide in BCNF.

3NF: R ist in 3NF, da alle FDs entweder trivial sind, X Superschlüssel ist oder Y Teil eines Schlüssels ist. In (A3,A4)→A1 ist A1 Teil des Schlüssels (A1,A2)? Nein, A1 ist Teil von (A1,A2). Daher 3NF erfüllt.

3. Relationale Algebra: Kino-Anfragen

Stell dir vor, du suchst nach dem Film „Zootopia“ (der 2026 immer noch beliebt ist). Gegeben: Movies(Title, Director, Actor), Location(Theater, Address, Phone), Schedule(Theater, Title, Time).

Q1: Welche Kinos zeigen „Zootopia“?
πTheater(σTitle='Zootopia'(Schedule))
Q2: Namen und Adressen von Kinos mit Filmen von Steven Spielberg.
πTheater, Address(Location ⋈ (σDirector='Steven Spielberg'(Movies) ⋈ Schedule))
Q3: Adresse und Telefon von „Le Champo“.
πAddress, Phone(σTheater='Le Champo'(Location))
Q4: Paare von Schauspielern, die im selben Film spielen.
ρM1(Movies) ⋈M1.Title=M2.Title ∧ M1.Actor < M2.Actor ρM2(Movies) → πM1.Actor, M2.Actor

4. Join-Operatoren: Kostenvergleich

Gegeben: R (20.000 Tupel, 10 Tupel/Block → 2.000 Blöcke), S (100.000 Tupel → 10.000 Blöcke), 52 Puffer. Keine Indizes.

4a. Block Nested Loop Join

Algorithmus: Für jeden Block von R (2.000 Blöcke) lade 51 Blöcke von S (da einer für R). Kosten: R einmal lesen (2.000) + für jeden R-Block (2.000) * (ceil(10.000/51) = 197) = 2.000 + 2.000*197 = 396.000 I/Os.

4b. Sort-Merge Join

Sortieren: R sortieren: 2.000 Blöcke, mit 52 Puffern: 2*2.000*log51(2.000) ≈ 2*2.000*2 = 8.000 I/Os. S sortieren: 2*10.000*log51(10.000) ≈ 2*10.000*2 = 40.000 I/Os. Merge: 2.000+10.000=12.000 I/Os. Gesamt: 60.000 I/Os.

4c. Hash Join

Partitionierungsphase: R in 51 Partitionen (da 1 Puffer für Input, 51 für Output). Kosten: 2*2.000=4.000 I/Os. S: 2*10.000=20.000 I/Os. Build/Probe: Jede Partition von R und S in den Speicher (51 Blöcke reichen, da Partitionen kleiner). Kosten: 2.000+10.000=12.000 I/Os. Gesamt: 36.000 I/Os.

Fazit: Hash Join ist am günstigsten, aber Sort-Merge kann bei sortierten Daten Vorteile bringen.

5. XML und RDF: Semantische Datenrepräsentation

Nehmen wir das Airport-Beispiel aus Assignment 1. Ein XML-Dokument ohne Schema könnte so aussehen:

<airports>
  <airport>
    <id>1</id>
    <name>Los Angeles International</name>
    <city>Los Angeles</city>
    <country>USA</country>
    <iata>LAX</iata>
  </airport>
  ...
</airports>

Ein XML-Schema (XSD) würde die Struktur definieren, Primärschlüssel als xs:key und Fremdschlüssel als xs:keyref. Für die natürlichen Sprachsätze (Familienbeziehungen) eignet sich RDF. Ein Graph mit Klassen wie Human, Man, Woman und Properties wie likes, hasSex, fatherOf, motherOf, marriedTo, birthYear. Die Regel „Wenn verheiratet, dann mögen sie sich“ wird als RDF-Schema-Constraint abgebildet.

6. Graph-Algorithmen: Label-constrained Reachability

Gegeben ein gerichteter Graph mit Kantenbeschriftungen. Eine Anfrage Q(u,v,L) prüft, ob ein Pfad von u nach v existiert, dessen Kantenlabels alle in L sind. Ein einfacher BFS:

Algorithmus: labelBFS(u, v, L)
  markiert[u] = true
  queue = [u]
  while queue nicht leer:
    node = queue.dequeue()
    if node == v: return true
    for each Kante (node, w) mit label in L:
      if nicht markiert[w]:
        markiert[w] = true
        queue.enqueue(w)
  return false

Dieser Algorithmus hat Laufzeit O(|V|+|E|). Für große Graphen (z.B. soziale Netzwerke) kann man Indexstrukturen wie Labeled Graph Indexing verwenden.

Mit diesen Grundlagen bist du bestens gerüstet für die CPTS415 Assignments. Denk dran: Übung macht den Meister – probier die Konzepte selbst in einer Datenbank aus!