Discussion :

[BIOoOAG]

Bonsoir tout le monde,

Question sur les produits cartésiens avec un exemple,
dans la base j'ai des flux avec ces jointures qui fonctionnent très bien (ce n'est pas moi qui ai dev le truc) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
FROM commande_produit cp
join commande c						on cp.commande_id = c.commande_id
join LITIGE_COMMANDE lc				on (lc.commande_id = c.commande_id and lc.commande_id = cp.commande_id)
join LITIGE_PRODUIT lp					on (lp.CP_ID = cp.CP_ID and lp.litige_id=lc.litige_id)

Pour "résumé" ça fait ça :

CP--LC
| \/ |
| /\ |
C , LP

Donc des jointures dans tous les sens.

Cependant je ne comprends pas pourquoi ça marche et pourquoi ça ne fait pas un produit cartésien?
Vous pouvez m'aider à comprendre svp?



Bonne soirée!

[fsmrel]

Rappel :
Par définition, dans le cadre de la théorie relationnelle, étant données les relations r1, r2, ... , rn, leur produit cartésien est une relation dont l’en-tête (ensemble des noms des attributs de la relation) est l’union des en-têtes des relations r1, r2, ... , rn, et dont le corps est l’ensemble de tous les tuples t tels que t est l’union d’un tuple de r1, d’un tuple de r2, ..., et d’un tuple de rn.

En exprimant cela en SQL :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
SELECT *
FROM   R1, R2, ..., Rn

Dans votre cas, vous n’avez que des jointures, plus précisément des équi-jointures, donc pas de produit cartésien.

Maintenant, d’un point de vue pratique, l’optimiseur de votre SGBD SQL va chercher la technique la plus efficace pour traiter votre requête. Les choses se passent dans la soute, au niveau physique, et ce sont les index (objets physiques déterminants pour la performance) qui seront exploités (s’ils existent !), par appareillage et autres techniques (merge scan, nested loop, etc.)

En passant, s’il a quelque compétences en sémantique, et s’il estime que le coût sera moins élevé, l’optimiseur commencera probablement par réécrire la requête.
Par exemple, sur la base de A = B et B = C => A = C, soit :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

on (lc.commande_id = c.commande_id and lc.commande_id = cp.commande_id)

si l’optimiseur estime que cela vaut le coup, il est possible qu’il réécrive cette partie ainsi :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

on (c.commande_id  = cp.commande_id)

Le SGBD conserve dans son catalogue intégré tous les éléments pour en juger. Et, toujours dans un souci d’économie et de performance, l’optimiseur va poursuivre ainsi son travail de simplification.

