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     <a href="" class="sws-previous"/>
  45     <div class="sws-slide sws-cover sws-option-nofooter">
  46       <h1>Bases de données</h1>
  47       <h3>Polytech Paris-Sud</h3>
  48       <h3>Apprentis 4<sup>ème</sup> année</h3>
  49       <h1>Cours 1 : Généralités &amp; rappels</h1>
  50       <a href="mailto:kn@lri.fr">kn@lri.fr</a><br/>
  51       <a href="http://www.lri.fr/~kn/">http://www.lri.fr/~kn</a>
  52     </div>
  53
  54     <h1>Avant-propos</h1>
  55     <div class="sws-slide">
  56       <h1>But du cours</h1>
  57       <p>
  58       Le but du cours est de donner une formation avancée sur un
  59       aspects central des bases de données : <em>l'évaluation de
  60       requêtes</em>. Le plan suivi par le cours est le suivant:
  61       </p>
  62       <ul>
  63         <li>Rappels de l'algèbre relationnelle et d'SQL (rapide)</li>
  64         <li>Propriétés physiques des disques (Rotatifs, SSD), notion
  65         de page mémoire, hierarchie d'accès mémoire</li>
  66         <li>Index: généralités, coût, structures de données (Arbres
  67         B+, Hash Index, Bitmap Index)</li>
  68         <li>Algorithmes de jointure</li>
  69         <li>Plan de requête et optimisations algébriques</li>
  70         <li>Bonus: ce que vous voulez (XML, Cloud, J2SE, …)</li>
  71       </ul>
  72     </div>
  73     <div class="sws-slide">
  74       <h1>Organisation du cours</h1>
  75       <p>9 séances de <em>4h:</em></p>
  76       <p>
  77       <table class="btable" style="width:90%">
  78         <tr><th >Date</th>
  79             <th >Type</th>
  80             <th >Heure</th>
  81         </tr>
  82         <tr>
  83           <td>2/2</td><td>Cours/TD</td> <td>13h30-17h30</td></tr>
  84         <tr><td>5/2</td><td> Cours/TD</td> <td>8h30-12h30</td></tr>
  85         <tr><td>9/2</td><td> TP</td> <td> 13h30-17h30</td></tr>
  86         <tr><td>12/2</td><td> Cours/TD</td> <td>8h30-12h30</td></tr>
  87         <tr><td>7/4</td><td> TP</td> <td> 8h30-12h30</td></tr>
  88         <tr><td>9/4</td><td> Cours/TD</td> <td>8h30-12h30</td> </tr>
  89         <tr><td>13/4</td><td> Cours/TD</td> <td>12h30-17h30</td> </tr>
  90         <tr><td>14/4</td><td> TP</td> <td> 13h30-17h30</td></tr>
  91         <tr><td>16/4</td><td> Cours bonus/<em>exam</em></td> <td>8h30-12h30</td></tr>
  92       </table>
  93       </p>
  94       <ul><li>Cours/TD : Kim Nguyen</li>
  95       <li>TP: Cécile Pereira (certains TP seront <em>notés</em>)</li></ul>
  96     </div>
  97     <h1>Algèbre relationnelle</h1>
  98     <div class="sws-slide">
  99       <h1>Qu'est-ce que l'algèbre relationnelle?</h1>
 100       <p class="sws-pause" >Une <em>algèbre</em> (ou <em>structure algébrique</em>) est un
 101       <em>ensemble d'objets</em> (que l'on étudie) muni d'un ensemble
 102       d'<em>opérations</em> (qui permettent de manipuler les objets)</p>
 103
 104       <p class="sws-pause" >Les objets manipulés par l'algèbre
 105       relationnelle sont les <em>relations</em> <i>i.e.</i>
 106       des <em>ensembles de n-uplets</em>.</p>
 107       <p class="sws-pause" style="font-size:80%">(Rappel: une
 108       relation n-aire est juste un ensemble de n-uplets. Par exemple,
 109       la relation d'égalité sur les entiers est l'ensemble qui
 110       contient tous les
 111       couples <tt>(0,0)</tt>, <tt>(1,1)</tt>, <tt>(2,2)</tt>… )</p>
 112       <p>On ne considère que des relations <em>finies</em>, sur des
 113       n-uplets <em>fixes</em> dont les composantes ont un
 114       type <em>simple</em></p>
 115       <p><code>{ (1, "Kim", 32, T), (3,"Foo", 28, F), (2, "Bar", 77, T) }</code></p>
 116       <ul class="sws-pause" style="background:white;">
 117         <li>Les relations représentent des tables: ensemble
 118         finis </li>
 119         <li>Les relations contiennent des n-uplets de la même
 120         taille</li>
 121         <li>Un n-uplet ne peut pas contenir un ensemble (pas de table
 122         dans une table)</li>
 123         <li>(optionel) on ajoute un <em>schema</em> à la relation
 124         (ex. <tt>(id, nom, age, prof)</tt>).</li>
 125       </ul>
 126     </div>
 127     <div class="sws-slide">
 128       <h1>Les opérateurs de l'algèbre relationnelle (1/2)</h1>
 129       <p class="sws-pause" style="font-size:80%">(attention, plusieurs
 130       présentations possibles)</p>
 131       <p><tt>R</tt> et <tt>S</tt> sont deux relations, munies chacune
 132       d'un schéma (<tt>ℝ=(a<sub>1</sub>,…,a<sub>m</sub>)</tt>
 133       et <tt>𝕊=(b<sub>1</sub>,…,b<sub>n</sub>)</tt>) </p>
 134       <p>Opérateurs ensemblistes:
 135       <table>
 136         <tr>
 137           <td style="width:10%">Union :</td>
 138           <td style="width:40%"><tt><em>R ∪ S</em> ≝ { r | r &in; R ∨ r &in; S }</tt></td>
 139           <td style="width:25%;text-align:right;">(requiert <tt>ℝ = 𝕊</tt>)</td>
 140         </tr>
 141         <tr>
 142           <td style="width:10%">Différence :</td>
 143           <td style="width:40%"><tt><em>R ∖ S</em> ≝ { r | r &in; R ∧ r &notin; S  }</tt></td>
 144           <td style="width:25%;text-align:right;">(requiert <tt>ℝ = 𝕊</tt>)</td>
 145         </tr>
 146         <tr>
 147           <td style="width:10%">Produit :</td>
 148           <td colspan="2" style="width:85%;"><tt><em>R × S</em> ≝
 149  {(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>) &in; R
 151               ∧(s<sub>1</sub>,…,s<sub>n</sub>) &in; S}</tt></td>
 152         </tr>
 153       </table>
 154       </p>
 155       <p class="sws-pause">Q1: A-t-on besoin de l'intersection ? (<tt>R ∩ S</tt>)
 156       </p>
 157       <p class="sws-pause">R1: Non car <tt>R ∩ S = (R ∪ S) ∖ ((S ∖ R)∪(R ∖ S))  </tt>
 158       </p>
 159     </div>
 160     <div class="sws-slide">
 161       <h1>Les opérateurs de l'algèbre relationnelle (2/2)</h1>
 162       <p class="sws-pause" style="font-size:80%">(attention, plusieurs
 163       présentations possibles)</p>
 164       <p><tt>R</tt> est une  relation, munie
 165       d'un schéma (<tt>ℝ=(a<sub>1</sub>,…,a<sub>m</sub>)</tt>) </p>
 166       <p>Opérateurs relationnels:
 167       <table>
 168         <tr>
 169           <td style="width:20%">Projection :</td>
 170           <td style="width:54%"><tt><em>&pi;<sub>a<sub>1</sub>,…,a<sub>k</sub></sub></em>(R)
 171           ≝ { (r.a<sub>1</sub>,…,r.a<sub>k</sub>) | r &in; R }</tt></td>
 172           <td style="width:20%;text-align:right;"></td>
 173         </tr>
 174         <tr>
 175           <td >Sélection :</td>
 176           <td ><tt><em>&sigma;<sub>&phi;</sub></em>(R) ≝ { r &in; R | &sigma;(r)  }</tt></td>
 177           <td style="text-align:right;">&sigma; est une formule
 178           logique sur <tt>r</tt></td>
 179         </tr>
 180         <tr>
 181           <td >Renommage :</td>
 182           <td ><tt><em>&rho;<sub>a<sub>1</sub>&mapsto;b<sub>1</sub>,…</sub></em>(R)</tt>
 183           associe R au schéma <tt>ℝ'=(b<sub>1</sub>,…)</tt></td>
 184           <td style="text-align:right;"></td>
 185         </tr>
 186       </table>
 187       </p>
 188     </div>
 189     <div class="sws-slide">
 190       <h1>Opérateurs dérivés</h1>
 191       <p><tt>R</tt> et <tt>S</tt> sont deux relations, munies chacune
 192       d'un schéma (<tt>ℝ</tt> et  <tt>𝕊</tt>) </p>
 193       <ul>
 194         <li>Jointure: <tt>ℝ=(a<sub>1</sub>,…,a<sub>m</sub>,c<sub>1</sub>,…,c<sub>l</sub>)</tt>
 195         et <tt>𝕊=(b<sub>1</sub>,…,b<sub>n</sub>,c<sub>1</sub>,…,c<sub>l</sub>)</tt><code>
 196   R ⨝ S ≝ {
 197           (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>)
 198            | r &in; R ∧ s &in; S ∧ ∀ 1 ≤ i ≤ l, r.c<sub>i</sub> = s.c<sub>i</sub> }   </code>
 199         </li>
 200         <li>Intersection : <tt>R ∩ S = { r | r &in; R ∧ r &in; S } </tt></li>
 201         <li>Division : <tt>R ÷ S ≝ T</tt>, telle que <tt>T × S ⊆
 202         R</tt> (les attributs de <tt>S</tt> sont un sous-ensemble des
 203         attributs de <tt>T</tt></li>
 204       </ul>
 205     </div>
 206     <div class="sws-slide">
 207       <h1>Pourquoi utiliser l'algèbre relationnelle ?</h1>
 208       <ul>
 209         <li>Modèle abstrait qui permet de raisonner sur les requêtes
 210           sans se soucier de la syntaxe</li>
 211         <li>Permet de déduire des <em>optimisations
 212             algébriques</em>
 213           <p>Par exemple:<code>
 214               &sigma;<sub>&phi;</sub>(R ∪ S) = &sigma;<sub>&phi;</sub>(R) ∪ &sigma;<sub>&phi;</sub>(S)
 215             </code>
 216             Avantageux si <tt>R</tt> et <tt>S</tt> ont beaucoup
 217             d'éléments mais que &sigma;<sub>&phi;</sub> en sélectionne peu.
 218           </p>
 219         </li>
 220       </ul>
 221     </div>
 222     <h1>SQL</h1>
 223     <div class="sws-slide">
 224       <h1>SQL</h1>
 225       <p>SQL (<i>Structured Query Language</i>) est un langage de
 226       programmation dédié permettant de manipuler les données d'une BD
 227       relationnelle. Il permet de:
 228       </p>
 229       <ul><li>Créer et détruire des tables</li>
 230         <li>Insérer, supprimer, modifier des lignes d'une table</li>
 231         <li>Interroger des tables</li>
 232         <li>…</li>
 233       </ul>
 234
 235     </div>
 236     <div class="sws-slide">
 237       <h1>SQL <tt>≠</tt> Algèbre relationnelle</h1>
 238       <ul>
 239         <li>Table  <tt>≠</tt> Relation : <span class="sws-pause">les tables peuvent
 240         avoir plusieurs copies de la même ligne, alors que les
 241         relations sont des ensembles</span></li>
 242         <li>Opérations de comptage, d'agrégat, groupage, … </li>
 243         <li>Les types sont finis et ont toujours une taille fixe
 244           (<tt>INTEGER</tt>, <tt>VARCHAR(40)</tt>, <tt>DATE</tt>, …)</li>
 245       </ul>
 246     </div>
 247     <div class="sws-slide">
 248       <h1>Création/destruction de table</h1>
 249 <p><code>
 250 <em>CREATE TABLE</em> <i>MaTable</i> (
 251      <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>]
 252      [, <i>constr_table</i>]);</code></p>
 253 <ul>
 254   <li><tt>MaTable</tt> : nom de la table </li>
 255   <li><tt><i>att<sub>i</sub></i></tt> : nom de l'attribut <i>i</i></li>
 256   <li><tt><i>att<sub>i</sub></i></tt> : type de
 257   l'attribut <i>i</i>. Exemples de
 258   types: <tt>INTEGER</tt>, <tt>VARCHAR(<i>n</i>)</tt>, … (<s>dépend du
 259   système utlisé</s>)</li>
 260   <li><tt><i>constr_col<sub>i</sub></i></tt> : contrainte sur la
 261   colonne <i>i</i>. Exemple de contraintes: <tt>PRIMARY
 262   KEY</tt>, <tt>NOT NULL</tt>, <tt>DEFAULT <i>n</i>, …</tt></li>
 263   <li><tt><i>constr_table</i></tt> : contrainte de table. Exemple de
 264   contrainte de table: <tt>CHECK <i>cond</i></tt>, <tt>UNIQUE
 265   (<i>col1</i>, …, <i>coln</i>)</tt>, …</li>
 266 </ul>
 267 <p><code>
 268 <em>DROP TABLE</em> <i>Table<sub>1</sub></i>, …, <i>Table<sub>n</sub></i> [<em>CASCADE</em>];</code></p>
 269 <ul style="background:white;"><li><tt>CASCADE</tt> : détruit aussi les objets dépendants de la
 270     table (vues, autres tables avec clés étrangères, …) (<s>dépend du
 271     système utilisé</s>)</li>
 272 </ul>
 273     </div>
 274     <div class="sws-slide">
 275       <h1>Insertion/suppression/mise à jour</h1>
 276 <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>
 277 <ul><li>Si la liste de colonnes est précisée les valeurs sont insérées
 278     dans les colonnes correspondantes, sinon dans l'ordre du schéma</li></ul>
 279
 280 <code>   <em>DELETE FROM</em> <i>MaTable</i> [ <em>WHERE</em> <i>condition</i> ];</code>
 281 <ul><li>Supprime les lignes pour lesquelles <i><tt>condition</tt></i>
 282     est vraie (expression booléene sur les
 283     colonnes). Si <tt>WHERE</tt> est absent, supprime toutes les lignes.</li></ul>
 284
 285 <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>
 286 <ul><li>Mise à jour de toutes les colonnes <i>i</i> des lignes pour lesquelles <i><tt>condition</tt></i>
 287     est vraie (expression booléene sur les
 288     colonnes). Si <tt>WHERE</tt> est absent, modifie toutes les lignes.</li></ul>
 289
 290 </div>
 291     <div class="sws-slide">
 292       <h1>Requêtes SQL 1/3</h1>
 293 <code>
 294  <em>SELECT</em> [<em>ALL</em>|<em>DISTINCT</em>] <i>res<sub>1</sub></i>, …,  <i>res<sub>n</sub></i>
 295   <em>FROM</em> <i>tab_ref<sub>1</sub></i>, …,  <i>tab_ref<sub>m</sub></i>
 296   [<em>WHERE</em> <i>condition_w</i>]
 297   [<em>GROUP BY</em> <i>col<sub>1</sub></i>, …,  <i>col<sub>k</sub></i>]
 298   [<em>HAVING </em> <i>condition_h</i>]
 299   [<em>ORDER BY</em> <i>col<sub>1</sub></i>,  …,  <i>col<sub>;</sub></i> [<em>ASC</em>|<em>DESC</em>]]</code>
 300 <ul>
 301   <li><tt>ALL</tt> force à garder tous les
 302   résultats, <tt>DISTINCT</tt> retire les doublons</li>
 303   <li><i>res<sub>i</sub></i> peut être un nom de colonne, <tt>*</tt>
 304   (toutes les colones), un agrégat (<tt>SUM(price)</tt>,
 305   éventuellement nommé : <tt>AS TotalPrice</tt>)</li>
 306   <li><i>tab_ref<sub>i</sub></i> est soit un nom de table, soit une
 307   sous-requête (<tt>(SELECT … )</tt>) éventuellement nommé (<tt>AS T1</tt>)</li>
 308   <li><i>condition_w</i> est une condition booléenne sur les attributs
 309   des <i>m</i> tables mentionnées</li>
 310   <li><tt>GROUP BY</tt> et <tt>HAVING</tt> définissent des conditions
 311   de groupage </li>
 312   <li><tt>ORDER BY</tt> trie les résultats en ordre croissant (par
 313   défaut ou <tt>ASC</tt>) ou décroissant (<tt>DESC</tt>)</li>
 314 </ul>
 315 </div>
 316     <div class="sws-slide">
 317       <h1>Requêtes SQL 2/3</h1>
 318 <code>
 319           <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>
 320           <em>(</em><i>req<sub>1</sub></i><em>)</em> <em>INTERSECT</em>  <em>(</em><i>req<sub>2</sub></i><em>)</em>
 321           <em>(</em><i>req<sub>1</sub></i><em>)</em> <em>EXCEPT</em>  <em>(</em><i>req<sub>2</sub></i><em>)</em>
 322 </code>
 323 <p>Union, intersection et différence de deux requêtes. Par défaut,
 324   retire les doublons des résultats des requêtes (comportement
 325   ensembliste) sauf pour <tt>UNION ALL</tt> ou si <tt>SELECT ALL</tt>
 326   a été utilisé dans les sous-requêtes</p>
 327     </div>
 328 <div class="sws-slide">
 329       <h1>Requêtes SQL 3/3</h1>
 330 <p>Exemple de conditions de groupage. On considère une table
 331   d'employés (<tt>nom</tt>), appartenant chacun à un département
 332   (<tt>num_dept</tt>) et ayant chacun un salaire (<tt>sal</tt>). On
 333   souhaite avoir les salaires moyens, pour chaque département, pour
 334   les départements ayant plus de 10 employés.</p>
 335
 336 <code>
 337     SELECT num_dept, AVERAGE(sal)
 338     FROM TABLE_EMP
 339     GROUP BY num_dept
 340     HAVING COUNT(nom) >= 10;
 341 </code>
 342 <p><tt>HAVING</tt> est nécessaire car la clause <tt>WHERE</tt>
 343   s'applique ligne à ligne, ici on veut groupe à groupe (i.e. pour
 344   chaque département, i.e. pour toutes les lignes qui ont le même
 345   departement).</p>
 346 </div>
 347   </body>
 348 </html>