L'opération «différence» ajoute-t-elle de l'expressivité à un langage de requête qui inclut déjà la «jointure»?

19

L'opérateur de différence définie (par exemple, EXCEPTdans certaines variantes SQL) est l'un des nombreux opérateurs fondamentaux de l'algèbre relationnelle. Cependant, certaines bases de données ne prennent pas directement en charge l'opérateur de différence d'ensemble, mais prennent en charge LEFT JOIN(une sorte de jointure externe), et en pratique, cela peut être utilisé à la place d'une opération de différence d'ensemble pour obtenir le même effet.

Cela signifie-t-il que la puissance expressive d'un langage de requête est la même même sans l'opérateur de différence définie, tant que l' LEFT JOINopérateur est maintenu? Comment prouverait-on ce fait?

Ken Li
la source
1
Pour montrer qu'ils ont la même puissance expressive, cela montre que l'opération de différence peut être construite avec l'opération de jointure gauche (et éventuellement d'autres opérations dans RA).
sxd

Réponses:

14

Dans l'algèbre relationnelle, nous fournirons d'abord une définition informelle de la jointure gauche (externe), et continuerons à prouver que le renommage, la sélection, la jointure et la projection peuvent construire la différence, ainsi que cette différence, la sélection et l'union peuvent être utilisées pour construire jointure externe gauche. En fait, nous finirons par le faire dans l'ordre inverse: nous montrerons comment construire des jointures gauches en utilisant des différences, puis nous montrerons comment construire des différences en utilisant des jointures gauches.

Soit et des schémas et , respectivement, où et sont les ensembles d'attributs dans un schéma mais pas l'autre, et est l'ensemble d'attributs communs.S ( R , T ) ( T , S ) R S TRS(R,T)(T,S)RST

Soit le tuple nul pour le schéma . C'est-à-dire qu'il s'agit du tuple composé de toutes les valeurs nulles pour chaque attribut de . Ensuite, nous définissons la jointure externe gauche comme suit: est l'ensemble de tous les tuples appartenant au schéma où ...S ' S ' ( r , t , s ) ( R ' , T , S ' )w=(ϵ,ϵ,...,ϵ)SSR LEFT JOIN S(r,t,s)(R,T,S)

  1. R(r,t) est un tuple dans ;R
  2. (a) est un tuple de ou (b) ;S s = w(t,s)Ss=w
  3. Si est dans l'ensemble pour , alors n'est pas dans l'ensemble.s w ( r , t , w )(r,t,s)sw(r,t,w)

Exemple: le schéma de est , le schéma de est , et nous l'avons et . Par (1) et (2) on obtient le résultat intermédiaire . Par (3), nous devons supprimer , car nous avons (par exemple) et . Il nous reste donc , le résultat attendu pour une jointure gauche.RS ( A 2 , A 3 , A 4 ) R = { ( 1 , 2 , 3 ) , ( 4 , 5 , 6 ) } S = { ( 2 , 3 , 4 ) , ( 2 , 3 , 6 ) } {(A1,A2,A3)S(A2,A3,A4)R={(1,2,3),(4,5,6)}S={(2,3,4),(2,3,6)}( 1 , 2 , 3 , ϵ ) ( 1 , 2 , 3 , 4 ) s = 4{(1,2,3,4),(1,2,3,6),(1,2,3,ϵ),(4,5,6,ϵ)}(1,2,3,ϵ)(1,2,3,4){ ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 4 , 5 , 6 , ϵ ) }s=4ϵ=w{(1,2,3,4),(1,2,3,6),(4,5,6,ϵ)}

Théorème: R LEFT JOIN Sest équivalent à (R EQUIJOIN S) UNION ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w).

Preuve: (R EQUIJOIN S)nous donne tout ce qui est requis par (1) et (2a). Nous prétendons que cela ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)nous donne tout de la forme (r, t, w)requise par (2b) et (3).

Pour le voir, premier avis qui (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R)est l'ensemble de toutes les lignes en pour lesquels il n'y a pas tuple correspondant dans . Pour voir cela, il suffit de noter qu'en projetant les attributs communs de et (l'ensemble d'attributs ) et en prenant la différence, on se retrouve avec tous et seulement les tuples (avec le schéma ) qui sont représentés dans mais pas . Par le avec , nous récupérons tous et seulement les tuples dans qui ont des valeurs pour les attributs dans qui sont présents dans mais pas dansS R S T T R S R R T R SRSRSTTRSEQUIJOINRRTRS; à savoir, précisément l'ensemble de tuples que nous avons jusqu'à présent revendiqué.

Ensuite, notez que le schéma de (((PROJECT_T R) DIFFERENCE (PROJECT_T S))est le même que celui de (à savoir, ), tandis que le schéma de est . L' opération est donc un produit cartésien, nous nous obtenons toutes les lignes de la forme où il n'y a pas en correspondant à dans .( R , T ) w S ( r , t , w ) ( t , s ) S ( r , t ) RR(R,T)wSJOIN(r,t,w)(t,s)S(r,t)R

Pour voir que c'est précisément l'ensemble de tuples que nous devions ajouter pour R EQUIJOIN Sconstruire R LEFT JOIN S, considérons ce qui suit: par construction, (3) est satisfait, car R EQUIJOIN Sne peut pas contenir si contient (si c'était le cas, alors la deuxième partie contenant serait une contradiction); si nous devions ajouter un autre pas dedans, alors il y aurait un dans correspondant à dans , et par la définition de , serait également en contradiction avec (3). Ceci complète la preuve.( r , t , w ) ( r , t , w ) ( r , t , w ) ( t , s ) S ( r , t ) R ( r , t , s )(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)(t,s)S(r,t)REQUIJOIN(r,t,s)R LEFT JOIN S

Nous montrons maintenant que la jointure gauche peut être utilisée pour construire la différence:

Théorème: R DIFFERENCE Sest équivalent àPROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))

