Min-Max-Notation

Die Min-Max-Notation (auch (min,max)-Notation) ist eine Art, die Kardinalität einer Beziehung zwischen Entitätstypen in einem Entity-Relationship-Modell einzuschränken. Sie wurde eingeführt, weil die Chen-Notation nur beschränkte Aussagen zu einer Beziehung erlaubt. Mit der (min,max)-Notation können sowohl untere als auch obere Schranken präzise ausgedrückt werden.

Bei der (min,max)-Notation wird für jeden an einer Beziehung beteiligten Entitätstyp ein geordnetes Paar mit einem Minimal- und einem Maximalwert angegeben. Diese Werte geben an, an wie vielen Beziehungsausprägungen die Entitätausprägungen mindestens teilnehmen müssen und an wie vielen sie höchstens teilnehmen dürfen.

Die (min,max)-Notation wurde 1974 durch Jean-Raymond Abrial^[1] im Rahmen eines semantischen Modells eingeführt, das mit dem von Chen konkurrierte. Mittlerweile hat die Chen-Notation die (min,max)-Notation jedoch assimiliert, und man kann sie konzeptionell losgelöst von der Abrial-Notation als Ergänzung zu Chen verwenden.

Definition

Für eine Beziehung zwischen zwei Entitätstypen X und Y hat der Entitätstyp X die Kardinalität (a,b), wenn jede Entität aus der Entitätsmenge X zu mindestens a und höchstens b verschiedenen Entitäten aus der Entitätsmenge Y in Beziehung stehen darf, wobei $a,b \in \mathbb{N} \cup \{N\}$.

Dabei ist „N“ ein Symbol für die von der Ausprägung abhängige maximale Anzahl an möglichen Relationspartnern, das heißt, für eine konkrete Ausprägung des Schemas wird „N“ interpretiert als die Anzahl der Entitäten vom Typ Y in der Ausprägung. „N“ als Max-Wert ist also gleichbedeutend mit einer Unbeschränktheit nach oben, da | Y | theoretisch beliebig groß werden darf. Eine Entität mit Max-Kardinalität „N“ darf also mit beliebig vielen Entitäten in Relation stehen. Deshalb wird in Anlehnung an UML-Syntax häufig auch ein Stern („ * “) anstelle des Symbols „N“ geschrieben, wobei in der Originalnotation von Abrial ausschließlich das „N“ hierfür Verwendung fand.

Allgemeiner gilt, dass in einer n-ären Beziehung zwischen dem Entitätstyp X₁ und n − 1 weiteren Entitätstypen $X_2, \dots, X_n$ dem Entitätstyp X₁ das Min-Max-Paar (a,b) zugeordnet wird, falls jede Entität aus der Entitätsmenge X₁ mit mindestens a und höchstens b n − 1-Tupeln aus $X_2 \times \dots \times X_n$ in Beziehung steht, d.h. falls es für jedes $x_1 \in X_1$ in jeder Ausprägung der betreffenden Relation zwischen a und b Tupel der Form $(x_1, \dots)$ gibt.

Allgemein gehaltene, formale Definition

In der Sprache der relationalen Algebra bedeutet das: Sei $n\in\mathbb{N}$ und $n\geq 2$, dann hat in einer Relation $R\subseteq X_1\times \dots \times X_n$ der Entitätstyp X_i die Kardinalität (a,b), falls für alle $x\in X_i$ die Mächtigkeit der Menge $M:=\{(x_1,\dots ,x_{i-1},x,x_{i+1},\dots ,x_n)\in R\}$ durch a nach unten und durch b nach oben beschränkt ist, also

$a\leq |M| \leq b$

gilt. Unbeschränktheit nach oben wird dabei wieder durch b: = N beziehungsweise b: = * angezeigt.

Erst bei der allgemeinen Definition für n-äre Relationen tritt der wesentliche Charakter der Min-Max-Notation, Schranken für Ausprägungen der Relation anzugeben, deutlich zu Tage.

Vergleich mit anderen Notationen

Unterschied zu Multiplizitätsangaben in UML

Bei der min…max-Notation aus der UML, die die sogenannte Multiplizität einer Assoziation festlegt, wird für jede an einer Assoziation beteiligten Klasse zwar ebenfalls ein geordnetes Paar mit einem Minimal- und einem Maximalwert angegeben. In UML jedoch besagen diese Werte für einen Entitätstyp X, wie viele Entitäten vom Typ X es für eine gegebene Kombination der übrigen Entitäten geben kann.

