Tupel

Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:

Korrektheit: 4 (großteils überprüft)

Umfang: 2 (wichtige Fakten fehlen)

Quellenangaben: 2 (wichtige Quellen fehlen)

Quellenarten: 3 (gut)

Konformität: 5 (ausgezeichnet)

Anschauliche Definition (nach Kowarschick)

Ein Tupel ist eine Menge von unterschiedlich benannten Elementen, d.h. von Schlüssel/Wert-Paaren, wobei jeder Schlüssel nur einmal vorkommen darf.

Indexmenge

Die Menge aller Schlüssel (= Elementnamen) eines Tupels wird Indexmenge des Tupels genannt.

Länge eines Tupels

Die Länge eines Tupel ist gleich der Mächtigkeit der zugehörigen Indexmenge.

Ein Tupel der Länge $n$ wird auch $n$-Tupel genannt.

Gleichheit zweier Tupel

Zwei Tupel sind genau dann gleich, wenn die zugehörigen Indexmengen gleich sind und wenn die jeweils gleich benannten Elemente ebenfalls gleich sind.

Beispiele

Tupel sind im Prinzip nichts anderes als Funktionen, deren Definitionsbereich Indexmenge genannt wird. Eine Funktion ordnet jedem Element des Definitionsbreichs einen Wert zu, entsprechend ordnet ein Tupel jedem Schlüssel, also jedem Element der Indexmenge einen Wert zu.

Beispiele in Attribut-Notation

Im Fall von endlichen Indexmengen kann ein Tupel einfach durch die explizite Angabe von Schlüssel/Wert-Paaren erfolgen:

$t_1 = \{(\text{name}, \text{Wolfgang}), (\text{geburtsjahr}, \text{1961}), (\text{hochschule}, \text{HSA})\}$

$t_2 = \{(\text{name}, \text{Wolfgang}), (\text{geburtsjahr}, \text{1961}), (\text{ehefrau}, \text{Marianne})\}$

$t_3 = \{(\text{name}, \text{Wolfgang}), (\text{geburtsjahr}, \text{1962}), (\text{hochschule}, \text{HSA})\}$

$t_4 = \{(\text{ehefrau}, \text{Marianne}), (\text{geburtsjahr}, \text{1961}), (\text{name}, \text{Wolfgang})\}$

$t_5 = \{(\text{name}, \text{Wolfgang}), (\text{geburtsjahr}, \text{1961}), (\text{ehefrau}, \text{Marianne}), (\text{hochschule}, \text{HSA})\}$

Nur Tupel $t_2$ und $t_4$ sind gleich, alle anderen Tupel unterscheiden sich. Entweder stimmen nicht alle gleich benannten Elemente überein (Tupel $t_1$ und $t_3$) oder die Indexmengen unterscheiden sich (alle übrigen Tupelpaare).

Die Länge der ersten vier Tupel beträgt 3, die Länge des fünften Tupels beträgt 4.

Folgendes ist kein Tupel (und auch keine Funktion), da zwei Elemente gleich benannt sind:

$\{ (\text{name}, \text{Wolfgang}), (\text{name}, \text{Lukas}), (\text{hochschule}, \text{HSA})\}$

In der Informatik werden Schlüssel/Wert-Paare häufig als Attribute (attributes, properties) bezeichnet. Dabei werden der Schlüssel Attributname (attribute name, property name) und der Wert Atrtibutwert (attribute value, property value) genannt.

Beispielsweise können in JSON innerhalb einer Mengenklammer beliebig viele (jedoch nur endlich viele) Attribute angeben werden. Als Attributnamen werden Zeichenketten (Strings) verwendet. Der zugehörige Attributwert wird vom Attributnamen durch einen Doppelpunkt abgetrennt.

t1 = {"name": "Wolfgang", "geburtsjahr": 1961, "hochschule": "HSA"}

t2 = {"name": "Wolfgang", "geburtsjahr": 1961, "ehefrau": "Marianne"}

