Tupel-Rechnung ist eine Rechnung, die von Edgar F. Codd als ein Teil des Verwandtschaftsmodells eingeführt wurde, um eine Aussagedatenbankabfrage-Sprache für dieses Datenmodell zur Verfügung zu stellen. Es hat die Inspiration für die Datenbankabfrage-Sprachen QUEL und SQL gebildet, dessen der Letztere, obwohl viel weniger treu, dem ursprünglichen Verwandtschaftsmodell und der Rechnung, jetzt die De-Facto-Standarddatenbankabfrage-Sprache ist; nämlich wird ein Dialekt von SQL durch fast jedes Verwandtschaftsdatenbankmanagement-System verwendet. Lacroix und Pirotte haben Bereichsrechnung vorgeschlagen, die an der Logik der ersten Ordnung näher ist, und die gezeigt hat, dass beide dieser Rechnungen (sowie Verwandtschaftsalgebra) in der ausdrucksvollen Macht gleichwertig sind. Nachher wurden Anfragensprachen für das Verwandtschaftsmodell Verwandtschafts-abgeschlossen genannt, wenn sie mindestens alle diese Abfragen ausdrücken konnten.

Definition der Rechnung

Verwandtschaftsdatenbank

Da die Rechnung eine Anfragensprache für Verwandtschaftsdatenbanken ist, müssen wir zuerst eine Verwandtschaftsdatenbank definieren. Der grundlegende Verwandtschaftsbaustein ist das Gebiet oder Datentyp. Ein Tupel ist ein bestellter Mehrsatz von Attributen, die befohlene Paare des Gebiets und Werts sind; oder gerade eine Reihe. Ein relvar (Beziehungsvariable) ist eine Reihe von befohlenen Paaren des Gebiets und Namens, der als der Kopfball für eine Beziehung dient. Eine Beziehung ist eine Reihe von Tupeln. Obwohl diese Verwandtschaftskonzepte, jene Definitionen Karte lose zu traditionellen Datenbankkonzepten mathematisch definiert werden. Ein Tisch ist eine akzeptierte Sehdarstellung einer Beziehung; ein Tupel ist dem Konzept der Reihe ähnlich.

Wir nehmen zuerst die Existenz eines Satzes C von Säulennamen an, von denen Beispiele "Name", "Autor", "Adresse" und so weiter sind. Wir definieren Kopfbälle als begrenzte Teilmengen von C. Ein Verwandtschaftsdatenbankdiagramm wird als ein Tupel S = definiert (D, R, h), wo D das Gebiet von Atomwerten ist (sieh Verwandtschaftsmodell für mehr auf den Begriffen des Gebiets und Atomwerts), R ist ein begrenzter Satz von Beziehungsnamen und

:h: R  2

eine Funktion, die einen Kopfball mit jedem Beziehungsnamen in R. vereinigt (Bemerken, dass das eine Vereinfachung vom vollen Verwandtschaftsmodell ist, wo es mehr als ein Gebiet und einen Kopfball gibt, ist nicht nur eine Reihe von Säulennamen sondern auch stellt diese Säulennamen zu einem Gebiet kartografisch dar.) Gegeben ein Gebiet D definieren wir ein Tupel über D als eine teilweise Funktion

:t: C  D

das stellt einige Säulennamen zu einem Atomwert in D kartografisch dar. Ein Beispiel würde sein (Name: "Verwüsten" Alter: 25).

Der Satz aller Tupel über D wird als T angezeigt. Die Teilmenge von C, für den ein Tupel t definiert wird, wird das Gebiet von t genannt (um mit dem Gebiet im Diagramm nicht verwirrt zu sein), und hat als dom (t) angezeigt.

Schließlich definieren wir eine Verwandtschaftsdatenbank gegeben ein Diagramm S = (D, R, h) als eine Funktion

:db: R  2

das stellt die Beziehungsnamen in R zu begrenzten Teilmengen von T, solch kartografisch dar, dass für jeden Beziehungsnamen r in R und Tupel t im DB (r) es das hält

:dom (t) = h (r).

Die letzte Voraussetzung sagt einfach, dass alle Tupel in einer Beziehung dieselben Säulennamen, nämlich diejenigen enthalten sollten, die dafür im Diagramm definiert sind.

