Min-max notation

The min-max notation (also (min, max) notation ) is a way of restricting the cardinality of a relationship between entity types in an entity relationship model . It was introduced because the Chen notation allows only limited statements about a relationship. With the (min, max) notation, both lower and upper bounds can be expressed precisely.

In the (min, max) notation, an ordered pair with a minimum and a maximum value is specified for each entity type involved in a relationship . These values indicate how many relationship expressions the entity characteristics must participate in and how many they are allowed to participate in.

The (min, max) notation was introduced by Jean-Raymond Abrial in 1974 as part of a semantic model that rivaled Chen's. In the meantime, however, the Chen notation has assimilated the (min, max) notation, and it can be used conceptually separately from the Abrial notation as a supplement to Chen.

definition

For a relationship between two entity types and , the entity type has cardinality if each entity from the entity set may be related to at least and at most different entities from the entity set , where . ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle X}$ ${\ displaystyle (a, b)}$ ${\ displaystyle X}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle Y}$ ${\ displaystyle a, b \ in \ mathbb {N} \ cup \ {N \}}$

" " Is a symbol for the maximum number of possible relationship partners, which is dependent on the characteristic, that is, for a specific characteristic of the schema, " " is interpreted as the number of entities of the type in the characteristic. " " As the maximum value is therefore synonymous with an unlimited upwards, since theoretically it can be of any size. An entity with max cardinality " " can therefore be related to any number of entities. Therefore, based on UML syntax, an asterisk (" ") is often written instead of the symbol " ", whereby in the original Abrial notation only the " " was used for this. ${\ displaystyle N}$ ${\ displaystyle N}$ ${\ displaystyle Y}$ ${\ displaystyle N}$ ${\ displaystyle | Y |}$ ${\ displaystyle N}$ ${\ displaystyle *}$ ${\ displaystyle N}$ ${\ displaystyle N}$

More generally, in a -ary relationship between the entity type and other entity types, the entity type is assigned the min-max pair if each entity from the entity set is related to at least and at most tuples from , i. H. if for each in each occurrence of the relevant relation between and there are tuples of the form . ${\ displaystyle n}$ ${\ displaystyle X_ {1}}$ ${\ displaystyle n-1}$ ${\ displaystyle X_ {2}, \ dots, X_ {n}}$ ${\ displaystyle X_ {1}}$ ${\ displaystyle (a, b)}$ ${\ displaystyle X_ {1}}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle n-1}$ ${\ displaystyle X_ {2} \ times \ dots \ times X_ {n}}$ ${\ displaystyle x_ {1} \ in X_ {1}}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle (x_ {1}, \ dots)}$

General, formal definition

In the language of relational algebra, this means: If and , then the entity type in a relation has cardinality if the power of the set is bounded by downward and by upward for all , i.e. ${\ displaystyle n \ in \ mathbb {N}}$ ${\ displaystyle n \ geq 2}$ ${\ displaystyle R \ subseteq X_ {1} \ times \ dots \ times X_ {n}}$ ${\ displaystyle X_ {i}}$ ${\ displaystyle (a, b)}$ ${\ displaystyle x \ in X_ {i}}$ ${\ displaystyle M: = \ {(x_ {1}, \ dots, x_ {i-1}, x, x_ {i + 1}, \ dots, x_ {n}) \ in R \}}$ ${\ displaystyle a}$ ${\ displaystyle b}$

{\ displaystyle a \ leq | M | \ leq b}

applies. Unrestricted upward is again indicated by or . ${\ displaystyle b: = N}$ ${\ displaystyle b: = *}$

Only with the general definition of -ary relations does the essential character of the min-max notation, which is to indicate boundaries for expressions of the relation, become clear. ${\ displaystyle n}$

Comparison with other notations

Difference to multiplicity specifications in UML

With the min… max notation from the UML, which defines the so-called multiplicity of an association , an ordered pair with a minimum and a maximum value is also specified for each class involved in an association. In UML, however, these values for an entity type X tell how many entities of type X there can be for a given combination of the other entities.

The semantics of the multiplicity specification from UML is comparable to the Chen and MC notation . All three are in fundamental contrast to the (min, max) notation: The (min, max) notation counts the characteristics of relationships, while the other notations count entity type characteristics.

In binary relationships

For example, if we wanted to express how the relationship of membership between the entity types football team and player is, then in UML the multiplicity of the player entity would be 11..11 (since there should be exactly 11 players for each team who belong to it ) and that of the team entity 1..1 (since every player should belong to exactly one team), while the min-max notation (see figure) indicates for the player entity (1,1) and for the team Entity (11,11) (since every player in the form of our belongs-to-relation should appear exactly once and every team exactly 11 times). In the case of binary relations, the information is reversed because of the different perspectives.

