Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken ::

Datenbanken

• Datenstrukturen

• Algorithmen

• Anwendungen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Motivation

Motivation

Datenbanken sind eine wichtige "Anwendung" für Algorithmen und Datenstrukturen.

• Viele Algorithmen und Datenstrukturen aus dem Kurs finden sich in Datenbankprogrammen wieder
  • Extern sichtbar für die Datenorganisation durch/über die Nutzer
  • Intern unsichtbar aber elementar wichtig für die extern sichtbare Datenorganisation

Links: Mehrere Anwendungen verwalten ihre Daten selbst in Dateien. Rechts: Die Daten aller Anwendungen werden in einer gemeinsamen Datenbank von einem Datenbankmanagement-System verwaltet.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Motivation

Motivation

Die wichtigsten Vorteile von Datenbankmanagement-Systemen im Vergleich zu einer dateiorientierten Strategie sind:

1. Die Daten werden in der Regel unabhängig von den Anwendungen gespeichert, die diese verwenden.

   • Die Daten sollten damit möglichst unabhängig von der verwendeten Programmiersprache sein, da sich diese im Laufe der Zeit eventuell ändert.
   • Die Anwendung kann durch eine neuere Software mit größerer Operationalität und Performant ersetzt oder ergänzt werden, dieselben Daten können aber langfristig weiter verwendet werden.

2. Die Daten werden in der Regel nur einmal zentral verwaltet und nicht redundant an mehreren unabhängigen Stellen. Damit sinkt das Risiko von Inkonsistenzen (mehrere unterschiedlich geänderte Kopien derselben Daten). Zusätzlich wird dadurch weniger Speicherplatz benötigt.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Motivation

Motivation

3. Die Daten werden nicht nur persistent gespeichert, das Datenbankmanagement-System (DBMS) sorgt für die Konsistenz der Daten, auch wenn die Anwendung mitten in einer Operation abstürzt. Auch wenn die Datenbank zerstört ist, kann sie mithilfe von Backup und Recovery wieder hergestellt werden.

4. Das DBMS ermöglicht, dass viele Anwendungen bzw. Benutzer quasi gleichzeitig lesend und auch schreibend zugreifen können. Hierzu werden Konzepte wie Transaktionen angeboten.

5. Das DBMS kontrolliert die Zugriffe auf die Daten und sorgt dafür, dass definiert werden kann, welcher Nutzer bzw. welche Anwendung welche Daten ansehen oder ändern darf.

DBMS: Datenbankmanagement-System, die Softwareschnittstelle und das Ausführungsprogramm

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Motivation

Motivation

6. Die Programmierung der Anwendungen wird vereinfacht, da das DBMS das Anlegen, Ändern, Löschen und Suchen von Daten implementiert und optimiert. Die Implementierung der Operationen ist nicht festgelegt und kann geändert werden (z.B. Bäume statt Listen verwenden)
   • Über die Sektoren der Festplatte und die Speicherseiten des Betriebssystems zerbrechen sich jetzt die Entwickler des Herstellers des DBMS den Kopf. Die Benutzer und Entwickler der Anwendungen kennen nur eine konzeptuelle Sicht auf die Daten in Form von Knoten eines Graphen, von Zeilen in Tabellen oder von Schlüssel-Wert-Paaren.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Daten und Datenstrukturen

Daten und Datenstrukturen

je nach Datenbankmodell können verschiedene Daten und Datenstrukturen gespeichert und verarbeitet werden:

1. Name / Wert-Paare dienen dazu Daten wiederzufinden. Dazu müssen diese eindeutig identifizierbar sein. Im einfachsten Fall ist das ein eindeutiger Name (wie die Pfad- und Dateinamen in einem Dateisystem). Das kann auch ein aus den Daten selbst berechneter Hash-Wert sein. Damit wäre jede Entität bzw. jedes Objekt jeweils ein Wert. Als identifizierender Name kann eventuell eines der Attribute verwendet werden.