Preuve: notez qu'ici, et sont vides, car tous les attributs sont partagés pour avoir du sens. Tout d'abord, nous créons une nouvelle relation à partir de en dupliquant l'ensemble d'attributs dans (géré par et ) afin qu'il se compose de tuples sur l'ensemble d'attributs où (géré par le ). La jointure gauche nous laisse avec des tuples de la forme où ou . Maintenant, pour se débarrasser des entrées qui apparaissent également en , il ne faut garder que les tuples du formulaireS RSDIFFERENCES ( t , t ) ( T , T ) t = t ( t , t ) t = t t = w S ( t , w ) T SSRENAMEJOIN(t,t)(T,T)t=tSELECT(t,t)t=tt=wS(t,w), qui est géré par le plus externe SELECT. Le dernier PROJECTse débarrasse de l'ensemble d'attributs temporaires et nous laisse la différence en termes de schéma d'origine.T

Exemple: Soit et . Nous obtenons d'abord avec l' ensemble d'attributs d : . L' opération nous donne le produit cartésien avec les neuf paires possibles; cet ensemble n'est pas écrit ici pour des raisons de formatage. Le pares alors cela à . Le avec donne . Le donne . Le donneS = { ( 3 , 4 ) , ( 5 , 6 ) , ( 7 , 8 ) } S T { ( 3 , 4 ) , ( 5 , 6 ) , ( 7 ,R={(1,2),(3,4),(5,6)}S={(3,4),(5,6),(7,8)}SRENAMET{ ( 3 , 4 , 3 , 4 ) , ( 5 , 6 , 5 , 6 ) , ( 7 , 8 , 7 , 8 ) } R { ( 1 , 2 , ϵ , ϵ ) , ( 3 , 4 , 3 , 4 ) , ( 5 , 6 ,{(3,4),(5,6),(7,8)}JOINSELECT{(3,4,3,4),(5,6,5,6),(7,8,7,8)}LEFT JOINR{ ( 1 , 2 , ϵ , ϵ ) } { ( 1 , 2 ) }{(1,2,ϵ,ϵ),(3,4,3,4),(5,6,5,6)}SELECT{(1,2,ϵ,ϵ)}PROJECT{(1,2)}, la réponse souhaitée.

Patrick87
la source
Veuillez modifier votre message pour utiliser la syntaxe LaTeX. Commencez par enfermer toutes vos formules dans les symboles $ (par exemple, $ (1,2) $ devient ). Des mots clés comme select doivent être mis dans `(par exemple,` SELECT` devient ). (1,2)SELECT
Raphael
@Raphael Merci d'avoir souligné que je devrais utiliser LaTeX pour cela. J'ai fait une tentative de bonne foi de LaTeX'ing les mathématiques et backtick'ing le code ... s'il vous plaît laissez-moi savoir s'il y a autre chose que je dois faire. Merci encore!
Patrick87
Grand merci! Vous voudrez peut-être considérer $ $ ... $ $ pour créer des éléments mathématiques en retrait (pas en ligne). Cela peut souvent améliorer la lisibilité s'il est utilisé correctement. MathJax prend également en charge les équations numérotées, mais je ne sais pas comment procéder.
Raphael
Je pense que votre logique est défectueuse ici. Vous utilisez DIFFERENCEpour définir LEFT JOIN, puis vous utilisez LEFT JOINpour exprimer DIFFERENCE, concluant que SQL peut s'en passer. Pour que cela soit valide, vous devez exprimer LEFT JOINen termes d'opérateurs autres queDIFFERENCE , puis prouver que cela DIFFERENCEest équivalent.
Janoma
@Janoma Je ne pense pas que ce soit obligatoire ... nous essayons de montrer que la différence peut être exprimée en termes de jointures gauches, donc une jointure gauche fonctionnelle est supposée. Pensez-y: si ce que vous dites avait du mérite, je pourrais affirmer que LEFT JOIN est l'opération "fondamentale" ou "nécessaire", et exiger que vous définissiez la DIFFÉRENCE en fonction des autres opérateurs, mais pas LEFT JOIN. J'ai montré que chacun peut simuler l'autre, donc ni l'un ni l'autre n'est plus ou moins "fondamental" que l'autre ... qu'est-ce qui rend la différence spéciale? En prop. la logique, NON et ET est complète, de même que OU et NON; vous n'avez pas besoin des trois.
Patrick87
-1

LEFT JOIN tel qu'implémenté par SQL, ne produit pas de relations comme résultat (car certains attributs du résultat n'auront pas de valeur).

Ergo, LEFT JOIN tel qu'il est implémenté par SQL, n'est pas l'équivalent direct d'un opérateur d'algèbre relationnelle.

Ergo, L' opérateur de différence relationnelle ne peut pas être exprimé en termes de LEFT JOIN (car LEFT JOIN ne peut pas faire partie de l'algèbre relationnelle, ceci parce que LEFT JOIN produit quelque chose qui n'est pas une relation, violant ainsi la fermeture de l'algèbre).

Tout ensemble d'opérateurs primitifs d'une algèbre relationnelle qui satisfait la fermeture que je connais, inclut toujours soit la différence relationnelle, soit la semi-différence relationnelle.

Erwin Smout
la source