NF26 : deuxième partie | cours 1
=====

:::danger
# Rédaction collaborative du cours 2 disponible ici : [https://hackmd.io/xvb6fOuLTTWSWHirEAaiYA#](https://hackmd.io/xvb6fOuLTTWSWHirEAaiYA#)
:::

# Formalités
## Projet

2 séances dédiées en TD au projets.
Rapport très court,
Soutenance très courte (5 minutes) lors d'une séance de cours et une autre séance posée à posteriori

## Poly collabortaif

Projet sur `git`
Inviter à contribution
Poly imprimé avec le final et disponible pour l'examen

# Introduction

## BDD classiques

**MCD :**

Qu'est ce qu'on va perdre en passant à de gros volumes de données ? Contraindre le modèle logique pour qu'il respecte le modèle conceptuel.

La normalisation permet d'assurer l'intégrité des données en supprimant toute redondance.

**MLD :**

UV(#code, nom, filiere → Filiere.nom)
Étudiant(#login)
UVEtudiant(#uv → UV.code, etu → Etudiant.login)
Filiere(#nom)
PCBF(#uv → UV.code, #Filiere.nom)  // PCB de fillère

On a oublié toutes les contraintes 1_N (on a implémenté des contraintes 0_N). Pour cela, on doit écrire des requêtes extérieures, l'implémentation est lourde.

> **Exemple :**

(UV (1_N) → (1_N) Etudiant)
Projection(UV, code) \in Projection(UVEtudiant, uv)

-- Sélection des UVs sans étudiants présents
(SELECT code FROM UV
WHERE code NOT IN
    (SELECT uv from UVEtudiant)
)

On va maintenant créer un trigger pour s'assurer de la contrainte d'intégrité `1…N`:

CREATE FUNCTION funtrig_cl()
    RETURNS trigger AS
$func$
BEGIN
    IF EXISTS
        (SELECT code FROM UV
        WHERE code NOT IN
            (SELECT uv from UVEtudiant))
    THEN RAISE EXCEPTION '~';
    END IF;
RETURN NEW;

> Remarque : on fait souvent cela pour s'assurer de l'intégrité des données dans le cas de contrainte que l'on ne peut pas directement implémenter dans le modèle logique de données.

Imaginons que l'on rajoute une UV non présente dans la base :

INSERT INTO UV(code) VALUES ('NF26');

Une exception sera levée car la contrainte sera violée.
On impose alors que l'ensemble des requettes d'une transaction respecte la contrainte pour éviter de se faire déggager à chaque fois que l'on veut insérer une nouvelle UV :

INSERT INTO UVEtudiant (UV,etu)
            VALUES ('NF26', 'totopassoir');

La ligne du dessus ne fonctionne pas non plus : la valeur de l'attribut `UV` est une clé étrangère. Il faut réaliser une transaction pour que cela fonctionne :

BEGIN TRANSACTION
    INSERT INTO UV(code) VALUES('NF26');
    INSERT INTO UVEtudiant (UV,etu)
                VALUES ('NF26', 'totopassoir');
COMMIT

On peut néanmoins arriver dans des cas où l'on ne peut passer à l'échelle.

Mais pourquoi ?
- Débit des transactions ? (en général ça va, mais quand on a plus de 1000 transactions par seconde)
- Volume de données à traiter lors de la vérification dans les triggers.

> **Exemple :** La base de données Open Street Map tourne sous PostgreSQL avec plus d'un million d'enregistrements dans une table et ça passe oklm (nombre de requêtes qui reste raisonnable).

## Bilan relationnel / non relationnel

**Relationnel - Avantages :**

- Intégrité des données
- Possibilité de faire des requêtes très complexes avec moultes jointures, on stocke la relation
- Possibilité de faire des requêtes complexes
- Structure standard
- Grande communauté d'utilisateurs et d'utilisatrices ($\Rightarrow$ logiciels aboutis)

**Relationnel - Inconvénients :**

- Volumes peu élevés (même en distribuant ~ même avec un nœud coordinateur)
- Débit en lecture et en écriture (généralement le début en lecture pose très peu de problèmes mais l'écriture en pose à cause des contraintes d'intégrité)
- Existence d'un SPOF (_Single Point Of Failure_) - un problème sur un seul point (comme un noeud coordinateur, par exemple) peut remettre en cause l'intégralité de la base de données

Big data : gros volume de données et ça loupe

Réponse → Le seul moyen pour résoudre ces problèmes c'est de faire du _passage à l'échelle verticale_ (= utiliser des serveurs plus gros...)

**Dans le cadre non relationnel, on va oublier l'utilisation du relationnel mais ne pas oublier ses propriétés.**

**Formalisation :**
1. Propriétés ACID
2. Théorème du CAP
3. Propriétés BASE

## Propriétés ACID

:::warning
- **A** : Atomicité. Considérer les requêtes comme atomiques : l'intégralité d'un transaction est soit acceptée soit rejeté ; un ensemble de transactions sera accepté ou rejeté en bloc.
- **C** : Cohérence : intégrité des données insérées avec les schémas et autres données déjà présentes
- **I** : Isolation. Exécution de transactions en parallèle de façon équivalente à une exécution en série.
- **D** : Durabilité. Une fois fois que les données sont acceptées elles vont rester dans la base de données... _ad vitam aeternam_.
:::

> [name=Jean-Benoit Léger]« Les noms français correspondent aux noms anglais, c'est absolument merveilleux. » — 17 mai 2018

> [name=Jean-Benoit Léger]« Euh… Y a pas un 'e' à "*ad vitam eternam*" ? » — 17 mai 2018

> [name=Jean-Benoit Léger] « Je vais me casser la gueule un jour. » — 17 mai 2018

Ces propriétés sont respectées par les moteurs de base de données relationnelles, mais c'est ce qui va nous poser problème.

## Théorème du CAP ou plutôt Conjecture de Brewer
:::info
Certains l'appellent _Théorème de Brewer_ mais celui-ci ne l'a jamais démontré, on parlera donc plutôt de _Conjecture de Brewer_.
:::

:::warning
- **C** : _Cohérence_. Si lecture, on obtient l'enregistrement le plus récent ou une erreur: pas question de lire une donnée absente ou périmée.
- **A** : _Availability_. Chaque lecture retourne un résultat, le plus récent ou non.
- **P** : _Tolérance au partitionnement_ : Le système continue d'être opérationnel même si une de ses sous-parties est absente.
:::

<center>
<img width="50%" src="https://www.ibm.com/developerworks/community/blogs/IMSupport/resource/BLOGS_UPLOADED_IMAGES/CAP_Theorem.jpg">
</center>

:::danger
**Théorème/Conjecture :** Le respect de ces trois propriétés simultanément est impossible : on ne peut pas construire un système qui respecte ces trois propriétés en même temps.
:::

> [name=Jean-Benoit Léger]« La tolérance au partitionnement, c'est ce qui fait la différence entre un corail et un humain. » — 17 mai 2018

En relationnel, on est entre C et A (i.e. le relationnel est tout sauf tolérant au partitionnement) là ou en non relationnel, on est soit entre C et P, soit entre A et P.

<center>
<img width="80%" src="https://image.noelshack.com/fichiers/2018/20/4/1526541024-t.jpg">
</center>

:::success
Le théorème a finalement été démontré par Gilbert et Lynch en 2002, _par un formalisme assez pédestre_ (voir [ici](https://mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/) pour une explication plus simple ; [là](https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf) pour le papier original).
:::

## Propriétés BASE

:::warning
- **Basic Availability** : Disponibilité la plupart du temps. On sait prévoir quand la base de données sera à nouveau disponible.
- **Soft state** : Pas de cohérence au niveau des écritures.
- **Eventual consistancy** : La cohérence sera atteinte à un moment donné. A partir d'un certain temps, la dernière donnée est disponible.
:::

# Stockage clef/valeur

## Introduction

La structure de données clef/valeur est disponible même si le nom est susceptible de varier selon la technologie.
- `Python` : dictionnaires
- `Perl` : tables de hashage
- `C++` : `map` (de la STL)
- `LISP` : `car` et `cdr` des listes 🙃
- `Scala` : `Map`
- `JS` : `object`
- ...

:::warning
**Définition :**
La structure clef–valeur est un ensemble de couples $\{ (k_i, v_i)\}_i$.
:::

:::info
Le plus souvent, les clefs sont uniques.

$$
\forall i,j,\quad i\neq j \Rightarrow k_i \neq k_j
$$

Si ce n'est pas le cas, on peut associer à une clef le $n$-upplet de valeurs correspondantes. Donc l'unicité des clefs est **WLOG** (sans perte de généralité -- _Without Loss Of Generality_).
:::

## Exemple
(retour partiel sur l'exemple Etu/UV) :
> UV(#code, (nom, filière))
> Etudiant(#login, $\emptyset$)
> UVEtudiant(#(UV, etu), $\emptyset$)

## Opérations
:::warning
Avec un système clef/valeur on peut définir les 4 opérations **CRUD** (qui permettent de _tout_ faire -- y compris du $kmeans$ comme nous le verrons dans le premier TP):

- **Create**
- **Read**
- **Update**
- **Delete**
:::

## Technologies

On a notamment :

- [Voldemort](http://www.project-voldemort.com/voldemort/) (utilisé par exemple par Twitter)
- [Redis](https://redis.io/) (utilisé par Mastodon)
- [BDB](https://www.oracle.com/database/berkeley-db/db.html) (Berkley DB) et [LMDB](https://symas.com/lmdb/) (même API), dans la même idée que `sqlite`, pas besoin de serveur

Bilan :
- **Pour :** c'est simple (et rapide et puissant)
- **Contre :** c'est simple

## Distribution des données

### Hashage

> Problématique : comment stocker des couples clef/valeur ?

Technique souvent utilisée : utilisation d'un _hash_ parce que les clés ne sont pas toujours comparables (par exemple faisant partie de différents ensembles).
Nous allons considérer un `hash` comme étant une fonction, qui $\forall i, \; h(k_i) \in 0..N$

Dans l'idéal, on voudrait que *la fonction de hashage soit injective* ie :
$$\forall i,j \quad k_i \neq k_j \Rightarrow h(k_i) \neq h(k_j)$$
Dans les faits, c'est impossible (quand ça arrive, on parle de *collision*).

:::info
C'est le cas de la fonction de hachage MD5, mais aussi de SHA-1, utilisée dans `git`. Dans certains cas, cela ne remet pas en question leur utilisation — de ce point de vue, SHA-1 continue d'être utilisé pour `git` car les cas de collisions sont extrêmement rares.
:::

On demande juste que $\{h(k_i)\}_i$ soit à peu près uniforme.

#### Exemples de fonctions de `hash`

> _Fonction de condensat_ en français

- CRC
- hash cryptographique comme sha2, sha3
- md5 (**pas** un hash cryptographique)

> [name=Jean-Benoit Léger] « Ça n'a pas de rapport avec le cours, mais juste, si quelqu'un pense que MD5 c'est une fonction de hash cryptographique, il mérite de mourir. » — 17 mai 2018

Cas d'usage : on a $k$ et on cherche $h(k)$.
On obtient
$$
A = \{(k_i, V_i) \mid h(k_i)=h(k)\}_i
$$
puis
$$
\{(k_i, V_i) \in A \mid k_i=k\}
$$

Exemple :
On a l'ensemble de données suivant
$$
\{('a',...),\, ('b',...),\, ('c',...),\, ('f',...)\}
$$

Avec :

$$
\begin{align}
h('a')&=113\\
h('b')&=8\\
h('c')&=127\\
h('f')&=113
\end{align}
$$

On veut stocker cet ensemble de données par $h$ trié.

| $h$ | $k$ |$V$|
|-----|-----|---|
| 8 | 'b' |...|
| 113 | 'f' |...|
| 113 | 'a' |...|
| 127 | 'c' |...|

Question : quelle valeur il y a derrière $'f'$ ?
$$h('f')=113\\
A=\{('f',),\, ('a',)\}$$

> [name=Jean-Benoit Léger]« J'ai fumé là. » — 17 mai 2018

Trouver les $h$ ne revient pas à trouver les clés.

Les opérations qui sont linéaires dans la BDD peuvent être faites mais avec parcimonie.

### Constant hash
késéko ?
TO BE CONTINUÈDE