Jointure, jointure, vous avez dit jointure ? [Débat]

[pacmann]

ça va trop vite, je voulais me prendre le temps de me pencher sur le sujet avant d'intervenir...
Mais je n'ai pas pu résister parce que le dernier post de fsmrel à attisé ma curiosité !
J'ai du commencer par chercher la définition de tous les termes employés

R1 X R2 = R1 : c'est une équation ?

Si oui, sur quoi porte l'égalité ?
=> Sur l'intention : l'égalité n'a pas de solution, si on suppose qu'une intention ne peut être l'ensemble vide (au sens degré nul). Sinon, toute R2 est solution (parce que le vide, ça absorbe énormément)

=> Sur l'extention : Si on définit l'extention du produit cartésien comme le produit cartésien mathématique (SELECT R1.*, R2.*) on ne peut avoir l'égalité à moins que l'extention de R1 soit vide (c'est à dire aucune donnée)
Par contre, avec un tout petit abus de langage, on peut considérer que lorsque le cardinal de R2 (je pense au cardinal de son extention) vaut 1, R1 * R2 ressemble beaucoup à R2. Je crois qu'on peut dire que R1 est simplement une projection de R1 * R2

(Un peu d'indulgence s'il vous plait, même en y mettant toutes mes forces, j'ai un peu de mal à conceptualiser le truc...)

[fsmrel]

Envoyé par pacmann

R1 X R2 = R1 : c'est une équation ?

Ma formulation fut un peu succincte, pardonnez-moi. Disons que R1 et R2 sont deux relvars (variables relationnelles, dont les valeurs successives sont des relations au sens de Codd).

Si la valeur de R1 est r1 et celle de R2 est r2, alors on veut que la valeur du résultat du produit cartésien soit r1...

Cela aboutit à quelques contraintes sympathiques. Soit n1 le degré de R1 (le nombre d’attributs de son en-tête) et n2 le degré de R2.
Soit c1 le cardinal de R1 et c2 celui de R2.

Toujours au sens de Codd, le degré de la relation résultant du produit cartésien est égal à n1 + n2 et son cardinal est égal à c1 x c2.

Comme vous l’avez souligné, on doit vérifier :

n1 + n2 = n1

c1 x c2 = c1

La conclusion est intéressante quant aux propriétés de r2... Il s’agit en réalité d’une constante faisant partie du Modèle Relationnel de Données et elle s’appelle Table_Dee (elle a du reste une petite sœur qui s’appelle Table_Dum). Si vous avez cinq minutes, je vous suggère à ce sujet de jeter un coup d’œil à un article de Chris Date, mais ne vous sentez quand même pas obligé, tout ceci n’est qu’une récréation...

Incidemment, pour produire Table_Dee en SQL, il faudrait que l’on soit autorisé à écrire quelque chose comme :

SELECT
FROM ;

ou plus simplement :

;

Quant à produire Table_Dum :

SELECT
FROM
WHERE false ;

Rigolo, non ?

[marchand_de_sable]

Envoyé par fsmrel

tout ceci n’est qu’une récréation...

Je suis avec intérêt cette discussion (merci M'sieurs-dames), même si j'avoue n'en saisir qu'une infime partie...
C'est sans doute parce que mes récréations se passe devant une mousse et une partie de cartes

[fsmrel]

Bonjour Marchand de sable,

Envoyé par marchand_de_sable

mes récréations se passe devant une mousse et une partie de cartes

Tchin ! Vous me forcez à avouer que ce que j'ai écrit hier le fut à l’aide d'un Lagavulin fleurant bon la tourbe...

Table_Dee et Table_Dum sont de curieux petits personnages, sortis de l'imagination de Hugh Darwen, tandis qu'il avait en tête la comptine de Tweedle Dee et de Tweedle Dum qui récitèrent leurs poésies à Alice quand celle-ci fut passée de l'autre côté du miroir. Comme vous êtes amateur de cartes, je vous conseille de jeter un coup d'oeil au Double Dummy Corner de Hugh.





Pour mémoire, je rappelle que c'est grâce à Hugh qu'en SQL vous pouvez utiliser des expressions de tables dans la clause FROM :

... FROM [...,] (SELECT ... FROM ... ) ...

[pacmann]

Bonsoir !

fsmrel, marchand_de_sable : effectivement, c'est très divertissant. Et ça fait vraiment plaisir de s'adresser à un spécialiste qui accepte de répondre à des novices

Par rapport à l'article de Cris Date, je crois qu'on m'avait déjà fait ce genre de blague, mais avec une phrase du genre "je mens toujours". Si je mens toujours, la phrase est vraie, il y a un problème puisque je viens du coup de dire la vérité...

Mais quant à la relation table_dee, ne peut-on pas se poser la même question que pour la proposition mise en défaut dans son article ?
C'est à dire : la relation table_dee existe-t-elle vraiment ou encore table_dee est-elle une relation ?

En fait, l'existence de la table_dum me pose moins de problème, puisque, d'un point de vue intention, c'est l'ensemble vide. Mais pour moi, la définition de la table_dee revient à considérer un élément appartenant à l'ensemble vide...

Soit R, tel qu'il existe une suite finie d'ensemble A1, ..., An et R est inclus dans A1 x ... x An.

Alors considérer la relation que n=0, c'est juste définir un cas limite, soit considérer que l'ensemble vide est un élément de l'ensemble des relations.
Mais dire qu'il existe a € R dans ce cas, ne serait-ce pas simplement faux ?

Sinon, comment définit-on le fait d'appartenir à une relation ?

[marchand_de_sable]

Arrfff, je ne connaîs pas le Bridge...
Mais je garde le lien, il serait peut-être temps que je m'y mette.

[pacmann]

Je me permets de revenir sur un vieux post de fsmrel !

Et de la même façon, les opérateurs relationnels ne sont pas exactement ceux qu’on utilise en mathématiques. Ainsi, concernant le produit cartésien U = S X T, je cite Codd :
In textbooks on mathematics the usual explanation is that U is the set of all tuples of the form
< < a1,a2, ..., am >, < b1, b2, ..., bn > >,
where < a1,a2, ..., am > is a tuple of S and < b1, b2, ..., bn > is a tuple of T... For purposes of database management, it is more useful to adopt a slightly different definition, and to say that U is the set of all tuples of the form
< a1,a2, ..., am, b1, b2, ..., bn >.

Je pense que jusqu'à un certain point, on peut séparer ce qui se passe dans le SELECT du reste. Ou plus précisément, considérer que les résultats des opérations ensemblistes sur les relations sont indifféremment de la forme < < a1,a2, ..., am >, < b1, b2, ..., bn > > ou de la forme < a1,a2, ..., am, b1, b2, ..., bn > pour les clauses autres que SELECT.
Je ressens la clause SELECT comme un opérateur très fonctionnel (par opposition à la relation simple : elle effectue un lien n..1 entre deux ensembles), qui s'applique sur le sous-ensemble du produit cartésien.
C'est un peu faux et simpliste, mais bon...

Etc. Comme en plus, l’ordre des éléments n’intervient plus du fait de l’utilisation d’attributs nommés, le produit cartésien relationnel est commutatif et associatif (ce qui est intéressant pour un optimiseur).

Je ne dirais pas que l'opération est commutative :
SELECT *
FROM A, B

ne donne pas la même chose que

SELECT *
FROM B, A

puisque le résultat n'est pas considéré comme un ensemble de champ, mais bien comme une séquence.
Si on peut s'abstraire de cet ordre, c'est parce qu'on connaît l'ordre qui a été choisi au moment de la requête, ou qualifier les champs du résultat.
Cela revient à considérer, plutôt que le n-uplet <a1, ..., an>, l'ensemble des couples {<nom1, a1>; ...; <nomn, an>}, ou encore considérer non pas le sous-ensemble du produit cartésient, mais la donnée de ce sous-ensemble et d'un élément appartenant à l'ensemble des intentions...

Quant à l'associativité, elle découle naturellement de "l'abus de langage" (ou simplification de notation) de CODD.
Ce genre de chose doit être assez courante. Genre quand on considère qu'une matrice réelle de taille (1, 1) est un réel, ou encore le polynôme P avec la fonction x -> P(x), ...

Vous remarquerez que l’opérateur relationnel UNION est lui aussi différent de l’UNION au sens traditionnel, il en est une extension du fait de sa contrainte d’union-compatibilité.

Oui, effectivement. C'est comme une restriction, une loi de composition interne sur l'ensemble des sous-relations d'une relation donné.
C'est un peu comme si on considère l'addition sur les réels, l'addition sur les entiers 5 * 1,5 est parfaitement défini sur les réels, mais si on considère le '+' du groupe des entiers (N, +), cela n'a pas de sens de dire 5 + 1,5...

Le but de ces remarques, c'est juste de dire que je ne trouve pas qu'on s'éloigne de la théorie mathématique, mais plutôt qu'on "l'approfondit", qu'on la spécialise dans une direction. Qu'on en "hérite" (pour faire informaticien ).

Cela dit, WHERE est aussi un autre nom pour l’opérateur de restriction du modèle relationnel. Je cite Chris Date, le complice de Ted Codd :
Soit a une relation d’attributs X, Y, ..., Z et soit p une fonction vérifonctionnelle dont les paramètres sont, précisément, un certain sous-ensemble de X, Y, ..., Z. Alors la restriction de a selon p
a WHERE p
est une relation dont l’en-tête est identique à celui de a et dont le corps est constitué de tous les tuples de a tels que p est évaluée à VRAI pour les tuples considérés.

C'est exactement ce à quoi je pensais !
Nous avons de manière de voir les choses :
- considérer la relation R=A x B, puis R'=a WHERE p (avec a € R)
- considérer A Join B ON p.
Si le résultat est le même après passage de l'optimisateur, d'un point de vue conceptuel, ça peut s'interpréter différemment : p est soit un lien logique entre deux ensembles, ou p est simplement la caractérisation d'un sous ensemble...

[fsmrel]

Bonsoir,

Envoyé par pacmann

ça fait vraiment plaisir de s'adresser à un spécialiste qui accepte de répondre à des novices

Pas spécialiste, mais généraliste plus particulièrement intéressé par le Modèle relationnel, qui a eu à le défendre dans certaines occasions, face à des "spécialistes" particulièrement incompétents à son sujet, et toujours prêt à expliquer, dans la mesure de ses moyens.

Envoyé par pacmann

la relation table_dee existe-t-elle vraiment ou encore table_dee est-elle une relation ?

Dans le cadre du Modèle relationnel, une relation est constituée d’un en-tête (ensemble de ses attributs, dont le cardinal n est appelé degré de la relation) et d’un corps (ensemble de ses n-uplets). Un ensemble pouvant être vide, il n’est pas interdit que n soit égal à zéro. L’en-tête d’une relation peut donc être vide, mais en vertu du principe d’orthogonalité (ou indépendance) cher aux tenants du Modèle relationnel, cela n’entraîne pas la vacuité du corps. Ou bien le corps d’une telle relation contient un unique n-uplet, le 0-uplet, ou bien il n’en contient aucun. Il y a donc exactement deux relations de ce type et elles sont appelées respectivement Table_Dee et Table_Dum (Dee et Dum pour abréger). Ce sont deux constantes, qui sont au Modèle relationnel ce que VRAI er FAUX sont à la logique. Dee et Dum sont encore considérés comme les seuls représentants de la relation nullaire (nullary relation), c'est-à-dire de la relation n-aire pour laquelle n = 0.

Une relvar (variable relationnelle) prend successivement des valeurs qui sont des relations. Toute relvar est astreinte à être dotée d’une clé. Une relvar de degré zéro n’échappe pas à la règle et elle a pour clé l’ensemble vide, ø. Incidemment, il n’est pas interdit qu’une relvar de degré > 0 ait ø pour clé : ceci permet par exemple de limiter à un le nombre de tuples de cette relvar (cas par exemple de la racine d’une structure arborescente), même s’il existe d’autres moyens, moins élégants d’assurer la contrainte.

[fsmrel]

Envoyé par pacmann

Je ressens la clause SELECT comme un opérateur très fonctionnel (par opposition à la relation simple : elle effectue un lien n..1 entre deux ensembles), qui s'applique sur le sous-ensemble du produit cartésien.

SELECT joue un rôle analogue à celui de PROJECT, l’opérateur relationnel utilisé pour effectuer une projection, mais il ne peut être confondu avec lui. Pour mieux percevoir l’analogie, au lieu d’écrire :

SELECT colx, coly, ...
FROM ...
WHERE ...

il suffit de présenter ainsi les choses, c'est-à-dire dans l’ordre selon lequel les choses se passent (au moins conceptuellement) :

FROM ...
WHERE ...
SELECT colx, coly, ...

SELECT est l’opérateur qui permet de présenter le résultat final, par projection sur colx, coly, ....
Dans le contexte de la tambouille SQL, ce résultat n’est pas forcément une relation car les doublons y sont autorisés : si l’on a le moindre doute, il est prudent d’utiliser la clause DISTINCT. Malgré cela, le résultat peut encore ne pas être une relation : les colonnes ne sont pas nécessairement nommées et l’on peut avoir des doutes quant à leur domaine de référence. Il est possible aussi de faire figurer plusieurs fois la même colonne... Par ailleurs, ce résultat peut comporter des valeurs nulles, auquel cas il peut s’avérer impossible de respecter l’intégrité d’entité (toute relation doit être munie d’une clé et celle-ci ne peut pas comporter d’attribut pouvant être marqué null).

Je ne dirais pas que l'opération est commutative :

SELECT *
FROM A, B

ne donne pas la même chose que

SELECT *
FROM B, A

Dans le cadre du Modèle relationnel, le produit cartésien étendu est bien commutatif. Il faut le dissocier de SELECT, qui comme on vient de le voir ressemble vaguement à PROJECT. En fait, vos requêtes sont équivalentes à celles-ci :

SELECT A.*, B.*
FROM A, B

et

SELECT B.*, A.*
FROM B, A

Les produits A TIMES B et B TIMES A donnent lieu au même résultat, en revanche, dans un 2e temps, c’est bien le simulacre de projection qui produit des résultats différents.

Quant à l'associativité, elle découle naturellement de "l'abus de langage" (ou simplification de notation) de CODD.

Codd utilise l’expression : "expanded cartesian product" (Cf. Relational completeness of data base sublanguages, page 5).

Le but de ces remarques, c'est juste de dire que je ne trouve pas qu'on s'éloigne de la théorie mathématique, mais plutôt qu'on "l'approfondit", qu'on la spécialise dans une direction

I agree with you Tovaritch ! Le but de Codd fut bien de construire sur des bases simples mais solides, un modèle théorique pour les bases de données, qui reste accessible à tous, à une époque où l’on ne traitait ces bases de données qu’au niveau élémentaire et non pas ensembliste, de manière plutôt fruste, strictement procédurale, navigationnelle, séquentielle, enregistrement par enregistrement, en suivant les pointeurs. Codd a créé un pays qui s’appelle le Relationland, lequel est hélas ! encerclé par le Askew wall (prononcer SQL), sorte de construction bancale, non orthogonale et dans laquelle tout le monde se vautre, croyant avoir atteint le pays des relations. Je relis de temps en temps ce qu’a écrit Codd il y a bientôt 40 ans et je reste impressionné. De temps en temps, un peu comme en relisant les aventures d’Astérix le Gaulois, je découvre des choses qui m’avaient échappé ou encore je me rends compte que j’avais mal capté certains points (et il y a surement bien des choses qui m’échappent encore). En revanche, quand je feuillette les documentations jaunies traitant des bases de données pré-relationnelles (qui m'ont quand même fait vivre du temps où Codd posait ses fondations), j’ai l’impression de revenir à une époque extrêmement lointaine, plus qu'antédiluvienne...

Si le résultat est le même après passage de l'optimisateur, d'un point de vue conceptuel, ça peut s'interpréter différemment : p est soit un lien logique entre deux ensembles, ou p est simplement la caractérisation d'un sous ensemble...

Certes, mais comme dirait Chevallier à Laspalès, c’est vous qui voyez...

[SQLpro]

Petite chose importante : oui le plan d'exécution est le même (ou devrait l'être) que la jointure INTERNE se fasse dans le where ou dans le JOIN.
Pour les jointures externes, ce n'est pas la même chose car chaque éditeur ayant fait a sa tête, ni la syntaxe ni les résultats ne sont les mêmes...
Par exemple les jointures externes de SQL Server avec *= ne donnent pas les mêmes résultats que le OUTER JOIN !

En revanche en ce qui concerne SQL Server, l'optimiseur tire partit de beaucoup de choses, y compris les contraintes. Par exemple vous serez surpris de constater que la plan de requête change si vous cherchez une valeur négative sur une colonne pourvue d'une clause CHECK avec VALUE > 0...
Et là ce n'est plus de l'optimisation de la requête que nous devons parler, mais de l'optimisation du plan lui même.
En effet avec les JOIN, l'optimiseur pré suppose que la jointure est naturelle et que dans ce cas les colonnes en jeu sont indexées ce qui la plupart du temps s'avère exact (sauf aux rigolos qui n'ont toujours pas compris ce qu'étais un SGBD relationnel et s'obstinent à éviter les contraintes d'intégrité référentielles et les index qui vont avec... mais bon passons).
Autrement dit : avec un modèle respectant les règles de l'art et dont les clefs étrangères sont proprement indexées, l'optimiseur passera moins de temps à trouver le plan parfait. Ou plus exactement il aura plus de chance dans le temps qui lui est impartit, de trouver le meilleur plan de requête.

A +

[fsmrel]

Bonsoir SQLpro,


A propos des erreurs commises par certains optimiseurs, je vous conseille la lecture de A cure for Madness (1re partie) de Chris Date, ainsi que la suite qu'il en a donnée : A cure for Madness (2e partie).

Peut-être avez-vous déjà lu ces articles, quoi qu'il en soit, chacun peut vérifier très rapidement que SQL Server n'est pas délinquant en ce qui concerne le problème particulier évoqué par CJD...

[SQLpro]

Oui, je connais bien ce test, assez rigolo, que je passe de temps en temps pour savoir comment se comporte certains moteurs SQL !!!

A +

[SQLpro]

Pour mémoire, je rappelle que c'est grâce à Hugh qu'en SQL vous pouvez utiliser des expressions de tables dans la clause FROM

Juste corriger un petite erreur... Ceci ne s'appelle pas expression de table, mais table dérivée.

L'expression de table est en fait un genre de vue introduite par le mot clef WITH et dont la particularité (outre les possibilité de récursion) est de n'exister que le temps d'exécuter la requête.

A lire sur les expressions de tables : http://sqlpro.developpez.com/cours/s...te-recursives/

A +

[fsmrel]

Envoyé par SQLpro

Juste corriger un petite erreur... Ceci ne s'apelle pas expression de table, mais table dérivée.

Sauf à faire impunément du passé table rase, il ne s’agit pas d’une erreur. Hugh Darwen (sous un de ses noms de plume, Andrew Warden), a fourni en 1988 dans "The Relational Journal, Issue 3, March 1988)" un article intitulé "The Naming of Columns" et dans lequel il a écrit (les mots en gras le sont dans le texte original) :

"Can a table expression be used anywhere where a table name can be used?
In other words, a table-name is merely the trivial case of a table expression!
Would you tolerate a programming language (say a dialect of Fortran) in which you didn’t have complete freedom to use a formula of arbitrary complexity anywhere where a number is required?
Why the title of this article?
That wonderful property of true algebras (such as Relational Algebra), which guarantees that results are the same kind of things as the operands, is called closure..."

Les gens qui font la norme ont été attentifs à ce qu’a écrit Hugh qui fut le représentant d’IBM UK dans les instances, à partir de 1988.
Sans son plaidoyer, il se pourrait que l’on ne puisse toujours pas écrire :

FROM t1, ..., (Select ...) As Tj, ...

Pour des raisons d’antériorité et en hommage à Hugh et à ses collègues d’IBM UK qui ont fait BS12 entre 1978 et 1982 (et assassiné par le Monstre en 1985), je continuerai donc à utiliser l’expression originale "expressions de tables" ("relational expressions" dans BS12), en dépit des glissements sémantiques opérés ultérieurement par les gens de la norme. Vous pouvez retrouver l’article d'Andrew Warden dans Relational Database, Writings 1985-1989.

[SQLpro]

Oui, mais ta position ne va pas faciliter la lecture des internautes.... Bref, de belles confusions en perspective !

A +

[Luc Orient]

Envoyé par SQLpro

Juste corriger un petite erreur... Ceci ne s'appelle pas expression de table, mais table dérivée.

Pour apporter ma modeste contribution au débat et sauf erreur de ma part, il me semble qu'avec DB2 for z/OS (le mainframe pour faire simple) on parle bien de " nested table expression ".

A fullselect in parentheses is called a nested table expression. If a nested table expression is specified, the result table is the result of that nested table expression. The columns of the result do not need unique names, but a column with a non-unique name cannot be referenced. At any time, the table consists of the rows that would result if the fullselect were executed

cf. ( extraits du " DB2 UDB for z/OS V8 SQL Reference " ) :

from clause

table reference

[SQLpro]

La " nested table expression " de DB2 a une toute autre signification dans la norme SQL. C'est en fait le concept de table dérivée. Les expressions de table (CTE : Common Table Expression) étant une forme proche du concept de table dérivée...

Exemple :

SELECT *
FROM (SELECT ... FROM ...)

la partie en gras est une table dérivée

WITH T AS
(SELECT ... FROM ...)
SELECT *
FROM T

La partie en gras est une expression de table.

A +

[Bonne Année]

Salut à tous,

Pour ma part, la jointure se fait dans le WHERE, je pense que l'on pourrait le faire dans une autre condition mais il faut savoir toucher pour pouvoir y arriver.

Voilà

Bonne fin de journée à tous

Bonne.Année

[CinePhil]

Ben c'est une mauvaise habitude à perdre !

Ce forum commence à se remplir d'exemple de requêtes qui posaient des problèmes à leur auteur parce qu'ils avaient mélangé les clauses de jointure et de restriction.

En écrivant avec des jointures normalisées, l'erreur dans la requête apparaît soudainement beaucoup plus évidente !

[pacmann]

Fsmrel, quelques petites remarques :

Dans "Relational completeness of data base sublanguages", Codd donne la définition suivante de la jointure :

2.3.3 Join - Let θ denote any of the relations =, <>, <, <=, >, and >=. The
θ-join of relation R on domain A with relation S on domain B is
defined by
R[A θ B]S = {(r s): r € R ^ s € S ^ (r[A] θ s[b])}

Un peu plus loin, en 2.3.5, il définit la Restriction (C'est déjà amusant qu'il le fasse dans cet ordre...) et note que :

The θ -join of R with S is likewise definable in terms of Cartesian product and 8-restriction:
R[A θ B]S = (R X S)[A θ B].

On y ajoute la remarque de quelqu'un de célèbre (un peu moins que Codd, cela dit) :

WHERE est en fait le pendant de l’opérateur RESTRICT (ou θ-RESTRICT, ou θ-SELECT, etc.) de la théorie relationnelle

Vous avez pas la sensation qu'il dit "Tiens, au passage, on peut aussi voir la jointure comme un sous-ensemble du produit cartésien " ?
Perso, je trouve que la première définition ressemble plus à JOIN, et la seconde plus à WHERE

Dans le "Principia mathematica" (qu'il faudrait que je me remette à parcourir...), on parle un peu de ce qu'est une définition (page 11), et on distingue deux types aspects :
1) L'aspect pratique.

Practically, of course, if we introduced no definitions, our formulae would very soon become so lengthy as to be unmanageable; but theoretically, all definitions are superfluous

2) Conceptuel.

First, a definition usually implies that the definiens is worthy of careful consideration. Hence the collection of definitions embodies our choice of subjects and our judgment as to what is most important.
Secondly, when what is defined is something already familiar, such as cardinal or ordinal numbers, the definition contains an analysis of a common idea, and may therefore express a notable advance.

A trop insister sur le fait que la relation est un sous-ensemble du produit cartésien étendu, on oublie le deuxième point... et on risque d'en venir à dire "all definitions are superfluous" !
Je ne sais pas exactement ce qu'est ou n'est pas une primitive (et donc en quoi Codd ne considérait pas la jointure comme une primitive !), mais la définition de l'opérateur de jointure matérialise une notion intuitive de lien. La notion définie / le concept créé a bien plus d'importance que la définition en elle même...