2. Die Tabelle ist eine sehr häufige Darstellungsform von Daten, besonders im Bereich betriebswirtschaftlicher Anwendungen. Aus einem Entitätstyp bzw. einer Klasse wird im einfachsten Fall eine Tabelle. Aus jedem Attribut wird eine Spalte. Objekte bzw. Entitäten sind jeweils die Zeilen. Tabellen sind die Grundlage der relationalen Datenbankmanagement-Systeme.

3. Die Baumstruktur: Von einer Wurzel aus sind die anderen Knoten erreichbar. Aus einem Entitätstyp bzw. einer Klasse wird eine Menge von Bäumen. Ein Objekt bzw. eine Entität wird als Baum dargestellt werden: Jedes Attribut ist ein innerer Knoten oder ein Blatt. Baumstrukturen bieten verbesserte Sucheigenschaften.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Daten und Datenstrukturen

Daten und Datenstrukturen

4. Ein Gerichteter Graph: Wenn die Objekte bzw. Entitäten sich untereinander häufig referenzieren, kann dies gut als gerichteter Graph dargestellt werden mit den Objekten bzw. Entitäten als Knoten und den jeweiligen Referenzen als (annotierte) Kanten.

5. Zeitreihe und zeitabhängige Daten: Ein Sensor misst eine physikalische Größe, zu speichern sind Zeitpunkt und Messwert. Das wäre ein Objekt bzw. eine Entität. Eventuell kommen noch Metadaten dazu wie die Geoposition und die physikalische Einheit in der der Sensor misst. Regelmäßiges Messen erzeugt so eine Zeitreihe.

6. (Text) Dokumente: (Internet-) Anwendungen erzeugen teilweise große Mengen von mehr oder weniger strukturierten Textdokumenten, auch die Log-Ausgaben zählen dazu. Damit wäre ein Textdokument, z. B. ein Text über einen Mitarbeiter ein Objekt bzw. die Entität. Möglicherweise gibt es dazu eine Klasse, die Strukturvorgaben an das Dokument macht.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Daten und Datenstrukturen

Daten und Datenstrukturen

Überblick über verschiedene Möglichkeiten Daten darzustellen. a) als Menge von Name-Wert Paaren, b) als Tabelle oder in mehreren Tabellen, c) als Zeitreihe, d) als Menge von Bäumen, e) als ungerichteten oder gerichteten annotierten Graphen oder f) als Menge von (Text-) Dokumenten

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Zugriffsmuster auf gespeicherte Daten

Zugriffsmuster auf gespeicherte Daten

Was sind nun Kriterien zur Wahl einer bestimmten Repräsentation der Daten als Baum, Graph oder Tabelle?

Darstellung als Tabellen

• Ein Entitätstype besteht aus einer Klasse mit Attributen

• Im einfachsten Fall wird aus jedem Entitätstyp eine Tabelle modelliert

• Die Attribute werden jeweils zu Spalten. Ein identifizierendes Attribut ist dabei der Primärschlüssel der Tabelle.

Entity-Relationship-Modell der Relationen Mitarbeiter und Abteilung

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Zugriffsmuster auf gespeicherte Daten

• Die Beziehung zwischen Mitarbeiter und Abteilung ist 1 zu N,

  • ein Mitarbeiter ist genau in einer Abteilung und in einer Abteilung können beliebig viele Mitarbeiter sein.

• Dies wird über einen Fremdschlüssel dargestellt, die Tabelle Mitarbeiter hat eine Spalte mit Abt. Nr. Werten, diese sind Primärschlüssel in der Abteilung-Tabelle.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Zugriffsmuster auf gespeicherte Daten

kap16db Abbildung des ER-Modells auf Tabellen und auf eine Baumstruktur

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Relationale Datenbankmanagement-Systeme

Relationale Datenbankmanagement-Systeme

• Das relationale Datenbankmodell und darauf aufbauende relationale Datenbankmanagement-Systeme (RDBMS) gehen auf eine in 1970 veröffentlichte Arbeit von E. F. Codd zurück.

  • Codd legte damit das mathematische Fundament in Form der relationalen Algebra

