Différences entre les types de jointures
Bonjour,
J'essaie de comprendre la différence entre plusieurs types de jointures car certaines définitions ne me semblent pas très claires. (Indépendamment des SGBD ou du langage SQL)
1. Définition (mathématique) de la jointure (en général) par rapport à celle de la theta-jointure ?
2. Définition de l'équi-jointure par rapport à celle de la jointure naturelle ?
3. Définition de la jointure externe par rapport à celle de la semi-jointure ?
4. Est-ce qu'on peut dire que la condition de la jointure est un prédicat ?
5. Si on veut faire une hiérarchie en partant de la définition générale d'une jointure jusqu'aux cas particuliers, comment les mettre dans l'ordre ?
Merci.
Théorie relationnelle et jointure
Bonsoir,
Citation:
Envoyé par
SQLpro
les attributs doivent porter le même nom. C'est une stupidité ! Vous pouvez avoir une jointure naturelle sur des attributs ayant un nom non identique.
Excuse-moi Frédéric, mais ça n’est pas une stupidité, puisqu’il s’agit de la théorie relationnelle : si les attributs sur lesquels portent la jointure n’ont pas le même nom (mais sont du même type !), on les renomme à l’aide de l’opérateur RENAME avant d’effectuer la jointure. Maintenant, que SQL permette de noter l’opération différemment, pourquoi pas (notamment à cause du typage), mais la norme SQL n’est pas une théorie.
Je rappelle ici la définition de la jointure dans le cadre de la théorie relationnelle (je fais référence à The Relational Database Dictionary).
Jointure naturelle
1. (Cas dyadique) Soit les relations r1 er r2 où les attributs qui ont le même nom sont du même type. La jointure naturelle de r1 et r2 :
r1 JOIN r2
est une relation dont l’en-tête est l’union (au sens de la théorie des ensembles) des en-têtes de r1 et r2, et dont le corps est l’ensemble des tuples t tels que t est l’union (au sens de la théorie des ensembles) d’un tuple de r1 et d’un tuple de r2.
2. (Cas N-adique) Soit les relations r1, r2, ..., rn (n ≥ 0) où les attributs ayant le même nom sont du même type. La jointure naturelle {r1, r2, ..., rn} est ainsi définie : Si n = 0 le résultat est TABLE_DEE ; si n = 1, le résultat est r1 ; sinon on choisit deux relations distinctes parmi l’ensemble r1, r2, ..., rn et on les remplace par leur jointure naturelle (dyadique) puis on répète le procédé jusqu’à ce que l’ensemble soit constitué d’une seule relation r qui représente le résultat final.
Considérons par exemple les relvars (variables relationnelles) décrivant les fournisseurs (S) et les livraisons de pièces (SP) :
S {S#, SNAME, STATUS, CITY}
SP {S#, P#, QTY}
Où S# représente le numéro d'un fournisseur, SNAME son nom, STATUS son score, CITY sa ville de résidence, P# un numéro de pièce et QTY le nombre de pièces livrées par le fournisseur.
L’expression S JOIN SP représente la jointure naturelle des relations qui sont les valeurs actuelles des relvars S et SP. Cette jointure est une relation de type
RELATION {S#, SNAME, STATUS, CITY, P#, QTY}
Qui plus est, si les valeurs des relvars S et SP sont respectivement s et sp, le corps de cette relation est constitué de tous les tuples de la forme <s#,sn,st,sc,p#,q> tels que le tuple <s#,sn,st,sc> est présent dans s et le tuple <s#,p#,q> présent dans sp.
Thêta-jointure : c'est une opération relationnelle équivalant à une expression de la forme :
(r1 TIMES r2) WHERE A1 thêta A2
Où TIMES représente le produit cartésien, WHERE A1 thêta A2 représente une condition prenant la valeur vrai ou faux, A1 et A2 sont respectivement des attributs (du même type T) de r1 et r2 et thêta est un opérateur de comparaison (« = », « > », « ≥ », etc.) utilisable pour les valeurs du type T.
Équi-jointure : une thêta-jointure où thêta est « = ».
Semi-jointure : Soit les relations r1 et r2. La semi-jointure de r1 et r2 (dans cet ordre) est notée :
r1 MATCHING r2
Et représente un raccourci pour (r1 JOIN r2){X}, où {X} représente l’en-tête de r1 (c’est donc la projection sur X de r1 JOIN r2).
Vous avez dit Θ-jointure ?
Bonsoir,
Citation:
Envoyé par
Age_of_Aquarius
Voici deux définitions qui, pour moi, n'ont pas la même signification mathématique.
Bien entendu, car conformément à la théorie relationnelle, Darwen ne propose pas la définition de la thêta-jointure mais celle de la jointure naturelle, équivalente à celle que j’ai extraite de The Relational Database Dictionary. Un point important pour mieux comprendre sa position quand il se focalise sur la jointure naturelle et n’attache aucune importance particulière à la thêta-jointure : au début des années soixante-dix, comme tout un chacun il a utilisé la définition de la thêta-jointure inventée et enseignée par le génial inventeur du Modèle Relationnel de Données, Ted Codd (vous trouverez cette définition dans Relational Completeness of Data Base Sublanguages) : On commence par définir la thêta-jointure, puis on passe à l’équi-jointure (comme cas particulier de la thêta-jointure) puis à la jointure naturelle (comme cas particulier de l’équi-jointure). Très tôt, Chris Date, le héraut du modèle relationnel a commencé lui aussi par enseigner consciencieusement dans l’ordre, thêta-jointure, équi-jointure, puis jointure naturelle, tout en faisant invariablement remarquer, à l’instar de Codd, que la thêta-jointure n’est jamais qu’une restriction d’un produit cartésien, et dans la foulée, c’est ce que nous avons tous appris et fidèlement enseigné à notre tour. Mais plus de vingt ans après la parution de l'article de Codd, en 1995, on a pu observer un glissement bien perceptible dans la 6e édition de l’ouvrage de référence An Introduction to Database Systems (pas loin de 800 000 exemplaires vendus...), car Date y présente d’abord la jointure naturelle (qu’il appelle désormais formellement jointure), la thêta-jointure ne venant que comme appendice, cantonnée dans un rôle secondaire, avec le statut de restriction d’un produit cartésien. Dans les ouvrages théoriques commis ensuite par Date et Darwen (qu'affectueusement j'appelle les Dupontd), tels que Databases, Types and the Relational Model, The Third Manifesto, la thêta-jointure a totalement disparu. Que vous ne l’ayez pas trouvée chez Darwen est on ne peu plus normal, puisqu’elle est — oserai-je dire —pieusement rangée au musée des curiosités historiques.
Pour mieux comprendre l’insistance de Darwen sur le rôle fondamental de la jointure naturelle, voici ce qu’il a écrit en 1987 et repris en tant que contribution darwenienne (signée du pseudonyme anagrammique Andrew Warden) dans l’ouvrage de Chris Date Relational Database, Writings 1985-1989, paru en 1990, je traduis :
« Étudions maintenant l’opérateur
Jointure naturelle et voyons comment il nous change la vie. Je le représente selon la syntaxe suivante :
MARRIAGE (table-expression-1, table-expression-2)
On peut voir ainsi la merveilleuse union accomplie par cet opérateur :
Dans un premier temps, il y a les tendres préliminaires à l’occasion desquels les colonnes des deux opérandes sont examinées, afin de voir lesquelles portent le même nom. Celles-ci sont appelées « colonnes communes » quand, outre le même nom, elles sont du même domaine.
Dans un deuxième temps a lieu l’accouplement : à cette occasion les lignes compatibles des deux opérandes sont jointes (à savoir les lignes qui ont la même valeur pour les colonnes communes).
Il y a enfin, l’orgasme grandiose quand un ensemble de colonnes communes est éjaculé.
Le fruit de cette union est un individu aussi parfait qu’on peut le souhaiter, ayant hérité des caractéristiques de ses parents. »
Ainsi, vous comprendrez pourquoi Darwen, ne porte qu’un intérêt fort mineur à la thêta-jointure et se démarque donc de la définition coddienne, scrupuleusement respectée par les auteurs que vous citez...
Dans un petit ouvrage paru en 2001, The Database Relational Model, a Retrospective Review and Analysis, Date commente l’article de Codd dont j’ai fait mention ci-dessus, Relational Completeness of Data Base Sublanguages (je traduis) :
Θ-jointure et jointure naturelle
[A l’époque, les définitions de] ces opérations sont à peu de choses près celles d’aujourd’hui. Il est cependant intéressant de noter que Codd définit la jointure naturelle — comme une simple touche finale pourrait-on dire — en termes de Θ-jointure (plus précisément comme la projection d’une équi-jointure). Aujourd’hui nous tendons à considérer la jointure naturelle comme étant l’opération la plus fondamentale (au point que le terme « jointure » sans qualificatif est habituellement considéré comme désignant plus spécifiquement la jointure naturelle). On aura remarqué que la Θ-jointure en tant que telle ne figurait même pas dans les deux premiers articles de Codd (1969 et 1970). Codd fait observer que la Θ-jointure peut être définie en termes de Θ-restriction, en conséquence de quoi ça n’est pas une opération primitive. (En fait, l’inverse est vrai aussi, c'est-à-dire que la Θ-restriction peut être définie en termes de Θ-jointure ; considérer quelle collection d’opérations est primitive a donc quelque chose d’arbitraire, tout dépend du point de vue selon lequel on se place. Il est communément admis qu’une collection primitive est constituée de la restriction, de la projection, du produit, de l’union et de la différence).
Note : Comme les opérations d’union, intersection et produit (étendu), la jointure naturelle est commutative et associative.
Clairement la jointure naturelle désormais baptisée JOIN joue bien le rôle essentiel qu'on lui connaît et nos deux compères ont passé la thêta-jointure au rasoir d’Ockham...