Tupel
Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:
Korrektheit: 3 (zu größeren Teilen überprüft) |
Umfang: 4 (unwichtige Fakten fehlen) |
Quellenangaben: 5 (vollständig vorhanden) |
Quellenarten: 5 (ausgezeichnet) |
Konformität: 5 (ausgezeichnet) |
Anschauliche Definition (Kowarschick)
Ein Tupel ordnet jedem Element einer Klasse (oder Menge) von Schlüsseln oder Attributnamen jeweilse einen Wert zu. Ein Tupel ist also eine Klasse von unterschiedlich benannten Attributen, d.h. eine Klasse von Schlüssel/Wert-Paaren, wobei jeder Schlüssel nur einmal vorkommen darf.
Begriff | Alternativnamen | englische Bezeichnungen |
---|---|---|
Tupel | Familie, Folge | tuple, sequence, indexed family, |
Attribut | Schlüssel/Wert-Paar | attribute, key/value pair, property |
Attributname | Schlüssel, Index | key, index, attribute/property name, attribute/property key |
Attributwert | Wert, Glied | value, attribute/property value |
Attribute können auch mehr als einen Attributnamen haben. Diese werden dann mit Schlüssel-Schlüssel-Wert-Tripeln etc. dargestellt.
Indexbereich und Indexmenge
Die Klasse aller Schlüssel eines Tupels wird Indexbereich des Tupels genannt. Wenn es sich beim Indexbereich um eine Menge handelt, kann man auch Indexmenge sagen.
Tupellänge
Die Länge eines Tupel ist gleich der Mächtigkeit des zugehörigen Indexbereichs.
Ein Tupel der Länge $ l $ wird auch $ l $-Tupel genannt.
Gleichheit zweier Tupel
Zwei Tupel sind genau dann gleich, wenn die zugehörigen Indexbereiche gleich sind und wenn die Werte jeweils gleich benannter Elemente ebenfalls gleich sind.
Formale Definition (Kowarschick)
Siehe Tupel: Formale Definition.
Anmerkungen
Tupel sind im Prinzip nichts anderes als Funktionen, deren Definitionsbereich Indexbereich genannt wird. Eine Funktion ordnet jedem Element des Definitionsbereichs einen Wert zu, entsprechend ordnet ein Tupel jedem Schlüssel, also jedem Element des Indexbereichs einen Wert zu.
Tupel können auch als geordnete Multimengen, d.h. als Listen aufgefasst werden, sofern für den Indexbereich eine Ordnung definiert ist:
- Werte können mehrfach vorkommen (im Gegensatz zu normalen Mengen, aber in Einklang mit Multimengen).
- Die Werte sind (gemäß der auf den Schlüsseln definierten Ordnung) angeordnet (im Gegensatz zu Mengen und Multimengen).
Üblicherweise spielt in der Informatik die Ordnung der Tupelelemente nur dann eine Rolle , wenn als Indexbereich eine Menge von aufeinanderfolgenden natürlichen Zahlenverwendet wird.
Beispiele
Tupelart | Tupelschema | Beispiel |
---|---|---|
Attributtupel Attributnotation |
{name: String, sex: {'f','m','x'}}
|
{name: 'Anton', sex: 'm'}
|
Positionstupel Attributnotation Listennotation |
{1: String, 2: {'f','m','x'}} (String, {'f','m','x'})
|
{1: 'Anton', 2: 'm'} ('Anton', 'm')
|
Positionsattributtupel Attributnotation Listennotation |
{1/name: String, 2/sex: {'f','m','x'} } (name: String, sex: {'f','m','x'})
|
{1/name: 'Anton', 2/sex: 'm' } (name: 'Anton', sex:'m')
|
Positionsattributtupel sind Tupel, deren Attribute zwei unterschiedliche Attributnamen haben: Eine Zeichenkette und einen Positionsbezeichner. Dies ist die ideale Darstellung für Tupel, die durch Tabellenzeilen repräsentiert werden:
name | sex | spouse |
---|---|---|
'Anton'
|
'm'
|
'Berta'
|
'Berta'
|
'f'
|
'Anton'
|
'Cäsar'
|
'm'
|
null
|
Jedes Attribut dieser drei Tupel hat sowohl einen Namen, der über der jeweiligen Spalte notiert wird, sowie eine Position, die sich durch die Spaltenposition ergibt.
In den folgenden Beispielen werden Attribute teils mittels Attributnotation a:v
, i/a:v
und teils mittels
Listennotation $ (a,v) $, $ (i,a,v) $ dargestellt.
Attributnotation
Im Fall von endlichen Indexbereichen kann ein Tupel einfach durch die explizite Angabe von Schlüssel/Wert-Paaren erfolgen.
t1 = {name: 'Anton', geburtsjahr: 1961, ehefrau: 'Berta'}
t2 = {ehefrau: 'Berta', geburtsjahr: 1961, name: 'Anton'}
t3 = {name: 'Anton', geburtsjahr: 1961, hochschule: 'HSA'}
t4 = {name: 'Anton', geburtsjahr: 1962, hochschule: 'HSA'}
t5 = {name: 'Anton', geburtsjahr: 1961, ehefrau: 'Berta', hochschule: 'HSA'}
Nur Tupel t1
und t2
sind gleich, alle anderen Tupel unterscheiden sich. Entweder unterscheiden sich
die Indexbereiche (t1
bis t4
haben die Länge 3, Tupel t5
hat dagegen die Länge 4) oder
es stimmen nicht alle gleich benannten Elemente überein (alle übrigen Tupelpaare).
Folgendes ist kein Tupel (und damit auch keine Funktion), da zwei Elemente gleich benannt sind:
{name: 'Anton', name: 'Cäsar', hochschule: 'HSA'}
Attributnotation in der Informatik
Die Attributnotation kommt in der Informatik häufig zum Einsatz.
Beispielsweise können in JSON innerhalb einer Mengenklammer beliebig viele (jedoch nur endlich viele)
Attribute angeben werden. Als Attributnamen werden Zeichenketten (Strings) verwendet, die mit Anführungszeichen "
markiert sind.
Der zugehörige Attributwert wird vom Attributnamen durch einen Doppelpunkt abgetrennt.
{"name": "Anton", "geburtsjahr": 1961, "ehefrau": "Berta"}
...
Weitere Beispiele für Datenstrukturen, in denen Mengen von Schlüssel/Wert-Paaren zum Einsatz kommen:
- C/C++: Datentyp
struct
(die Länge kann zur Laufzeit nicht verändert werden) - Pascal: Datentyp
record
(die Länge kann zur Laufzeit nicht verändert werden) - diverse Sprachen: Hashtabelle (auch hash map, hash array, assoziatives Array etc.; die Länge kann zur Laufzeit verändert werden)
- SQL: Tabellenzeilen, d.h. Elemente von Relationen (die Länge kann zur Laufzeit durch Schema-Evolution verändert werden)
- JavaScript: Objekte (die Länge kann zur Laufzeit verändert werden, sofern dies nicht explizit mittels
Object.freeze
„untersagt“ wird) - Java und viele andere Sprachen: Objekte (die Länge kann zur Laufzeit i. Allg. nicht verändert werden)
Attributzugriff
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.
In der Mathematik sind dagegen folgende Konstrukte üblich:
- Die Funktionsauswertung: $ \rm{t1}(\rm{name}) $, $ \rm{t5}(\rm{ehefrau}) $ etc.
- Die Projektionsfunktion $ π $: $ π_{\rm{name}}(\rm{t1}) $, $ π_{\rm{ehefrau}}(\rm{t5}) $ etc.
- Die Indexnotation: $ \rm{t1}_{\rm{name}} $, $ \rm{t5}_{\rm{ehefrau}} $ etc.
Listennotation
Für Tupel, deren Indexbereich 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 Listennotation an. Bei dieser werden die Schlüssel nicht explizit angegeben, sondern implizit durch die Position der Elemente festgelegt:
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 Indexbereiche ($ \{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 ω. Tupel $ t_9 $ enthält also abzählbar unendlich Elemente. 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:
Listennotation in der Informatik
In der Informatik, wie beispielsweise in JSON, kommt die Listennotation ebenfalls zu Einsatz:
t6 = [555, 333]
t7 = [333, 555]
t8 = [555, 333, 555]
Unendliche lange Tupel können in JSON nicht definiert werden. Allerdings ist es in JavaScript möglich, mittels Generatoren beliebig große Tupel zu generieren. Der Generator selbst kann als unendlich langes Tupel aufgefasst werden:
// Generator für Fibonacci-Zahlen (BigInt).
function* fib()
{ let a = 0n, b = 1n; // 0n = BigInt(0), 1n = BigInt(1), ...
yield a;
yield b;
while (true)
{ [a, b] = [b, a+b];
yield b;
}
}
// Hilfsfunktion zum Materialisieren der
// ersten n Elemente eines Generators.
function take(n, p_iterable)
{ let tuple = [], i = 0;
while (i++ < n)
{ tuple.push(p_iterable.next().value); }
return tuple;
}
let f = fib();
console.log(f.next().value, f.next().value, f.next().value, f.next().value, f.next().value);
// -> 0n, 1n, 1n, 2n, 3n
console.log(take(1000, fib()));
// -> [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n ...] // tausend Elemente
In der Informatik finden sich weitere Datenstrukturen, in denen Elemente sequenziell abgespeichert werden, d.h., bei denen Tupel nicht als Menge von Attributen, sondern als Folge von Elementen aufgefasst werden:
- Arrays oder Felder (häufig mit fixer Länge)
- Listen in zahlreichen Ausprägungen (i. Allg. mit variabler Länge)
- Streams (evtl. sogar unendlich lang)
Attributzugriff
Um mittels der Attributposition auf einen Attributwert zuzugreifen, hat sich in der Informatik ein syntaktisches Konstrukt etabliert:
- Die Indexnotation:
t[1]
,t[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 mittels einer Funktion oder Methode (z. B. next
) von einem
Element zu nächsten „hangelt“ (Traversierung), bis man beim
gewünschten Element angekommen ist (siehe z. B. die Funktion take
im vorangegangenen Abschnitt).
In der Mathematik sind dagegen folgende Konstrukte üblich:
- Die Funktionsauswertung: $ t(1) $, $ t(2) $ etc.
- Die Indexnotation: $ t_1 $, $ t_2 $ etc.
- Die Projektionsfunktion $ π $: $ π_1(t) $, $ π_2(t) $ etc.
Spezielle Tupel mit Positionsattributen
Länge $ n $ | Name | Attributnotation | Listennotation |
---|---|---|---|
0 | Leeres Tupel | $ \{\} $ | $ () $ |
1 | Singel | $ \{(1,5)\} $ | $ (5) $ |
2 | (geordnetes) Paar | $ \{(1,5), (2,3)\} $ | $ (5,3) $ |
3 | Triple | $ \{(1,5), (2,3), (3,8)\} $ | $ (5,3,8) $ |
4 | Quadrupel | $ \{(1,5), (2,3), (3,8), (4,π)\} $ | $ (5,3,8,π) $ |
5 | Quintupel | $ \vdots $ | $ \vdots $ |
6 | Sextupel | ||
7 | Septupel | ||
8 | Oktupel | ||
$ \vdots $ | $ \vdots $ | ||
100 | Centupel | ||
n | n-Tupel | ||
ω oder $ \aleph_0 $ | ω- oder oder $ \aleph_0 $-Tupel | $ \{(i,i^2)| i \in \mathbb N\} $ | $ (i^2)_{i \in \mathbb N} $ |
$ 2^{\aleph_0} $ | $ 2^{\aleph_0} $-Tupel | $ \{(r,r^2)| i \in \mathbb R\} $ | $ (r^2)_{r \in \mathbb R} $ |
Jede endliche oder abzählbar unendliche Folge, Sequenz oder Familie kann als Tupel in Listennotation aufgefasst werden. Jede (mathematische) Funktion kann als Tupel aufgefasst werden.
Geschichte
Definition „Tupel“ (Bourbaki (1939)[1])
Die Mathematikergruppe Bourbaki definiert zunächst das geordnete Paar (couple) nach Kazimierez Kuratowski und erwähnen, dass es das Paaraxiom erfüllt (S. E II.7):
Im Anschluss daran definieren sie das geordnete Tripel (triplet) mit Hilfe zweier Paare (S. E II.9):
Sie weisen außerdem daraufhin, dass sich dies für vier und mehr Elemente verallgemeinern lässt.
Auf Seite E IV.5 führt Bourbaki den Begriff Tupel (multiplet) für den Term $ (s_1,\ldots,s_p) $ ein und verweisen dabei explizit auf die obige Definition.
Zusammenfassung: Der Begriff Tupel (multiplet) wird von Bourbaki folgendermaßen definiert:
$ (x,y) := \{\{x\},\{x,y\}\} $
Wenn $ n \ge 3 $, dann $ (x_1,\ldots,x_n) := ((x_1,\ldots,x_{n-1}), x_n) $
Definition „Familie“ (Bourbaki (1939)[2])
Die Mathematikergruppe Bourbaki definiert zunächst funktionelle Relationen (Relations fonctionelles) als Relationen $ R $, die rechtseindeutig sind (S. E I.40):
Im Anschluss an die Paardefinition (siehe vorangegangenen Abschnitt) zeigt das Mathematikerteam, dass jede Relation eindeutig durch eine Menge von Paaren repräsentiert wird. Diese Menge bezeichnen sie als Graph (graphe) der Relation:
Le graphe $ G $ est alors unique en vertu de l'axiome d'extensionalite, et s'appelle le graphe
de $ R $Anschließend definieren sie die eigenlichen Funktionen (fonctions) als funktionelle Relationen mit Definitionsbereich $ A $ und Wertebereiche $ B $ (S. E II.13):
$ F $ ist als Graf der Funktion eine Menge von Paaren. Dies ist die typische Mengentheoretische Definition des Funktionsbegriffs.
Zu guter Letzt führt die Gruppe den Begriff Familie als Alternative für den Begriff Funktion ein (S. E II.16):
Die Begriffe Familie' und Funktion unterscheiden sich nur syntaktisch. Die Syntax $ (f_x)_{x \in A} $ wurde in Anlehnung an die Tupelsyntax gewählt und betont damit die Verwandschaft zwischen diesen beiden Begriffen. Der Begriff Familie kann also als Alternative für den Begriff Tupel aufgefasst werden. Diese Definition hat den Vorteil hat, dass auch nicht-endliche Indexbereiche unterstützt werden.
Definition (Gödel (1940)[3])
Dfn $ <xy> = \{\{x\}\{xy\}\} $
Dfn $ <x_1,\ldots,x_n> = <x_1<x2\ldots x_{n}>> $ [Anm. WK: wobei $ n \ge 3 $]
Dfn $ <x> = x $
Wegen der Rechtsassoziativität gilt folgender Satz (wie man laut Gödel per Indujktion nachweist):
$ <x_1,\ldots,x_n<x_{n+1}\ldots x_{n+p}>> = <x_1\ldots x_{n}x_{n+1}\ldots x_{n+p}>> $
Anmerkung:
Diese Definition unterschiedet sich nicht wesentlich von der Definition der Mathematikergruppe Bourbaki (siehe Definition zuvor): Die Klammerung wurde rechts- an Stelle von linksassoziativ angegeben und das einelementige Tupel wurde als Spezialfall ergänzt.
Definition (McCarthy (1960)[4])
TO BE DONE
Definition (McCarthy et al. (1965)[5])
TO BE DONE
Definition (Schmidt (1966)[6])
TO BE DONE
Definition (Ebbinghaus (2003)[7])
Ebbinghaus definiert zunächst das geordnete Paar
nach Kazimierez Kuratowski und verallgemeinert es dann für beliebige $ n $-Tupel ($ n \ge 1 $):
(i) $ (x) := x $
(ii) Für $ n \ge 1 $ sei $ (x_0,\ldots,x_n) := ((x_0,\ldots,x_{n-1}), x_n) $
Er formuliert den folgenden Satz:
Einen Beweis gibt er nicht an, da sich dieser leicht durch metaprachliche Induktion ergäbe.
Anmerkung:
Diese Definition unterschiedet sich nicht von der Definition der Mathematikergruppe Bourbaki (siehe oben). Es wurde lediglich das einelementige Tupel als Spezialfall ergänzt, in derselben Weise, wie dies Gödel vorgeschlagen hat (siehe oben).
Quellen
- ↑ Bourbaki (1939): Nicolas Bourbaki; Théorie des ensembles; Verlag: Hermann; Adresse: Paris; 1939; Quellengüte: 5 (Buch), S. E II.7, E II.9, E IV.5
- ↑ Bourbaki (1939): Nicolas Bourbaki; Théorie des ensembles; Verlag: Hermann; Adresse: Paris; 1939; Quellengüte: 5 (Buch), S. E I.40, S. E II.13, S. E II.16
- ↑ Gödel (1940): Kurt Gödel; The Consistency of the Continuum Hypothesis; Verlag: Princeton University Press; ISBN: 0-691-07927-7; Web-Link; 1940; Quellengüte: 5 (Buch), S. 4
- ↑ McCarthy (1960): John McCarthy; Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I; in: Communications of the ACM; Band: 3; Nummer: 4; Seite(n): 184-195; Verlag: Association for Computing Machinery; Adresse: New York; Web-Link 0, Web-Link 1; 1960; Quellengüte: 5 (Artikel)
- ↑ McCarthy et. al. (1965): John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart und Michael I. Levin; LISP 1.5 Programmer's Manual; Verlag: The MIT Press; Adresse: Cambridge, Massachusetts; Web-Link; 1965 (Buch)
- ↑ Schmidt (1966): Jürgen Schmidt; Mengenlehre – Grundbegriffe; Reihe: B.I.Hochschultaschenbücher; Band: 1; Nummer: 56; Verlag: Bibliographisches Institut AG; Adresse: Mannheim; ISBN: B0000BUJC6; 1966; Quellengüte: 5 (Buch), S. 122
- ↑ Ebbinghaus (2003): Heinz-Dieter Ebbinghaus; Einführung in die Mengenlehre; Reihe: Hochschultaschenbuch; Auflage: 4; Verlag: Spektrum Akademischer Verlag; Adresse: Heidelberg, Berlin; ISBN: 3-8274-1411-3; 2003; Quellengüte: 5 (Buch), S. 59–60
Siehe auch
- Kowarschick (MMDB-Skript): Wolfgang Kowarschick; Vorlesung Multimedia-Datenbanksysteme – Sommersemester 2018; Hochschule: Hochschule Augsburg; Adresse: Augsburg; Web-Link; 2018; Quellengüte: 4 (Skript)