• Unter einer Relation versteht man im Zusammenhang mit dem relationalen Datenmodell eine logische Zusammenfassung von Informationen in einer Form, die in etwa einer Tabelle vergleichbar ist.

  • Gemeint ist auch eine Relation im mathematischen Sinne, also eine Menge von Tupeln.

• Zur eindeutigen Identifikation aller Zeilen der Relation sollte diese einen Primärschlüssel (Pri-mary Key) besitzen (vorhandenes Attribut oder erzeugte Nummer ID).

  • Um den Zugriff zu beschleunigen, kann man neben dem Primärschlüssel weitere eindeutige Schlüssel einführen, sog. Zweitschlüssel (Secondary Keys).

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Relationale Datenbankmanagement-Systeme

Relationen

Die Relation Mitarbeiter hat vier Attribute (Namen PersonalNr , Name , Gehalt und AbteilungsNr) drei Zeilen (also insgesamt drei 4-Tupel). Die Relation Abteilung hat drei Attribute (AbteilungsNr , Name und Standort) sowie vier Zeilen (also insgesamt fünf 3-Tupel). Die (Primär)Schlüssel der beiden Tabellen sind jeweils für jede Zeile eindeutig: PersonalNr ist Schlüssel der Relation Mitarbeiter und AbteilungsNr ist Schlüssel von Abteilung.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Beziehungen (Relationships)

Beziehungen (Relationships)

• Relationen und ihre Tupel bzw. Tabellen und ihre Zeilen können nicht isoliert betrachtet werden.

• Relationen können also in Beziehung zu einander stehen, wie dies schon in den ER-Modellen in Form der Beziehungen (Relationships) zwischen den Entitäten zum Ausdruck kommt. Abhängig von den Kardinalitäten unterscheidet man:

• 1:1 Beziehungen ⇒ Zu einem Tupel gehört genau ein anderes Tupel.

• 1:N Beziehung ⇒ Zu einem Tupel gehört mindestens ein (≥ 1) anderes Tupel.
• M:N Beziehung ⇒ Zu einem Tupel gehören beliebig viele (≥ 0) andere Tupel umgekehrt gilt dasselbe.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Relationale Algebra

Relationale Algebra

• In unserem Fall ist die Grundmenge die Menge aller Relationen (Tabellen), die Operationen bilden eine oder mehrere Relationen wieder auf Relationen ab und können flexibel miteinander verknüpft werden.

• Die relationale Algebra legt ein mathematisches Fundament für relationale DBMS.

• Eine Datenbank-anfrage kann mathematisch vergleichsweise einfach modelliert werden.

  • Mithilfe der Operationen der Algebra kann diese dann z. B. durch Rechenregeln in eine andere Anfrage umgeformt werden, die dasselbe Ergebnis liefert aber effizienter ausgeführt werden kann.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Relationale Algebra

Relationale Algebra

Selektion σ

Mit der Selektion σ werden aus einer Relation entsprechend einer Bedingung (Prädikat) ein oder mehrere Tupel herausgegriffen.

Anwendung der Selektion auf die Relation Mitarbeiter

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Relationale Algebra

Relationale Algebra

Projektion π

Mit der Projektion π können Attribute Attr_i (in einer Tabelle wären das Spalten) aus einer Relation herausgegriffen werden.

Anwendung der Projektion auf die Relation Mitarbeiter

Stefan Bosse - Algorithmen und Datenstrukturen - Modul DB Datenbanken :: Relationale Algebra

Relationale Algebra

Kartesisches Produkt (Kreuzprodukt ×)

Mit dem (kartesischen) Produkt × wird analog zum kartesischen Produkt zweier Mengen das Produkt zweier Relationen gebildet. Die resultierende Relation Rel 1 × Rel 2 enthält dann sämtliche Kombinationen, die sich aus den Tupeln der beiden Relationen bilden lassen.