From: Kim Nguyễn Date: Mon, 3 Feb 2014 09:20:40 +0000 (+0100) Subject: Typos et nouveau cours. X-Git-Url: http://git.nguyen.vg/gitweb/?p=hacks%2FsimpleWebSlides.git;a=commitdiff_plain;h=a09e9a046f0de86550287ada42103e4015da7973 Typos et nouveau cours. --- diff --git a/bd/bd01.xhtml b/bd/bd01.xhtml new file mode 100644 index 0000000..3746faf --- /dev/null +++ b/bd/bd01.xhtml @@ -0,0 +1,349 @@ + +∈"> + ∉"> + +] + > + + + Rappels + + + + + + + + + + + + + + + + + + + +
+

Bases de données

+

Polytech Paris-Sud

+

Apprentis 4ème année

+

Cours 1 : Généralités & rappels

+ kn@lri.fr
+ http://www.lri.fr/~kn +
+ +

Avant-propos

+
+

But du cours

+

+ Le but du cours est de donner une formation avancée sur un + aspects central des bases de données : l'évaluation de + requêtes. Le plan suivi par le cours est le suivant: +

+ +
+
+

Organisation du cours

+

9 séances de 4h:

+

+ + + + + + + + + + + + + + + +
DateTypeHeure
3/2Cours/TD 13h-17h
5/2 Cours/TD 8h-12h
6/2 TP au PUIO, 13h-17h
10/2 Cours/TD 13h-17h
12/2 TP au PUIO, 8h-12h
13/2 TP au PUIO, 13h-17h
31/3 Cours/TD 13h-17h
3/4 TP au PUIO, 13h-17h
9/4 Cours bonus/exam 8h-12h
+

+ +
+

Algèbre relationnelle

+
+

Qu'est-ce que l'algèbre relationnelle?

+

Une algèbre (ou structure algébrique) est un + ensemble d'objets (que l'on étudie) muni d'un ensemble + d'opérations (qui permettent de manipuler les objets)

+ +

Les objets manipulés par l'algèbre + relationnelle sont les relations i.e. + des ensembles de n-uplets.

+

(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 (0,0), (1,1), (2,2)… )

+

On ne considère que des relations finies, sur des + n-uplets fixes dont les composantes ont un + type simple

+

{ (1, "Kim", 32, T), (3,"Foo", 28, F), (2, "Bar", 77, T) }

+ +
+
+

Les opérateurs de l'algèbre relationnelle (1/2)

+

(attention, plusieurs + présentations possibles)

+

R et S sont deux relations, munies chacune + d'un schéma (ℝ=(a1,…,am) + et 𝕊=(b1,…,bn))

+

Opérateurs ensemblistes: + + + + + + + + + + + + + + + + +
Union :R ∪ S ≝ { r | r ∉ R ∨ r ∈ S }(requiert ℝ = 𝕊)
Différence :R ∖ S ≝ { r | r ∈ R ∧ r ∉ S }(requiert ℝ = 𝕊)
Produit :R × S ≝ { + (r1,…,rm,s1,…,sn) + |
+ (r1,…,rm) ∈ R ∧ + (s1,…,sn) ∈ S }
+

+

Q1: A-t-on besoin de l'intersection ? (R ∩ S) +

+

R1: Non car R ∩ S = (R ∪ S) ∖ ((S ∖ R)∪(R ∖ S)) +

+
+
+

Les opérateurs de l'algèbre relationnelle (2/2)

+

(attention, plusieurs + présentations possibles)

+

R est une relation, munie + d'un schéma (ℝ=(a1,…,am))

+

Opérateurs relationnels: + + + + + + + + + + + + + + + + +
Projection :πa1,…,ak(R) + ≝ { (r.a1,…,r.ak) | r ∈ R }
Sélection :σφ(R) ≝ { r ∈ R | σ(r) }σ est une formule + logique sur r
Renommage :ρa1↦b1,…(R) + associe R au schéma ℝ'=(b1,…)
+

+
+
+

Opérateurs dérivés

+

R et S sont deux relations, munies chacune + d'un schéma (ℝ et 𝕊)

+ +
+
+

Pourquoi utiliser l'algèbre relationnelle ?

+ +
+

SQL

+
+

SQL

+

