--- /dev/null
+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"
+[
+ <!ENTITY in "<small style='font-size:small'>∈</small>">
+ <!ENTITY notin "<small style='font-size:small'>∉</small>">
+ <!ENTITY mapsto "↦">
+]
+ >
+<html xmlns="http://www.w3.org/1999/xhtml" >
+ <head>
+ <title>Rappels</title>
+
+ <meta http-equiv="Content-Type"
+ content="text/html; charset=utf-8" />
+ <meta name="copyright"
+ content="Copyright © 2013 Kim Nguyễn" />
+
+ <!-- Load jQuery -->
+ <script src="../jquery-2.0.3.min.js" type="text/javascript" ></script>
+ <script src="../libs/raphael-min.js" type="text/javascript" ></script>
+ <!-- Load the library -->
+ <script src="../simpleWebSlides.js" type="text/javascript" ></script>
+
+ <link rel="stylesheet" href="../simpleWebSlides.css" type="text/css" media="all" />
+ <!-- Load a custom Theme, the class-element marks this style-sheet
+ a "theme" that can be swtiched dynamicaly -->
+ <link class="sws-theme" rel="stylesheet" title="U-Psud style" href="../themes/uPsud.css" type="text/css" />
+
+ <!-- Customize some templates and initialize -->
+
+ <script type="text/javascript">
+ SWS.Config['sws-slide-change'] = SWS.Effects.slideChangeFadeOutIn;
+ SWS.Config['sws-object-deactivate'] = SWS.Effects.objectDeactivateFadeOut;
+ SWS.Config['sws-object-activate'] = SWS.Effects.objectActivateFadeIn;
+
+ //Ensures that we load SWS at the very end, after MathJax has
+ //been initialized
+
+ $(window).load(SWS.Presentation.init);
+ </script>
+ </head>
+ <body>
+ <div class="sws-slide sws-cover sws-option-nofooter">
+ <h1>Bases de données</h1>
+ <h3>Polytech Paris-Sud</h3>
+ <h3>Apprentis 4<sup>ème</sup> année</h3>
+ <h1>Cours 1 : Généralités & rappels</h1>
+ <a href="mailto:kn@lri.fr">kn@lri.fr</a><br/>
+ <a href="http://www.lri.fr/~kn/">http://www.lri.fr/~kn</a>
+ </div>
+
+ <h1>Avant-propos</h1>
+ <div class="sws-slide">
+ <h1>But du cours</h1>
+ <p>
+ Le but du cours est de donner une formation avancée sur un
+ aspects central des bases de données : <em>l'évaluation de
+ requêtes</em>. Le plan suivi par le cours est le suivant:
+ </p>
+ <ul>
+ <li>Rappels de l'algèbre relationnelle et d'SQL (rapide)</li>
+ <li>Propriétés physiques des disques (Rotatifs, SSD), notion
+ de page mémoire, hierarchie d'accès mémoire</li>
+ <li>Index: généralités, coût, structures de données (Arbres
+ B+, Hash Index, Bitmap Index)</li>
+ <li>Algorithmes de jointure</li>
+ <li>Plan de requête et optimisations algébriques</li>
+ <li>Bonus: ce que vous voulez (XML, Cloud, J2SE, …)</li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Organisation du cours</h1>
+ <p>9 séances de <em>4h:</em></p>
+ <p>
+ <table class="btable" style="width:90%">
+ <tr><th >Date</th>
+ <th >Type</th>
+ <th >Heure</th>
+ </tr>
+ <tr>
+ <td>3/2</td><td>Cours/TD</td> <td>13h-17h</td></tr>
+ <tr><td>5/2</td><td> Cours/TD</td> <td>8h-12h</td></tr>
+ <tr><td>6/2</td><td> TP</td> <td>au PUIO, 13h-17h</td></tr>
+ <tr><td>10/2</td><td> Cours/TD</td> <td>13h-17h</td></tr>
+ <tr><td>12/2</td><td> TP</td> <td>au PUIO, 8h-12h</td></tr>
+ <tr><td>13/2</td><td> TP</td> <td>au PUIO, 13h-17h</td></tr>
+ <tr><td>31/3</td><td> Cours/TD</td> <td>13h-17h</td> </tr>
+ <tr><td>3/4</td><td> TP</td> <td>au PUIO, 13h-17h</td></tr>
+ <tr><td>9/4</td><td> Cours bonus/<em>exam</em></td> <td>8h-12h</td></tr>
+ </table>
+ </p>
+ <ul><li>Cours/TD : Kim Nguyen</li>
+ <li>TP: Andres Romero (certains TP seront <em>notés</em>)</li></ul>
+ </div>
+ <h1>Algèbre relationnelle</h1>
+ <div class="sws-slide">
+ <h1>Qu'est-ce que l'algèbre relationnelle?</h1>
+ <p class="sws-pause" >Une <em>algèbre</em> (ou <em>structure algébrique</em>) est un
+ <em>ensemble d'objets</em> (que l'on étudie) muni d'un ensemble
+ d'<em>opérations</em> (qui permettent de manipuler les objets)</p>
+
+ <p class="sws-pause" >Les objets manipulés par l'algèbre
+ relationnelle sont les <em>relations</em> <i>i.e.</i>
+ des <em>ensembles de n-uplets</em>.</p>
+ <p class="sws-pause" style="font-size:80%">(Rappel: une
+ relation n-aire est juste un ensemble de n-uplets. Par exemple,
+ la relation d'égalité sur les entiers est l'ensemble qui
+ contient tous les
+ couples <tt>(0,0)</tt>, <tt>(1,1)</tt>, <tt>(2,2)</tt>… )</p>
+ <p>On ne considère que des relations <em>finies</em>, sur des
+ n-uplets <em>fixes</em> dont les composantes ont un
+ type <em>simple</em></p>
+ <p><code>{ (1, "Kim", 32, T), (3,"Foo", 28, F), (2, "Bar", 77, T) }</code></p>
+ <ul class="sws-pause" style="background:white;">
+ <li>Les relations représentent des tables: ensemble
+ finis </li>
+ <li>Les relations contiennent des n-uplets de la même
+ taille</li>
+ <li>Un n-uplet ne peut pas contenir un ensemble (pas de table
+ dans une table)</li>
+ <li>(optionel) on ajoute un <em>schema</em> à la relation
+ (ex. <tt>(id, nom, age, prof)</tt>).</li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Les opérateurs de l'algèbre relationnelle (1/2)</h1>
+ <p class="sws-pause" style="font-size:80%">(attention, plusieurs
+ présentations possibles)</p>
+ <p><tt>R</tt> et <tt>S</tt> sont deux relations, munies chacune
+ d'un schéma (<tt>ℝ=(a<sub>1</sub>,…,a<sub>m</sub>)</tt>
+ et <tt>𝕊=(b<sub>1</sub>,…,b<sub>n</sub>)</tt>) </p>
+ <p>Opérateurs ensemblistes:
+ <table>
+ <tr>
+ <td style="width:25%">Union :</td>
+ <td style="width:40%"><tt><em>R ∪ S</em> ≝ { r | r ∉ R ∨ r ∈ S }</tt></td>
+ <td style="width:25%;text-align:right;">(requiert <tt>ℝ = 𝕊</tt>)</td>
+ </tr>
+ <tr>
+ <td style="width:25%">Différence :</td>
+ <td style="width:40%"><tt><em>R ∖ S</em> ≝ { r | r ∈ R ∧ r ∉ S }</tt></td>
+ <td style="width:25%;text-align:right;">(requiert <tt>ℝ = 𝕊</tt>)</td>
+ </tr>
+ <tr>
+ <td style="width:25%">Produit :</td>
+ <td style="width:40%;text-align:right;"><tt><em>R × S</em> ≝ {
+ (r<sub>1</sub>,…,r<sub>m</sub>,s<sub>1</sub>,…,s<sub>n</sub>)
+ | <br/>
+ (r<sub>1</sub>,…,r<sub>m</sub>) ∈ R ∧
+ (s<sub>1</sub>,…,s<sub>n</sub>) ∈ S }</tt></td>
+ <td style="width:25%;text-align:right;"></td>
+ </tr>
+ </table>
+ </p>
+ <p class="sws-pause">Q1: A-t-on besoin de l'intersection ? (<tt>R ∩ S</tt>)
+ </p>
+ <p class="sws-pause">R1: Non car <tt>R ∩ S = (R ∪ S) ∖ ((S ∖ R)∪(R ∖ S)) </tt>
+ </p>
+ </div>
+ <div class="sws-slide">
+ <h1>Les opérateurs de l'algèbre relationnelle (2/2)</h1>
+ <p class="sws-pause" style="font-size:80%">(attention, plusieurs
+ présentations possibles)</p>
+ <p><tt>R</tt> est une relation, munie
+ d'un schéma (<tt>ℝ=(a<sub>1</sub>,…,a<sub>m</sub>)</tt>) </p>
+ <p>Opérateurs relationnels:
+ <table>
+ <tr>
+ <td style="width:20%">Projection :</td>
+ <td style="width:54%"><tt><em>π<sub>a<sub>1</sub>,…,a<sub>k</sub></sub></em>(R)
+ ≝ { (r.a<sub>1</sub>,…,r.a<sub>k</sub>) | r ∈ R }</tt></td>
+ <td style="width:20%;text-align:right;"></td>
+ </tr>
+ <tr>
+ <td >Sélection :</td>
+ <td ><tt><em>σ<sub>φ</sub></em>(R) ≝ { r ∈ R | σ(r) }</tt></td>
+ <td style="text-align:right;">σ est une formule
+ logique sur <tt>r</tt></td>
+ </tr>
+ <tr>
+ <td >Renommage :</td>
+ <td ><tt><em>ρ<sub>a<sub>1</sub>↦b<sub>1</sub>,…</sub></em>(R)</tt>
+ associe R au schéma <tt>ℝ'=(b<sub>1</sub>,…)</tt></td>
+ <td style="text-align:right;"></td>
+ </tr>
+ </table>
+ </p>
+ </div>
+ <div class="sws-slide">
+ <h1>Opérateurs dérivés</h1>
+ <p><tt>R</tt> et <tt>S</tt> sont deux relations, munies chacune
+ d'un schéma (<tt>ℝ</tt> et <tt>𝕊</tt>) </p>
+ <ul>
+ <li>Jointure: <tt>ℝ=(a<sub>1</sub>,…,a<sub>m</sub>,c<sub>1</sub>,…,c<sub>l</sub>)</tt>
+ et <tt>𝕊=(b<sub>1</sub>,…,b<sub>n</sub>,c<sub>1</sub>,…,c<sub>l</sub>)</tt><code>
+ R ⨝ S ≝ {
+ (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>)
+ | r ∈ R ∧ s ∈ S ∧ ∀ 1 ≤ i ≤ l, r.c<sub>i</sub> = s.c<sub>i</sub> } </code>
+ </li>
+ <li>Intersection : <tt>R ∩ S = { r | r ∈ R ∧ r ∈ S } </tt></li>
+ <li>Division : <tt>R ÷ S ≝ T</tt>, telle que <tt>T × S ⊆
+ R</tt> (les attributs de <tt>S</tt> sont un sous-ensemble des
+ attributs de <tt>T</tt></li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Pourquoi utiliser l'algèbre relationnelle ?</h1>
+ <ul>
+ <li>Modèle abstrait qui permet de raisonner sur les requêtes
+ sans se soucier de la syntaxe</li>
+ <li>Permet de déduire des <em>optimisations
+ algébriques</em>
+ <p>Par exemple:<code>
+ σ<sub>φ</sub>(R ∪ S) = σ<sub>φ</sub>(R) ∪ σ<sub>φ</sub>(S)
+ </code>
+ Avantageux si <tt>R</tt> et <tt>S</tt> ont beaucoup
+ d'éléments mais que σ<sub>φ</sub> en séléctionne peu.
+ </p>
+ </li>
+ </ul>
+ </div>
+ <h1>SQL</h1>
+ <div class="sws-slide">
+ <h1>SQL</h1>
+ <p>SQL (<i>Structured Query Language</i>) est un langage de
+ programmation dédié permettant de manipuler les données d'une BD
+ relationnelle. Il permet de:
+ </p>
+ <ul><li>Créer et détruire des tables</li>
+ <li>Insérer, supprimer, modifier des lignes d'une table</li>
+ <li>Interroger des tables</li>
+ <li>…</li>
+ </ul>
+
+ </div>
+ <div class="sws-slide">
+ <h1>SQL <tt>≠</tt> Algèbre relationnelle</h1>
+ <ul>
+ <li>Table <tt>≠</tt> Relation : <span class="sws-pause">les tables peuvent
+ avoir plusieurs copies de la même ligne, alors que les
+ relations sont des ensembles</span></li>
+ <li>Opérations de comptage, d'agrégat, groupage, … </li>
+ <li>Les types sont finis et ont toujours une taille fixe
+ (<tt>INTEGER</tt>, <tt>VARCHAR[40]</tt>, <tt>DATE</tt>, …)</li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Création/destruction de table</h1>
+<p><code>
+<em>CREATE TABLE</em> <i>MaTable</i> (
+ <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>]
+ [, <i>constr_table</i>]);</code></p>
+<ul>
+ <li><tt>MaTable</tt> : nom de la table </li>
+ <li><tt><i>att<sub>i</sub></i></tt> : nom de l'attribut <i>i</i></li>
+ <li><tt><i>att<sub>i</sub></i></tt> : type de
+ l'attribut <i>i</i>. Exemples de
+ types: <tt>INTEGER</tt>, <tt>VARCHAR[<i>n</i>]</tt>, … (<s>dépend du
+ système utlisé</s>)</li>
+ <li><tt><i>constr_col<sub>i</sub></i></tt> : contrainte sur la
+ colonne <i>i</i>. Exemple de contraintes: <tt>PRIMARY
+ KEY</tt>, <tt>NOT NULL</tt>, <tt>DEFAULT <i>n</i>, …</tt></li>
+ <li><tt><i>constr_table</i></tt> : contrainte de table. Exemple de
+ contrainte de table: <tt>CHECK <i>cond</i></tt>, <tt>UNIQUE
+ (<i>col1</i>, …, <i>coln</i>)</tt>, …</li>
+</ul>
+<p><code>
+<em>DROP TABLE</em> <i>Table<sub>1</sub></i>, …, <i>Table<sub>n</sub></i> [<em>CASCADE</em>];</code></p>
+<ul style="background:white;"><li><tt>CASCADE</tt> : détruit aussi les objets dépendants de la
+ table (vues, autres tables avec clés étrangères, …) (<s>dépend du
+ système utilisé</s>)</li>
+</ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Insertion/suppression/mise à jour</h1>
+<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>
+<ul><li>Si la liste de colonnes est précisée les valeurs sont insérées
+ dans les colonnes correspondantes, sinon dans l'ordre du schéma</li></ul>
+
+<code> <em>DELETE FROM</em> <i>MaTable</i> [ <em>WHERE</em> <i>condition</i> ];</code>
+<ul><li>Supprime les lignes pour lesquelles <i><tt>condition</tt></i>
+ est vraie (expression booléene sur les
+ colonnes). Si <tt>WHERE</tt> est absent, supprime toutes les lignes.</li></ul>
+
+<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>
+<ul><li>Mise à jour de toutes les colonnes <i>i</i> des lignes pour lesquelles <i><tt>condition</tt></i>
+ est vraie (expression booléene sur les
+ colonnes). Si <tt>WHERE</tt> est absent, modifie toutes les lignes.</li></ul>
+
+</div>
+ <div class="sws-slide">
+ <h1>Requêtes SQL 1/3</h1>
+<code>
+ <em>SELECT</em> [<em>ALL</em>|<em>DISTINCT</em>] <i>res<sub>1</sub></i>, …, <i>res<sub>n</sub></i>
+ <em>FROM</em> <i>tab_ref<sub>1</sub></i>, …, <i>tab_ref<sub>m</sub></i>
+ [<em>WHERE</em> <i>condition_w</i>]
+ [<em>GROUP BY</em> <i>col<sub>1</sub></i>, …, <i>col<sub>k</sub></i>]
+ [<em>HAVING </em> <i>condition_h</i>]
+ [<em>ORDER BY</em> <i>col<sub>1</sub></i>, …, <i>col<sub>;</sub></i> [<em>ASC</em>|<em>DESC</em>]]</code>
+<ul>
+ <li><tt>ALL</tt> force à garder tous les
+ résultats, <tt>DISTINCT</tt> retire les doublons</li>
+ <li><i>res<sub>i</sub></i> peut être un nom de colonne, <tt>*</tt>
+ (toutes les colones), un agrégat (<tt>SUM(price)</tt>,
+ éventuellement nommé : <tt>AS TotalPrice</tt>)</li>
+ <li><i>tab_ref<sub>i</sub></i> est soit un nom de table, soit une
+ sous-requête (<tt>(SELECT … )</tt>) éventuellement nommé (<tt>AS T1</tt>)</li>
+ <li><i>condition_w</i> est une condition booléenne sur les attributs
+ des <i>m</i> tables mentionnées</li>
+ <li><tt>GROUP BY</tt> et <tt>HAVING</tt> définissent des conditions
+ de groupage </li>
+ <li><tt>ORDER BY</tt> trie les résultats en ordre croissant (par
+ défaut ou <tt>ASC</tt>) ou décroissant (<tt>DESC</tt>)</li>
+</ul>
+</div>
+ <div class="sws-slide">
+ <h1>Requêtes SQL 2/3</h1>
+<code>
+ <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>
+ <em>(</em><i>req<sub>1</sub></i><em>)</em> <em>INTERSECT</em> <em>(</em><i>req<sub>2</sub></i><em>)</em>
+ <em>(</em><i>req<sub>1</sub></i><em>)</em> <em>EXCEPT</em> <em>(</em><i>req<sub>2</sub></i><em>)</em>
+</code>
+<p>Union, intersection et différence de deux requêtes. Par défaut,
+ retire les doublons des résultats des requêtes (comportement
+ ensembliste) sauf pour <tt>UNION ALL</tt> ou si <tt>SELECT ALL</tt>
+ a été utilisé dans les sous-requêtes</p>
+ </div>
+<div class="sws-slide">
+ <h1>Requêtes SQL 3/3</h1>
+<p>Exemple de conditions de groupage. On considère une table
+ d'employés (<tt>nom</tt>), appartenant chacun à un département
+ (<tt>num_dept</tt>) et ayant chacun un salaire (<tt>sal</tt>). On
+ souhaite avoir les salaires moyens, pour chaque département, pour
+ les départements ayant plus de 10 employés.</p>
+
+<code>
+ SELECT num_dept, AVERAGE(sal)
+ FROM TABLE_EMP
+ GROUP BY num_dept
+ HAVING COUNT(nom) >= 10;
+</code>
+<p><tt>HAVING</tt> est nécessaire car la clause <tt>WHERE</tt>
+ s'applique ligne à ligne, ici on veut groupe à groupe (i.e. pour
+ chaque département, i.e. pour toutes les lignes qui ont le même
+ departement).</p>
+</div>
+ </body>
+</html>
projects / hacks / simpleWebSlides.git / blobdiff