FLBK-Wiki - Letzte Änderungen [de]

Quicksort

Flbkwikiadmin — Tue, 05 May 2026 07:28:30 GMT

Laufzeitanalyse

Angebotsvergleich

Flbkwikiadmin — Thu, 30 Apr 2026 08:12:41 GMT

Beispiele

← Nächstältere Version		Version vom 30. April 2026, 10:12 Uhr
Zeile 11:		Zeile 11:

	==Beispiele==		==Beispiele==
	Wir betrachten im ~~folgenden~~ zwei Beispiele für einen Angebotsvergleich.		Wir betrachten im Folgenden zwei Beispiele für einen Angebotsvergleich.

	===Angebotsvergleich mit Barwerten durchführen===		===Angebotsvergleich mit Barwerten durchführen===
	Wir haben uns ein Fahrrad gekauft. Der Zinssatz beträgt 4 % pro Jahr. Es besteht die Möglichkeit in einem Jahr 450 € oder in zwei Jahren 480 € zu zahlen.		Wir haben uns ein Fahrrad gekauft. Der Zinssatz beträgt 4 % pro Jahr. Es besteht die Möglichkeit, in einem Jahr 450 € oder in zwei Jahren 480 € zu zahlen.

	Wir verwenden die [[Zinseszinsrechnung#Zinseszinsformel\|Zinseszinsformel]] und berechnen jeweils das [[Zinseszinsrechnung\|Anfangskapital]]:		Wir verwenden die [[Zinseszinsrechnung#Zinseszinsformel\|Zinseszinsformel]] und berechnen jeweils das [[Zinseszinsrechnung\|Anfangskapital]]:

	#Möglichkeit mit <math>q=1,04,~n=1 \text{ und } K(1)=450</math>: <br><math>K(n)=K(0)\cdot q^n</math><br><math>450=K(0)\cdot 1,04^1~\|~:1,04</math><br><math>\frac{450}{{1,04}}=K(0)</math><br><math>432,69\approx K(0)</math>		#Möglichkeit mit <math>q=1,04,~n=1 \text{ und } K(1)=450</math>: <br><math>K(n)=K(0)\cdot q^n</math><br><math>450=K(0)\cdot 1,04^1~\|~:1,04</math><br><math>\frac{450}{{1,04}}=K(0)</math><br><math>432,69\approx K(0)</math>
	#Möglichkeit mit <math>q=1,04,~n=2 \text{ und } K(2)=480</math>: <br><math>K(n)=K(0)\cdot q^n</math><br><math>~~450~~=K(0)\cdot 1,04^2~\|~:1,04^2</math><br><math>\frac{~~450~~}{{1,04^2}}=K(0)</math><br><math>443,79\approx K(0)</math>		#Möglichkeit mit <math>q=1,04,~n=2 \text{ und } K(2)=480</math>: <br><math>K(n)=K(0)\cdot q^n</math><br><math>480=K(0)\cdot 1,04^2~\|~:1,04^2</math><br><math>\frac{480}{{1,04^2}}=K(0)</math><br><math>443,79\approx K(0)</math>

	Wir wählen Möglichkeit 1 ~~wählen~~, weil das Anfangskapital mit ca. 432,69 € geringer ist als das Anfangskapital ~~über~~ 443,79 € bei Möglichkeit 2.		Wir wählen Möglichkeit 1, weil das Anfangskapital mit ca. 432,69 € geringer ist als das Anfangskapital von 443,79 € bei Möglichkeit 2.

	===Angebotsvergleich ohne Barwerte durchführen===		===Angebotsvergleich ohne Barwerte durchführen===
	Wir haben uns ein Fahrrad gekauft. Der Zinssatz beträgt 4 % pro Jahr. Es besteht die Möglichkeit in einem Jahr 450 € oder in zwei Jahren 480 € zu zahlen.		Wir haben uns ein Fahrrad gekauft. Der Zinssatz beträgt 4 % pro Jahr. Es besteht die Möglichkeit, in einem Jahr 450 € oder in zwei Jahren 480 € zu zahlen.

	Alternativ zur vorherigen Rechnung können wir die Zahlungen aufzinsen und anschließend vergleichen:		Alternativ zur vorherigen Rechnung können wir die Zahlungen aufzinsen und anschließend vergleichen:

Insertion-sort

Flbkwikiadmin — Tue, 28 Apr 2026 08:52:09 GMT

Flbkwikiadmin verschob die Seite Insertion-sort nach Insertionsort

Neue Seite

== Einführung ==
Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist relativ simpel. Das Prinzip von Insertion Sort ist folgendes: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links verschoben – und zwar so lange, bis das einzufügende Element größer oder gleich dem Element ist, das an der aktuell betrachteten Position steht.

Der Platz für das Element, das verschoben wird, ist währenddessen frei. Diese Lücke wird anschließend mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

== Beispiel ==
[[Datei:Animation Insertio-Sort.gif|mini]]
Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite (grün dargestellt) befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links verschoben wurde. Das aktuell eingefügte Element ist fett markiert.

{| class="wikitable" style="text-align:center; font-family:monospace;"
|-
| ''5'' || 7 || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''5''' || '''7''' || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''''0''''' || 5 || 7 || 3 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || '''''3''''' || 5 || 7 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || 3 || '''''4''''' || 5 || 7 || 2 || 6 || 1 || (2)
|-
| 0 || '''''2''''' || 3 || 4 || 5 || 7 || 6 || 1 || (4)
|-
| 0 || 2 || 3 || 4 || 5 || '''''6''''' || 7 || 1 || (1)
|-
| 0 || '''''1''''' || 2 || 3 || 4 || 5 || 6 || 7 || (6)
|}

== Pseudocode ==
Der [[Algorithmus]] sieht im Pseudocode so aus:

<syntaxhighlight lang="text">
prozedur insertionSort(A ist Liste sortierbarer Elemente)
n = Länge von A
für i von 1 bis n - 1 wiederhole
einzusortierenderWert = A[i]
j = i - 1
solange j ≥ 0 und A[j] > einzusortierenderWert wiederhole
A[j + 1] = A[j]
j = j - 1
ende solange
A[j + 1] = einzusortierenderWert
ende für
ende prozedur
</syntaxhighlight>

== Komplexität ==

=== Best Case ===
Die optimale Eingabe ist ein bereits sortiertes [[Array]]. In diesem Fall wird pro Iteration lediglich ein Vergleich durchgeführt, und die innere Schleife wird nie betreten. Die Gesamtanzahl der Vergleiche ist somit proportional zur Anzahl der Elemente <math>n</math>.

Insertion Sort besitzt im Best Case daher eine lineare Laufzeit von <math>O(n)</math>.

=== Average Case ===
Das Average-Case-Szenario geht von einer zufälligen Verteilung der Werte in der Liste aus.

Im Durchschnitt ist das aktuell betrachtete Element kleiner als die Hälfte der bereits sortierten Elemente. Die innere Schleife muss das Element also im Mittel nur bis in die Mitte des bisher sortierten Teilbereichs verschieben. Die Anzahl der Vergleiche und Verschiebungen halbiert sich im Vergleich zum Worst Case dadurch in etwa.

Da in der asymptotischen Landau-Notation konstante Faktoren (wie diese Halbierung) ignoriert werden, dominiert weiterhin die höchste Potenz das Wachstum. Die Zeitkomplexität liegt im Average Case demnach bei <math>O(n^2)</math>.

=== Worst Case ===
Eine Liste in umgekehrter (absteigender) Reihenfolge stellt das Worst-Case-Szenario für Insertion Sort dar, beispielsweise:

<math>[11, 7, 5, 3, 2, 0]</math>

Wir betrachten nur die Vergleichsoperationen, die mit der Variablen <math>c</math> gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt <math>n</math>.

Beim ersten äußeren Schleifendurchlauf ist <math>c = 1</math>, da nur ein Vergleich durchgeführt wird. Beim zweiten Durchlauf sind es 2 Vergleiche, beim dritten 3 usw., bis zum letzten Durchlauf mit <math>n - 1</math> Vergleichen.

Die Gesamtanzahl der Vergleiche ergibt sich zu:

<math>1 + 2 + 3 + \dots + (n - 1)</math>

Dies ist eine [[Arithmetische-reihe|arithmetische Reihe]]. Mit der gaußschen Summenformel erhält man:

<math>\frac{n(n-1)}{2}</math>

Für große <math>n</math> dominiert der quadratische Term, sodass Insertion Sort im Worst Case in der Komplexitätsklasse <math>O(n^2)</math> liegt.

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Selection-sort

Flbkwikiadmin — Tue, 28 Apr 2026 08:51:59 GMT

Flbkwikiadmin verschob die Seite Selection-sort nach Selectionsort

Neue Seite

== Einführung ==
Ein einfacher [[Sortieren|Sortieralgorithmus]] ist der Selection Sort (Sortieren durch Auswählen). Dieser Algorithmus sucht zunächst das kleinste Element in der Liste, merkt es sich und tauscht es mit dem Element am Anfang aus, sodass sich das kleinste Element an der ersten Stelle befindet.

Anschließend wird das zweitkleinste Element im verbleibenden, noch unsortierten Teil der Liste gesucht und mit dem Element an der zweiten Stelle vertauscht, und so weiter. Auf diese Weise erhalten die Elemente auf der linken Seite der aktuellen Position schrittweise ihren festen Platz und werden nicht mehr verändert.

== Beispiel ==
[[Datei:Array Selectionsort.gif|mini]]
Es soll eine Liste mit dem Inhalt <code>[4, 3, 1, 5, 2]</code> sortiert werden.

Im ersten Durchlauf wird die komplette Liste durchsucht, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel ist das der Wert 1. Der ursprüngliche Wert der Startposition (hier die 4) wird mit dem Wert an der Position des kleinsten Elements (hier die 1 am Index 2) vertauscht.

[[Datei:Animation Selectionsort.gif|mini]]
Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun bei Index 1. An Index 0 befindet sich bereits das kleinste Element der gesamten Liste, daher ist dort keine Suche mehr erforderlich. Der restliche Teil der Liste wird durchsucht. Es wird die 2 als kleinstes Element ausgewählt und mit der neuen Startposition vertauscht.

Die Suche wiederholt sich nach diesem Prinzip, bis alle Elemente sortiert sind. Der Suchbereich verkleinert sich dabei Schritt für Schritt um ein Element. Die folgende Animation visualisiert den Algorithmus.

== Pseudocode ==
Der [[Algorithmus]] sieht im Pseudocode so aus:

<syntaxhighlight lang="text">
prozedur selectionSort(A ist Liste sortierbarer Elemente)
n = Länge von A
für einfuegeIndex von 0 bis n - 2 wiederhole
minPosition = einfuegeIndex
für idx von einfuegeIndex + 1 bis n - 1 wiederhole
falls A[idx] < A[minPosition] dann
minPosition = idx
ende falls
ende für
falls minPosition ≠ einfuegeIndex dann
vertausche A[minPosition] und A[einfuegeIndex]
ende falls
ende für
ende prozedur
</syntaxhighlight>

== Java-Implementierung ==
<syntaxhighlight lang="java">
public ArrayList<Mitarbeiter> sortierenNachNachnamen() {
ArrayList<Mitarbeiter> sortierteListe = new ArrayList<>(mitarbeiterListe);
int stelle = 0;

while (stelle < sortierteListe.size() - 1) {
int kleinstesElement = stelle;

for (int index = stelle + 1; index < sortierteListe.size(); index++) {
if (sortierteListe.get(index).getNachname()
.compareTo(sortierteListe.get(kleinstesElement).getNachname()) < 0) {
kleinstesElement = index;
}
}

if (kleinstesElement != stelle) {
Mitarbeiter puffer = sortierteListe.get(kleinstesElement);
sortierteListe.set(kleinstesElement, sortierteListe.get(stelle));
sortierteListe.set(stelle, puffer);
}

stelle++;
}

return sortierteListe;
}
</syntaxhighlight>

== Komplexität ==
Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des Algorithmus Selection Sort.

Ein besonderes Merkmal dieses Algorithmus ist, dass seine Laufzeit **unabhängig** von der anfänglichen Sortierung der Elemente ist. Um eine Datenstruktur (z. B. ein [[Array]]) mit <math>n</math> Einträgen zu sortieren, muss <math>n - 1</math> Mal das Minimum durch Vergleichen bestimmt werden.

Bei der ersten Bestimmung des Minimums sind <math>n - 1</math> Vergleiche notwendig, bei der zweiten <math>n - 2</math> Vergleiche, und so weiter bis zum letzten Durchlauf mit exakt 1 Vergleich. Mit der [[Arithmetische-reihe|gaußschen Summenformel]] erhält man die Gesamtanzahl der immer notwendigen Vergleiche:

<math>(n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n</math>

=== Best Case ===
Das Best-Case-Szenario tritt ein, wenn das Array bereits vollständig aufsteigend sortiert ist.
Auch wenn alle Elemente bereits am richtigen Platz stehen, "weiß" der Selection Sort dies nicht. Er muss trotzdem in jedem Durchlauf den kompletten unsortierten Rest der Liste überprüfen, um sicherzustellen, dass nicht doch ein noch kleineres Element existiert. Es finden zwar keine Vertauschungen (Swaps) statt, die Anzahl der Vergleiche bleibt jedoch bei <math>\frac{n(n - 1)}{2}</math>. Da die Vergleiche asymptotisch dominieren, liegt die Zeitkomplexität im Best Case bei <math>\mathcal{O}(n^2)</math>.

=== Average Case ===
Im durchschnittlichen Fall (Average Case) liegt eine zufällig durchmischte Liste vor.
Genau wie im Best Case muss der Selection Sort die gesamte arithmetische Reihe an Vergleichen durchführen, um das Minimum in jedem Schritt zu finden. Die Anzahl der durchgeführten Vertauschungen liegt im Schnitt zwischen 0 und <math>n - 1</math>. Auch hier ändert dies nichts an der dominanten quadratischen Anzahl der Vergleiche. Die Zeitkomplexität im Average Case ist somit ebenfalls <math>\mathcal{O}(n^2)</math>.

=== Worst Case ===
Das Worst-Case-Szenario liegt vor, wenn die Liste in umgekehrter (absteigender) Reihenfolge sortiert ist.
Der Algorithmus führt wieder exakt <math>\frac{n(n - 1)}{2}</math> Vergleiche aus. In diesem Fall muss bei fast jedem Durchlauf (maximal <math>n - 1</math> Mal) das kleinste Element mit dem aktuellen Start-Element vertauscht werden. Da die maximale Anzahl der Vertauschungen linear (<math>\mathcal{O}(n)</math>) wächst, die Anzahl der Vergleiche jedoch quadratisch, bestimmt der quadratische Term das Laufzeitverhalten. Die Komplexitätsklasse im Worst Case liegt demnach bei <math>\mathcal{O}(n^2)</math>.

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Bubble-sort

Flbkwikiadmin — Tue, 28 Apr 2026 08:51:48 GMT

Flbkwikiadmin verschob die Seite Bubble-sort nach Bubblesort

Neue Seite

== Einführung ==
Der Bubble Sort (Sortieren durch Aufsteigen) ist ein verhältnismäßig einfacher [[Sortieren|Sortieralgorithmus]]. In der sogenannten Bubble-Phase wird die Eingabeliste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuell betrachtete Element mit seinem rechten Nachbarn verglichen. Falls die beiden Elemente das vorgegebene Sortierkriterium verletzen (z. B. das linke größer als das rechte ist), werden sie vertauscht. Am Ende einer solchen Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe fest am Ende der Liste.

Die Bubble-Phase wird so lange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das jeweils letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da es bereits seine finale Position erreicht hat und die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Luftblasen im Wasser (daher der Name ''Bubble'') Schritt für Schritt immer weiter nach oben an das Ende der Liste. Es werden stets zwei benachbarte Zahlen miteinander in „Bubbles“ verglichen und bei Bedarf vertauscht.

== Beispiel ==
[[Datei:Animation Bubble Sort.gif|mini]]
Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett und kursiv markierten Zahlen werden jeweils miteinander verglichen. Ist die linke Zahl größer als die rechte, so werden beide vertauscht. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts an die letzte Position. Im zweiten Durchlauf muss diese letzte Position folglich nicht mehr verglichen werden. Im dritten Durchlauf entfallen die letzten zwei Positionen, und so weiter.

'''1. Durchlauf'''
* '''''55 07''''' 78 12 42 (55 ist größer als 07 -> Tausch)
* 07 '''''55 78''''' 12 42 (55 ist nicht größer als 78 -> kein Tausch)
* 07 55 '''''78 12''''' 42 (78 ist größer als 12 -> Tausch)
* 07 55 12 '''''78 42''''' (78 ist größer als 42 -> Tausch, letzter Vergleich)

'''2. Durchlauf''' (78 ist bereits fest positioniert)
* '''''07 55''''' 12 42 78
* 07 '''''55 12''''' 42 78 (Tausch)
* 07 12 '''''55 42''''' 78 (Tausch, letzter Vergleich)

'''3. Durchlauf''' (55 und 78 sind fest positioniert)
* '''''07 12''''' 42 55 78
* 07 '''''12 42''''' 55 78 (Letzter Vergleich)

'''4. Durchlauf'''
* '''''07 12''''' 42 55 78 (Letzter Vergleich)

07 12 42 55 78 – Die Liste ist fertig sortiert.

== Pseudocode ==
Der [[Algorithmus]] sieht im Pseudocode der unoptimierten Basisvariante so aus:

<syntaxhighlight lang="text">
prozedur bubbleSort(A ist Liste sortierbarer Elemente)
n = Länge von A
wiederhole solange n > 1
n = n - 1
i = 0
wiederhole solange i < n
falls A[i] > A[i + 1] dann
tausche A[i] und A[i + 1]
ende falls
i = i + 1
ende wiederhole
ende wiederhole
ende prozedur
</syntaxhighlight>

== Komplexität ==
Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des Algorithmus Bubble Sort für ein [[Array]] der Länge <math>n</math>.

=== Best Case ===
Das Best-Case-Szenario tritt ein, wenn die Liste bereits von Beginn an vollständig aufsteigend sortiert ist.
* '''Unoptimierte Variante (siehe Pseudocode):''' Auch wenn keine Vertauschungen notwendig sind, durchläuft der oben notierte Algorithmus die Liste strikt weiter. Er führt <math>\frac{n(n - 1)}{2}</math> Vergleiche aus. Die Zeitkomplexität liegt hier also bei <math>O(n^2)</math>.
* '''Optimierte Variante (Praxis-Standard):''' In der Praxis wird Bubble Sort fast immer mit einer Abbruchbedingung (z. B. einem Boolean-Flag `wurdeGetauscht`) implementiert. Findet in einem kompletten Durchlauf kein einziger Tausch statt, weiß der Algorithmus, dass die Liste sortiert ist, und bricht vorzeitig ab. In dieser optimierten Form benötigt er im Best Case nur <math>n - 1</math> Vergleiche. Die Zeitkomplexität sinkt dadurch auf eine lineare Laufzeit von <math>O(n)</math>.

=== Average Case ===
Im durchschnittlichen Fall (Average Case) liegt eine zufällig durchmischte Liste vor.
Etwa die Hälfte der maximal möglichen Vertauschungen muss durchgeführt werden. Sowohl die Anzahl der Vergleiche als auch die der Vertauschungen wachsen quadratisch zur Eingabemenge <math>n</math>. Konstante Faktoren (wie die Halbierung der Tauschoperationen) werden in der Landau-Notation ignoriert. Die Zeitkomplexität im Average Case liegt somit bei <math>O(n^2)</math>.

=== Worst Case ===
Das Worst-Case-Szenario liegt vor, wenn die Liste in umgekehrter (absteigender) Reihenfolge sortiert ist.
In diesem Fall ist das aktuell betrachtete Element immer größer als sein rechter Nachbar. Der Algorithmus muss in jedem einzelnen Schritt eine Vertauschung durchführen, da jedes Element an das andere Ende der Liste "blubbern" muss. Er führt die maximale Anzahl an Vergleichen und Vertauschungen durch: <math>\frac{n(n - 1)}{2}</math>. Da der Term mit der höchsten Potenz das Wachstum dominiert, liegt die Komplexitätsklasse des Bubble Sorts im Worst Case bei <math>O(n^2)</math>.

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Quicksort

Flbkwikiadmin — Tue, 28 Apr 2026 08:51:30 GMT

Laufzeitanalyse

@@ Zeile 155: / Zeile 155: @@
 == Laufzeitanalyse ==
 === Best-Case (Bester Fall) ===
@@ Zeile 223: / Zeile 207: @@
 Da konstante Vorfaktoren wie die <math>2</math> beim Groß-O ignoriert werden, ist nun stochastisch bewiesen:
 '''Fazit Average-Case:''' Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums der harmonischen Reihe sicher gegen die Komplexitätsklasse <math>\mathcal{O}(n \log n)</math>.
 [[Kategorie:Programmierung]]
 [[Kategorie:AHR_I_Informatik_LK]]
 [[Kategorie:FI_I_TP2]]

Bubble-sort

Flbkwikiadmin — Tue, 28 Apr 2026 08:50:55 GMT

← Nächstältere Version		Version vom 28. April 2026, 10:50 Uhr
Zeile 1:		Zeile 1:
	== Einführung ==		== Einführung ==
	Der Bubble Sort ist ein ~~relativ~~ einfacher [[Sortieren\|Sortieralgorithmus]]. In der Bubble-Phase wird die Eingabeliste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das ~~aktuelle~~ Element mit ~~dem~~ rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie vertauscht. Am Ende ~~der~~ Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.		Der Bubble Sort (Sortieren durch Aufsteigen) ist ein verhältnismäßig einfacher [[Sortieren\|Sortieralgorithmus]]. In der sogenannten Bubble-Phase wird die Eingabeliste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuell betrachtete Element mit seinem rechten Nachbarn verglichen. Falls die beiden Elemente das vorgegebene Sortierkriterium verletzen (z. B. das linke größer als das rechte ist), werden sie vertauscht. Am Ende einer solchen Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe fest am Ende der Liste.

	Die Bubble-Phase wird so lange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.		Die Bubble-Phase wird so lange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das jeweils letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da es bereits seine finale Position erreicht hat und die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.

	Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie ~~Blasen~~ im Wasser (daher der Name) immer weiter nach oben~~, das heißt~~ an das Ende der Liste. Es werden ~~jeweils~~ zwei Zahlen miteinander in „Bubbles“ vertauscht.		Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Luftblasen im Wasser (daher der Name ''Bubble'') Schritt für Schritt immer weiter nach oben an das Ende der Liste. Es werden stets zwei benachbarte Zahlen miteinander in „Bubbles“ verglichen und bei Bedarf vertauscht.

	== Beispiel ==		== Beispiel ==
	[[Datei:Animation Bubble Sort.gif\|mini]]		[[Datei:Animation Bubble Sort.gif\|mini]]
	Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett ~~gedruckten~~ Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht~~; das Zahlenpaar ist dann blau markiert~~. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts. ~~Der zweite~~ Durchlauf ~~braucht somit die~~ letzte Position nicht mehr ~~zu vergleichen~~. ~~→ Dritter~~ Durchlauf~~: kein Vergleich der~~ letzten ~~drei~~ Positionen ~~mehr~~.		Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett und kursiv markierten Zahlen werden jeweils miteinander verglichen. Ist die linke Zahl größer als die rechte, so werden beide vertauscht. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts an die letzte Position. Im zweiten Durchlauf muss diese letzte Position folglich nicht mehr verglichen werden. Im dritten Durchlauf entfallen die letzten zwei Positionen, und so weiter.

	'''''55 07''''' 78 12 42 ~~1. Durchlauf~~		'''1. Durchlauf'''
			* '''''55 07''''' 78 12 42 (55 ist größer als 07 -> Tausch)
			* 07 '''''55 78''''' 12 42 (55 ist nicht größer als 78 -> kein Tausch)
			* 07 55 '''''78 12''''' 42 (78 ist größer als 12 -> Tausch)
			* 07 55 12 '''''78 42''''' (78 ist größer als 42 -> Tausch, letzter Vergleich)

	07 '''''55 78''''' 12 42		'''2. Durchlauf''' (78 ist bereits fest positioniert)
			* '''''07 55''''' 12 42 78
			* 07 '''''55 12''''' 42 78 (Tausch)
			* 07 12 '''''55 42''''' 78 (Tausch, letzter Vergleich)

	07 55 '''''78 12''''' 42		'''3. Durchlauf''' (55 und 78 sind fest positioniert)
			* '''''07 12''''' 42 55 78
			* 07 '''''12 42''''' 55 78 (Letzter Vergleich)

	~~07 55 12~~ '''''~~78 42~~''''' Letzter Vergleich		'''4. Durchlauf'''
			* '''''07 12''''' 42 55 78 (Letzter Vergleich)

	~~'''''07 55''''' 12 42 78 2. Durchlauf~~		07 12 42 55 78 – Die Liste ist fertig sortiert.

	~~07 '''''55 12''''' 42 78~~

	~~07 12 '''''55 42''''' 78 Letzter Vergleich~~

	~~'''''07 12''''' 42 55 78 3. Durchlauf~~

	~~07 '''''12 42''''' 55 78 Letzter Vergleich~~

	~~'''''07 12''''' 42 55 78 4. Durchlauf + letzter Vergleich~~

	07 12 42 55 78 ~~Fertig~~ sortiert.

	== Pseudocode ==		== Pseudocode ==
	Der [[Algorithmus]] sieht im Pseudocode so aus:		Der [[Algorithmus]] sieht im Pseudocode der unoptimierten Basisvariante so aus:

	<syntaxhighlight lang="text">		<syntaxhighlight lang="text">
Zeile 50:		Zeile 48:
	ende prozedur		ende prozedur
	</syntaxhighlight>		</syntaxhighlight>

			== Komplexität ==
			Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des Algorithmus Bubble Sort für ein [[Array]] der Länge <math>n</math>.

			=== Best Case ===
			Das Best-Case-Szenario tritt ein, wenn die Liste bereits von Beginn an vollständig aufsteigend sortiert ist.
			* '''Unoptimierte Variante (siehe Pseudocode):''' Auch wenn keine Vertauschungen notwendig sind, durchläuft der oben notierte Algorithmus die Liste strikt weiter. Er führt <math>\frac{n(n - 1)}{2}</math> Vergleiche aus. Die Zeitkomplexität liegt hier also bei <math>O(n^2)</math>.
			* '''Optimierte Variante (Praxis-Standard):''' In der Praxis wird Bubble Sort fast immer mit einer Abbruchbedingung (z. B. einem Boolean-Flag `wurdeGetauscht`) implementiert. Findet in einem kompletten Durchlauf kein einziger Tausch statt, weiß der Algorithmus, dass die Liste sortiert ist, und bricht vorzeitig ab. In dieser optimierten Form benötigt er im Best Case nur <math>n - 1</math> Vergleiche. Die Zeitkomplexität sinkt dadurch auf eine lineare Laufzeit von <math>O(n)</math>.

			=== Average Case ===
			Im durchschnittlichen Fall (Average Case) liegt eine zufällig durchmischte Liste vor.
			Etwa die Hälfte der maximal möglichen Vertauschungen muss durchgeführt werden. Sowohl die Anzahl der Vergleiche als auch die der Vertauschungen wachsen quadratisch zur Eingabemenge <math>n</math>. Konstante Faktoren (wie die Halbierung der Tauschoperationen) werden in der Landau-Notation ignoriert. Die Zeitkomplexität im Average Case liegt somit bei <math>O(n^2)</math>.

			=== Worst Case ===
			Das Worst-Case-Szenario liegt vor, wenn die Liste in umgekehrter (absteigender) Reihenfolge sortiert ist.
			In diesem Fall ist das aktuell betrachtete Element immer größer als sein rechter Nachbar. Der Algorithmus muss in jedem einzelnen Schritt eine Vertauschung durchführen, da jedes Element an das andere Ende der Liste "blubbern" muss. Er führt die maximale Anzahl an Vergleichen und Vertauschungen durch: <math>\frac{n(n - 1)}{2}</math>. Da der Term mit der höchsten Potenz das Wachstum dominiert, liegt die Komplexitätsklasse des Bubble Sorts im Worst Case bei <math>O(n^2)</math>.

	[[Kategorie:Programmierung]]		[[Kategorie:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]
	[[Kategorie:FI_I_TP2]]		[[Kategorie:FI_I_TP2]]

Selection-sort

Flbkwikiadmin — Tue, 28 Apr 2026 08:49:46 GMT

← Nächstältere Version		Version vom 28. April 2026, 10:49 Uhr
Zeile 1:		Zeile 1:
	== Einführung ==		== Einführung ==
	Ein einfacher [[Sortieren\|Sortieralgorithmus]] ist der Selection Sort. Dieser Algorithmus sucht zunächst das kleinste Element in der Liste, merkt es sich und tauscht es mit dem Element am Anfang aus, sodass sich das kleinste Element an ~~erster~~ Stelle befindet. Anschließend wird das zweitkleinste Element gesucht und mit dem Element an ~~zweiter~~ Stelle vertauscht ~~usw~~. Auf diese Weise erhalten die Elemente auf der linken Seite der aktuellen Position schrittweise ihren festen Platz und werden nicht mehr verändert.		Ein einfacher [[Sortieren\|Sortieralgorithmus]] ist der Selection Sort (Sortieren durch Auswählen). Dieser Algorithmus sucht zunächst das kleinste Element in der Liste, merkt es sich und tauscht es mit dem Element am Anfang aus, sodass sich das kleinste Element an der ersten Stelle befindet.

			Anschließend wird das zweitkleinste Element im verbleibenden, noch unsortierten Teil der Liste gesucht und mit dem Element an der zweiten Stelle vertauscht, und so weiter. Auf diese Weise erhalten die Elemente auf der linken Seite der aktuellen Position schrittweise ihren festen Platz und werden nicht mehr verändert.

	== Beispiel ==		== Beispiel ==
	[[Datei:Array Selectionsort.gif\|mini]]		[[Datei:Array Selectionsort.gif\|mini]]
	Es soll eine Liste mit dem Inhalt [4\|3\|1\|5\|2] sortiert werden.		Es soll eine Liste mit dem Inhalt <code>[4, 3, 1, 5, 2]</code> sortiert werden.

	Im ersten Durchlauf wird die komplette Liste durchsucht, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel ist das der Wert 1. Der ursprüngliche Wert der Startposition (hier 4) wird mit dem Wert an der Position des kleinsten Elements (hier 1 an Index 2) vertauscht.		Im ersten Durchlauf wird die komplette Liste durchsucht, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel ist das der Wert 1. Der ursprüngliche Wert der Startposition (hier die 4) wird mit dem Wert an der Position des kleinsten Elements (hier die 1 am Index 2) vertauscht.

	[[Datei:Animation Selectionsort.gif\|mini]]		[[Datei:Animation Selectionsort.gif\|mini]]
	Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun bei Index 1. An Index 0 befindet sich bereits das kleinste Element, daher ist dort keine Suche mehr erforderlich. Der restliche Teil der Liste wird durchsucht~~. Das kleinste Element befindet sich hier am Ende der Liste~~. Es wird die 2 als kleinstes Element ausgewählt und mit der neuen Startposition vertauscht.		Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun bei Index 1. An Index 0 befindet sich bereits das kleinste Element der gesamten Liste, daher ist dort keine Suche mehr erforderlich. Der restliche Teil der Liste wird durchsucht. Es wird die 2 als kleinstes Element ausgewählt und mit der neuen Startposition vertauscht.

	Die Suche wiederholt sich nach diesem Prinzip, bis alle Elemente sortiert sind. Der Suchbereich verkleinert sich Schritt für Schritt. Die folgende Animation visualisiert den Algorithmus.		Die Suche wiederholt sich nach diesem Prinzip, bis alle Elemente sortiert sind. Der Suchbereich verkleinert sich dabei Schritt für Schritt um ein Element. Die folgende Animation visualisiert den Algorithmus.

	== Pseudocode ==		== Pseudocode ==
	Der Algorithmus sieht im Pseudocode so aus:		Der [[Algorithmus]] sieht im Pseudocode so aus:

	<syntaxhighlight lang="text">		<syntaxhighlight lang="text">
Zeile 63:		Zeile 65:

	== Komplexität ==		== Komplexität ==
	Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des [[~~Algorithmus~~]] ~~SelectionSort~~.		Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des Algorithmus Selection Sort.

			Ein besonderes Merkmal dieses Algorithmus ist, dass seine Laufzeit unabhängig von der anfänglichen Sortierung der Elemente ist. Um eine Datenstruktur (z. B. ein [[Array]]) mit <math>n</math> Einträgen zu sortieren, muss <math>n - 1</math> Mal das Minimum durch Vergleichen bestimmt werden.

			Bei der ersten Bestimmung des Minimums sind <math>n - 1</math> Vergleiche notwendig, bei der zweiten <math>n - 2</math> Vergleiche, und so weiter bis zum letzten Durchlauf mit exakt 1 Vergleich. Mit der [[Arithmetische-reihe\|gaußschen Summenformel]] erhält man die Gesamtanzahl der immer notwendigen Vergleiche:

			<math>(n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n</math>

	~~Um eine Datenstruktur (z~~. B. ein ~~[[Array]]~~) ~~mit~~ n ~~Einträgen mittels SelectionSort zu sortieren, muss n−1~~-~~mal das Minimum durch Vergleichen bestimmt werden~~. ~~Bei der ersten Bestimmung des Minimums sind n−1~~ Vergleiche ~~notwendig~~, bei ~~der zweiten n−2 Vergleiche usw~~. ~~Mit der [[Arithmetische-reihe\|gaußschen Summenformel]] erhält man die Gesamtanzahl der notwendigen Vergleiche:~~		=== Best Case ===
			Das Best-Case-Szenario tritt ein, wenn das Array bereits vollständig aufsteigend sortiert ist.
			Auch wenn alle Elemente bereits am richtigen Platz stehen, "weiß" der Selection Sort dies nicht. Er muss trotzdem in jedem Durchlauf den kompletten unsortierten Rest der Liste überprüfen, um sicherzustellen, dass nicht doch ein noch kleineres Element existiert. Es finden zwar keine Vertauschungen (Swaps) statt, die Anzahl der Vergleiche bleibt jedoch bei <math>\frac{n(n - 1)}{2}</math>. Da die Vergleiche asymptotisch dominieren, liegt die Zeitkomplexität im Best Case bei <math>\mathcal{O}(n^2)</math>.

	(n − 1~~) +~~ (n − 2) ~~+ … + 1 = n(n − 1)~~ / 2		=== Average Case ===
			Im durchschnittlichen Fall (Average Case) liegt eine zufällig durchmischte Liste vor.
			Genau wie im Best Case muss der Selection Sort die gesamte arithmetische Reihe an Vergleichen durchführen, um das Minimum in jedem Schritt zu finden. Die Anzahl der durchgeführten Vertauschungen liegt im Schnitt zwischen 0 und <math>n - 1</math>. Auch hier ändert dies nichts an der dominanten quadratischen Anzahl der Vergleiche. Die Zeitkomplexität im Average Case ist somit ebenfalls <math>\mathcal{O}(n^2)</math>.

	~~SelectionSort~~ liegt ~~somit~~ in der Komplexitätsklasse <math>O(n^2)</math>.		=== Worst Case ===
			Das Worst-Case-Szenario liegt vor, wenn die Liste in umgekehrter (absteigender) Reihenfolge sortiert ist.
			Der Algorithmus führt wieder exakt <math>\frac{n(n - 1)}{2}</math> Vergleiche aus. In diesem Fall muss bei fast jedem Durchlauf (maximal <math>n - 1</math> Mal) das kleinste Element mit dem aktuellen Start-Element vertauscht werden. Da die maximale Anzahl der Vertauschungen linear (<math>\mathcal{O}(n)</math>) wächst, die Anzahl der Vergleiche jedoch quadratisch, bestimmt der quadratische Term das Laufzeitverhalten. Die Komplexitätsklasse im Worst Case liegt demnach bei <math>\mathcal{O}(n^2)</math>.

	[[Kategorie:Programmierung]]		[[Kategorie:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]
	[[Kategorie:FI_I_TP2]]		[[Kategorie:FI_I_TP2]]

Insertion-sort

Flbkwikiadmin — Tue, 28 Apr 2026 08:48:13 GMT

← Nächstältere Version		Version vom 28. April 2026, 10:48 Uhr
Zeile 46:		Zeile 46:

	== Komplexität ==		== Komplexität ==

			=== Best Case ===
			Die optimale Eingabe ist ein bereits sortiertes [[Array]]. In diesem Fall wird pro Iteration lediglich ein Vergleich durchgeführt, und die innere Schleife wird nie betreten. Die Gesamtanzahl der Vergleiche ist somit proportional zur Anzahl der Elemente <math>n</math>.

			Insertion Sort besitzt im Best Case daher eine lineare Laufzeit von <math>O(n)</math>.

			=== Average Case ===
			Das Average-Case-Szenario geht von einer zufälligen Verteilung der Werte in der Liste aus.

			Im Durchschnitt ist das aktuell betrachtete Element kleiner als die Hälfte der bereits sortierten Elemente. Die innere Schleife muss das Element also im Mittel nur bis in die Mitte des bisher sortierten Teilbereichs verschieben. Die Anzahl der Vergleiche und Verschiebungen halbiert sich im Vergleich zum Worst Case dadurch in etwa.

			Da in der asymptotischen Landau-Notation konstante Faktoren (wie diese Halbierung) ignoriert werden, dominiert weiterhin die höchste Potenz das Wachstum. Die Zeitkomplexität liegt im Average Case demnach bei <math>O(n^2)</math>.

	=== Worst Case ===		=== Worst Case ===
	Eine Liste in umgekehrter Reihenfolge stellt das Worst-Case-Szenario für ~~InsertionSort~~ dar:		Eine Liste in umgekehrter (absteigender) Reihenfolge stellt das Worst-Case-Szenario für Insertion Sort dar, beispielsweise:

	<math>[11,7,5,3,2,0]</math>		<math>[11, 7, 5, 3, 2, 0]</math>

	Wir betrachten nur die Vergleichsoperationen, die mit der Variablen c gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt n.		Wir betrachten nur die Vergleichsoperationen, die mit der Variablen <math>c</math> gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt <math>n</math>.

	Beim ersten äußeren Schleifendurchlauf ist c = 1, da nur ein Vergleich durchgeführt wird. Beim zweiten Durchlauf sind es 2 Vergleiche, beim dritten 3 usw., bis zum letzten Durchlauf mit ~~n−1~~ Vergleichen.		Beim ersten äußeren Schleifendurchlauf ist <math>c = 1</math>, da nur ein Vergleich durchgeführt wird. Beim zweiten Durchlauf sind es 2 Vergleiche, beim dritten 3 usw., bis zum letzten Durchlauf mit <math>n - 1</math> Vergleichen.

	Die Gesamtanzahl der Vergleiche ergibt sich zu:		Die Gesamtanzahl der Vergleiche ergibt sich zu:
Zeile 64:		Zeile 76:
	<math>\frac{n(n-1)}{2}</math>		<math>\frac{n(n-1)}{2}</math>

	Für große n dominiert der quadratische Term, sodass ~~InsertionSort~~ im Worst Case in der Komplexitätsklasse <math>O(n^2)</math> liegt.		Für große <math>n</math> dominiert der quadratische Term, sodass Insertion Sort im Worst Case in der Komplexitätsklasse <math>O(n^2)</math> liegt.

	~~=== Best Case ===~~
	~~Die optimale Eingabe ist ein bereits sortiertes [[Array]]. In diesem Fall wird pro Iteration lediglich ein Vergleich durchgeführt. Die Gesamtanzahl der Vergleiche ist somit proportional zu n.~~

	~~InsertionSort besitzt im Best Case daher eine lineare Laufzeit von <math>O(n)</math>~~.

	[[Kategorie:Programmierung]]		[[Kategorie:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]
	[[Kategorie:FI_I_TP2]]		[[Kategorie:FI_I_TP2]]

Fremdschlüssel

Flbkwikiadmin — Thu, 23 Apr 2026 09:21:39 GMT

Weiterleitung nach Schlüssel#Fremdschlüssel erstellt

Neue Seite

#redirect[[Schlüssel#Fremdschlüssel]]

Referentielle Integrität

Flbkwikiadmin — Thu, 23 Apr 2026 09:21:21 GMT

Weiterleitung nach Schlüssel#Referentielle Integrität erstellt

Neue Seite

#redirect[[Schlüssel#Referentielle_Integrität]]

Schlüssel

Flbkwikiadmin — Thu, 23 Apr 2026 09:08:15 GMT

Fremdschlüssel

@@ Zeile 53: / Zeile 53: @@
 == Fremdschlüssel ==
-Ein '''Fremdschlüssel''' ist ein Attribut oder eine Attributkombination einer Relation, welches auf einen Primärschlüssel (bzw. Schlüsselkandidaten) einer anderen oder der gleichen Relation verweist. Er dient als Verweis zwischen zwei Relationen und zeigt an, welche Tupel der Relationen inhaltlich miteinander in Verbindung stehen.
+Ein '''Fremdschlüssel''' (engl. ''Foreign Key'') ist ein Attribut oder eine Attributkombination einer Relation (Tabelle), welches auf einen [[Primärschlüssel]] (bzw. Schlüsselkandidaten) einer anderen oder der gleichen Relation verweist. Er dient als Verweis zwischen zwei Relationen und zeigt an, welche Tupel (Datensätze) inhaltlich miteinander in Verbindung stehen.
 == Künstlicher Schlüssel ==

Laufzeitanalyse

Flbkwikiadmin — Tue, 21 Apr 2026 06:38:52 GMT

Laufzeitanalyse von Insertion Sort

← Nächstältere Version		Version vom 21. April 2026, 08:38 Uhr
(3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 29:		Zeile 29:
	Man berechnet ihn, indem man alle möglichen Eingaben durchspielt und gewichtet. Die Formel für den Erwartungswert <math>E(T)</math> lautet:		Man berechnet ihn, indem man alle möglichen Eingaben durchspielt und gewichtet. Die Formel für den Erwartungswert <math>E(T)</math> lautet:

	<math>E(T) = \sum_{i=1}^{\|E\|} p_i \cdot t_i</math>		<math>E(T) = \sum_{i=1}^{\|F\|} p_i \cdot t_i</math>

	Hierbei bedeuten die Variablen:		Hierbei bedeuten die Variablen:
	* <math>E</math> ist die Menge aller theoretisch möglichen Eingaben der Größe <math>n</math> (z. B. alle möglichen Anordnungen einer Zahlenliste).		* <math>F</math> ist die Menge aller theoretisch möglichen Eingaben der Größe <math>n</math> (z. B. alle möglichen Anordnungen einer Zahlenliste).
	* <math>\|E\|</math> (Betragsstriche) steht in der Mathematik für die Mächtigkeit einer Menge. Es ist also die '''exakte Anzahl''' aller dieser möglichen Eingaben.		* <math>\|F\|</math> (Betragsstriche) steht in der Mathematik für die Mächtigkeit einer Menge. Es ist also die '''exakte Anzahl''' aller dieser möglichen Eingaben.
	* <math>p_i</math> ist die Wahrscheinlichkeit, dass genau die spezifische Eingabe <math>i</math> auftritt.		* <math>p_i</math> ist die Wahrscheinlichkeit, dass genau die spezifische Eingabe <math>i</math> auftritt.
	* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus für exakt diese Eingabe <math>i</math> braucht.		* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus für exakt diese Eingabe <math>i</math> braucht.
Zeile 65:		Zeile 65:
	int v, i, j;		int v, i, j;
	for (i = 1; i < zSortfeld.length; i++) {		for (i = 1; i < zSortfeld.length; i++) {
	~~c++; // Zähler für Vergleiche~~
	if (zSortfeld[i] < zSortfeld[i - 1]) {		if (zSortfeld[i] < zSortfeld[i - 1]) {
	v = zSortfeld[i];		v = zSortfeld[i];
Zeile 100:		Zeile 99:

	=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===		=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===
	~~Die Werte im~~ Array sind ~~völlig zufällig verteilt~~.		Wir sortieren ein Array der Länge <math>n</math>. Wir nehmen an, alle Permutationen (Anordnungen) der Zahlen sind gleich wahrscheinlich. Der Algorithmus fügt nacheinander jedes Element an Index <math>i</math> (von Position 2 bis <math>n</math>) in den bereits sortierten vorderen Teil der Länge <math>i-1</math> ein.
	* '''~~Verhalten~~:''' ~~Im Durchschnitt müssen wir ein Element nicht~~ bis ganz ~~an den Anfang schieben (wie im Worst-Case~~), ~~sondern nur bis zur~~ '''~~Hälfte~~''' des ~~bisher sortierten Bereichs~~.
	* '''~~Aufwand~~:''' Die ~~Anzahl~~ der ~~Vergleiche halbiert~~ sich ~~grob im Vergleich zum Worst-Case~~. ~~Der Aufwand liegt~~ bei ~~ca.~~ <math>\frac{1}{2} \cdot \frac{c}{2}n^2</math>.		* '''Schritt 1: Wahrscheinlichkeit bestimmen.''' Beim Einfügen des <math>i</math>-ten Elements gibt es genau <math>i</math> mögliche Zielpositionen (von ganz vorne bis zu seinem aktuellen Platz ganz hinten). Da die ursprüngliche Reihenfolge zufällig ist, ist jede dieser Positionen gleich wahrscheinlich. Die Wahrscheinlichkeit für jede Position ist also <math>p = \frac{1}{i}</math>.
	* '''~~Komplexität~~:''' ~~Wie wir gelernt haben, ignoriert die Groß-~~O-Notation ~~konstante Brüche~~ (wie <math>\frac{1}{4}</math>)~~. Es bleibt bei~~ der ~~höchsten Potenz: Das Wachstum ist und bleibt quadratisch. Die Komplexität lautet also weiterhin~~ <math>\mathcal{O}(n^2)</math>.		* '''Schritt 2: Schritte zählen.''' Das Finden der richtigen Position ist wie eine rückwärtsgerichtete lineare Suche. Im besten Fall (das Element ist bereits größer als alle vorherigen und bleibt am Ende) brauchen wir 1 Vergleich. Im Durchschnitt muss das Element mit der Hälfte der bereits sortierten Elemente verglichen werden, um seinen Platz zu finden. Der durchschnittliche Aufwand (Vergleiche) für das Einfügen des <math>i</math>-ten Elements liegt daher bei etwa <math>\frac{i}{2}</math>.
			* '''Schritt 3: Erwartungswert berechnen.''' Um die Gesamtlaufzeit zu erhalten, summieren wir den durchschnittlichen Aufwand für alle Elemente, die eingefügt werden müssen (von <math>i=2</math> bis <math>n</math>):

			<math>E(T) \approx \sum_{i=2}^{n} \frac{i}{2}</math>

			Wir klammern <math>\frac{1}{2}</math> aus:

			<math>E(T) \approx \frac{1}{2} \cdot \sum_{i=2}^{n} i</math>

			Die Summe der Zahlen von 1 bis <math>n</math> lässt sich wieder mit der '''Gaußschen Summenformel''' (kleiner Gauß) vereinfachen zu <math>\frac{n(n+1)}{2}</math>. Da unsere Summe aber erst bei <math>i=2</math> startet, ziehen wir die 1 (für den fehlenden Schritt <math>i=1</math>) ab:

			<math>E(T) \approx \frac{1}{2} \cdot \left( \frac{n(n+1)}{2} - 1 \right) = \frac{n^2 + n - 2}{4} = \frac{1}{4}n^2 + \frac{1}{4}n - \frac{1}{2}</math>

			'''Fazit:''' Im Durchschnitt braucht der Insertion Sort etwa <math>\frac{1}{4}n^2</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{4}</math> und Terme niedrigerer Ordnung (wie <math>\frac{1}{4}n - \frac{1}{2}</math>) wegfallen, gehört der Insertion Sort im Durchschnitt zur Klasse <math>\mathcal{O}(n^2)</math>.

	[[Kategorie:Programmierung]]		[[Kategorie:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]

Quicksort

Flbkwikiadmin — Mon, 20 Apr 2026 10:26:21 GMT

← Nächstältere Version		Version vom 20. April 2026, 12:26 Uhr
Zeile 121:		Zeile 121:
	</syntaxhighlight>		</syntaxhighlight>

	== ~~Maximumsuche~~ ==		== Vorbereitung: Indikatorvariablen und die Harmonische Reihe ==
	Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen nicht mehr aus. Hier arbeiten wir mit einem ~~mathematischen Trick~~: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das zu ~~verstehen~~, analysieren wir einen simplen Code zur Maximumsuche:		Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen der Vergleiche oft nicht mehr aus. Hier arbeiten wir in der Laufzeitanalyse mit einem stochastischen Werkzeug: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das Prinzip zu verinnerlichen, analysieren wir vorab einen simplen Code zur Maximumsuche:

	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">
Zeile 135:		Zeile 135:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	Die Vergleiche in der <code>if</code>-Bedingung werden immer <math>n-1</math> Mal ausgeführt. Aber wie oft wird die Variable <code>max</code> im Durchschnitt überschrieben (Update-Operation)?		Die Vergleiche in der <code>if</code>-Bedingung werden immer exakt <math>n-1</math> Mal ausgeführt. Aber wie oft wird die Variable <code>max</code> im Durchschnitt tatsächlich überschrieben (Update-Operation)?

	Wir stellen uns vor, das Array enthält völlig zufällig gemischte Zahlen.		Wir stellen uns vor, das Array enthält völlig zufällig gemischte Zahlen.
	* '''Intuitiver Ansatz:'''		* '''Intuitiver Ansatz:'''
	Das 1. Element ist automatisch das bisherige Maximum (Wahrscheinlichkeit: 1).		Das 1. Element ist automatisch das bisherige Maximum (Wahrscheinlichkeit: 1).
	Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist exakt 50% (<math>\frac{1}{2}</math>).		Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist bei zufälliger Verteilung exakt 50% (<math>\frac{1}{2}</math>).
	Damit das 3. Element ein neues Maximum ist, muss es das Größte der ersten drei Elemente sein. Die Chance dafür ist <math>\frac{1}{3}</math>.		Damit das 3. Element ein neues Maximum ist, muss es das Größte der ersten drei Elemente sein. Die Chance dafür ist <math>\frac{1}{3}</math>.

Zeile 152:		Zeile 152:
	Diese spezielle Summe nennt man in der Mathematik die '''Harmonische Reihe''' (<math>H_n</math>). Sie wächst extrem langsam. Für große Zahlen <math>n</math> entspricht sie in etwa dem '''natürlichen Logarithmus''' (<math>\ln(n)</math>).		Diese spezielle Summe nennt man in der Mathematik die '''Harmonische Reihe''' (<math>H_n</math>). Sie wächst extrem langsam. Für große Zahlen <math>n</math> entspricht sie in etwa dem '''natürlichen Logarithmus''' (<math>\ln(n)</math>).

	'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um ~~später selbst~~ zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.		'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um im nächsten Abschnitt zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.

	== Laufzeitanalyse ==		== Laufzeitanalyse ==
Zeile 169:		Zeile 169:
	<math>c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n</math>		<math>c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n</math>

	Da in der ~~asymtotischen~~ Laufzeitanalyse konstante Faktoren und kleinere Terme (wie <math>n</math>) ignoriert werden, wächst der Aufwand quadratisch.		Da in der asymptotischen Laufzeitanalyse konstante Faktoren und kleinere Terme (wie <math>n</math>) ignoriert werden, wächst der Aufwand quadratisch.
	'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.		'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.

Zeile 205:		Zeile 205:

	=== Average-Case (Durchschnittlicher Fall) ===		=== Average-Case (Durchschnittlicher Fall) ===
	In der Praxis haben wir selten den perfekten Best-Case, aber fast nie den absoluten Worst-Case. Meistens teilt das Pivot die Liste ~~beispielsweise im Verhältnis~~ 30:70 oder 60:40.		In der Praxis haben wir selten den perfekten Best-Case, aber fast nie den absoluten Worst-Case. Meistens teilt das Pivot die Liste in ungleiche, aber moderate Verhältnisse (z. B. 30:70 oder 60:40).

	Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf ~~das Prinzip der '''~~Indikatorvariablen~~'''~~ und ~~der '''Harmonischen~~ Reihe~~'''~~ zurück. Wir fragen uns: ''Wie hoch ist die Wahrscheinlichkeit, dass zwei beliebige Elemente (nennen wir sie <math>z_i</math> und <math>z_j</math>) im Laufe des Algorithmus miteinander verglichen werden?''		Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf unser Vorwissen (Indikatorvariablen und Harmonische Reihe) zurück. Wir fragen uns: ''Wie hoch ist die Wahrscheinlichkeit, dass zwei beliebige Elemente (nennen wir sie <math>z_i</math> und <math>z_j</math>, wobei <math>z_i < z_j</math>) im Laufe des Algorithmus direkt miteinander verglichen werden?''

	* Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, '''bevor''' irgendein Element, dessen Wert zwischen ~~den beiden~~ liegt, als Pivot gewählt wird.		* Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, '''bevor''' irgendein anderes Element, dessen Wert zwischen <math>z_i</math> und <math>z_j</math> liegt, als Pivot gewählt wird.
	* Sind die Daten völlig zufällig verteilt, ~~ist die Wahrscheinlichkeit, dass von~~ <math>k</math> ~~Elementen genau das größte oder kleinste~~ zuerst als Pivot gewählt ~~wird~~, exakt <math>\frac{2}{k}</math>.		* Zwischen <math>z_i</math> und <math>z_j</math> (inklusive der beiden Randelemente) liegen exakt <math>k = j - i + 1</math> Elemente.
			* Sind die Daten völlig zufällig verteilt, hat jedes dieser <math>k</math> Elemente die gleiche Chance, zuerst als Pivot gewählt zu werden. Damit <math>z_i</math> und <math>z_j</math> verglichen werden, muss exakt <math>z_i</math> oder <math>z_j</math> der "Gewinner" dieser Ziehung sein. Da es <math>2</math> günstige Fälle (<math>z_i</math> oder <math>z_j</math>) bei <math>k</math> möglichen Fällen gibt, beträgt die Wahrscheinlichkeit exakt <math>\frac{2}{k}</math>.

	Summieren wir diese Wahrscheinlichkeiten (Erwartungswert) für alle Elementpaare im Array auf, erhalten wir folgende Doppel-Summe:		Summieren wir diese Wahrscheinlichkeiten (den Erwartungswert) für alle möglichen Elementpaare im gesamten Array auf, erhalten wir folgende Doppel-Summe:
	<math>E(X) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j - i + 1}</math>		<math>E(X) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j - i + 1}</math>

	~~Setzt~~ man ~~für~~ den Abstand <math>(j - i + 1)</math> ~~eine neue Variable~~ <math>k</math> ~~ein~~, löst sich die innere Summe auf zu:		Ersetzt man den Abstand <math>(j - i + 1)</math> formal durch die Laufvariable <math>k</math>, löst sich die innere Summe auf zu:
	<math>\sum_{k=2}^{n} \frac{2}{k} = 2 \cdot \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)</math>		<math>\sum_{k=2}^{n} \frac{2}{k} = 2 \cdot \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)</math>

	Hier erkennen wir exakt die '''Harmonische Reihe''' (<math>H_n</math>) wieder~~, die wir bereits bei der Maximumsuche kennengelernt haben~~! Da die Harmonische Reihe für große <math>n</math> gegen den natürlichen Logarithmus <math>\ln(n)</math> konvergiert, ergibt die innere Summe ungefähr <math>2 \cdot \ln(n)</math>. Da die äußere Summe <math>n</math>-mal läuft, erhalten wir insgesamt rund <math>2n \cdot \ln(n)</math> Vergleiche.		Hier erkennen wir exakt die '''Harmonische Reihe''' (<math>H_n</math>) wieder! Da die Harmonische Reihe für große <math>n</math> gegen den natürlichen Logarithmus <math>\ln(n)</math> konvergiert, ergibt die innere Summe ungefähr <math>2 \cdot \ln(n)</math>. Da die äußere Summe (stark vereinfacht) <math>n</math>-mal läuft, erhalten wir insgesamt rund <math>2n \cdot \ln(n)</math> Vergleiche.

	Da ~~Konstanten~~ wie ~~der Faktor~~ 2 beim Groß-O ignoriert werden, ist nun stochastisch bewiesen:		Da konstante Vorfaktoren wie die <math>2</math> beim Groß-O ignoriert werden, ist nun stochastisch bewiesen:
	'''Fazit Average-Case:''' Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums der harmonischen Reihe sicher gegen die Komplexitätsklasse <math>\mathcal{O}(n \log n)</math>.		'''Fazit Average-Case:''' Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums der harmonischen Reihe sicher gegen die Komplexitätsklasse <math>\mathcal{O}(n \log n)</math>.

Laufzeitanalyse

Flbkwikiadmin — Mon, 20 Apr 2026 10:26:00 GMT

← Nächstältere Version		Version vom 20. April 2026, 12:26 Uhr
Zeile 31:		Zeile 31:
	<math>E(T) = \sum_{i=1}^{\|E\|} p_i \cdot t_i</math>		<math>E(T) = \sum_{i=1}^{\|E\|} p_i \cdot t_i</math>

	* <math>p_i</math> ist die Wahrscheinlichkeit ~~für einen bestimmten Fall~~ <math>i</math>.		Hierbei bedeuten die Variablen:
	* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus ~~in diesem Fall~~ braucht.		* <math>E</math> ist die Menge aller theoretisch möglichen Eingaben der Größe <math>n</math> (z. B. alle möglichen Anordnungen einer Zahlenliste).
			* <math>\|E\|</math> (Betragsstriche) steht in der Mathematik für die Mächtigkeit einer Menge. Es ist also die '''exakte Anzahl''' aller dieser möglichen Eingaben.
			* <math>p_i</math> ist die Wahrscheinlichkeit, dass genau die spezifische Eingabe <math>i</math> auftritt.
			* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus für exakt diese Eingabe <math>i</math> braucht.

	Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder ~~Fall~~ tritt mit derselben Wahrscheinlichkeit auf.		Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Eingabefall tritt mit exakt derselben Wahrscheinlichkeit auf.

	=== Average-Case der Linearen Suche ===		=== Average-Case der Linearen Suche ===

Quicksort

Flbkwikiadmin — Mon, 20 Apr 2026 07:39:38 GMT

@@ Zeile 120: / Zeile 120: @@
+}
 </syntaxhighlight>
 == Laufzeitanalyse ==

Laufzeitanalyse

Flbkwikiadmin — Mon, 20 Apr 2026 07:39:06 GMT

← Nächstältere Version		Version vom 20. April 2026, 09:39 Uhr
Zeile 54:		Zeile 54:

	'''Fazit:''' Im Durchschnitt braucht die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{2}</math> wegfallen, gehört die lineare Suche im Durchschnitt zur Klasse <math>\mathcal{O}(n)</math>.		'''Fazit:''' Im Durchschnitt braucht die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{2}</math> wegfallen, gehört die lineare Suche im Durchschnitt zur Klasse <math>\mathcal{O}(n)</math>.

	~~=== Maximumsuche ===~~
	Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen nicht mehr aus. Hier arbeiten wir mit einem mathematischen Trick: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das zu verstehen, analysieren wir einen simplen Code zur Maximumsuche:

	~~<syntaxhighlight lang="java">~~
	~~public int findMax(int[] A) {~~
	~~int max = A[0];~~
	~~for (int i = 1; i < A.length; i++) {~~
	~~if (A[i] > max) {~~
	~~max = A[i]; // Update-Operation~~
	}
	}
	~~return max;~~
	}
	~~</syntaxhighlight>~~
	~~Die Vergleiche in der <code>if</code>-Bedingung werden immer <math>n-1</math> Mal ausgeführt. Aber wie oft wird die Variable <code>max</code> im Durchschnitt überschrieben (Update-Operation)?~~

	~~Wir stellen uns vor, das Array enthält völlig zufällig gemischte Zahlen.~~
	* '''Intuitiver Ansatz:'''
	~~Das 1. Element ist automatisch das bisherige Maximum (Wahrscheinlichkeit: 1).~~
	~~Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist exakt 50% (<math>\frac{1}{2}</math>).~~
	~~Damit das 3. Element ein neues Maximum ist, muss es das Größte der ersten drei Elemente sein. Die Chance dafür ist <math>\frac{1}{3}</math>.~~

	* '''Mathematischer Ansatz (Indikatorvariablen):'''
	Wir definieren einen „Schalter“ (die Indikatorvariable) <math>X_i</math>. Er ist <math>1</math>, wenn ein neues Maximum an Stelle <math>i</math> gefunden wird, sonst <math>0</math>. Die Wahrscheinlichkeit dafür ist <math>P(X_i = 1) = \frac{1}{i}</math>.

	~~Um die durchschnittliche Gesamtzahl der Updates zu finden, addieren wir einfach diese Wahrscheinlichkeiten auf:~~

	~~<math>E[X] = \sum_{i=1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots + \frac{1}{n}</math>~~

	Diese spezielle Summe nennt man in der Mathematik die '''Harmonische Reihe''' (<math>H_n</math>). Sie wächst extrem langsam. Für große Zahlen <math>n</math> entspricht sie in etwa dem '''natürlichen Logarithmus''' (<math>\ln(n)</math>).

	'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um später selbst zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.

	== Laufzeitanalyse von Insertion Sort ==		== Laufzeitanalyse von Insertion Sort ==

Quicksort

Flbkwikiadmin — Mon, 20 Apr 2026 07:37:11 GMT

Änderungen zeigen

Laufzeitanalyse

Flbkwikiadmin — Mon, 20 Apr 2026 07:35:10 GMT

Änderungen zeigen

DCL

Flbkwikiadmin — Fri, 17 Apr 2026 09:40:09 GMT

← Nächstältere Version		Version vom 17. April 2026, 11:40 Uhr
Zeile 56:		Zeile 56:
	Da die genaue Syntax für die Benutzerverwaltung (z. B. das Anlegen von Benutzern mit Passwörtern) stark vom eingesetzten Datenbankmanagementsystem abhängt, weichen die Befehle in der Praxis oft leicht ab. Der exakte Befehlsumfang der DCL für das Produkt MySQL (von Oracle) kann im offiziellen MySQL-Manual nachgeschlagen werden.		Da die genaue Syntax für die Benutzerverwaltung (z. B. das Anlegen von Benutzern mit Passwörtern) stark vom eingesetzten Datenbankmanagementsystem abhängt, weichen die Befehle in der Praxis oft leicht ab. Der exakte Befehlsumfang der DCL für das Produkt MySQL (von Oracle) kann im offiziellen MySQL-Manual nachgeschlagen werden.

	~~[[Kategorie:SQL]]~~
	[[Kategorie:Datenbanken]]		[[Kategorie:Datenbanken]]
	[[Kategorie:AHR_I_Informatik LK]]		[[Kategorie:AHR_I_Informatik LK]]
	[[Kategorie:FI_I_SDM]]		[[Kategorie:FI_I_SDM]]

Relationale Algebra

Flbkwikiadmin — Fri, 17 Apr 2026 09:38:59 GMT

Einführung

← Nächstältere Version		Version vom 17. April 2026, 11:38 Uhr
Zeile 5:		Zeile 5:

	Als Erfinder der relationalen Algebra gilt '''Edgar F. Codd'''. In den 1970er Jahren hat er mit dieser mathematischen Grundlage die Datenbankwelt revolutioniert. Die Datenbanksprache SEQUEL, ein Vorläufer des heutigen [[SQL]], war eine der ersten praktischen Umsetzungen der Ideen des relationalen Modells und damit der relationalen Algebra.		Als Erfinder der relationalen Algebra gilt '''Edgar F. Codd'''. In den 1970er Jahren hat er mit dieser mathematischen Grundlage die Datenbankwelt revolutioniert. Die Datenbanksprache SEQUEL, ein Vorläufer des heutigen [[SQL]], war eine der ersten praktischen Umsetzungen der Ideen des relationalen Modells und damit der relationalen Algebra.

			[[Datei:RelationMitarbeiter.png\|mini]]

	== Mengenoperationen ==		== Mengenoperationen ==

Relationale Algebra

Flbkwikiadmin — Fri, 17 Apr 2026 09:38:30 GMT

Die Seite wurde neu angelegt: „== Einführung == Die '''relationale Algebra''' (auch Relationenalgebra genannt) bildet die theoretische Grundlage für Abfragesprachen in relationalen Datenbanken. In der Theorie der Datenbanken versteht man unter einer relationalen Algebra eine formale Sprache, mit der sich Abfragen über einem relationalen Schema formulieren lassen. Sie erlaubt es, Relationen miteinander zu verknüpfen und komplexere Informationen daraus herzu…“

Neue Seite

== Einführung ==
Die '''relationale Algebra''' (auch Relationenalgebra genannt) bildet die theoretische Grundlage für Abfragesprachen in [[Relationale Datenbank|relationalen Datenbanken]]. In der Theorie der Datenbanken versteht man unter einer relationalen Algebra eine formale Sprache, mit der sich Abfragen über einem relationalen Schema formulieren lassen. Sie erlaubt es, Relationen miteinander zu verknüpfen und komplexere Informationen daraus herzuleiten.

Die relationale Algebra definiert Operationen, die sich auf eine Menge von Relationen anwenden lassen. Damit lassen sich beispielsweise Relationen verknüpfen, filtern oder umbenennen. Die Ergebnisse dieser Operationen sind immer wieder neue Relationen.

Als Erfinder der relationalen Algebra gilt '''Edgar F. Codd'''. In den 1970er Jahren hat er mit dieser mathematischen Grundlage die Datenbankwelt revolutioniert. Die Datenbanksprache SEQUEL, ein Vorläufer des heutigen [[SQL]], war eine der ersten praktischen Umsetzungen der Ideen des relationalen Modells und damit der relationalen Algebra.

== Mengenoperationen ==
Relationen bezeichnen Mengen im mathematischen Sinne. Eine Menge enthält sogenannte Tupel (Datensätze). Zwischen den Tupeln einer Menge bzw. Relation ist keine Ordnung (wie z. B. eine Reihenfolge) definiert. Auf Tabellen in der Praxis sind hingegen stets Ordnungen definiert, da es dort eine physische Reihenfolge der Datensätze gibt.

Zudem kann ein Tupel in einer mathematischen Menge nicht mehrfach vorkommen – es gibt '''keine Duplikate'''. In einer reinen Datenbanktabelle wären Duplikate (ohne Primärschlüssel) hingegen technisch möglich. Auf diesen relationalen Mengen können unter gewissen Voraussetzungen die folgenden mathematischen Operationen ausgeführt werden.

=== Vereinigungsverträglichkeit (Typkompatibilität) ===
Um Mengenoperationen auf Relationen durchführen zu können, müssen diese miteinander kompatibel sein. Die Typkompatibilität (auch '''Vereinigungsverträglichkeit''' genannt) zweier Relationen ist gegeben, wenn:
# sie den gleichen Grad haben (die Anzahl der Attribute/Spalten ist identisch).
# der Wertebereich (Datentyp) der korrespondierenden Attribute identisch ist.

=== Vereinigung (Union) ===
[[Datei:MengeVereinigungsmenge.png|mini|rechts|Vereinigungsmenge]]
Ist die Vereinigungsverträglichkeit gegeben, können zwei Mengen vereinigt werden. Bei der Vereinigung von zwei Relationen <math>R \cup S</math> werden alle Tupel der Relation R mit allen Tupeln der Relation S zu einer einzigen neuen Relation vereint. Duplikate, die in beiden Relationen vorkommen, werden bei der Vereinigung gelöscht.

'''Beispiel:'''
* Relation R enthält die Mitarbeiter {Müller, Meier}.
* Relation S enthält die Mitarbeiter {Meier, Schulze}.
* Die Vereinigung <math>R \cup S</math> ergibt {Müller, Meier, Schulze}.

=== Schnittmenge (Intersection) ===
[[Datei:MengeSchnittmenge.png|mini|rechts|Schnittmenge]]
Ist die Vereinigungsverträglichkeit gegeben, können zwei Mengen geschnitten werden. Die Schnittmenge <math>R \cap S</math> beschreibt die Menge der Tupel, die sich exakt in '''beiden''' zu schneidenden Mengen wiederfinden.

'''Beispiel:'''
* Die Schnittmenge aus R {Müller, Meier} und S {Meier, Schulze} ist <math>R \cap S</math> = {Meier}.

=== Differenz (Difference) ===
[[Datei:MengeDifferenzmenge.png|mini|rechts|Differenzmenge]]
Die Differenz zweier Mengen kann gebildet werden, falls Vereinigungsverträglichkeit herrscht. Es wird eine Untermenge gebildet, die nur Elemente der einen Menge enthält, abzüglich der Elemente, die auch in der zweiten Menge vorkommen.

'''Beispiel:'''
* Die Differenz <math>R \setminus S</math> (gesprochen: R ohne S) aus {Müller, Meier} und {Meier, Schulze} ergibt {Müller}.

=== Symmetrische Differenz ===
Die symmetrische Differenz zweier Mengen kann gebildet werden, falls Vereinigungsverträglichkeit herrscht. Bei der symmetrischen Differenz handelt es sich um die Menge aller Tupel, die '''entweder''' in R '''oder''' in S, aber '''nicht in beiden gleichzeitig''' enthalten sind.

'''Beispiel:'''
* Die symmetrische Differenz aus R {Müller, Meier} und S {Meier, Schulze} ergibt {Müller, Schulze}.

== Spezifische Relationenoperationen ==

=== Kartesisches Produkt (Cross Product) ===
Ohne Voraussetzung bezüglich der Vereinigungsverträglichkeit lässt sich das Kartesische Produkt (<math>R \times S</math>) zweier Mengen bilden. Das Resultat ist die Menge '''aller möglichen Kombinationen''' der Tupel aus R und S. Das heißt: Jedes Tupel der einen Relation wird mit jedem Tupel der anderen Relation kombiniert.

Wenn alle Attribute verschieden sind, umfasst die Resultatsrelation die Summe der Attribute (Spalten) der Ausgangstabellen. Die Anzahl der Tupel (Zeilen) in der Resultatstabelle ist das Ergebnis der Multiplikation der Zeilenanzahlen der Ausgangstabellen (z. B. 3 Zeilen in R und 4 Zeilen in S ergeben 12 Zeilen im Kartesischen Produkt).

=== Projektion ===
Die Projektion (<math>\pi</math>) kann ohne Voraussetzungen durchgeführt werden. Sie extrahiert einzelne Attribute (Spalten) aus der ursprünglichen Attributmenge und ist somit als eine Art Filterung auf Spaltenebene zu verstehen. Die Projektion blendet also Spalten aus. Entstehen durch das Ausblenden von Spalten identische Zeilen, werden diese Duplikate in der Ergebnisrelation eliminiert.

'''Beispiel:''' Aus einer Mitarbeitertabelle mit {Personalnummer, Name, Abteilung} wird durch Projektion nur die Spalte {Abteilung} extrahiert. Das Ergebnis ist eine Liste aller Abteilungen ohne Duplikate.

=== Selektion (Selection) ===
Die Selektion (<math>\sigma</math>) kann ebenfalls ohne Voraussetzungen zur Kompatibilität mit anderen Tabellen durchgeführt werden, da sie nur auf einer Relation operiert. Sie extrahiert einzelne Tupel (Datensätze), die eine bestimmte Bedingung erfüllen, aus der ursprünglichen Relation. Sie ist somit als eine Art Filterung auf Zeilenebene zu verstehen (das heißt, die Selektion blendet Zeilen aus, die das Kriterium nicht erfüllen).

'''Beispiel:''' Aus einer Mitarbeitertabelle werden durch Selektion nur die Tupel extrahiert, bei denen das Attribut ''Gehalt > 3000'' ist.

[[Kategorie:Datenbanken]]
[[Kategorie:AHR_I_Informatik LK]]
[[Kategorie:FI_I_SDM]]

DCL

Flbkwikiadmin — Fri, 17 Apr 2026 09:33:33 GMT

Die Seite wurde neu angelegt: „== Einführung == Die '''Data Control Language''' (kurz '''DCL''') ist die Datenüberwachungs- und Berechtigungssprache und ein Teilbereich der Structured Query Language (SQL). Sie wird in relationalen Datenbanksystemen verwendet, um Zugriffsrechte, Rollen und Sicherheitsrichtlinien für Datenbankbenutzer zu verwalten (Berechtigungen vergeben oder entziehen). == Abgrenzung und Systemabhängigkeit == Die Implementierung der DCL existiert in unters…“

Neue Seite

== Einführung ==
Die '''Data Control Language''' (kurz '''DCL''') ist die Datenüberwachungs- und Berechtigungssprache und ein Teilbereich der [[SQL|Structured Query Language (SQL)]]. Sie wird in relationalen Datenbanksystemen verwendet, um Zugriffsrechte, Rollen und Sicherheitsrichtlinien für Datenbankbenutzer zu verwalten (Berechtigungen vergeben oder entziehen).

== Abgrenzung und Systemabhängigkeit ==
Die Implementierung der DCL existiert in unterschiedlichen Datenbanksystemen in verschiedenen Ausprägungen. Es gibt in der Datenbankwelt keine absolut einheitliche Trennung der SQL-Teilsprachen: Einige Datenbank-Hersteller verwenden den isolierten Begriff der DCL nicht und zählen die Berechtigungsbefehle stattdessen mit zur [[Data Definition Language]] (DDL) oder zur Systemverwaltung.

== Die Kernbefehle der DCL ==
Die Zugriffssteuerung in SQL basiert primär auf zwei fundamentalen Befehlen: '''GRANT''' und '''REVOKE'''.

=== GRANT (Rechte vergeben) ===
Mit dem Befehl `GRANT` werden einem Datenbankbenutzer oder einer Benutzerrolle spezifische Berechtigungen (Privilegien) für bestimmte Datenbankobjekte (wie Tabellen, Views oder die gesamte Datenbank) erteilt.

'''Syntax:'''
<syntaxhighlight lang="sql">
GRANT <Privilegien> ON <Datenbankobjekt> TO <Benutzer>;
</syntaxhighlight>

'''Beispiel:'''
Einem Benutzer namens ''mitarbeiter'' wird das Recht gegeben, Datensätze in der Tabelle `salon` der Datenbank `friseur` zu lesen (`SELECT`) und neue Datensätze hinzuzufügen (`INSERT`).
<syntaxhighlight lang="sql">
GRANT SELECT, INSERT ON friseur.salon TO 'mitarbeiter'@'localhost';
</syntaxhighlight>

=== REVOKE (Rechte entziehen) ===
Der Befehl `REVOKE` ist das Gegenstück zu `GRANT` und wird verwendet, um zuvor erteilte Berechtigungen wieder zu entziehen.

'''Syntax:'''
<syntaxhighlight lang="sql">
REVOKE <Privilegien> ON <Datenbankobjekt> FROM <Benutzer>;
</syntaxhighlight>

'''Beispiel:'''
Dem Benutzer ''mitarbeiter'' wird das Recht, Datensätze hinzuzufügen, wieder entzogen. Das Leserecht bleibt dabei bestehen.
<syntaxhighlight lang="sql">
REVOKE INSERT ON friseur.salon FROM 'mitarbeiter'@'localhost';
</syntaxhighlight>

== Typische Berechtigungen (Privilegien) ==
Beim Vergeben oder Entziehen von Rechten können verschiedene Abstufungen vorgenommen werden. Zu den gängigsten Privilegien gehören:

{| class="wikitable"
! Privileg !! Beschreibung
|-
| '''SELECT''' || Erlaubt das Abfragen/Lesen von Daten (DQL).
|-
| '''INSERT''' || Erlaubt das Einfügen neuer Datensätze (DML).
|-
| '''UPDATE''' || Erlaubt das Ändern bestehender Datensätze (DML).
|-
| '''DELETE''' || Erlaubt das Löschen von Datensätzen (DML).
|-
| '''ALL PRIVILEGES''' || Erteilt alle verfügbaren Rechte für das angegebene Objekt (oft Administratoren vorbehalten).
|}

== Herstellerspezifische Umsetzung (MySQL) ==
Da die genaue Syntax für die Benutzerverwaltung (z. B. das Anlegen von Benutzern mit Passwörtern) stark vom eingesetzten Datenbankmanagementsystem abhängt, weichen die Befehle in der Praxis oft leicht ab. Der exakte Befehlsumfang der DCL für das Produkt MySQL (von Oracle) kann im offiziellen MySQL-Manual nachgeschlagen werden.

[[Kategorie:SQL]]
[[Kategorie:Datenbanken]]
[[Kategorie:AHR_I_Informatik LK]]
[[Kategorie:FI_I_SDM]]

DDL

Flbkwikiadmin — Fri, 17 Apr 2026 09:31:42 GMT

← Nächstältere Version		Version vom 17. April 2026, 11:31 Uhr
(3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1:		Zeile 1:
	== Einstieg ==		== Einstieg ==
	Die '''Data Definition Language''' (kurz '''DDL''') ist ein fundamentaler Bestandteil von SQL. Die DDL wird eingesetzt, um das Datenschema in relationalen Datenbanken zu beschreiben, zu ändern oder zu entfernen. Das Erstellen von Tabellen mit Hilfe der DDL ist in der Regel der letzte strukturelle Schritt im Datenbankenentwicklungsprozess, bevor Daten eingefügt werden können.		Die '''Data Definition Language''' (kurz '''DDL''') ist ein fundamentaler Bestandteil von SQL. Die DDL wird eingesetzt, um das Datenschema in relationalen Datenbanken zu beschreiben, zu ändern oder zu entfernen. Das Erstellen von Tabellen mit Hilfe der DDL ist in der Regel der letzte strukturelle Schritt im Datenbankenentwicklungsprozess, bevor Daten eingefügt werden können.
			[[Datei:ERM-Softwarentwicklungsprozess.png\|mini]]
	---		[[Datei:DBMS-MySQL.png\|mini\|Darstellung in der MySQL-Workbench]]
			[[Datei:Schlüssel-SchlüsselInTabellen.png\|mini]]
	== CREATE SCHEMA ==		== CREATE SCHEMA ==
	Alle Datenbank-Tabellen befinden sich in einem Schema. Dieses Schema repräsentiert die Datenbank an sich. Bevor Tabellen angelegt werden können, muss ein Schema vorhanden sein.		Alle Datenbank-Tabellen befinden sich in einem Schema. Dieses Schema repräsentiert die Datenbank an sich. Bevor Tabellen angelegt werden können, muss ein Schema vorhanden sein.
Zeile 21:		Zeile 21:

	Das Schema `friseur` verwaltet alle Salons. Eine Tabelle `Salon` lässt sich also über `friseur.salon` ansprechen.		Das Schema `friseur` verwaltet alle Salons. Eine Tabelle `Salon` lässt sich also über `friseur.salon` ansprechen.

	~~---~~

	== CREATE TABLE ==		== CREATE TABLE ==
Zeile 53:		Zeile 51:
	);		);
	</syntaxhighlight>		</syntaxhighlight>

	~~---~~

	== CONSTRAINTs (Einschränkungen) ==		== CONSTRAINTs (Einschränkungen) ==
Zeile 109:		Zeile 105:
	);		);
	</syntaxhighlight>		</syntaxhighlight>



	==== FOREIGN KEY Optionen (Referenzielle Aktionen) ====		==== FOREIGN KEY Optionen (Referenzielle Aktionen) ====
Zeile 148:		Zeile 142:
	);		);
	</syntaxhighlight>		</syntaxhighlight>

	~~---~~

	== ALTER TABLE ==		== ALTER TABLE ==
Zeile 170:		Zeile 162:
	ALTER TABLE Mitarbeiter ADD (istWeiblich BOOLEAN);		ALTER TABLE Mitarbeiter ADD (istWeiblich BOOLEAN);
	</syntaxhighlight>		</syntaxhighlight>

	~~---~~

	== DROP TABLE ==		== DROP TABLE ==
Zeile 178:		Zeile 168:
	DROP TABLE <Tabellen_Name>;		DROP TABLE <Tabellen_Name>;
	</syntaxhighlight>		</syntaxhighlight>

	~~---~~

	== CREATE VIEW ==		== CREATE VIEW ==

DDL

Flbkwikiadmin — Fri, 17 Apr 2026 09:24:39 GMT

Die Seite wurde neu angelegt: „== Einstieg == Die '''Data Definition Language''' (kurz '''DDL''') ist ein fundamentaler Bestandteil von SQL. Die DDL wird eingesetzt, um das Datenschema in relationalen Datenbanken zu beschreiben, zu ändern oder zu entfernen. Das Erstellen von Tabellen mit Hilfe der DDL ist in der Regel der letzte strukturelle Schritt im Datenbankenentwicklungsprozess, bevor Daten eingefügt werden können. --- == CREATE SCHEMA == Alle Datenbank-Tabellen befinden sich…“

Neue Seite

== Einstieg ==
Die '''Data Definition Language''' (kurz '''DDL''') ist ein fundamentaler Bestandteil von SQL. Die DDL wird eingesetzt, um das Datenschema in relationalen Datenbanken zu beschreiben, zu ändern oder zu entfernen. Das Erstellen von Tabellen mit Hilfe der DDL ist in der Regel der letzte strukturelle Schritt im Datenbankenentwicklungsprozess, bevor Daten eingefügt werden können.

---

== CREATE SCHEMA ==
Alle Datenbank-Tabellen befinden sich in einem Schema. Dieses Schema repräsentiert die Datenbank an sich. Bevor Tabellen angelegt werden können, muss ein Schema vorhanden sein.

'''Syntax:'''
<syntaxhighlight lang="sql">
CREATE SCHEMA <Schema-Name>;
</syntaxhighlight>

'''Beispiel:'''
<syntaxhighlight lang="sql">
CREATE SCHEMA friseur;
</syntaxhighlight>

In einem Datenbankmanagementsystem (DBMS) können mehrere Schemata verwaltet werden. Daher ist sicherzustellen, dass sich alle Anweisungen der SQL eindeutig auf ein Schema beziehen lassen, damit das DBMS die angesprochenen Tabellen identifizieren kann. Der Bezug zu einem Schema ergibt sich aus der Punktnotation:
<code>Schemaname.Tabellenname</code>

Das Schema `friseur` verwaltet alle Salons. Eine Tabelle `Salon` lässt sich also über `friseur.salon` ansprechen.

---

== CREATE TABLE ==
Tabellen stellen die Grundstruktur für die Speicherung von Daten in der Datenbank dar.

'''Syntax:'''
<syntaxhighlight lang="sql">
CREATE TABLE <Tabellen_Name> (
<Spalte 1> <Datentyp_für_Spalte_1>,
<Spalte 2> <Datentyp_für_Spalte_2>,
...
);
</syntaxhighlight>

'''Beispiele:'''
Zur Erstellung einer einfachen Mitarbeitertabelle:
<syntaxhighlight lang="sql">
CREATE TABLE mitarbeiter (
idmitarbeiter INT,
nachname VARCHAR(45),
vorname VARCHAR(45)
);
</syntaxhighlight>

Zur Erstellung einer simplen Salontabelle:
<syntaxhighlight lang="sql">
CREATE TABLE salon (
idsalon INT,
name VARCHAR(45)
);
</syntaxhighlight>

---

== CONSTRAINTs (Einschränkungen) ==
CONSTRAINT heißt übersetzt "Zwang" oder "Einschränkung". Ein CONSTRAINT ist eine Bedingung, der ein Datensatz zwingend entsprechen muss. Wenn eine der aktuell gültigen Bedingungen verletzt wird, wird der betreffende Datensatz nicht gespeichert. Hierdurch wird die '''Datenkonsistenz''' gewährleistet.

Die Befehle `PRIMARY KEY`, `FOREIGN KEY`, `NOT NULL` und `UNIQUE` fallen in die Kategorie CONSTRAINT. Nach der Attributliste wird das Schlüsselwort `CONSTRAINT` gesetzt (wobei das Wort `CONSTRAINT` selbst oft optional ist, wenn man die Standardnamen des DBMS akzeptiert).

=== Primärschlüssel (PRIMARY KEY) ===
Es gibt drei Varianten, um die Entitätsintegrität (Eindeutigkeit) mit Hilfe eines Primärschlüssels zu definieren:

1. '''Am Ende der Attributliste:'''
<syntaxhighlight lang="sql">
CREATE TABLE mitarbeiter (
idmitarbeiter INT,
nachname VARCHAR(45),
vorname VARCHAR(45),
PRIMARY KEY (idmitarbeiter)
);
</syntaxhighlight>

2. '''Direkt in der Spaltendefinition:'''
<syntaxhighlight lang="sql">
CREATE TABLE mitarbeiter (
idmitarbeiter INT PRIMARY KEY,
nachname VARCHAR(45),
vorname VARCHAR(45)
);
</syntaxhighlight>

3. '''Mit explizitem CONSTRAINT-Namen:''' (Im Beispiel "pk" für primary key)
<syntaxhighlight lang="sql">
CREATE TABLE mitarbeiter (
idmitarbeiter INT,
nachname VARCHAR(45),
vorname VARCHAR(45),
fksalon INT,
CONSTRAINT pk PRIMARY KEY (idmitarbeiter)
);
</syntaxhighlight>

=== Fremdschlüssel (FOREIGN KEY) ===
Mit einem Fremdschlüssel wird eine Spalte der einen Tabelle mit einer gleichartigen Spalte einer anderen Tabelle (meist dem Primärschlüssel) verknüpft, um referenzielle Integrität sicherzustellen. Beide Spalten müssen den exakt gleichen Datentyp besitzen.

> '''Wichtig:''' Die referenzierte Tabelle (hier `salon`) muss bereits existieren, bevor der Fremdschlüssel in der referenzierenden Tabelle (`mitarbeiter`) angelegt werden kann.

<syntaxhighlight lang="sql">
CREATE TABLE mitarbeiter (
idmitarbeiter INT,
nachname VARCHAR(45),
vorname VARCHAR(45),
fksalon INT,
CONSTRAINT pk PRIMARY KEY (idmitarbeiter),
CONSTRAINT fk FOREIGN KEY (fksalon) REFERENCES salon(idsalon)
);
</syntaxhighlight>

==== FOREIGN KEY Optionen (Referenzielle Aktionen) ====
Diese Optionen bestimmen das Verhalten der Detailtabelle, wenn in der Primärtabelle Datensätze geändert (`ON UPDATE`) oder gelöscht (`ON DELETE`) werden:

* '''NO ACTION / RESTRICT''': Die Änderung oder Löschung in der Primärtabelle wird verweigert und mit einem Fehler abgebrochen, falls abhängige Datensätze existieren.
* '''CASCADE''': Die Änderung (z. B. eine neue ID) oder die Löschung wird "kaskadierend" an die Detailtabelle weitergegeben. Löscht man den Salon, werden alle Mitarbeiter dieses Salons ebenfalls gelöscht.
* '''SET NULL''': Wird der Primärschlüssel gelöscht oder geändert, wird der Fremdschlüssel in der Detailtabelle auf `NULL` gesetzt (nur möglich, wenn die Spalte nicht als `NOT NULL` definiert ist).

=== NOT NULL ===
Die Schlüsselwörter `NULL` bzw. `NOT NULL` legen fest, ob leere Werte in der Spalte zulässig sind. Der Standardwert ist "zulässig" (`NULL`). Primärschlüssel sollten grundsätzlich als `NOT NULL` deklariert werden.

=== AUTO_INCREMENT / AUTOINCREMENT ===
Dieses Schlüsselwort legt fest, dass die Werte in der Spalte automatisch vom DBMS hochgezählt werden (z. B. für IDs).
* '''In MySQL:''' `idSalon INT AUTO_INCREMENT`
* '''In MS Access:''' `idSalon AUTOINCREMENT` (wird hier wie ein eigener Datentyp behandelt).

=== DEFAULT ===
Legt einen Standardwert fest, der eingesetzt wird, wenn bei einem neuen Datensatz kein Wert für diese Spalte übergeben wird. (Achtung: Wird in MS Access in reinem DDL oft nicht nativ unterstützt).
<syntaxhighlight lang="sql">
fksalon INT NOT NULL DEFAULT 1
</syntaxhighlight>

=== UNIQUE ===
Sorgt dafür, dass innerhalb einer Spalte (oder Spaltenkombination) kein Wert doppelt auftreten darf.

'''Komplexes Beispiel (Zusammenführung aller Constraints):'''
<syntaxhighlight lang="sql">
CREATE TABLE mitarbeiter (
idmitarbeiter INT NOT NULL AUTO_INCREMENT,
nachname VARCHAR(45),
vorname VARCHAR(45),
fksalon INT NOT NULL DEFAULT 1,
CONSTRAINT pk_mitarbeiter PRIMARY KEY (idmitarbeiter),
CONSTRAINT fk_salon FOREIGN KEY (fksalon) REFERENCES salon(idsalon),
CONSTRAINT uq_nachname UNIQUE (nachname)
);
</syntaxhighlight>

---

== ALTER TABLE ==
`ALTER TABLE` ermöglicht das nachträgliche Ändern der Struktur einer vorhandenen Tabelle.

Mögliche Änderungsoperatoren sind:
* '''ADD''': Spalten/Constraints hinzufügen.
* '''DROP''': Spalten/Constraints entfernen.
* '''MODIFY / ALTER COLUMN''': Datentypen ändern.
* '''RENAME''': Umbenennen.

'''Beispiele:'''
Tabelle umbenennen:
<syntaxhighlight lang="sql">
ALTER TABLE Salon RENAME TO Filiale;
</syntaxhighlight>

Neue Spalte hinzufügen:
<syntaxhighlight lang="sql">
ALTER TABLE Mitarbeiter ADD (istWeiblich BOOLEAN);
</syntaxhighlight>

---

== DROP TABLE ==
Löscht eine vollständige Tabelle inklusive aller darin enthaltenen Daten unwiderruflich aus der Datenbank.
<syntaxhighlight lang="sql">
DROP TABLE <Tabellen_Name>;
</syntaxhighlight>

---

== CREATE VIEW ==
Abfragen (DQL) können als sogenannte '''Views''' (Sichten/virtuelle Tabellen) in der Datenbank gespeichert werden. Sie verhalten sich bei Abfragen wie echte Tabellen, speichern aber keine eigenen Daten, sondern führen die hinterlegte `SELECT`-Abfrage bei jedem Aufruf dynamisch aus.

'''Syntax:'''
<syntaxhighlight lang="sql">
CREATE VIEW <View-Name> AS <Select-Ausdruck>;
</syntaxhighlight>

'''Beispiel:'''
<syntaxhighlight lang="sql">
CREATE VIEW weiblicheMitarbeiter AS
SELECT vorname, nachname
FROM mitarbeiter
WHERE istWeiblich = TRUE;
</syntaxhighlight>

[[Kategorie:Datenbanken]]
[[Kategorie:AHR_I_Informatik LK]]
[[Kategorie:FI_I_SDM]]

Funktionale Abhängigkeit

Flbkwikiadmin — Fri, 17 Apr 2026 08:56:16 GMT

← Nächstältere Version		Version vom 17. April 2026, 10:56 Uhr
Zeile 1:		Zeile 1:
	== Einführung ==		== Einführung ==
	'''Funktionale Abhängigkeiten''' bilden ~~die Grundlage~~ für die [[Normalisierung]] von Relationenschemata und die Bestimmung von [[Primärschlüssel]]n. [[Relation (Datenbanken)\|Relationen]] ~~werden durch~~ [[Attribut\|~~Attribute~~]] ~~definiert~~. ~~Bestimmen einige dieser Attribute~~ eindeutig ~~die Werte anderer Attribute~~, ~~so spricht man von funktionaler~~ Abhängigkeit.		'''Funktionale Abhängigkeiten''' bilden das theoretische Fundament für die [[Normalisierung]] von Relationenschemata und die Bestimmung von [[Primärschlüssel]]n. [[Relation (Datenbanken)\|Relationen]] bestehen aus einer Menge von [[Attribut\|Attributen]]. Bestimmt der Wert eines bestimmten Attributs (oder einer Attributkombination) eindeutig den Wert eines anderen Attributs, liegt zwischen ihnen eine funktionale Abhängigkeit vor.

	== Funktionale Abhängigkeit ==		== Funktionale Abhängigkeit ==
	~~Betrachtet man folgende~~ Relation~~, wird man feststellen~~, dass die Attribute ''Nachname'' und ''Vorname'' ~~abhängig sind von~~ der ''IdMitarbeiter''. ~~Man~~ sagt ~~in diesem Zusammenhang, die~~ Attribute Nachname und Vorname sind funktional abhängig von ~~der~~ IdMitarbeiter.		Anhand der folgenden Relation lässt sich erkennen, dass die Attribute ''Nachname'' und ''Vorname'' stets eindeutig mit der ''IdMitarbeiter'' verknüpft sind. In der Fachsprache sagt man: Die Attribute Nachname und Vorname sind funktional abhängig von IdMitarbeiter.

	{\| class="wikitable"		{\| class="wikitable"
Zeile 21:		Zeile 21:
	\|}		\|}

	Wenn ~~man also~~ die `IdMitarbeiter` ~~kennt~~, ~~kann man auch den Namen des Mitarbeiters benennen~~. ~~Andersherum ist der Schluss~~ nicht ~~möglich~~: Ist der Nachname bekannt (z. B. Krause), lässt sich die `IdMitarbeiter` nicht eindeutig ~~bestimmen~~.		Wenn die `IdMitarbeiter` bekannt ist, lässt sich der Name der Person zweifelsfrei bestimmen. Die Umkehrung gilt jedoch nicht: Ist lediglich der Nachname bekannt (z. B. Krause), lässt sich die `IdMitarbeiter` nicht eindeutig ermitteln, da es mehrere Mitarbeiter mit diesem Nachnamen geben kann.

	~~In Anlehnung an die~~ Mathematik ~~wird hier von der funktionalen Abhängigkeit gesprochen, da eine~~ mathematische Funktion ~~immer den gleichen~~ Ausgabewert ~~bei gleichen Eingabewerten liefert~~. Die Funktion ~~\({~~ y = 3 \cdot x ~~}\)~~ liefert für ~~\({~~ x = 4 ~~}\)~~ immer ~~die Ausgabe \(~~12~~\) für die Variable \(y\). Für jede beliebige Zahl, die man für die Variable \(x\) einsetzt, ergibt sich also ein ganz bestimmter Wert für \(y\)~~. ~~Man kann sagen, dass der~~ Wert \(y\) abhängig ~~ist~~ vom Wert \(~~x\)~~ bzw. \(x\) bestimmt \(y\).		Der Begriff leitet sich aus der Mathematik ab: Eine mathematische Funktion ordnet jedem Eingabewert exakt einen definierten Ausgabewert zu. Die Funktion <math>y = 3 \cdot x</math> liefert für <math>x = 4</math> immer das Ergebnis <math>12</math>. Der Wert <math>y</math> ist somit abhängig vom Wert <math>x</math> (bzw. <math>x</math> bestimmt <math>y</math>).

	~~Mathematisch~~ spricht man ~~auch~~ von einer '''Determinante''' und ~~schreibt~~:		In der Relationenalgebra spricht man hierbei von einer '''Determinante''' (Bestimmer) und notiert dies mit einem Pfeil:
	~~\({ x~~ \rightarrow ~~y }\)~~		<math>X \rightarrow Y</math>

	~~Analog~~ schreibt man ~~also für die besprochene funktionale Abhängigkeit der Attribute~~:		Für die beschriebene Datenbank-Abhängigkeit schreibt man formal:
	~~\({~~ \text{IdMitarbeiter} \rightarrow \text{Nachname}, \text{Vorname} ~~}\)~~		<math>\text{IdMitarbeiter} \rightarrow \text{Nachname}, \text{Vorname}</math>

	> '''Wichtig:''' ~~Die~~ funktionale Abhängigkeit ~~muss~~ für alle möglichen ~~bzw. denkbaren~~ Tupel (Datensätze) ~~einer~~ Relation ~~gelten~~.		> '''Wichtig:''' Eine funktionale Abhängigkeit ist nur dann gültig, wenn sie für ''alle'' möglichen, fachlich zulässigen Tupel (Datensätze) der Relation gilt, nicht nur für den aktuell gespeicherten Zustand.

	== Volle funktionale Abhängigkeit ==		== Volle funktionale Abhängigkeit ==
	~~Man spricht von~~ '''~~voller funktionaler~~ Abhängigkeit''', wenn ~~jedes~~ Nichtschlüssel-Attribut ~~nur durch den~~ ''gesamten'' Primärschlüssel ~~eindeutig~~ bestimmt werden kann.		Von einer '''vollen funktionalen Abhängigkeit''' spricht man, wenn ein Nichtschlüssel-Attribut zwingend vom ''gesamten'' Primärschlüssel abhängig ist und nicht schon durch eine Teilmenge des Schlüssels bestimmt werden kann. Dies ist insbesondere bei zusammengesetzten Schlüsseln relevant.

	~~Nehmen wir an~~, der ~~zusammengesetzte~~ Primärschlüssel der obigen Relation ~~würde sich~~ aus ~~den Attributen~~ `IdMitarbeiter` und `Nachname` ~~zusammensetzen~~. Es gälte ~~also~~:		Angenommen, der Primärschlüssel der obigen Relation bestünde aus der Kombination von `IdMitarbeiter` und `Nachname`. Es gälte formal:
	~~\({~~ (\text{IdMitarbeiter}, \text{Nachname}) \rightarrow \text{Vorname} ~~}\)~~		<math>(\text{IdMitarbeiter}, \text{Nachname}) \rightarrow \text{Vorname}</math>
	(Vorname ist funktional von ~~IdMitarbeiter~~ und Nachname ~~abhängig~~.)		(Der Vorname ist funktional abhängig von der Kombination aus ID und Nachname).

	~~Allerdings~~ ist ~~der Vorname nicht vom Nachnamen funktional abhängig. Der Vorname „Claudia“ gilt sowohl für Schulze als auch für Schrotter~~. Das Attribut `IdMitarbeiter` ~~bestimmt aber nach wie vor alleine und~~ eindeutig ~~das Attribut `Vorname`. Auf das Attribut `Nachname` kann also im Schlüssel verzichtet werden~~.		Prüft man dies genauer, stellt man fest, dass das Attribut `Nachname` für die Bestimmung des Vornamens überflüssig ist. Das Attribut `IdMitarbeiter` reicht bereits völlig aus, um den Vornamen eindeutig zu ermitteln.

	Da das Nichtschlüssel-Attribut `Vorname` ~~auch~~ durch einen Teil des Primärschlüssels ~~– nämlich~~ `IdMitarbeiter` – bestimmbar ist, ist `Vorname` '''nicht voll funktional abhängig''' ~~von der Kombination aus IdMitarbeiter und Nachname~~. ~~Die~~ volle funktionale Abhängigkeit ~~würde hier~~ nur ~~für das isolierte Attribut `IdMitarbeiter` gelten~~.		Da das Nichtschlüssel-Attribut `Vorname` bereits durch einen Teil des Primärschlüssels (`IdMitarbeiter`) bestimmbar ist, ist `Vorname` '''nicht voll funktional abhängig''' vom zusammengesetzten Schlüssel. Eine volle funktionale Abhängigkeit läge nur dann vor, wenn zur Bestimmung zwingend ''beide'' Attribute des Schlüssels benötigt würden.

	== Transitive Abhängigkeit ==		== Transitive Abhängigkeit ==
	~~Angenommen~~, ~~wir haben~~ eine ~~Relation \(R\) mit den Attributen \(A\), \(B\) und \(C\).~~		Eine '''transitive Abhängigkeit''' liegt vor, wenn eine Abhängigkeit "über eine Zwischenstation" besteht.
	* \(A\) ist der Primärschlüssel.
	* \(A\) bestimmt \(B\) (\({ A \rightarrow B }\)).
	* \(B\) ist nicht Teil des Primärschlüssels.
	* Dennoch gilt \({ B \rightarrow C }\).

	~~Somit~~ ist \(C\) '''transitiv''' ~~von \~~(A\) ~~abhängig~~.		Gegeben sei eine Relation <math>R</math> mit den Attributen <math>A</math>, <math>B</math> und <math>C</math>.
			* <math>A</math> ist der Primärschlüssel.
			* <math>A</math> bestimmt <math>B</math> (<math>A \rightarrow B</math>).
			* <math>B</math> ist kein Bestandteil des Primärschlüssels.
			* Dennoch bestimmt <math>B</math> eindeutig <math>C</math> (<math>B \rightarrow C</math>).

			In diesem Fall ist <math>C</math> zwar funktional von <math>A</math> abhängig, aber eben nur '''transitiv''' (indirekt) über das Attribut <math>B</math>.

	'''Beispiel aus der Praxis:'''		'''Beispiel aus der Praxis:'''
	Mit Hilfe des Primärschlüssels `IdMitarbeiter` lässt sich eindeutig ~~der Salon~~ bestimmen, in dem der Mitarbeiter arbeitet. ~~Allerdings~~ hängt ~~der Salonname~~ funktional von der `IdSalon` ab ~~und somit~~ nur ''transitiv'' von der `IdMitarbeiter`.		Mit Hilfe des Primärschlüssels `IdMitarbeiter` lässt sich eindeutig die ID des Salons (`IdSalon`) bestimmen, in dem der Mitarbeiter arbeitet. Der Klarname des Salons (`Salonname`) hängt jedoch funktional direkt von der `IdSalon` ab. Somit ist der `Salonname` nur transitiv von der `IdMitarbeiter` abhängig.

	Um ~~ein solches Schema~~ in die [[Normalisierung#Die_3._Normalform_(3NF)\|3. Normalform (3NF)]] zu überführen, müssen die Saloninformationen in ~~eine~~ eigene ~~Relation~~ ausgelagert werden.		Um solche Schemata zu optimieren und in die [[Normalisierung#Die_3._Normalform_(3NF)\|3. Normalform (3NF)]] zu überführen, müssen Attribute mit transitiven Abhängigkeiten (wie die Saloninformationen) in eigene Relationen ausgelagert werden.

	[[Kategorie:Datenbanken]]		[[Kategorie:Datenbanken]]
			[[Kategorie:AHR_I_Informatik LK]]
	[[Kategorie:FI_I_SDM]]		[[Kategorie:FI_I_SDM]]

Normalisierung

Flbkwikiadmin — Fri, 17 Apr 2026 08:55:51 GMT

Änderungen zeigen

Funktionale Abhängigkeit

Flbkwikiadmin — Thu, 16 Apr 2026 12:27:35 GMT

Die Seite wurde neu angelegt: „== Einführung == '''Funktionale Abhängigkeiten''' bilden die Grundlage für die Normalisierung von Relationenschemata und die Bestimmung von Primärschlüsseln. Relationen werden durch Attribute definiert. Bestimmen einige dieser Attribute eindeutig die Werte anderer Attribute, so spricht man von funktionaler Abhängigkeit. == Funktionale Abhängigkeit == Betrachtet man folgende Relation, wird man festste…“

Neue Seite

== Einführung ==
'''Funktionale Abhängigkeiten''' bilden die Grundlage für die [[Normalisierung]] von Relationenschemata und die Bestimmung von [[Primärschlüssel]]n. [[Relation (Datenbanken)|Relationen]] werden durch [[Attribut|Attribute]] definiert. Bestimmen einige dieser Attribute eindeutig die Werte anderer Attribute, so spricht man von funktionaler Abhängigkeit.

== Funktionale Abhängigkeit ==
Betrachtet man folgende Relation, wird man feststellen, dass die Attribute ''Nachname'' und ''Vorname'' abhängig sind von der ''IdMitarbeiter''. Man sagt in diesem Zusammenhang, die Attribute Nachname und Vorname sind funktional abhängig von der IdMitarbeiter.

{| class="wikitable"
! IdMitarbeiter !! Nachname !! Vorname
|-
| 1 || Krause || Sabine
|-
| 2 || Schrotter || Claudia
|-
| 3 || Hermann || Markus
|-
| 4 || Krause || Christoph
|-
| 5 || Bitter || Manuel
|-
| 6 || Schulze || Claudia
|}

Wenn man also die `IdMitarbeiter` kennt, kann man auch den Namen des Mitarbeiters benennen. Andersherum ist der Schluss nicht möglich: Ist der Nachname bekannt (z. B. Krause), lässt sich die `IdMitarbeiter` nicht eindeutig bestimmen.

In Anlehnung an die Mathematik wird hier von der funktionalen Abhängigkeit gesprochen, da eine mathematische Funktion immer den gleichen Ausgabewert bei gleichen Eingabewerten liefert. Die Funktion \({ y = 3 \cdot x }\) liefert für \({ x = 4 }\) immer die Ausgabe \(12\) für die Variable \(y\). Für jede beliebige Zahl, die man für die Variable \(x\) einsetzt, ergibt sich also ein ganz bestimmter Wert für \(y\). Man kann sagen, dass der Wert \(y\) abhängig ist vom Wert \(x\) bzw. \(x\) bestimmt \(y\).

Mathematisch spricht man auch von einer '''Determinante''' und schreibt:
\({ x \rightarrow y }\)

Analog schreibt man also für die besprochene funktionale Abhängigkeit der Attribute:
\({ \text{IdMitarbeiter} \rightarrow \text{Nachname}, \text{Vorname} }\)

> '''Wichtig:''' Die funktionale Abhängigkeit muss für alle möglichen bzw. denkbaren Tupel (Datensätze) einer Relation gelten.

== Volle funktionale Abhängigkeit ==
Man spricht von '''voller funktionaler Abhängigkeit''', wenn jedes Nichtschlüssel-Attribut nur durch den ''gesamten'' Primärschlüssel eindeutig bestimmt werden kann.

Nehmen wir an, der zusammengesetzte Primärschlüssel der obigen Relation würde sich aus den Attributen `IdMitarbeiter` und `Nachname` zusammensetzen. Es gälte also:
\({ (\text{IdMitarbeiter}, \text{Nachname}) \rightarrow \text{Vorname} }\)
(Vorname ist funktional von IdMitarbeiter und Nachname abhängig.)

Allerdings ist der Vorname nicht vom Nachnamen funktional abhängig. Der Vorname „Claudia“ gilt sowohl für Schulze als auch für Schrotter. Das Attribut `IdMitarbeiter` bestimmt aber nach wie vor alleine und eindeutig das Attribut `Vorname`. Auf das Attribut `Nachname` kann also im Schlüssel verzichtet werden.

Da das Nichtschlüssel-Attribut `Vorname` auch durch einen Teil des Primärschlüssels – nämlich `IdMitarbeiter` – bestimmbar ist, ist `Vorname` '''nicht voll funktional abhängig''' von der Kombination aus IdMitarbeiter und Nachname. Die volle funktionale Abhängigkeit würde hier nur für das isolierte Attribut `IdMitarbeiter` gelten.

== Transitive Abhängigkeit ==
Angenommen, wir haben eine Relation \(R\) mit den Attributen \(A\), \(B\) und \(C\).
* \(A\) ist der Primärschlüssel.
* \(A\) bestimmt \(B\) (\({ A \rightarrow B }\)).
* \(B\) ist nicht Teil des Primärschlüssels.
* Dennoch gilt \({ B \rightarrow C }\).

Somit ist \(C\) '''transitiv''' von \(A\) abhängig.

'''Beispiel aus der Praxis:'''
Mit Hilfe des Primärschlüssels `IdMitarbeiter` lässt sich eindeutig der Salon bestimmen, in dem der Mitarbeiter arbeitet. Allerdings hängt der Salonname funktional von der `IdSalon` ab und somit nur ''transitiv'' von der `IdMitarbeiter`.

Um ein solches Schema in die [[Normalisierung#Die_3._Normalform_(3NF)|3. Normalform (3NF)]] zu überführen, müssen die Saloninformationen in eine eigene Relation ausgelagert werden.

[[Kategorie:Datenbanken]]
[[Kategorie:FI_I_SDM]]

Normalisierung

Flbkwikiadmin — Thu, 16 Apr 2026 12:23:59 GMT

Die Seite wurde neu angelegt: „== Einführung == Unter '''Normalisierung''' eines relationalen Datenbankmodells versteht man die Aufteilung von Attributen in mehrere Relationen (Tabellen) mithilfe der Normalisierungsregeln und deren Normalformen, sodass ein Schema entsteht, das keine vermeidbaren '''Redundanzen''' mehr enthält. Das Ziel ist die redundanzfreie Datenspeicherung. Ein Schema, das Redundanzen enthält, kann dazu führen, dass bei Änderungen die…“

Neue Seite

== Einführung ==
Unter '''Normalisierung''' eines relationalen Datenbankmodells versteht man die Aufteilung von Attributen in mehrere [[Relation (Datenbanken)|Relationen]] (Tabellen) mithilfe der Normalisierungsregeln und deren Normalformen, sodass ein Schema entsteht, das keine vermeidbaren '''Redundanzen''' mehr enthält.

Das Ziel ist die redundanzfreie Datenspeicherung. Ein Schema, das Redundanzen enthält, kann dazu führen, dass bei Änderungen die mehrfach enthaltenen Daten nicht konsistent, sondern nur teilweise und unvollständig geändert werden. Hierdurch können die Datenänderungen überflüssig oder widersprüchlich werden. Außerdem können [[Anomalie|Anomalien]] auftreten. Zudem belegt das mehrfache Speichern derselben Daten unnötig Speicherplatz.

Es gibt verschiedene Grade der Normalisierung: Die so genannte erste, zweite, dritte usw. Normalform. Diese Normalformen sind durch formale Anforderungen definiert.

Man bringt ein relationales Schema in eine Normalform, indem man für sie geltende funktionale Abhängigkeiten in einfachere Relationen zerlegt, bis keine weitere Zerlegung mehr möglich ist. Dabei dürfen jedoch keine Daten verloren gehen.

Normalisiert wird vor allem in der Phase des Entwurfs einer [[Relationale Datenbank|relationalen Datenbank]]. Ein exakter Modellentwurf, wie das [[Entity-Relationship-Modell]] (ERM), macht eine Normalisierung eigentlich überflüssig, kann aber eingesetzt werden, um Anomalien zu beseitigen oder Redundanzen nachträglich zu minimieren.

== Beispiel der Normalisierungsschritte ==
Folgendes Schema wird exemplarisch aus einem denormalisierten Zustand in die 3. Normalform überführt.

=== Ausgangssituation (Nicht normalisiert) ===
In diesem Zustand gibt es Attribute mit mehreren Werten (Wiederholungsgruppen bei Termindatum) und nicht atomare Werte (Vor- und Nachname in einem Feld).
{| class="wikitable"
! Kundenname !! Mitarbeitername !! Salon !! Termindatum
|-
| Klaus Meyer || Sabine Krause || Hammer Haare || 11.10.2012, 14.10.2012
|-
| Paula Meyer || Claudia Schrotter || Friedrich List Frisuren || 09.11.2012
|}

---

== Die 1. Normalform (1NF) ==
Die 1. Normalform (kurz '''1NF''') ist erfüllt, wenn jedes Attribut einer Relation einen '''atomaren Wertebereich''' aufweist. Eine Relation befindet sich in der ersten Normalform, wenn alle Attribute nur einfache Attributwerte aufweisen. (Beispiel: Die Adresse darf nicht als ein Attribut verwendet werden, sondern muss in PLZ, Ort, Straße und Hausnummer aufgeteilt werden). Zudem darf es keine Wiederholungsgruppen geben.

Zur Bildung der ersten Normalform müssen die nicht atomaren Attribute umgewandelt werden. Dies kann durch Einfügen zusätzlicher Zeilen, Spalten oder neuer Relationen erfolgen.

'''Umsetzung:''' Um die 1NF zu erfüllen, müssen für Werte der Spalte ''Termindatum'' zusätzliche Zeilen eingefügt werden und die Inhalte der Spalten ''Mitarbeitername'' und ''Kundennamen'' müssen in jeweils zwei Spalten (MVorname und MNachname bzw. KVorname und KNachname) ausgelagert werden.

{| class="wikitable"
! KVorname !! KNachname !! MVorname !! MNachname !! Salon !! Termindatum
|-
| Klaus || Meyer || Sabine || Krause || Hammer Haare || 11.10.2012
|-
| Klaus || Meyer || Sabine || Krause || Hammer Haare || 14.10.2012
|-
| Paula || Meyer || Claudia || Schrotter || Friedrich List Frisuren || 09.11.2012
|}
''Nun befindet sich die Tabelle in der 1NF!''

---

== Die 2. Normalform (2NF) ==
Ein Relationenschema ist in der 2. Normalform (kurz '''2NF'''), wenn es in der 1. Normalform ist und jedes Nicht-Schlüsselattribut von einem [[Primärschlüssel]] '''vollständig funktional abhängig''' ist.

Zunächst muss also ein Primärschlüssel definiert werden. In diesem Beispiel lässt sich aber keine Attributkombination finden, für die sich immer jeder Datensatz identifizieren lässt. Denn es ist denkbar, dass ein Kunde beim gleichen Mitarbeiter am gleichen Datum zwei Friseurtermine wahrnimmt.

'''Umsetzung:''' Wird ein künstlicher Primärschlüssel für die Relation definiert, ist die Anforderung automatisch erfüllt. Man erweitert die Tabelle um eine Spalte `IdTermin`. Der künstliche Primärschlüssel generiert einen Autowert, anhand dessen sich jede Spalte eindeutig identifizieren lässt.

{| class="wikitable"
! IdTermin !! KVorname !! KNachname !! MVorname !! MNachname !! Salon !! Termindatum
|-
| 1 || Klaus || Meyer || Sabine || Krause || Hammer Haare || 11.10.2012
|-
| 2 || Klaus || Meyer || Sabine || Krause || Hammer Haare || 14.10.2012
|-
| 3 || Paula || Meyer || Claudia || Schrotter || Friedrich List Frisuren || 09.11.2012
|}
''Die Relation erfüllt nun die Anforderungen der 2NF. Sie befindet sich in der 1NF und es gibt kein Attribut in der Tabelle, das sich nicht eindeutig und voll funktional durch den Primärschlüssel IdTermin bestimmen lässt.''

---

== Die 3. Normalform (3NF) ==
Ein Relationenschema befindet sich in der 3. Normalform (kurz '''3NF'''), wenn es in der 2NF ist und kein Attribut, das nicht zum Primärschlüssel gehört, von diesem '''transitiv abhängt'''.

Betrachten wir die Relation aus der 2NF: Mit Hilfe des Primärschlüssels `IdTermin` lässt sich eindeutig der Vorname eines Mitarbeiters, eines Kunden oder eines Salons bestimmen. Allerdings hängt der Salonname von der Salonnummer (SNR) ab und nur ''transitiv'' von `IdTermin`. Gleiches gilt für Kunden (KNR -> KVorname, KNachname) und Mitarbeiter (MNR -> MVorname, MNachname).

'''Umsetzung:''' Um das Schema in die 3NF zu überführen, müssen Kunden-, Mitarbeiter- und Saloninformationen in eine eigene Relation ausgelagert werden.

'''Tabelle: Salon'''
{| class="wikitable"
! SNR !! Salonname
|-
| 1 || Hammer Haare
|-
| 2 || Friedrich List Frisuren
|}

'''Tabelle: Mitarbeiter'''
{| class="wikitable"
! MNR !! MVorname !! MNachname !! FK_SNR
|-
| 1 || Sabine || Krause || 1
|-
| 2 || Claudia || Schrotter || 2
|}

'''Tabelle: Kunde'''
{| class="wikitable"
! KNR !! KVorname !! KNachname
|-
| 1 || Klaus || Meyer
|-
| 2 || Paula || Meyer
|}

'''Tabelle: Termin'''
{| class="wikitable"
! IdTermin !! FK_KNR !! FK_MNR !! Termindatum
|-
| 1 || 1 || 1 || 11.10.2012
|-
| 2 || 1 || 1 || 14.10.2012
|-
| 3 || 2 || 2 || 09.11.2012
|}

''Das Schema befindet sich nun in der 3NF. Es herrschen nur direkte vollfunktionale Abhängigkeiten. Durch [[Fremdschlüssel|Fremdschlüsselbeziehungen]] bleibt der Bezug der Daten untereinander erhalten. Das Ziel der redundanzfreien Datenhaltung ist erreicht.''

[[Kategorie:Datenbanken]]
[[Kategorie:AHR_I_Informatik LK]]
[[Kategorie:FI_I_SDM]]

Datenbanktabelle

Flbkwikiadmin — Thu, 16 Apr 2026 12:15:22 GMT

Die Seite wurde neu angelegt: „'''Datenbanktabellen''' sind die Grundlage von Datenbanken. In einer Datenbanktabelle wird eine Menge von Daten, die in Zeilen und Spalten einer Tabelle strukturiert sind, dauerhaft gespeichert. Dabei legen die Spalten fest, was in der Tabelle gespeichert wird. In den Zeilen liegen die einzelnen Datensätze vor. == Bezug zum relationalen Modell == Tabellen sind eine Form von Relationen, welche die Name…“

Neue Seite

'''Datenbanktabellen''' sind die Grundlage von [[Relationale Datenbank|Datenbanken]]. In einer Datenbanktabelle wird eine Menge von Daten, die in Zeilen und Spalten einer Tabelle strukturiert sind, dauerhaft gespeichert. Dabei legen die Spalten fest, was in der Tabelle gespeichert wird. In den Zeilen liegen die einzelnen Datensätze vor.

== Bezug zum relationalen Modell ==
Tabellen sind eine Form von [[Relation (Datenbanken)|Relationen]], welche die Namensgeber der relationalen Datenbanken sind.
* Die '''Zeilen''' einer Tabelle werden hierbei als Tupel bezeichnet und entsprechen einem Datensatz.
* Die '''Spalten''' werden Attribute genannt.

== Schema und Schlüssel ==
Die Struktur der Daten muss einem festen Schema folgen. Dieses Schema legt fest, welche Daten in der Tabelle gespeichert werden können.

In dem Schema kann auch ein sogenannter [[Primärschlüssel]] definiert werden. Ein Primärschlüssel ist eine eindeutige Bezeichnung eines Datensatzes. Neben dem Primärschlüssel können [[Fremdschlüssel]] enthalten sein, die auf den Primärschlüssel einer anderen Tabelle verweisen, um Beziehungen zwischen den Tabellen herzustellen.

== Erstellung (DDL) ==
Die Tabelle selbst und das zugrunde liegende Relationenschema werden mit Hilfe der [[Data Definition Language]] (DDL) der [[SQL|Structured Query Language (SQL)]] erzeugt.

---

== Beispiele ==

=== Beispiel Datenbanktabelle ===
Zur Veranschaulichung hier die fiktive Tabelle `Mitarbeiter`, die dem unten stehenden Schema folgt:

{| class="wikitable"
|+ Tabelle: Mitarbeiter
! idMitarbeiter !! Vorname !! Nachname !! FKSalon
|-
| 1 || Sabine || Krause || 1
|-
| 2 || Claudia || Schrotter || 1
|-
| 3 || Markus || Hermann || 1
|}

=== Beispiel Relationenmodell ===
Die textuelle Kurzschreibweise für das zugrunde liegende Schema im Relationenmodell lautet:

<code>Mitarbeiter: '''idMitarbeiter''', Vorname, Nachname, ↑FKSalon</code>

=== Beispiel Schema in SQL ===
Die logische Definition der Attribute und Schlüsselbedingungen sieht in SQL wie folgt aus:

<syntaxhighlight lang="sql">
idMitarbeiter INT NOT NULL,
Vorname VARCHAR(45),
Nachname VARCHAR(45),
FKSalon INT,
FOREIGN KEY (FKSalon) REFERENCES Salon(IdSalon),
PRIMARY KEY (idMitarbeiter)
</syntaxhighlight>

=== Beispiel Erzeugung eines Schemas in DDL ===
Der vollständige `CREATE TABLE`-Befehl, um diese Struktur physisch in der Datenbank anzulegen:

<syntaxhighlight lang="sql">
CREATE TABLE mydb.Mitarbeiter (
idMitarbeiter INT NOT NULL,
Vorname VARCHAR(45) NULL,
Nachname VARCHAR(45) NULL,
FKSalon INT NOT NULL,
PRIMARY KEY (idMitarbeiter),
FOREIGN KEY (FKSalon) REFERENCES Salon(IdSalon)
);
</syntaxhighlight>

[[Kategorie:Datenbanken]]
[[Kategorie:AHR_I_Informatik LK]]
[[Kategorie:FI_I_SDM]]

Speicher

Flbkwikiadmin — Thu, 16 Apr 2026 12:08:31 GMT

← Nächstältere Version		Version vom 16. April 2026, 14:08 Uhr
Zeile 2:		Zeile 2:

	[[Kategorie:Informatik]]		[[Kategorie:Informatik]]
			[[Kategorie:FI_I_SDM]]
			[[Kategorie:AHR_I_Informatik_LK]]

← Nächstältere Version		Version vom 5. Mai 2026, 09:28 Uhr
Zeile 158:		Zeile 158:
	=== Best-Case (Bester Fall) ===		=== Best-Case (Bester Fall) ===
	[[Datei:Verzweigungsbaum Quicksort symetrisch.png\|mini\|Best-Case: Symmetrischer Baum]]		[[Datei:Verzweigungsbaum Quicksort symetrisch.png\|mini\|Best-Case: Symmetrischer Baum]]
	Der beste Fall liegt vor, wenn das Pivot-Element die Liste ~~immer~~ exakt in der Mitte teilt. Die Teillisten sind dann immer gleich groß.		Der beste Fall liegt vor, wenn das Pivot-Element die Liste in jedem Rekursionsschritt exakt in der Mitte teilt. Die entstehenden Teillisten sind dann immer gleich groß.
	[[Datei:SubArrays symetrisch Quicksort.png\|mini\|Halbierung der Arraygrößen]]		[[Datei:SubArrays symetrisch Quicksort.png\|mini\|Halbierung der Arraygrößen]]

	Wird die Anzahl der zu sortierenden Elemente <math>n</math> verdoppelt, kommt durch die fortlaufende Halbierung lediglich '''eine einzige neue Rekursionsebene''' (ein Baum-Level) hinzu. Dieses Wachstumsverhalten (~~wie~~ oft kann ich <math>n</math> durch 2 teilen, bis 1 übrig bleibt?) wird mathematisch durch den Logarithmus zur Basis 2 ausgedrückt: <math>\log_2(n)</math>.		Wird die Anzahl der zu sortierenden Elemente <math>n</math> verdoppelt, kommt durch die fortlaufende Halbierung lediglich '''eine einzige neue Rekursionsebene''' (ein Baum-Level) hinzu. Dieses Wachstumsverhalten (Wie oft kann ich <math>n</math> durch 2 teilen, bis 1 übrig bleibt?) wird mathematisch durch den Logarithmus zur Basis 2 ausgedrückt: <math>\log_2(n)</math>.

	{\| class="wikitable" style="text-align:center"		{\| class="wikitable" style="text-align:center"
Zeile 184:		Zeile 184:
	\|}		\|}

	Wir haben also insgesamt <math>\log_2(n)</math> Ebenen. Auf '''jeder einzelnen Ebene''' müssen in der Summe <math>n</math> Elemente betrachtet und mit ~~dem~~ jeweiligen ~~Pivot~~ verglichen werden.		Wir haben also insgesamt <math>\log_2(n)</math> Ebenen. Nun müssen wir noch den Aufwand pro Ebene bestimmen: Obwohl die einzelnen Teillisten nach unten hin immer kürzer werden, verdoppelt sich gleichzeitig ihre Anzahl. Auf '''jeder einzelnen Ebene''' müssen daher in der Summe über alle Teillisten hinweg wieder (nahezu) <math>n</math> Elemente betrachtet und mit den jeweiligen Pivots verglichen werden.
	Wir multiplizieren also die Arbeit pro Ebene (<math>n</math>) mit der Anzahl der Ebenen (<math>\log_2(n)</math>).
			Wir multiplizieren also die Arbeit pro Ebene (<math>n</math> Vergleiche) mit der Anzahl der Ebenen (<math>\log_2(n)</math>).
	'''Fazit Best-Case:''' Die Laufzeit beträgt <math>\mathcal{O}(n \log n)</math>.		'''Fazit Best-Case:''' Die Laufzeit beträgt <math>\mathcal{O}(n \log n)</math>.

	=== Average-Case (Durchschnittlicher Fall) ===		=== Average-Case (Durchschnittlicher Fall) ===
	In der Praxis haben wir ~~selten~~ den perfekten Best-Case, aber ~~fast nie~~ den absoluten Worst-Case. Meistens teilt das Pivot die Liste in ungleiche, aber moderate Verhältnisse (z. B. 30:70 oder 60:40).		In der Praxis haben wir fast nie den perfekten Best-Case, aber zum Glück auch extrem selten den absoluten Worst-Case. Meistens teilt das Pivot die Liste in ungleiche, aber moderate Verhältnisse (z. B. 30:70 oder 60:40). Auch bei solchen ungleichen Teilungen wächst die Tiefe des Baumes weiterhin nur logarithmisch.

	Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf unser Vorwissen ~~(Indikatorvariablen und Harmonische~~ Reihe) zurück. Wir fragen uns: ''Wie hoch ist die Wahrscheinlichkeit, dass zwei beliebige Elemente (nennen wir sie <math>z_i</math> und <math>z_j</math>, wobei <math>z_i < z_j</math>) im Laufe des Algorithmus direkt miteinander verglichen werden?''		Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf Stochastik und unser Vorwissen zur Harmonischen Reihe zurück. Wir fragen uns: ''Wie hoch ist die Wahrscheinlichkeit, dass zwei beliebige Elemente (nennen wir sie <math>z_i</math> und <math>z_j</math>, wobei <math>z_i < z_j</math>) im Laufe des gesamten Algorithmus direkt miteinander verglichen werden?''

	* Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, '''bevor''' irgendein anderes Element, dessen Wert zwischen <math>z_i</math> und <math>z_j</math> liegt, als Pivot gewählt wird.		* Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, '''bevor''' irgendein anderes Element, dessen Wert zwischen <math>z_i</math> und <math>z_j</math> liegt, als Pivot gewählt wird.
	* Zwischen <math>z_i</math> und <math>z_j</math> (inklusive der beiden Randelemente) liegen exakt <math>k = j - i + 1</math> Elemente.		* Zwischen <math>z_i</math> und <math>z_j</math> (inklusive der beiden Randelemente) liegen exakt <math>k = j - i + 1</math> Elemente.
	* ~~Sind die Daten völlig zufällig verteilt~~, hat jedes dieser <math>k</math> Elemente die gleiche Chance, zuerst als Pivot ~~gewählt~~ zu werden. Damit <math>z_i</math> und <math>z_j</math> verglichen werden, muss exakt <math>z_i</math> oder <math>z_j</math> der "Gewinner" dieser Ziehung sein. Da es <math>2</math> günstige Fälle ~~(<math>z_i</math> oder <math>z_j</math>)~~ bei <math>k</math> möglichen Fällen gibt, beträgt die Wahrscheinlichkeit exakt <math>\frac{2}{k}</math>.		* Gehen wir von einer zufälligen Pivot-Wahl aus, hat jedes dieser <math>k</math> Elemente die gleiche Chance, zuerst als Pivot gezogen zu werden. Damit <math>z_i</math> und <math>z_j</math> verglichen werden, muss exakt <math>z_i</math> oder <math>z_j</math> der "Gewinner" dieser Ziehung sein. Da es <math>2</math> günstige Fälle bei <math>k</math> möglichen Fällen gibt, beträgt die Wahrscheinlichkeit exakt <math>\frac{2}{k}</math>.

	Summieren wir diese Wahrscheinlichkeiten (den Erwartungswert) für alle möglichen Elementpaare im gesamten Array auf, erhalten wir folgende Doppel-Summe:		Summieren wir diese Wahrscheinlichkeiten (den sogenannten Erwartungswert) für alle möglichen Elementpaare im gesamten Array auf, erhalten wir folgende Doppel-Summe:
	<math>E(X) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j - i + 1}</math>		<math>E(X) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j - i + 1}</math>

Zeile 203:		Zeile 204:
	<math>\sum_{k=2}^{n} \frac{2}{k} = 2 \cdot \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)</math>		<math>\sum_{k=2}^{n} \frac{2}{k} = 2 \cdot \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)</math>

	~~Hier~~ erkennen wir exakt die '''Harmonische Reihe''' ~~(<math>H_n</math>)~~ wieder! Da die Harmonische Reihe für große <math>n</math> gegen den natürlichen Logarithmus <math>\ln(n)</math> konvergiert~~, ergibt die~~ innere Summe ungefähr <math>2 \cdot \ln(n)</math>. Da die äußere Summe (~~stark vereinfacht~~) <math>n</math>-mal ~~läuft~~, erhalten ~~wir~~ insgesamt rund <math>2n \cdot \ln(n)</math> Vergleiche.		In der Klammer erkennen wir exakt die '''Harmonische Reihe''' wieder! Aus der Mathematik wissen wir, dass die Harmonische Reihe für große <math>n</math> gegen den natürlichen Logarithmus <math>\ln(n)</math> konvergiert. Die innere Summe ergibt also maximal ungefähr <math>2 \cdot \ln(n)</math>. Da die äußere Summe (die Variable <math>i</math>) insgesamt <math>n</math>-mal durchlaufen wird, multiplizieren wir diesen Wert mit <math>n</math> und erhalten insgesamt rund <math>2n \cdot \ln(n)</math> zu erwartende Vergleiche.

	Da konstante Vorfaktoren wie die <math>2</math> ~~beim Groß-O~~ ignoriert werden, ist ~~nun stochastisch bewiesen~~:		Da konstante Vorfaktoren (wie die <math>2</math>) und die Basis des Logarithmus in der asymptotischen Notation ignoriert werden, ist der Beweis erbracht:
	'''Fazit Average-Case:''' Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums ~~der harmonischen Reihe~~ sicher gegen die Komplexitätsklasse <math>\mathcal{O}(n \log n)</math>.		'''Fazit Average-Case:''' Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums sicher gegen die Komplexitätsklasse <math>\mathcal{O}(n \log n)</math>.

	=== Worst-Case (Schlechtester Fall) ===		=== Worst-Case (Schlechtester Fall) ===
	[[Datei:Baum N-Ebenen.png\|mini\|Worst-Case: Entarteter Baum]]		[[Datei:Baum N-Ebenen.png\|mini\|Worst-Case: Entarteter Baum]]
	~~Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]].~~ Angenommen, wir haben extremes Pech und die Partitionierung ist maximal unausgeglichen. Das gewählte Pivot ist immer das absolut kleinste oder größte Element. Dann enthält eine der Partitionen 0 Elemente und die andere Partition <math>n-1</math> Elemente.		Angenommen, wir haben extremes Pech und die Partitionierung ist maximal unausgeglichen. Das gewählte Pivot ist immer das absolut kleinste oder größte Element der aktuellen Teilliste. Dann enthält eine der Partitionen 0 Elemente und die andere Partition <math>n-1</math> Elemente. Der Baum "entartet" zu einer linearen Kette.
			''Hinweis für die Praxis: Wird bei einer naiven Implementierung immer stur das letzte Element als Pivot gewählt, tritt dieser Worst-Case ironischerweise genau dann auf, wenn die Liste bereits aufsteigend oder absteigend sortiert ist!''

	Der Aufwand für das Vergleichen (Partitionieren) ~~einer~~ Ebene mit <math>n</math> Elementen ist proportional zu <math>n</math>. Nennen wir diesen Aufwand <math>c \cdot n</math> (wobei <math>c</math> eine Konstante für die Dauer eines Vergleichs ist).		Der Aufwand für das Vergleichen (Partitionieren) auf der ersten Ebene mit <math>n</math> Elementen ist proportional zu <math>n</math>. Nennen wir diesen Aufwand <math>c \cdot n</math> (wobei <math>c</math> eine Konstante für die Dauer eines einzelnen Vergleichs ist).
	Auf der nächsten Ebene müssen wir <math>n-1</math> Elemente vergleichen, der Aufwand ist <math>c \cdot (n-1)</math>. Danach <math>c \cdot (n-2)</math> und so weiter.		Auf der nächsten Ebene müssen wir <math>n-1</math> Elemente vergleichen, der Aufwand ist also <math>c \cdot (n-1)</math>. Danach <math>c \cdot (n-2)</math> und so weiter.

	Wenn wir die Partitionierungszeiten für alle Ebenen aufsummieren, erhalten wir folgende Reihe:		Wenn wir die Partitionierungszeiten für alle Ebenen aufsummieren, erhalten wir folgende Reihe:
Zeile 221:		Zeile 223:
	<math>c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n</math>		<math>c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n</math>

	Da in der asymptotischen Laufzeitanalyse konstante Faktoren und ~~kleinere~~ Terme (wie <math>n</math>) ignoriert werden, ~~wächst~~ der ~~Aufwand quadratisch~~.		Da in der asymptotischen Laufzeitanalyse konstante Faktoren (<math>\frac{c}{2}</math>) und niederwertige Terme (wie <math>n</math>) ignoriert werden, bestimmt allein der quadratische Term das Wachstumsverhalten.
	'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.		'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.