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

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?

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 ′$R$$S$$(R', T)$$(T, S')$$R'$$S'$$T$

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 = (\epsilon, \epsilon, ..., \epsilon)$$S'$$S'$R LEFT JOIN S$(r, t, s)$$(R', T, S')$

1. $(r, t)$ est un tuple dans ;$R$
2. (a) est un tuple de ou (b) ;S s = $(t, s)$$S$$s = w$
3. Si est dans l'ensemble pour , alors n'est pas dans l'ensemble.s ≠ w ( r , t , w $(r, t, s)$$s \neq w$$(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.$R$S ( A 2 , A 3 , A 4 ) R = { ( 1 , 2 , 3 ) , ( 4 , 5 , 6 ) } S = { ( 2 , 3 , 4 ) , ( 2 , 3 , 6 ) } $(A_{1}, A_{2}, A_{3})$$S$$(A_{2}, A_{3}, A_{4})$$R = \{(1, 2, 3), (4, 5, 6)\}$$S = \{(2, 3, 4), (2, 3, 6)\}$( 1 , 2 , 3 , ϵ ) ( 1 , 2 , 3 , 4 ) s = $\{(1, 2, 3, 4),(1, 2, 3, 6), (1, 2, 3, \epsilon),(4, 5, 6, \epsilon)\}$$(1, 2, 3, \epsilon)$$(1, 2, 3, 4)${ ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 4 , 5 , 6 , ϵ ) $s = 4 \neq \epsilon = w$$\{(1, 2, 3, 4), (1, 2, 3, 6), (4, 5, 6, \epsilon)\}$

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 $R$$S$$R$$S$$T$$T$$R$$S$EQUIJOIN$R$$R$$T$$R$$S$; à 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 ) $R$$(R', T)$$w$$S'$JOIN$(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)$$R$EQUIJOIN$(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 $R'$$S'$DIFFERENCES ( t , t ′ ) ( T , T ′ ) t = t ′ ( t , t ′ ) t = t ′ t ′ = w S ( t , w ) T $S$$S$RENAMEJOIN$(t, t')$$(T, T')$$t = t'$SELECT$(t, t')$$t=t'$$t'=w$$S$$(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)\}$$S$RENAME$T'${ ( 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 JOIN$R${ ( 1 , 2 , ϵ , ϵ ) } { ( 1 , 2 ) $\{(1, 2, \epsilon, \epsilon), (3, 4, 3, 4), (5, 6, 5, 6)\}$SELECT$\{(1, 2, \epsilon, \epsilon)\}$PROJECT$\{(1, 2)\}$, la réponse souhaitée.

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.