Datenbanksysteme I

Welcome

Data Models and Languages

v2 (letztes Update: 20. Oktober 2015)

Typed Data, Declarativity, Data Independence, Persistence

v2 (letztes Update: 27. Oktober 2015)

The Relational Data Model

v1 (letztes Update: 2. November 2015)

Constraints

v1 (letztes Update: 9. November 2015)

A Diversion into SQL

v1 (letztes Update: 10. November 2015)

Referential Integrity

v1 (letztes Update: 16. November 2015)

Database Design

v3 (letztes Update: 24. November 2015)

Grouping and Aggregation

v2 (letztes Update: 30. November 2015)

Functional Dependencies

v2 (letztes Update: 14. Dezember 2015)

The Entity-Relationship Model

v2 (letztes Update: 10. Januar 2016)

The Relational Algebra

Recursive Queries

Datenmodell Text

(Shell-Skript)

Basierend auf sed und awk (Datenmodell Text).

Usage (UNIX-Shell): weight-of-set5610.sh < set5610-1.txt

(Shell-Skript)

Basierend auf awk und cut (Datenmodell Text). Extrahiert Subsequenz im Bereich ⟨from⟩..⟨to⟩ einer DNA-Sequenz.

Usage (UNIX-Shell): dna-subsequence.sh ⟨from⟩ ⟨to⟩ < ⟨GenBank-Eintrag⟩

Datenmodell JSON

Datenmodell JSON

(JSONiq-Query)

Usage (UNIX-Shell): zorba -r -i -f -q weight-of-set5610.jq

(JSONiq-Query)

Usage (UNIX-Shell): zorba -r -i -f -q worst-northern-quake-mag.jq

(JSONiq-Query)

File enthält drei Varianten der Query (zwei Varianten sind derzeit via (: ... :) auskommentiert).

Usage (UNIX-Shell): zorba -r -i -f -q worst-northern-quake-mag-place.jq

Datenmodell Tabular (CSV)

Einfache Query-Library (PyQL und relationale Algebra) für Python 2.7. Einbindung in Python-Code via

from DB1 import Table

(PyQL-Query)

Usage (UNIX-Shell): python worst-northern-quake-mag-place.py

Datenmodell Tabular (CSV)

Datenmodell Tabular (CSV)

Datenmodell Tabular (CSV)

(PyQL-Query)

Usage (UNIX-Shell): python weight-of-set5610.py

(PyQL-Query)

Optimierung basiert auf Regeln (constraints) der LEGO Mini-World: eindeutige Identifier in Tabellen bricks und minifigs sowie Disjunktheit beider Tabellen.

Usage (UNIX-Shell): python weight-of-set5610-key.py

(PyQL-Query)

Optimierung basiert auf Konstruktion einer temporären Datenstruktur (Dictionary/partielle Funktion quantity).

Usage (UNIX-Shell): python weight-of-set5610-temp.py

(PyQL-Query)

Optimierung basiert auf Konstruktion einer temporären Datenstruktur (Dictionary/partielle Funktion quantity) und der parallelen Abarbeitung der Tabellen bricks und minifigs.

Usage (UNIX-Shell): python weight-of-set5610-par.py

(PyQL-Query)

Einführung einer temporären Liste pieces als Vereinigung von bricks und minifig.

Usage (UNIX-Shell): python weight-of-set5610-pieces-list.py

(PyQL-Query)

Basiert auf einer neuen persistenten Tabelle pieces.csv, die in der UNIX-Shell durch folgendes Kommando konstruiert werden kann:

cut -f1-6 bricks.csv | last +2 | cat minifigs.csv - > pieces.csv

Usage (UNIX-Shell): python weight-of-set5610-pieces-table.py

(SQL-Skript)

Demonstration der SQL DML Kommandos INSERT, UPDATE und DELETE.

Usage (UNIX-Shell): psql -f calendar.sql

(SQL-Skript)

Demonstration des PostgreSQL Foreign Data Wrappers (CSV-File wird in den Zustand einer Relation gespiegelt, read-only: Änderungen im CSV-File werden vom RDBMS übernommen, INSERT/UPDATE/DELETE-Kommandos sind auf die Relation nicht anwendbar).

