Différences
Ci-dessous, les différences entre deux révisions de la page.
tc_info:cm [2020/06/18 15:54] – edauce | tc_info:cm [2024/06/28 15:18] (Version actuelle) – modification externe 127.0.0.1 | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ===== CM ===== | ||
+ | |||
+ | ===== 1. Complexité(s) ===== | ||
+ | |||
+ | <note tip> **TODO** | ||
+ | |||
+ | * Complexité : | ||
+ | * Définition. intérêt. | ||
+ | * Complexité dans le cas le pire, le meilleur | ||
+ | * Complexité des algos récursifs (exemples : factorielle, | ||
+ | * Complexité en moyenne (exemple du tri par insertion (simple) & de quicksort (un peu plus dur)) | ||
+ | * Complexité minimales des pb (inversion de matrices en n^2, tri en n · log n, enveloppe convexe en n · log n) | ||
+ | * Introduction à la preuve de programmes ; exemple de l' | ||
+ | * Présentation des Piles & Files d' | ||
+ | </ | ||
+ | |||
+ | ===== 2. Graphes ===== | ||
+ | |||
+ | [[http:// | ||
+ | |||
+ | |||
+ | |||
+ | ===== 3. Données non structurées ===== | ||
+ | |||
+ | ==== 3.1 Données texte ==== | ||
+ | |||
+ | ===3.1.1 Encodage des données=== | ||
+ | |||
+ | On distingue classiquement deux grandes catégories de données : | ||
+ | |||
+ | * données **quantitatives**: | ||
+ | * numérique entier ou réel, discrètes ou continues, bornées ou non. ex: poids, taille, âge, taux d’alcoolémie, | ||
+ | * temporel : date, heure | ||
+ | * numéraire | ||
+ | * etc... | ||
+ | * données **qualitatives**: | ||
+ | * de type vrai/faux (données booléennes). ex: marié/non marié, majeur/non majeur | ||
+ | * de type appartenance à une classe. ex: célibataire/ | ||
+ | * de type texte (autrement dit “chaine de caractères”). ex: nom, prénom, ville,... | ||
+ | |||
+ | < | ||
+ | < | ||
+ | Parfois, la distinction entre quantitatif et qualitatif n’est pas nette: | ||
+ | * Possibilité d’ordonner les chaînes de caractères (de type nom/ | ||
+ | * On peut “traduire” une chaîne de caractères en entier (son code ASCII) | ||
+ | * Les valeurs logiques vrai/faux sont souvent traduites en valeurs “entières” 1/0 | ||
+ | * Plus subtil : il est possible de définir des ordres partiels, des hiérarchies sur des données qualitatives : | ||
+ | * regroupement par secteur géographique | ||
+ | * notion de distance (géographique et temporelle) entre catégories | ||
+ | * Inversement, | ||
+ | </ | ||
+ | --!></ | ||
+ | |||
+ | <note important> | ||
+ | D'un point de vue informatique, | ||
+ | |||
+ | Une valeur numérique (digitale) consiste en: | ||
+ | * un champ de bits (dont la longueur est exprimée en octets) | ||
+ | * un processus de décodage : le **format** (ou type) | ||
+ | </ | ||
+ | |||
+ | * Les données manipulées par un programme: | ||
+ | * sont codées sous un format binaire, | ||
+ | * correspondant à un des types informatiques que vous connaissez déjà : | ||
+ | * entier, | ||
+ | * chaîne de caractères, | ||
+ | * réel simple ou double précision etc... | ||
+ | * ce qui implique en particulier : | ||
+ | * une précision finie, | ||
+ | * éventuellement des contraintes de place (le nom ou le prénom ne pouvant pas dépasser n caractères, | ||
+ | < | ||
+ | < | ||
+ | **Types de données standards** | ||
+ | |||
+ | Les principaux types de données SQL sont les suivants : | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | </ | ||
+ | --></ | ||
+ | |||
+ | === 3.1.2 Codage des caractères === | ||
+ | <code python> | ||
+ | x = ' | ||
+ | </ | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | * | ||
+ | * Codage ASCII : | ||
+ | * codage de symboles du clavier numérique. | ||
+ | * Le nombre de symboles étant inférieur à 256, on le code sur un octet : 2⁸ (= 256) valeurs différentes | ||
+ | * Codage UTF-8 : | ||
+ | * codage universel qui permet entre autre de coder les accents | ||
+ | * Codage latin-1 (caractères latins étendus) | ||
+ | * etc... | ||
+ | |||
+ | |||
+ | <note important> | ||
+ | Il existe différents encodages binaires possibles pour les caractères : | ||
+ | * le code ASCII code les caractères du clavier anglais sur 7 bits, ce qui permet d' | ||
+ | * ainsi : | ||
+ | <code python> | ||
+ | code = ord('/' | ||
+ | print(code) | ||
+ | </ | ||
+ | * | ||
+ | * affiche la valeur '' | ||
+ | * La norme UTF-8 encode les caractères sur un nombre d' | ||
+ | * Exemple : le smiley ''' | ||
+ | <code python> | ||
+ | code = ord(' | ||
+ | print(code) | ||
+ | </ | ||
+ | * On peut inversement afficher le caractère à partir de son code entier : | ||
+ | <code python> | ||
+ | print(chr(233)) | ||
+ | print(chr(119070)) | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | === 3.1.3 Codage des mots et du texte === | ||
+ | Chaîne de caractère : | ||
+ | <code python> | ||
+ | s = " | ||
+ | </ | ||
+ | * '' | ||
+ | * ''" | ||
+ | * " | ||
+ | * assimilable à un tableau de caractère : | ||
+ | <code python> | ||
+ | for c in s : | ||
+ | print (c) | ||
+ | </ | ||
+ | Affiche : | ||
+ | b | ||
+ | o | ||
+ | n | ||
+ | j | ||
+ | o | ||
+ | u | ||
+ | r | ||
+ | |||
+ | Le programme affiche les caractère 1 par 1, c’est une " | ||
+ | |||
+ | **Donnée texte** | ||
+ | |||
+ | Un texte, au même titre qu'un mot, est une chaîne de caractères (dont la longueur est définie par la longueur de | ||
+ | la séquence de caractères qui définissent le texte, ponctuations, | ||
+ | <note tip> ** Les caractères séparateurs ** | ||
+ | |||
+ | Par définition les caractères séparateurs définissent la taille des espaces entre les mots, ainsi que les passages à la ligne lors de l' | ||
+ | * ''""'' | ||
+ | * ''" | ||
+ | * ''" | ||
+ | * ''" | ||
+ | * ''" | ||
+ | * etc. | ||
+ | </ | ||
+ | |||
+ | **Codage du texte** | ||
+ | |||
+ | L' | ||
+ | |||
+ | Pour traduire une //chaîne de caractères// | ||
+ | * ainsi, dans le système décimal, la position du chiffre dans le nombre définit à quelle puissance de 10 il appartient (unité, dizaines, centaines, etc...) Le chiffre le plus à gauche a la puissance la plus élevée et celui le plus à droite la puissance la plus faible. | ||
+ | * Si on suppose, pour simplifier, que chaque caractère est codé par un entier entre 0 et 255 (soit le code ASCII " | ||
+ | * Un tel nombre s' | ||
+ | * Il existe une fonction '' | ||
+ | * Exemple : | ||
+ | <code python> | ||
+ | s = ' | ||
+ | b = s.encode() | ||
+ | </ | ||
+ | Un nombre en base 256 est difficile à lire et interpréter. On le traduit en base 10 : | ||
+ | <code python> | ||
+ | i = int.from_bytes(b, | ||
+ | print(" | ||
+ | </ | ||
+ | Ce qui donne : | ||
+ | < | ||
+ | i = 852806586114976881510056778471769180697471859150728801241505293627173168229624211058 | ||
+ | </ | ||
+ | |||
+ | |||
+ | === 3.1.4 Textes et bases de textes === | ||
+ | |||
+ | |||
+ | * Bases de textes : ensemble constitué de plusieurs textes | ||
+ | * Bases de documents, | ||
+ | * Dossiers contenant des documents | ||
+ | * Collections de livres (électroniques) | ||
+ | * → 10 - 10⁴ | ||
+ | * Contenus en ligne (descriptifs de films, articles de journaux, descriptifs de produits.) | ||
+ | * → 10⁵ - 10⁶ | ||
+ | * Ensemble du web (les pages web, en tant que telles, peuvent être considérées comme du texte mis en forme par du html). | ||
+ | * → 10⁹ | ||
+ | * Messageries, | ||
+ | * 10³ - 10⁶ | ||
+ | |||
+ | ==== 3.2 Recherche dans les textes ==== | ||
+ | ==Exemples :== | ||
+ | * → Recherche d’un terme : “artichaud” | ||
+ | * → Recherche d’un motif (expression régulière) : une adresse email, une URL, un expéditeur, | ||
+ | |||
+ | ==Problématiques de la recherche de texte :== | ||
+ | |||
+ | * temps de réponse des algorithmes : | ||
+ | * l’utilisateur classique veut attendre moins de 2 à 3 secondes. | ||
+ | * Sur des bases extrêmement grandes (type recherche web), il faut donc être très performant pour atteindre ces temps de réponses. | ||
+ | * Stockage des données : | ||
+ | * intégralité des textes ou simple descriptif/ | ||
+ | * Les moteurs de recherche par exemple ne stockent aucune page web, ils ne stockent que des index et des références. | ||
+ | |||
+ | |||
+ | ==Remarque :== | ||
+ | Un document texte pourra être décrit soit comme : | ||
+ | * une séquence de caractères (lettres) | ||
+ | * une séquence de termes (mots) | ||
+ | |||
+ | |||
+ | === 3.2.1 Rechercher un terme === | ||
+ | |||
+ | ** Recherche simple ** | ||
+ | |||
+ | '' | ||
+ | On cherche un algorithme qui retourne toutes les occurrences (position dans le doc) d’un certain terme '' | ||
+ | |||
+ | '' | ||
+ | |||
+ | '' | ||
+ | |||
+ | "Les amis de mes amis sont mes amis." | ||
+ | | ||
+ | | ||
+ | |||
+ | * → La position de la première occurrence du terme t : | ||
+ | * → Les positions de toutes les occurrences du terme t : | ||
+ | * Complexité : O(m×k) | ||
+ | |||
+ | on note '' | ||
+ | |||
+ | < | ||
+ | Algo : recherche_simple | ||
+ | Données : d, t : chaînes de caractères | ||
+ | Début | ||
+ | n = len (d) | ||
+ | m = len (t) | ||
+ | i <-- 0 | ||
+ | tant que i < n - m: | ||
+ | j <-- 0 | ||
+ | tant que j < m et d[i+j] = t[j] : | ||
+ | j += 1 | ||
+ | si j == m : | ||
+ | | ||
+ | sinon : | ||
+ | i <-- i + 1 | ||
+ | Fin | ||
+ | </ | ||
+ | |||
+ | **Remarque :** Il peut être nécessaire de vérifier que le terme est précédé et suivi par les caractères d’espacement pour éviter de détecter les mots dont le mot recherché est préfixe ou suffixe. | ||
+ | |||
+ | Cette approche a un inconvénient : après une comparaison infructueuse, | ||
+ | |||
+ | ** Algorithme de Knuth-Morris-Pratt ** | ||
+ | |||
+ | L' | ||
+ | |||
+ | * On suppose qu'on peut tester si un caractère '' | ||
+ | * Le but est de calculer un décalage permettant de ne pas inspecter les positions où il n'y a aucune chance de trouver le motif '' | ||
+ | * On commence par chercher la position '' | ||
+ | * On inspecte la chaîne '' | ||
+ | * Soit '' | ||
+ | * On note '' | ||
+ | * Le décalage est égal à '' | ||
+ | * Si on ne trouve rien, le décalage vaut '' | ||
+ | |||
+ | <note tip> | ||
+ | Exemple | ||
+ | RECHERCHE DE CHAINES CODEES EN MACHINE | ||
+ | CHINE | ||
+ | CHINE | ||
+ | CHINE | ||
+ | CHINE | ||
+ | CHINE | ||
+ | CHINE | ||
+ | CHINE | ||
+ | CHINE | ||
+ | CHINE | ||
+ | CHINE | ||
+ | RECHERCHE DE CHAINES CODEES EN MACHINE | ||
+ | </ | ||
+ | < | ||
+ | Algo : recherche améliorée (Knuth-Morris-Pratt) | ||
+ | Données : d, t : chaînes de caractères | ||
+ | Début: | ||
+ | n = len (d) | ||
+ | m = len (t) | ||
+ | i <-- m - 1 | ||
+ | tant que i < n : | ||
+ | # PRE-TRAITEMENT | ||
+ | j <-- 0 | ||
+ | tant que j < m - 1: | ||
+ | c = d[i - j] | ||
+ | si c appartient à t[:m-j-1] | ||
+ | k <-- dernière_occurrence(c, | ||
+ | | ||
+ | break | ||
+ | sinon | ||
+ | j += 1 | ||
+ | si j == m - 1: | ||
+ | | ||
+ | # TRAITEMENT | ||
+ | j <-- 0 | ||
+ | tant que j < m : | ||
+ | si t[m - j - 1] = d[i - j] | ||
+ | j += 1 | ||
+ | sinon | ||
+ | break | ||
+ | si j = m: | ||
+ | retourner i - m + 1 | ||
+ | # DECALAGE | ||
+ | i <-- i + decalage | ||
+ | retourner -1 | ||
+ | Fin | ||
+ | </ | ||
+ | |||
+ | |||
+ | === 3.2.2 Compter les mots === | ||
+ | |||
+ | |||
+ | Lecture séquentielle des caractères : | ||
+ | "Les amis de mes amis sont mes amis." | ||
+ | | ||
+ | | ||
+ | |||
+ | * Il ne faut compter que les debuts de mots | ||
+ | * Un début de mot est un caractère // | ||
+ | < | ||
+ | {a, | ||
+ | </ | ||
+ | * Tout ce qui n'est pas alphanumérique est un caractère // | ||
+ | < | ||
+ | {!,#, | ||
+ | </ | ||
+ | * Autrement dit on compte les couples (caractère séparateur, | ||
+ | * remarque : le début de chaîne compte comme un caractère séparateur | ||
+ | |||
+ | **remarque** : pour extraire la liste des mots présents dans le texte, on doit identifier les débuts et les fins de mots : | ||
+ | * un début de mot est un couple (sep., alphanum.) | ||
+ | * une fin de mot est un couple (alphanum., sep.) | ||
+ | |||
+ | < | ||
+ | Algo : compte-mots | ||
+ | Données : | ||
+ | - d : chaîne de caractères | ||
+ | Début: | ||
+ | nb_mots <-- 0 | ||
+ | sep <-- Vrai | ||
+ | pour tout c dans d: | ||
+ | si sep est Vrai et c est alphanumérique: | ||
+ | sep <-- Faux | ||
+ | nb_mots <-- nb_mots + 1 | ||
+ | sinon si sep est Faux et c est séparateur: | ||
+ | sep <-- Vrai | ||
+ | retourner nb_mots | ||
+ | Fin | ||
+ | </ | ||
+ | |||
+ | Code équivalent : compter les mots à l'aide d'un automate fini: | ||
+ | |||
+ | {{: | ||
+ | <code python> | ||
+ | def compte_mots(d): | ||
+ | state = 0 | ||
+ | cpt = 0 | ||
+ | for i in range(len(d)): | ||
+ | if state == 0 and is_alpha(d[i]): | ||
+ | state = 1 | ||
+ | cpt += 1 | ||
+ | if state == 1 and is_sep(d[i]): | ||
+ | state = 0 | ||
+ | return cpt | ||
+ | </ | ||
+ | |||
+ | **Présentation**: | ||
+ | |||
+ | * les sommets du graphe sont les états. Un état identifie une étape de calcul. L' | ||
+ | * les arêtes représentent les transitions d' | ||
+ | |||
+ | Pour réaliser des calculs, on a besoin d' | ||
+ | |||
+ | Enfin, des résultats de calcul sont produits en sortie de l' | ||
+ | |||
+ | Plus concrètement, | ||
+ | |||
+ | **Définition**: | ||
+ | |||
+ | Un automate fini est défini par : | ||
+ | * un alphabet d' | ||
+ | * un alphabet de sortie Σ' | ||
+ | * un ensemble (fini) de sommets : S | ||
+ | * un ensemble fini d' | ||
+ | * un état initial s0∈S | ||
+ | |||
+ | L' | ||
+ | |||
+ | <note tip> | ||
+ | Exemple : un automate qui effectue l' | ||
+ | * Σ={0,1}² | ||
+ | * Σ′={0,1} | ||
+ | * S={1,2} | ||
+ | * s0=1 | ||
+ | {{: | ||
+ | </ | ||
+ | La famille des automates finis définit une classe de calculs (l' | ||
+ | * séquences | ||
+ | * boucles et branchements conditionnels | ||
+ | |||
+ | Mais pas : | ||
+ | * appels récursifs | ||
+ | |||
+ | remarque: | ||
+ | * automates à piles (calcul récursif) | ||
+ | * machines de Turing et machines de Turing universelles (calcul sur des automates) | ||
+ | permettant d' | ||
+ | |||
+ | === 3.2.3 Recherche de motifs et expressions régulières === | ||
+ | |||
+ | De manière plus générale recherche d’expressions peut être effectuée à l’aide d’automates finis **non déterministes**. | ||
+ | * Parmi les états on distingue les états initiaux et terminaux. | ||
+ | * Il existe (parfois) plusieurs transitions possibles pour un même symbole lu | ||
+ | * Lorsque l' | ||
+ | |||
+ | Remarque : pour tout automate fini non déterministe A, il existe un automate fini déterministe A′ qui reconnait le même langage (plus compliqué à écrire). | ||
+ | |||
+ | Représentation graphique : | ||
+ | * les états dans des cercles, | ||
+ | * l’unique état initial par une flèche pointant sur un état, | ||
+ | * les états terminaux par un double cercle concentrique sur l’état. | ||
+ | * Les transitions d’état quant à elles sont représentées par une flèche allant de l’état de départ jusqu’à l’état d’arrivée indexée par le caractère (ou le groupe de caractères) autorisant la transition. | ||
+ | |||
+ | |||
+ | Lecture séquentielle des caractères : | ||
+ | "Les amis de mes amis sont mes amis." | ||
+ | | ||
+ | | ||
+ | |||
+ | |||
+ | <note tip> | ||
+ | Exemple : mots se terminant par ab | ||
+ | * Σ={a,b} | ||
+ | |||
+ | L' | ||
+ | ab | ||
+ | bab | ||
+ | abab | ||
+ | bbab | ||
+ | aabab | ||
+ | abbab | ||
+ | babab | ||
+ | bbbab | ||
+ | aaabab | ||
+ | etc.. | ||
+ | | ||
+ | {{: | ||
+ | </ | ||
+ | |||
+ | **Exemples**: | ||
+ | * Reconnaître un nombre entier : '' | ||
+ | {{: | ||
+ | * Reconnaître un nombre réel : | ||
+ | * TODO | ||
+ | |||
+ | **Remarques** : | ||
+ | * Les classes d' | ||
+ | * En python, les expressions régulières s' | ||
+ | |||
+ | Traduction de l' | ||
+ | [ab]*ab | ||
+ | | ||
+ | Remarque : les langages qui peuvent être reconnus par des expressions régulières sont appelés les //langages réguliers// | ||
+ | |||
+ | Exemples de langages non réguliers: | ||
+ | * reconnaître les palindromes | ||
+ | * reconnaître une expression arithmétique | ||
+ | * vérifier la syntaxe d'un code informatique | ||
+ | |||
+ | |||
+ | |||
+ | === Syntaxe des expressions régulières Python === | ||
+ | |||
+ | Définition : Il s’agit d’une syntaxe “condensée” de description d’automates finis permettant de reconnaître des motifs dans un texte. | ||
+ | |||
+ | En Python, les expressions régulières sont implémentées dans la librairie '' | ||
+ | |||
+ | <code python> | ||
+ | |||
+ | import re | ||
+ | |||
+ | d = "Les astronautes de la mission Gemini 8 sont désignés le 20 septembre 1965 : Armstrong est le commandant et David Scott le pilote. Ce dernier est le premier membre du groupe d' | ||
+ | |||
+ | liste_termes = re.findall(r" | ||
+ | </ | ||
+ | |||
+ | == Transitions : caractères et groupes de caractères== | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | Def : une expression est définie comme une suite de transition. Le mot est accepté lorsque la suite de transitions est respectée | ||
+ | |||
+ | Exemple : | ||
+ | r" | ||
+ | accepte chalet et chalut | ||
+ | r" | ||
+ | accepte tous les mots de 3 lettres | ||
+ | |||
+ | **Branchements et Récursion** | ||
+ | * Les parenthèses permettent : | ||
+ | * de factoriser une expression (qui peut alors être traitée comme une transition) | ||
+ | * '' | ||
+ | * de définir des branchements : | ||
+ | * '' | ||
+ | |||
+ | * '' | ||
+ | * '' | ||
+ | * ''?'' | ||
+ | |||
+ | ==exemples== | ||
+ | |||
+ | * reconnaître une adresse mail : | ||
+ | < | ||
+ | | ||
+ | </ | ||
+ | ==== 3.3 Complétion / Correction ==== | ||
+ | Un algorithme de complétion est un mécanisme logique permettant d' | ||
+ | |||
+ | On utilise pour cela une structure de données arborescente, | ||
+ | |||
+ | On commence par construire un arbre de complétion à partir de mots de vocabulaire, | ||
+ | |||
+ | <note tip> | ||
+ | V = {art, arbre, des, dessin} | ||
+ | |||
+ | {{: | ||
+ | </ | ||
+ | |||
+ | L' | ||
+ | * Pour chaque nœud, le nombre de fils est de l' | ||
+ | * La hauteur maximale est celle de la taille maximale des mots de vocabulaire nmax | ||
+ | * Par construction, | ||
+ | |||
+ | Une fois l' | ||
+ | |||
+ | Exemple : | ||
+ | * début de mot : '' | ||
+ | * complétions possibles : '' | ||
+ | ==== 3.4 Comparaison/ | ||
+ | On cherche à exprimer une distance entre deux chaînes de caractères. | ||
+ | Une distance entre 2 textes d1 et d2 est telle que : | ||
+ | * dist(d1,d2) = dist(d2,d1) | ||
+ | * dist(d1,d2) ≥ 0 | ||
+ | * dist(d1,d2) + dist(d2,d3) ≥ dist(d1,d3) | ||
+ | |||
+ | === Distance de Hamming | ||
+ | La distance de Hamming entre deux chaînes de même taille est définie comme le nombre de caractères non appariés. Ainsi la distance de Hamming entre " | ||
+ | |||
+ | |||
+ | **Exemple** : | ||
+ | |||
+ | p a s s o i r e | ||
+ | | | | x x x x | | ||
+ | p a s t e q u e | ||
+ | |||
+ | distance = 4 | ||
+ | |||
+ | Peut-on généraliser cette distance à des chaînes de taille différente? | ||
+ | |||
+ | === Distance d' | ||
+ | La distance d’édition est définie, pour deux chaînes de longueur quelconque, comme le nombre minimal d’opérations permettent de transformer d1 en d2, avec les opérations suivantes : | ||
+ | * **ins**(a) ⇢ insertion du caractère a | ||
+ | * **perm** (a, b) ⇢ remplacement de a par b | ||
+ | * **del** (a) ⇢ suppression du caractère a | ||
+ | |||
+ | Il existe différentes manières de transformer la chaîne d1 en d2. On peut par exemple supprimer tous les caractères de d1 et insérer tous les caractères de d2, mais c'est rarement le nombre d' | ||
+ | |||
+ | - Exemples: | ||
+ | * distance entre " | ||
+ | < | ||
+ | - r o b - e | ||
+ | v | ^ | v | | ||
+ | a r - b r e | ||
+ | </ | ||
+ | dist = 3 | ||
+ | < | ||
+ | r o b - e | ||
+ | x | x v | | ||
+ | p o r t e | ||
+ | </ | ||
+ | dist = 3 | ||
+ | < | ||
+ | a - r b r e | ||
+ | x v | x ^ | | ||
+ | p o r t - e | ||
+ | </ | ||
+ | dist = 4 | ||
+ | |||
+ | |||
+ | ===Calcul complet cloche/ | ||
+ | |||
+ | La résolution de ce problème repose sur les principes de la programmation dynamique. | ||
+ | |||
+ | Un problème d' | ||
+ | * un problème | ||
+ | * un ensemble de solutions à ce problème | ||
+ | * une fonction de coût (ou une fonction objectif) qui attribue un coût (resp un gain) à chacune des solutions possibles apportées au problème | ||
+ | |||
+ | Le nombre de solutions possibles à un problème d' | ||
+ | |||
+ | Certains problèmes d'OC peuvent être résolus selon le principe de la **programmation dynamique** qui consiste à décomposer le problème en sous-problèmes (et en sous-solutions): | ||
+ | * soit un problème P présentant une solution S de coût C | ||
+ | * Étant donné un sous problème p⊂P, | ||
+ | * on liste l' | ||
+ | * et on sélectionne celle dont le coût est le plus faible | ||
+ | * on modifie S selon la sous-solution sélectionnée | ||
+ | * on met à jour le coût global | ||
+ | * on met à jour le sous-problème | ||
+ | * et on recommence jusqu' | ||
+ | |||
+ | Dans le cas de l' | ||
+ | * une solution est un ensemble de transformations acceptables pour passer de la chaîne A à la chaîne B | ||
+ | * le coût est la somme des coûts des transformations appliquées | ||
+ | * un sous-problème consiste à apparier un morceau de A avec un morceau de B | ||
+ | |||
+ | En pratique: | ||
+ | * on représente l’ensemble des transformations de d1 vers d2 sous la forme d’un tableau de (m + 1) lignes et (n + 1) colonnes, avec m = |d1| et n = |d2| | ||
+ | * pour chaque case (i,j) du tableau, | ||
+ | * le passage vers la case (i, j+1) correspond à ins(d2[j]) | ||
+ | * le passage vers la case (i+1, j) correspond à del(d1[i]) | ||
+ | * le passage vers la case (i+1, j+1) correspond à perm(d1[i], | ||
+ | * la valeur de la distance au niveau de la case (i,j) est égale au minimum de : | ||
+ | * 1 + dist(i, j+1) | ||
+ | * 1 + dist(i+1, j) | ||
+ | * dist(i+1, j+1) si d1[i]=d2[j], | ||
+ | * la distance au niveau de la case (m,n) vaut 0 | ||
+ | * la distance d' | ||
+ | |||
+ | {{: | ||
+ | |||
+ | === Algorithme === | ||
+ | |||
+ | Préparation | ||
+ | |||
+ | < | ||
+ | variables globales : d1, d2 : chaînes de caractères | ||
+ | m = |d1| | ||
+ | n = |d2| | ||
+ | </ | ||
+ | |||
+ | Récursif!! | ||
+ | < | ||
+ | algo : distance | ||
+ | données : | ||
+ | i, j : etape de calcul | ||
+ | début | ||
+ | si i = m et j = n : | ||
+ | | ||
+ | sinon si i = m : | ||
+ | | ||
+ | sinon si j = n : | ||
+ | | ||
+ | sinon si d1[i] = d2[j] : | ||
+ | | ||
+ | sinon | ||
+ | | ||
+ | fin | ||
+ | </ | ||
+ | |||
+ | === Alignement glouton === | ||
+ | |||
+ | {{: | ||
+ | |||
+ | ===== 4. Fichiers et indexation ===== | ||
+ | |||
+ | <note tip> | ||
+ | Les données numériques sont une des composantes essentielles des programmes informatiques. | ||
+ | * Il s'agit par définition des // | ||
+ | * Avec l’augmentation des capacités de stockage et leur mise en réseau, les quantités de données conservées ont considérablement augmenté au cours des dernières décennies. | ||
+ | |||
+ | Dans le cadre de ce cours, nous aborderons : | ||
+ | * la question du stockage de ces données sur un support informatique (Fichiers, bases de données), | ||
+ | * ainsi que les méthodes permettant de consulter et mettre à jour régulièrement ces données. | ||
+ | </ | ||
+ | |||
+ | |||
+ | ====4.1 Données et fichiers==== | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | === 4.1.3 Transport et flux de données === | ||
+ | |||
+ | * La transmission des données entre programmes nécessite l’ouverture d’un canal de communication | ||
+ | * entre client et serveur | ||
+ | * par lequel transitent les données (les requêtes et les réponses). | ||
+ | * Le transport est géré | ||
+ | * par le système d’exploitation (lorsque les données transitent au sein d’un même ordinateur) | ||
+ | * ainsi que par des routeurs (lorsque les données transitent d’un ordinateur à l’autre sur le réseau). | ||
+ | * Au niveau du client, | ||
+ | * les réponses en provenance du serveur sont organisées sous la forme d’une liste, | ||
+ | * qu’on appelle un **flux de données**. | ||
+ | <note tip> | ||
+ | La notion de flux de données signifie que les réponses sont lues dans un ordre fixe, telles qu’elles ont été écrites au niveau du serveur. On parle de lecture à accès **séquentiel** (par opposition à la lecture à accès aléatoire). | ||
+ | </ | ||
+ | |||
+ | == Formats d' | ||
+ | |||
+ | Les principaux formats d' | ||
+ | * csv | ||
+ | * json | ||
+ | * xml | ||
+ | < | ||
+ | TODO | ||
+ | </ | ||
+ | |||
+ | Exemples : | ||
+ | * {{http:// | ||
+ | * {{http:// | ||
+ | * {{http:// | ||
+ | * {{http:// | ||
+ | |||
+ | |||
+ | ===4.1.4 Conservation des données === | ||
+ | |||
+ | La conservation des données repose principalement sur la **structure de stockage**, | ||
+ | * définissant la manière dont les données sont physiquement stockées sur le support, | ||
+ | * autrement dit la méthode de **rangement** de la série de mesures : | ||
+ | * fichiers, | ||
+ | * répertoires, | ||
+ | * index, | ||
+ | * etc... | ||
+ | * reposant sur des supports de stockage (ou mémoires) : | ||
+ | * mémoire centrale, | ||
+ | * mémoires secondaires (disque dur, CD-ROM, memoire flash (SSD), etc...). | ||
+ | |||
+ | |||
+ | === Trame et bloc de données === | ||
+ | |||
+ | Un jeu de valeurs encodé et stocké sur un support informatique est appelé un “**enregistrement**”, | ||
+ | * conservé sous la forme d'une **trames de données**. | ||
+ | * Une trame peut obéir à un format //textuel// ou //binaire// | ||
+ | |||
+ | **Encodage binaire :** | ||
+ | |||
+ | * Définition d’une trame, en général de taille fixe. | ||
+ | * Chaque rubrique occupe un nombre d’octets déterminé, | ||
+ | * L’utilisation de trames de taille fixe facilite le stockage et la conservation des données sur les supports magnétiques (disque dur, etc...) | ||
+ | * Les données sont transmises dans un format numérique (type) identique à celui utilisé en mémoire centrale. | ||
+ | |||
+ | < | ||
+ | |||
+ | {{https:// | ||
+ | </ | ||
+ | |||
+ | **Encodage textuel :** | ||
+ | |||
+ | * Le jeu de données est codé dans un format descriptif (contenant à la fois les valeurs et une description des données : types, attributs, ...). | ||
+ | * Ce format facilite la transmission d’un programme à un autre (format “plat”) mais est moins propice au stockage. | ||
+ | * La “sérialisation” est l’opération qui consiste à encoder des données sous la forme d’un texte brut (codage ASCII ou utf8), en “perdant” le moins possible d’information. | ||
+ | * Des exemples de formats textes standards sont donnés en [[public: | ||
+ | |||
+ | === Tableaux statiques === | ||
+ | |||
+ | == Bloc de données == | ||
+ | Un **bloc de données** correspond à une série d’enregistrements obéissant au même **format**: | ||
+ | * Chaque enregistrement est de taille identique; | ||
+ | * L' | ||
+ | |||
+ | La structure de base servant à stocker à une série d’enregistrements est le tableau de données à 2 dimensions : | ||
+ | * Tableau de données (data frame) = intitulé de colonnes + liste de lignes | ||
+ | * Intitulé de colonne = nom de l’attribut | ||
+ | * Une ligne = un enregistrement | ||
+ | Structure sous-jacente : tableau à 2 dimensions (ou matrice de données) | ||
+ | < | ||
+ | {{https:// | ||
+ | </ | ||
+ | |||
+ | == Tableau statique== | ||
+ | Un bloc de données obéit formellement à une structure de type **tableau statique**: | ||
+ | * Un tableau statique est une structure séquentielle **de taille fixe**, constituée de N " | ||
+ | * Les cases peuvent être " | ||
+ | |||
+ | |||
+ | <note tip> | ||
+ | Le tableau statique correspond à l' | ||
+ | * taille limitée du support matériel | ||
+ | * données accessibles grâce à leur **adresse** (position dans le tableau) | ||
+ | * problème de rangement (il faut conserver une information sur la position des données déjà enregistrées) => organisation //logique// des données sur le support. | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | * Dans un **tableau statique** '' | ||
+ | * '' | ||
+ | * Analogie : les pages d'un cahier{{ : | ||
+ | |||
+ | * Dans un **tableau dynamique** (liste python par exemple), la position des cases varie au cours de l' | ||
+ | * '' | ||
+ | * Analogie : briques de lego, puzzle glissant | ||
+ | {{ : | ||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | === Structure de stockage === | ||
+ | |||
+ | Les mémoires informatiques sont des structures statiques. Une fois les données sauvegardées sur le disque, il est difficile d’insérer ou de supprimer des éléments. | ||
+ | |||
+ | La difficulté consiste à définir une // | ||
+ | * savoir où enregistrer les données | ||
+ | * savoir comment les retrouver | ||
+ | |||
+ | On parle de //structure de stockage//. Une telle structure doit permettre : | ||
+ | * d’ajouter des données | ||
+ | * d' | ||
+ | * d’accéder rapidement à une case particulière | ||
+ | |||
+ | === Stockage dense === | ||
+ | On considère un ensemble de '' | ||
+ | |||
+ | Remarques : | ||
+ | * Les cases du tableau sont numérotées de '' | ||
+ | * Les données sont de type quelconque mais chaque case ne peut contenir qu'une donnée | ||
+ | * Si '' | ||
+ | * '' | ||
+ | |||
+ | **Propriété ** : les données sont stockés dans les '' | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Opérations fondamentales : | ||
+ | * insertion de données : O(1) | ||
+ | * recherche de données : O(k) | ||
+ | * suppression de données : O(k) | ||
+ | |||
+ | === Stockage distribué === | ||
+ | |||
+ | On conserve une table des cases libres | ||
+ | * **Index bitmap** : | ||
+ | * Chaque bit correspond à une case (libre/ | ||
+ | * Lors de l’écriture d'une nouvelle donnée (allocation), | ||
+ | * Lorsque la donnée est effacée, le bit correspondant passe de 1 à 0 | ||
+ | B=0010010100100.....01n−1 | ||
+ | * **Table d' | ||
+ | * On considère un tableau de taille n dans lequel k<n cases sont occupées. | ||
+ | * Chaque //bloc de données// d est indexée par l' | ||
+ | * On connaît également sa taille m. | ||
+ | * La //table d' | ||
+ | * sa position i | ||
+ | * le nombre m de cases occupées | ||
+ | |||
+ | // | ||
+ | |||
+ | Stratégie par bloc: on alloue des blocs composés de plusieurs cases (S’il existe des blocs libres consécutifs, | ||
+ | |||
+ | On souhaite : | ||
+ | * minimiser le nombre de blocs libres | ||
+ | * maximiser la taille des blocs libres | ||
+ | |||
+ | * Plus proche choix : la liste des blocs libres est parcourue jusqu’à trouver un bloc de la taille demandée (ou sinon, le premier bloc de taille supérieure, | ||
+ | * first fit : le premier bloc suffisamment grand pour les besoins | ||
+ | * best fit : le plus petit bloc qui ait une taille au moins égale à la taille demandée | ||
+ | * worst fit : le plus grand bloc disponible (qui est donc découpé) | ||
+ | |||
+ | < | ||
+ | |||
+ | Écrire un algorithme permettant d' | ||
+ | </ | ||
+ | |||
+ | Autre stratégie (allocation rapide): | ||
+ | On alloue des blocs de 1, | ||
+ | |||
+ | Problème des stratégies par bloc: s’il y a trop de données, on obtient des blocs de taille 1 --> nécessité de réorganiser (défragmenter) | ||
+ | |||
+ | ===4.1.5 Fichiers et répertoires=== | ||
+ | |||
+ | La mémoire secondaire n’est pas directement accessible (les programmes n’ont pas la possibilité d’aller écrire directement sur le disque). Le système d’exploitation assure ainsi l’indépendance du programme par rapport à l’emplacement des données, au travers d’instructions d’entrée/ | ||
+ | |||
+ | Pour que les programmes puissent écrire sur le disque, on introduit des objets intermédiaires : les fichiers. | ||
+ | |||
+ | <note important> | ||
+ | **A retenir :** | ||
+ | * Un fichier est une référence vers un ou plusieurs blocs de données, enregistrés sur un support physique. | ||
+ | * Un fichier est caractérisé par son descripteur, | ||
+ | </ | ||
+ | |||
+ | * La gestion des fichiers est une des fonctions essentielles des systèmes d’exploitation : | ||
+ | * possibilité de traiter et conserver des quantités importantes de données | ||
+ | * possibilité de partager des données entre plusieurs programmes. | ||
+ | |||
+ | <note tip> | ||
+ | ** Opérations de base ** : | ||
+ | * // | ||
+ | * //Lecture// : consultation des lignes l'une après l' | ||
+ | * // | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Volume** | ||
+ | |||
+ | Le volume est le support sur lequel sont enregistrées les données. On parle de mémoire secondaire (Disque dur, disquette, | ||
+ | |||
+ | **Page** (ou secteur) | ||
+ | |||
+ | Les pages sont les unités de base pour la lecture et l' | ||
+ | |||
+ | La mémoire secondaire est donc organisée comme un tableau de pages : (T[0], | ||
+ | </ | ||
+ | |||
+ | ** Répertoires ** | ||
+ | Chaque volume possède un numéro appelé le label du volume. | ||
+ | Tous les descripteurs de fichiers sont regroupés dans une table des matières appelée Répertoire (Directory). | ||
+ | |||
+ | Remarque : cette table des matières est en fait un fichier dont le descripteur est contenu dans le label du volume. | ||
+ | |||
+ | **Organisation hiérarchique :** | ||
+ | * Lorsque le nombre de fichiers est élevé, les descripteurs de fichiers sont classés dans plusieurs répertoires, | ||
+ | * Le répertoire de plus bas niveau hiérarchique est appelé racine → chemin d’accès (path) | ||
+ | |||
+ | {{: | ||
+ | |||
+ | === Consultation des données : lecture d’un fichier (Read)=== | ||
+ | Méthode traditionnelle pour le traitement de fichiers de petite taille. La consultation des données nécessite d’ouvrir une “communication” entre le programme et les fichiers. Ce canal de communication permet de recevoir un flux de données. | ||
+ | |||
+ | Pour établir la communication, | ||
+ | le “chemin d’accès” aux données (disque dur local) | ||
+ | l’”adresse” des données (lorsqu’il s’agit de données stockées sur un serveur distant) | ||
+ | |||
+ | L’opération d’ouverture de fichier initialise un descripteur de fichier, qui sert à désigner (dans le programme) le fichier sur lequel on travaille, et d’accéder au contenu du flux. | ||
+ | |||
+ | Ouverture simple: | ||
+ | |||
+ | <note tip> **Python** | ||
+ | |||
+ | f = open('/ | ||
+ | |||
+ | Le deuxième argument représente le mode d’ouverture, | ||
+ | </ | ||
+ | |||
+ | ==Ouverture avec test : == | ||
+ | Il est important de vérifier que cette opération d’ouverture s’effectue correctement avant de poursuivre le programme (nombreuses possibilités d’erreur : fichier effacé, erreur de nom, pas de droits de lecture, | ||
+ | On utilise une instruction de test spécifique pour vérifier que l’ouverture du fichier s’est correctement effectuée, de type '' | ||
+ | |||
+ | <note tip> | ||
+ | **Python** | ||
+ | |||
+ | try : | ||
+ | f = open('/ | ||
+ | except IOError: | ||
+ | print " | ||
+ | </ | ||
+ | |||
+ | Lorsque l’opération d’ouverture est réalisée avec succès, le flux de données devient accessible en lecture (les premières lignes du fichier sont chargées en mémoire et une tête de lecture se positionne sur le premier caractère de la première ligne). Il ne reste plus qu’à lire les données. | ||
+ | |||
+ | |||
+ | |||
+ | La consultation des données s’effectue séquentiellement à l’aide de l’opérateur de lecture '' | ||
+ | |||
+ | <note tip> | ||
+ | **Algorithmes de bas niveau (niveau système d’exploitation)** | ||
+ | |||
+ | Remarque : | ||
+ | // | ||
+ | |||
+ | Les opérateurs lire_ligne (readline) et écrire_ligne (write) ne travaillent pas directement sur les données du fichier. Les données du fichier sont chargées en mémoire centrale dans une mémoire “tampon”. L’objet f servant à décrire le fichier a comme attributs : | ||
+ | * t : table des pages, | ||
+ | * i : numero de la page courante, | ||
+ | * p : tableau d' | ||
+ | * j : position dans la page courante (tête de lecture). | ||
+ | |||
+ | Lors des opération de lecture, la mémoire tampon est mise à jour au fur et à mesure qu’on avance dans la lecture du fichier par des opérations de lecture sur le disque. En général, plusieurs pages sont chargées en avance. | ||
+ | Lors d’une opération d’écriture, | ||
+ | </ | ||
+ | |||
+ | Si on suppose que les données sont rangées sous la forme d’un tableau de lignes, chaque opération de lecture consiste à consulter une ligne du tableau, et à positionner la tête de lecture sur la ligne suivante. | ||
+ | |||
+ | <note tip> | ||
+ | **Exemples :** lecture de données texte : chaque opération de lecture lit tous les caractères jusqu’au caractère “fin de ligne”. | ||
+ | |||
+ | __ 1. Lecture d’une ligne unique :__ | ||
+ | |||
+ | **Python** | ||
+ | s = f.readline() | ||
+ | |||
+ | |||
+ | __ 2. Lecture de toutes les lignes (la lecture s’effectue dans une boucle) + affichage de la ligne:__ | ||
+ | |||
+ | **Python** | ||
+ | |||
+ | for s in f : | ||
+ | print s | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | === Enregistrement des données : sauvegarde dans un fichier (Write)=== | ||
+ | |||
+ | L’opération de sauvegarde des données est l’opération complémentaire de la lecture. De nouvelles données doivent être enregistrées sur le disque dur en vue d’une consultation future. | ||
+ | Le format de sauvegarde peut être de type texte ou de type binaire. Nous présentons ici la sauvegarde des données dans des formats texte. | ||
+ | |||
+ | Comme dans le cas de l’opération de lecture, il faut au préalable définir dans le programme un descripteur de fichier servant de point d’entrée pour les opération d’écriture. On effectue ce qu’on appelle une ouverture en mode “écriture”. | ||
+ | |||
+ | |||
+ | **Python** | ||
+ | try : | ||
+ | f = open(' | ||
+ | except IOError: | ||
+ | print " | ||
+ | | ||
+ | |||
+ | |||
+ | On notera qu’il existe en python (ainsi qu’en C, C++, …) plusieurs modes d’ouverture exprimés par le deuxième argument de la fonction open. On retiendra le mode ‘w’ (création d’un nouveau fichier vide) et le mode ‘a’ (ajout de nouvelles données à la suite d’un fichier déjà existant). | ||
+ | |||
+ | La sauvegarde dans le fichier s’effectue à l’aide d’un opérateur d’écriture. Dans le cas des chaînes de caractères, | ||
+ | |||
+ | |||
+ | **Python** | ||
+ | f.write(" | ||
+ | |||
+ | |||
+ | |||
+ | La sauvegarde de données nécessite d’effectuer un choix sur le mode d’encodage, | ||
+ | |||
+ | Une fois les opérations de lecture ou d’écriture terminées, il est nécessaire de fermer le fichier. L’opération de fermeture assure que les données sont effectivement enregistrées sur le disque (et non simplement stockées dans la mémoire tampon | ||
+ | |||
+ | |||
+ | |||
+ | **Voir aussi** : | ||
+ | * [[public: | ||
+ | |||
+ | |||
+ | |||
+ | ==== 4.2 Index et Données ==== | ||
+ | <note tip> **Rappel ** | ||
+ | |||
+ | Une //donnée informatique// | ||
+ | * Consultable/ | ||
+ | * Possibilité de la conserver sur un support de stockage numérique (CD-ROM, disque dur, SSD, ...) | ||
+ | * Les informations peuvent être stockés dans un fichier (ex : fichier csv). | ||
+ | * Un jeu de valeurs encodé et enregistré est appelé un // | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | Pour une gestion efficace des données, il est nécessaire de pouvoir identifier chaque enregistrement de façon unique. | ||
+ | |||
+ | L' | ||
+ | |||
+ | === 4.2.1 Définitions et propriétés === | ||
+ | |||
+ | * L' | ||
+ | * On parle également | ||
+ | |||
+ | On peut représenter l' | ||
+ | |||
+ | |||
+ | === Unicité/ | ||
+ | L' | ||
+ | |||
+ | <note important> | ||
+ | * soient d1 et d2 deux enregistrements, | ||
+ | * Unicité : | ||
+ | * si d1=d2, alors k(d1)=k(d2). | ||
+ | * Spécificité: | ||
+ | * si k(d1)=k(d2), alors d1=d2. | ||
+ | </ | ||
+ | |||
+ | === Efficacité === | ||
+ | |||
+ | L' | ||
+ | |||
+ | La recherche par identifiant repose sur une fonction d' | ||
+ | Ainsi si k est l' | ||
+ | * i=I(k) (lecture de l' | ||
+ | * d=D[i] (lecture des données elles mêmes) | ||
+ | |||
+ | <note tip> | ||
+ | La lecture de l' | ||
+ | L=((k1,i1),(k2,i2),...,(kN,iN)) telle que k1<k2<...<kN, de telle sorte que la recherche s' | ||
+ | </ | ||
+ | |||
+ | === Compacité === | ||
+ | |||
+ | L' | ||
+ | * |k|<<|d| | ||
+ | pour que : | ||
+ | * |L|<<|D| | ||
+ | |||
+ | <note tip> | ||
+ | Un identifiant entier, codé sur 4 octets, permet d' | ||
+ | </ | ||
+ | |||
+ | |||
+ | === 4.2.2 Utilisation === | ||
+ | |||
+ | ** Définir un ordre sur les données ** | ||
+ | |||
+ | La présence d'un identifiant permet de définir un ordre total sur les données : | ||
+ | * ordre sur les entiers (identifiant entier) | ||
+ | * ordre alphabétique (identifiant texte) | ||
+ | * ordre // | ||
+ | |||
+ | ** Lier les données ** | ||
+ | |||
+ | Dans le cas des bases de données, l' | ||
+ | |||
+ | __Exemple :__ | ||
+ | * {{http:// | ||
+ | * {{http:// | ||
+ | * {{http:// | ||
+ | |||
+ | * Pour chaque album de la table des albums, l' | ||
+ | * Pour chaque piste de la table des pistes, | ||
+ | |||
+ | < | ||
+ | **Exercice** : donner le nom du groupe qui interprète la piste '// | ||
+ | </ | ||
+ | |||
+ | |||
+ | ** Structure d' | ||
+ | |||
+ | L' | ||
+ | |||
+ | Soit E un // | ||
+ | E={d1,d2,...,dK} | ||
+ | On a l' | ||
+ | d∈E⇔k(d)∈I | ||
+ | |||
+ | Ainsi, il ne peut y avoir de doublon car ∀d : | ||
+ | * k(d) est unique | ||
+ | * i=I(k(d)) est unique ssi d∈E et indéfini sinon. | ||
+ | |||
+ | ==== 4.3 Exemples d' | ||
+ | |||
+ | === 4.3.1 Adressage des tableaux === | ||
+ | |||
+ | L' | ||
+ | * Soit D un tableau de n lignes | ||
+ | * le numéro i<n est à la fois l' | ||
+ | |||
+ | {{https:// | ||
+ | |||
+ | === 4.3.2 Maintenance centralisée d'un index=== | ||
+ | |||
+ | **Dans le cas général, l' | ||
+ | |||
+ | On sépare donc l' | ||
+ | * k est l' | ||
+ | * i est l' | ||
+ | |||
+ | <note important> | ||
+ | Lors de l' | ||
+ | * l'// | ||
+ | * l' | ||
+ | </ | ||
+ | |||
+ | Il existe différentes méthodes permettant d' | ||
+ | * Le programme maintient une liste triée des identifiants déjà utilisées. Lors de l' | ||
+ | * Coût : | ||
+ | * O(n) en mémoire | ||
+ | * O(logn) pour l' | ||
+ | * Dans le cas où les identifiants sont des numéros (entiers), il est possible d' | ||
+ | * Coût : | ||
+ | * O(1) en mémoire | ||
+ | * O(1) pour l' | ||
+ | |||
+ | < | ||
+ | **Exemples d' | ||
+ | * numéro INE (étudiants) | ||
+ | * numéro URSSAF (sécurité sociale) | ||
+ | * numéro d' | ||
+ | * numéro de compte en banque | ||
+ | * code barre | ||
+ | * etc. | ||
+ | </ | ||
+ | |||
+ | |||
+ | === 4.3.3 Indexation pseudo-aléatoire : les fonctions de hachage === | ||
+ | Utilisation d'une //fonction de hachage// : | ||
+ | * qui " | ||
+ | * La fonction de hachage doit être telle que la probabilité de choisir le même identifiant pour deux données différentes soit extrêmement faible. | ||
+ | |||
+ | Attribution d'un identifiant arbitraire entre 0 et n-1 | ||
+ | * Etape 1 : **transcodage** binaire des données | ||
+ | * '' | ||
+ | * avantage : les données différentes ont un code entier différent | ||
+ | * mais : |i| = |d| | ||
+ | <code python> | ||
+ | s = ' | ||
+ | d = bytes(s, ' | ||
+ | i = int.from_bytes(d, | ||
+ | print(" | ||
+ | </ | ||
+ | donne : | ||
+ | < | ||
+ | i = 852806586114976881510056778471769180697471859150728801241505293627173168229624211058 | ||
+ | </ | ||
+ | * Etape 2 : **réduction** du code | ||
+ | * __Méthode 1__ : le modulo n (reste de la division entière par n) | ||
+ | * '' | ||
+ | * Avantage : | ||
+ | * |k|<<|d| | ||
+ | * Inconvénient: | ||
+ | * deux données différentes peuvent avoir le même code | ||
+ | * ce codage revient à sélectionner les bits de poids faible | ||
+ | * deux données proches ou très similaires auront un index proche ou similaire : si '' | ||
+ | * ---> il faut prendre n //premier// | ||
+ | |||
+ | * | ||
+ | * | ||
+ | * n=232=4294967296 : | ||
+ | * H_code('' | ||
+ | * H_code('' | ||
+ | * n=67280421310721 (premier): | ||
+ | * H_code('' | ||
+ | * H_code('' | ||
+ | |||
+ | * | ||
+ | * __Méthode 2__ : combiner produit et modulo -- soient m et n deux nombres premiers entre eux | ||
+ | * '' | ||
+ | * Avantage : | ||
+ | * |k|<<|d| | ||
+ | * deux entiers proches donneront auront des codes très différents : si '' | ||
+ | * Inconvénient : | ||
+ | * deux données différentes peuvent avoir le même code | ||
+ | * le produit '' | ||
+ | |||
+ | * __Méthode 3__ : Hachage cryptographique : | ||
+ | * Le hachage cryptographique est construit de telle sorte qu'il soit très difficile de trouver un entier '' | ||
+ | * Un tel code est appelé une " | ||
+ | * Exemples : | ||
+ | * {{https:// | ||
+ | * {{https:// | ||
+ | |||
+ | === Exemple === | ||
+ | |||
+ | Le gestionnaire de bases de données {{https:// | ||
+ | |||
+ | ==== 4.4 Généralisation : multi-indexation ==== | ||
+ | |||
+ | <note tip> | ||
+ | TODO | ||
+ | </ | ||
+ | |||
+ | ==== 4.5 Structures de données pour l' | ||
+ | |||
+ | === 4.5.1 Liste triée == | ||
+ | <note tip> | ||
+ | TODO | ||
+ | </ | ||
+ | |||
+ | === 4.5.2 Index bitmap === | ||
+ | <note tip> | ||
+ | TODO | ||
+ | </ | ||
+ | |||
+ | === 4.5.3 Les B-arbres === | ||
+ | Que faire lorsque l' | ||
+ | * L' | ||
+ | * Les blocs sont organisés sous la forme d'un arbre (B-arbre = "// | ||
+ | |||
+ | Considérons un index composé de couples (clé, numero de page). On suppose que l’index est également découpé en pages, chaque page d' | ||
+ | | ||
+ | {{ restricted: | ||
+ | |||
+ | * chaque noeud de l’arbre contient une liste croissante de couples (clé, numéro d’une sous-page) | ||
+ | * chaque clé est dupliquée dans sa sous-page : | ||
+ | * les clés contenues dans la sous-page sont inférieures ou égales à elle, | ||
+ | * les clés contenues dans la sous-page sont strictement supérieures à celles de la sous-page précédente. | ||
+ | * les feuilles contiennent des couples (clé, numéro de la page du tableau de données) | ||
+ | |||
+ | < | ||
+ | * paramètre d’entrée : k | ||
+ | |||
+ | I ← charger la racine de l’arbre | ||
+ | tant que I n’est pas une feuille : | ||
+ | k’ ← première clé de I | ||
+ | tant que k > k’ | ||
+ | k’ ← clé suivante | ||
+ | I ← charger sous-page de k’ | ||
+ | </ | ||
+ | |||
+ | Remarque : Pour que l’accès aux données soit efficace, | ||
+ | * il faut que l’arbre soit le moins profond possible : arbre “équilibré”. | ||
+ | * Dans ce cas, | ||
+ | * chaque noeud a '' | ||
+ | * et la profondeur de l’arbre est de l’ordre de logb(N). | ||
+ | * Pour charger la page contenant le tuple cherché, | ||
+ | * il faut donc logb(N) + 1 lectures sur disque. | ||
+ | * | ||
+ | En pratique, il existe des algos permettant d’assurer que chaque noeud contient entre b/2 et b clés (sauf la racine). | ||
+ | <note tip> | ||
+ | Voir : | ||
+ | * http:// | ||
+ | * http:// | ||
+ | </ | ||
+ | |||
+ | ===== 5. TODO ===== | ||
+ | |||
+ | ===== 6. Bases de données relationnelles ===== | ||
+ | |||
+ | On introduit dans ce chapitre le **modèle relationnel** qui sert de fondation à la conception de bases de données. | ||
+ | |||
+ | Les différents modèles utiles en représentation des connaissances reposent sur des notions de base de la théorie des ensembles : | ||
+ | * Ensemble finis | ||
+ | * Éléments partiellement (ou totalement) discernables | ||
+ | |||
+ | ==== 6.1 Structures de données ==== | ||
+ | |||
+ | === 6.1.1 Production des données === | ||
+ | |||
+ | Tout commence par une fiche à remplir… | ||
+ | |||
+ | {{https:// | ||
+ | |||
+ | * Un formulaire se présentant sous la forme d’un ensemble de rubriques à remplir. | ||
+ | * Le **modèle de fiche** définit le format des données à enregistrer: | ||
+ | * liste des rubriques du formulaire, | ||
+ | * domaine de valeurs attendues dans chaque rubrique. | ||
+ | * A toute fiche remplie correspond un **jeu de valeurs** (ou mesure) : | ||
+ | * liste de valeurs correspondant au contenu d’une fiche particulière. | ||
+ | |||
+ | <note tip> | ||
+ | Un jeu de valeurs sert à décrire : | ||
+ | * une personne réelle : assuré, client, étudiant, auteur, plaignant, contribuable, | ||
+ | * une personne morale : fournisseur, | ||
+ | * un objet physique : article, véhicule, composant, ingrédient, | ||
+ | * un objet contractuel ou administratif : fiche de paye, contrat, procès verbal, billet, dossier... | ||
+ | * un lieu : salle, local, manufacture, | ||
+ | * un événement : transaction, | ||
+ | * etc... | ||
+ | </ | ||
+ | |||
+ | === 6.1.2 Stockage des données === | ||
+ | |||
+ | * D’un point de vue informatique, | ||
+ | * correspondant à l’encodage des données recueillies sur un support numérique | ||
+ | * Une **structure de données** définit les données de manière logique, | ||
+ | * c’est à dire l’ordre dans lequel elles doivent être lues | ||
+ | * et la manière dont elles doivent être interprétées par les programmes qui les utilisent. | ||
+ | |||
+ | <note tip> | ||
+ | Exemples de structures de données (cours d' | ||
+ | * listes, | ||
+ | * listes de listes, | ||
+ | * dictionnaires, | ||
+ | * arbres,... | ||
+ | </ | ||
+ | |||
+ | * Les types des valeurs étant déterminés (selon les cas de taille fixe ou variable), | ||
+ | * la **structure de données** correspond au “véhicule” qui servira à transporter et échanger les données (entre programmes, entre ordinateurs). | ||
+ | * Différentes structures de données sont possibles pour l’encodage et le stockage d’un jeu de valeurs, voir : | ||
+ | * Données non structurées | ||
+ | * Données vectorielles | ||
+ | * Tuples | ||
+ | * Données structurées | ||
+ | * Données Hiérarchisées | ||
+ | |||
+ | === Tuples=== | ||
+ | |||
+ | |||
+ | Le **Tuple** est la structure de données de base servant pour le recueil, le transport et le stockage des données. | ||
+ | |||
+ | <note important> | ||
+ | * Un **Tuple** est une liste, **finie**, **ordonnée** et **de taille fixe** contenant une suite de valeurs. | ||
+ | * Chaque valeur peut obéir à un format différent | ||
+ | * On note //m// la taille du tuple (nombre de valeurs) | ||
+ | t=(a1,...,am) | ||
+ | **Exemple :** | ||
+ | (" | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | === Données brutes === | ||
+ | *Textes, | ||
+ | *comptes rendus, | ||
+ | *série de notes, de valeurs sans format précis : | ||
+ | -> format texte en général. | ||
+ | |||
+ | < | ||
+ | Le format '' | ||
+ | * ASCII (caractères sans accent), | ||
+ | * utf8 (caractères accentués et spéciaux), | ||
+ | * ... | ||
+ | </ | ||
+ | |||
+ | === Données vectorielles=== | ||
+ | * Chaque jeu de valeurs est codé sous la forme d’un **vecteur** | ||
+ | * constitué de grandeurs entières ou réelles : | ||
+ | * toutes les valeurs sont quantitatives (numériques). | ||
+ | * C’est un encodage adapté aux grandeurs physiques : | ||
+ | * chaque champ du formulaire est codé dans un format numérique | ||
+ | * il est possible de représenter les données dans un espace vectoriel | ||
+ | |||
+ | <note important> | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Exemple** : | ||
+ | Considérons une station météorologique enregistrant à intervalle réguliers les données de ses capteurs : | ||
+ | * thermomètre, | ||
+ | * baromètre, | ||
+ | * hygromètre | ||
+ | * et anémomètre. | ||
+ | Un jeu de valeurs sera constitué de //5 réels double précision// | ||
+ | * la température, | ||
+ | * la pression, | ||
+ | * l’humidité, | ||
+ | * la vitesse | ||
+ | * et la direction du vent. | ||
+ | </ | ||
+ | |||
+ | |||
+ | === Tuples=== | ||
+ | |||
+ | **NB**: | ||
+ | * Les données sont organisées sous la forme d’une liste de valeurs qualitatives ou quantitatives. | ||
+ | * Le tuple est la structure de base servant pour la transmission des données (simple, facile à coder et à échanger). | ||
+ | --></ | ||
+ | |||
+ | **NB**: un **tuple** est une séquence (ordonnée et finie) de valeurs, chaque valeur pouvant être de type qualitatif ou quantitatif, | ||
+ | |||
+ | |||
+ | <note tip> | ||
+ | **Exemple** : considérons une fiche servant à décrire un étudiant. L’étudiant doit remplir les rubriques nom, prénom et âge, numero de voie, nom de la voie, code postal, ville. Chaque rubrique correspond à un composant d’un 7-tuplet tel que: | ||
+ | * les composants 1, 2, 5 et 7 sont des chaînes de caractères | ||
+ | * les composants 3, 4 et 6 sont des entiers | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | **Le format csv - “Comma Separated Values” ** | ||
+ | |||
+ | Chaque enregistrement est codé sur une ligne, chaque valeur étant séparé par un caractère séparateur (virgule, point-virgule, | ||
+ | |||
+ | Exemple : | ||
+ | Dubois, | ||
+ | |||
+ | Remarques : | ||
+ | * les données sont des chaînes de caractères | ||
+ | * les guillemets sont nécessaires lorsque la valeur contient le caractère séparateur (ici la virgule) | ||
+ | * les noms des attributs sont éventuellement indiqué sur une ligne séparée | ||
+ | </ | ||
+ | |||
+ | |||
+ | === Données indexées === | ||
+ | * Données organisées sous la forme d’une liste d’attributs. | ||
+ | * Chaque attribut est défini par un nom et un format (**type**). | ||
+ | * Chaque valeur est stockée sous la forme d’un couple (attribut : **valeur**). | ||
+ | |||
+ | <note tip> | ||
+ | **Exemple** : | ||
+ | |||
+ | Considérons une fiche servant à décrire un étudiant. L’étudiant doit remplir les rubriques nom, prénom et âge, numero de voie, nom de la voie, code postal, ville. | ||
+ | |||
+ | Chaque rubrique correspond à un attribut, où: | ||
+ | * nom, prenom, voie, et ville sont des attributs de type chaîne de caractères | ||
+ | * age et numero et code_postal sont des attributs de type entier | ||
+ | |||
+ | La structure de données sous-jacente est le **dictionnaire**, | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | Un **dictionnaire** est une liste non ordonnée de valeurs, chaque valeur étant associée à une clé unique (ici la clé est le nom de l’attribut). | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | **Le format json - JavaScript Object Notation** | ||
+ | |||
+ | Exemple : | ||
+ | {" | ||
+ | |||
+ | Remarques : | ||
+ | * reprend la syntaxe vue en Python | ||
+ | * données numériques ou chaînes de caractères | ||
+ | </ | ||
+ | |||
+ | |||
+ | === Données Hiérarchisées=== | ||
+ | |||
+ | * Organisation des données correspondant à une structure d’**arbre**. | ||
+ | * Dans le cas d’un recueil de données, correspond à la définition de rubriques et sous-rubriques. | ||
+ | |||
+ | <note tip> | ||
+ | **Exemples** : | ||
+ | * La rubrique **adresse** peut contenir les sous-rubriques **numero**, **voie**, **code_postal** et **ville**. | ||
+ | * Un document contient des **chapitres**, | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | |||
+ | Pour les données organisées de manière hiérarchique. Des balises servent à séparer les différents attributs. | ||
+ | |||
+ | Ex : | ||
+ | |||
+ | <nom> Dubois </ | ||
+ | < | ||
+ | < | ||
+ | <num> 28 </ | ||
+ | < | ||
+ | <code postal> 45000 </code postal> | ||
+ | < | ||
+ | </ | ||
+ | < | ||
+ | |||
+ | remarque : le format '' | ||
+ | { | ||
+ | " | ||
+ | " | ||
+ | " | ||
+ | { | ||
+ | " | ||
+ | " | ||
+ | " | ||
+ | " | ||
+ | }, | ||
+ | " | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | |||
+ | === Tableaux de données === | ||
+ | |||
+ | Un tableau de données est une liste (finie et ordonnée) de tuples, chaque tuple obéissant à un même schéma R. | ||
+ | |||
+ | {{https:// | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ==== 6.2 Schéma et relation ==== | ||
+ | |||
+ | 2 approches en modélisation : | ||
+ | * approche ensembliste (plus général) | ||
+ | * modèle relationnel (plus pratique) | ||
+ | |||
+ | <note important> | ||
+ | Le **Modèle relationnel** sert à représenter logiquement les **tableaux de données**. | ||
+ | </ | ||
+ | < | ||
+ | **Tableau de données** | ||
+ | |||
+ | Un tableau de données est une liste (finie et ordonnée) de tuples, chaque tuple obéissant à un même schéma R. | ||
+ | |||
+ | {{https:// | ||
+ | </ | ||
+ | |||
+ | Rappel: | ||
+ | * Un enregistrement est un jeu de valeurs organisé sous forme de **tuple** | ||
+ | * A un tuple on associe | ||
+ | {{public: | ||
+ | |||
+ | * Définir un **schéma** consiste à définir : | ||
+ | * une liste d' | ||
+ | * A chaque **attribut** correspond : | ||
+ | * un // | ||
+ | * un //domaine// de valeurs (type/ | ||
+ | |||
+ | * Soit R(A1,...,Am) un schéma. | ||
+ | * On note dom(Ai) le domaine associé à l' | ||
+ | * On dit d'un tuple t qu'il //obéit au schéma R// si les valeurs qu'il contient correspondent aux domaines des attributs du schéma. | ||
+ | |||
+ | |||
+ | |||
+ | <note important> | ||
+ | **Définition** | ||
+ | |||
+ | Soit R=(A1,...,Am) un schéma de données | ||
+ | |||
+ | Une **relation** r obéissant au schéma R est un // | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Corollaire** : une relation est un **ensemble** de tuples : | ||
+ | r={t1,...,tn}={(a11,...,a1m),...,(an1,...,anm)} | ||
+ | |||
+ | * avec : | ||
+ | * ∀(i,j),aij∈dom(Aj), | ||
+ | * ∀i,ti∈dom(A1)×...×dom(Am) | ||
+ | * n : nombre de tuples | ||
+ | * m : nombre d' | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Remarque :** | ||
+ | * Le **schéma** R représente le niveau abstrait (modélisation) | ||
+ | * La **relation** r représente un cas concret de réalisaton (à un schéma R peuvent correspondre une infinité de réalisations possibles : r, r′, r″, | ||
+ | </ | ||
+ | |||
+ | |||
+ | < | ||
+ | |||
+ | __[[public: | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | __[[public: | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | __[[public: | ||
+ | |||
+ | **Client**(nom, | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | < | ||
+ | ** __Exemples de schémas relationnels__ :** | ||
+ | |||
+ | **Étudiant**(nom, | ||
+ | |||
+ | **Ouvrage**(titre, | ||
+ | |||
+ | **Véhicule**(immatriculation, | ||
+ | </ | ||
+ | |||
+ | ==== 6.3 Dépendances fonctionnelles ==== | ||
+ | |||
+ | * Au sein d'un schéma R, | ||
+ | * Il peut exister un ensemble de contraintes, | ||
+ | * portant sur les attributs (plus précisément sur les valeurs prises par les attributs). | ||
+ | * L' | ||
+ | * On parle de **contraintes d’intégrité**. | ||
+ | * Ces contraintes s’expriment sous la forme de **dépendances fonctionnelles**. | ||
+ | |||
+ | < | ||
+ | **Rappels d’algèbre de base:** | ||
+ | |||
+ | * **Relation binaire** : une relation binaire r portant sur deux domaines dom(A) et dom(B): | ||
+ | * est un sous-ensemble du produit cartésien dom(A)×dom(B). | ||
+ | * si (a,b)∈r, on note parfois arb ce qui signifie “a est en relation avec b”. | ||
+ | * **Fonction** : une fonction f:dom(A)→dom(B) est une relation binaire sur dom(A)×dom(B) telle que | ||
+ | * pour tout a∈dom(A), | ||
+ | * il existe un unique b tel que (a,b)∈f. | ||
+ | * On note b=f(a) , | ||
+ | * ce qui signifie qu'au sein de la relation f, b est déterminé de façon unique par le choix de a (autrement dit : “b dépend de a”) | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | **Dépendance fonctionnelle** | ||
+ | |||
+ | * Soit r une relation définie selon R(A1,...,Am) | ||
+ | * Soient X et Y deux sous-ensembles de R | ||
+ | * On dit que la relation r définit une // | ||
+ | * notée Xr→Y | ||
+ | * si les valeurs de r permettent de définir une fonction de dom(X) vers dom(Y). | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **__Exemple 1__** : | ||
+ | |||
+ | Soit la relation r: | ||
+ | ^ A ^ B ^ C ^ | ||
+ | | 1 | a | e | | ||
+ | | 2 | b | f | | ||
+ | | 2 | c | f | | ||
+ | | 3 | d | k | | ||
+ | | 4 | d | k | | ||
+ | |||
+ | * On a les dépendances suivantes : | ||
+ | * A→C | ||
+ | * B→C | ||
+ | * mais pas : A→B, B→A, ni C→A | ||
+ | * On a aussi : | ||
+ | * A,B→C | ||
+ | * mais pas : B,C→A, ni A,C→B, etc. | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **__Exemple 2__** : | ||
+ | |||
+ | * Soit le schéma : | ||
+ | * **Commande** (num_client, | ||
+ | * et l’ensemble de contraintes | ||
+ | $$ \begin{array}{rl}F &= \{\\ | ||
+ | & \text{num_client, | ||
+ | & \text{num_article, | ||
+ | &\} | ||
+ | \end{array} | ||
+ | $$ | ||
+ | * La première contrainte indique qu'il ne peut y avoir deux factures émises pour un même client à une date donnée. | ||
+ | * La seconde contrainte indique que le prix payé dépend de l’article et de la quantité commandée. | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **__Exemple 3__** : | ||
+ | * Soit le schéma : | ||
+ | * **Ouvrage** (titre, auteur, éditeur, prix, date_edition) | ||
+ | * et la contrainte : | ||
+ | * {titre, auteur, éditeur → prix, date_édition} | ||
+ | La contrainte signifie : | ||
+ | * “//pour une oeuvre chez un certain éditeur, une seule édition est possible (pas de réédition à une date ultérieure)// | ||
+ | * “// | ||
+ | |||
+ | </ | ||
+ | |||
+ | < | ||
+ | **Exercice :** | ||
+ | Soit le schéma : | ||
+ | |||
+ | * **Réservation**(code_appareil, | ||
+ | |||
+ | Exprimer la dépendance fonctionnelle : | ||
+ | * « //Un appareil ne peut pas être utilisé dans deux locaux différents au même moment //» | ||
+ | </ | ||
+ | |||
+ | * Il importe donc de bien réfléchir, | ||
+ | * du réalisme et du caractère limitant de certaines dépendances fonctionnelles, | ||
+ | * et du caractère éventuellement limitant du choix des attributs. | ||
+ | * Ainsi, le schéma décrivant les commandes (exemple 2) | ||
+ | * ne permet pas de commander des articles de nature différente au sein d'une même commande | ||
+ | * (un client, pour commander deux râteaux et une truelle, doit donc effectuer deux commandes, qui plus est à des dates différentes!). | ||
+ | |||
+ | < | ||
+ | |||
+ | Soit le schéma relationnel suivant : | ||
+ | |||
+ | **Billet**(num_train, | ||
+ | |||
+ | Définir des dépendances fonctionnelles sur cet ensemble d' | ||
+ | </ | ||
+ | |||
+ | ====6.4 Clé d'une relation==== | ||
+ | |||
+ | === 6.4.1 Définitions === | ||
+ | * Soit un schéma R(A1,...,Am). | ||
+ | <note important> | ||
+ | **Clé** | ||
+ | |||
+ | * Une **clé** K : | ||
+ | * est un ensemble **minimal** d' | ||
+ | * tel que toute relation r de schéma R définit une dépendance fonctionnelle de dom(K) dans dom(R), | ||
+ | * cette dépendance est notée K→R. | ||
+ | </ | ||
+ | < | ||
+ | * **Remarques** : | ||
+ | * Si un schéma R possède une clé K, alors tous les éléments d’une relation r de schéma R sont discernables : la valeur de la clé permet d’identifier de façon unique chaque élément de l’ensemble. | ||
+ | * Au sein d'un schéma, il est souvent possible de définir plusieurs clés à partir des attributs. Le concepteur du modèle choisit une clé parmi les clés possibles. Cette clé est appelée **clé primaire**. | ||
+ | * Graphiquement, | ||
+ | {{public: | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | **__Exemple 1__** : | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | </ | ||
+ | |||
+ | < | ||
+ | **__Exemple 2__** : | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | *Pour certains schémas, | ||
+ | * il est courant de définir comme clé un entier **identifiant de façon unique** chaque élément de l' | ||
+ | * La clé est alors constituée de cet attribut unique. | ||
+ | {{public: | ||
+ | |||
+ | **Représentation [[public: | ||
+ | {{public: | ||
+ | |||
+ | </ | ||
+ | |||
+ | === 6.4.2 Axiomes d' | ||
+ | |||
+ | Soit K une clé candidate. On démontre que K→R à l'aide des //axiomes d' | ||
+ | |||
+ | <note tip> **Axiomes d' | ||
+ | |||
+ | - **Réflexivité** : Y⊆X⇒X→Y | ||
+ | - **Augmentation** : X→Y⇒X,Z→Y,Z | ||
+ | - **Transitivité** : X→Y et Y→Z⇒X→Z | ||
+ | - **Pseudo-transitivité** : X→Y et Y,W→Z⇒X,W→Z | ||
+ | - **Union** : X→Y et X→Z⇒X→Y,Z | ||
+ | - **Décomposition** : X→Y,Z⇒X→Y et X−>Z | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | |||
+ | Soit le schéma relationnel suivant : | ||
+ | |||
+ | **Billet**(num_train, | ||
+ | |||
+ | Montrer que l' | ||
+ | </ | ||
+ | ====6.4 Normalisation d'un schéma==== | ||
+ | __**Tables mal construites**__ | ||
+ | < | ||
+ | ** Exemple : fournisseurs de composants électroniques: | ||
+ | |||
+ | Fournisseur(nom_f, composant_,adresse_f, prix) | ||
+ | |||
+ | * **Problèmes :** | ||
+ | * **Redondance** : l’adresse des fournisseurs est répétée plusieurs fois | ||
+ | * **Inconsistance** : mauvaise mise à jour => adresses différentes pour un même fournisseur. | ||
+ | * **Problème Insertion** : on ne peut pas insérer dans la table un fournisseur qui ne fournit rien | ||
+ | * **Problème suppression** : si un fournisseur ne fournit plus rien, on perd son adresse | ||
+ | * Solution? | ||
+ | |||
+ | * Couper la table en 2? | ||
+ | <note warning> | ||
+ | Fournisseurs(nom_f, adresse_f) | ||
+ | Catalogue(composant, prix) | ||
+ | </ | ||
+ | --> Impossible de retrouver les prix pratiqués par les différents fournisseurs. | ||
+ | |||
+ | |||
+ | * Nouveau Schéma : | ||
+ | <note tip> | ||
+ | Fournisseurs(nom_f, adresse_f) | ||
+ | Catalogue(nom_f, composant, prix) | ||
+ | </ | ||
+ | --> Il est possible de reconstruire la table initiale en effectuant une jointure entre ces 2 tables sur l’attribut '' | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | < | ||
+ | **Exercice** : Les tables suivantes sont-elles bien ou mal construites? | ||
+ | |||
+ | * **Enseignement** (__id_enseignant__, | ||
+ | |||
+ | * **Arrêt** (__num_train__, | ||
+ | |||
+ | * **Facture** (__id_client, | ||
+ | </ | ||
+ | |||
+ | ==== 6.5 Formes Normales ===== | ||
+ | **__Les Formes normales__** | ||
+ | * Restreignent les dépendances admises dans un schéma relationnel | ||
+ | * Permettent d’éviter la duplication de l’information au sein des relations | ||
+ | * Définissent une méthode | ||
+ | * de **décomposition** d’un schéma relationnel redondant | ||
+ | * en plusieurs schémas //liés entre eux//: | ||
+ | |||
+ | === 6.5.1 2ème forme normale (2FN) === | ||
+ | <note important> | ||
+ | **Dépendance fonctionnelle élémentaire (DFE) ** | ||
+ | * Soit R un schéma relationnel | ||
+ | * Soit X un ensemble d’attributs ⊆ R | ||
+ | * Soit A un attribut de R | ||
+ | * Il existe une DFE entre X et A ssi : | ||
+ | * X→A | ||
+ | * Il n’existe aucun sous-ensemble Y ⊆ X tel que Y→A | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | **2ème forme normale (2FN) ** | ||
+ | |||
+ | * Un schéma R est en 2FN : | ||
+ | * ssi la clé primaire de R est en DFE avec tous les autres attributs. | ||
+ | * Donc : il n’y a pas d’attributs qui ne dépendent que d’une partie de la clé. | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Exemple :** | ||
+ | Fournisseur(nom_f,composant_,adresse_f,prix) | ||
+ | nom_f→adresse_f | ||
+ | nom_f,composant→prix | ||
+ | ⇒ Pas 2FN!! | ||
+ | </ | ||
+ | |||
+ | === 6.5.2 Normalisation 2FN === | ||
+ | * Lorsqu’un schéma relationnel n’est pas en deuxième forme normale, __il doit être **normalisé**__: | ||
+ | |||
+ | < | ||
+ | **Normalisation 2FN** : | ||
+ | * Pour obtenir un schéma 2FN: | ||
+ | * on “// | ||
+ | * La normalisation consiste: | ||
+ | * à créer une nouvelle table pour chaque DFE ainsi trouvée. | ||
+ | |||
+ | * Soit : | ||
+ | R(A1,...,Ai,...,An_,B1,...,Bj,...,Bm) | ||
+ | * avec : | ||
+ | AiDFE→Bj | ||
+ | A1,...,Ai,...,AnDFE→B1,...,Bj−1,Bj+1...,Bm | ||
+ | * Alors le schéma de table doit être modifié comme suit : | ||
+ | R1(A1,...,Ai,...,An_,B1,...,Bj−1,Bj+1...,Bm) | ||
+ | R2(Ai_,Bj) | ||
+ | |||
+ | <note important> | ||
+ | |||
+ | Même si aucun attribut ne dépend plus de la clé primaire initiale, il est important de la conserver dans une table spécifique (elle sert à “lier” les valeurs dispersées dans les différentes tables). | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **__Exemple__** | ||
+ | * __Avant__: | ||
+ | Fournisseur(nom_f,composant_,adresse_f, prix) | ||
+ | nom_f→adresse_f | ||
+ | nom_f, composant→prix | ||
+ | * __Après__: | ||
+ | Catalogue(nom_f,composant_,prix) | ||
+ | Fournisseur(nom_f_,adresse_f) | ||
+ | |||
+ | < | ||
+ | **Remarque :** le schéma est maintenant constitué de deux tables. | ||
+ | * Les tables ont un attribut commun : //nom_f// (clé primaire de la table Fournisseur). | ||
+ | * La clé primaire de la table des Fournisseurs est dupliquée dans la table des prix (appelée ici **Catalogue**). | ||
+ | * On dit que //nom_f// est une **clé étrangère** de la table des prix (l’attribut fait référence à la clé primaire d’une autre table, en l’occurrence la table des fournisseurs - voir [[public: | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | === 6.5.3 3ème forme normale (3FN) === | ||
+ | |||
+ | <note important> | ||
+ | **Dépendance Fonctionnelle Directe (DFD) :** | ||
+ | |||
+ | La dépendance fonctionnelle entre 2 attributs Ai et Aj est //directe// s’il n’existe pas de Ak tel que : | ||
+ | Ai→Ak→Aj | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | **3ème Forme Normale (3FN)** | ||
+ | |||
+ | Un schéma est 3FN : | ||
+ | * S’il est 2FN | ||
+ | * Si tous les attributs sont en DFD avec la clé. | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | **Exemple :** | ||
+ | |||
+ | Commande(num_commande_,nom_f, adresse_f, composant, quantité) | ||
+ | num_commande→nom_f, composant, quantité | ||
+ | nom_f→adresse_f | ||
+ | |||
+ | Le schéma n’est pas 3FN!! (dépendance transitive entre num_commande et adresse) | ||
+ | </ | ||
+ | |||
+ | |||
+ | === 6.5.4 Normalisation 3FN === | ||
+ | * Lorsqu’un schéma relationnel n’est pas en troisième forme normale, __il doit être **normalisé**__: | ||
+ | |||
+ | < | ||
+ | **Normalisation 3FN** | ||
+ | * On crée une table pour chaque DFD trouvée au sein des attributs n' | ||
+ | |||
+ | |||
+ | Soit : | ||
+ | R(A1,...,Am_,B1,...,Bi,...,Bj,...,Bn) | ||
+ | avec : | ||
+ | A1,...,AmDFD→B1,...,Bi,...,Bj−1,Bj+1,...,Bn | ||
+ | BiDFD→Bj | ||
+ | Alors : | ||
+ | R1(A1,...,Am_,B1,...,Bi,...,Bj−1,Bj+1,...,Bn) | ||
+ | R2(Bi_,Bj) | ||
+ | |||
+ | <note important> | ||
+ | ** Attention ** | ||
+ | |||
+ | Comme précédemment, | ||
+ | </ | ||
+ | |||
+ | </ | ||
+ | |||
+ | < | ||
+ | |||
+ | __Avant__ : | ||
+ | * **Commande** (__num_commande__, | ||
+ | * avec : | ||
+ | * num_commande → nom_f, composant, quantité | ||
+ | * nom_f → adresse_f | ||
+ | |||
+ | __Après__ : | ||
+ | * **Commande** (__num_commande__, | ||
+ | * **Client** (__nom_f__, adresse_f) | ||
+ | |||
+ | L’attribut nom_f est maintenant clé primaire de la table Client et clé étrangère de la table Commande. | ||
+ | </ | ||
+ | |||
+ | ==== 6.6 Modèle ensembliste ==== | ||
+ | |||
+ | |||
+ | <note tip> | ||
+ | Pour leur conception, les bases de données sont ici vues comme des ensembles constitués de plusieurs populations d' | ||
+ | </ | ||
+ | |||
+ | Une base de donnée est constituée de plusieurs ensembles d' | ||
+ | |||
+ | __Exemple 1 :__ | ||
+ | * Ensembles d' | ||
+ | * Ensembles de commandes | ||
+ | * Ensembles d' | ||
+ | * Ensembles de clients | ||
+ | |||
+ | __Exemple 2 :__ | ||
+ | * Ensembles d' | ||
+ | * Ensembles de séances | ||
+ | * Ensembles de cours | ||
+ | * Ensembles de copies | ||
+ | |||
+ | On parle plus généralement d' | ||
+ | |||
+ | |||
+ | |||
+ | <note tip> | ||
+ | ** Le modèle entité/ | ||
+ | |||
+ | Le modèle entité/ | ||
+ | |||
+ | Le modèle entités/ | ||
+ | |||
+ | </ | ||
+ | |||
+ | === Généralités === | ||
+ | |||
+ | Une **entité** x | ||
+ | * est une représentation d'un objet du monde réel, | ||
+ | * appartenant au système/à l' | ||
+ | * Une entité est décrite par une ou plusieurs valeurs caractéristiques, | ||
+ | |||
+ | Les informations conservées au sujet des entités d'un ensemble sont les **attributs**. | ||
+ | * Chaque **attribut** : | ||
+ | * a un **nom** unique dans le contexte de cet ensemble d' | ||
+ | * Exemples de noms concrets : // | ||
+ | * prend ses valeurs dans un domaine bien spécifié, | ||
+ | * également appelé le **type** de l' | ||
+ | * Le domaine d'un attribut est noté dom(Aj)=Dj. | ||
+ | * Exemples : | ||
+ | * dom(couleur)=rouge,vert,bleu,jaune, | ||
+ | * dom(nom)=ensemble des chaînes de caractères, | ||
+ | * dom(salaire)= entiers naturels | ||
+ | * etc... | ||
+ | <note important> | ||
+ | * Un attribut Aj est une fonction à valeur sur Dj : | ||
+ | Aj:E→Dj | ||
+ | x↦Aj(x) | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | * Un attribut peut être : | ||
+ | * simple ou composé. | ||
+ | * Exemple : une //adresse// peut être décrite par une simple chaîne de caractères, | ||
+ | * obligatoire ou facultatif (Dj peut ou non contenir la valeur ø ). | ||
+ | * atomique ou non (Un attribut peut posséder 0, 1 voire plusieurs valeurs...) | ||
+ | </ | ||
+ | |||
+ | |||
+ | Un **ensemble d' | ||
+ | E={x1,…,xn} | ||
+ | Il regroupe (ou associe) plusieurs entités ayant des caractéristiques communes (descriptibles à l'aide du même ensemble d' | ||
+ | |||
+ | <note tip> | ||
+ | **Exemples** : | ||
+ | * les employés d'une firme, | ||
+ | * les cours de Centrale Méditerranée, | ||
+ | * une collection de disques, | ||
+ | * etc… | ||
+ | </ | ||
+ | |||
+ | * Les éléments d’un ensemble d’entités sont // | ||
+ | * les attributs (A1,...,Am) servent à décrire les éléments de l’ensemble. | ||
+ | * Le schéma R de l’ensemble E est une // | ||
+ | * Soit : | ||
+ | R:X→D1×...×Dm | ||
+ | xi↦(A1(xi),…,Am(xi)) | ||
+ | |||
+ | <note tip> | ||
+ | ** représentation graphique ** : | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | </ | ||
+ | |||
+ | < | ||
+ | ** Exemples **: | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | | ||
+ | |||
+ | === Définitions === | ||
+ | |||
+ | Modéliser une base de données, c'est : | ||
+ | * Identifier les différents ensembles en interaction | ||
+ | * Identifier les liens de dépendance entre les différents ensembles | ||
+ | |||
+ | < | ||
+ | {{public: | ||
+ | </ | ||
+ | < | ||
+ | {{public: | ||
+ | </ | ||
+ | < | ||
+ | {{public: | ||
+ | </ | ||
+ | <note tip> | ||
+ | Les liens entre les différents ensembles sont appelés des **associations** | ||
+ | </ | ||
+ | |||
+ | === Association === | ||
+ | |||
+ | <note important> | ||
+ | Une association exprime des relations de dépendance entre deux ou plusieurs ensembles d’entités. | ||
+ | |||
+ | **Définition** : Une **association** entre les ensembles E1, ..., Ek est un sous-ensemble du produit E1×...×Ek. | ||
+ | |||
+ | Il s'agit donc d'un ensemble de k-uplets {...,(x1,…,xk),…} | ||
+ | |||
+ | où k est le degré de l' | ||
+ | * k=2 : association binaire | ||
+ | * k=3 : association ternaire | ||
+ | * etc… | ||
+ | |||
+ | </ | ||
+ | |||
+ | === Rôles des associations === | ||
+ | * // | ||
+ | * // | ||
+ | * // | ||
+ | * // | ||
+ | * ... | ||
+ | |||
+ | |||
+ | === Contraintes de cardinalité === | ||
+ | |||
+ | <note tip> | ||
+ | Pour chaque ensemble participant à une association, | ||
+ | |||
+ | On donne en général un intervalle [binf,bsup] qui définit le nombre d' | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | === Représentation graphique === | ||
+ | |||
+ | **Associations binaires** | ||
+ | |||
+ | |{{public: | ||
+ | |{{public: | ||
+ | |{{public: | ||
+ | |||
+ | **Associations ternaires** | ||
+ | |||
+ | | {{public: | ||
+ | |||
+ | |||
+ | === Types d' | ||
+ | |||
+ | **Associations de 1 à plusieurs (fonctionnelle)** | ||
+ | |||
+ | Relation non symétrique entre les deux ensembles : […,1] d'un côté, […,N] de l' | ||
+ | Relation de type contenant/ | ||
+ | Il s'agit du type d' | ||
+ | |||
+ | <note tip> | ||
+ | On dit parfois que l’ensemble dont la participation est unique est dit “à gauche” de l’association fonctionnelle, | ||
+ | |||
+ | “à gauche” → “à droite” | ||
+ | </ | ||
+ | |||
+ | |{{public: | ||
+ | |{{public: | ||
+ | |||
+ | **Associations de plusieurs à plusieurs (croisée)** | ||
+ | |||
+ | Dans une association “croisée”, | ||
+ | |||
+ | |{{public: | ||
+ | |{{public: | ||
+ | |||
+ | === Modèles Entité Associations valués === | ||
+ | |||
+ | <note important> | ||
+ | Dans le cadre du modèle entité/ | ||
+ | * les attributs des ensembles d' | ||
+ | * Soit A un attribut de l' | ||
+ | A:E→dom(A) | ||
+ | * les attributs des associations sont des // | ||
+ | * Soit B un attribut de l' | ||
+ | B:E×F→dom(B) | ||
+ | </ | ||
+ | |||
+ | ** Mesures ** | ||
+ | * Les mesures sont les données saisies sur les éléments d'un ensemble. Chaque mesure est associée à un attribut. | ||
+ | * Le schéma de l' | ||
+ | * Les éléments de l' | ||
+ | * Une //clé// est un ensemble d' | ||
+ | |||
+ | <note tip> **TODO** | ||
+ | |||
+ | Ensembles discernables / non discernables | ||
+ | </ | ||
+ | ** Opérateurs ** | ||
+ | * On s’intéresse ici aux associations qui représentent une “opération” (inscription, | ||
+ | * Lors d’une mise à jour de la base, certains événements tels que l’emprunt ou le retour d’un ouvrage, l’affectation d’un employé à un poste, | ||
+ | * Il est possible de garder une trace des événements passés en mettant un (ou plusieurs) attributs sur une association. | ||
+ | * Ainsi, certaines associations peuvent être " | ||
+ | * avoir lieu à une date | ||
+ | * ou prendre place sur une durée précise (prêt, | ||
+ | * On peut ainsi mémoriser : | ||
+ | * " | ||
+ | * " | ||
+ | |||
+ | |||
+ | |||
+ | <note tip> | ||
+ | **Exemple** | ||
+ | " | ||
+ | |{{public: | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Exemple** | ||
+ | * Chaque coureur est décrit par ses nom, prénom, nationalité et numéro de maillot. | ||
+ | * Chaque coureur appartient à une équipe qui possède un numéro, un sponsor associé. | ||
+ | * Chaque coureur participe à une ou plusieurs étapes. Une étape se caractérise par son numéro, son type (contre la montre/ | ||
+ | * A chaque étape est associée un classement d' | ||
+ | |||
+ | |{{public: | ||
+ | |||
+ | </ | ||
+ | |||
+ | === 6.6.2 Traduction vers le modèle relationnel === | ||
+ | |||
+ | Il est possible de traduire un modèle entité/ | ||
+ | |||
+ | <note tip> | ||
+ | Lors de la réalisation d'une base de données, on passe en général par les étapes suivantes: | ||
+ | - Conception de la base sous forme d'un modèle entité/ | ||
+ | - Traduction sous la forme d'un modèle relationnel. | ||
+ | - Normalisation (voir [[https:// | ||
+ | - Mise en œuvre informatique. | ||
+ | </ | ||
+ | |||
+ | Un petit nombre de règles permettent de traduire un modèle entité/ | ||
+ | * Selon ces règles, à la fois les ensembles d' | ||
+ | * Les liaisons et dépendances entre schémas de relation sont assurés par la définition des **clés étrangères** (attributs communs à plusieurs tables). | ||
+ | |||
+ | === Schéma de base et clé étrangère === | ||
+ | |||
+ | <note important> | ||
+ | * Un schéma (ou modèle) de bases de données est un ensemble fini de schémas de relation. | ||
+ | * Une base de données est un ensemble fini de relations. | ||
+ | * Les liens et associations entre relations entre s’expriment sous la forme de **clés étrangères** | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Définition** | ||
+ | |||
+ | * Au sein d'un schéma relationnel R, Une clé étrangère est un attribut (ou un groupe d' | ||
+ | * La présence d'une clé étrangère au sein d'une relation r de schéma R introduit une contrainte d' | ||
+ | * la valeur des attributs de la clé étrangère d'un tuple de r doit être trouvée dans la table s correspondante. | ||
+ | * On indique la présence d'une clé étrangère à l'aide de pointillés : {…, __C__l__é__ __é__t__r__a__n__g__è__r__e__, | ||
+ | </ | ||
+ | |||
+ | |||
+ | **Exemple ** | ||
+ | < | ||
+ | **Schéma de base relationnelle** : | ||
+ | |||
+ | * **Clients** ( __nom_client__, | ||
+ | * **Commandes** ( __num_Commande__, | ||
+ | * **Fournisseurs** ( __nom_fournisseur__, | ||
+ | * **Catalogue** ( __nom_fournisseur, | ||
+ | </ | ||
+ | |||
+ | === Traduction des associations de plusieurs à plusieurs === | ||
+ | |||
+ | Une association croisée ne contient que des contraintes de cardinalité de type [..,N]. Soit R une telle association et E1, ..., Ek les ensembles participant à l' | ||
+ | |||
+ | <note important> | ||
+ | **Règle de traduction :** | ||
+ | * Chaque ensemble Ei est traduit par un schéma relationnel (contenant les mêmes attributs) | ||
+ | * L' | ||
+ | * les clés primaires des ensembles participant à l’association | ||
+ | * (éventuellement) les attributs propres à l' | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | {{public: | ||
+ | |||
+ | ** Traduction :** | ||
+ | * **Pays** (__nom_pays__, | ||
+ | * **Matière_première** ( __nom_matière__, | ||
+ | * **Exportation** (__n__o__m__ __p__a__y__s, | ||
+ | |||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | {{public: | ||
+ | **Traduction** : | ||
+ | * **Appareil** (__code_appareil__, | ||
+ | * **Séance** (__date, heure, local__) | ||
+ | * **Réservation** (__c__o__d__e __a__p__p__a__r__e__i__l, | ||
+ | |||
+ | </ | ||
+ | |||
+ | === Traduction des associations de un à plusieurs === | ||
+ | |||
+ | Soit une association fonctionnelle R. On suppose qu'il existe au moins un ensemble A de cardinalité unique [1,1] participant l’association. | ||
+ | |||
+ | <note important> | ||
+ | **Règle de traduction** | ||
+ | * Chaque ensemble participant est traduit sous forme de schéma relationnel | ||
+ | * L' | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Exemple** : | ||
+ | {{public: | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Remarque** : lorsque l’association est valuée, les attributs de l’association sont également injectés dans la table représentant l’ensemble de gauche. | ||
+ | {{public: | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Exemple** | ||
+ | {{public: | ||
+ | **Traduction** : | ||
+ | * **Groupe_TD**( __num_groupe__, | ||
+ | * **Entreprise** ( __nom_entreprise__, | ||
+ | * **Etudiant** ( __num_etudiant__, | ||
+ | </ | ||
+ | |||
+ | === Exemple complet === | ||
+ | |||
+ | < | ||
+ | **Schéma de base relationnelle** : | ||
+ | |||
+ | * **Clients** ( __nom_client__, | ||
+ | * **Commandes** ( __num_Commande__, | ||
+ | * **Fournisseurs** ( __nom_fournisseur__, | ||
+ | * **Catalogue** ( __nom_fournisseur, | ||
+ | </ | ||
+ | < | ||
+ | ** Réalisation ** : | ||
+ | |||
+ | **Clients** : | ||
+ | ^__nom_client__^adresse_client^solde^ | ||
+ | |Durand|7, rue des Lilas|335, | ||
+ | |Dubois|44, av. du Maréchal Louis|744, | ||
+ | |Duval|5, place du marché|33, | ||
+ | |||
+ | **Commandes** : | ||
+ | ^__num_Commande__^ __n__o__m__ __c__l__i__e__n__t^ composant^ quantité^ | ||
+ | |6674|Dubois|micro controller|55| | ||
+ | |6637|Dubois|radio tuner|2| | ||
+ | |6524|Durand|transistor|4| | ||
+ | |6443|Duval|micro controller|7| | ||
+ | |||
+ | **Fournisseurs** : | ||
+ | ^__nom_fournisseur__^ adresse_fournisseur^ | ||
+ | |Sage|33, College street, London| | ||
+ | |MoxCom|77 Ashley square, | ||
+ | |||
+ | **Catalogue** : | ||
+ | ^__nom_fournisseur__^ __composant__^ prix^ | ||
+ | |Sage|transistor|4, | ||
+ | |MoxCom|micro controller|3, | ||
+ | |MoxCom|radio tuner|7,0| | ||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | === 6.6.3 Gestionnaire de Bases de données | ||
+ | |||
+ | <note tip> | ||
+ | Les données sont structurées en **tables**, contenant des **tuples** organisés comme séquence de **valeurs**, | ||
+ | * Une **base de données** est un ensemble de **tables** (parfois appelées relations). | ||
+ | * Une **table** est un ensemble de **tuples** (parfois appelés enregistrements). | ||
+ | * Un **tuple** est un ensemble de **valeurs** (parfois appelés « champs » ou attributs). | ||
+ | </ | ||
+ | |||
+ | Un SGBD (Système de Gestion de Bases de Données) est un programme qui gère une (ou des) base(s) de données. Il s’agit d’un programme optimisé afin d’accélérer l’accès et rationaliser le traitement d’un grand ensemble d’enregistrements stockés sur un support informatique. | ||
+ | |||
+ | Le fonctionnement d'un tel programme repose sur : | ||
+ | * des méthodes de conception ensemblistes fondées sur le modèle relationnel (description des ensembles d’enregistrements et des relations entre ces ensembles) | ||
+ | * un langage de requête permettant de consulter et mettre à jour les données stockées dans la base | ||
+ | * des algorithmes de stockage et de classement efficace (afin d’accélérer les temps de recherche) | ||
+ | |||
+ | |||
+ | |||
+ | Il existe enfin un administrateur de bases de données. Celui-ci doit : | ||
+ | * installer la base de données, | ||
+ | * gérer sa sauvegarde régulière, | ||
+ | * garantir sa sécurité et | ||
+ | * gérer les droits des utilisateurs de la base. | ||
+ | |||
+ | |||
+ | === SQL (Structured Query Language)=== | ||
+ | **SQL** : | ||
+ | * est un langage de création et d' | ||
+ | * supporté par la plupart des systèmes de gestion de bases de données relationnelles du marché. | ||
+ | |||
+ | < | ||
+ | **Structured query language** (SQL), ou langage structuré de requêtes, est un langage informatique standard et normalisé, destiné à interroger ou manipuler une base de données relationnelle. Les instructions SQL se répartissent en trois familles distinctes : | ||
+ | * un langage de définition de données (LDD, ou en anglais DDL, Data definition language), qui permet la description de la structure de la base (tables, vues, index, attributs, ...). | ||
+ | * un langage de manipulation de données (LMD, ou en anglais DML, Data manipulation language), c'est la partie la plus courante et la plus visible de SQL, qui permet la manipulation des tables et des vues. | ||
+ | * et un langage de contrôle de données (LCD, ou en anglais DCL, Data control language), qui contient les primitives de gestion des transactions et des privilèges d' | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | Exemple de définition de schéma de table avec clé étrangère en SQL : | ||
+ | <code sql> | ||
+ | CREATE TABLE Commande ( | ||
+ | num_commande INTEGER NOT NULL, | ||
+ | nom_client VARCHAR(30), | ||
+ | nom_fournisseur VARCHAR(30), | ||
+ | composant VARCHAR(30), | ||
+ | quantité INTEGER, | ||
+ | montant DECIMAL(12, | ||
+ | PRIMARY KEY (num_commande), | ||
+ | FOREIGN KEY (nom_client) REFERENCES Client, | ||
+ | FOREIGN KEY (nom_fournisseur, | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | <note tip> **Lecture/ | ||
+ | |||
+ | * Création : | ||
+ | <code SQL> | ||
+ | INSERT INTO Client VALUES (" | ||
+ | </ | ||
+ | * Mise à jour | ||
+ | <code SQL> | ||
+ | UPDATE Client SET adresse = "9, rue des Lilas" WHERE nom_client=" | ||
+ | </ | ||
+ | * Suppression | ||
+ | <code SQL> | ||
+ | DELETE FROM Client WHERE nom_client=" | ||
+ | </ | ||
+ | Voir : {{https:// | ||
+ | </ | ||
+ | |||
+ | ==== 6.7 - Recherche d' | ||
+ | |||
+ | |||
+ | === 6.7.1 Interrogation des Bases de Données === | ||
+ | |||
+ | Interroger une base de données , c’est sélectionner certaines données parmi l' | ||
+ | |||
+ | En informatique, | ||
+ | * Le programme **client** représente l’utilisateur, | ||
+ | * Les données sont centralisées au niveau du **serveur**, | ||
+ | |||
+ | |||
+ | {{public: | ||
+ | |||
+ | === Consultation des données === | ||
+ | |||
+ | La requête peut être une simple référence vers un fichier, ou être l’expression d’une recherche plus spécifique (consultation de certaines fiches d’un fichier, croisement d’information (entre plusieurs fichiers), etc...). Dans ce cas, il est nécessaire d’utiliser un langage de requête (le plus souvent [[public: | ||
+ | |||
+ | On distingue quatre grands types de requêtes (approche “CRUD”): | ||
+ | * **Création** (// | ||
+ | * **Lecture/ | ||
+ | * **Mise à jour** (// | ||
+ | * **Suppression** (// | ||
+ | |||
+ | Lors d’une consultation de type lecture/ | ||
+ | |||
+ | <note tip> | ||
+ | __Exemples :__ | ||
+ | * requêtes http : demande de consultation d’une page web ( = référence vers un fichier) | ||
+ | * moteur de recherche : recherche de pages contenant les mots-clés spécifiés | ||
+ | * bases de données : utilisation d’un langage de requête : | ||
+ | <code sql> | ||
+ | SELECT * | ||
+ | FROM Eleves | ||
+ | WHERE NOM = ' | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | Exemples : | ||
+ | |||
+ | * **croisement de facteurs de recherche :** | ||
+ | * Donner la liste des pays exportateurs de pétrole | ||
+ | * Liste des musiciens jouant à la fois du piano et du violon | ||
+ | * Liste des artistes français disque d'or en 1977 | ||
+ | * Liste des suspects châtain taille moyenne présents à Poitiers la nuit du 12 au 13 février | ||
+ | * ** Analyse des données ** | ||
+ | * faire ressortir des corrélations (exemple : type d' | ||
+ | * pour des enquêtes de consommation, | ||
+ | * **Information personnalisée :** | ||
+ | * ne retenir que les informations utiles à un instant et pour une personne donnée. | ||
+ | * Emploi du temps de l' | ||
+ | * Factures impayées du client Z | ||
+ | |||
+ | <note tip> | ||
+ | Lors d’une consultation de type lecture/ | ||
+ | * il y a souvent plusieurs réponses qui correspondent à la demande. | ||
+ | * Le résultat d’une requête prend donc la forme d’un ensemble de réponses. | ||
+ | * Ces réponses sont éventuellement classées, | ||
+ | * selon la valeur d’un certain identifiant, | ||
+ | * ou selon le degré de pertinence. | ||
+ | </ | ||
+ | |||
+ | |||
+ | <note important> | ||
+ | L’**algèbre relationnelle** | ||
+ | * propose un certain nombre d’opérations ensemblistes : | ||
+ | * Intersection, | ||
+ | * Union, | ||
+ | * Projection, | ||
+ | * Différence, | ||
+ | * … | ||
+ | * qui, à partir d'un ensemble de relations, permettent de construire de nouvelles relations. | ||
+ | * La relation nouvellement construite contient le résultat de la **requête** | ||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | === 6.7.2 Opérateurs mono-table=== | ||
+ | |||
+ | Extraction d' | ||
+ | * projection π = extraction de colonnes | ||
+ | * sélection σ = extraction de lignes | ||
+ | |||
+ | === Projection : π === | ||
+ | < | ||
+ | * Soit r une relation de schéma R. | ||
+ | * Soit S un ensemble d' | ||
+ | La **projection** | ||
+ | πS(r)={t(S)|t∈r} | ||
+ | |||
+ | (avec t(S) la restriction de t au schéma S) | ||
+ | </ | ||
+ | |||
+ | <note tip> **Exemple** | ||
+ | **Catalogue** : | ||
+ | ^nom_fournisseur^adresse_fournisseur^composant^ prix^ | ||
+ | |Sage|33, College street, London|transistor|4, | ||
+ | |MoxCom|77 Ashley square, | ||
+ | |MoxCom|77 Ashley square, | ||
+ | |||
+ | Requete : //Donner la liste des fournisseurs (avec leur adresse)//: | ||
+ | u=πnom_fournisseur, adresse_fournisseur(Catalogue) | ||
+ | |||
+ | → **u** : | ||
+ | ^nom_fournisseur^adresse_fournisseur^ | ||
+ | |Sage|33, College street, London| | ||
+ | |MoxCom|77 Ashley square, | ||
+ | |||
+ | </ | ||
+ | |||
+ | === Sélection : σ === | ||
+ | |||
+ | <note important> | ||
+ | **Condition sur R** | ||
+ | * On considère le schéma R(A1,…,An) | ||
+ | * Une condition F sur R : | ||
+ | * est un ensemble de contraintes sur les valeurs des attributs A1, …, An | ||
+ | * construites à l'aide d' | ||
+ | * ∧(et), | ||
+ | * ∨(ou), | ||
+ | * ¬(non), | ||
+ | * =, ≠, >,<, ≥ ,≤, ... | ||
+ | * et de valeurs numériques ou de texte. | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Exemples** : | ||
+ | F=(A1=3)∧(A1>A2)∧(A3≠4) | ||
+ | F = (A_1 = 2) ∨ (A_2 = "Dupont") | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | **Sélection** | ||
+ | * Soit r une relation de schéma R | ||
+ | * Soit F une condition sur R | ||
+ | |||
+ | La **sélection** σ_F(r) est une nouvelle relation de schéma R , constituée de l' | ||
+ | |||
+ | σ_F(r) = \{ t ∈ r | F( t ) \text{est vrai} \} | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Exemple** : | ||
+ | |||
+ | Requête : //Donner la liste des fournisseurs qui vendent des micro-controleurs// | ||
+ | |||
+ | u = Π_\text{nom_fournisseur}( σ_\text{Composant = micro controller} ( \text{Fournisseur} )) | ||
+ | **u** : | ||
+ | ^nom_f^ | ||
+ | |Moxcom| | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Exemple** | ||
+ | |||
+ | **Pays** : | ||
+ | ^nom_pays^superficie^population ^PIB/hab^ | ||
+ | |Algérie|2.300.000|31.300.000|1630$| | ||
+ | |Niger|1.200.000|11.400.000|890$| | ||
+ | |Arabie Saoudite|2.150.000|24.300.000|8110$| | ||
+ | |||
+ | Requête : //Donner la liste des pays dont le PIB/hab est > 1000$// | ||
+ | u = Π_\text{nom_pays}( σ_\text{PIB/hab > 1000 } ( \text{Pays} )) | ||
+ | |||
+ | **u** : | ||
+ | ^nom_pays^ | ||
+ | |Algérie| | ||
+ | |Arabie Saoudite| | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | === Structure d'une requête SQL=== | ||
+ | |||
+ | <code sql> | ||
+ | SELECT | ||
+ | FROM R // nom de la table | ||
+ | WHERE | ||
+ | </ | ||
+ | |||
+ | cette requête est semblable à : | ||
+ | * une sélection algébrique σ_F | ||
+ | * suivie par une projection algébrique Π_{A1, …, An} | ||
+ | soit : | ||
+ | Π_{A1, …, An}( σ_F ( R )) | ||
+ | |||
+ | **Exemples :** | ||
+ | * //Qui fournit des transistors ?// | ||
+ | <code sql> | ||
+ | SELECT nom_fournisseur | ||
+ | FROM Fournisseur | ||
+ | WHERE composant = ’transistor’; | ||
+ | </ | ||
+ | * //Liste de toutes les commandes de transistors :// | ||
+ | <code sql> | ||
+ | SELECT * | ||
+ | FROM Commandes | ||
+ | WHERE composant = ’transistor’ | ||
+ | </ | ||
+ | * //Qui fournit des micro-controleurs à moins de 5$?// | ||
+ | <code sql> | ||
+ | SELECT nom_fournisseur | ||
+ | FROM Catalogue | ||
+ | WHERE composant = ’micro controller’ AND prix < 5 | ||
+ | </ | ||
+ | |||
+ | === Aspects algorithmiques === | ||
+ | |||
+ | **Algo de sélection :** | ||
+ | pour tout tuple e de r: | ||
+ | si e obéit à la condition | ||
+ | ajouter e à la réponse | ||
+ | |||
+ | complexité : O(n) | ||
+ | |||
+ | <note tip> | ||
+ | * On parle de recherche ciblée lorsque le nombre d’éléments obéissant à la condition F est a priori très faible : | ||
+ | * exemple : on cherche le salaire de Mr “Dupont”. | ||
+ | * On parle de recherche extensive lorsque l’ensemble de valeurs obéissant à la condition F est a priori élevé. | ||
+ | * exemple : les employés dont le salaire est < 2000 euros | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | **Rappel** : | ||
+ | |||
+ | Organisation des données sous forme de tableaux bidimensionnels : | ||
+ | |||
+ | ** Schémas de données ** | ||
+ | |||
+ | * Les données sont organisées sous forme de **tuple** | ||
+ | * A un tuple correspond en général | ||
+ | {{public: | ||
+ | |||
+ | ** Relation ** | ||
+ | |||
+ | Une // | ||
+ | |||
+ | {{https:// | ||
+ | </ | ||
+ | |||
+ | |||
+ | Remarque : dans le cas d'une recherche ciblée, la présence d'un index sur le critère de recherche permet d' | ||
+ | pour toute a ∈ F: | ||
+ | i ← Index(a) | ||
+ | ajouter r[i] à la réponse | ||
+ | |||
+ | === 6.7.3 Opérateurs multi-tables === | ||
+ | |||
+ | Principe : recoupement d' | ||
+ | * Croisement des critères de sélection : **Jointure** | ||
+ | * Recherche ciblée : **Division** | ||
+ | |||
+ | === La jointure : ⋈ === | ||
+ | |||
+ | <note important> | ||
+ | **Union de deux éléments :** | ||
+ | * Soient les relations r et s de schémas R et S. | ||
+ | * On note R ⋂ S la liste des attributs communs aux deux schémas et R ⋃ S la liste des attributs appartenant à R ou à S. | ||
+ | * soit t ∈ r et q ∈ s tels que t(R ⋂ S) = q(R ⋂ S) | ||
+ | On note t ⋃ q le tuple formé des valeurs de t et de q étendues au schéma R ⋃ S | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | **Produit cartésien ** | ||
+ | * Soient r et s (de schémas R et S), avec R ⋂ S = Ø | ||
+ | Le produit cartésien r × s est une nouvelle table de schéma R ⋃ S combinant les tuples de r et de s de toutes les façons possibles : | ||
+ | r × s = \{t \cup q : t \in r, q \in s\} | ||
+ | </ | ||
+ | |||
+ | * La **jointure** est une opération qui consiste à effectuer un produit cartésien des tuples de deux relations pour lesquelles certaines valeurs correspondent. | ||
+ | * Le résultat de l' | ||
+ | |||
+ | <note important> | ||
+ | **Jointure** | ||
+ | * Soient r et s (de schémas R et S), avec R ⋂ S ≠ Ø | ||
+ | * La **jointure** | ||
+ | r ⋈ s = \{t \cup q : t∈ r, q∈ s, t(R \cap S) = q(R \cap S)\} | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | **Exemple** | ||
+ | |||
+ | |||
+ | **Matière_première :** | ||
+ | ^nom_matière^unité^prix^ | ||
+ | |pétrole|baril|45$| | ||
+ | |gaz|GJ|3$| | ||
+ | |uranium|lb|12$| | ||
+ | |||
+ | |||
+ | **Exportations :** | ||
+ | ^nom_pays^nom_matière^quantité^ | ||
+ | |Algérie|pétrole|180.000| | ||
+ | |Algérie|gaz|20.000| | ||
+ | |Niger|uranium|30.000| | ||
+ | |Arabie Saoudite|pétrole|2.000.000| | ||
+ | |Arabie Saoudite|gaz|750.000| | ||
+ | |||
+ | **Matière_première ⋈ Exportations **: | ||
+ | ^nom_pays^nom_matière^quantité^unité^prix^ | ||
+ | |Algérie|pétrole|180.000|baril|45$| | ||
+ | |Algérie|gaz|20.000|GJ|3$| | ||
+ | |Niger|uranium|30.000|lb|12$| | ||
+ | |Arabie Saoudite|pétrole|2.000.000|baril|45$| | ||
+ | |Arabie Saoudite|gaz|750.000|GJ|3$| | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | **Exemples de requêtes ** | ||
+ | |||
+ | |||
+ | |||
+ | * “//Donner la liste des PIB/hab des pays exportateurs de pétrole// | ||
+ | Π_\text{PIB/hab}( σ_\text{nom_matière = pétrole} ( \text{Pays} ⋈ \text{Exportations} )) | ||
+ | |||
+ | < | ||
+ | **Schéma de base relationnelle** : | ||
+ | |||
+ | * **Clients** ( __nom_client__, | ||
+ | * **Commandes** ( __num_Commande__, | ||
+ | * **Fournisseurs** ( __nom_fournisseur__, | ||
+ | * **Catalogue** ( __nom_fournisseur, | ||
+ | </ | ||
+ | |||
+ | * “//Donner le nom et l' | ||
+ | Π_\text{nom_client,adresse_client}( σ_\text{composant = 'micro-controller'} ( \text{Client} ⋈ \text{Commandes} )) | ||
+ | |||
+ | |||
+ | === Requêtes multi-tables en SQL === | ||
+ | |||
+ | <code sql> | ||
+ | SELECT | ||
+ | FROM R1, …, Rm // liste de tables | ||
+ | WHERE F1 AND … AND Fl // liste de conditions sur les attributs | ||
+ | // (en particulier conditions sur les attributs | ||
+ | // sur lesquel | ||
+ | </ | ||
+ | |||
+ | Pour exprimer la jointure sur l’attribut ' | ||
+ | |||
+ | **Exemples :** | ||
+ | |||
+ | * **Approche prédicative : ** | ||
+ | <code sql> | ||
+ | SELECT PIB_par_hab | ||
+ | FROM Pays NATURAL JOIN Exportations | ||
+ | WHERE nom_matiere = ' | ||
+ | </ | ||
+ | |||
+ | <code sql> | ||
+ | SELECT PIB_par_hab | ||
+ | FROM Pays, Exportations | ||
+ | WHERE nom_matiere = ' | ||
+ | AND Pays.nom_pays = Exportations.nom_pays | ||
+ | </ | ||
+ | |||
+ | * **Approche ensembliste : ** | ||
+ | <code sql> | ||
+ | SELECT PIB_par_hab | ||
+ | FROM Pays | ||
+ | WHERE nom_pays IN ( | ||
+ | select | ||
+ | FROM Exportations | ||
+ | WHERE nom_matiere = ' | ||
+ | ) | ||
+ | </ | ||
+ | |||
+ | === Aspects algorithmiques et optimisation === | ||
+ | |||
+ | Lors d’une opération de jointure, on distingue en général la “table de gauche” de la “table de droite”. | ||
+ | <note tip> | ||
+ | Dans le modèle Entité/ | ||
+ | * La table de gauche est celle qui est de cardinalité unique, | ||
+ | * et la table de droite est celle qui est de cardinalité multiple (définissant une relation fonctionnelle gauche → droite) | ||
+ | * L’attribut servant pour la jointure est donc clé étrangère de la table de gauche et clé primaire de la table de droite. | ||
+ | </ | ||
+ | |||
+ | Il y a deux stratégies possibles pour faire une jointure : | ||
+ | * **double boucle** : c'est l' | ||
+ | * **tri-fusion** : chaque table est triée sur les attributs de jointure avant que la jointure soit effectuée. Une fois le tri fait, les tables peuvent être fusionnée : chaque table n'est examinée qu'une seule fois (ici, la jointure n'est pas coûteuse, c'est bien sûr sur l' | ||
+ | |||
+ | ** Exemple :** | ||
+ | |||
+ | On considère les schémas R(a1,a2,a3) et S(a3,a4,a5) ayant l’attribut a3 en commun : | ||
+ | * L’attribut a3 est une clé étrangère du schéma R. | ||
+ | * R est “à gauche” (contient la clé étrangère), | ||
+ | |||
+ | Soient r et s deux tables obéissant aux schémas R et S, et de taille |r| et |s|. | ||
+ | |||
+ | //Algo naif :// | ||
+ | Pour chaque tuple e de r: | ||
+ | Pour chaque tuple f de s: | ||
+ | Si e(a3)=f(a3): | ||
+ | ajouter e U f à la réponse | ||
+ | |||
+ | Complexité : O (|r| ×|s|) | ||
+ | |||
+ | Si la table de droite est indexée sur l' | ||
+ | |||
+ | Pour chaque tuple e de r: # table de gauche | ||
+ | x ← e(a3) | ||
+ | i ← Index(x) # index sur la table de droite | ||
+ | f ← s[i] | ||
+ | ajouter e U f à la réponse | ||
+ | |||
+ | * si la recherche dans l' | ||
+ | * Complexité : O (|r| × log |s|) | ||
+ | |||
+ | === La division === | ||
+ | |||
+ | <note important> | ||
+ | * Soient r (de schémas R) et s (de schémas S), avec S ⊆ R : | ||
+ | La division r ÷ s est la relation (table) u de schéma R-S maximale contenant des tuples tels que u × s ⊆ r (avec × représentant le produit cartésien) | ||
+ | |||
+ | r ÷ s = \{ t | ∀ q ∈ s, t \cup q ∈ r\} | ||
+ | |||
+ | → on cherche les éléments de t qui “correspondent” à s | ||
+ | </ | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | Exemples : | ||
+ | * Liste des pays qui exportent //tous// les types de matières premières | ||
+ | * Liste des pays qui exportent les //mêmes// matières premières que l' | ||
+ | * Liste des élèves présents à tous les cours magistraux d' | ||
+ | |||
+ | === 6.7.4 Recherches composées === | ||
+ | |||
+ | * Certaines requêtes, peuvent être le résultat de la combinaison de plusieurs critères de recherche | ||
+ | * La combinaison de résultats est généralement réalisée à l'aide des opérations ensemblistes classiques (intersection, | ||
+ | * Pour alléger les formules, il est possible | ||
+ | |||
+ | <note important> | ||
+ | **Union** | ||
+ | * Soient r1 et r2 deux tables de schéma R. | ||
+ | L' | ||
+ | r1 \cup r2 = { t ∈ r1} \cup { t ∈ r2} | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | * Soient r1 et r2 deux tables de schéma R. | ||
+ | L' | ||
+ | r1 \cap r2 = \{ t ∈ r1\} \cap \{ t ∈ r2\} | ||
+ | </ | ||
+ | |||
+ | <note important> | ||
+ | * Soient r1 et r2 deux tables de schéma R. | ||
+ | La **différence** r1 - r2 est une nouvelle table de schéma R constituée de l' | ||
+ | r1 - r2 = \{ t ∈ r1\} - \{ t ∈ r2\} | ||
+ | </ | ||
+ | |||
+ | **Exemples :** | ||
+ | * Donner la liste des pays qui exportent à la fois du gaz et du pétrole : | ||
+ | \pi _{Pays} σ_\text{matière = gaz} (\text{Exportations}) \cap \pi _{Pays} σ_\text{matière = pétrole} (\text{Exportations}) | ||
+ | en SQL : | ||
+ | <code sql> | ||
+ | SELECT pays FROM Exportations | ||
+ | WHERE matière = ' | ||
+ | INTERSECT ( | ||
+ | WHERE matière = ' | ||
+ | </ | ||
+ | * Donner la liste des pays qui exportent du gaz mais pas du pétrole : | ||
+ | \pi _{Pays} σ_\text{matière = gaz} (\text{Exportations}) - \pi _{Pays} σ_\text{matière = pétrole} (\text{Exportations}) | ||
+ | en SQL : | ||
+ | <code sql> | ||
+ | SELECT pays FROM Exportations | ||
+ | WHERE matière = ' | ||
+ | EXCEPT ( | ||
+ | WHERE matière = ' | ||
+ | </ | ||
+ | |||
+ | * Donner la liste des clients qui commandent uniquement des produits ' | ||
+ | \pi_{nom\_client}Client - \pi_{nom\_client} \sigma_{fournisseur \neq 'Moxcom'} Client ⋈ Commande | ||
+ | en SQL : | ||
+ | <code sql> | ||
+ | SELECT nom_client FROM Client | ||
+ | EXCEPT ( SELECT client FROM Client NATURAL JOIN Commande | ||
+ | WHERE fournisseur <> ' | ||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | ===== 7. Analyse des données===== | ||
+ | |||
+ | L’analyse des données a pour but de recomposer l’information contenue dans les données recueillies afin d’en fournir une vue plus synthétique, | ||
+ | |||
+ | Exemples de grandes masses de données : | ||
+ | * Masses de données (pullulantes) : tickets de caisse, clics web, appels tel, operations bancaires, remboursements no URSSAF, trajets SNCF… | ||
+ | * Données importantes : fichiers de clients, données biométriques, | ||
+ | * Données géographiquement localisées (gestion d’un “territoire”) : appels tel, centres de production, consommation eau-électricité-gaz, | ||
+ | |||
+ | |||
+ | |||
+ | Le but est de dégager | ||
+ | * des **tendances** (covariables) | ||
+ | * des **modes** de la distribution (présence de plusieurs maxima) | ||
+ | à partir d’un **grand** ensemble de données (chiffre d’affaires, | ||
+ | * définir des **indicateurs** pertinents | ||
+ | * faciliter la prise de décision. | ||
+ | |||
+ | ==== 7.1 L' | ||
+ | |||
+ | == Agrégation == | ||
+ | |||
+ | L' | ||
+ | * à organiser les données en classes selon la valeur d'un attribut. | ||
+ | * à utiliser des **opérateur d’aggrégation** : | ||
+ | * comptage, somme, moyenne, ecart-type, max, min, ... | ||
+ | * ('' | ||
+ | * afin de dégager : | ||
+ | * des tendances (selon une dimension) | ||
+ | * des modes (analyse par histogramme) | ||
+ | |||
+ | **cas d’utilisation** : | ||
+ | * Quels sont les catégories de films/ | ||
+ | * A quelles heures de la journée la messagerie est-elle la plus sollicitée? | ||
+ | * Comment se répartissent géographiquement les utilisateurs de la messagerie? | ||
+ | |||
+ | === SQL === | ||
+ | En SQL, l' | ||
+ | * définit des regroupements de données à partir des valeurs de l' | ||
+ | * il est possible de faire des regroupements selon les valeurs de plusieurs attributs | ||
+ | |||
+ | Exemples de requêtes faisant appel aux fonctions d’agrégation : | ||
+ | |||
+ | //Nombre d’élèves par groupe de TD / par prépa d’origine etc..:// | ||
+ | <code sql> | ||
+ | SELECT groupe_TD , count(num_eleve) | ||
+ | FROM Eleve | ||
+ | GROUP BY groupe_TD | ||
+ | </ | ||
+ | |||
+ | //Donner les chiffres des ventes du magasin pour chaque mois de l’année// | ||
+ | <code sql> | ||
+ | SELECT mois, sum(montant) | ||
+ | FROM Vente | ||
+ | GROUP BY mois | ||
+ | </ | ||
+ | |||
+ | //Donner le nombre de ventes d’un montant > à 1000 euros pour les mois dont le chiffre d' | ||
+ | <code sql> | ||
+ | SELECT mois, count(num_vente) | ||
+ | FROM Vente | ||
+ | GROUP BY mois | ||
+ | HAVING sum(montant) >= 10000 | ||
+ | </ | ||
+ | |||
+ | //Tester les disparités salariales entre hommes et femmes// | ||
+ | <code sql> | ||
+ | SELECT sexe, avg( salaire ) | ||
+ | FROM Employé | ||
+ | GROUP BY sexe | ||
+ | </ | ||
+ | |||
+ | //Tester les disparités salariales selon le niveau d’éducation// | ||
+ | <code sql> | ||
+ | SELECT niveau_educatif, | ||
+ | FROM Employé | ||
+ | GROUP BY niveau_éducatif | ||
+ | </ | ||
+ | |||
+ | ==== 7.2 Découverte d' | ||
+ | |||
+ | La découverte d' | ||
+ | facilitant leur analyse. Elle repose sur deux aspects : | ||
+ | * projection de données qualitatives sur des espaces vectoriels (" | ||
+ | * production d' | ||
+ | |||
+ | Le but est ici de dégager : | ||
+ | * des corrélations (analyse croisée) | ||
+ | |||
+ | ** Exemples de corrélations :** | ||
+ | * Réussite / taux d’embauche / salaire en fonction de la prépa d’origine / sexe / profession des parents | ||
+ | * Tester les disparités salariales hommes/ | ||
+ | * Donner le taux de réussite aux examens par groupe de matière en fonction de la filière d’origine (MP, PSI, PC, PT, ...) | ||
+ | * Y a-t-il une corrélation entre le lancement d’une campagne publicitaire et les chiffres de vente? quels sont les supports les plus efficaces? | ||
+ | |||
+ | Sites de données : | ||
+ | * {{https:// | ||
+ | * {{https:// | ||
+ | * {{https:// | ||
+ | * {{https:// | ||
+ | * {{https:// | ||
+ | |||
+ | === 7.2.1 Tables pivot === | ||
+ | |||
+ | * Notion de fait élémentaire (//fact//): transaction ou opération localisée dans le temps et dans l’espace | ||
+ | * | ||
+ | Remarque : Les transactions marchandes sont un cas classique (acte d’achat bien répertorié et enregistrés, | ||
+ | |||
+ | Exemples de “fait”: | ||
+ | * Achat/Vente | ||
+ | * Opération bancaire (débit/ | ||
+ | * Consultation (site web) | ||
+ | * Souscription à un contrat d’assurance | ||
+ | * Appel téléphonique | ||
+ | * Inscription | ||
+ | |||
+ | Tous ces faits peuvent être localisés. Des mesures peuvent être effectuées sur ces faits (montant d’une vente, durée d’un appel, montant d’une opération bancaire, …) | ||
+ | |||
+ | **Points clés** : | ||
+ | * distinction entre **Dimension** et **Mesure**. | ||
+ | * Notion de dimension : qui? quoi? où? quand? Comment? : associe des **coordonnées** à l’événement (géographiques, | ||
+ | * Notion de **mesure(s)** associées à l’événement (exemple : montant de la vente) | ||
+ | * distributions, | ||
+ | * les événements sont associés par paquets sur des intervalles réguliers ou selon des catégories discretes. | ||
+ | * Fonctions d’aggrégation : réalise la mesure sur les groupe : somme, comptage, moyenne, min, max, etc... | ||
+ | * histogramme : nb d’événements observés par secteur sur un maillage régulier de l’espace des coordonnées. Par extension mesure sur ce maillage par une fonction d’aggrégation. | ||
+ | |||
+ | <note tip> **principe :** | ||
+ | * les mesures portent sur des données de type // | ||
+ | * les classes reposent sur des données de //type qualitatif// | ||
+ | </ | ||
+ | |||
+ | Les tables pivot permettent d' | ||
+ | |||
+ | L' | ||
+ | <code python> | ||
+ | import numpy as np | ||
+ | import matplotlib.pyplot as plt | ||
+ | import pandas | ||
+ | </ | ||
+ | |||
+ | Considérons des informations stockées dans un fichier au format ‘csv’ (comma separated values) : '' | ||
+ | |||
+ | On utilise: | ||
+ | * '' | ||
+ | |||
+ | <code python> | ||
+ | with open(' | ||
+ | data = pandas.read_csv(f) | ||
+ | print(data) | ||
+ | </ | ||
+ | avec '' | ||
+ | |||
+ | exemple : on représente les ventes selon (1) la dimension géographique et (2) la dimension temporelle | ||
+ | |||
+ | <code python> | ||
+ | T = pandas.pivot_table(data, | ||
+ | print(T) | ||
+ | </ | ||
+ | |||
+ | Evolution des ventes au cours de l' | ||
+ | <code python> | ||
+ | selection = data[data.PAYS == " | ||
+ | T2 = pandas.pivot_table(selection, | ||
+ | print(T2) | ||
+ | |||
+ | T2.plot(kind=' | ||
+ | plt.show() | ||
+ | </ | ||
+ | |||
+ | === 7.2.2 Modèle en étoile === | ||
+ | |||
+ | Ici les données sont organisées autour de plusieurs dimensions. L' | ||
+ | * à positionner les données sur des axes (temporels, géographiques, | ||
+ | * ou à les organiser de manière hiérarchique en classes (et sous-classes) selon la valeur d'un ou plusieurs attributs. | ||
+ | |||
+ | Exemple de hiérarchie: | ||
+ | * pays > région > département | ||
+ | |||
+ | == Dimensions == | ||
+ | * (qui?) Quels sont les magasins les plus rentables? doit-on ouvrir / fermer des magasins? | ||
+ | * (Où?) répartition des appels/ | ||
+ | * (qui?) Quelle est la liste des clients à contacter? | ||
+ | * (quand?) De quelle quantité doit-on approvisionner quels magasins en fonction de la période de l’année? | ||
+ | |||
+ | ** Problèmes : ** | ||
+ | * définir les bons intervalles temporels?? créneaux horaires? | ||
+ | * définir des secteurs géographiques? | ||
+ | |||
+ | |||
+ | |||
+ | == Modèle en étoile== | ||
+ | * un fait est une association située au centre du schéma. Les attributs de l’association sont les mesures effectuées | ||
+ | * une dimension est une relation participant au fait. Les dimensions sont donc décrites par des attributs (ex : attributs année, trimestre, mois, jour, heure, minute, seconde, | ||
+ | * pour chaque dimension, on décrit une hiérarchie sur les différents attributs de la dimension en définissant un ordre, du particulier au général. | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | ==Exemples :== | ||
+ | * sur la dimension temporelle : mois ⊂ trimestre ⊂ année | ||
+ | * sur la dimension promotion : nom ⊂ catégorie ⊂ média ⊂ type de média | ||
+ | etc... | ||
+ | |||
+ | |||
+ | ==Exemples== | ||
+ | * {{https:// | ||
+ | |||
+ | * {{http:// | ||
+ | |||
+ | * {{http:// | ||
+ | |||
+ | |||
+ | |||
+ | ===Cubes de données=== | ||
+ | |||
+ | Un cube de données est une structure de données organisée sur le principe des espaces vectoriels. Différents axes sont définis, chaque axe étant associé à une dimension particulière. | ||
+ | |||
+ | * Les dimensions peuvent correspondre à des valeurs discrètes (catégories : type de produit, catégorie de client,...) ou continues (valeurs temporelles ou géographiques, | ||
+ | * Chaque fait est décrit comme un point de l’espace vectoriel. Il est positionné dans une cellule du cube. A ce point sont associées une ou plusieur mesures. | ||
+ | * Le cube est un ensemble de cellules (voir figure), chaque cellule correspondant à un intervalle (sur les axes continus) ou une valeur (sur les axes discrets). | ||
+ | |||
+ | |||
+ | Un élément essentiel du modèle de données est la définition de **hiérarchies** sur les dimensions du cube. Chaque dimension se divise en intervalles et sous-intervalles (pour le continu/ quantitatif) ou en catégories et sous-catégories (pour le discret/ | ||
+ | |||
+ | Les hiérarchies sur les différentes dimensions permettent de définir le “niveau de résolution” sur les différentes dimensions. | ||
+ | * On peut ainsi s’intéresser à l’évolution d’une certaine grandeur au cours du temps année par année, trimestre par trimestre ou mois par mois selon le niveau de résolution choisi. | ||
+ | *-> Hiérarchie : description arborescente d’intervalles et de sous-intervalles sur une dimension. Implemente differentes granularités sur la dimension considérée. | ||
+ | |||
+ | {{public: | ||
+ | |||
+ | La structure de cube de données est adaptée pour la réalisation d’histogramme multidimensionnels, | ||
+ | * Histogramme et aggrégation | ||
+ | * (vue quantitative) comptage/ | ||
+ | * (vue qualitative) comptage d’événements par catégorie | ||
+ | * (vue intermediaire) comptage d’événements par catégories hiérarchisées | ||
+ | |||
+ | |||
+ | === 7.2.2 Mise en oeuvre === | ||
+ | |||
+ | |||
+ | === XMLA / MDX === | ||
+ | |||
+ | ==== 7.3 Méthodes avancées ==== | ||
+ | |||
+ | **REPRESENTATION DES DONNEES** : Représenter des jeux de valeurs de grande taille de façon plus synthétique (algorithmes de réduction de dimension) | ||
+ | |||
+ | **REGROUPEMENT (“CLUSTERING”)** : Définir des regroupements (ou des classements simples ou hiérarchiques) entre jeux de valeurs | ||
+ | |||
+ | **COMPLETION** : Méthodes de classification automatique (ou d’interpolation) visant à deviner soit la classe, soit certaines valeurs non mesurées, | ||
+ | |||
+ | **ESTIMATION ET DECISION** : Méthodes visant à estimer la “valeur” associée à un jeu de données (pour l’aide à la décision) | ||