Verwandtschaftsalgebra, ein Spross der Logik der ersten Ordnung (und der Algebra von Sätzen), befasst sich mit einer Reihe von finitary Beziehungen (sieh auch Beziehung (Datenbank)), der unter bestimmten Maschinenbedienern geschlossen wird. Diese Maschinenbediener funktionieren auf einer oder mehr Beziehungen, um eine Beziehung nachzugeben. Verwandtschaftsalgebra ist ein Teil der Informatik.

Einführung

Verwandtschaftsalgebra hat wenig Aufmerksamkeit außerhalb der reinen Mathematik bis zur Veröffentlichung des Verwandtschaftsmodells von E.F. Codd von Daten 1970 erhalten. Codd hat solch eine Algebra wie eine Basis für Datenbankanfragensprachen vorgeschlagen. (Sieh Abteilungsdurchführungen.)

Verwandtschaftsalgebra ist in der ausdrucksvollen Macht zur Verwandtschaftsrechnung (und so Logik der ersten Ordnung) im Wesentlichen gleichwertig; dieses Ergebnis ist als der Lehrsatz von Codd bekannt. Sie müssen darauf achten, eine Fehlanpassung zu vermeiden, die zwischen den zwei Sprachen entstehen kann, da Ablehnung, die auf eine Formel der Rechnung angewandt ist, eine Formel baut, die auf einem unendlichen Satz von möglichen Tupeln wahr sein kann, während der Unterschied-Maschinenbediener der Verwandtschaftsalgebra immer ein begrenztes Ergebnis zurückgibt. Um diese Schwierigkeiten zu überwinden, hat Codd den operands der Verwandtschaftsalgebra zu begrenzten Beziehungen nur eingeschränkt und hat auch eingeschränkte Unterstützung für die Ablehnung (NICHT) und Trennung vorgeschlagen (ODER). Analoge Beschränkungen werden auf vielen anderen logikbasierten Computersprachen gefunden. Codd hat den Begriff Verwandtschaftsvollständigkeit definiert, um sich auf eine Sprache zu beziehen, die in Bezug auf die Prädikat-Rechnung der ersten Ordnung abgesondert von den Beschränkungen abgeschlossen ist, die er vorgeschlagen hat. In der Praxis haben die Beschränkungen keine nachteilige Wirkung auf die Anwendbarkeit seiner Verwandtschaftsalgebra zu Datenbankzwecken.

Primitive Operationen

Als in jeder Algebra sind einige Maschinenbediener primitiv, und andere werden in Bezug auf die primitiven abgeleitet. Es ist nützlich, wenn die Wahl von primitiven Maschinenbedienern der üblichen Wahl von primitiven logischen Maschinenbedienern anpasst. Obwohl es weithin bekannt ist, dass die übliche Wahl in der Logik UND, ODER und NICHT etwas willkürlich ist, hat Codd eine ähnliche willkürliche Wahl für seine Algebra gemacht.

Fünf primitive Maschinenbediener der Algebra von Codd sind die Auswahl, der Vorsprung, das Kartesianische Produkt (hat auch das Kreuzprodukt oder die böse Verbindungslinie genannt), die Satz-Vereinigung und der Satz-Unterschied. Ein anderer Maschinenbediener, benennen Sie um wurde von Codd nicht bemerkt, aber das Bedürfnis danach wird von den Erfindern von ISBL gezeigt. Diese sechs Maschinenbediener sind im Sinn grundsätzlich, dass, wenn Sie irgendwelche von ihnen weglassen, Sie ausdrucksvolle Macht verlieren werden. Viele andere Maschinenbediener sind in Bezug auf diese sechs definiert worden. Unter dem wichtigsten sind Satz-Kreuzung, Abteilung und die natürliche Verbindungslinie. Tatsächlich hat ISBL zwingende Argumente dafür vorgebracht, das Kartesianische Produkt durch die natürliche Verbindungslinie zu ersetzen, deren das Kartesianische Produkt ein degenerierter Fall ist.

Zusammen haben die Maschinenbediener der Verwandtschaftsalgebra identische ausdrucksvolle Macht zu diesem des Gebiets Verwandtschaftsrechnung oder Tupel Verwandtschaftsrechnung. Jedoch, aus den in der Abteilungseinführung gegebenen Gründen, ist Verwandtschaftsalgebra weniger ausdrucksvoll als Prädikat-Rechnung der ersten Ordnung ohne Funktionssymbole. Verwandtschaftsalgebra entspricht einer Teilmenge der Logik der ersten Ordnung, nämlich Klauseln von Horn ohne recursion und Ablehnung.

Satz-Maschinenbediener