In multi-valued relationships

For relations with more than two entity types involved, however, there is no longer any direct relationship between the numbers occurring in UML and Min-Max. For example, consider a ternary relation that relates students, courses they attended, and grades they received. In UML we get 0 .. * for student (since there can be any number of students who receive the grade in the respective course for every combination of course and grade), for course 0 .. * (because there is a 0 .. * for every combination of student and Grade can give any number of courses in which the corresponding result was achieved) and for grade 0..1 (since each student receives a maximum of one grade for each course). With the Min-Max notation, for example, we get (0, N) for student (since each student can have participated in any number of graded courses), for course (1, N) (because there is at least one participant with a grade for each course must; if we only include completed courses in the database) and for grade (0, N) (since each grade can be given any number of times).

Even if there is a reference for binary relations, the two notations are fundamentally different!

Expressiveness of the min-max notation

The expressiveness of the min-max notation is not comparable with the Chen notation (or multiplicity specifications in UML); H. no notation subsumes the other. There are consistency conditions for both notations that cannot be expressed in the other notation.

This is already evident from the example above: In the Chen notation, the student-course-grade relationship is an n: m: 1 relationship. In particular, it is stated that there may be a maximum of one grade for each student-course pair. The min-max notation is not able to express it. Conversely, however, the Min-Max notation uses (1, N) on the course entity to express that there are no courses in which at least one student with a grade does not participate, which in turn cannot be expressed using the Chen notation.

Note: If you limit yourself to binary relationships, the min-max notation is more expressive.

Comparison of different notations

Chen notation, MC notation, multiplicity specifications of the UML and (min, max) notation in comparison:

Example: Two entity types in which for each entity x from the first entity set there can be any number of elements from the second entity set that are related to x. Furthermore, each element y of the second entity set must be related to exactly one element of the first entity set (i.e., for the second entity type, total participation in the relation is required).

Chen notation : Entity 1 ← - 1: n - → Entity 2 + "full participation" of Entity 2 in the relationship

Note: Entity 2 is connected to the relationship with a double line, the double line is referred to as the "Chen side" with regard to the full participation of this example

MC notation : Entity 1 ← - 1: mc - → Entity 2

Note: full participation is represented in the form of 1 on the side of Entity 1, i.e. the Chen counterpart

Multiplicity : class 1 ← 1..1 ——— 0 .. * → class 2

Please note: full participation in the form of the "min = 1" restriction is on the class 1 side; thus comparable to the MC notation, also on the other side of Chen

(min, max) notation : Entity 1 ← (0, N) ——— (1,1) → Entity 2

Please note: the full participation (in the form of the "min = 1" restriction) is here on the entity 2 side, ie on the Chen side "where you expect it" (in contrast to the max restriction ...)

In this example of full participation, even with binary relationships, the fundamentally different view of (min, max) notation on the one hand and MC notation / multiplicities on the other emerges.

Comparison of (min, max) notation, Chen notation, MC notation and multiplicities:

(min, max) [Entity 1]	Multiplicity [UML, Entity 1]	Chen notation	MC notation	Multiplicity [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	cm	1..*	(0.1)
(1.1)	1..1	totally part. + 1: 1 + total part.	1: 1	1..1	(1.1)
(1, N)	1..1	totally 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..*	totally part. + M: N + total part.	m: m	1..*	(1, N)

The (min, max) notation is considered counter-intuitive to Chen with regard to the (max) cardinality, because the (min, max) notation counts Relationships. Chen, MC and multiplicities count entities!

Note on the min side: with the (min, max) notation, the criterion for "complete participation" (ie 0 or 1 related to min) is correctly on the Chen side, in contrast to the counter-intuitive (max) cardinality . However, the side in which the "full participation" in the multiplicity specification and in the MC notation comes into play is counter-intuitive with regard to Chen, in contrast to the intuitive (max) cardinality.

Individual evidence

^ Jean-Raymond Abrial: Data Semantics . In: IFIP Working Conference Data Base Management 1974 . 1974, p. 1-60 .

literature

Alfons Kemper, André Eickler: Database systems. An introduction. 6th edition. Oldenbourg, Munich 2006, ISBN 3-486-57690-9 .
Ramez Elmasri, Shamkant B. Navathe: Fundamentals of Database Systems. Addison-Wesley, Reading 2000, ISBN 0-8053-1755-4 .

[1] Jean-Raymond Abrial: Data Semantics . In: IFIP Working Conference Data Base Management 1974 . 1974, p. 1-60 .