1 <?xml version="1.0" encoding="utf-8" ?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
3 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"
5 <!ENTITY in "<small style='font-size:small'>∈</small>">
6 <!ENTITY notin "<small style='font-size:small'>∉</small>">
10 <html xmlns="http://www.w3.org/1999/xhtml" >
12 <title>Rappels</title>
14 <meta http-equiv="Content-Type"
15 content="text/html; charset=utf-8" />
16 <meta name="copyright"
17 content="Copyright © 2013 Kim Nguyễn" />
20 <script src="../jquery-2.0.3.min.js" type="text/javascript" ></script>
21 <script src="../libs/raphael-min.js" type="text/javascript" ></script>
22 <!-- Load the library -->
23 <script src="../simpleWebSlides.js" type="text/javascript" ></script>
25 <link rel="stylesheet" href="../simpleWebSlides.css" type="text/css" media="all" />
26 <!-- Load a custom Theme, the class-element marks this style-sheet
27 a "theme" that can be swtiched dynamicaly -->
28 <link class="sws-theme" rel="stylesheet" title="U-Psud style" href="../themes/uPsud.css" type="text/css" />
30 <!-- Customize some templates and initialize -->
32 <script type="text/javascript">
33 SWS.Config['sws-slide-change'] = SWS.Effects.slideChangeFadeOutIn;
34 SWS.Config['sws-object-deactivate'] = SWS.Effects.objectDeactivateFadeOut;
35 SWS.Config['sws-object-activate'] = SWS.Effects.objectActivateFadeIn;
37 //Ensures that we load SWS at the very end, after MathJax has
40 $(window).load(SWS.Presentation.init);
44 <div class="sws-slide sws-cover sws-option-nofooter">
45 <h1>Bases de données</h1>
46 <h3>Polytech Paris-Sud</h3>
47 <h3>Apprentis 4<sup>ème</sup> année</h3>
48 <h1>Cours 1 : Généralités & rappels</h1>
49 <a href="mailto:kn@lri.fr">kn@lri.fr</a><br/>
50 <a href="http://www.lri.fr/~kn/">http://www.lri.fr/~kn</a>
54 <div class="sws-slide">
57 Le but du cours est de donner une formation avancée sur un
58 aspects central des bases de données : <em>l'évaluation de
59 requêtes</em>. Le plan suivi par le cours est le suivant:
62 <li>Rappels de l'algèbre relationnelle et d'SQL (rapide)</li>
63 <li>Propriétés physiques des disques (Rotatifs, SSD), notion
64 de page mémoire, hierarchie d'accès mémoire</li>
65 <li>Index: généralités, coût, structures de données (Arbres
66 B+, Hash Index, Bitmap Index)</li>
67 <li>Algorithmes de jointure</li>
68 <li>Plan de requête et optimisations algébriques</li>
69 <li>Bonus: ce que vous voulez (XML, Cloud, J2SE, …)</li>
72 <div class="sws-slide">
73 <h1>Organisation du cours</h1>
74 <p>9 séances de <em>4h:</em></p>
76 <table class="btable" style="width:90%">
82 <td>3/2</td><td>Cours/TD</td> <td>13h-17h</td></tr>
83 <tr><td>5/2</td><td> Cours/TD</td> <td>8h-12h</td></tr>
84 <tr><td>6/2</td><td> TP</td> <td>au PUIO, 13h-17h</td></tr>
85 <tr><td>10/2</td><td> Cours/TD</td> <td>13h-17h</td></tr>
86 <tr><td>12/2</td><td> TP</td> <td>au PUIO, 8h-12h</td></tr>
87 <tr><td>13/2</td><td> TP</td> <td>au PUIO, 13h-17h</td></tr>
88 <tr><td>31/3</td><td> Cours/TD</td> <td>13h-17h</td> </tr>
89 <tr><td>3/4</td><td> TP</td> <td>au PUIO, 13h-17h</td></tr>
90 <tr><td>9/4</td><td> Cours bonus/<em>exam</em></td> <td>8h-12h</td></tr>
93 <ul><li>Cours/TD : Kim Nguyen</li>
94 <li>TP: Andres Romero (certains TP seront <em>notés</em>)</li></ul>
96 <h1>Algèbre relationnelle</h1>
97 <div class="sws-slide">
98 <h1>Qu'est-ce que l'algèbre relationnelle?</h1>
99 <p class="sws-pause" >Une <em>algèbre</em> (ou <em>structure algébrique</em>) est un
100 <em>ensemble d'objets</em> (que l'on étudie) muni d'un ensemble
101 d'<em>opérations</em> (qui permettent de manipuler les objets)</p>
103 <p class="sws-pause" >Les objets manipulés par l'algèbre
104 relationnelle sont les <em>relations</em> <i>i.e.</i>
105 des <em>ensembles de n-uplets</em>.</p>
106 <p class="sws-pause" style="font-size:80%">(Rappel: une
107 relation n-aire est juste un ensemble de n-uplets. Par exemple,
108 la relation d'égalité sur les entiers est l'ensemble qui
110 couples <tt>(0,0)</tt>, <tt>(1,1)</tt>, <tt>(2,2)</tt>… )</p>
111 <p>On ne considère que des relations <em>finies</em>, sur des
112 n-uplets <em>fixes</em> dont les composantes ont un
113 type <em>simple</em></p>
114 <p><code>{ (1, "Kim", 32, T), (3,"Foo", 28, F), (2, "Bar", 77, T) }</code></p>
115 <ul class="sws-pause" style="background:white;">
116 <li>Les relations représentent des tables: ensemble
118 <li>Les relations contiennent des n-uplets de la même
120 <li>Un n-uplet ne peut pas contenir un ensemble (pas de table
122 <li>(optionel) on ajoute un <em>schema</em> à la relation
123 (ex. <tt>(id, nom, age, prof)</tt>).</li>
126 <div class="sws-slide">
127 <h1>Les opérateurs de l'algèbre relationnelle (1/2)</h1>
128 <p class="sws-pause" style="font-size:80%">(attention, plusieurs
129 présentations possibles)</p>
130 <p><tt>R</tt> et <tt>S</tt> sont deux relations, munies chacune
131 d'un schéma (<tt>ℝ=(a<sub>1</sub>,…,a<sub>m</sub>)</tt>
132 et <tt>𝕊=(b<sub>1</sub>,…,b<sub>n</sub>)</tt>) </p>
133 <p>Opérateurs ensemblistes:
136 <td style="width:25%">Union :</td>
137 <td style="width:40%"><tt><em>R ∪ S</em> ≝ { r | r ∉ R ∨ r ∈ S }</tt></td>
138 <td style="width:25%;text-align:right;">(requiert <tt>ℝ = 𝕊</tt>)</td>
141 <td style="width:25%">Différence :</td>
142 <td style="width:40%"><tt><em>R ∖ S</em> ≝ { r | r ∈ R ∧ r ∉ S }</tt></td>
143 <td style="width:25%;text-align:right;">(requiert <tt>ℝ = 𝕊</tt>)</td>
146 <td style="width:25%">Produit :</td>
147 <td style="width:40%;text-align:right;"><tt><em>R × S</em> ≝ {
148 (r<sub>1</sub>,…,r<sub>m</sub>,s<sub>1</sub>,…,s<sub>n</sub>)
150 (r<sub>1</sub>,…,r<sub>m</sub>) ∈ R ∧
151 (s<sub>1</sub>,…,s<sub>n</sub>) ∈ S }</tt></td>
152 <td style="width:25%;text-align:right;"></td>
156 <p class="sws-pause">Q1: A-t-on besoin de l'intersection ? (<tt>R ∩ S</tt>)
158 <p class="sws-pause">R1: Non car <tt>R ∩ S = (R ∪ S) ∖ ((S ∖ R)∪(R ∖ S)) </tt>
161 <div class="sws-slide">
162 <h1>Les opérateurs de l'algèbre relationnelle (2/2)</h1>
163 <p class="sws-pause" style="font-size:80%">(attention, plusieurs
164 présentations possibles)</p>
165 <p><tt>R</tt> est une relation, munie
166 d'un schéma (<tt>ℝ=(a<sub>1</sub>,…,a<sub>m</sub>)</tt>) </p>
167 <p>Opérateurs relationnels:
170 <td style="width:20%">Projection :</td>
171 <td style="width:54%"><tt><em>π<sub>a<sub>1</sub>,…,a<sub>k</sub></sub></em>(R)
172 ≝ { (r.a<sub>1</sub>,…,r.a<sub>k</sub>) | r ∈ R }</tt></td>
173 <td style="width:20%;text-align:right;"></td>
176 <td >Sélection :</td>
177 <td ><tt><em>σ<sub>φ</sub></em>(R) ≝ { r ∈ R | σ(r) }</tt></td>
178 <td style="text-align:right;">σ est une formule
179 logique sur <tt>r</tt></td>
182 <td >Renommage :</td>
183 <td ><tt><em>ρ<sub>a<sub>1</sub>↦b<sub>1</sub>,…</sub></em>(R)</tt>
184 associe R au schéma <tt>ℝ'=(b<sub>1</sub>,…)</tt></td>
185 <td style="text-align:right;"></td>
190 <div class="sws-slide">
191 <h1>Opérateurs dérivés</h1>
192 <p><tt>R</tt> et <tt>S</tt> sont deux relations, munies chacune
193 d'un schéma (<tt>ℝ</tt> et <tt>𝕊</tt>) </p>
195 <li>Jointure: <tt>ℝ=(a<sub>1</sub>,…,a<sub>m</sub>,c<sub>1</sub>,…,c<sub>l</sub>)</tt>
196 et <tt>𝕊=(b<sub>1</sub>,…,b<sub>n</sub>,c<sub>1</sub>,…,c<sub>l</sub>)</tt><code>
198 (r.a<sub>1</sub>,…,r.a<sub>m</sub>,r.c<sub>1</sub>,…,r.c<sub>l</sub>,s.b<sub>1</sub>,…,s.b<sub>n</sub>)
199 | r ∈ R ∧ s ∈ S ∧ ∀ 1 ≤ i ≤ l, r.c<sub>i</sub> = s.c<sub>i</sub> } </code>
201 <li>Intersection : <tt>R ∩ S = { r | r ∈ R ∧ r ∈ S } </tt></li>
202 <li>Division : <tt>R ÷ S ≝ T</tt>, telle que <tt>T × S ⊆
203 R</tt> (les attributs de <tt>S</tt> sont un sous-ensemble des
204 attributs de <tt>T</tt></li>
207 <div class="sws-slide">
208 <h1>Pourquoi utiliser l'algèbre relationnelle ?</h1>
210 <li>Modèle abstrait qui permet de raisonner sur les requêtes
211 sans se soucier de la syntaxe</li>
212 <li>Permet de déduire des <em>optimisations
214 <p>Par exemple:<code>
215 σ<sub>φ</sub>(R ∪ S) = σ<sub>φ</sub>(R) ∪ σ<sub>φ</sub>(S)
217 Avantageux si <tt>R</tt> et <tt>S</tt> ont beaucoup
218 d'éléments mais que σ<sub>φ</sub> en séléctionne peu.
224 <div class="sws-slide">
226 <p>SQL (<i>Structured Query Language</i>) est un langage de
227 programmation dédié permettant de manipuler les données d'une BD
228 relationnelle. Il permet de:
230 <ul><li>Créer et détruire des tables</li>
231 <li>Insérer, supprimer, modifier des lignes d'une table</li>
232 <li>Interroger des tables</li>
237 <div class="sws-slide">
238 <h1>SQL <tt>≠</tt> Algèbre relationnelle</h1>
240 <li>Table <tt>≠</tt> Relation : <span class="sws-pause">les tables peuvent
241 avoir plusieurs copies de la même ligne, alors que les
242 relations sont des ensembles</span></li>
243 <li>Opérations de comptage, d'agrégat, groupage, … </li>
244 <li>Les types sont finis et ont toujours une taille fixe
245 (<tt>INTEGER</tt>, <tt>VARCHAR[40]</tt>, <tt>DATE</tt>, …)</li>
248 <div class="sws-slide">
249 <h1>Création/destruction de table</h1>
251 <em>CREATE TABLE</em> <i>MaTable</i> (
252 <i>att<sub>1</sub></i> <i>type<sub>1</sub></i> [<i>constr_col<sub>1</sub></i>], …, <i>att<sub>n</sub></i> <i>type<sub>n</sub></i> [<i>constr_col<sub>n</sub></i>]
253 [, <i>constr_table</i>]);</code></p>
255 <li><tt>MaTable</tt> : nom de la table </li>
256 <li><tt><i>att<sub>i</sub></i></tt> : nom de l'attribut <i>i</i></li>
257 <li><tt><i>att<sub>i</sub></i></tt> : type de
258 l'attribut <i>i</i>. Exemples de
259 types: <tt>INTEGER</tt>, <tt>VARCHAR[<i>n</i>]</tt>, … (<s>dépend du
260 système utlisé</s>)</li>
261 <li><tt><i>constr_col<sub>i</sub></i></tt> : contrainte sur la
262 colonne <i>i</i>. Exemple de contraintes: <tt>PRIMARY
263 KEY</tt>, <tt>NOT NULL</tt>, <tt>DEFAULT <i>n</i>, …</tt></li>
264 <li><tt><i>constr_table</i></tt> : contrainte de table. Exemple de
265 contrainte de table: <tt>CHECK <i>cond</i></tt>, <tt>UNIQUE
266 (<i>col1</i>, …, <i>coln</i>)</tt>, …</li>
269 <em>DROP TABLE</em> <i>Table<sub>1</sub></i>, …, <i>Table<sub>n</sub></i> [<em>CASCADE</em>];</code></p>
270 <ul style="background:white;"><li><tt>CASCADE</tt> : détruit aussi les objets dépendants de la
271 table (vues, autres tables avec clés étrangères, …) (<s>dépend du
272 système utilisé</s>)</li>
275 <div class="sws-slide">
276 <h1>Insertion/suppression/mise à jour</h1>
277 <code> <em>INSERT INTO</em> <i>MaTable</i> [ <em>(</em><i>col<sub>1</sub></i>,…,<i>col<sub>n</sub></i><em>)</em> ] <em>VALUES</em> <em>(</em><i>val<sub>1</sub></i>,…,<i>val<sub>n</sub></i><em>);</em></code>
278 <ul><li>Si la liste de colonnes est précisée les valeurs sont insérées
279 dans les colonnes correspondantes, sinon dans l'ordre du schéma</li></ul>
281 <code> <em>DELETE FROM</em> <i>MaTable</i> [ <em>WHERE</em> <i>condition</i> ];</code>
282 <ul><li>Supprime les lignes pour lesquelles <i><tt>condition</tt></i>
283 est vraie (expression booléene sur les
284 colonnes). Si <tt>WHERE</tt> est absent, supprime toutes les lignes.</li></ul>
286 <code> <em>UPDATE</em> <i>MaTable</i> <em>SET</em> <i>col<sub>1</sub></i><em>=</em><i>val<sub>1</sub></i>, …, <i>col<sub>n</sub></i><em>=</em><i>val<sub>n</sub></i> [ <em>WHERE</em> <i>condition</i> ];</code>
287 <ul><li>Mise à jour de toutes les colonnes <i>i</i> des lignes pour lesquelles <i><tt>condition</tt></i>
288 est vraie (expression booléene sur les
289 colonnes). Si <tt>WHERE</tt> est absent, modifie toutes les lignes.</li></ul>
292 <div class="sws-slide">
293 <h1>Requêtes SQL 1/3</h1>
295 <em>SELECT</em> [<em>ALL</em>|<em>DISTINCT</em>] <i>res<sub>1</sub></i>, …, <i>res<sub>n</sub></i>
296 <em>FROM</em> <i>tab_ref<sub>1</sub></i>, …, <i>tab_ref<sub>m</sub></i>
297 [<em>WHERE</em> <i>condition_w</i>]
298 [<em>GROUP BY</em> <i>col<sub>1</sub></i>, …, <i>col<sub>k</sub></i>]
299 [<em>HAVING </em> <i>condition_h</i>]
300 [<em>ORDER BY</em> <i>col<sub>1</sub></i>, …, <i>col<sub>;</sub></i> [<em>ASC</em>|<em>DESC</em>]]</code>
302 <li><tt>ALL</tt> force à garder tous les
303 résultats, <tt>DISTINCT</tt> retire les doublons</li>
304 <li><i>res<sub>i</sub></i> peut être un nom de colonne, <tt>*</tt>
305 (toutes les colones), un agrégat (<tt>SUM(price)</tt>,
306 éventuellement nommé : <tt>AS TotalPrice</tt>)</li>
307 <li><i>tab_ref<sub>i</sub></i> est soit un nom de table, soit une
308 sous-requête (<tt>(SELECT … )</tt>) éventuellement nommé (<tt>AS T1</tt>)</li>
309 <li><i>condition_w</i> est une condition booléenne sur les attributs
310 des <i>m</i> tables mentionnées</li>
311 <li><tt>GROUP BY</tt> et <tt>HAVING</tt> définissent des conditions
313 <li><tt>ORDER BY</tt> trie les résultats en ordre croissant (par
314 défaut ou <tt>ASC</tt>) ou décroissant (<tt>DESC</tt>)</li>
317 <div class="sws-slide">
318 <h1>Requêtes SQL 2/3</h1>
320 <em>(</em><i>req<sub>1</sub></i><em>)</em> <em>UNION</em> [<em>ALL</em>] <em>(</em><i>req<sub>2</sub></i><em>)</em>
321 <em>(</em><i>req<sub>1</sub></i><em>)</em> <em>INTERSECT</em> <em>(</em><i>req<sub>2</sub></i><em>)</em>
322 <em>(</em><i>req<sub>1</sub></i><em>)</em> <em>EXCEPT</em> <em>(</em><i>req<sub>2</sub></i><em>)</em>
324 <p>Union, intersection et différence de deux requêtes. Par défaut,
325 retire les doublons des résultats des requêtes (comportement
326 ensembliste) sauf pour <tt>UNION ALL</tt> ou si <tt>SELECT ALL</tt>
327 a été utilisé dans les sous-requêtes</p>
329 <div class="sws-slide">
330 <h1>Requêtes SQL 3/3</h1>
331 <p>Exemple de conditions de groupage. On considère une table
332 d'employés (<tt>nom</tt>), appartenant chacun à un département
333 (<tt>num_dept</tt>) et ayant chacun un salaire (<tt>sal</tt>). On
334 souhaite avoir les salaires moyens, pour chaque département, pour
335 les départements ayant plus de 10 employés.</p>
338 SELECT num_dept, AVERAGE(sal)
341 HAVING COUNT(nom) >= 10;
343 <p><tt>HAVING</tt> est nécessaire car la clause <tt>WHERE</tt>
344 s'applique ligne à ligne, ici on veut groupe à groupe (i.e. pour
345 chaque département, i.e. pour toutes les lignes qui ont le même