Die Mulitiplizitätsangabe aus UML ist in ihrer Semantik vergleichbar zur Chen- und MC-Notation. Alle drei stehen im fundamentalen Gegensatz zur (min,max)-Notation: Die (min,max)-Notation zählt die Ausprägung von Beziehungen, während die anderen Notationen Entitätstypausprägungen zählen.

In binären Beziehungen

Wenn wir beispielsweise ausdrücken wollten, wie die Beziehung der Zugehörigkeit zwischen den Entitätstypen Fußballmannschaft und Spieler geartet ist, so wäre in UML die Multiplizität der Spieler-Entität 11..11 (da es für jede Mannschaft genau 11 Spieler geben soll, die zu ihr gehören) und die der Mannschafts-Entität 1..1 (da jeder Spieler zu genau einer Mannschaft gehören soll), während die Min-Max-Notation (siehe Abbildung) für die Spieler-Entität (1,1) angibt und für die Mannschafts-Entität (11,11) (da jeder Spieler in der Ausprägung unserer gehörtZu-Relation genau einmal vorkommen soll und jede Mannschaft genau 11 mal). Für binäre Relationen sind die Angaben wegen der unterschiedlichen Sichtweisen also genau vertauscht.

In mehrwertigen Beziehungen

Für Relationen mit mehr als zwei beteiligten Entitätstypen gibt es jedoch keinen unmittelbaren Bezug mehr zwischen den bei UML und Min-Max auftretenden Zahlen. Betrachten wir beispielsweise eine ternäre Relation, die Studenten, von diesen besuchte Kurse und dabei erhaltene Noten in Beziehung setzt. Wir erhalten in UML für Student 0..* (da es für jede Kombination aus Kurs und Note beliebig viele Studenten geben kann, die die Note im jeweiligen Kurs erhalten), für Kurs 0..* (da es für jede Kombination aus Student und Note beliebig viele Kurse geben kann, in denen das entsprechende Ergebnis erzielt wurde) und für Note 0..1 (da jeder Student für jeden Kurs maximal eine Note erhält). Mit der Min-Max-Notation erhalten wir beispielsweise für Student (0,N) (da jeder Student an beliebig vielen benoteten Kursen teilgenommen haben kann), für Kurs (1,N) (da es für jeden Kurs mindestens einen Teilnehmer mit Note geben muss; wenn wir nur abgeschlossene Kurse in die Datenbank aufnehmen) und für Note (0,N) (da es jede Note beliebig oft geben kann).

Auch wenn es einen Bezug für binäre Relationen gibt, so sind die beiden Notation doch grundsätzlich verschieden!

Ausdrucksstärke der Min-Max-Notation

Die Ausdrucksstärke der Min-Max-Notation ist nicht mit der Chen-Notation (bzw. Multiplizitätsangaben in UML) vergleichbar, d.h. keine Notation subsumiert die jeweils andere. Es gibt für beide Notationen Konsistenzbedingungen, die sich in der jeweils anderen Notation nicht ausdrücken lassen.

Dies geht bereits aus dem obigen Beispiel hervor: In der Chen-Notation handelt es sich bei der Studenten-Kurse-Noten-Beziehung um eine n:m:1-Relation. Es wird also insbesondere ausgedrückt, dass es für jedes Student-Kurs-Paar maximal eine Note geben darf. Die Min-Max-Notation ist nicht imstande dies auszudrücken. Umgekehrt drückt die Min-Max-Notation jedoch durch (1,N) an der Kurs-Entität aus, dass es keine Kurse gibt, an denen nicht mindestens ein Student mit Note teilnimmt, was wiederum durch die Chen-Notation nicht ausdrückbar ist.

Man beachte: Beschränkt man sich auf binäre Beziehungen, so ist die Min-Max-Notation ausdrucksstärker.

Gegenüberstellung verschiedener Notationen

Chen-Notation, MC-Notation, Multiplizitätsangaben der UML und (min,max)-Notation im Vergleich:

Beispiel: Zwei Entitätstypen, bei denen es zu jeder Entität x aus der ersten Entitätsmenge beliebig viele Elemente aus der zweiten Entitätsmenge geben kann, die zu x in Relation stehen. Weiter muss jedes Element y der zweiten Entitätsmenge zu genau einem Element der ersten Entitätsmenge in Relation stehen (d.h. für den zweiten Entitätstyp wird die vollständige Teilnahme/total participation an der Relation gefordert).

Chen-Notation: Entität 1 ←— 1:n —→ Entität 2 + "vollständige Teilnahme" der Entität 2 an der Beziehung

Anmerkung: die Entität 2 ist also per Doppelstrich mit der Beziehung verbunden, der Doppelstrich sei als die "Chen-Seite" hinsichtlich der vollständigen Teilnahme dieses Beispiels bezeichnet

MC-Notation: Entität 1 ←— 1:mc —→ Entität 2

Man beachte: die vollständige Teilnahme ist in Form von 1 auf Seite der Entität 1 repräsentiert, also der Chen-Gegenseite

Multiplizität: Klasse 1 ← 1..1 ——— 0..* → Klasse 2

Man beachte: die vollständige Teilnahme in Form der "min=1"-Beschränkung ist auf der Seite der Klasse 1; also vergleichbar mit der MC-Notation, ebenfalls auf der Chen-Gegenseite

(min,max)-Notation: Entität 1 ← (0,N) ——— (1,1) → Entität 2

Man beachte: die vollständige Teilnahme (in Form der "min=1"-Einschränkung) ist hier auf der Seite der Entität 2, also auf der Chen-Seite "wo man sie erwartet" (im Gegensatz zur max-Einschränkung...)

In diesem Beispiel zur vollständigen Teilnahme tritt, selbst schon bei binären Beziehungen, die fundamental andere Sichtweise von (min,max)-Notation auf der einen Seite und MC-Notation/Multiplizitäten auf der anderen zum Vorschein.

Gegenüberstellung von (min,max)-Notation, Chen-Notation, MC-Notation und Multiplizitäten:

(min,max) [Entity 1]	Multiplizität [UML, Entity 1]	Chen-Notation	MC-Notation	Multiplizität [UML, Entity 2]	(min,max) [Entity 2]
(0,1)	0..1	1:1	c:c	0..1	(0,1)
(0,N)	0..1	1:n	c:mc	0..*	(0,1)
(0,N)	1..1	1:N + total participation	1:mc	0..*	(1,1)
(0,N)	0..*	m:n	mc:mc	0..*	(0,N)
(1,1)	0..1	total participation + 1:1	c:1	1..1	(0,1)
(1,N)	0..1	total participation + 1:N	c:m	1..*	(0,1)
(1,1)	1..1	total part. + 1:1 + total part.	1:1	1..1	(1,1)
(1,N)	1..1	total part. + 1:N + total part.	1:m	1..*	(1,1)
(1,N)	0..*	total participation + M:N	mc:m	1..*	(0,N)
(1,N)	1..*	total part. + M:N + total part.	m:m	1..*	(1,N)

Die (min,max)-Notation gilt als kontra-intuitiv zu Chen bezüglich der (Max-)Kardinalität, weil die (min,max)-Notation Relationships zählt. Chen, MC und Multiplizitäten zählen Entities!

Anmerkung zur Min-Seite: bei der (min,max)-Notation ist das Kriterium zur "vollständigen Teilnahme" (also 0 oder 1 bezogen auf Min) korrekterweise auf der Chen-Seite, im Gegensatz zur kontra-intuitiven (Max-)Kardinalität. Diejenige Seite in der die "vollständige Teilnahme" bei der Multiplizitätsangabe und bei der MC-Notation zum tragen kommt ist bezüglich Chen jedoch kontra-intuitiv, im Gegensatz zur intuitiven (Max-)Kardinalität.

Einzelnachweise

1. ↑ Jean-Raymond Abrial: Data Semantics. In: IFIP Working Conference Data Base Management 1974. 1974, S. 1–60.

Literatur

• Alfons Kemper, André Eickler: Datenbanksysteme. Eine Einführung. 6. Auflage. Oldenbourg, München 2006, ISBN 3-486-57690-9.
• Ramez Elmasri, Shamkant B. Navathe: Fundamentals of Database Systems. Addison Wesley, Reading 2000, ISBN 0-8053-1755-4.