Cela dit, pour en avoir le cœur net, vous pouvez demander à votre SGBD de vous dire comment il procède. Pour cela, utilisez l’instruction EXPLAIN précédant votre SELECT. Voyez par exemple ici : popom s’arrachait les cheveux, puis grâce à quelques EXPLAIN, on a pu trouver le moyen que tout rentre dans l’ordre (message #12).

Au fait, quel est votre SGBD ?

[BIOoOAG]

Merci beaucoup pour cette réponse détaillée!
Je suis sur Sql serveur 2016


Donc si je comprends bien le produit cartésien est plus dû à l'absence d'une jointure ou une jointure partielle?

Car en faisant les jointures je partais du principe qu'il fallait un chemin logique A vers B vers C.


De ce fait dans quels cas on peut avoir un produit cartésien lorsque l'on fait des jointures (autre que des jointures partielles)?

Merci d'avance!

[SQLpro]

Donc si je comprends bien le produit cartésien est plus dû à l'absence d'une jointure ou une jointure partielle?

Le produit cartésien est une opération primaire de l'algèbre relationnelle, tout comme la jointure. S'il y a une jointure il n'y a pas de produit cartésien, inversement, et vice verso versa !

le produit cartésien sert à faire une "multiplication" relationnelle. Son inverse étant la division relationnelle...

A +

[escartefigue]

S'il y a une jointure il n'y a pas de produit cartésien, inversement, et vice verso versa !

Sauf que... la norme SQL a prévu la jointure croisée "CROSS JOIN" qui fait ... le produit cartésien

[SQLpro]

Sauf que... la norme SQL a prévu la jointure croisée "CROSS JOIN" qui fait ... le produit cartésien

oui mais ce n'est pas une jointure, juste une facilité d'écriture...

Elle a aussi prévu le UNION JOIN qui ne fait pas non plus de jointure au sens algébrique du terme...

Voir mes livres sur SQL

A +

[fsmrel]

BIOoOAG, il faut que vous fassiez bien le distinguo entre ce qui se passe sur le pont (niveau logique) et ce qui se passe dans la soute (niveau physique).

Sur le pont, nous disposons d’une algèbre, l’algèbre relationnelle (inventée par E.F. Codd en 1969).Dans son article de 1972, Relational completeness of data base sublanguages, Codd fournit l’ensemble nécessaire et suffisant des opérateurs permettant l’exploitation des bases de données relationnelles : produit cartésien, union, intersection, différence, projection, restriction, jointure, division.

Bien entendu, au fil des ans l’algèbre relationnelle a été étendue dans le but de faciliter le travail de ses utilisateurs (theta-join, exclusive union, semijoin, semidifference, extend, j’en passe et des meilleures).

La norme SQL n’est pas en reste, et la jointure de deux tablest1 et t2 peut d’écrire par exemple ainsi :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
1.    t1 NATURAL JOIN t2
2.    t1 JOIN t2 ON bx
3.    t1 JOIN t2 USING (C1, C2, ..., Cn)
4.    t1 CROSS JOIN t2

où bx est une expression booléenne (comme dans le cas de votre requête initiale), et C1, C2, ..., Cn sont des noms de colonnes.

L’opération CROSS JOIN représente le produit cartésien, sous réserve que les noms des colonnes de t1 et ceux de t2 soient tous différents. Vous noterez que le produit cartésien n’est jamais qu’un cas particulier de la jointure, dégénéré, mais néanmoins cas particulier.

A noter que t1 CROSS JOIN t2 est équivalent à SELECT * FROM t1, t2.

SQL Server propose l’opération CROSS JOIN, voyez la documentation chez Microsoft.

En reprenant la définition que j’en ai donnée dans mon message précédent, on voit donc ce qu’on entend par produit cartésien au niveau logique.

si je comprends bien le produit cartésien est plus dû à l'absence d'une jointure ou une jointure partielle?

Puisque le produit cartésien est en fait un cas particulier (dégénéré) de la jointure, ce que vous écrivez est à aménager : dans le cas de votre requête, c’est l’absence systématique de l’expression booléenne bx qui ferait que la jointure dégénérerait en produit cartésien :

Code SQL :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
FROM commande_produit cp
     join commande c
     join LITIGE_COMMAND lc
     join LITIGE_PRODUIT lp

Pour sa part votre requête comporte systématiquement des expressions bx, elle ne provoque donc aucunement la dégénérescence de la jointure.

Manifestement, votre interrogation porte sur le niveau physique : que se passe-t-il dans la soute ? Comme je l’ai écrit, c’est l’instruction EXPLAIN qui vous éclairera.

dans quels cas on peut avoir un produit cartésien lorsque l'on fait des jointures

Supposons que vos tables soient dépourvues d’index : un SGBD lambda pourrait par exemple balayer la table commande_produit et pour chaque ligne concaténer l’ensemble des lignes de la table commande. Ceci fait, le SGBD pourrait concaténer chaque ligne du résultat avec chaque ligne de la table LITIGE_COMMAND, puis rebeloter avec la table LITIGE_PRODUIT. Sur le plan de la consommation du temps et de l’espace, on risque de tout faire exploser...

Le SGBD pourrait adopter une autre stratégie : créer des fichiers temporaires appareillés selon les colonnes participant aux expressions booléennes bx : cp.commande_id = c.commande_id, etc.

Pour savoir objectivement comment les choses se passent dans la soute : EXPLAIN !

en faisant les jointures je partais du principe qu'il fallait un chemin logique A vers B vers C.

C’est un principe qu’on utilisait du temps des SGBD non relationnels, qualifiés de navigationnels et qui sont morts dès que les SGBD R ont été rendus opérationnels. En relationnel, on ne navigue pas, on ne suit pas des chemins, on compare des ensembles.

[fsmrel]

Le produit cartésien est une opération primaire de l'algèbre relationnelle, tout comme la jointure. S'il y a une jointure il n'y a pas de produit cartésien, inversement, et vice verso versa !

Fred,

Il est bon de préciser que si le produit est un opérateur primitif, alors c'est un élément de l’ensemble suivant des opérateurs primitifs de l’algèbre relationnelle, et dont la jointure naturelle (join) ne fait pas partie :

{restrict, project, product, union, difference}

Mais l’ensemble suivant peut lui aussi être considéré comme l’ensemble des opérateurs primitifs, où la jointure a remplacé le produit (qui n’est après tout qu’un cas particulier de la jointure) :

{restrict, project, join, union, difference}

Référence : l’ouvrage de C. J. Date, An Introduction to Database Systems (Eighth Edition), page 192.

Sauf que... la norme SQL a prévu la jointure croisée "CROSS JOIN" qui fait ... le produit cartésien

oui mais ce n'est pas une jointure, juste une facilité d'écriture...

Je suis d’accord avec C.J. Date et escartefigue, c’est une jointure, un cas particulier certes, mais une jointure quand même.

BIOoOAG, ne vous inquiétez pas, nous chipotons et débattons à l’occasion du sexe des anges...

[SQLpro]

Je suis d’accord avec C.J. Date et escartefigue, c’est une jointure, un cas particulier certes, mais une jointure quand même.

Je dirais l'inverse... Une jointure interne est un raffinement du produit cartésien... Mais pas que ! La jointure externe ne l'est pas !

A +

[escartefigue]

A noter que t1 CROSS JOIN t2 est équivalent à SELECT * FROM t1, t2.

Oui et pour les esprits retors on peut également coder

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
SELECT * FROM TAB1
INNER JOIN TAB2 ON 1=1
INNER JOIN TAB3 ON 1=1
. . .

Tout ça c'est bonnet blanc et blanc bonnet

[CinePhil]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
FROM commande_produit cp
join commande c						on cp.commande_id = c.commande_id
join LITIGE_COMMANDE lc				on (lc.commande_id = c.commande_id and lc.commande_id = cp.commande_id)
join LITIGE_PRODUIT lp					on (lp.CP_ID = cp.CP_ID and lp.litige_id=lc.litige_id)

Je ne vois pas bien l'intérêt des AND dans la première condition de jointure ici présente.
Puisque cp.commande_id = c.commande_id alors lc.commande_id = cp.commande_id est suffisant lc.commande_id sera forcément égal à c.commande_id.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
FROM commande_produit cp
join commande c						on cp.commande_id = c.commande_id -- A = B
join LITIGE_COMMANDE lc				on lc.commande_id = cp.commande_id -- C = A donc A = B = C, c'est suffisant

Quant à la seconde, CP_ID est-il l'identifiant de commande_produit ?
Cet identifiant est-il d'ailleurs utile ? Vu le nom de la table, il semble qu'elle soit issue d'une association entre la commande et le produit. Sa clé primaire composée de l'identifiant de la commande et de l'identifiant du produit devrait donc suffire.

Ou alors il y a un pataques dans les données qu'il faut démêler ?

[escartefigue]

Je ne vois pas bien l'intérêt des AND dans la première condition de jointure ici présente.
Puisque cp.commande_id = c.commande_id alors lc.commande_id = cp.commande_id est suffisant lc.commande_id sera forcément égal à c.commande_id.

Tout à fait d'accord, critères de jointure redondants + parenthèses inutiles rendent la lecture malaisée ... à simplifier

[fsmrel]

Je dirais l'inverse... Une jointure interne est un raffinement du produit cartésien...

Plaît-il ? Veux-tu dire qu’au moyen du seul opérateur produit (TIMES), on peut réaliser une jointure ? Que sous-entend le mot « raffinement » ? Sois précis !

J’en reste au fait que le produit est un cas particulier de la jointure et que l’« inverse » est faux (il est faux que la jointure puisse être obtenue à partir du seul produit). En effet, considérons les relations R1 et R2 d’en-têtes composés respectivement des attributs

X1, X2, ..., Xm, Y1, Y2, ..., Yn

et

Y1, Y2, ..., Yn, Z1, Z2, ..., Zp

Y1, Y2, ..., Yn étant les seuls attributs « joignables » (même nom, même type).

Pour simplifier la rédaction, utilisons les attributs composés

X = {X1, X2, ..., Xm} ; Y = {Y1, Y2, ..., Yn} et Z = {Z1, Z2, ..., Zp}

Alors la jointure naturelle (JOIN) de R1 et R2

R12 = R1 JOIN R2

est une relation ayant pour en-tête {X, Y, Z} et pour corps l’ensemble des tuples {X x, Y y, Z z}, tel que le tuple {X x, Y y} appartient à R1 (c'est-à-dire avec la valeur x pour X et la valeur y pour Y), et le tuple {Y y, Z z} appartient à R2 (c'est-à-dire avec la valeur y pour Y et la valeur z pour Z).

En passant aux cas particuliers :

– Si m= p = 0, R1 JOIN R2 dégénère en R1 INTERSECT R2 (intersection) ;

– Si n = 0 (c'est-à-dire si R1 et R2 n’ont aucun attribut en commun), R1 JOIN R2 dégénère en R1 TIMES R2 (produit cartésien).

Mais si n est > 0, au moyen du seul opérateur produit (TIMES), on ne peut pas réaliser la jointure de R1 et R2.

Maintenant, soit R3 la relation résultant du produit de R1 et R2, d’en-tête

{X1, X2, ..., Xm, Y1, Y2, ..., Yn Y’1, Y’2, ..., Y’n, Z1, Z2, ..., Zp}

dans lequel il aura fallu renommer en Y’1, Y’2, ..., Y’n les attributs Y1, Y2, ..., Yn de R2.

A partir du produit :

R3 = R1 TIMES R2

pour parvenir à réaliser la jointure R1 JOIN R2 il est nécessaire d’effectuer en plus une 2e opération, une restriction portant sur R3, c'est-à-dire faire intervenir l’opérateur RESTRICT (WHERE) avec R3 pour opérande :

R3 WHERE p

Où p est une expression booléenne, en fait un prédicat qui est la condition de restriction :

Y1 = Y’1 AND Y2 = Y’2 AND ... Yn = Y’n

Cette 2e opération correspond-elle au raffinement dont tu parles ?

[fsmrel]

Salve Philippe,

Je ne vois pas bien l'intérêt des AND dans la première condition de jointure ici présente.

Comme je l’ai écrit ici, l’optimiseur doit être à même d’expertiser la requête et de la simplifier la condition de restriction avec sa palanquée de AND, puisqu’il a toutes les billes en main pour cela, grâce catalogue relationnel. En tout cas, comme aurait dit le pilote du vol DC1-32, ça reste suspicieux...

[escartefigue]

Salve Philippe,

Comme je l’ai écrit ici, l’optimiseur doit être à même d’expertiser la requête et de la simplifier la condition de restriction avec sa palanquée de AND, puisqu’il a toutes les billes en main pour cela, grâce catalogue relationnel. En tout cas, comme aurait dit le pilote du vol DC1-32, ça reste suspicieux...

Sans aucun doute, mais si l'optimiseur fait le ménage sans effort, le développeur n'a pas les mêmes automatismes ni la même facilité à se débarrasser du code inutile.

[SQLpro]

Cette 2e opération correspond-elle au raffinement dont tu parles ?

OUI...

En gros :

Produit cartésien :
...
X TIMES Y

Produit cartésien "raffiné" :
...
X TIMES Y
WHERE somme_attribute comparizon_operator some_value

Jointure :
...
X JOIN Y WHERE somme_attribute comparizon_operator some_value

Pour la jointure externe :
...
X { LEFT | RIGHT | FULL } [OUTER] JOIN Y WHERE somme_attribute comparizon_operator some_value

Question : quel est l'équivalent, en "pur" relationnel ??? (sachant que en AR le NULL n'existe pas...)... Ok il y a l'UNION... À voir !

A +

[fsmrel]

Produit cartésien "raffiné" :
...
X TIMES Y
WHERE somme_attribute comparizon_operator some_value

Ce produit cartésien "raffiné" est-il décrit de façon formelle dans la norme SQL ?

Quoi qu’il en soit, dans ce que tu présentes, l’opération de restriction (WHERE) ne permet pas de réaliser une jointure, puisque « some_value » met manifestement en jeu une valeur et non pas un attribut (une variable).

En l’état des choses, je suis désolé, mais :

« Une jointure interne est un raffinement du produit cartésien » est un énoncé faux.

Si tu remplaces « some_value » par «some_attribute » alors on retrouve l’opération de restriction (WHERE), mais qui agit en complément de TIMES : il faut bien deux opérations pour réaliser la jointure, ce qui confirme que TIMES à lui seul ne suffit pas.

quel est l'équivalent, en "pur" relationnel ??? (sachant que en AR le NULL n'existe pas...)...

