Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algèbre relationnelle Skander Zannad et Judicaël Courant 2014-04-12 1 Résumé de

Algèbre relationnelle Skander Zannad et Judicaël Courant 2014-04-12 1 Résumé des épisodes précédents 1. MCD / MLD ; 2. Implantation en SQL (MPD) et requêtes ; 3. Calcul relationnel pour modéliser les requêtes. 2 Problème Expressivité de SQL ? Calcul relationnel modélise les requêtes qu’on veut faire ; Algèbre relationnelle modélise les requêtes que SQL peut faire. 3 Algèbre relationnelle Algèbre : on étudie des opérations sur les données d’une base (similaire aux LCI). Neuf opérations : 1. sélection) ; 2. projection ; 3. renommage ; 4. produit cartésien ; 5. division cartésienne ; 6. jointure (naturelle) ; 7. union ; 8. intersection ; 9. différence. 1 3.1 Sélection Quelles sont les personnes dont le prénom est «Clint» ? Pour répondre à la question, on sélectionne, dans la table PERSONNE, les nuplets dont le champ nom est «Clint». Déﬁnition 3.1.1 (Sélection). Pour A, B ∈att et a ∈dom, on appelle opérations de sélection σA=a (resp. σA=B), les fonctions déﬁnies par σA=a(I) = { t ∈I | t(A) = a } (resp. σA=B(I) = { t ∈I | t(A) = t(B) }) pour toute relation I ayant au moins A (resp. et B) comme attribut(s). 3.2 Projection Quels sont les numéros des personnes qui sont des réalisateurs ? Pour répondre à la question, il sufﬁt de prendre la colonne idrealisateur de la table FILM. On dit qu’on projette la table ﬁlm sur l’attribut idrealisateur. Déﬁnition 3.2.1 (Projection). Soit n ∈N∗et A1, . . . , An ∈att. On appelle opération de projection sur les attributs A1, . . . , An et on note πA1,...,An l’opération déﬁnie par πA1,...,An(I) = { t[A1 . . . An] | t ∈I } pour toute relation I ayant au moins les attributs A1, . . . , An. 3.3 Renommage Déﬁnition 3.3.1 (Renommage). Soit U un ensemble ﬁni d’attributs. On appelle renommage d’attributs toute f : U →att injective. On appelle alors renommage associé à f d’un nuplet u sur U le nuplet ρf(u) sur f(U) déﬁni par ∀a ∈att ρf(u)(f(a)) = u(a) Autrement dit, si U = { α1, . . . , αp }, pour tous v1, . . . , vp ∈dom, on a ρf(⟨α1 : v1, . . . , αp : vp⟩) = ⟨f(α1) : v1, . . . , f(αp) : vp⟩ 2 On appelle opération de renommage ρf associée à f l’opération déﬁnie par ρf(I) = { ρf(u) | u ∈I } pour toute relation I sur U. Souvent : — U est clair d’après le contexte ; — et f laisse invariant tous les éléments de U sauf n éléments A1, . . . , An dont les images respectives sont B1, . . . , Bn. l’opération de renommage ρf est alors notée ρA1→B1,...,An→Bn 3.4 Produit cartésien En mathématiques, A × B désigne l’ensemble des couples (x, y) pour x ∈A et y ∈B. Ici, ce sera l’ensemble des x ⊕y où x ⊕y désigne la concaténation des deux nuplets x et y, supposés n’avoir aucun attribut commun : Déﬁnition 3.4.1 (Produit cartésien). Soit I et J deux relations de sorts U et V avec U ∩V = ∅. On note I × J la relation de sort U ∪V déﬁnie par I × J = { u ⊕v | u ∈I et v ∈J } = { u : U ∪V →att | u[U] ∈I et u[V ] ∈J } 3.5 Division cartésienne Notons : — J[nomtitre] l’ensemble des ⟨nom : n, titre : t⟩pour n nom d’une personne et t ﬁlm tel que n a joué dans t et Clint Eastwood a réalisé t ; — P[nom] l’ensemble des ⟨nom : n⟩pour n nom d’une personne (P = πnom(PERSONNE)) ; — E[titre] l’ensemble des ⟨titre : t⟩pour t ﬁlm de Clint Eastwood. — K[nom] l’ensemble ⟨nom : n⟩pour n ayant joué dans tous les ﬁlms de Clint Eastwood. K est la plus grande relation sur { nom } vériﬁant K × E ⊂J. Cette relation est appelée division cartésienne de J par E. 3 Déﬁnition 3.5.1 (Division cartésienne). Soit I et J deux relations, respectivement sur U et V avec U ⊂V . Alors la division cartésienne de J par I est la relation sur V \ U notée J ÷ I et déﬁnie par : J ÷ I = { t : V \ U →att | ∀u ∈I u ⊕t ∈J } = { t : V \ U →att | ∀u ∈I∃v ∈J v[U] = u et v[V \ U] = t } 3.6 Jointure simple Quels sont les titres des ﬁlms réalisés par des personnes dont le prénom est «Clint» ? Pour répondre : 1. on calcule I = σprenom=”Clint”(PERSONNE) ; 2. on calcule J = πtitre,idrealisateur(FILM) ; 3. on calcule le produit I × J ; 4. on calcule la sélection S = σid=idrealisateur(I × J) ; 5. le résultat est πtitre(S). Les étapes 3 et 4 constituent un calcul de jointure. Déﬁnition 3.6.1 (Jointure). Soit I et J deux relations de sorts U et V avec U ∩V = ∅, A ∈U et B ∈V . Alors la jointure symétrique de I et J selon (A, B) est la relation I[A = B]J de sort U ∪V déﬁnie par I[A = B]J = σA=B(I × J) La jointure : — N’apporte aucune expressivité par rapport au produit suivi d’une sélection ; — En général, se calcule plus facilement (si on s’y prend bien). Exemple : prenez un annuaire téléphonique de Lyon et la liste des enseignants de MPSI, calculez la jointure sur le couple nom de l’enseignant/nom de l’abonné : — par produit puis sélection ; — directement. 3.7 Union Même déﬁnition qu’en mathématiques. Quels sont les personnes dont le prénom est «Clint» ou «Martin» ? σprenom=”Clint”(PERSONNE) ∪σprenom=”Martin”(PERSONNE) 4 3.8 Intersection Déﬁnition mathématique habituelle. Quelles sont les personnes dont le prénom est «Clint» et le nom «Eastwood» ? σprenom=”Clint”(PERSONNE) ∩σnom=”Eastwood”(PERSONNE) NB : il est souvent plus simple de combiner deux opérations de sélection. Par exemple ici : σprenom=”Clint”(σnom=”Eastwood”(PERSONNE)) 3.9 Diﬀérence Déﬁnition mathématique habituelle. Les personnes qui ont réalisé un ﬁlm : I = πid,nom,prenom,datenaissance(PERSONNE[id = idrealisateur]FILM) Quelles sont les personnes qui n’ont réalisé aucun ﬁlm ? PERSONNE \ I 4 Théorème de Codd Les deux questions qui nous intéressent : 1. Étant donné une requête exprimée en calcul relationnel, l’ensemble répondant à cet requête peut-il être exprimé comme une expression de l’algèbre relationnelle ? 2. Étant donné une expression de l’algèbre relationnelle, l’ensemble qu’elle repré- sente peut-il être exprimé comme l’ensemble répondant à une requête en calcul relationnel ? Théorème 4.0.1 (de Codd). Une requête est exprimable en calcul relationnel si et seulement si elle peut être exprimée par une expression de l’algèbre relationnelle. Mieux : la démonstration de ce théorème repose sur un algorithme de traduction qui donne un moyen effectif de passer de l’un à l’autre. Idée de l’algorithme de traduction calcul vers algèbre : ramener la traduction d’une formule à la traduction de sous-formules. Exemple : pour une requête { t1, . . . , tn | φ ∧ψ }, on traduit les requêtes { t1, . . . , tn | φ } et { t1, . . . , tn | ψ } en des expressions calculant des relations I1 et I2, puis on calcule I1 ∩I2. Opérations associées au différentes formules : 5 1. A atomique : c’est déjà une relation 2. φ ∧ψ : ∩ 3. φ ∨ψ : ∪ 4. φ ⇒ψ : traduire ¬φ ∨ψ 5. ¬φ : différence 6. ∃x φ : projection (on oublie le champ x) 7. ∀x φ : division (par une table contenant tous les x) ou traduire ¬∃x¬φ. 5 SQL et l’algèbre relationnelle La question initiale : Quelle est l’expressivité de SQL ? Nous n’y avons pas vraiment répondu : SQL n’est ni le calcul relationnel, ni l’algèbre relationnelle. Mais : — la traduction SQL vers calcul relationnel très facile ; — la traduction algèbre relationnelle vers SQL facile ; — la traduction SQL vers algèbre relationnelle facile. 5.1 Traduction de l’algèbre relationnelle vers SQL Exercices : sur des exemples, comment traduire : 5.1.1 Sélection σid=3(PERSONNE) 5.1.2 Renommage σid→idrealisateur(PERSONNE) 5.1.3 Projection πnom(PERSONNE) 5.1.4 Produit cartésien PERSONNE × FILM 6 5.1.5 Jointure PERSONNE[id = idrealisateur]FILM Jointure implicite : SELECT ∗FROM PERSONNE , FILM WHERE PERSONNE . id = idrealisateur ; Jointure explicite : SELECT ∗FROM PERSONNE INNER JOIN FILM ON id = idrealisateur ; SELECT ∗FROM PERSONNE JOIN FILM ON id = idrealisateur ; 5.1.6 Union, intersection, diﬀérence πnom(PERSONNE) ∪πnom(PERSONNAGE) SELECT nom FROM PERSONNE UNION SELECT nom FROM PERSONNAGE ; Intersection : INTERSECT Différence : EXCEPT Requête sans intérêt mais à la syntaxe incorrecte : PERSONNE UNION PERSONNE ; On doit toujours avoir un «SELECT» : SELECT ∗FROM PERSONNE UNION SELECT ∗FROM PERSONNE ; 5.1.7 Division cartésienne On veut l’ensemble des ⟨nom : n⟩pour n ayant joué dans tous les ﬁlms de Clint Eastwood. Malheureusement : pas d’opérateur de division dans SQL ! Possibilité : calculer d’abord l’ensemble des ⟨nom : n⟩pour n uploads/Industriel/ 24-bd-algebre-relationnelle-poly.pdf