Verleiht die Operation 'difference' einer Abfragesprache, die bereits 'join' enthält, Ausdruck?

19

Der gesetzte Differenzoperator (z. B. EXCEPTin einigen SQL-Varianten) ist einer der vielen grundlegenden Operatoren der relationalen Algebra. Es gibt jedoch einige Datenbanken, die den Mengenunterschiedsoperator nicht direkt unterstützen, die jedoch LEFT JOIN(eine Art äußere Verknüpfung) unterstützen. In der Praxis kann dies anstelle einer Mengenunterschiedsoperation verwendet werden, um den gleichen Effekt zu erzielen.

Bedeutet dies, dass die Ausdruckskraft einer Abfragesprache auch ohne den eingestellten Differenzoperator dieselbe ist, solange der LEFT JOINOperator beibehalten wird? Wie würde man diese Tatsache beweisen?

Ken Li
quelle
1
Zu zeigen, dass sie dieselbe Ausdruckskraft haben, bedeutet, dass die Differenzoperation mit der Left-Join-Operation (und möglicherweise mit anderen Operationen in RA) konstruiert werden kann.
sxd

Antworten:

14

In der relationalen Algebra werden wir zunächst eine informelle Definition des linken (äußeren) Joins bereitstellen und anschließend nachweisen, dass durch Umbenennen, Auswählen, Verknüpfen und Projizieren Unterschiede konstruiert werden können und dass Unterschiede, Auswahlen und Vereinigungen konstruiert werden können Linke äußere Verbindung. Tatsächlich machen wir das in umgekehrter Reihenfolge: Wir zeigen, wie Links-Joins mithilfe von Differenzen erstellt werden und dann, wie Unterschiede mithilfe von Links-Joins erstellt werden.

Es sei angenommen, dass und S die Schemata ( R ' , T ) bzw. ( T , S ' ) haben, wobei R ' und S ' die Mengen von Attributen in einem Schema sind, aber nicht das andere, und T die Menge von gemeinsamen Attributen ist.RS(R,T)(T,S)RST

Lassen Sie für Schema der Null - Tupel sein S ' . Das heißt, es ist das Tupel, das aus allen Nullwerten für jedes Attribut von S 'besteht . Dann definieren wir die linke äußere Verknüpfung wie folgt: Ist die Menge aller Tupel ( r , t , s ), die zum Schema ( R , T , S ) gehören, wobei ...w=(ϵ,ϵ,...,ϵ)SSR LEFT JOIN S(r,t,s)(R,T,S)

  1. ist ein Tupel in R ;(r,t)R
  2. (a) ist ein Tupel von S oder (b) s = w ;(t,s)Ss=w
  3. Befindet sich in der Menge für s w , dann befindet sich ( r , t , w ) nicht in der Menge.(r,t,s)sw(r,t,w)

Beispiel: Das Schema von ist ( A 1 , A 2 , A 3 ) , das Schema von S ist ( A 2 , A 3 , A 4 ) , und wir haben das R = { ( 1 , 2 , 3 ) , ( 4 , 5 , 6 ) } und S = { ( 2 , 3 , 4 )R(EIN1,EIN2,EIN3)S(EIN2,EIN3,EIN4)R={(1,2,3),(4,5,6)} . Mit (1) und (2) erhalten wir das Zwischenergebnis { ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 1 , 2 , 3 , ϵ ) , ( 4 , 5 , 6 , ϵ ) } . Nach (3) müssen wir ( 1 , 2 entfernenS={(2,3,4),(2,3,6)}{(1,2,3,4),(1,2,3,6),(1,2,3,ϵ),(4,5,6,ϵ)} , da wir (zum Beispiel) ( 1 , 2 , 3 , 4 ) und s = 4 ϵ = w haben . Wir haben also { ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 4 , 5 , 6 , ϵ ) }(1,2,3,ϵ)(1,2,3,4)s=4ϵ=w{(1,2,3,4),(1,2,3,6),(4,5,6,ϵ)}, das erwartete Ergebnis für einen linken Join.

Satz: R LEFT JOIN Sist äquivalent zu (R EQUIJOIN S) UNION ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w).