En relationnel, on utilise les RVA (Relation Valued Attribute). Vois ici et surtout les développements dans les ouvrages de référence Databases, Types, and the Relational Model, The Third Manifesto et Database Explorations (chapitre 8, Setting the Record Straight (Part 5 of 6): Relation Valued Attributes, Dispensing with outer join).

[fsmrel]

Salve capitaine,

si l'optimiseur fait le ménage sans effort, le développeur n'a pas les mêmes automatismes ni la même facilité à se débarrasser du code inutile.

Faciliter la vie du développeur, c’est bien pour ça que, dès 1974, D. Chamberlin et son équipe ont inventé l’optimiseur ! lequel n’existait évidemment pas dans les systèmes prérelationnels (fondamentalement procéduraux et exigeant de fortes compétences quant au SGBD, j’ai donné !). Le prototype System R a beaucoup servi à la mise au point de la chose (et bien entendu de sa mémoire, le catalogue relationnel).

Je cite Access Path Selection in a Relational Database Management System :

« In System R a user need not know how the tuples are physically stored and what access paths are available (e.g. which columns have indexes). SQL statements do not require the user to specify anything about the access path to be used for tuple retrieval. Nor does a user specify in what order joins are to be performed. The System R optimizer chooses both join order and an access path for each table in the SQL statement. Of the many possible choices, the optimizer chooses the one which minimizes “total access cost” for performing the entire statement. »

14 ans plus tard, avec DB2 V2 on nous vantait les mérites de l’« optimisation sémantique » (ça fait chic !), de la jointure transitive, consistant à l’enrichissement de nos requêtes, sous le capot, à l’aide de prédicats de jointure supplémentaires, pour bénéficier de la mise en œuvre d’index qui autrement n’auraient malheureusement servi à rien.

Conseil de lecture : A History and Evaluation of System R.

A voir aussi : Optimisation de Requêtes du professeur Georges Gardarin.