SQL (Structured Query Language) est un langage de + programmation dédié permettant de manipuler les données d'une BD + relationnelle. Il permet de: +

+ + +
+
+

SQL ≠ Algèbre relationnelle

+ +
+
+

Création/destruction de table

+

+CREATE TABLE MaTable ( + att1 type1 [constr_col1], …, attn typen [constr_coln] + [, constr_table]);

+ +

+DROP TABLE Table1, …, Tablen [CASCADE];

+ +
+
+

Insertion/suppression/mise à jour

+ INSERT INTO MaTable [ (col1,…,coln) ] VALUES (val1,…,valn); + + + DELETE FROM MaTable [ WHERE condition ]; + + + UPDATE MaTable SET col1=val1, …, coln=valn [ WHERE condition ]; + + +
+
+

Requêtes SQL 1/3

+ + SELECT [ALL|DISTINCT] res1, …, resn + FROM tab_ref1, …, tab_refm + [WHERE condition_w] + [GROUP BY col1, …, colk] + [HAVING condition_h] + [ORDER BY col1, …, col; [ASC|DESC]] + +
+
+

Requêtes SQL 2/3

+ + (req1) UNION [ALL] (req2) + (req1) INTERSECT (req2) + (req1) EXCEPT (req2) + +

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 UNION ALL ou si SELECT ALL + a été utilisé dans les sous-requêtes

+
+
+

Requêtes SQL 3/3

+

Exemple de conditions de groupage. On considère une table + d'employés (nom), appartenant chacun à un département + (num_dept) et ayant chacun un salaire (sal). On + souhaite avoir les salaires moyens, pour chaque département, pour + les départements ayant plus de 10 employés.

+ + + SELECT num_dept, AVERAGE(sal) + FROM TABLE_EMP + GROUP BY num_dept + HAVING COUNT(nom) >= 10; + +

HAVING est nécessaire car la clause WHERE + 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).

+
+ + diff --git a/bd/bd02.xhtml b/bd/bd02.xhtml new file mode 100644 index 0000000..5505555 --- /dev/null +++ b/bd/bd02.xhtml @@ -0,0 +1,367 @@ + +∈"> + ∉"> + +] + > + + + Stockage + + + + + + + + + + + + + + + + + + + + +
+

Bases de données

+

Polytech Paris-Sud

+

Apprentis 4ème année

+

Cours 2 : Stockage

+ kn@lri.fr
+ http://www.lri.fr/~kn +
+ +

Introduction

+
+

Où stocker les données ?

+

Hierarchie mémoire :

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
TypeAccèsTaille maxCoûtdurée de vie
Registre < 1ns128 bitsTrès cheralimenté
Cache L1/2/3 ~ 10 ns1ko ~ 1MoTrès cheralimenté
RAM ~ 50 ns10 Go Cheralimenté
Disque SSD ~ 0.1ms1 To - CherÉcritures limitées
Disque dur ~ 5ms10 To Peu cherFragiles
Bandes 10 s1 Po/Eo DonnéBonne
+ + +
+
+

Quels types de mémoire pour une BD ?

+

On attend en général d'une BD:

+ +

Celà implique l'utilisation de mémoire primaire (comme toutes + les applications) et secondaire

+

Pas d'adressage direct du disque par le processeur, nécessité de + « monter » les données en RAM

+

Goulet d'étranglement : facteur 10 000 (SSD) ~ 100 000 (HDD) entre + mémoire et disques

+