Obwohl drei der sechs grundlegenden Maschinenbediener von der Mengenlehre genommen werden, gibt es zusätzliche Einschränkungen, die in ihren Verwandtschaftsalgebra-Kollegen da sind: Für die Satz-Vereinigung und den Satz-Unterschied müssen die zwei beteiligten Beziehungen mit der Vereinigung vereinbar sein — d. h. die zwei Beziehungen müssen denselben Satz von Attributen haben. Weil gesetzte Kreuzung in Bezug auf den Satz-Unterschied definiert werden kann, müssen die zwei an der Satz-Kreuzung beteiligten Beziehungen auch mit der Vereinigung vereinbar sein.

Das Kartesianische Produkt wird verschieden von demjenigen in der Mengenlehre im Sinn definiert, dass, wie man betrachtet, Tupel zu den Zwecken der Operation 'seicht' sind. D. h. das Kartesianische Produkt eines N-Tupels durch eine M Tupel "ließ" den 2-Tupel-in (n + m) - Tupel "glatt machen". In der Mengenlehre ist das Kartesianische Produkt eine Reihe von 2 Tupeln. Mehr formell R × wird S wie folgt definiert:

:R × S = {(r, r..., r, s, s..., s) | (r, r..., r)  R, (s, s..., s)  S }\

Wie das Kartesianische Produkt ist der cardinality des Ergebnisses das Produkt des cardinalities seiner Faktoren, d. h., |R × S = |R × |S. Außerdem, für das Kartesianische zu definierende Produkt, müssen die zwei beteiligten Beziehungen zusammenhanglose Kopfbälle haben — d. h. sie müssen keinen allgemeinen Attribut-Namen haben.

Vorsprung

Ein Vorsprung ist eine unäre Operation schriftlich als, wo eine Reihe von Attribut-Namen ist. Das Ergebnis solchen Vorsprungs wird als der Satz definiert, der erhalten wird, wenn alle Tupel in R auf den Satz eingeschränkt werden.

Das gibt die spezifische Teilmenge von Säulen (Attribute jedes Tupels) an, um wiederbekommen zu werden. Um die Namen und Telefonnummern aus einem Adressbuch zu erhalten, könnte der Vorsprung geschrieben werden. Das Ergebnis dieses Vorsprungs würde eine Beziehung sein, die nur den contactName und die ContactPhoneNumber-Attribute für jeden einzigartigen Zugang in addressBook enthält.

Auswahl (σ)

Eine verallgemeinerte Auswahl ist eine unäre Operation schriftlich als, wo eine Satzformel ist, die aus Atomen, wie erlaubt, in der normalen Auswahl und den logischen Maschinenbedienern (und), (oder) und (Ablehnung) besteht. Diese Auswahl wählt alle jene Tupel in R aus, für den hält.

Um eine Auflistung aller Freunde oder Teilhaber in einem Adressbuch zu erhalten, könnte die Auswahl als geschrieben werden. Das Ergebnis würde eine Beziehung sein, die jedes Attribut jeder einzigartigen Aufzeichnung enthält, wo isFriend wahr ist, oder wo isBusinessContact wahr ist.

Benennen Sie um (ρ)

Ein Umbenennen ist eine unäre Operation schriftlich als, wo das Ergebnis zu R identisch ist, außer dass das B-Attribut in allen Tupeln zu ein Attribut umbenannt wird. Das wird einfach verwendet, um das Attribut einer Beziehung oder der Beziehung selbst umzubenennen.

Um das 'IsFriend'-Attribut zu 'isBusinessContact' in einer Beziehung umzubenennen, könnte verwendet werden.

Schließt sich an und einer Verbindungslinie ähnliche Maschinenbediener

Natürliche Verbindungslinien sind ein binärer Maschinenbediener, der als geschrieben wird (R S), wo R und S Beziehungen sind. Das Ergebnis der natürlichen Verbindungslinie ist der Satz aller Kombinationen von Tupeln in R und S, die auf ihren allgemeinen Attribut-Namen gleich sind. Weil ein Beispiel den Tabellenangestellten und die Abteilung und ihre natürliche Verbindungslinie denkt:

||

||

| }\

Das kann auch verwendet werden, um Zusammensetzung von Beziehungen zu definieren. Zum Beispiel ist die Zusammensetzung des Angestellten und der Abteilung ihre Verbindungslinie, wie gezeigt, oben, geplant auf allen außer dem allgemeinen Attribut DeptName. In der Kategorie-Theorie ist die Verbindungslinie genau das Faser-Produkt.