t3 = {"name": "Wolfgang", "geburtsjahr": 1962, "hochschule": "HSA"}

t4 = {"ehefrau": "Marianne", "geburtsjahr": 1961, "name": "Wolfgang", }

t5 = {"name": "Wolfgang", "geburtsjahr": 1961, "ehefrau": "Marianne", "hochschule": "HSA"}

Weitere Beispiele Datenstrukturen, in denen Mengen von Schlüssel/Wert-Paaren, d.h. Tupel zum Einsatz kommen.

• C/C++: Datentyp struct (zur Laufzeit nicht erweiterbar oder kürzbar)
• Pascal: Datentyp record (zur Laufzeit nicht erweiterbar oder kürzbar)
• diverse Sprachen: Hashtabelle (auch hash map, hash Array, assoziatives Array etc.; zur Laufzeit erweiterbar und kürzbar)
• SQL: Tabellenzeilen, d.h. Elemente von Relationen (zur Laufzeit durch Schema-Evolution erweiterbar und kürzbar)
• JavaScript: Objekte (zur Laufzeit erweiterbar oder kürzbar, sofern dies nicht explizit mittels Object.freeze „untersagt“ wird)
• Java und viele andere Sprachen: Objekte (zur Laufzeit i. Allg. nicht erweiterbar oder kürzbar)

Um mittels des Attributnamens auf einen Attributwert zuzugreifen, haben sich in der Informatik zwei syntaktische Konstrukte etabliert (obwohl es durchaus noch Sprachen gibt, die andere syntaktische Konstrukte verwenden):

• Die Indexnotation: t1["name"], t5["ehefrau"] etc.
• Die Punktnotation: t1.name, t5.ehefrau etc.

Beispiele in Vektor-Notation

Für Tupel, deren Indexmenge eine Menge von $n$ aufeinanderfolgenden natürlichen Zahlen ist (i. Allg. $\{i: 0 < i \le n\}$, oder, wie in vielen Programmiersprachen üblich, $\{i: 0 \le i < n\}$), bietet sich die in der Mathematik gebräuchliche Vektor-Notation an. Bei dieser werden die Elementnamen nicht explizit angegeben, sondern implizit durch die Position der Elemente festgelegt:

$t_6 = (555, 333)$

$t_7 = (333, 555)$

$t_8 = (555, 333, 555)$

$t_9 = (0, 2, 4, 6, 8, 10, 12, \ldots)$

Die Tupel $t_6$ bis $t_9$ unterscheiden sich alle voneinander. In Tupel $t_6$ steht an Position 1 das Element $555$, während in Tupel $t_7$ an Position 1 das Element $333$ steht. Tupel $t_8$ unterscheidet sich von Tupel $t_6$ und $t_7$, da die Indexmengen ($\{1,2\}$ bei Tupel $t_6$ und $t_7$; $\{1,2,3\}$ bei Tupel $t_8$) nicht übereinstimmen.

Tupel $t_6$ und $t_7$ sind $2$-Tupel, Tupel $t_8$ ist um ein Element länger, die Länge von Tupel $t_9$ beträgt ω (abzählbar unendlich). Tupel $t_9$ ist also ein ω-Tupel. Da ein unendlich großes Tupel nicht mehr explizit angegeben werden kann, muss die Definition entweder anschaulich erfolgen (siehe obige Definition von Tupel $t_9$) oder mittels einer Rechenvorschrift.

In JSON kommt die Vektor-Notation ebenfalls zu Einsatz:

t6 = [555, 333]

t7 = [333, 555]

t8 = [555, 333, 555]

Unendliche lange Tupel können in JSON nicht angegeben werden, wohl aber beispielsweise in JavaScript mit Hilfe der Bibliothek stream.js, die ein Element eines Streams (= Tupel) mittels Lazy Evaluation erst dann ermittelt, wenn es wirklich benötigt wird:

  var nat = Stream.range(0);                     // nat = (0, 1, 2, 3, ...)  
  var t9  = nat.map(function(x){ return 2*x; }); // t9  = (0, 2, 4, 6, ...) 
  t9.take(3).print();                            // Gibt 0, 2, 4 auf der Konsole aus