Achtung: Im SQL-Skript muss der (absolute) Pfad zum CSV-File angepasst werden.

Usage (UNIX-Shell): psql -f fdw.sql

(SQL-Skript)

Kopiert erst Schema und dann Zustand einer existierenden Tabelle, benötigt lediglich je ein DDL- und DML-Statement.

Usage (UNIX-Shell): psql -f insert-query.sql

(SQL-Skript)

Reichert Tabelle calendar mit einer Reihe von Constraints an, um die Abbildung der Kalender-Miniwelt in die Datenbank zu verfeinern.

Usage (UNIX-Shell): psql -f calendar-constraints.sql

(SQL-Skript)

Deklariert und lädt die Tabellen der LEGO-Miniwelt und fügt Kandidaten- sowie Primärschlüssel hinzu. NB: Einige SQL-Statements führen zu (erwarteten) Fehlern, siehe Kommentare.

Achtung: Im SQL-Skript müssen die (absoluten) Pfade zu den CSV-Files angepasst werden.

Usage (UNIX-Shell): psql -f keys.sql

(SQL-Skript)

Demonstriert, dass die Nennung von Subqueries in der FROM-Klausel reihenfolgeunabhängig ist.

Usage (UNIX-Shell): psql -f calendar-attendees.sql

(SQL-Skript)

Demonstriert das Konzept der row types und row values in SQL.

Usage (UNIX-Shell): psql -f row-types.sql

(SQL-Skript)

Demonstriert, das für einige Queries die Nennung von DISTINCT überflüssig sein kann, da ohnehin keine Duplikate erzeugt werden. Das RDBMS erkennt die meisten dieser Situationen nicht selbsttätig.

Usage (UNIX-Shell): psql -f distinct-vs-keys.sql

(SQL-Skript)

Demonstriert die Formulierung von Equi- und allgemeiner θ-Joins (Theta-Joins), auch zwischen mehreren Tabellen (hier: 3-Way Join).

Usage (UNIX-Shell): psql -f who-is-busy-at-what-times.sql

(SQL-Skript)

Demonstriert den Einsatz von Subqueries (⟨query⟩) in der Berechnung von Ausdrücken.

Usage (UNIX-Shell): psql -f compositional.sql

(SQL-Skript)

Demonstriert den Einsatz von WITH ... zur Konstruktion komplexerer Queries. Die in WITH gebundenen Namen sind nur lokal sichtbar und sind nicht persistent.

Usage (UNIX-Shell): psql -f large-yellow-bricks.sql

(SQL-Skript)

Demonstriert die Nutzung korrelierter Unteranfragen (die freie Variablen beinhalten, die in der umgebenden Anfrage gebunden werden).

Usage (UNIX-Shell): psql -f correlation.sql

(Python-Skript)

Demonstriert Korrelation und Kompositionalität in PyQL:

1. Unteranfragen können sich auf Variablen beziehen, die in der umgebenden Anfrage gebunden werden und
2. Unteranfragen können überall da eingesetzt werden, wo eine Anfrage ansonsten einen atomaren Wert erwartet (in PyQL: explizite Konversion von Tabelle zu Atom mittels Funktion single()).

Usage (UNIX-Shell): python correlation.py

(SQL-Skript)

Demonstriert die Deklaration und den Einsatz von Fremdschlüsseln (foreign keys), um eine konsistente Verweisstruktur zwischen Source- und Target-Tabellen zu gewährleisten.

Achtung: Im SQL-Skript müssen die (absoluten) Pfade zu den CSV-Files angepasst werden.

Usage (UNIX-Shell): psql -f foreign-keys.sql

(SQL-Skript)

Demonstriert die (manuelle) Überprüfung der referentiellen Integrität einer Datenbank mittels der SQL-Prädikate EXISTS und [NOT] IN.

Achtung: Im SQL-Skript muss ein (absoluter) Pfade zu einem CSV-File angepasst werden.

Usage (UNIX-Shell): psql -f referential-integrity.sql

(SQL-Skript)

Repräsentation von Bäumen mittels Fremdschlüsseln innerhalb einer Tabelle (tree). Baum-Operationen führen zu Self-Joins.