Priorité des SGBD (ce qu'on présente dans ce cours) : + limiter les accès disque

+
+

Aspects bas-niveau

+
+

Caractéristiques physiques de disques

+

Disques rotatifs:

+
+ hdd +
+ +
+
+

Temps d'accès à un disque

+

Accès à un secteur arbitraire :

+ +

Tout cela constitue la latence du disque

+

Une fois qu'on a payé le temps de latence, lire le secteur + suivant ne demande que le temps de transfert

+

On va donc essayer d'organiser les données de manière éviter + les déplacements arbitraires

+
+
+

Unité de transfert

+

On appelle page (ou bloc) la quantité de + mémoire que le disque dur transfert de manière atomique en + mémoire. En pratique 512o ~ 4ko (dépendant des disques). +

+

On doit lire/écrire au moins une page même si on ne + désir lire/écrire qu'un octet

+

Exemple : on souhaite stocker 5 chaines de caractères de 200o + chacunes sur le disque

+ +
+
+

Stratégies de placement

+

On peut placer en priorité les données « reliées » (qu'on + veut utiliser en même temps):

+
    +
  1. Dans le même bloc (T.A. à la deuxième donnée: + 0)
    2. +
  2. Sur deux blocs contigus (T.A. à la deuxième donnée: + T. transfert)
    3. +
  3. Bloc à la même position sur un autre plateau (T.A. à la + deuxième donnée: T. transfert)
    4. +
  4. Sur la même piste (T.A. à la deuxième donnée: + T. rotation)
    5. +
  5. Sur des pistes proches
    6. +
+
+
+

Mise en place de la stratégies de placement

+

Pour mettre en place les stratégies de placement il faut + connaître:

+ +

On ne travaille pas page à page : on alloue + un buffer de pages

+

+ + + +
+ P1 P132 + P10 P99
+ P2 P1000 P507 +
+

+ On maintient pour chaque page : un compteur + d'utilisation et un dirty-bit qui indique si la + page a été modifiée (on doit donc l'écrire sur le disque à un + moment donné).
+ Lorsque le buffer est plein, il faut supprimer des pages (et + en monter d'autres en mémoire) suivant une stratégie: + LRU, MRU, Random, FIFO, LIFO, … +

+
+
+

Qui gère les accès disques bas-niveau, le buffer, … ?

+

+

+

+

Les systèmes d'exploitation ont énormément progressé + (les SGBD ne pouvaient pas reposer sur quelque chose d'aussi + primitif que FAT ou NTFS, mais les systèmes de fichier modernes + sont plus performant que le traitement natif du disque fais par + les SGBD, en particulier pour les SSD).
+ Pour prédire le bon comportement d'un SGBD il faut connaître + non seulement ce dernier, mais aussi, de manière + détaillée, les caractéristiques de l'OS et du système de + fichier. +

+
+
+

Un mot sur les SSD

+

Solid State Disk : « disque » dur composé entièrement + de mémoire flash. Avantages:

+ + +
+

Stockage pour les SGBD

+
+

Utilisation du disque par les SGBD

+ +

Opérations de base sur les enregistrements

+ +

Les fichiers (i.e. les tables) sont paginées + (découpées en pages)

+
+
+

Représentation des enregistrements fixes

+ +

+ + +
C1 C2 C3 C4 C5
+ + +
B L1  L2  L3  L4  L5

+Pour accéder au ième champ d'un enregistrement en + connaissant l'addresse de base B, on ajout à B + les longueurs des champs 0, 1, …, i-1.
+ adresse de C4 = B + L1 + L2 + L3
+

+
+ +
+

Représentation des enregistrements variables

+ +

+ + +
C1 $C2 $ C3 $C4$ C5
+ On utilise un séparateur spécial entre les champs (scan linéaire + pour arriver au ième champ.
+ + +
L1 L2 L3 L4 L5C1 C2 C3 C4 C5
+ On stocke les longueurs dans l'enregistrement +

+
+
+

Méta-données

+

Chaque enregistrement possède un en-tête stockant des données + auxiliaires

+ +
+
+

Stockage des enregistrements dans une page

+

Chaque enregistrement à une adresse (rid : record id) + constituée de l'adresse de la page et de la position de + l'enregistrement au sein de la page

+

Lors d'une insertion, on doit trouver un emplacement libre + dans la page

+

Lors d'une suppression, on doit « effacer » un emplacement + occupé et éventuellement compacter la page

+
+
+

Stockage compact vs non compact (taille fixe)

+

+ + +

+
+
+

Stockage compact (taille variable)

+

+ +

+
+ + diff --git a/bd/hdd.svg b/bd/hdd.svg new file mode 100644 index 0000000..2ffd7ce --- /dev/null +++ b/bd/hdd.svg @@ -0,0 +1,354 @@ + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Piste + + Secteur + + Plateau + + + + + + Bras + + Tête de lecture + + diff --git a/bd/page_comp.svg b/bd/page_comp.svg new file mode 100644 index 0000000..a756f0b --- /dev/null +++ b/bd/page_comp.svg @@ -0,0 +1,242 @@ + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + emplacement 1 + emplacement 2 + … + emplacement N + espacelibre + + en-tête + + N + + diff --git a/bd/page_ncomp.svg b/bd/page_ncomp.svg new file mode 100644 index 0000000..9a84ee4 --- /dev/null +++ b/bd/page_ncomp.svg @@ -0,0 +1,298 @@ + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + emplacement 1 + emplacement 2 + … + emplacement N + espacelibre + + en-tête + + N + + + + … + 1 + 0 + + diff --git a/bd/page_var.svg b/bd/page_var.svg new file mode 100644 index 0000000..563fdc7 --- /dev/null +++ b/bd/page_var.svg @@ -0,0 +1,303 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + N + Espace libre + + + + + Espace ocupé + Dictionaire d'emplacements (pointeurs) + + diff --git a/bd/pdf/bd01.pdf b/bd/pdf/bd01.pdf new file mode 100644 index 0000000..196c732 Binary files /dev/null and b/bd/pdf/bd01.pdf differ diff --git a/bd/pdf/bd01_print.pdf b/bd/pdf/bd01_print.pdf new file mode 100644 index 0000000..70ddd36 Binary files /dev/null and b/bd/pdf/bd01_print.pdf differ diff --git a/bd/pdf/bd02.pdf b/bd/pdf/bd02.pdf new file mode 100644 index 0000000..34e532e Binary files /dev/null and b/bd/pdf/bd02.pdf differ diff --git a/bd/pdf/bd02_print.pdf b/bd/pdf/bd02_print.pdf new file mode 100644 index 0000000..04edb59 Binary files /dev/null and b/bd/pdf/bd02_print.pdf differ diff --git a/prog_internet/pdf/prog_internet_09.pdf b/prog_internet/pdf/prog_internet_09.pdf index 3bb6362..393ed86 100644 Binary files a/prog_internet/pdf/prog_internet_09.pdf and b/prog_internet/pdf/prog_internet_09.pdf differ diff --git a/prog_internet/pdf/prog_internet_09_print.pdf b/prog_internet/pdf/prog_internet_09_print.pdf index 1334e7f..86df3a2 100644 Binary files a/prog_internet/pdf/prog_internet_09_print.pdf and b/prog_internet/pdf/prog_internet_09_print.pdf differ diff --git a/prog_internet/prog_internet_09.xhtml b/prog_internet/prog_internet_09.xhtml index e1a3e3a..d2166a9 100644 --- a/prog_internet/prog_internet_09.xhtml +++ b/prog_internet/prog_internet_09.xhtml @@ -259,7 +259,7 @@
  • Permet d'authentifier les correspondants et de protéger les données
    • -
  • Suppose l'existence de tiers de confience Alice +
  • Suppose l'existence de tiers de confiance Alice et Bob font confiance à Trent (Trusted Third Party)
    • @@ -299,8 +299,8 @@
    -

    Tiers de confience

    -

    Les tiers de confience sont des entités (états, associations, +

    Tiers de confiance

    +

    Les tiers de confiance sont des entités (états, associations, compagnies privées) qui se chargent de vérifier les clés publiques d'autres entitées. C'est une vérification physique (documents administratifs, …). @@ -312,10 +312,10 @@

    -

    Tiers de confience

    +

    Tiers de confiance

    Attaques contre les authorités de certifications - (tiers de confience): difficiles, mais pas impossible. Certains - tiers de confience sont douteux (états voyous, compagnie + (tiers de confiance): difficiles, mais pas impossible. Certains + tiers de confiance sont douteux (états voyous, compagnie piratées dont les clées privées sont compromises,…)
    Attaques d'implémentation (plus probables) : on exploite un bug dans le code des serveurs web ou des diff --git a/themes/uPsud.css b/themes/uPsud.css index e64202f..6d4777c 100644 --- a/themes/uPsud.css +++ b/themes/uPsud.css @@ -270,4 +270,13 @@ div.twocol > div:last-child { vertical-align:text-top; right: 0pt; top:0pt; +} +table.withborder { + border-collapse: collapse; +} +table.withborder td { + border-style: solid; + border-width: 1pt; + min-width:20pt; + height: 20pt; } \ No newline at end of file