In der Informatik finden sich ebenfalls diverse Datenstrukturen, in denen Elemente sequenziell abgespeichert werden, d.h., in denen Tupel nicht als Menge von Attributen, sondern als Folge von Elementen aufgefasst werden:

• Arrays oder Felder (häufig mit fixer Länge)
• Listen (i. Allg. mit variabler Länge) in zahlreichen Ausprägungen
• Streams (evtl. unendlich lang)

Um mittels der Attributposition auf einen Attributwert zuzugreifen, hat sich in der Informatik ein syntaktisches Konstrukt etabliert:

• Die Indexnotation: t6[1], t8[2] etc.

Bei verketteten Listen, Streams etc. ist der Zugriff auf ein Element an einer bestimmten Position dagegen manchmal nur dadurch möglich, dass man sich von einem Element zu nächsten „hangelt“, bis man beim gewünschten Element angekommen sit.

Formale Definition (in Anlehnung an Ebbinghaus)

Familie, $I$-Tupel

Es sei $I$ eine Menge (oder, allgemeiner, eine Klasse).

Eine Funktion $f: I \rightarrow \mathcal{V}$ von $I$ in die Allklasse $\mathcal{V}$ heißt Familie oder Tupel,
genauer $I$-Familie oder $I$-Tupel der Länge $n := |I|$ über der Indexmenge (bzw. Indexklasse) $I$.

Gleichheit zweier Tupel

Zwei Tupel $t_1$ und $t_2$ sind genau dann gleich, wenn $t_1$ und $t_2$ als Klassen gleich sind, d.h., wenn:

$t_1 \subseteq t_2 \wedge t_2 \subseteq t_1$

oder, anders fomuliert:

$\forall x \in \mathcal{V}: x \in t_1 \Leftrightarrow x \in t_2$

Satz

Es seien $t_1$ und $t_2$ zwei Tupel.

$t_1$ und $t_2$ sind genau dann gleich, wenn die zugehörigen Indexmengen übereinstimmen und wenn die Funktionswerte für jedes Element der Indexmenge ebenfalls übereinstimmen:

$t_1 = t_2 \Leftrightarrow \rm{Def}(t_1) = \rm{Def}(t_2) \wedge \forall i \in \rm{Def}(t_1): t_1(i) = t_2(i)$

Mit $\rm{Def}(f)$ wird hier die Definitionsmenge, also die Indexmenge einer Funktion $f$ bezeichnet.

Lemma

Zwei gleiche Tupel sind trivialerweise gleichlang:

$t_1 = t_2 \Rightarrow |t_1| = |t_2|$

Beweis: Die Behauptung folgt direkt aus der Leibnitzschen Ersetzbarkeit.

Spezielle Tupel

Länge $n$	Name
0	Leeres Tupel
1	Singel
2	(geordnetes) Paar
3	Triple
4	Quadrupel
5	Quintupel
6	Sextupel
7	Septupel
8	Oktupel
$\vdots$	$\vdots$
100	Centupel
$n$	$n$-Tupel
ω	ω-Tupel, Folge, Reihe, Familie

Anmerkungen

Tupel können als geordnete Multimengen, d.h. als Listen aufgefasst werden, sofern für die Elementnamen eine Ordnung definiert ist:

• Elementwerte können mehrfach vorkommen (im Gegensatz zu normalen Mengen aber in Einklang mit Multimengen).
• Die Elemente sind angeordnet (im Gegensatz zu Mengen und Multimengen). Die Ordnung ist durch die Ordnung der Elementnamen vorgegeben.

Insbesondere für Tupel in Vektornotation trifft diese Aussage zu: Als Elementnamen werden natürliche Zahlen verwendet und legen damit eine sehr natürliche Ordnung fest.

Siehe auch

• Kowarschick, W. (2013): Skriptum zur Vorlesung Multimedia-Datenbanksysteme