Atome

Für den Aufbau der Formeln werden wir einen unendlichen Satz V von Tupel-Variablen annehmen. Die Formeln werden gegeben ein Datenbankdiagramm S = (D, R, h) und ein teilweiser Funktionstyp definiert: V-> 2, der eine Typ-Anweisung definiert, die Kopfbälle einigen Tupel-Variablen zuteilt. Wir definieren dann den Satz von atomaren Formeln A [S, Typ] mit den folgenden Regeln:

1. wenn v und w in V im Typ (v) und b im Typ (w) dann die Formel "v.a = w.b" in [S, Typ], ist
2. wenn v in V, im Typ (v) und k einen Wert in D dann anzeigt, ist die Formel "v.a = k" in [S, Typ], und
3. wenn v in V, r in R und Typ (v) = h (r) dann die Formel "r (v)" in [S, Typ] ist.

Beispiele von Atomen sind:

• (t.age = s.age) — t hat ein Altersattribut, und s hat ein Altersattribut mit demselben Wert
• (t.name = "Codd") — Tupel t hat ein Namenattribut, und sein Wert ist "Codd"
• Buch (t) — Tupel t ist im Beziehungsbuch da.

Die formelle Semantik solcher Atome wird gegeben ein Datenbank-DB über S und eine Tupel-Variable definiert, die val bindet: V-> T, der Tupel-Variablen zu Tupeln über das Gebiet in S kartografisch darstellt:

1. "v.a = w.b" ist wenn und nur wenn val (v) (a) = val (w) (b) wahr
2. "v.a = k" ist wenn und nur wenn val (v) (a) = k wahr
3. "r (v)" ist wahr, wenn, und nur wenn val (v) im DB (r) ist

Formeln

Die Atome können in Formeln verbunden werden, wie in der Logik der ersten Ordnung, mit den logischen Maschinenbedienern  (und),  (oder) und ¬ (nicht) üblich ist, und wir den existenziellen quantifier () und den universalen quantifier () verwenden können, um die Variablen zu binden. Wir definieren den Satz von Formeln F [S, Typ] induktiv mit den folgenden Regeln:

1. jedes Atom in [S, Typ] ist auch in F [S, Typ]
2. wenn f und f in F [S, Typ] dann sind, ist die Formel "f  f" auch in F [S, Typ]
3. wenn f und f in F [S, Typ] dann sind, ist die Formel "f  f" auch in F [S, Typ]
4. wenn f in F [S, Typ] dann ist, ist die Formel "¬ f" auch in F [S, Typ]
5. wenn v in V, H ein Kopfball und f eine Formel in F [S, Typ] dann die Formel " v: H (f)" ist auch in F [S, Typ], wo Typ die Funktion anzeigt, die gleich ist, um zu tippen, außer dass es v zu H, kartografisch darstellt
6. wenn v in V, H ein Kopfball und f eine Formel in F [S, Typ] dann die Formel " v: H (f)" ist auch in F [S, Typ]

Beispiele von Formeln:

• t.name = "C. J. Date"  t.name = "H. Darwen"
• Buch (t)  Zeitschrift (t)
•  t: {Autor, Titel, Thema} (¬ (Buch (t)  t.author = "C. J. Date"  ¬ (t.subject = "Verwandtschaftsmodell")))

Bemerken Sie, dass die letzte Formel feststellt, dass alle Bücher, die von C. J. Date geschrieben werden, als ihr Thema das Verwandtschaftsmodell haben. Wie gewöhnlich lassen wir Klammern weg, wenn das keine Zweideutigkeit über die Semantik der Formel verursacht.

Wir werden annehmen, dass die quantifiers über das Weltall aller Tupel über das Gebiet im Diagramm messen. Das führt zur folgenden formellen Semantik für Formeln gegeben ein Datenbank-DB über S und eine Tupel-Variable, die val bindet: V-> T:

1. "f  f" ist wahr, wenn, und nur wenn "f" wahr ist und "f", wahr

ist

1. "f  f" ist wahr, wenn, und nur wenn "f" wahr ist oder "f" wahr ist oder beide, wahr