Die natürliche Verbindungslinie ist wohl einer der wichtigsten Maschinenbediener, da es die Verwandtschaftskopie von logischen ist UND. Bemerken Sie sorgfältig, dass, wenn dieselbe Variable in jedem von zwei Prädikaten erscheint, die durch UND dann verbunden werden, diese Variable für dasselbe Ding eintritt und beider Anschein immer durch denselben Wert eingesetzt werden muss. Insbesondere natürliche Verbindungslinie erlaubt die Kombination von Beziehungen, die durch einen Auslandsschlüssel vereinigt werden. Zum Beispiel im obengenannten Beispiel hält ein Auslandsschlüssel wahrscheinlich vom Angestellten. DeptName zur Abteilung DeptName und dann die natürliche Verbindungslinie des Angestellten und der Abteilung verbindet alle Angestellten mit ihren Abteilungen. Bemerken Sie, dass das arbeitet, weil der Auslandsschlüssel zwischen Attributen mit demselben Namen hält. Wenn das nicht der Fall solcher als im Auslandsschlüssel von Dept.manager bis Angestellten ist. Name dann wir müssen diese Säulen umbenennen, bevor wir die natürliche Verbindungslinie nehmen. Solch eine Verbindungslinie wird manchmal auch einen equijoin genannt (sieh θ-join).

Mehr formell wird die Semantik der natürlichen Verbindungslinie wie folgt definiert:

:

wo Spaß ein Prädikat ist, das für eine Beziehung r wahr ist, wenn, und nur wenn r eine Funktion ist. Es ist gewöhnlich erforderlich, dass R und S mindestens ein allgemeines Attribut haben müssen, aber wenn diese Einschränkung weggelassen wird, und R und S keine allgemeinen Attribute haben, dann wird die natürliche Verbindungslinie genau das Kartesianische Produkt.

Die natürliche Verbindungslinie kann mit den Primitiven von Codd wie folgt vorgetäuscht werden. Nehmen Sie an, dass c..., c die für R üblichen Attribut-Namen sind und S, r..., r der sind

schreiben Sie zu nennt einzigartig zu R, und s..., sind s der

schreiben Sie einzigartig zu S zu. Nehmen Sie außerdem an, dass das Attribut x nennt..., sind x weder in R noch in S. In einem ersten Schritt können wir jetzt die allgemeinen Attribut-Namen in S umbenennen:

:

Dann nehmen wir das Kartesianische Produkt und wählen die Tupel aus, die angeschlossen werden sollen:

:

Schließlich nehmen wir einen Vorsprung, um die umbenannten Attribute loszuwerden:

:

θ-join und equijoin

Denken Sie Tabellenauto und Boot, die Modelle von Autos und Booten und ihren jeweiligen Preisen verzeichnen. Nehmen Sie an, dass ein Kunde ein Auto und ein Boot kaufen will, aber sie will mehr Geld für das Boot nicht ausgeben als für das Auto. Der θ-join auf der Beziehung CarPrice  BoatPrice erzeugt einen Tisch mit allen möglichen Optionen. Wenn Sie eine Bedingung verwenden, wo die Attribute der ähnliche Preis gleich sind, kann die Bedingung als Price=Price angegeben werden

oder wechselweise (Preis) selbst.

||||| }\

Wenn wir Tupel von zwei Beziehungen verbinden wollen, wo die Kombinationsbedingung nicht einfach die Gleichheit von geteilten Attributen dann ist, ist es günstig, eine allgemeinere Form des Verbindungslinie-Maschinenbedieners zu haben, der der θ-join ist (oder schließen Sie sich theta-an). Der θ-join ist ein binärer Maschinenbediener, der als geschrieben wird, oder wo a und b Attribut-Namen sind, ist θ eine binäre Beziehung im Satz {< , =, > } ist v ein Wert unveränderlich, und R, und S sind Beziehungen. Das Ergebnis dieser Operation besteht aus allen Kombinationen von Tupeln in R und S, die die Beziehung θ befriedigen. Das Ergebnis des θ-join wird nur definiert, wenn die Kopfbälle von S und R zusammenhanglos sind, d. h. enthalten Sie kein allgemeines Attribut.

Die Simulation dieser Operation in den grundsätzlichen Operationen ist deshalb wie folgt:

: R S = σ (R × S)

Im Falle dass der Maschinenbediener θ der Gleichheitsmaschinenbediener ist (=) dann wird diese Verbindungslinie auch einen equijoin genannt.

Bemerken Sie jedoch, dass eine Computersprache, die die natürliche Verbindungslinie unterstützt und Maschinenbediener umbenennt, θ-join ebenso nicht braucht, weil das durch die Auswahl vom Ergebnis einer natürlichen Verbindungslinie erreicht werden kann (der zum Kartesianischen Produkt degeneriert, wenn es keine geteilten Attribute gibt).

