Résumé "Bases de Données" (c) 2003-01-11 Fabian M. Suchanek http://www.mpi-inf.mpg.de/~suchanek/personal/texts/summaries/bd.txt Ceci est le résumé du cours "Bases de données" donné par M Bardou en hiver 2002 à l'Université Pierre-Mendès-France Grenoble. (Since this text is supposed to be in French, I could not avoid using non-ASCII characters, sorry for that to all foreign readers) Le lecteur, en lisant le texte ci-dessous, accepte que l'auteur décline toute responsabilité concernant des informations fausses ou incomplètes. Si quelqu'un trouve une faute, je lui serais reconnaissant de bien vouloir me le dire. C'est le seul moyen de profiter moi-même de la publication de ce résumé. Mon e-mail est f.m.suchanek@zweb.de, mais il faut effacer la lettre 'z' dans l'adresse. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Introduction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ cf aussi maths.txt (en francais) cf aussi gc.txt (en francais) cf aussi ia.txt (en francais) Ensemble: Une collection non rangée d'éléments non identiques. M = {x1, x2, ..., xn} est l'ensemble de x1 x2, ... xn M = {x | f(x) } est l'ensemble de tous les x pour lesquels f(x) est vrai Sous ensemble d'un ensemble M: Un ensemble T tel que tous les éléments appartenant à T appartiennent à M. On dit que T est inclu dans M. T < M Application, Fonction: Un classement f qui prend un élément appartenant à un ensemble A (ou à plusieurs ensembles) et qui redonne un élément appartenant à un ensemble B. On écrit: f: A -> B f(a)=b, où a appartient à A et b appartient à B Paramètre: Un élément qu'on donne à une apllication. Opération: Une fonction ayant un paramètre ou deux paramètres. Au lieu de f(a,b), on écrit aussi a f b. Opérateur de comparaison: Un des symboles suivants: < > != = =< >= Identité: La fonction f(x)=x. Union: L'application "\/" qui prend deux ensembles M1 et M2 et redonne l'ensemble qui contient les élements qui appartiennent à M1 ou à M2 ou à tous les deux. L'union est associative et commutative. Intersection: L'application "/\" qui prend deux ensembles M1 et M2 et redonne l'ensemble qui contient exactement les élements qui appartiennent à M1 et à M2. L'intersection est associative et commutative. Exclusion: L'application "-" qui prend deux ensembles M1 et M2 et redonne l'ensemble M1 sans les éléments de M2. Partition d'un ensemble X: Un ensemble d'ensembles X[i] tels que X = X[1] \/ X[2] \/ ... X[n] et X[i] /\ X[j] = {} pour tout i != j Liste, Suite, Tuple: Une collection rangée d'éléments. v = (v[1], v[2], ... v[n]) Couple: Un tuple de deux éléments. Triple: Un tuple de trois éléments. Juxtaposition des tuples (a[1],...a[n]) et (b[1],...b[m]): Le tuple (a[1],...a[n], b[1],...b[m]). Produit cartésien des ensembles A[1],...A[n]: L'ensemble de tous les tuples (a[1],...a[n]) où a[i] appartient à A[i]. On note le produit comme A[1] x A[2] x ... A[n]. Annotation: Bien entendu, A x B x C != (A x B) x C, bien que cela soit très souvent supposé Relation entre des ensembles: Un sous ensemble du produit cartésien de ces ensembles. Chaque élément de cet ensemble est noté comme R(valeur1, valeur2, ...) où "R" est le nom de la relation. Une relation peut être notée sous forme d'un tableau, dont chaque colonne correspond à un ensemble et dont chaque ligne correspond à un élément de la relation. Composante d'une relation: Un des ensembles qui fait partie de la relation. Schéma d'une relation: Une chaîne de la forme relation(composante1, composante2, ...). Occurance, Instance, Entité: Quelque chose. Attribut d'une entité: Une propriété de cette entité qui peut avoir une valeur. Exemple: La couleur des yeux d'une personne, qui peut avoir les valeurs "bleu", "noir" ou "vert" selon les individus Type d'entité, Concept, Classe: Un ensemble d'entités qui ont les mêmes attributs (mais ne pas nécessairement les mêmes valeurs). Exemple: "Université" est un concept qui regroupe toutes les universités: Des attributs communs sont p.ex. "ville", "filières", "qualité" etc. Annotation: Pour un traitement détaillé cf philo.txt (en anglais) ou funclog.htm (en francais, disponible à partir du février 2003) Attribut d'une classe A: L'ensemble des valeurs d'un attribut que les entités de A ont en commun. Exemple: Un attribut de la classe "Personne" est couleur_des_yeux = {bleu, noir, vert} Arbre: Un élément et une suite d'arbres. La suite peut être vide. Chaque arbre de cette suite est appelé un "enfant", l'élément est appelé "noeud". Exemple: N1 / | \ N2 N3 N4 | \ \ N5 N6 N7 Forêt: Un ensemble d'arbres. Chaîne: Une suite de caractères. Exemple: "Salut" est une chaîne Concaténation de deux chaînes: Leur juxtaposition. Langage: Un ensemble de chaînes. Les chaînes qui appartiennent au langage sont d'ordinaire décrites par une grammaire. Exemple: Java est un langage Algorithme: Une suite finie d'instructions. Programme: Un algorithme (codé) qui peut être effectué par un ordinateur. Fichier: Une suite d'octets stockée sur une disque. Synonyme d'un mot M: Un mot qui fait référence au même concept ou à la même entité que M. Graphe: Une structure de noeuds et flèches entre eux. Annotation: Pour une définition plus exacte, cf gc.txt ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Historique ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ SFG, Système de gestion de fichiers: Un programme ou un ensemble de programmes qui permet de créer, modifier, arranger, copier et supprimer des fichiers. Définition par intension: Une définition d'un ensemble par une condition que tous ses éléments (et seulement eux) satisfont. Définition par extension: Une définition d'un ensemble par une liste de tous ses éléments. BD, Base de données: Une collection d'informations structurées, stockée sur un support permanent (d'ordinaire sous forme de fichiers). Une BD comprend un schéma (une définition par intension) et l'ensemble de données (une définition par extension). Intégrité, Cohérence d'une BD: Sa propriété de ne pas contenir des informations contradictoires. Redondance d'une structure: Sa propriété de contenir une information qui peut être déduite des autres informations. SGBD, Système de gestion de bases de donnée: Un programme qui permet d'organiser, interroger et contrôler une BD. Objectifs premiers: * Indépendance physique des programmes par rapport aux données * Indépendance logique des programmes par rapport aux données * Manipulation des données par des langages non procéduraux * Administration facilitée des données Objectifs additionnels: * Efficacité d'accès aux données * Partage des données * Assurance de la cohérence et de l'intégrité des données * Contrôle de la redondance des données * Assurance de la sécurité des données Un SGBD peut interagir avec l'utilisateur, d'autres programmes, l'administrateur de la BD. Il interagit avec le SFG pour l'accès à la BD. Vision du SGBD centrée sur les traitements: Le schéma suivant: données --> TRAITEMENT --> résultats Les données entrent dans le traitement et les résultats en sortent. Vision du SGBD centrée sur les données: Le schéma suivant: DONNÉES <--> Traitement Les données sont stockées et le traitement interagit avec elles. LDD, Langage de définition de données: Un langage avec lequel on décrit des données pourqu'un SGBD les admette dans la BD. LMD, Langage de manipulation de données: Un langage avec lequel on instruit un SGBD à modifier ou interroger la BD. Histoire des SGBDs: * Les années 1960 * Systèmes de gestion de fichiers * Fonctions de base * création * destruction * allocation de mémoire * accès * localisation * Fonctions de contrôle * partage * résistance aux pannes * sécurité et confidentalité * Fin des années 1960 * Première génération de SGBDs * séparation de la gestion des données des programmes * mise en place des premiers langages de navigation (LDD, LMD) * Les années 1970 * Deuxième génération de SGBDs * modèle relationel * modèle entités/associations * Les années 1980-1990 * Troisième génération de SGBDS * SGBDs à objets * BDs déductives * BDs reparties/fédérées * BDs temporelles * BDs versionnées Occurrance d'association entre des entités: Un lien entre ces entités. Type d'association entre des classes: Un lien entre ces classes qui reprend les occurrances d'association qui existent pour toutes les entités des classes. Association: Un type d'association ou une occurance d'association, selon le contexte. Annotation: On distingue entre des "associations concrètes" (donc des occurrances d'association) et des "associations en général" (donc des types d'association). Les dernières réfléchissent au niveau des classes les occurrances d'association. La terminologie n'est pas toujours utilisée d'une manière cohérente. La définition de ci-dessus simplifie ce résumé tout en gardant sa cohérence. Arité, degré, dimension d'une association: Le nombre d'entités liées par l'association. Association x à y entre les classes A et B: Un type d'association qui exprime qu'un nombre de x entités de A est toujours lié à un nombre de y entités de B. On écrit "n" pour x ou y si le lien concerne un nombre inconnu d'entités. Exemple: Un triangle a trois arrêtes, donc il existe une association 1 à 3 entre le concept "triangle" et le concept "arrête". Multiciplité, cardinalité d'une classe A par rapport à une association: Un couple d'un nombre minimal et un nombre maximal d'entités auxquelles une entité de la classe A est liée. On écrit "n" pour un nombre inconnu. Exemple: Un pilot peut effectuer un nombre inconnu de vols, mais chaque vol est effectué par un seul pilote. Alors la multiplicité de "pilote" est (1,n) et celle de "vol" est (1,1). Annotation: Cette notation peut sembler intuitivement "à l'invers". En effet, c'est vice versa en UML. Modèle: Une forme d'organisation d'une BD. Modèle hierarchique: Un modèle comme un arbre. IBM, Industrial Business Machines: Une certaine entreprise américaine. // I BM, you BM, we all BM :-) Schéma d'une classe: Une suite d'attributs de cette classe. Elle est notée comme CLASSE(attribut1, attribut2, ...) Un tel schéma identifie la classe dans le monde de l'informatique. Exemple: PERSONNE(nom, age) Annotation: Cette notion n'est pas officielle Article d'une entité X: La suite des valeurs de X pour le schéma de sa classe. L'article identifie une entité dans le monde de l'informatique. Exemple: Schéma de "Personne": PERSONNE(nom, age) Article de la personne Bob: (Bob, 73) IMS, Information Management System: Un modèle hierarchique proposé par IBM. Il consiste d'articles. Les articles sont organisés dans un arbre, dont chaque niveau contient des articles d'entités d'une même classe. Un forêt de ces arbres constitut la BD. Le LMD et le LDD sont intégrés dans les langages de programmation PL1 et COBOL. Avantages: * Simple à comprendre * Simple à programmer Désavantages: * Il permet uniquement des associations 1 à n * Il peut nécessiter des duplications d'enrégistrement, impliquant * un problème de cohérence * un problème de contrôle Exemple: racine / | \ x1 x2 x3 Classe X /| / \ | \ y1 y2 y3 y4 y5 y6 Classe Y ANSI, American National Standards Institute: L'institut de norme des États Unis. Modèle réseaux: Un modèle proposé par le Data Base Task Group. Dans ce modèle, un article x d'une classe X est toujours lié à plusieurs articles y[1],...y[n] d'une classe Y. Cela est mémorisé en stockant une référence de x à y[1], une référence de chaque y[i] à son successeur y[i+1] et une référence de y[n] à x. Cette notation aboutit à une "liste circulaire" de y[i]s autour de x. Un y[i] peut de même être lié à plusieurs z[1],...z[m] d'une classe Z. Pour cela, il faut que les liens autour de x et autour de y[i] soient distinguables. Avantages: * Peut représenter des associations 1 à n * Pas de dédoublement dû à une structure hierarchique * Simple à comprendre Désavantages: * Certains dédoublements sont nécessaires * Dépendance entre la description des données et la programmation Exemple: y1 <- x1 <- y5 | ^ V | y2 -> y3 -> y4 > z1 ^ v z3 < z2 Architecture ANSI X3SPARC: Une structure autour d'une BD, qui a été normée en 1970 par l'ANSI. Elle distingue 3 niveaux de "schémas": 1. Les sous schémas (les vues externes des données, propres aux programmes d'application) 2. Le Schéma conceptuel ou schéma logique (l'abstraction du monde réel, chaque BD a un schéma conceptuel) 3. Le Schéma interne ou schéma physique (le stockage des données) Le modèle prévoit une indépendance des niveaux 1 et 2 ("Indépendance logique") et une indépendance des niveaux 2 et 3 ("indépendance physique"). Étapes de la réalisation d'une BD: 1. Analyse des besoins Une description opérationelle de la BD sous forme textuelle ou avec un formalisme 2. Établissement du modèle conceptuel Une description de la BD en termes de structures à un haut niveau d'abstraction (p.ex. par le modèle entités/associations, voir ci-dessous) 3. Établissement du modèle logique Une description des données avec un LDD ou le modèle relationnel (voir ci-dessous) 4. Optimisation Une amélioration des performances de la BD Type d'une donnée: L'ensemble des valeurs possibles de cette donnée. Exemple: Le type de "nombre_d'enfants" est l'ensemble des entiers. Domaine: Une part du monde réel. Modélisation: La description d'un domaine par un formalisme. Il s'agit donc d'une abstraction de la réalité, qui est incomplète, mais correcte. Le résultat de la modélisation est la structure d'une BD, qui précise les types des données, les relations et les contraintes entre elles. La modélisation est guidé par le modèle des données, c'est-à-dire l'ensemble de conceptions. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Modélisation entités/associations ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Identifiant d'une classe: Un ensemble d'attributs dont les valeurs identifient sans ambiguité une entité de cette classe. Exemple: Pour la classe "homme", la suite du nom, de la date de naissance et de l'adresse est d'ordinaire regardée comme identifiant: (nom, date_de_naissance, adresse) Modèle entités/associations, Modèle E/A: Un modèle des années 1980, qui base sur les traveaux de Chen. Il connait comme concepts fondamentaux la classe et le type d'association. Une classe est notée comme une boîte, qui a le nom de la classe comme titre et ses attributs comme contenu. Un type d'association est noté comme un cercle qui contient le nom de l'association -- d'ordinaire sous forme d'un verbe. On peut aussi noter des attributs de l'association dans le cercle. Les types d'association sont liés aux classes qu'ils concernent par des lignes. Auprès d'une classe concernée, on note sa multiciplité. Entre deux classes, il ne peut avoir qu'une seule association. Pour transformer une description d'un problème en une BD selon le modèle entités/associations, on procède de la manière suivante: 1. On trouve les mots clés du texte 2. On y élimine les synonymes 3. On distingue les attributs, les entités et les associations 4. On peint la modélisation Plusieures règles doivent être respectées: 1.* Chaque classe et chaque association doit avoir un identifiant (noté en souslignant ces attributs) 2.* Pour chaque attribut de chaque entité de chaque classe, il existe une et une seule valeur (des listes sont donc pas permies) 3. Tous les attributs sont élémentaires (= 2.) 4. Tous les attributs non identifiants dépendent de l'identifiant (ce qui résulte de la définition de "identifiant") 5. Chaque type d'association correspond à une association entre des entités de toutes les classes concernées (ce qui résulte de la définition de "type d'association") 6. Pour chaque occurance d'un type d'association, chaque attribut doit avoir une et une seule valeur (ce qui résulte de la définition d'"attribut de classe") 7. Tous les attributs d'une association doivent dépendre de l'identifiant de l'association (ce qui résulte de la définition de "identifiant") 8.* Une classe possède au moins un attribut 9.* Les noms des attributs sont uniques dans toute la BD Exemple: ________ _______ |Pilote | _________ |Vol | |--------| / \ |-------| |nom |---------| effectuer |--------|numéro | |adresse |(1,n) \_________/ (1,1)|date | |________| |_______| Annotation: Bien que le modèle s'appelle "Entités/Associations", il modélise des classes et des types d'associations. En parlant du modèle E/A, la notion "entité" signifie très souvent "classe". Ceci est évité dans ce résumé. Association binaire: Une association qui concerne deux entités ou deux classes. Association tertiaire: Une association qui concerne trois entités ou trois classes. Règles de transformation du modèle E/A: Les règles suivantes pour la simplification d'une BD sous forme E/A: 1. Si une classe a la multiplicité (1,1) par rapport à une association, les attributs de l'associtation peuvent être intégrés dans la classe. L'association n'a plus besoin d'attributs. 2. Une association entre plus de 2 classes peut être transformée en une classe. Celle-ci reprend les attributs de l'association. Elle est liée à toutes les classes concernées par des associations binaires. La multiplicité de la nouvelle classe par rapport à ces associations est (1,1) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Modèle relationnel et algèbre relationelle ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Contrainte: Une condition qui doit être respectée. Modèle relationnel: Un modèle qui a été proposé par Codd en 1970 et qui est le modèle le plus utilisé. Il se base sur la notion de la relation. Une relation de cette modèle est un sous ensemble du produit cartésien d'attributs. Un élément de la relation est donc un tuple avec une valeur pour chaque attribut -- ce qui correspond à une entité. Comme les attributs doivent être distincts, leur ordre n'est pas important. On ajoute une nombre de contraintes pour garantir l'intégrité des données. Exemple des relations: PILOTE(nom, ville, num_vol) VOL(num_vol, date) Exemple des entités: PILOTE(Bob, Chicago, #123) VOL(#123, 11|09|2001) Annotation: Dans toute la suite, la notation "relation" est utilisé dans le sens de ce modèle. Surclé d'une relation: Un ensemble de composantes, dont les valeurs identifient sans ambiguité un élément de cette relation. Exemple: {nom, ville} identifie bien un pilote Surclé evidente d'une relation: L'ensemble de toutes ses composantes. Clé d'une relation: Une surclé telle que si l'on y supprime une composante, le résultat n'est plus une surclé. Une clé est donc d'une surclé non redondante. Exemple: Pour PERSONNE, {nom, date_de_naissance} est une clé: Si on efface un attribut, l'identification n'est plus possible. Clé primaire d'une relation: Une clé qui a été choisie parmi les clés possibles. Les composantes de la relation qui appartiennent au clé primaire sont souslignés dans le schéma de la relation. Contrainte de domaine d'un attribut: Une limite pour les valeurs de cet attribut. Exemple: L'âge ne peut pas excéder la valeur 150 Contrainte fonctionnelle d'une classe: Un rapport obligatoire entre plusieurs attributs de cette classe. Exemple: L'âge d'une personne doit être la différence de la date actuelle et sa date de naissance. Contrainte référencielle de deux classes: L'exigence que deux attributs des deux classes doivent avoir la même valeur. Transformation du modèle E/A au modèle relationnel: L'application des règles suivantes: 1. À chaque classe correspond une relation, qui a * pour nom le nom de la classe * pour composantes les attributs de la classe * pour clé l'identifiant de la classe 2. À chaque type d'association correspond une relation, qui a * pour nom le nom de l'association * pour composantes l'union des attributs de l'association et des identifiants des classes concernées * pour clé l'union des identifiants des classes concernées 3. Si une classe C a (0,1) ou (1,1) comme multiplicité par rapport à une association binaire A, la relation de A peut être éliminée. On ajoute à C les composantes de A et la clé de l'autre classe concernée par A. Algèbre relationnelle: Un système d'opérations sur des relations. On distingue * les opérations de base * les opérations ensemblistes * l'union * la différence * le produit cartésien * les opérations spécifiques * la sélection (ou encore restriction) * la projection * la jointure * opérations complémentaires * l'intersection * la division * la sémi-jointure Chaque opération peut être notée sous forme textuelle, sous forme mathématique et sous forme graphique. Union de relation: Une opération, qui prend deux relations R1 et R2 du même schéma et redonne la relation qui a comme éléments les élements de R1 et les eléments de R2. Forme textuelle: UNION(R1,R2) Forme mathématique: R1 \/ R2 Forme graphique: ___ R1 ---> / U \__________\ résultat R2 ---> \___/ / Différence de relation: Une opération, qui prend deux relations R1 et R2 du même schéma et redonne la relation qui a comme éléments les élements de R1 sans les eléments de R2. Forme textuelle: DIFFERENCE(R1,R2) Forme mathématique: R1 - R2 Forme graphique: ___ R1 ---> / - \__________\ résultat R2 ---> \___/ / Produit cartésien de relation: Une opération, qui prend deux relations R1 et R2 et redonne la relation qui a comme éléments toutes les juxtapositions possibles d'un tuple de R1 avec un tuple de R2. Forme textuelle: PRODUCT(R1,R2) Forme mathématique: R1 x R2 Forme graphique: ___ R1 ---> / x \__________\ résultat R2 ---> \___/ / Restriction, Sélection: Une opération, qui prend une relation R et une condition C et redonne la relation qui a comme éléments tous les éléments de R qui satisfont C. La condition a la forme A op val où A est un attribut, op un opérateur de comparaison et val une valeur. Forme textuelle: SELECTION(R, C) Forme mathématique: SIGMA C (R) où SIGMA est la lettre grèque minuscule sigma Forme graphique: __A___ R ---> \ op /_________\ résultat \__/ / val Projection: Une opération, qui prend une relation R et un sous ensemble de ses attributs A={A[1], ... A[n]} et redonne la relation R sans les composantes appartenant à A. Forme textuelle: PROJECTION(R, A[1], ... A[n]) Forme mathématique: PI A[1], ... A[n] (R) où PI est la lettre grèque minuscule pi Forme graphique: R | V ________________ \ A[1],...A[n] / \____________/ | V résultat Jointure, Joint: Une opération, qui prend deux relations R1 et R2 et une condition C et redonne le produit cartésien R1 x R2. Dans ce produit, elle élimine d'abord les éléments qui ne satisfont pas la condition C. Puis, elle supprime les composantes identiques de la manière suivante: Si la i-ème et la j-ème composante de R1 x R2 ont le même nom, chaque tuple de forme (r[1],...,r[i],...,r[j],...r[n]) devient deux tuples (r[1],...,r[i],... ,...r[n]) et (r[1],...,r[j],... ,...r[n]) La condition C est de la forme A1 op A2, où A1 est un attribut de R1, A2 est un attribut de R2 et op est un opérateur de comparaison. Forme textuelle: JOINT(R1, R2, C) Forme mathématique: (?) Forme graphique: R1 R2 | | V V _ _ | \ op / | | \ / | |A1 \/ A2| | /\ | | / \ | |_/ \_| | V résultat Équijointure: Une jointure dont l'opérateur de la condition est '='. Jointure naturelle: Une équijointure dont les attributs de la condition ont le même nom. Dans ce cas, on n'écrit ni l'opérateur ni les deux attributs dans la forme graphique. La jointure naturelle correspond à la composition intuitive des informations des deux relations. Intersection de relation: Une opération, qui prend deux relations R1 et R2 du même schéma et redonne la relation qui a comme éléments les élements de R1 qui appartiennent aussi à R2. Il est R /\ R2 = R1 - (R1 - R2) Forme textuelle: INTERSECTION(R1,R2) Forme mathématique: R1 /\ R2 Forme graphique: ____ R1 ---> / /\ \__________\ résultat R2 ---> \____/ / Division de relation: Une opération, qui prend deux relations R1 et R2 et redonne une relation R. Un tuple t appartient à R ssi pour tout u appartenant à R2 la juxtaposition de t et u appartient à R1. Pour cela, il faut que les relations soient de la forme R1(A[1],...A[p],...A[n]) et R2(A[p+1],...A[n]). L'algorithme pour le calcul de R = R1 ÷ R2 est le suivant: 1. Soit R := {} 2. Pour tout élément r1=(a[1],...a[p],...a[n]) de R1 3. Pour tout élément r2=(b[1],...b[n-p]) 4. Si (a[1],...a[p],b[1],...b[n-p]) n'appartient pas à R1, alors continue à 7 5. FinPourTout 6. R := R \/ { (a[1],...a[p]) } 7. FinPourTout Il est R1 ÷ R2 = PI A[1],... A[p] (R1) - PI A[1],... A[p] ((PI A[1],...A[p] (R1) x R2) - R1) Forme textuelle: DIVISION(R1,R2) Forme mathématique: R1 ÷ R2 Forme graphique: ___ R1 ---> / ÷ \__________\ résultat R2 ---> \___/ / Sémi-jointure, Démi-jointure à gauche: Une opération, qui prend deux relations R1 et R2 et redonne la projection de la jointure naturelle sur les attributs de R1. On compose donc les informations des deux relations et on ne garde que les attributs de R1. Forme textuelle: SEMI-JOINTURE(R1,R2) Forme mathématique: R1 |x R2 Forme graphique: R1 R2 | | V V |\ / | \/ | /\ |/ \ | V résultat ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ SQL ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Schéma BNF: Une des chaînes suivantes * "C" où C est un caractère Extension: La chaîne qui ne comprend que ce caractère * "AB" où A et B sont des schémas BNF Extension: Toute chaîne qui est la concatenation d'une chaîne de l'extension de A et d'une chaîne de l'extension de B * "[A]" où A est un schéma BNF Extension: La chaîne vide et toute chaîne de l'extension de A * "{A}" où A est un schéma BNF Extension: Toute chaîne qui est la concaténation de chaînes de l'extension de A * "(A|B)" où A et B sont des schémas BNF Extension: Toute chaîne qui appartient soit à l'extension de A soit à l'extension de B * "" où N est le nom d'une classe Extension: Tout nom d'une entité de N Chaque schéma BNF a donc une extension associée. Cette extension est un ensemble de chaînes qui sont dites d'avoir la forme du schéma BNF. BNF, Forme Backus-Naur d'un langage: Un schéma BNF dont l'extension est le langage. SQL, Strucured Query Language: Un langage qui est à la fois un LDD et un LDM et qui a été proposé par IBM. Table: Une représentation d'une relation d'une BD relationelle. Alias: Un identifieur qu'on choisit pour une table. Identifieur d'attribut: Une chaîne qui fait référence à un attribut ou plusieurs attributs d'une table. Une telle chaîne a la forme suivante: [ (|) . ] (|*) Si le nom de la table n'est pas évident, on met son nom ou bien son alias. Par contre, si la table est connue, on peut la supprimer. Si on veut faire référence à un seul attribut, on met son nom. Si on veut faire référence à tous les attributs de la table, on remplace par l'étoile. Requêtes SQL: Le sous ensemble de SQL qui est utilisé pour l'interrogation de la BD. Il de la forme suivante: SELECT [DISTINCT] { (|) } FROM {
[] } [ WHERE ] [ GROUP BY { } ] [ ((UNION | INTERSECT) | MINUS) ( ) ] [ ORDER BY { [ (ASC | DESC) ] } ] Il faut que toutes les tables auxquelles est fait référence se trouvent énumérées dans la clause FROM. Une requête SQL effectue l'algorithme suivant: 1. Construis le produit cartésien P de toutes les tables données par FROM 2. Introduis les alias donnés par FROM 3. Si WHERE est donné, alors élimine de P tous les éléments qui ne satisfont pas la condition 4. P devient la projection de P sur les attributs donnés par SELECT 5. Si DISTINCT est donné, alors élimine de P les éléments doubles 6. Si GROUP BY est donné, alors regroupe les éléments de P selon le premier attribut, puis regroupe chaque groupe selon le deuxième attribut etc. 7. Calcule les expressions agrégat, ajoute-les à P 8. Si ORDER BY est donné, alors classe les éléments de P selon l'ordre lexicographique du premier attribut donné, soit d'ordre ascendant, soit d'ordre déscendant. Puis, classe les éléments qui sont tombés sur la même place par le deuxième attribut etc. 9. Si UNION est donné, alors P devient l'union de P et du résultat de la requête donnée 10. Si INTERSECT est donné, alors P devient l'intersection de P et du résultat de la requête donnée 11. Si MINUS est donné, alors P devient la différence de P et du résultat de la requête donnée SQL ne distingue pas les minuscules des majuscules. Les requêtes intérieures peuvent utiliser les alias définis par la requête entourante. Annotation: J'ai supprimé les parts dont on n'a pas parlé dans le cours. Condition SQL: Une chaîne qui a une des formes suivantes (avec les éléments qui satisfont la condition): * | Tous les éléments dont les valeurs satisfont la comparaison * AND Tous les éléments qui satisfont toutes les deux conditions * OR Tous les éléments qui satisfont au moins une des deux conditions * NOT Tous les éléments qui ne satisfont pas la condition * IN ( ) Tous les éléments dont la valeur de l'attribut donné se retrouve dans le même attribut de la requête donnée * ALL ( ) Tous les éléments dont la valeur de l'attribut donné satisfait la comparaison avec toutes les valeurs du même attribut dans la requête donnée * ANY ( ) Tous les éléments dont la valeur de l'attribut donné satisfait la comparaison avec une valeur du même attribut dans la requête donnée * EXISTS ( ) Tous les éléments pour lesquels la requête n'est pas vide * BETWEEN AND Tous les éléments dont la valeur de l'attribut donné se trouve entre les deux valeurs données * LIKE Tous les éléments dont la valeur de l'attribut donné a la forme donnée par la chaîne. Un '.' dans cette chaîne correspond à un symbole quelconque et un '%' correspond à une suite de symboles quelconques. * IS [NOT] NULL Tous les éléments dont la valeur de l'attribut donné [n'] est [pas] inconnu Expression agrégat: Une chaîne de la forme suivante () AS Une telle expression crée une composante qui a comme nom et le résultat de la fonction agrégat comme valeur. Fonction agrégat: Une fonction qui prend un identifieur d'attribut et redonne une valeur. Il y en a les suivantes: * COUNT, qui redonne la cardinalité de son paramètre * SUM, qui redonne la somme des éléments de son paramètre * MIN, qui redonne le minimum des éléments de son paramètre * MIN, qui redonne le maximum des éléments de son paramètre * AVG, qui redonne la moyenne des éléments de son paramètre ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Normalisation et dépendances fonctionelles ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ DF, Dépendance fonctionelle entre les ensembles d'attributs X et Y: Le phénomène que deux entités qui ont les mêmes valeurs pour les attributs de X ont aussi les mêmes valeurs pour les attributs de Y. Il s'agit donc d'une redondance. On dit que X détermine Y et que Y dépend fonctionnellement de X. On écrit X -> Y. Exemple: Si on stocke pour un jour férié son nom, son jour, son mois et sa saison, la saison dépend fonctionnellement du mois: JF(noel, 25, décembre, hiver) JF(saint_sylvestre, 31, décembre, hiver) { mois } -> { saison } Si on connait le mois, on connait aussi la saison. Annotation: Cela correspond à l'idée de la supervenance de la philosophie de l'esprit, voir pom.txt (en allemand) Dépendance entre les valeurs x[1],...x[n] et y[1],...[m]: L'information que les valeurs x[1],...x[n] pour les attributs X[1],...X[n] entraînent toujours les valeurs y[1],...y[m] pour les attributs Y[1],...Y[m]. Exemple: Le savoir que la valeur "décembre" pour "mois" entraîne toujours la valeur "hiver" pour "saison" est une dépendance. Anomalie: Une difficulté dans la gestion d'une BD qui provient d'une classe qui a deux ensembles d'attributs X et Y qui sont fonctionnellement dépendants. Une instance de la classe stocke donc implicitement la dépendance entre les valeurs des attributs, c'est-à-dire le savoir que x[1],...x[n] entraîne y[1],...[m]. Exemple: La gestion des jours fériés de la facon de ci-dessus peut poser des problèmes. Anomalie d'insertation: Le problème qu'on ne peut pas mémoriser une nouvelle dépendance entre les valeurs de X et Y sans créer une nouvelle instance de la classe entourante. Exemple: Si on n'a pas de jour férié au printemps, on ne peut pas stocker l'information que "mars" entraîne "printemps". Anomalie de suppression: Le problème qu'on ne peut pas supprimer la dernière instance avec certaines valeurs pour X sans perdre l'information de dépendance qui est stocké dans cette instance. Exemple: Si on supprime Noel et Saint Sylvestre, on perd l'information que "décembre" entraîne "hiver". Anomalie de modification: Le problème qu'on ne peut pas changer une dépendance sans changer les instances de la classe. Union des ensembles d'attributs X et Y: L'ensemble qui contient les attributs de X et les attributs de Y. On le note XY. Il est XY=YX et XX=X. DF1, Reflexivité de DF: Le fait que Si Y < X, alors X -> Y Exemple: Comme {jour} < {jour, mois}, alors {jour, mois} -> {jour} DF2, Augmentation de DF: Le fait que Si X -> Y, alors WX -> WY pour un attribut W quelconque Exemple: Comme {mois} -> {saison}, alors {jour, mois} -> {jour, saison} DF3, Transitivité de DF: Le fait que Si X -> Y et Y -> Z, alors X -> Z Exemple: Comme {nom} -> {mois} et {mois} -> {saison}, alors {nom} -> {saison} Règles de Armstrong: L'ensemble de DF1, DF2 et DF3, qui permet de déduire DF4, DF5 et DF6. DF4, Union de DF: Le fait que Si X -> Y et X -> Z, alors X -> YZ Exemple: Comme {nom} -> {mois} et {nom} -> {jour}, alors {nom} -> {jour, mois} DF5, Décomposition de DF: Le fait que Si X -> YZ, alors X -> Y et X -> Z Exemple: Comme {nom} -> {jour, mois}, alors {nom} -> {jour} et {nom} -> {mois} DF6, Pseudotransitivité de DF: Le fait que Si X -> Y et WY -> Z, alors WX -> Z Exemple: Comme {nom_du_mois} -> {mois} et {jour,mois} -> {nom}, alors {nom_du_mois, jour} -> {nom} Dépendance fonctionnelle élémentaire, DFE: Une dépendance fonctionnelle X -> Y telle que * Y ne comporte qu'un seul attribut * Pour tout X' < X, X' -> Y n'est pas vérifiée Il s'agit donc d'une dépendance minimale, non redondante. Exemple: {jour, mois} -> {saison} est redondante. Par contre {mois} -> {saison} est élémentaire, car il suffit d'avoir le mois pour avoir la saison. Forme canonique d'un ensemble F de DFs: Un ensemble de DFEs qui exprime les mêmes dépendances. On le note Fc. Tout ensemble F de DFs peut être transformé en forme canonique par l'algorithme suivant: 1. PourTout X -> Y[1],...Y[n] 2. Pour i=1..n, introduis X->Y[i] 3. Efface X -> Y[1],...Y[n] 4. FinPourTout 5. PourTout X -> Y, WX -> Y 6. Efface WX -> Y 7. FinPourTout Fermeture transitive d'un ensemble de DFs: L'ensemble de DFs qu'on peut déduire de F à l'aide de la transitivité. On le note F+. Tout ensemble F de DFs peut être transformé en sa fermeture transitive par l'algorithme suivant: 1. PourTout X->Y, Y->Z 2. Introduis X->Z 3. FinPourTout Couverture irredondante d'un ensemble F de DFs: Un ensemble minimal de DFEs qui permet de déduire toutes les dépendances à l'aide de la transitivité. On le note F-. La couverture irredondante peut être calculée par l'algorithme suivant: 1. PourTout X->Y, Y->Z, X->Z 2. Efface X->Z 3. FinPourTout Attribut ensembliste: Un attribut dont les valeurs sont des ensembles. Relation en 1FN: Une relation sans attributs ensemblistes. Toute relation R peut être transformé en 1FN par décomposition. Décomposition d'une relation R: L'algorithme suivant: 1. Détermine une clé de R 2. PourTout attribut ensembliste A de R 3. Introduis une nouvelle relation R' qui a comme composantes la clé de R et un attribut du nom de A 4. PourTout élément r de R 5. Soient c[1],...c[n] les valeurs clé de r 6. Soient a[1],...a[m] les valeurs de l'attribut A de r 7. Pour i=1..m, repète 8. Introduis R'(c[1],...c[n], a[i]) 9. FinPour 10. FinPourTout 11. Supprime A de R 12. FinPourTous DF partielle d'un attribut d'une relation: Une DF clé -> { attribut } qui n'est pas élémentaire. C'est-à-dire: Un sous ensemble de la clé est déjà suffisant pour déterminer l'attribut. Relation en 2FN: Une relation en 1FN qui n'a pas de DF partielle. Toute relation R en 1FN peut être transformée en 2FN par l'algorithme suivant: 1. PourTout DF partielle {C[1],...C[n]} -> { A } de R 2. Introduis une relation R' = PROJECTION(R,C[1],...C[n],A) 3. Efface A de R 4. FinPourTout DF directe: Une DF qui ne peut pas être déduite par transitivité. Relation en 3FN: Une relation en 2FN dont toute DF est directe. Toute relation en 1FN peut être transformée en 3FN par l'algorithme de synthèse de Bernstein. Algorithme de synthèse de Bernstein: L'algorithme suivant qui transforme une relation en 1FN R en 3FN: 1. Soit F l'ensemble des DFs de R 2. Détermine la couverture irredondante de F 3. Partitionne F = F[1] \/ F[2] \/ ... F[n] de sorte que les DF d'un ensemble F[i] ont la même partie gauche 4. Pour i=1..n, repète 5. Introduis une relation R[i], qui a comme clé la partie gauche de F[i] et comme autres composantes la partie droite de F[i] 6. FinPour Relation en 3FNBC: Une relation en 3FN, dont toute DF est de la forme clé -> X. Normalisation: L'algorithme suivant qui transforme une grande relation en un ensemble de relations en 3FN afin d'éviter la redondance: 1. Transforme la relation en 1FN 2. Détermine l'ensemble F des DFs 3. Détermine la forme canonique de F 4. Si une solution non biasée est demandée, alors détermine la fermeture transitive de F 5. Détermine la couverture irredondante de F 7. Effectue l'algorithme de synthèse de Bernstein à partir de l'étape 3 Graphe d'un ensemble de DFs: Un graphe qui a comme noeuds des sous ensembles d'attributs et comme flèches les DFs entre eux. Ce graphe peut être utilisé pour effectuer facilement l'algorithme de normalisation.