Usage (UNIX-Shell): psql -f intra-table-foreign-keys.sql

(SQL-Skript)

Systematische Übersetzung von Anfragen für NF²-Daten in äquivalente Anfragen über Tabellen in erster Normalform (1NF).

Usage (UNIX-Shell): psql -f functions-1NF.sql

(SQL-Skript)

Demonstration verschiedener SQL Aggregat-Funktionen (siehe auch die PostgreSQL 9.4-Dokumentation zu Aggregat-Funktionen).

Usage (UNIX-Shell): psql -f grouping-aggregation.sql

(SQL-Skript)

Demonstration von Gruppierung und Aggregation im shapes/turtles-Beispiel.

Usage (UNIX-Shell): psql -f grouping-turtle.sql

(SQL-Skript)

Gruppierung und Aggregation auf der Kalender-Datenbank

Usage (UNIX-Shell): psql -f who-is-busy-at-what-times-grouped.sql

(SQL-Skript)

Aufbau eines Mini-Data Warehouse für die LEGO-Datenbank. Einfache Report-Queries.

Usage (UNIX-Shell): psql -f dw.sql

(SQL-Skript)

Weitere Gruppierungen und Aggregationen auf dem LEGO Data Warehouse (Set mit der meisten Teilen, schwerstes Set).

Usage (UNIX-Shell): psql -f lego-aggregates.sql

(SQL-Skript)

Test: Ist die angegebene Attributmenge ein Kandidatenschlüssel für Tabelle contains?

Usage (UNIX-Shell): psql -f candidate-key-test.sql

(SQL-Skript)

Verhalten von Gruppierung und Aggregation auf leeren Tabellen und bei der Verarbeitung von NULL-Werteb.

Usage (UNIX-Shell): psql -f grouping-null.sql

(SQL-Skript)

Generiert Tabelle instructions, die einen Auszug einer LEGO-Bauanleitung darstellt. Szenario zur Demonstration von funktionalen Abhängigkeiten.

Achtung: Im Skript müssen Pfade zu den Illustrationen der Bauanleitung angepasst werden. Die Illustrationen selbst befinden sich ich im ZIP-Archiv instructions.zip.

Usage (UNIX-Shell): psql -f instructions.sql

(ZIP-Archiv mit PNG-Bildern)

Enthält die Illustrationen zur LEGO-Bauanleitung in Tabelle instructions. Werden in die Datenbank geladen durch SQL-Skript instructions.sql.

Usage (UNIX-Shell): unzip instructions.zip

(Haskell-Source)

Haskell-Implementation der Algorithmen key(K,U,F) und cover(α,F). Mehrere Beispiel-Szenarien sind vorbereitet (siehe Funktion main).

Usage (UNIX-Shell): ghc --make cover-derive-keys.hs; ./cover-derive-keys

(SQL-Skript)

Nutzt einen SQL-Trigger, um die FD rating → stars in Tabelle users zu überwachen. Achtung: Dies ist ineffizient und kein gutes Datenbank-Design.

Usage (UNIX-Shell): psql -f simulate-FD-constraint.sql

(SQL-Skript)

Nutzt den SQL-Datentyp serial zur automatischen Generierung künstlicher Schlüsselwerte.

Usage (UNIX-Shell): psql -f serial.sql

(SQL-Skript)

Relationale Implementation eines ER-Diagramms, das eine many-to-one-Relationship zwischen Entities Airport und Country beschreibt.

Usage (UNIX-Shell): psql -f airport-country.sql

(SQL-Skript)

Relationale Implementation eines ER-Diagramms, das Entity-Typ Employee sowie dessen Spezialisierungen Secretary und Engineer beschreibt. Nutzt die SQL-Klausel INHERITS.

Usage (UNIX-Shell): psql -f employee-secretary-engineer.sql

(Python-Skript, benötigt Python-Modul DB1)

Demonstriert den Selektions-Operators σ[p](R) der Relationalen Algebra (RA). Das Selektionsprädikat p wird hier in Form eines λ-Ausdrucks als anonyme Funktion angegeben:

lambda t: ...⟨Boolescher Ausdruck, der sich auf Tupel t bezieht⟩ ...

Usage (UNIX-Shell): python selection.py

(Python-Skript, benötigt Python-Modul DB1)

Demonstriert den Projektions-Operators π[ℓ](R) der Relationalen Algebra (RA). Die Projektions-Funktion ℓ kann in zwei Formen angegeben werden:

1. Als anonyme Funktion, die ein Eingabetupel t auf ein Ausgabetupel abbildet (z.B. zur Umbenennung oder Erzeugung neuer Spalten), Beispiel:

   lambda t: { 'X': t['A'], 'Z': int(t['B']) + 42 }

2. Als Liste von Namen von Spalten, die nach der Projektion erhalten bleiben — alle anderen Spalten werden "wegprojiziert"):

   ['A', 'B']

Usage (UNIX-Shell): python projection.py

(Python-Skript, benötigt Python-Modul DB1)

Demonstriert das Zusammenspiel der RA-Operatoren π, σ und ⨉ zur Implementation einer Anfrage über Graphen (findet alle Pfade der Länge 2).

Usage (UNIX-Shell): python two-hops.py

(Python-Skript, benötigt Python-Modul DB1)

Demonstriert die Funktionalität des Natural Join-Operators ⨝ (verbindet zwei Relationen, Join-Prädikat ergibt sich implizit aus der Gleichheit der gleich benannter Spalten).

Usage (UNIX-Shell): python natural-joins.py

(Java Archive)

⚠︎ Benötigt PostgreSQL.

Implementation eines Interpreters und einer REPL für die RA. Basiert auf der Abbildung von RA-Ausdrücken auf äquivalente SQL-Anfragen. Siehe auch Jun Yang: A Relational Algebra Interpreter.

Usage (UNIX-Shell): java -jar ra.jar (startet REPL) oder java -jar ra.jar -i ⟨file.alg⟩

(.alg-File für Jun Yangs Implementation der RA)

Demonstriert das Zusammenspiel der RA-Operatoren π, σ und ⨉ zur Implementation einer Anfrage über Graphen (findet alle Pfade der Länge 2).

Usage (UNIX-Shell): java -jar ra.jar -i two-hops.alg

(Python-Skript, benötigt Python-Modul DB1)

Findet die LEGO-Steine, die aus einer Kategorie mit Bezug zu "Animal" stammen. Greift auf die Tabellen sets.csv und categories.csv zu.

Usage (UNIX-Shell): python animal-bricks.py

(Python-Skript, benötigt Python-Modul DB1)

Findet die LEGO-Sets, die schwerer als das LEGO-Set "Taj Mahal" sind. RA-Query ist bereits in mehrern Schritten optimiert. Greift auf die Tabelle sets.csv zu.

Usage (UNIX-Shell): python heavy-sets.py

Datenmodell Tabular (CSV)

Datenmodell Tabular (CSV)

Datenmodell Tabular (CSV)

Datenmodell Tabular (CSV)

Datenmodell Tabular (CSV)

Datenmodell Tabular (CSV)

Datenmodell Tabular (CSV)

(Python-Skript, benötigt Python-Modul DB1)

Kategorisiert LEGO-Sets nach ihrem Volumen (small, medium, large). Greift auf Tabelle sets zu.

Usage (UNIX-Shell): python set-size-categories.py

(SQL-Skript)

Kategorisiert LEGO-Sets nach ihrem Volumen (small, medium, large). Zwei Varianten nutzen Fallunterscheidung (CASE...WHEN) und Mengenoperationen (UNION ALL).

Usage (UNIX-Shell): psql -f set-size-categories.sql

(Python-Skript, benötigt Python-Modul DB1)

Findet die LEGO-Sets, in denen kein Baustein einen Aufkleber erhält. Nicht-monotone Anfrage, demonstriert den Einsatz der relationalen Differenz. Greift auf gekürzte Varianten der Tabellen sets, contains und bricks zu.

Usage (UNIX-Shell): python no-sticker-bricks.py

(Python-Skript, benötigt Python-Modul DB1)