() ()

Die Verlasse-Halbverbindungslinie schließt sich ähnlich der natürlichen Verbindungslinie und schriftlich als R an

S, wo R und S Beziehungen sind. Das Ergebnis dieser Halbverbindungslinie ist der Satz aller Tupel in R, für den es ein Tupel in S gibt, der auf ihren allgemeinen Attribut-Namen gleich ist. Weil ein Beispiel den Tabellenangestellten und die Abteilung und ihren denkt

Halbverbindungslinie:

||||| }\

Mehr formell wird die Semantik der Halbverbindungslinie als definiert

folgt:

: R S = {t: t R, s S, Spaß (t s) }\

wo Fun(r) als in der Definition der natürlichen Verbindungslinie ist.

Die Halbverbindungslinie kann mit der natürlichen Verbindungslinie als vorgetäuscht werden

folgt. Wenn a... des zu sein

Attribut-Namen von R, dann

: R S = (R S).

Da wir die natürliche Verbindungslinie mit den grundlegenden Maschinenbedienern vortäuschen können, hieraus folgt dass das auch für die Halbverbindungslinie hält.

()

Die Antiverbindungslinie, schriftlich als R S, wo R und S Beziehungen sind, ist der natürlichen Verbindungslinie ähnlich, aber das Ergebnis einer Antiverbindungslinie ist nur jene Tupel in R, für den es kein Tupel in S gibt, der auf ihren allgemeinen Attribut-Namen gleich ist.

Weil ein Beispiel den Tabellenangestellten und die Abteilung und ihren denkt

schließen Sie sich antian:

||||| }\

Die Antiverbindungslinie wird wie folgt formell definiert:

: R S = {t: t R s S: Spaß (t s) }\

oder

: R S = {t: t R gibt es kein Tupel s S, der Spaß (t s) }\befriedigt

wo Fun(r) als in der Definition der natürlichen Verbindungslinie ist.

Die Antiverbindungslinie kann auch als die Ergänzung der Halbverbindungslinie wie folgt definiert werden:

: R S = R − R S

In Anbetracht dessen wird die Antiverbindungslinie manchmal die Antihalbverbindungslinie genannt, und der Antiverbindungslinie-Maschinenbediener wird manchmal geschrieben, wie sich Symbol mit einer Bar darüber, statt halbanschließen.

(÷)

Die Abteilung ist eine binäre Operation, die als R ÷ S geschrieben wird. Das Ergebnis besteht aus den Beschränkungen von Tupeln in R zu den Attribut-Namen, die zu R, d. h., im Kopfball von R, aber nicht im Kopfball von S einzigartig sind, für den es meint, dass alle ihre Kombinationen mit Tupeln in S in R da sind. Weil ein Beispiel die Tische Vollendet, sieht

DBProject und ihre Abteilung:

||||| }\

Wenn DBProject alle Aufgaben der Datenbank enthält

Projekt dann enthält das Ergebnis der Abteilung oben genau

die Studenten, die beide der Aufgaben im Datenbankprojekt vollendet haben.

Mehr formell wird die Semantik der Abteilung wie folgt definiert:

: R ÷ S = {t [a...,]: t R s S ((t [a...,] s) R) }\

wo {a...,} der Satz von ist

schreiben Sie zu nennt einzigartig zu R und

t [a...,] ist die Beschränkung von

t zu diesem Satz. Es ist gewöhnlich erforderlich, dass das Attribut nennt

im Kopfball von S sind eine Teilmenge von denjenigen von R weil

sonst wird das Ergebnis der Operation immer leer sein.

Die Simulation der Abteilung mit den grundlegenden Operationen ist als

folgt. Wir nehmen dass a an... zu sein

das Attribut nennt einzigartig zu R und

b..., sind b die Attribut-Namen von

S. Im ersten Schritt wir Projekt R über sein einzigartiges Attribut

Namen und Konstruktion alle Kombinationen mit Tupeln in S:

: T: = π (R) × S

Im vorherigen Beispiel würde T einen solchen Tisch vertreten, dass jeder Student (weil Student der einzigartige Schlüssel / Attribut des Vollendeten Tisches ist) mit jeder gegebenen Aufgabe verbunden wird. So würde Eugene zum Beispiel zwei Reihen, Eugene-> Database1 und Eugene-> Database2 in T haben.

Im nächsten Schritt ziehen wir R von diesem ab

Beziehung:

: U: = T − R

Bemerken Sie, dass in U wir den möglichen haben

