bd/bd01.xhtml

   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"
   4 [
   5           <!ENTITY in  "<small style='font-size:small'>∈</small>">
   6           <!ENTITY notin  "<small style='font-size:small'>∉</small>">
   7           <!ENTITY mapsto  "↦">
   8 ]
   9           >
  10 <html xmlns="http://www.w3.org/1999/xhtml" >
  11   <head>
  12     <title>Rappels</title>
  13
  14     <meta http-equiv="Content-Type"
  15           content="text/html; charset=utf-8" />
  16     <meta name="copyright"
  17           content="Copyright &#169; 2013 Kim Nguyễn" />
  18
  19     <!-- Load jQuery -->
  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>
  24
  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" />
  29
  30     <!-- Customize some templates and initialize -->
  31
  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;
  36
  37       //Ensures that we load SWS at the very end, after MathJax has
  38       //been initialized
  39
  40       $(window).load(SWS.Presentation.init);
  41     </script>
  42   </head>
  43   <body>
  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 &amp; 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>
  51     </div>
  52
  53     <h1>Avant-propos</h1>
  54     <div class="sws-slide">
  55       <h1>But du cours</h1>
  56       <p>
  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:
  60       </p>
  61       <ul>
  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>
  70       </ul>
  71     </div>
  72     <div class="sws-slide">
  73       <h1>Organisation du cours</h1>
  74       <p>9 séances de <em>4h:</em></p>
  75       <p>
  76       <table class="btable" style="width:90%">
  77         <tr><th >Date</th>
  78             <th >Type</th>
  79             <th >Heure</th>
  80         </tr>
  81         <tr>
  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>
  91       </table>
  92       </p>
  93       <ul><li>Cours/TD : Kim Nguyen</li>
  94       <li>TP: Andres Romero (certains TP seront <em>notés</em>)</li></ul>
  95     </div>
  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>
 102
 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
 109       contient tous les
 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
 117         finis </li>
 118         <li>Les relations contiennent des n-uplets de la même
 119         taille</li>
 120         <li>Un n-uplet ne peut pas contenir un ensemble (pas de table
 121         dans une table)</li>
 122         <li>(optionel) on ajoute un <em>schema</em> à la relation
 123         (ex. <tt>(id, nom, age, prof)</tt>).</li>
 124       </ul>
 125     </div>
 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:
 134       <table>
 135         <tr>
 136           <td style="width:25%">Union :</td>
 137           <td style="width:40%"><tt><em>R ∪ S</em> ≝ { r | r &notin; R ∨ r &in; S }</tt></td>
 138           <td style="width:25%;text-align:right;">(requiert <tt>ℝ = 𝕊</tt>)</td>
 139         </tr>
 140         <tr>
 141           <td style="width:25%">Différence :</td>
 142           <td style="width:40%"><tt><em>R ∖ S</em> ≝ { r | r &in; R ∧ r &notin; S  }</tt></td>
 143           <td style="width:25%;text-align:right;">(requiert <tt>ℝ = 𝕊</tt>)</td>
 144         </tr>
 145         <tr>
 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>)
 149           | <br/>
 150               (r<sub>1</sub>,…,r<sub>m</sub>) &in; R ∧
 151               (s<sub>1</sub>,…,s<sub>n</sub>) &in; S  }</tt></td>
 152           <td style="width:25%;text-align:right;"></td>
 153         </tr>
 154       </table>
 155       </p>
 156       <p class="sws-pause">Q1: A-t-on besoin de l'intersection ? (<tt>R ∩ S</tt>)
 157       </p>
 158       <p class="sws-pause">R1: Non car <tt>R ∩ S = (R ∪ S) ∖ ((S ∖ R)∪(R ∖ S))  </tt>
 159       </p>
 160     </div>
 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:
 168       <table>
 169         <tr>
 170           <td style="width:20%">Projection :</td>
 171           <td style="width:54%"><tt><em>&pi;<sub>a<sub>1</sub>,…,a<sub>k</sub></sub></em>(R)
 172           ≝ { (r.a<sub>1</sub>,…,r.a<sub>k</sub>) | r &in; R }</tt></td>
 173           <td style="width:20%;text-align:right;"></td>
 174         </tr>
 175         <tr>
 176           <td >Sélection :</td>
 177           <td ><tt><em>&sigma;<sub>&phi;</sub></em>(R) ≝ { r &in; R | &sigma;(r)  }</tt></td>
 178           <td style="text-align:right;">&sigma; est une formule
 179           logique sur <tt>r</tt></td>
 180         </tr>
 181         <tr>
 182           <td >Renommage :</td>
 183           <td ><tt><em>&rho;<sub>a<sub>1</sub>&mapsto;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>
 186         </tr>
 187       </table>
 188       </p>
 189     </div>
 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>
 194       <ul>
 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>
 197   R ⨝ S ≝ {
 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 &in; R ∧ s &in; S ∧ ∀ 1 ≤ i ≤ l, r.c<sub>i</sub> = s.c<sub>i</sub> }   </code>
 200         </li>
 201         <li>Intersection : <tt>R ∩ S = { r | r &in; R ∧ r &in; 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>
 205       </ul>
 206     </div>
 207     <div class="sws-slide">
 208       <h1>Pourquoi utiliser l'algèbre relationnelle ?</h1>
 209       <ul>
 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
 213             algébriques</em>
 214           <p>Par exemple:<code>
 215               &sigma;<sub>&phi;</sub>(R ∪ S) = &sigma;<sub>&phi;</sub>(R) ∪ &sigma;<sub>&phi;</sub>(S)
 216             </code>
 217             Avantageux si <tt>R</tt> et <tt>S</tt> ont beaucoup
 218             d'éléments mais que       &sigma;<sub>&phi;</sub> en séléctionne peu.
 219           </p>
 220         </li>
 221       </ul>
 222     </div>
 223     <h1>SQL</h1>
 224     <div class="sws-slide">
 225       <h1>SQL</h1>
 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:
 229       </p>
 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>
 233         <li>…</li>
 234       </ul>
 235
 236     </div>
 237     <div class="sws-slide">
 238       <h1>SQL <tt>≠</tt> Algèbre relationnelle</h1>
 239       <ul>
 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>
 246       </ul>
 247     </div>
 248     <div class="sws-slide">
 249       <h1>Création/destruction de table</h1>
 250 <p><code>
 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>
 254 <ul>
 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>
 267 </ul>
 268 <p><code>
 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>
 273 </ul>
 274     </div>
 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>
 280
 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>
 285
 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>
 290
 291 </div>
 292     <div class="sws-slide">
 293       <h1>Requêtes SQL 1/3</h1>
 294 <code>
 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>
 301 <ul>
 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
 312   de groupage </li>
 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>
 315 </ul>
 316 </div>
 317     <div class="sws-slide">
 318       <h1>Requêtes SQL 2/3</h1>
 319 <code>
 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>
 323 </code>
 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>
 328     </div>
 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>
 336
 337 <code>
 338     SELECT num_dept, AVERAGE(sal)
 339     FROM TABLE_EMP
 340     GROUP BY num_dept
 341     HAVING COUNT(nom) >= 10;
 342 </code>
 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
 346   departement).</p>
 347 </div>
 348   </body>
 349 </html>