Beweis: (R EQUIJOIN S)gibt uns alles, was nach (1) und (2a) erforderlich ist. Wir behaupten, dass ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)uns dies alles in der (r, t, w)unter (2b) und (3) geforderten Form gibt .

Um dies zu sehen, beachten Sie zuerst, dass dies (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R)die Menge aller Tupel in für die es in S kein entsprechendes Tupel gibt . Um das zu sehen, genügt die Feststellung, dass durch Projizieren der gemeinsamen Attribute aus R und S (der Attributmenge T ) und Differenzieren alle und nur die Tupel (mit Schema T ) übrig bleiben, die in R aber dargestellt sind nicht S . Durch das mit R gewinnen wir alle und nur die Tupel in R zurück , die Werte für Attribute in T haben, die in R aber nicht in S vorhanden sindRSRSTTRSEQUIJOINRRTRS; nämlich genau die Menge von Tupeln, die wir bisher behauptet haben.

Als nächstes wird bemerkt , dass das Schema (((PROJECT_T R) DIFFERENCE (PROJECT_T S))ist das gleiche wie die von (nämlich ( R ' , T ) ), während das Schema von w ist S ' . Die Operation ist also ein kartesisches Produkt, wir erhalten alle Tupel der Form ( r , t , w ), bei denen es in S kein ( t , s ) gibt , das ( r , t ) in R entspricht .R(R,T)wSJOIN(r,t,w)(t,s)S(r,t)R

Um zu sehen , dass dies genau die Menge von Tupeln wir hinzufügen benötigt R EQUIJOIN Szu konstruieren , um R LEFT JOIN S, Folgendes zu beachten: durch den Bau, (3) erfüllt ist , da R EQUIJOIN Snicht enthält , wenn enthält ( r , t , w ) (wenn ja, dann wäre der zweite Teil, der ( r , t , w ) enthält , ein Widerspruch); wenn wir einen weiteren hinzuzufügen waren ( r , t , w ) nicht in , dann gäbe es ein ((r,t,s)((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)(r,t,w)(r,t,w)(r,t,w)((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w) in S zu entsprechenden ( r , t ) in R , und durch die Definition, ( r , t , s ) wäre auch ineinem Widerspruch von (3). Damit ist der Beweis abgeschlossen.(t,s)S(r,t)REQUIJOIN(r,t,s)R LEFT JOIN S

Nun zeigen wir, dass left join verwendet werden kann, um Unterschiede zu konstruieren:

Satz: R DIFFERENCE Sist äquivalent zuPROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))

Beweis: Beachten Sie, dass hier und S ' leer sind, da alle Attribute geteilt werden , um einen Sinn zu ergeben. Zunächst erstellen wir eine neue Beziehung aus S, indem wir die Attributmenge in S (behandelt von und ) so duplizieren , dass sie aus Tupeln ( t , t ' ) auf der Attributmenge ( T , T ' ) besteht, wobei t = t ' (behandelt von die ). Die linke Verknüpfung lässt uns Tupel der Form ( t , t )RSDIFFERENCESSRENAMEJOIN(t,t)(T,T)t=tSELECT(t,t)wobei oder t ' = w ist . Um Einträge zu entfernen, die auch in S vorkommen , müssen wir nur die Tupel des Formulars ( t , w ) behalten , das vom äußersten behandelt wird . Der letzte entfernt die temporäre Attributmenge T ' und hinterlässt den Unterschied zum ursprünglichen Schema.t=tt=wS(t,w)SELECTPROJECTT

Beispiel: Es sei und S = { ( 3 , 4 ) , ( 5 , 6 ) , ( 7 , 8 ) } . Wir erhalten zuerst S mit der d-Attributmenge T ' : { ( 3 , 4 )R={(1,2),(3,4),(5,6)}S={(3,4),(5,6),(7,8)}SRENAMET . DieOperation gibt uns das kartesische Produkt mit allen neun möglichen Paarungen; Dieser Satz wird hier aus Formatierungsgründen nicht geschrieben. Diedann pares dies auf { ( 3 , 4 , 3 , 4 ) , ( 5 , 6 , 5 , 6 ) , ( 7 , 8 , 7 , 8 ) } . Diemit{(3,4),(5,6),(7,8)}JOINSELECT{(3,4,3,4),(5,6,5,6),(7,8,7,8)}LEFT JOIN ergibt { ( 1 , 2 , ϵ , ϵ ) , ( 3 , 4 , 3 , 4 ) , ( 5 , 6 , 5 , 6 ) } . Dasergibt { ( 1 , 2 , ϵ , ϵ ) } . Dasgibt { ( 1 , 2 ) } die gewünschte Antwort.R{(1,2,ϵ,ϵ),(3,4,3,4),(5,6,5,6)}SELECT{(1,2,ϵ,ϵ)}PROJECT{(1,2)}

Patrick87
quelle
Bearbeiten Sie Ihren Beitrag, um die LaTeX-Syntax zu verwenden. Schließen Sie zunächst alle Ihre Formeln in $ -Symbole ein (zum Beispiel wird $ (1,2) $ zu ). Schlüsselwörter wie select sollten in `eingegeben werden (zum Beispiel wird` SELECT` ). (1,2)SELECT
Raphael
@Raphael Vielen Dank für den Hinweis, dass ich dafür LaTeX verwenden sollte. Ich habe in gutem Glauben versucht, die Mathematik zu testen und den Code zurückzusetzen. Bitte lassen Sie mich wissen, ob ich noch etwas anderes tun sollte. Danke noch einmal!
Patrick87
Vielen Dank! Vielleicht möchten Sie $ $ ... $ $ in Betracht ziehen, um eingerückte (nicht inline) Teile der Mathematik zu erstellen. Dies kann bei korrekter Verwendung häufig die Lesbarkeit verbessern. MathJax unterstützt auch nummerierte Gleichungen, aber ich bin nicht sicher, wie ich das machen soll.
Raphael
Ich denke, deine Logik ist hier fehlerhaft. Sie DIFFERENCEdefinieren LEFT JOINmit und LEFT JOINdrücken dann aus DIFFERENCE, dass SQL darauf verzichten kann. Damit dies gültig ist, sollten Sie andereLEFT JOIN Operatoren alsDIFFERENCE ausdrücken und dann nachweisen, dass dies DIFFERENCEgleichwertig ist.
Janoma
@ Janoma Ich glaube nicht, dass dies erforderlich ist. Wir versuchen zu zeigen, dass der Unterschied in Form von Links-Joins ausgedrückt werden kann. Daher wird ein funktionierender Links-Join angenommen. Denken Sie darüber nach: Wenn das, was Sie sagen, Verdienst hat, könnte ich behaupten, dass LEFT JOIN die "grundlegende" oder "notwendige" Operation ist, und fordern, dass Sie DIFFERENCE in Bezug auf die anderen Operatoren definieren, LEFT JOIN jedoch nicht. Ich habe gezeigt, dass jeder den anderen simulieren kann, also ist keiner mehr oder weniger "grundlegend" als der andere ... was macht den UNTERSCHIED besonders? In Stütze. Logik, NOT und AND sind vollständig, ebenso wie OR und NOT; du brauchst nicht alle drei.
Patrick87
-1

LEFT JOIN, wie von SQL implementiert, erzeugt keine Relationen als Ergebnis (da einige Attribute des Ergebnisses keinen Wert haben).

Ergo, LEFT JOIN wie von SQL implementiert, ist kein direktes Gegenstück zu einem relationalen Algebraoperator.

Ergo, der Vergleichsoperator kann nicht in LEFT JOIN ausgedrückt werden (weil LEFT JOIN möglicherweise nicht Teil der relationalen Algebra sein kann, weil LEFT JOIN etwas produziert, das keine Beziehung ist, und somit das Schließen der Algebra verletzt).

Jede Menge von primitiven Operatoren einer relationalen Algebra , die den mir bekannten Abschluss befriedigt , schließt immer entweder relationale Differenz oder auch relationale Semidifferenz ein.

Erwin Smout
quelle