Kombinationen, die "in R" gewesen sein könnten, aber nicht waren. So, wenn

wir nehmen jetzt den Vorsprung auf den Attribut-Namen, die zu R einzigartig

sind

dann haben wir die Beschränkungen der Tupel in R für der nicht

alle Kombinationen mit Tupeln in S sind in R da gewesen:

: V: = π (U)

So, was getan werden muss, ist nehmen den Vorsprung von R auf seinem

einzigartige Attribut-Namen und ziehen diejenigen in V ab:

: W: = π (R) − V

Äußere Verknüpfungen

Wohingegen das Ergebnis einer Verbindungslinie (oder innere Verknüpfung) aus gebildeten Tupeln durch das Kombinieren des Zusammenbringens von Tupeln in den zwei operands besteht, enthält eine äußere Verknüpfung jene Tupel, und zusätzlich "füllen" einige gebildete Tupel durch das Verlängern eines unvergleichlichen Tupels in einem der operands dadurch Werte für jedes der Attribute des anderen operand.

Die in dieser Abteilung definierten Maschinenbediener nehmen die Existenz eines ungültigen Werts, ω an, den wir nicht definieren, um für die füllen Werte verwendet zu werden. Es sollte nicht angenommen werden, dass das die NULL ist, die für die Datenbanksprache SQL definiert ist, noch es angenommen werden sollte, dass ω ein Zeichen aber nicht ein Wert ist, noch es angenommen werden sollte, dass die umstrittene drei geschätzte Logik dadurch eingeführt wird.

Drei Maschinenbediener der äußeren Verknüpfung werden definiert: verlassene äußere Verknüpfung, richtige äußere Verknüpfung und volle äußere Verknüpfung. (Das "Außen-" Wort wird manchmal weggelassen.)

()

Die linke äußere Verknüpfung wird als R  S geschrieben, wo R und S Beziehungen sind. Das Ergebnis der linken äußeren Verknüpfung ist der Satz aller Kombinationen von Tupeln in R und S, die auf ihren allgemeinen Attribut-Namen, außerdem gleich sind (lose sprechend) zu Tupeln in R, die keine zusammenpassenden Tupel in S haben.

Weil ein Beispiel den Tabellenangestellten und die Abteilung und ihre linke äußere Verknüpfung denkt:

||||| }\

In der resultierenden Beziehung nehmen Tupel in S, die keine allgemeinen Werte in allgemeinen Attribut-Namen mit Tupeln in R haben, einen ungültigen Wert, ω.

Da es keine Tupel in der Abteilung mit DeptName der Finanz oder des Managers gibt, kommen ωs in der resultierenden Beziehung vor, wo Tupel in DeptName Tupel der Finanz oder des Managers haben.

Lassen Sie r, r..., r die Attribute der Beziehung R sein und {(ω..., ω)} zu lassen, der Singleton zu sein

die Beziehung auf den Attributen, die zur Beziehung S einzigartig sind (diejenigen, die nicht Attribute von R sind). Dann kann die linke äußere Verknüpfung in Bezug auf die natürliche Verbindungslinie (und folglich das Verwenden grundlegender Maschinenbediener) wie folgt beschrieben werden:

:

()

Die richtige äußere Verknüpfung benimmt sich fast identisch zur linken äußeren Verknüpfung, aber die Rollen der Tische werden geschaltet.

Die richtige äußere Verknüpfung von Beziehungen R und S wird als R  S geschrieben. Das Ergebnis der richtigen äußeren Verknüpfung ist der Satz aller Kombinationen von Tupeln in R und S, die auf ihren allgemeinen Attribut-Namen zusätzlich zu Tupeln in S gleich sind, die keine zusammenpassenden Tupel in R haben.

Denken Sie zum Beispiel den Tabellenangestellten und die Abteilung und ihren

richtige äußere Verknüpfung:

||||| }\

In der resultierenden Beziehung nehmen Tupel in R, die keine allgemeinen Werte in allgemeinen Attribut-Namen mit Tupeln in S haben, einen ungültigen Wert, ω.

Da es keine Tupel im Angestellten mit DeptName der Produktion gibt, kommen ωs im Namenattribut der resultierenden Beziehung vor, wo Tupel in DeptName Tupel der Produktion hatten.

Lassen Sie s, s..., s die Attribute der Beziehung S sein und {(ω..., ω)} zu lassen, der Singleton zu sein

die Beziehung auf den Attributen, die zur Beziehung R einzigartig sind (diejenigen, die nicht Attribute von S sind). Dann, als mit der linken äußeren Verknüpfung, kann die richtige äußere Verknüpfung mit der natürlichen Verbindungslinie wie folgt vorgetäuscht werden:

:

()

Die äußere Verknüpfung oder volle äußere Verknüpfung verbinden tatsächlich die Ergebnisse des verlassenen und der richtigen äußeren Verknüpfungen.

Die volle äußere Verknüpfung wird als R  S geschrieben, wo R und S Beziehungen sind. Das Ergebnis der vollen äußeren Verknüpfung ist der Satz aller Kombinationen von Tupeln in R und S, die auf ihren allgemeinen Attribut-Namen zusätzlich zu Tupeln in S gleich sind, die keine zusammenpassenden Tupel in R und Tupel in R haben, die keine zusammenpassenden Tupel in S in ihren allgemeinen Attribut-Namen haben.

Weil ein Beispiel den Tabellenangestellten und die Abteilung und ihren denkt

volle äußere Verknüpfung:

||||| }\

In der resultierenden Beziehung nehmen Tupel in R, die keine allgemeinen Werte in allgemeinen Attribut-Namen mit Tupeln in S haben, einen ungültigen Wert, ω. Tupel in S, die keine allgemeinen Werte in allgemeinen Attribut-Namen mit Tupeln in R auch haben, nehmen einen ungültigen Wert, ω.

Die volle äußere Verknüpfung kann mit dem verlassenen und den richtigen äußeren Verknüpfungen (und folglich die natürliche Verbindungslinie und Satz-Vereinigung) wie folgt vorgetäuscht werden:

:R  S = (R  S) (R  S)

Operationen wegen der Bereichsberechnung

Ansammlung

Es gibt fünf gesamte Funktionen, die mit den meisten Datenbanken eingeschlossen werden. Diese Operationen sind Summe, Graf, Durchschnitt, Maximum und Minimum. In der Verwandtschaftsalgebra die Ansammlungsoperation über ein Diagramm (A, A... A) wird wie folgt geschrieben:

G, G..., G f ('), f (')..., f (') (r)

wo jeder', 1  j  k, eines der ursprünglichen Attribute A, 1  i  n ist.

Die Attribute, die vorangehen, gruppieren Attribute, die wie eine "Gruppe durch die" Klausel in SQL fungieren. Dann gibt es eine beliebige Zahl von auf individuelle Attribute angewandten Ansammlungsfunktionen. Die Operation wird auf eine willkürliche Beziehung r angewandt. Die sich gruppierenden Attribute sind fakultativ, und wenn sie nicht geliefert werden, werden die Ansammlungsfunktionen über die komplette Beziehung angewandt, auf die die Operation angewandt wird.

Wollen wir annehmen, dass wir einen Tisch genannt die Rechnung mit drei Säulen, nämlich Account_Number, Branch_Name und Gleichgewicht haben. Wir möchten das maximale Gleichgewicht jedes Zweigs finden. Das wird durch G (Rechnung) vollbracht. Um das höchste Gleichgewicht aller Rechnungen unabhängig vom Zweig zu finden, konnten wir einfach G (Rechnung) schreiben.

Die erweitern Operation

Die erweitern Operation wird für geschätzte Attribute verwendet. Zum Beispiel, wenn Sie ein Attribut haben, das den Preis von einem Artikel und einem anderen Attribut enthält, das die Menge dieses Artikels enthält, können Sie ein geschätztes Attribut bilden: STRECKEN SIE SICH (Preis * Menge) ALS Total_Price AUS.

Beschränkung der Verwandtschaftsalgebra

Obwohl Verwandtschaftsalgebra stark genug zu den meisten praktischen Zwecken scheint, gibt es einige einfache und natürliche Maschinenbediener auf Beziehungen, die durch die Verwandtschaftsalgebra nicht ausgedrückt werden können. Einer von ihnen ist transitiver Verschluss einer binären Beziehung. In Anbetracht eines Gebiets D, lassen Sie binäre Beziehung R eine Teilmenge von DxD sein. Der transitive Verschluss R R ist die kleinste Teilmenge von DxD, der R der satifies die folgende Bedingung enthält:

:x y z ((x, y) R (y, z) R (x, z) R)

Es gibt keinen Verwandtschaftsalgebra-Ausdruck E(R), der R als ein variables Argument nimmt, das R erzeugt. Das kann verwendend der Tatsache bewiesen werden, dass, in Anbetracht eines Vergleichsausdrucks E, für den er gefordert wird, dass E(R) = R, wo R eine Variable ist, wir immer ein Beispiel r R (und ein entsprechendes Gebiet d) solch dass E(r)  r finden können.

Gebrauch von algebraischen Eigenschaften für die Anfragenoptimierung

Abfragen können als ein Baum, wo vertreten werden

• die inneren Knoten sind Maschinenbediener,
• Blätter sind Beziehungen,
• Subbäume sind Subausdrücke.

Unsere primäre Absicht ist, Ausdruck-Bäume in gleichwertige Ausdruck-Bäume umzugestalten, wo die durchschnittliche Größe der Beziehungen, die durch Subausdrücke im Baum nachgegeben sind, kleiner ist, als sie vor der Optimierung waren. Unsere sekundäre Absicht ist zu versuchen, allgemeine Subausdrücke innerhalb einer einzelnen Abfrage zu bilden, oder wenn es mehr als eine Abfragen gibt, die zur gleichen Zeit in allen jenen Abfragen bewerten werden. Das Grundprinzip, hinter dem die zweite Absicht darin besteht, dass es genug ist, allgemeine Subausdrücke einmal, und die Ergebnisse zu schätzen, kann in allen Abfragen verwendet werden, die diesen Subausdruck enthalten.

Hier präsentieren wir eine Reihe von Regeln, die in solchen Transformationen verwendet werden können.

Auswahl

Regeln über Auswahl-Maschinenbediener spielen die wichtigste Rolle in der Anfragenoptimierung. Auswahl ist ein Maschinenbediener, der sehr effektiv die Anzahl gegen Reihen in seinem operand so reduziert, wenn wir schaffen, die Auswahlen in einem Ausdruck-Baum zu den Blättern zu bewegen, werden die inneren Beziehungen (nachgegeben durch Subausdrücke) wahrscheinlich zurückweichen.

Grundlegende Auswahl-Eigenschaften

Auswahl ist idempotent (vielfache Anwendungen derselben Auswahl haben keine zusätzliche Wirkung außer der ersten), und auswechselbar (werden die Ordnungsauswahlen darin angewandt hat keine Wirkung auf das schließliche Ergebnis).

Auswahlen mit komplizierten Bedingungen zerbrechend

Eine Auswahl, deren Bedingung eine Verbindung von einfacheren Bedingungen ist, ist zu einer Folge von Auswahlen mit jenen denselben individuellen Bedingungen gleichwertig, und Auswahl, deren Bedingung eine Trennung ist, ist zu einer Vereinigung von Auswahlen gleichwertig. Diese Identität kann verwendet werden, um Auswahlen zu verschmelzen, so dass weniger Auswahlen bewertet werden müssen, oder sie zu spalten, so dass die Teilauswahlen bewegt oder getrennt optimiert werden können.

Auswahl und Kreuzprodukt

Kreuzprodukt ist der kostspieligste Maschinenbediener, um zu bewerten. Wenn die Eingangsbeziehungen N und M Reihen haben, wird das Ergebnis Reihen enthalten. Deshalb ist es sehr wichtig, unser Bestes zu tun, die Größe von beiden operands vor der Verwendung des Kreuzprodukt-Maschinenbedieners zu vermindern.

Das kann effektiv getan werden, wenn dem Kreuzprodukt von einem Auswahl-Maschinenbediener, z.B (R × P) gefolgt wird. Die Definition der Verbindungslinie denkend, ist das der wahrscheinlichste Fall. Wenn dem Kreuzprodukt von einem Auswahl-Maschinenbediener nicht gefolgt wird, können wir versuchen, unten eine Auswahl von höheren Niveaus des Ausdruck-Baums mit den anderen Auswahlregeln zu stoßen.

Im obengenannten Fall zerbrechen wir Bedingung in Bedingungen B, C und D das Verwenden der Spalt-Regeln über komplizierte Auswahl-Bedingungen, so dass = B C D und B nur Attribute von R enthält, enthält C Attribute nur von P, und D enthält den Teil, der Attribute sowohl von R als auch von P enthält. Bemerken Sie, dass B, C oder D vielleicht leer sind. Dann hält der folgende:

:

Auswahl und Satz-Maschinenbediener

Auswahl ist über den setminus, die Kreuzung und die Vereinigungsmaschinenbediener verteilend. Die folgenden drei Regeln werden verwendet, um Auswahl unter Satz-Operationen im Ausdruck-Baum zu stoßen. Bemerken Sie, dass im setminus und den Kreuzungsmaschinenbedienern es möglich ist, den Auswahl-Maschinenbediener auf nur einen der operands nach der Transformation anzuwenden. Das kann Sinn in Fällen haben, wo einer der operands klein ist, und die Gemeinkosten, den Auswahl-Maschinenbediener zu bewerten, die Vorteile überwiegen, eine kleinere Beziehung als ein operand zu verwenden.

Auswahl und Vorsprung

Auswahl ist mit dem Vorsprung assoziativ, wenn, und nur wenn die in der Auswahl-Bedingung Verweise angebrachten Felder eine Teilmenge der Felder im Vorsprung sind. Wenn er Auswahl bevor durchführt, kann Vorsprung nützlich sein, wenn der operand ein Kreuzprodukt ist oder sich anschließen. In anderen Fällen, wenn die Auswahl-Bedingung relativ teuer ist, um zu rechnen, kann die bewegende Auswahl außerhalb des Vorsprungs die Anzahl von Tupeln vermindern, die geprüft werden müssen (da Vorsprung weniger Tupel wegen der Beseitigung von Duplikaten erzeugen kann, die sich aus elidierten Feldern ergeben).

:

Vorsprung

Grundlegende Vorsprung-Eigenschaften

Vorsprung ist idempotent, so dass eine Reihe von (gültigen) Vorsprüngen zum äußersten Vorsprung gleichwertig ist.

:

Vorsprung und Satz-Maschinenbediener

Vorsprung ist über die Satz-Vereinigung verteilend.

:

Vorsprung verteilt über die Kreuzung nicht und Unterschied setzen. Durch Gegenbeispiele wird gegeben:

::

und

::

wo, wie man annimmt, b von b verschieden ist.

Umbenennen

Grundlegend benennen Eigenschaften um

Aufeinander folgend benennt von einer Variable um kann in eine Single zusammengebrochen werden benennen um. Benennen Sie Operationen um, die keine Variablen haben, gemeinsam kann in Bezug auf einander willkürlich wiederbestellt werden, der ausgenutzt werden kann, um aufeinander folgend zu machen, benennt angrenzend um, so dass sie zusammengebrochen werden können.

Benennen Sie um und setzen Sie Maschinenbediener

Benennen Sie um ist über den Satz-Unterschied, die Vereinigung und die Kreuzung verteilend.

Durchführungen

Die erste Anfragensprache, um auf der Algebra von Codd zu basieren, war ISBL, und diese Pionierarbeit ist von vielen Behörden als gezeigt die Weise mit Jubel begrüßt worden, die Idee von Codd in eine nützliche Sprache zu machen. Geschäftssystem 12 war eine kurzlebige Industriekraft Verwandtschafts-DBMS, der dem ISBL Beispiel gefolgt ist.

1998 haben Chris Date und Hugh Darwen eine Sprache genannt Tutorial D vorgeschlagen, der für den Gebrauch im Unterrichten der Verwandtschaftsdatenbanktheorie beabsichtigt ist, und seine Anfragensprache stützt sich auch auf die Ideen von ISBL. Rel ist eine Durchführung von Tutorial D.

Sogar die Anfragensprache von SQL basiert lose auf einer Verwandtschaftsalgebra, obwohl die operands in SQL (Tische) nicht genau sind, halten Beziehungen und mehrere nützliche Lehrsätze über die Verwandtschaftsalgebra in der SQL Kopie (wohl zum Nachteil von optimisers und/oder Benutzern) nicht.

Siehe auch

• Kartesianisches Produkt
• Datenbank
• Logik von Verwandten
• Gegenstand-Rolle, modellierend
• Beziehung (Datenbank)
• Vorsprung (Mathematik)
• Vorsprung (Verwandtschaftsalgebra)
• Vorsprung (Mengenlehre)
• Beziehung
• Beziehungsalgebra
• Verwandtschaftsrechnung
• Beziehungsaufbau
• Beziehungszusammensetzung
• Die Beziehungsverminderung
• Verwandtschaftsdatenbank
• Verwandtschaftsmodell
• Theorie von Beziehungen
• Triadische Beziehung
• Tutorenkurs D
• D (Datensprachspezifizierung)
• D4 (Programmiersprache) (eine Durchführung von D)

Außenverbindungen

• RATTE. Software Verwandtschaftsalgebra-Übersetzer zu SQL
• Vortrag-Zeichen: Verwandtschaftsalgebra - Ein schneller Tutorenkurs, um SQL-Abfragen in die Verwandtschaftsalgebra anzupassen
• SPRUNG - Eine Durchführung der Verwandtschaftsalgebra
• Verwandtschafts-Eine grafische Durchführung der Verwandtschaftsalgebra
• Anfragenoptimierung ist Dieses Papier eine Einführung in den Gebrauch der Verwandtschaftsalgebra in der Optimierung von Abfragen, und schließt zahlreiche Zitate für mehr eingehende Studie ein.
• bandilab.org - ordentliche grafische Illustrationen der Vergleichsoperatoren
• Verwandtschaftsalgebra-System für das Orakel und Microsoft SQL Server