Findet die LEGO-Sets, in nur gelbe Bausteine enthalten sind. Nicht-monotone Anfrage, demonstriert den Einsatz der relationalen Differenz. Greift auf gekürzte Varianten der Tabellen sets, contains sowie auf Tabelle colors zu.

Usage (UNIX-Shell): python all-yellow-bricks.py

(Python-Skript, benötigt Python-Modul DB1)

Findet das schwerste LEGO-Set. Nicht-monotone Anfrage, demonstriert den Einsatz des Antijoin-Operators (▷). Greift auf gekürzte Variante der Tabelle sets zu.

Usage (UNIX-Shell): python max-weight-set.py

(Python-Skript, benötigt Python-Modul DB1)

Findet die LEGO-Sets, die alle Steine beinhalten, die benötigt werden, um das LEGO-Set 1609 zu bauen. Nicht-monotone Anfrage, demonstriert den Einsatz des Divisions-Operators (÷). Greift auf gekürzte Variante der Tabellen sets und contains zu.

Usage (UNIX-Shell): python what-can-we-build.py

(Python-Skript, benötigt Python-Modul DB1)

Listet die LEGO-Steine des Sets 336-1 auf und zeigt an, welche Steine als Ersatz eingesetzt werden können. Demonstriert den Einsatz des Left-Outerjoin-Operators (⟕). Greift auf die Tabellen contains, bricks und matches zu.

Usage (UNIX-Shell): python bricks-with-replacement.py

(SQL-Skript)

Listet die LEGO-Steine des Sets 336-1 auf und zeigt an, welche Steine als Ersatz eingesetzt werden können. Demonstriert den Einsatz des Left-Outerjoin-Operators in SQL (LEFT OUTER JOIN).

Usage (UNIX-Shell): psql -f bricks-with-replacement.sql

(SQL-Skript)

Ordnet alle Farben des LEGO-Sortiments nach Popularität (= Anzahl der Steine, die in einer Farbe verfügbar sind). Demonstriert die Interaktion des Left-Outerjoin-Operators (LEFT OUTER JOIN) und der Gruppierung/Aggregation in SQL.

Usage (UNIX-Shell): psql -f popular-colors.sql

(Python-Skript, benötigt Python-Modul DB1)

Beantwortet Teilbaum- und Pfadanfragen auf einer relationalen Baumrepräsentation. Demonstriert den Einsatz der (äquivalenten) iterate(q,r) und recurse(q,r) Query-Templates.

Usage (UNIX-Shell): python tree-queries.py

(SQL-Skript)

Beantwortet Teilbaumanfrage auf einer relationalen Baumrepräsentation. Demonstriert den Einsatz rekursiver Common Table Expressions in SQL (WITH RECURSIVE).

Usage (UNIX-Shell): psql -f tree-query-accum.sql

(SQL-Skript)

Beantwortet Pfadanfrage auf einer relationalen Graphrepräsentation (hier: DAG). Demonstriert den Einsatz rekursiver Common Table Expressions in SQL (WITH RECURSIVE).

Usage (UNIX-Shell): psql -f graph-paths-accu.sql

(SQL-Skript)

Beantwortet Pfadanfrage auf einer relationalen Graphrepräsentation (hier: zyklischer gerichteter Graph). Demonstriert den Einsatz rekursiver Common Table Expressions in SQL (WITH RECURSIVE) mit Mengensemantik (UNION [ DISTINCT ]).

Usage (UNIX-Shell): psql -f cycle-paths-accu.sql

(SQL-Skript)

Simuliert einen deterministischen endlichen Automaten (DFA) für den regulären Ausdruck (a|cd)*b. Validiert gegebenen Eingabe-String. Demonstriert den Einsatz rekursiver Common Table Expressions in SQL (WITH RECURSIVE).

Usage (UNIX-Shell): psql -f automaton.sql

(SQL-Skript)

Simuliert einen nicht-deterministischen endlichen Automaten (NFA) für einen regulären Ausdruck, der die Syntax von Fließkommazahlen beschreibt (etwa -123.56E+4). Validiert gegebenen Eingabe-String. Demonstriert den Einsatz rekursiver Common Table Expressions in SQL (WITH RECURSIVE).

Usage (UNIX-Shell): psql -f nfa.sql