sind

1. "¬ f" ist wahr, wenn, und nur wenn "f", nicht wahr

ist

1. " v: H (f)" ist wenn und nur wahr, wenn es ein Tupel t über solchen D gibt, dass dom (t) = H und die Formel "f" für val und wahr

ist

1. " v: H (f)" ist wahr, wenn und nur wenn für alle Tupel t über solchen D, dass dom (t) = H die Formel "f" für val wahr ist.

Abfragen

Schließlich definieren wir, wie was ein Anfragenausdruck gegeben ein Diagramm S = (D, R, h) aussieht:

: {v: H | f (v) }\

wo v eine Tupel-Variable, H ein Kopfball und f (v) eine Formel in F [S, Typ] wo Typ = {(v, H)} und mit v als seine einzige freie Variable ist. Das Ergebnis solch einer Abfrage für ein gegebenes Datenbank-DB über S ist der Satz aller Tupel t über D mit dom (t) = H solch, dass f für das DB und val = {(v, t)} wahr ist.

Beispiele von Anfragenausdrücken sind:

• {t: {Name}  s: {Name, Lohn} (Angestellter  s.wage = 50.000  t.name = s.name) }\
• {t: {Lieferant, Artikel}  s: {s#, sname} (Lieferant (En)  s.sname = t.supplier   p: {p#, pname} (Produkt (p)  p.pname = t.article   a: {s#, p#} (Bedarf (a)  s.s# = a.s#  a.p# = p.p#) }\

Semantische und syntaktische Beschränkung der Rechnung

Bereichsunabhängige Abfragen

Weil die Semantik des quantifiers solch ist, dass sie über alle Tupel über das Gebiet im Diagramm messen, kann es sein, dass eine Abfrage ein verschiedenes Ergebnis für eine bestimmte Datenbank zurückgeben kann, wenn ein anderes Diagramm gewagt wird. Denken Sie zum Beispiel die zwei Diagramme S = (D, R, h) und S = (D, R, h) mit Gebieten D = {1}, D = {1, 2}, Beziehung nennt R = {"r"} und Kopfbälle h = {("r", {"a"})}. Beide Diagramme haben ein allgemeines Beispiel:

: DB = {("r", {("a", 1)}) }\

Wenn wir den folgenden Anfragenausdruck denken

: {t: | t.a = t.a }\

dann ist sein Ergebnis auf dem DB irgendein {(a: 1)} unter S oder {(a: 1), (a: 2)} unter S. Es wird auch klar sein, dass, wenn wir das Gebiet nehmen, um ein unendlicher Satz dann zu sein, das Ergebnis der Abfrage auch unendlich sein wird. Um diese Probleme zu beheben, werden wir unsere Aufmerksamkeit auf jene Abfragen einschränken, die Gebiet unabhängig, d. h., die Abfragen sind, die dasselbe Ergebnis für eine Datenbank laut aller seiner Diagramme zurückgeben.

Ein interessantes Eigentum dieser Abfragen besteht darin, dass, wenn wir annehmen, dass sich die Tupel-Variablen über Tupel über das so genannte aktive Gebiet der Datenbank erstrecken, die die Teilmenge des Gebiets ist, das in mindestens einem Tupel in der Datenbank oder im Anfragenausdruck dann vorkommt, sich die Semantik der Anfragenausdrücke nicht ändert. Tatsächlich in vielen Definitionen der Tupel-Rechnung ist das, wie die Semantik des quantifiers definiert wird, der alle Abfragen definitionsgemäß unabhängiges Gebiet macht.

Sichere Abfragen

Um die solche Anfragenausdrücke zu beschränken, dass sie nur bereichsunabhängige Abfragen ausdrücken, wird ein syntaktischer Begriff der sicheren Abfrage gewöhnlich eingeführt. Um zu bestimmen, ob ein Anfragenausdruck sicher ist, werden wir zwei Typen der Information von einer Abfrage ableiten. Das erste ist, ob ein Paar der variablen Säule t.a zur Säule einer Beziehung oder einer Konstante gebunden wird, und das zweite ist, ob zwei Paare der variablen Säule direkt oder indirekt ausgeglichen werden (hat t.v == s.w angezeigt).

Um boundedness abzuleiten, führen wir die folgenden vernünftig urteilenden Regeln ein:

1. in "v.a = w.b" kein Paar der variablen Säule, wird gebunden
2. in "v.a = k" das Paar der variablen Säule wird v.a, gebunden
3. in "r (v)" alle Paare werden v.a für im Typ (v), gebunden
4. in "f  f" alle Paare werden gebunden, die entweder in f oder in f, gebunden werden
5. in "f  f" alle Paare werden gebunden, die sowohl in f als auch in f, gebunden werden
6. in "¬ f" keine Paare, werden gebunden
7. in " v: H (f)" ein Paar wird w.a gebunden, wenn er in f und w gebunden wird

1. in " v: H (f)" ein Paar wird w.a gebunden, wenn er in f und w gebunden wird

Um equatedness abzuleiten, führen wir die folgenden vernünftig urteilenden Regeln ein (neben den üblichen vernünftig urteilenden Regeln für Gleichwertigkeitsbeziehungen: reflexivity, Symmetrie und transitivity):

1. in "v.a = w.b" meint es dass v.a == w.b,
2. in "v.a = k" keine Paare, werden ausgeglichen
3. in "r (v)" werden keine Paare, ausgeglichen
4. in "f  f" meint es, dass v.a == w.b, wenn es entweder in f oder in f, hält
5. in "f  f" meint es, dass v.a == w.b, wenn es sowohl in f als auch in f, hält
6. in "¬ f" keine Paare, werden ausgeglichen
7. in " v: H (f)" meint es, dass w.a == x.b, wenn es in f und w hält
8. in " v: H (f)" meint es, dass w.a == x.b, wenn es in f und w hält

Wir sagen dann dass ein Anfragenausdruck {v: H | f (v)} ist wenn sicher

• für jeden Säulennamen a in H können wir das ableiten v.a wird mit einem bestimmten Paar in f, ausgeglichen
• für jeden Subausdruck von f der Form " w: G (g)" können wir das für jeden Säulennamen a in G ableiten wir können das ableiten w.a wird mit einem bestimmten Paar in g und ausgeglichen
• für jeden Subausdruck von f der Form " w: G (g)" können wir das für jeden Säulennamen a in G ableiten wir können das ableiten w.a wird mit einem bestimmten Paar in g ausgeglichen.

Die Beschränkung zu sicheren Anfragenausdrücken beschränkt das Ausdrucksvolle seit allen bereichsunabhängigen Abfragen nicht, die ausgedrückt werden konnten, kann auch durch einen sicheren Anfragenausdruck ausgedrückt werden. Das kann durch die Vertretung bewiesen werden, dass für ein Diagramm S = (D, R, h), ein gegebener K von Konstanten im Anfragenausdruck, eine Tupel-Variable v und ein Kopfball H gesetzt hat, können wir eine sichere Formel für jedes Paar v.a mit in H bauen, der feststellt, dass sein Wert im aktiven Gebiet ist. Nehmen Sie zum Beispiel an, dass K = {1,2}, R = {"r"} und h = {("r", {"a ", b"})} dann die entsprechende sichere Formel für v.b ist:

: v.b = 1  v.b = 2   w (r (w)  (v.b = w.a  v.b = w.b))

Diese Formel kann dann verwendet werden, um jeden unsicheren Anfragenausdruck zu einem gleichwertigen sicheren Anfragenausdruck durch das Hinzufügen solch einer Formel für jede Variable v und Säulennamen a in seinem Typ umzuschreiben, wo es im Ausdruck verwendet wird. Effektiv bedeutet das, dass wir alle Variablen sich über das aktive Gebiet erstrecken lassen, das, wie bereits erklärt wurde, die Semantik nicht ändert, wenn die ausgedrückte Abfrage unabhängiges Gebiet ist.

Siehe auch

• Verwandtschaftsalgebra

Verwandtschaftsrechnung

• Gebiet Verwandtschaftsrechnung (DRC)
• Edgar F. Codd: Ein Verwandtschaftsmodell von Daten für Große Geteilte Datenbanken. Kommunikationen des ACM, 13 (6):377-387, 1970.