Réda DEHAK [email protected]

Réda DEHAK [email protected]

Réda DEHAK 2

Organisation du cours

• Horaires :– Cours : 42 heures en T3 (jeudi + vendredi).– TD : 4 heures (mercredi)

• Projet :– Conception et utilisation d’une base de données sous

Postgresql.• Pré-requis :

– Théorie des ensembles– Algorithmes et structures de données.

Réda DEHAK 3

Plan du cours BDD

1. Conception d’une BD :• Comment construire une BD?• Quelles sont les informations à rajouter dans la BD?• Comment structurer une BD?• Trouver la meilleure représentation• …

2. Utilisation d’une BD :• Comment accéder aux informations contenues dans la BD?• Comment utiliser les capacités du SGBD?• …

3. Implémentation des SGBD (DBMS) :• Comment implémenter un SGBD : traitement des requêtes, gestionnaire des

transactions, organisation du support physique … ?

Réda DEHAK 4

Conception d’une base de données

1. Le modèle Entité Association.

2. Le modèle Relationnel.

3. Conception et optimisation du schéma relationnel (Formes normales).

4. Conception et optimisation du schéma physique.

Réda DEHAK 5

Utilisation d’une BD

1. Rappel de logique.2. Algèbre relationnel & Calcul

relationnel.3. Le langage SQL :

• Introduction.• Définition du schéma.• Requêtes sur une table.• Requêtes sur plusieurs tables.• Insertion, Suppression et MAJ.• Contrainte, Vue et Trigger.• PL/SQL

Réda DEHAK 6

Implémentation des SGBD

1. Stockage des données.2. Les indexes.3. Évaluation des requêtes.4. Optimisation des requêtes.5. Gestion de la concurrence

des transactions.6. Recouvrement et gestion des

logs.

Réda DEHAK 7

Bibliographie

1. R. Ramakrishnan, J. Gehrke, « Database

Management Systems », 3e édition, 2003.

2. J.D. Ullman, H.G. Molina, J. Widom,

« Database Systems : The Complete Book »,

2001.

3. R. Elmasri, S.B. Navathe, « Fundamentals of

Database Systems », 2003.

Réda DEHAK 8

Bibliographie

4. F. Brouard, « SQL », 2001.

http://sqlpro.developpez.com

5. J. Celko, « SQL avancé : programmation et

techniques avancées », 2000.

6. P. Gulutzan, T. Pelzer, « SQL-99 Complete,

Really: An Example-Based Manual of the

New Standards », 1999.

Réda DEHAK 9

Bibliographie

7. G.C. Simsion, « Data ModelingEssentials: Analyse, Design andInnovation », 2000.

8. D. Kroenke, « Database Processing:Fundamentals, Design & Implementation», 2003.

Réda DEHAK 10

Plan du cours

1. Définitions.

2. Objectifs et fonctions d’un SGBD.

3. Architecture d’un SGBD.

4. Organisation d’une BD.

5. Histoire des SGBD.

Réda DEHAK 11

Base de données (Database)

• Base de données (BD) :

– Une collection de données modélisant les objets d’une partie du monde réel et servant de support à une application.

– Exemple : La scolarité des étudiants à EPITA…

Réda DEHAK 12

Système de Gestion de Base des Données (SGBD)

DataBase Management System (DBMS)

• Système de Gestion de Base de Données (SGBD)– Système logiciel gérant une BD

• Peut avoir des composantes matériel

– Mono ou multi-ordinateur– En général, peut gérer plusieurs BDs– Peux aussi accéder aux BDs d’autres

SGBDs

Réda DEHAK 13

Banque de données

• Banque de données :– Une base de données (BD).– Un système de gestion de base de données (SGBD).– Services …

+ +

Réda DEHAK 14

Plan du cours

1. Définitions.





Réda DEHAK 15

Fichiers vs. SGBD?

Fiches de paye

Production en temps réel

Commandes

Clients

PiècesGestion d’une entreprise

Réda DEHAK 16

Fichiers vs SGBD?

Programme 1

Données

Fichiers

Programme 2

Données

Fichiers

Programme 3

Données

Fichiers

Programme 4

Données

Fichiers

Relations ?

Réda DEHAK 17

Problèmes avec les fichiers

• Redondance des données.– Partage limité au niveau du fichier.– Problèmes de cohérence globale des données.

• Mauvaise structuration des données.• Dépendance entre les programmes et les données

(fichiers).– Modification des fichiers modification des

programmes.– Difficulté pour le développement de nouvelles

applications.

Réda DEHAK 18

Fichiers vs. SGBD?

Fiches de paye


Commandes

Clients

PiècesGestion d’une entreprise

Réda DEHAK 19

SGBD

Fiches de paye


Commande

Clients

Pièces

Base de données

Réda DEHAK 20

Base de données

Programme 1 Programme 2 Programme 3 Programme 4

SGBD : Requêtes, transactions

Base de données

Réda DEHAK 21

Objectifs d’un SGBD

1. Indépendance des programmes aux données :─ Dépendance physique.─ Dépendance logique.

2. Simplicité des Manipulations des données :─ Langage non procédural : quoi et non comment.─ Recherche, Insertion et Mise à jour.

3. Efficacité des accès aux données :─ Temps de réponse.─ Débit global.

Réda DEHAK 22

Objectif d’un SGBD

4. Partage et sécurité des données :─ Simultanéité lecture/écriture.─ Confidentialité (authentification, droits d'accès, …).─ Gestion de la concurrence des transactions.─ Restauration après pannes (journal des transactions, sauvegarde).

5. Redondance contrôlée des données :─ Sauvegarde des données.

6. Conception facilité des applications :– Conception visuelle des BD (diagrammes E/R, E/A, objets).– Conception des traitements (diagrammes de flux entre modules).– Dictionnaire de données (objets BD, graphiques, applicatifs).

Réda DEHAK 23

Objectifs des SGBD

7. Facilité de l’administration système de la BD :– Outils d'audit & de tunning.– Visualisation des plans d ’accès.– Élaboration de statistiques.

Réda DEHAK 24

Langage des SGBD

• Langage de définition des données (LDD) :– Définition des schémas conceptuel, externe et

interne.– Ces définitions sont stockées dans le répertoire

système.• Langage de manipulation de données (LMD) :

– Langage de requêtes déclaratif pour lire et mettre àjour les données.

– Peut être autonome (ex. SQL) ou intégré dans un langage de programmation (C, java, …).

Réda DEHAK 25

Utilisateurs d’un SGBD

• Utilisateur final (ad-hoc) :– Recherche d’informations sans connaître la BD.– Accède à la BD par des interfaces applicatives, Web…– Utilisation de langage simple (ex: QBE).

• Programmeur d’applications :– Conçoit et implémente des applications qui accèdent à la BD

pour les utilisateurs finaux.– Spécialiste de SQL.

• Administrateur de la BD :– Définit et gère le schéma conceptuel et les vues.– Gère le schéma interne et règle les performances.– Charge et reformate la BD.– Gère la sécurité et la fiabilité.

Réda DEHAK 26

Plan du cours

1. Définitions.





Réda DEHAK 27

SGBDM.S.

Gestionnaire de fichiers

SGBD

Programmes d’application




SGBD externe

SGBD interne

Réda DEHAK 28

Architecture d’un SGBD

Gestionnaire de l’espace disque

Gestionnaire du tampon

Méthodes d’accès et fichiersGestionnaire des transactions

Gestionnaire des verrous

Récupération

Plan d’exécution Parser

OptimisationÉvaluation des opérateurs

Index, donnéesBase de donnéesSGBD

Évaluation des

requêtes

Gestion de la concurrence

Réda DEHAK 29

Décomposition d’un SGBD

Data

Metadata

Storage Manager

Query Processor

Transaction Manager

Schema Modification Query Modification

Réda DEHAK 30

Storage manager

Il est composé de deux parties :

1. Le file manager : permet de localiser les fichiers sur le disque et ainsi pouvoir récupérer les blocs du disque pour le buffer manager.

2. Le buffer manager : extraire un bloc de données du disque via le file manager et de le ranger en mémoire vive. Il gère la synchronisation entre le disque et la mémoire vive.

Réda DEHAK 31

Transaction

• Transaction : Une séquence considérée atomique d’actions (reads/writes) sur la base de données.

• Chaque transaction, qui s’exécute complètement, doit laisser la BD dans un état cohérent (consistent state) si la BD était dans un état cohérent avant le début de la transaction.– Les utilisateurs peuvent spécifier des contraintes d’intégrités

sur les données. Le SGBD doit forcer la satisfaction de ces contraintes.

– Le SGBD n’a aucune informations sur la sémantique des informations stockées dans la BD.

Réda DEHAK 32

Objectifs du Transaction Manager

• Préserver les propriétés ACID des transactions.– Atomicité : tout ou rien.– Cohérence de la base.– Isolation : Exécution indépendante.– Durabilité : préserver les modifications après un

commit même en cas de panne.

• Gestion des verrous.• Gestion du journal de la BD (les logs).

Réda DEHAK 33

Plan du cours

1. Définitions.





Réda DEHAK 34

Organisation d’une BD

Base de données physique

Schéma physique

Schéma conceptuel

Schéma externe 1

Schéma externe 2

Schéma externe n

Niveau interneNiveau conceptuelNiveau externe

User 1

User 2

User n Modélisation du Monde réel

Réda DEHAK 35

Exemple

• Conceptuel – description du monde réel

• Interne– implémentation dans les

fichiers

• Externe (vues)– description vues par un

utilisateur (ou un groupe d’utilisateurs)

Client Commande Produit

02345425Alex11097

04567689Durant12345

014586789Dupont12456

TelNomN°

Client

Index

13ScieAlex

4567ClouDupont

1234marteauDupont

QteProduitNom

Commande

Réda DEHAK 36

SGBD

Fiches de paye


Commande

Clients

Pièces

Base de données

Réda DEHAK 37

Plan du cours

1. Définitions.





Réda DEHAK 38

Histoire des bases de données (1)

• Années 1960 :– Début 1960 : Charles Bachman développe le premier

SGBD, IDS, chez Honeywell.• Modèle réseau : Les associations entre les données sont

représentées par un graphe.

– Fin 1960 : IBM lance le SGBD IMS• Modèle hiérarchique : les associations entre les données

sont représentées par un arbre.

– Fin 1960 : Standardisation du modèle réseau, Committee On DAta SYsteme Languages (CODASYL).

Réda DEHAK 39


• Années 1970 :– 1970 : Ted Codd définit le modèle relationnel au IBM San Jose

Laboratory (aujourd’hui IBM Almadem)– 2 projets de recherche majeurs

• INGRES : University of California, BerkleyDevint le produit INGRES suivi par POSTGRES, logiciel libre, quidevint le produit ILLUSTRA racheté par INFORMIX.

• Système R. IBM San Jose LaboratoryDevint DB2, inspira ORACLE

– 1976 : Peter Chen définit le modèle entité association– 1978 : Naissance de Relational Software Inc (ORACLE)

(version 1.0).

Réda DEHAK 40


• Années 1980 :– Maturation de la technique relationnelle.– 1989 : Standardisation de SQL (SQL89).

• Années 1990 :– 1992 : Norme SQL2 (SQL92)– Amélioration constante de la technologie relationnelle.– Support de la distribution et du parallélisme.– Modèle Objet (ODMG).– 1999 : Le relationnel-objet SQL3 (SQL99)– Nouveaux domaines d’application : entrepôts de données et

décisionnel, Web, Multimédia, Mobiles, etc.

Réda DEHAK 41


• Recherches actuelles :– Internet et Web.– Base de données multimédia.– Aide à la prise de décisions et extraction de

connaissance (DATA MINING)– Interrogation par le contenu des objets multimédia

distribués.– Systèmes d’Informations Géographiques (SIG)– …

Réda DEHAK 42

Types de SGBD : Par modèle de données

• 1ère génération 1950 – 65– SGF, SGF généralisés avec les langages booléens de manip.

• 2ème génération 1965 - 70– SGBD navigationnel

• Hierarchique (IMS), Réseau (Codasyl), Pseudo-relationnel

• 3ème génération 1969 - …– SGBD relationnel (DB2, Oracle, Informix, MsAcess…

• SGBD OO 1990 - 1999– En pratique : une impasse (O2, Objectstore, Objectivity..)

• SGBD relationnel – objet (RO) 1993 - …– Évolution de tout SGBD relationnel


Réda DEHAK 44

Plan

1. Modélisation2. Modèle E/A

1. Entité, type d’entité, attributs, identifiant2. Association, type d’association, attributs, identifiant3. Cardinalités4. Entité faible5. Spécialisation6. Agrégation7. Contraintes d’intégrités

3. Validation d’un schéma

Réda DEHAK 45

But de la modélisation

• Fournir des outils et un cadre rigoureux pour l’analyse des données et de leurs liaisons.

• Décrire la réalité perçue à travers les données mises en jeu.

• Indépendance par rapport aux opérations que l’on effectuera ultérieurement dessus.

Réda DEHAK 46

Générations des méthodes de modélisation

• 1ère génération : Méthodes d'analyse et de décomposition hiérarchiques– Diviser pour régner (Problème ⇒ Sous problème)– Warnier, SADT, Jackson, De Marco

• 2ème génération : Méthodes d'analyse et de représentation systémiques– Séparation des données et traitements– Merise, Axial, SSADM

• 3ème génération : Méthodes d'analyse et de conception orientées objets– Réconciliation données et traitements– Réutilisation de composants

Réda DEHAK 47

Phases de la conception d’une BD

Mini-monde

Recueil et analyse des besoins

Besoins en donnéesBesoins fonctionnels

ConceptionAnalyse fonctionnelle

Schéma conceptuel(dans un modèle de données

de haut niveau)

Définition de transaction de haut niveau

Indépendant du SGBD

Réda DEHAK 48

Phases de la conception d’une BDSchéma conceptuel

(dans un modèle de données de haut niveau)

Définition de transaction de haut niveau

Conception logique

(Mapping du modèle de données)

Schéma logique (conceptuel)

(Spécifique au SGBD)

Conception physique

Schéma interne

Conception des programmes applicatifs

Implémentation de transaction

Programmes applicatifs

Dépendant du SGBD

Réda DEHAK 49

Le modèle Entité Association (EA)

• Origines : Peter Chen (1976).• Concepts de base :

– Entité– Type d’entité– Association– Type d’association– Attribut– Valeur– Type de valeur

Réda DEHAK 50

Les outils

• Sybase : Power AMC

• Win’design

• Oracle designer

• Vision

• Rational Rose

• …

Réda DEHAK 51

Exemple

Optique : Conception d’une base de données destinée à conserver des descriptions d’articles parus dans les journaux.

1. Un éditeur édite des journaux. Il est caractérisé par un nom et une adresse.

2. Un journal est édité par un éditeur et publie des articles dans ses numéros. On conservera le nom du journal et le nom de son rédacteur en chef.

3. Un numéro de journal contient une collection d’articles.4. Chaque article paru dans un numéro est signé par un auteur. On

désire conserver le titre et un résumé de l’article ainsi que le nom de son auteur.

5. Les auteurs sont connus par leur nom, leur prénom, leur adresse et leur date de naissance.

Réda DEHAK 52

Diagramme E/A

ARTICLETitre

Résumé

NUMERON°

Date

AUTEURNom

Prénom

Adresse

Date de naissance

EDITEURNom Ed

Adresse

JOURNALNom J

EDITEUREN CHEF

Nom

Prénom

EDITER(1,n) (1,1)

SORTIE

PARUTIONRÉDACTION

DIRIGE

(1,n)

(1,1)

(0,n)

(1,n)(1,n)

(1,1)

(1,1)

(1,1)

Réda DEHAK 53

Plan




Réda DEHAK 54

Entité

Une entité est une chose concrète ou abstraite de la réalité perçue à propos de laquelle on veut conserver des informations. Une entité a une existence autonome.

• Entité = chose concrète ou abstraite, objet

Exemples :• Chaque crayon qui se trouve sur la table de l’étudiant

Dupont.• Le projet Tiger.

Réda DEHAK 55

Type d’entité

Dans un processus de modélisation, on ne s’intéresse pas à chaque entité séparément mais à un type d’entité.

Définitions:1. Un type d’entité est la classe de toutes les entités de la

réalité perçue qui sont de même nature est qui jouent le même rôle.

2. Un type d’entité est décrit par :─ Un nom─ Une définition qui précise la signification que nous voulons

retenir de ce type d’entité dans le cadre de la base de données.

─ Une liste d’attributs

Réda DEHAK 56

Attributs

Chaque entité possède ses propriétés particulières appelées attributs.

Définitions :1. Un attribut est une caractéristique ou une qualité d’une

entité ou d’une association, il peut prendre une (ou plusieurs) valeur (s).

2. Une valeur est un symbole utilisé pour représenter un fait élémentaire.

Réda DEHAK 57

Exemples

• Le type d’entité « auteur » regroupe des personnes auteur d’articles de journaux caractérisées par leur nom, leur prénom, leur adresse et leur date de naissance.

Par abus de langage :

• Entité ⇔ Type d’entité.

• Une occurrence d’une entité est un individu particulier faisant partie de l’entité.

Réda DEHAK 58

Exemples

12 Nov 1842Date de naissance

ParisAdressePascal, PierrePrénom

BlaiseNom

Auteurs

ValeursAttributsEntités

Attributs atomiques : Nom, Prénom, Adresse

Attributs composés : Date de naissance(jour, mois, année)

Attributs monovalués (Une seule valeur pour une entité donnée) : Nom, Adresse, Date de naissance.

Attributs Multivalués (Plusieurs valeur pour une entité donnée) : Prénom

Réda DEHAK 59

Diagramme E/A

AUTEUR

Nom Prénom adresse

Date de naissance

Jour Mois Année

Réda DEHAK 60

Exemple






5. Les auteurs sont connus par leur nom, leur prénom, leur adresseet leur date de naissance.

Réda DEHAK 61

Entité : Schéma, Intention et extension

• La description d’une entité est appelée le schéma de l’entité (intension de l’entité).

• L’ensemble des occurrences d’une entité qui existent (dans la base de données) à un instant donné s’appelle l’extension de l’entité.

• Le schéma de l’entité ne va pas changer fréquemment car il représente la structure de l’entité.

Réda DEHAK 62

Exemple

• Schéma, Intension :Auteur(Nom, Prénom, Adresse, Date de naissance)

• Extension :

12 janvier 1968LondreDavidLegrand

……………………..24 février 1973MarseilleDavidBeaudoin

14 novembre 1970ParisJeanDoignonDate de naissanceAdressePrénomNomAuteur

Réda DEHAK 63

Type de valeur ou domaine d’un attribut

• Le type de valeur ou le domaine d’un attribut est la spécification de toutes les valeurs possibles que peut prendre un attribut.

• Exemples :

– Nom : Chaîne de caractères alphabétiques.– Numéro de journal : entier compris entre 1 et 366.– Couleur : {rouge, bleu, jaune, vert, blanc, noir}

Réda DEHAK 64

Clé d’une entité

• On appelle attributs clé ou identifiant d’une entité un groupe minimal d’attributs (et/ou rôles) tel qu’à chaque combinaison de valeurs prises par ce groupe correspond au plus une occurrence de cette entité.

1. Cas 1 : L’identifiant est formé d’un ou plusieurs attributs de l’entité à identifier.

Nom de l’éditeur est la clé de l’entité éditeur.Nom et prénom sont les attributs clé de l’entité auteur.

2. Cas 2 : on ajoute à l’entité un attribut artificiel, un numéro arbitraire dont l’unicité est garantie

Réda DEHAK 65

Exemple

13 mars 1976ToulouseChristopheLegrand

12 janvier 1968LondreDavidLegrand24 février 1973MarseilleDavidBeaudoin

14 novembre 1970ParisJeanDoignonDate de naissanceAdressePrénomNomAuteur

Réda DEHAK 66

Diagramme E/A

AUTEUR

Nom Prénom adresse

Date de naissance

Jour Mois Année

Réda DEHAK 67

Exemples

ENTITE Liste d’attributsauteur nom, prénom, adresse, date de naiss.éditeur nom ed, adressejournal nom j.

rédacteur en chef nom, prénomarticle titre, résumé

Numéro n°, date

Réda DEHAK 68

Diagramme E/A

AUTEURNom

Prénom

Adresse

Date de naissance

EDITEURNom Ed

Adresse

JOURNALNom J

ARTICLETitre

Résumé

NUMERON°

Date

EDITEUREN CHEF

Nom

Prénom

Réda DEHAK 69

Plan




Réda DEHAK 70

Association

• Une association est une correspondance entre deux ou plusieurs occurrence d’entités à propos de laquelle on veut conserver des informations.

• L’existence d’une association exige l’existence des occurrences d’entités qu’elle met en correspondance.

• Chaque occurrence d’entité joue un rôle particulier dans l’association.

• On dit que ces occurrences d’entités participent àl’association.

Réda DEHAK 71

Exemples

• Jérome travaille sur la machine FIDJIL’association TRAVAILLE relie la personne JEROME a la

machine FIDJI.Jérome : rôle de travailleurFidji : rôle l’outil de travail

• Le Real de Madrid a battu Juventus au stade Delle AlpiAssociation BATTRE relie : l’équipe du REAL, l’équipe de

JUVENTUS et le stade DELLE ALPIREAL : rôle équipe gagnante.JUVENTUS : rôle équipe perdante.DELLE ALPI : rôle lieu du match.

Réda DEHAK 72

Association, type d’association

• Un type d’association est la classe de toutes les associations possibles de la réalité perçue qui vérifient la définition constitutive du type.

Par abus de langage :• Association ⇒ type d’association• Occurrence d’association ⇒ association

Exemple :• Ecriture(Auteur, Article)

Réda DEHAK 73

Diagramme E/A

MACHINEN° IP

NOM

Processeur

T. Mémoire

EQUIPENom

Adresse

STADENom S

Adresse

Nombre de plae

PERSONNENom

Prénom

Adresse

Date de naissance

TRAVAILLERTravailleur

Outil

BATTRE

gagnant

perdant

lieu

Réda DEHAK 74

Degré d’une association

• Nombre d’entité qui participe à une association.

• Exemple :– Ecriture(Auteur, article) degré =2– Cours(Salle, Groupe, Prof) degré =3

Réda DEHAK 75

Attribut d’une association

• Une association peut avoir ses attributs propres.

• Exemples :– Commande(Client, Produit, qte)– Cours(Salle, Groupe, Prof, date, durée)

Réda DEHAK 76

Association réflexive

• Appelée aussi cyclique ou récursive.

• Exemple :– FILIATION(père : PERSONNE, fils : PERSONNE)

Dans une occurrence d’association une personne peut assumer un des deux rôles père ou fils.

– Compose( composant : PRODUIT, composé : PRODUIT)

Réda DEHAK 77

Diagramme E/A

personne

nss nom prénom

parentsest père ou mère de

Fils, fille

Réda DEHAK 78

Diagramme E/A

produit

nprod nom volume

composeest composé

est composant

Réda DEHAK 79

Clé de l’association

• L’identifiant de l’association est implicite :– une association est identifiée par l’ensemble des rôles assumés

par les entités qu’elle met en correspondance.– L’identifiant de l’association sera formé par l’ensemble des

identifiants des entités qui participent à l’association.

• Remarque :– Il peut exister qu’une seule occurrence d’association entre les

même occurrence d’entité

Réda DEHAK 80

Diagramme E/A

Employe Service

ssn nom prénom

sno budgetsnom

dirige

depuis

Chef de Est dirigé par

E1

E2

…

En

S1

S2

…

Snfaux

Réda DEHAK 81

Diagramme E/A

musicien

orchestre

instrumentEngagement

date

est engagé est joué

engage

M1

M2

O1

O2

I1

I2

I3

I4

faux

Réda DEHAK 82

Plan




Réda DEHAK 83

Cardinalité

• Exprime le nombre minimum et le nombre maximum de participations de chaque occurrence d’entité à une association. (min, max)

Employe ServicedirigeChef de Est dirigé par

E1

E2

E3

E4

S1

S2

S3

S4

(0,n) (1,1)

Réda DEHAK 84

Cardinalité

• Exprime le nombre minimum et le nombre maximum de participations de chaque occurrence d’entité à une association. (min, max)– Min = 0 : toute occurrence de Ei peut exister indépendamment

de A; Participation partielle de Ei à A.– Min = 1 : Aucune occurrence de Ei ne peut exister

indépendamment de A; Participation totale de Ei à A.– Max = 1 : Toute occurrence de Ei assume au plus une fois le

rôle roi.– Max = k>1 : Toute occurrence de Ei assume au plus k fois le

rôle roi.– Max = n : Toute occurrence de Ei peut assumer un nombre

non limité de fois le rôle roi.

Réda DEHAK 85

Exemples

Employe Service

ssn nom prénom sno budgetsnom

dirige

depuis

Chef de Est dirigé par

(0,1) (1,1)

Client Produit

ssn nom prénom nprod prixpnom

CDE

date

commande Est commandé par

(1,n) (0,n)

qte

Réda DEHAK 86

Diagramme E/A

produit

nprod nom volume

composeest composé

est composant

0,n

0,n

Réda DEHAK 87

Diagramme E/A

personne

nss nom prenom

parentsest père ou mère de

Fils, fille

0,n

2,2

Réda DEHAK 88

Exemple






5. Les auteurs sont connus par leur nom, leur prénom, leur adresseet leur date de naissance.

Réda DEHAK 89

Diagramme E/A

ARTICLETitre

Résumé

NUMERON°

Date

AUTEURNom

Prénom

Adresse

Date de naissance

EDITEURNom Ed

Adresse

JOURNALNom J

EDITEUREN CHEF

Nom

Prénom

EDITER(1,n) (1,1)

SORTIE

PARUTIONRÉDACTION

DIRIGE

(1,n)

(1,1)

(0,n)

(1,n)(1,n)

(1,1)

(1,1)

(1,1)

Réda DEHAK 90

Plan




Réda DEHAK 91

Entité faible

• Ne peut pas être identifiée que par rapport à une autre entité, dite dominante, à laquelle elle se refère. Son identificateur est formé d’un identificateur partiel augmenté de l’identificateur de l’entité dominante.

• Exemple :

ChienPersonne Propriétaire

nom prénom adresse nom

(1,1)(0,N)

La cardinalité du role de l’entité faible au sein de l’association identifiante est (1,1)

Réda DEHAK 92

Diagramme E/A

ARTICLETitre

Résumé

NUMERON°

Date

AUTEURNom

Prénom

Adresse

Date de naissance

EDITEURNom Ed

Adresse

JOURNALNom J

EDITEUREN CHEF

Nom

Prénom

EDITER(1,n) (1,1)

SORTIE

PARUTIONRÉDACTION

DIRIGE

(1,n)

(1,1)

(0,n)

(1,n)(1,n)

(1,1)

(1,1)

(1,1)

Réda DEHAK 93

Min,Max

Diagramme entité association

EA

Entité

Entitéfaible

Association

Association identifiante

Attribut

Attribut clé

Attribut multivalué

Attribut composé

Cardinalité

Attribut clé partielle

Réda DEHAK 94

Plan




Réda DEHAK 95

Spécialisation

• Une classe d’entité E1 est une spécialisation d’une autre classe d’entités E2 si E2 a les mêmes propriétés que E2 ou plus.

E1 IS-A E2

• Buts:– Ajouter des attributs spécifiques à une sous classe.– Pour identifier les entités qui participent à une

association.

Employé

Cadre

isa

Réda DEHAK 96

Exemple

Employé

Ingénieur Secrétaire Vendeur

isa

nom

N°

Adresse

Salaire

Projet Bureau Bureau SpécialitéRégion Voiture

Réda DEHAK 97

Plan




Réda DEHAK 98

Agrégation

• Est utilisée quand on veut faire participer une association dans une autre.

Projet Service

nproj pdebut pbudget sno budgetsnom

sponsors

depuis

sponsorisé par sponsorise

1,n 0,n

Employé

ssn nom prénom

participeJusqu’a0,n

Réda DEHAK 99

Agrégation

• Est utilisée quand on veut faire participer une association dans une autre.

• Permet d’utiliser une association comme une entité.

Réda DEHAK 100

Plan




Réda DEHAK 101

Contrainte d’intégrité

Définition :Une contrainte d’intégrité (C.I.) est une propriété non représentée par les concepts de base du modèle E/A que doivent satisfaire les données appartenant à la base de données.

But :Spécifier les propriétés du monde réel non exprimable avec le modèle E/A.

Deux types de C.I. :1. C.I. statique2. C.I. dynamique

Réda DEHAK 102

Contrainte d’intégrité statique

Une propriété qui doit être vérifiée à tout moment.

Exemples :• Un auteur doit écrire au moins un article

(cardinalité).• La date de mariage d’une personne > sa date de

naissance.

Réda DEHAK 103

C.I. statiques (déjà vues)

1. Contrainte d’identification : (obligatoire)Toute entité ou association doit avoir une clé (sous ensemble minimal d’attributs), elle permet de déterminer de manière unique chaque occurrence de ce type.

2. Contrainte de cardinalité : (obligatoire)Définit le nombre minimum et le nombre maximum de participations de chaque occurrence d’entité àune association.

Réda DEHAK 104

3. Attribut obligatoire et attribut facultatif : (obligatoire)Un attribut facultatif ne prend une valeur que pour certaine occurrence de l’entité ou de l’association.

sexe

C.I. statiques obligatoires (2)

Personne

NSS nom prénom

adresse

nom jeune fille

Tous les attributs formant une clé sont obligatoires

Réda DEHAK 105

Contrainte d’intégrité dynamique

Une propriété que doit respecter tout changement d’état de la base de données : définit les séquences possibles des changements d’état de la BD

Exemples :• Le salaire d’un employé ne peut que croître.• Le changement d’état civil d’une personne doit

respecter le graphe de transition suivant :

célibataire mariédivorcé

veuf

Réda DEHAK 106

Exercice : Personnel

On veut représenter le personnel d'une entreprise et son affectation. L'entreprise est organisée en services auxquels est affecté le personnel. Chaque service est décrit par son nom, son chef (qui est nécessairement un cadre de l'entreprise) et la liste de ses locaux. Le personnel est réparti en trois catégories, les administratifs, les techniciens et les cadres. Tous possèdent un numéro d'employé, un nom, un prénom, une adresse, une identification bancaire (nom banque, nom agence, numéro de compte), un salaire et sont rattachés à un service. Chaque catégorie possède en outre des renseignements qui lui sont propres:

– pour un administratif ou un technicien, le prix de l'heure supplémentaire;

– pour un technicien, les machines dont il est responsable;– pour un administratif, le(s) cadre(s) pour le(s)quel(s) il travaille;– pour un cadre, son bureau, son numéro de poste téléphonique et l'(les)

administratif(s) (s'il en existe) qui lui est (sont) attaché(s).

Réda DEHAK 107

Plan




Réda DEHAK 108

Validation d'un schéma EA

• Syntaxique: respect des règles du modèle• Par confrontation aux dépendances:

– règles de normalisation• Par jeu d'essai• Complétude par rapport aux traitements• Par les utilisateurs

Règles à connaître et à appliquer !!!

Réda DEHAK 109

Validation du schéma E/A

1. Vérifier la complétude du schéma.

2. Vérifier la cohérence du schéma (Absence de contradictions).

3. Mise sous forme canonique du schéma (la forme canonique possède des propriétés très intéressantes pour les bases de données).

Réda DEHAK 110

1. Règles de complétude

• Chaque classe d’objets (entité, association, attribut, …) possède toutes les propriétés requise par le modèle E/A :1. Entité :

• Nom : Auteur• Définition : « un auteur est une personne qui a écrit au moins un article paru

dans un journal qui nous intéresse »• Liste d’attributs : nom_auteur, prénom_auteur, adresse_auteur• Au moins une clé : (nom_auteur, prénom_auteur)

2. Association• Nom : Ecriture• Définition : « l’écriture associe l’auteur à(aux) l’article(s) qu’il a écrit(s) »• Liste d’entité qui participent à l’association : Auteur, Article• Les rôles et leur cardinalité : (1,N) écrit: Auteur, (1,1) est écrit par :Article• La liste des attributs :

Réda DEHAK 111

1. Règles de complétude (2)

• Chaque classe d’objets (entité, association, attribut, …) possède toutes les propriétés requise par le modèle E/A :3. Attribut :

• Nom : adresse auteur• Définition : « nom de la ville dans laquelle réside l’auteur »• Une structure (atomique ou composé, monovalué ou multivalué) : atomique

et monovalué• Un domaine de définition : chaîne de caractères• Attribut obligatoire ou facultatif : facultatif

4. C.I. :• Nom : C.I. existence d’un mariage• Les éléments que fait intervenir la C.I. : Association mariage, attributs âge et

sexe de l’entité personne• Assertion (expression de la C.I.) : Une occurrence de l’association mariage

ne peut exister entre deux personnes p1 et p2 que si âgep1, âgep2 ≥ 18 et sexep1 ≠ sexep2

Réda DEHAK 112





Réda DEHAK 113

2. Cohérence du schéma

• Pas d’approche systématique.

étudiant

spécialité

cours

Inscritption

suivre

organisation

Est inscrit (0,N)

suit (1,N)

Avec la contrainte, « un étudiant ne peut pas suivre des cours que s’il est inscrit à une spécialité »

suit (0,N)

Réda DEHAK 114





Réda DEHAK 115

3. Mise sous forme canonique

• Production d’un schéma aussi significatif que possible.

• Production d’un schéma stable (limite les besoins de restructuration de la base lors de l’introduisant de nouveaux types (entités ou associations).

• Éviter les anomalies de mise à jour de la base.Objectifs :1. Élimination ou contrôle de la redondance.2. Élimination des ambiguïtés

Réda DEHAK 116


a) Unicité des noms, absence d’homonymes

b) Absence de synonymes

c) La clé doit être minimale

d) Mise en évidence des attributs dérivables

e) Élimination de structures redondantes

f) Désagrégation d’une entité

g) TA ou TE

h) Validation des attributs d’un TA

Réda DEHAK 117

a) Unicité des noms absence d’homonymes

• Chaque objet du schéma (entité, association, attribut, rôle et C.I.) reçoit un nom unique.La présence d’homonymes :

On a attribué le même nom à deux objets sémantiques différents ⇒ Compléter ou changer le nom.On a modélisé deux fois le même objet sémantique ⇒éliminer un des objets et restructurer le schéma.

On tolère la présence d’homonymes pour les associations ISA

Réda DEHAK 118


• Deux objets sémantiquement équivalents se retrouvent dans le schéma sous des noms différents ⇒ éliminer un des objets et restructurer le schéma.

Réda DEHAK 119

• Si la clé d’une entité ou d’une association est constituéd’un groupe d’attributs et/ou rôles, alors il n’existe pas au sein de ce groupe un sous-groupe qui forme une clé.

Exemple :

cours

prénom


Etudiant

nom

nss

spécialité

Réda DEHAK 120

Règle : dans un TE valide, tous les attributs directs (simples et complexes) dépendent uniquement de chaque identifiant entier du TE (TA).

n°carte, nom, prénoms, date naissance et adresses sont les attributs directs d’Etudiant, qui a pour identifiant n°carte

Etudiant

Nss nom prénoms date naissance adresses

jour mois année no rue ville code postal


Réda DEHAK 121

Exemples incorrectsLa règle est contredite si un attribut dépend d'une partiede l'identifiant ou d'un autre attribut non identifiant.

No-carte nom-section directeur section nom étudiant

Etudiant


Etudiantmauvais

mauvais

Réda DEHAK 122

Normalisation Processus de modification d'un schéma qui conduit à obtenir un schéma offrant les propriétés désirées.

Correct !No-carte section nom étudiant

nom nom directeur

Etudiant

Etudiant


mauvais

Réda DEHAK 123

Validation / attributs complexes

Règle : Un attribut du ième niveau peut seulement dépendre d'une combinaison d'attributs du même niveau et de niveaux supérieurs contigus.

nomLab directeur chercheurs

nomC adresse dateentrée %temps projets

nomP budget description

ligne montant

Laboratoire

Réda DEHAK 124

Dépendances entre TE

• Si tout projet n'est fait que par un seul labo, le schéma est incorrect

Labo ChercheurEmploie

Projetmauvais

Règle : un TA n-aire (n>2) avec une dépendance entre ses TE doit être décomposé

1:n

0:10:n

Réda DEHAK 125

Normalisation du TA: incorrect

• Mauvaise décomposition du TA ternaire incorrect en deux TA binaires

• Cette décomposition n'est pas correcte car elle induit une perte d'information – on ne sait plus sur quel projet travaille un chercheur !!

ChercheurEmploie

Projet

Conduit

Labo

mauvais

1:1

0:n

0:n 0:1

Réda DEHAK 126

Normalisation du TA: correct

Décomposition du TA ternaire incorrect en deux TA binaires sans perte d'information:

un chercheur est employé par le labo qui conduit le projet sur lequel le chercheur travaille

ChercheurEmploieProjet

Conduit

Labo

1:1

0:n

0:11:n

Réda DEHAK 127








g) TA ou TE


Réda DEHAK 128


• Un attribut est dérivable si sa valeur peut être calculée à partir de la valeur d’autres attributs.Exemples : total, moyenne, écart-type, …

⇒ Exprimer la règle de calcul sous forme d’une C.I.

Réda DEHAK 129


1. Attribut redondant avec une association:

numéro journalSortie

Nom de journal

1,1 0,Nest

sorti par

sort

Nom

Réda DEHAK 130


2. Association sémantiquement redondante avec d’autres associations :

Auteur LivreEcriture

Editer

Editeur

publication

est publié chez

publie

Réda DEHAK 131


3. Attention :

Personne entreprisetravaille

localisation

pays

Habitation

habite

héberge

Réda DEHAK 132

cours

prénom

Etudiant

nom

nss

spécialité

Nom cours

Note cours


1. Une entité est désagrégeable losqu’au moins un de ses attributs exprime un objet de la réalité perçue représentable sous la forme d’une association ou d’une entité.

prénom

Etudiant

nom

nss

spécialité Nom coursNote cours

CoursCours suivi

L’existence d’un attribut répétitif ou composé est souvent l’indice d’une imbrication non contrôlée de

structure.

Réda DEHAK 133

prénom

personne

nom localité

Code postal


2. Lorsqu’il y a d’autres Dépendances entre attributs que celles entre la clé et les attributs non clé.

personne

nom prénom

localité

Code postal

localitéLocalisation1,1 0,N

Est localisée localise

Avec la Dépendance : code postal localité

Réda DEHAK 134


3. Lorsqu’il y a des attributs prenant la valeur « inéxistante » en fonction de la valeur des autres attributs.

Si l’ouvrage est de type livre :

• ISSN et périodicité prennent une valeur inexistante.

Si l’ouvrage est de type revue :

• ISBN, auteur, n°édition, hauteur et largeur prennent une valeur inexistante.

ouvrage

titre auteurN° édition

dimensiontype

ISBN ISSN périodicité

hauteur

largeur

Réda DEHAK 135


ouvrage

auteur

périodicité

livre

titre

N° édition

dimension

ISBN

ISSNhauteur largeur

périodique

ISA ISA

Réda DEHAK 136








g) TA ou TE


Réda DEHAK 137

g) TA ou TE : (TA->TE)

nom adresse numéro typeéchéance No-contrat

Personne VoitureAssure0:n 1:1

numéro type

échéancenom adresse No-contrat

Personne ContratSouscrit

ObjetVoiture

1:1

1:1

0:n

1:1

Réda DEHAK 138


Employe Service

nss nom prenom sno budgetsnom

travailler

depuis

1,n 0,n

Jusqu’a

mauvais

Réda DEHAK 139


Employe Service


travailler

depuis

1,n 0,n

Jusqu’a

durée

Réda DEHAK 140

g) TA ou aggrégation

Projet Service


sponsors

depuis


1,n 0,n

Employe

ssn nom prénom

dirigeJusqu’a0,n

1,11,1

Réda DEHAK 141

g) TA ou aggrégation

Projet Service


sponsors

depuis


1,n 0,n

Employe

ssn nom prénom

Jusqu’a

0,n

Réda DEHAK 142


Règle : dans un TA sans dépendance entre les TEsliés, les attributs du TA dépendent de tous les TE liés par ce TA.

(No-carte,No-Mat) moyenne, notes

Etudiant Matière

No-carte nom moyenne notes No-Mat coefficient

Evaluation0,n 0,n

Réda DEHAK 143


Si Coef = fonction du nombre d'heures assuréespar l'enseignant dans cecours.

Alors Coef ne dépend pas d’Etudiant

Etudiant EnseignantContrôle

Nom Cours

Cours

No-carte notes coef Nom

mauvais

0:n0:n

0:n

Etudiant Enseignant

No-carte notes Nom

Contrôle

Nom Cours

Cours Assure

coefcorrect

0:n0:n

0:n

1:n1:n

Réda DEHAK 144

i) Remplacement d’un attribut par un TA

Employé Service

No-emp …. no-service no étage nom

mauvais

Règle de remplacement

No-emp …. no étage nom

Employé ServiceTravaille 0:n1:10:1

Réda DEHAK 145

Élimination des TE inutilesUn TE est inutile s'il ne présente d'intérêt pour aucun traitement de l'application

Si il n'existe pas pas de requête portant directement sur les services, Services est transformé en attribut.

No-emp …. no étage nom

Employé ServiceTravaille

No-emp …. service

Employé

no étage nom

Réda DEHAK 146

Élimination des TE inutilesUn TE est inutile s'il ne présente d'intérêt pour aucun traitement de l'application

Cours SalleA lieu dans

Cours

Nom Type Num_salle

Nom Type Num

Un seul attribut


Réda DEHAK 149

Plan

• Le modèle relationnel.

• Contrainte du modèle relationnel.

• Passage du modèle E/A vers le modèle relationnel.

• Algèbre relationnelle

Réda DEHAK 150

Le modèle relationnel

• modèle de niveau logique, très simple• défini par Ted Codd (IBM lab) en 1970; prix Turing en

1986.« A Relationnal Model for Large Shared Data Banks », Communications of the ACM, Juin 1970.

• aujourd'hui utilisé par beaucoup de SGBD commerciaux

(Oracle, Informix, DB2, Ingres, Sybase, dBase, Access …) et GIS

• modèle à deux concepts:relation (table)

attribut (colonne)

Réda DEHAK 151

A2

C1

A1

Groupe

20/09/80Titi43587

23/04/80Tata24323

25/01/81Toto12546

Date_naissNomuid

Concepts

ETUDIANT(Uid, Nom, Date_naiss, Groupe)

Attributs

Tuple ou occurence

Nom de la relation Nom des attributs

Schéma GroupeDate_naissNomUid

ETUDIANT

Population

Réda DEHAK 152

Schéma relationnel

• Base de données relationnelle : Un ensemble de relations.

• Schéma d’une BD relationnelle : Un ensemble de schémas de relations.

• Schéma d’une Relation : spécifie le nom de la relation ainsi que le nom et le type de chaque attribut.

R(A1:D1, A2:D2, …, An:Dn)– ETUDIANT(Uid:integer, Nom:string, Date_naiss:date,

Groupe:char(2))ou– ETUDIANT(Uid, Nom, Date_naiss, Groupe)

Réda DEHAK 153

Définitions

Exemples de la tableExtension

Définition de la tableSchéma de la relation (Intension)

Valeur de la colonneDomaine

LigneTuple

ColonneAttribut

TableRelation

Définition (Terme utilisé)Concepts

Réda DEHAK 154

Plan

• Le modèle relationnel.

• Contrainte du modèle relationnel.

• Passage du modèle E/A vers le modèle relationnel.

• Algèbre relationnelle

Réda DEHAK 155

Règles de structuration

• attributs: simples et mono-valués (domaine de valeurs atomiques)

• structure régulière

XXXX

xx

XXXX

Interdit

Réda DEHAK 156

Valeurs nulles

• Un attribut peut ne pas être valué pour un tuple : on dit alors qu'il a une valeur nulle– exemple: on ne connaît pas la date de naissance de Tata

A2

C1

A1

Groupe

20/09/80Titi43587

NULLTata24323

25/01/81Toto12546

Date_naissNomUid

Réda DEHAK 157

Règle d'identification

Toute relation possède un identifiant (clé)Un ensemble d’attributs C est une clé d’une relation ssi :

1. Deux tuples distincts ne peuvent pas avoir les mêmes valeurs pour les attributs de la clé.

2. La propriété 1 n’est pas vraie pour un sous ensemble d’attributs E de C.

C1NULLTata24323

A2

C1

A1

Groupe

20/09/80Titi43587

20/09/80Titi12528

25/01/81Toto12546

Date_naissNomUid

Réda DEHAK 158

Règle d'identification

• Si la propriété 2 n’est pas vérifiée, l’ensemble C est une super clé (non minimale).

1. Clé primaire : une clé de la relation.2. Clé candidate : clé non primaire.

C123/07/90Tata24323

A2

C1

A1

Groupe

22/09/80Titi43587

20/09/80Titi12528

25/01/81Toto12546

Date_naissNomUid

• L’identifiant n’admet pas de valeurs nulles

Réda DEHAK 159

Identifiant externe(référence)

• Cours (NomC, Horaire, Prof)

Olivier14h – 17hMathAkim10h – 13hCompilRéda8h30 – 12h45BDDProfHoraireNomC

AlgoCompilBDD

NomC

243232432312546Uid

?

• Suit(Uid, NomC)Suit.NomC est un attribut clé

étrangère

Réda DEHAK 160

Exemple

ETUDIANT(Uid, Login, Date_naiss, Groupe)

Groupe(Groupe, Nom_resp)

Uid : est la clé primaire de la relation ETUDIANT.

Login : est une clé candidate pour la relation

ETUDIANT

{Uid, Login} : est une super clé de la relation

ETUDIANT

ETUDIANT.Groupe : est une clé étrangère.

Réda DEHAK 161

Caractéristiques d’une Relation

• Basées sur la théorie des ensembles :Pas d’ordre entre les attributsPas d’ordre entre les tuples

Les résultats de requêtes peuvent être triésPas de tuples dupliqués

Les SGBDs autorisent les doubles

• Les valeurs d’attributs sont atomiques.• Degré ou arité :

Nombre d’attributs• Cardinalité :

Nombre de tuples

Réda DEHAK 162

Exemple

• ETUDIANT(Uid: integer, Nom: string, Date_naiss: date, Groupe: char(2))

⊆ (integer x string x date x string)

A2

C1

A1

Groupe

20/09/80Titi43587

NULLTata24323

25/01/81Toto12546

Date_naissNomUid

• Cardinalité (Nombre de tuples) = 3• Arité, degré (Nombre d’attributs) = 4

Réda DEHAK 163

Autres types de contraintes

• Contrainte d’intégrité sémantique :– Elles sont en relation avec la sémantique de l’application et on

ne peut pas les exprimer avec le modèle. Exemple : La somme des heures de cours suivis par un étudiant ne dépasse pas 20 heures

• Préciser dans un langage spécifique.• SQL99 propose les triggers et les assertions pour

vérifier certaines contraintes.

Réda DEHAK 164

Plan

• Le modèle relationnel.• Contrainte du modèle relationnel.

• Passage du modèle E/A vers le modèle relationnel :– Transformer un type d’entité.– Transformer les attributs multivalués.– Transformer une entité faible.– Transformer une association avec une cardinalité 1:1.– Transformer une association avec sans cardinalité 1:1.– Transformer une spécialisation.

Réda DEHAK 165

Modèle E/A – Modèle RelationnelEntité

Employe

nss nom prénom

EMPLOYE(NSS, Nom, NomJF, Prénom)

nomJF

• Étape 1 :– Pour chaque type d’entités E du modèle E/A, créer une relation R

contenant tous les attributs mono-valué de l’entité E.– Choisir une clé de l’entité E comme identifiant de la relation R.

Réda DEHAK 166

Modèle E/A – Modèle RelationnelEntité

Employe

nss nom prénom

EMPLOYE(NSS, Nom, Prénom, num, rue, ville)

adresse

Pour chaque composante d’un attribut composé de l’entitéE, créer un attribut dans la relation R.

num

rue

ville

Réda DEHAK 167

Modèle E/A – Modèle RelationnelAttributs multivalués

Etudiant

nss nom prénom

ETUDIANT(NSS, Nom, Prénom)

COURS(NSS, COURS)

DIPLOMES(NSS, DIPLOMES)

cours

• Pour chaque attribut multivalué, créer une relation R contenant la clé primaire de l’entité et l’attribut en question.

• La clé primaire de cette relation correspond à tous les attributs de cette relation.

diplômes

Réda DEHAK 168

Modèle E/A – Modèle Relationnel Entité faible

ChienPersonne Propriétaire

nom prénom adresse nom

0,N

age

PERSONNE(NOM, PRENOM, ADRESSE:string)

CHIEN(NOMP, PRENOMP, NOM, AGE:integer)

• Créer une relation R pour chaque entité faible EF. Tous les attributs de l’entitéEF feront partie de la relation R.

• Rajouter en tant que clé étrangère la clé primaire de la relation correspondant à(aux) l’entité(s) qui permet(ent) d’identifier l’entité EF.

• La clé primaire de R est composée de cette clé étrangère et de l’attribut clépartielle de l’entité faible.

Réda DEHAK 169

Modèle E/A – Modèle Relationnelassociation

Employe Service

nss nom prenom sno snom

travailler1,1 0,n

poste

budget

EMPLOYE(NSS, NOM, prenom, sno, poste)

SERVICE(SNO, SNOM, BUDGET)

Clé étrangère

• Pour chaque type d’association avec une ou plusieurs cardinalités 1:1, rajouter les clés primaires des autres entités dans le schéma de la relation R de l’entité qui joue le rôle de la cardinalité 1:1.

• S’il y a des attributs pour cette association, ils seront rajoutés au schéma R.

Réda DEHAK 170


• S’il n’existe pas de cardinalité 1:1 ou 0:1, créer une relation R contenant toutes les clés primaires des entités qui participent à cette association.

• Rajouter les attributs de l’association dans R.• La clé est composée de toutes les clés étrangères.

Employe Service


travailler

depuis

1,n 0,n

Jusqu’a

durée

0,n

EMPLOYE(NSS, NOM, PRENOM)


DUREE(DEPUIS, JUSQUA)

TRAVAILLER(NSS, SNO, DEPUIS, JUSQUA, poste)

poste

Réda DEHAK 171


produit

nprod nom volume

composeest composé

est composant0,n

0,n

PRODUIT(NPROD, NOM, VOLUME)

COMPOSE(COMPOSE, COMPOSANT)

Réda DEHAK 172

0,n

sponsorisé par

Modèle E/A – Modèle Relationnel Agrégation

Projet Service


sponsors

depuis

sponsorise

1,n 0,n

Employe

ssn nom prénom

travaillerJusqu’a 0,n

PROJET(NPROJ, PDEBUT, PBUDGET)


EMPLOYE(SSN, NOM, PRENOM)

SPONSORS(NPROJ, SNO, DEPUIS)

TRAVAILLER(SSN, NPROJ, SNO, JUSQUA)

Réda DEHAK 173

Modèle E/A – Modèle Relationnel Agrégation

Projet Service


sponsors

depuis


1,n 0,n

Employe

ssn nom prénom

dirigeJusqu’a 0,n

0,1

PROJET(NPROJ, PDEBUT, PBUDGET)


EMPLOYE(SSN, NOM, PRENOM)

SPONSORS(NPROJ, SNO, DEPUIS, SSN, JUSQUA)

Réda DEHAK 174

• Différentes approches :a) Cas général : (E/A)

EMPLOYE(N, NOM, ADRESSE, SALAIRE)INGENIEUR(N, PROJET, BUREAU)SECRETAIRE(N, BUREAU, SPECIALITE)VENDEUR(N, REGION, VOITURE)

Modèle E/A – Modèle Relationnel Spécialisation

Employé


isa

nomN°

Adresse

Salaire

Projet Bureau Bureau Spécialité Région Voiture

Réda DEHAK 175

• Différentes approches :b) (OO)

EMPLOYE(N, NOM, ADRESSE, SALAIRE)INGENIEUR(N, NOM, ADRESSE, SALAIRE, PROJET, BUREAU)SECRETAIRE(N, NOM, ADRESSE, SALAIRE, BUREAU, SPECIALITE)VENDEUR(N, NOM, ADRESSE, SALAIRE, REGION, VOITURE)

Modèle E/A – Modèle Relationnel e) Spécialisation

Employé

Ingénieur Secrétaire

Vendeur

isa

nomN°

Adresse

Salaire

Projet Bureau Bureau Spécialité

Région Voiture

Réda DEHAK 176

• Différentes approches :c) Avec des NULL

EMPLOYE(N, NOM, ADRESSE, SALAIRE, PROJET, BUREAU,BUREAU, SPECIALITE, REGION, VOITURE)

Modèle E/A – Modèle Relationnel e) Spécialisation

Employé


isa

nomN°

Adresse

Salaire

Projet Bureau Bureau Spécialité Région Voiture

Réda DEHAK 177

Exemple

• Voir Exemple avion avec sybase powerAMC


Réda DEHAK 179

Langages & BDD

• Le langage de manipulation :Insertion de valeurs.Suppression de valeurs.MAJ de valeurs.

• Le langage d’interrogation :Recherche des données obéissants à un certain critère.Des opérations de calcul.Langage déclaratif.

Réda DEHAK 180

Classification

• Deux grandes classes :1. Langage algébrique :

Algèbre relationnelle.Opérateurs relationnels.Définit les opérations : utile pour la définition des plans d’exécution.

2. Langage prédicatif :Logique des prédicats.Langage déclaratif : on définit les données recherchées et non la manière de les obtenir.

Réda DEHAK 181

Algèbre relationnelle

• Système Mathématique :– Opérandes :

• Des instances de relation.• Des Instances de relation sont calculées à partir des opérandes.

– Opérateurs :• Opérateurs relationnels unaires.• Opérateurs relationnels binaires.

Opérateur<paramètres>(Opérandes) RésultatInstances de relation Instance de relation

Réda DEHAK 182

Opérateurs de l’algèbre relationnelle

• Opérateurs de base :– Sélection : ( σ )– Projection : ( π )– Produit cartésien : ( X )– Renommage : ( ρ )– Union : ( U )– Différence : ( - )

• Opérateurs composés :– Jointure : ( )– Intersection : ( ∩ )– Division : ( / )

Réda DEHAK 183

Sélection

Opérateur unaire.Sélection des tuples (lignes) d’une instance qui vérifient une condition (C).

R1 := Select( R2, C )R1 := σ<C>( R2 )

Schéma( R1 ) = Schéma( R2 )Le résultat peut être l’opérande d’un autre opérateur.

C

R2

R1

Réda DEHAK 184

Exemples

R := σ< (NUM > 1400) >(CLIENT)

RENNESRenault1224

LILLEMaître3425

LYONBaudoin2543

NICEDupont1432

PARISDupont1324

ADRESSENOMNUMCLIENT

ADRESSENOMNUMCLIENT

LILLEMaître3425

LYONBaudoin2543

NICEDupont1432

Réda DEHAK 185

Projection

Opérateur unaire.Sélection des attributs (colonnes) d’une instance.

R1 := PROJ( R2, L )R1 := π<L>( R2 )

L est une liste d’attributs de R2.Le schéma de R1 contient uniquement les attributs de R2qui sont spécifiés dans L.Pas de duplication des tuples dans R1.

N’est pas vérifié par les SGBDs

L

R2

R1

Réda DEHAK 186

Exemples

R := π< NOM, ADRESSE >(CLIENT)

RENNESRenault1224

LILLEMaître3425

LYONBaudoin2543

NICEDupont1432

PARISDupont1324

ADRESSENOMNUMCLIENT

RENNESRenault

LILLEMaître

LYONBaudoin

NICEDupont

PARISDupont

ADRESSENOMCLIENT

Réda DEHAK 187

Exemples

R := π< NOM >(CLIENT)

RENNESRenault1224

LILLEMaître3425

LYONBaudoin2543

NICEDupont1432

PARISDupont1324

ADRESSENOMNUMCLIENT

Renault

Maître

Baudoin

Dupont

NOMCLIENT

Réda DEHAK 188

Produit cartésien

Opérateur binaire.Chaque tuple de R2 est combiné avec chaque tuple de R3 pour former un tuple de R1.

R1 := PRODUCT(R2, R3)R1 := R2 x R3

Le schéma de R1 contient tous les attributs de R2et R3 :

schéma(R1) = schéma(R2) ∪ schéma(R3)

x

R2

R1

R3

Réda DEHAK 189

Exemples

R := CLT x PROD

RENNESRenault1224LILLEMaître3425LYONBaudoin2543

ADRESSENOMNUMCLT

bleurouge

Couleur

Tour-vispince

NOM

142123

NUMPROD

rougepince123RENNESRenault1224

bleuTour-vis142LILLEMaître3425

bleuTour-vis142LYONBaudoin2543

bleu

rouge

rouge

Couleur

Tour-vis

pince

pince

NOM

142

123

123

(NUM)

RENNESRenault1224

LILLEMaître3425

LYONBaudoin2543

ADRESSENOM(NUM)R

Réda DEHAK 190

Renommage


ADRESSENOMNUMCLT

bleurouge

Couleur

Tour-vispince

NOM

142123

NUMPROD




bleu

rouge

rouge

Couleur

Tour-vis

pince

pince

NOM

142

123

123

NUMPROD

RENNESRenault1224

LILLEMaître3425

LYONBaudoin2543

ADRESSENOMNUMCLTR

R:= ρ<NUM NUMCLT>(CLT) x ρ<NUM NUMPROD>(PROD)

Réda DEHAK 191

Renommage


ADRESSENOMNUMCLT

bleurouge

Couleur

Tour-vispince

NOM

142123

NUMPROD




bleu

rouge

rouge

Couleur

Tour-vis

pince

pince

NOM

142

123

123

NUMPROD

RENNESRenault1224

LILLEMaître3425

LYONBaudoin2543

ADRESSENOMNUMCLTR

R := RENAME(CLT, NUM NUMCLT) x RENAME(PROD, NUM NUMPROD)

Réda DEHAK 192

Union

Opérateur binaire.R1 contient tous les tuples de R2 et R3.

R1 := UNION(R2, R3)R1 := R2 ∪ R3

Condition : R2 et R3 doivent être compatibleMême nombre d’attributs.Même domaine pour les attributs en relation.

schéma(R1) = schéma(R2)

∪

R2

R1

R3

Réda DEHAK 193

Exemples

R := PROD-R ∪ PROD-V

rougerouge

Couleur

Tour-vispince

NOM

142123

NUMPROD-R

vertmarteau132vert

vert

Couleur

Tour-vis

pince

DESIGN

144

124

NPROD-V

vertpince124vertmarteau132

rougeTour-vis142

vert

rouge

Couleur

Tour-vis

pince

NOM

144

123

NUMR

Réda DEHAK 194

Différence

Opérateur binaire.R1 contient tous les tuples de R2 qui ne figurent pas dans R3.

R1 := DIFF(R2, R3)R1 := R2 - R3

Condition : R2 et R3 doivent être compatible– Même nombre d’attributs.– Même domaine pour les attributs en relation.

schéma(R1) =schéma(R2)

-

R2

R1

R3

Réda DEHAK 195

Exemples

R := PROD_1 – PROD_2

rougerouge

Couleur

Tour-vispince

NOM

142123

NUMPROD_1

vertmarteau132vert

rouge

Couleur

Tour-vis

pince

DESIGN

144

123

NPROD_2

rougeTour-vis142

CouleurNOMNUMR

Réda DEHAK 196

Opérateurs de l’algèbre relationnelle

• Opérateurs composés :– Jointure : ( )– Intersection : ( ∩ )– Division : ( / )

Réda DEHAK 197

• Theta-jointure :R1 := join(R2, R3, C)

R1 := R2 R3

R1 = σ <C>(R2 x R3)

• Equi-jointure :R1 := join(R2, R3, C)

R1 := R2 R3

R1 = π<schema(R2) ∪ shema(R3)> (σ <C>(R2 x R3))C représente un prédicat qui formé à partir des deux opérateurs =, et «and» .

• Jointure Naturelle :R1 := join(R2, R3)

R1 := R2 R3

R1 = π<schema(R2) ∪ shema(R3)> (σ <scheam(R2)∩ schema(R3)>(R2 x R3))

Jointure

C

C

C

R2

R1

R3

Réda DEHAK 198

Exemples : Equi-jointure

R := PROD CMD

rougerouge

Couleur

Tour-vispince

NOM

142123

NPRODNPRODPROD

251423rougeTour-vis142101423rougepince123

20

QTE

1420

NCLT

rougeTour-vis142

CouleurNOMNPRODR

25142142320145143520

10

QTE

142

123

NPROD

1420

1423

NCLTCMD

PROD.NPROD=CMD.NPROD

Réda DEHAK 199

Exemples : Jointure Naturelle

R := PROD CMD

rougerouge

Couleur

Tour-vispince

NOM

142123

NPRODPROD

251423rougeTour-vis142101423rougepince123

20

QTE

1420

NCLT

rougeTour-vis142

CouleurNOMNPRODR

25142142320145143520

10

QTE

142

123

NPROD

1420

1423

NCLTCMD

Réda DEHAK 200

Intersection

Opérateur binaire.R1 contient tous les tuples qui sont présents dans R2 et dans R3.

R1 := INTERSECT(R2, R3)R1 := R2 ∩ R3

Condition : R2 et R3 doivent être compatible– Même nombre d’attributs.– Même domaine pour les attributs en relation.

schéma(R1) = schéma(R2)

∩

R2

R1

R3

Réda DEHAK 201

Exemples

R := PROD-1 ∩ PROD-2

rougerouge

Couleur

Tour-vispince

NOM

142123

NUMPROD-1

vertTour-vis144rouge

rouge

Couleur

Tour-vis

pince

DESIGN

148

123

NPROD-2

rouge

Couleur

pince

NOM

123

NUMR

Réda DEHAK 202

Division

Si on cherche les tuples qui sont en relation avec tousles tuples d’une autre instance.

rougerouge

Couleur

Tour-vispince

NOM

142123

NPRODPROD

25142142320123143520

10

QTE

142

123

NPROD

1420

1423

NCLTCMD

Réda DEHAK 203

Exemple

R := π<NPROD, NCLT>CMD / π<NPROD>(PROD)

1423

NCLTR

rougerouge

Couleur

Tour-vispince

NOM

142123

NPRODPROD

25142142320123143520

10

QTE

142

123

NPROD

1420

1423

NCLTCMD

Réda DEHAK 204

Division

Opérateur binaire.R1 := R2 / R3

R1 := DIV(R2, R3)Schéma(R3) ⊂ Schéma(R2)Schéma(R1) = Schéma(R2) - Schéma(R3)

Chercher les tuples qui ne font pas partie du resultat

Rx := π<schéma(R1)>(R2) x R3

Ry := Rx – R2

R1 := π<schéma(R3)>(R2) - π<schéma(R3)>(Ry)

/

R2

R1

R3

Réda DEHAK 205

Exemples

• Soit les trois tables suivantes :– CLIENT(nclt, nom, age, adresse)– PROD(nprod, design, couleur, volume)– CMD(nclt, nprod, qte, date).

1. La liste des noms de clients qui ont un age > 20.2. La liste des noms de clients ayant commandés le produit numéro 13.3. La liste des noms de clients ayant commandés un produit de couleur

rouge.4. La couleur des produits commandés par monsieur Dupont.5. La liste des noms de clients ayant commandés au moins un produit.6. La liste des noms de clients ayant commandés un produit vert ou rouge.7. La liste des noms de clients ayant commandés un produit vert ou bien

rouge.8. La liste des noms de clients ayant commandés au moins deux produits.9. La liste des clients qui ont un age > 50 et qui n’ont pas commandé un

produit vert.10. La liste des noms de clients qui ont commandé tous nos produits.11. La liste des noms de clients qui ont commandé tous nos types de pince.


Réda DEHAK 207

Plan

1. Récursivité et décidabilité2. Systèmes formels3. Logique des propositions4. Logique du premier ordre.

Réda DEHAK 208

De la philosophie à la logique

1. Logique comme « art de penser » (Aristote)Utilisation des connaissances pour tirer des conclusionsDiscipline littéraire jusque la fin XIX siècle

2. Logique mathématiqueFormalisation des connaissances et du raisonnement.Une conclusion est un théorème à démontrer à partir d’axiomes, en appliquant des règles.

3. Logique et informatiqueIntelligence artificielle Langage LISP, PROLOG, …Méthodes formellesLangages pour bases de données

Réda DEHAK 209

Notions de décidabilité

Fonctions récursivesLes fonctions qu’un programme peut calculer.Les autres fonctions ne peuvent être calculées.

Problèmes décidablesLes problème qu’un programme est susceptible de résoudre.Les autres problèmes ne peuvent être entièrement résolus

Réda DEHAK 210

Fonctions récursives

Soient :– E l’ensembles des entiers 0, 1, 2 etc.– f une fonction partielle de E dans E

f est récursive (on dit aussi calculable) s’il existe un programme P tel que :

– P(n) = f(n) si n est dans l’ensemble de définition de f

– P(n) = ⊥ sinon

Thèse de Church : (non démontrable)Toute les fonctions de E dans E calculables par des algorithmes sont des fonctions récursives

Réda DEHAK 211

Ensembles récursifs

Soit A ⊂ E

• A est récursif ssi la fonction f : E E définie par :– f(n) = 1 si n ∈ A– f(n) = 0 si n ∉ A

est récursive

Il existe un programme qui, pour tout n ∈ E, retourne OUI si n ∈ A ou NON si n ∉ A

Réda DEHAK 212

Prédicat décidable

Soit un prédicat P(x1, x2, …, xn) à n variablesP est décidable (ou récursif) ssi :– { (x1, x2, …, xn) / P(x1, x2, …, xn) est vrai} est récursif

Autrement dit, il existe un programme qui, pour tout (x1, x2, …, xn), retourne– OUI si P(x1, x2, …, xn) est vrai– NON si P(x1, x2, …, xn) est faux

Exemple :– P(n,m) : « n est diviseur de m » est décidable

Réda DEHAK 213

Prédicat semi-décidable

Soit un Prédicat P(x1, x2, …, xn) à n variable

P est semi-décidable s’il existe un programme qui pour tout (x1, x2, …, xn) retourne :– OUI si P(x1, x2, …, xn) est vrai– ⊥ si P(x1, x2, …, xn) est faux

Exemple :P(n) : « n est le numéro d’un programme à une entrée qui, pour la donnée n, s’arrête en un temps fini » est semi-décidable mais pas décidable

Réda DEHAK 214

Plan


Réda DEHAK 215

Théorie des systèmes formels

Cadre général pour étudier de façon rigoureuse les notions d’axiomatique et les mécanismes déductifs

– Les démonstrations et théorèmes deviennent des concept mathématiques objets.

– On en déduit des propriétés générales applicables à tous les systèmes de déduction

Réda DEHAK 216

Système formel

Un système formel S est composé de :1. Un alphabet ΣS

2. FS l’ensemble des formules bien formées de SFS est un sous-ensemble récursif de ΣS

*, l’ensemble de toutes les suites finies d’éléments de ΣS

3. AS l’ensemble des axiomes de S.AS ⊂ FS, AS récursif

4. RS l’ensemble des règles d’inférence de S.Prédicats décidables définis sur FS.

Réda DEHAK 217

Inférence

Une règle d’inférence r(f1, f2, …, fn, g) s’écritf1, f2, …, fn ├─r g

On peut dire alors :– À partir des formules f1, f2, …, fn on peut déduire la formule g

par la règle r– g est une déduction de r à partir des hypothèses f1, f2, …, fn

On appelle théorème de S toute formule t pour laquelle il existe une déduction à partir de AS, c-à-d :

AS ├─r t

Réda DEHAK 218

Exemple de système formel

S est défini par :

1. ΣS = {1, +, =}

2. FS ={1n + 1m = 1p | n,m,p ∈ E –{0} }

3. AS ={ 1 + 1 = 11}

4. RS = { r1, r2 }

1n + 1m = 1p ├─r 1n+1 + 1m = 1p+1

1n + 1m = 1p ├─r 1n + 1m+1 = 1p+1

Réda DEHAK 219


La suite de formules :

1. f1 : 1 + 11 = 112. f2 : 1 + 111 = 111 (application de r1 à f1)3. f3 : 11 + 111 = 1111 (application de r2 à f2)

est une déduction de 11 + 111 = 1111 à partir de la formule 1 + 11 = 11

Réda DEHAK 220


La suite de formules :1. f1 : 1 + 1 = 11 (axiome)2. f2 : 1 + 11 = 111 (application de r2 à f1)3. f3 : 1 + 111 = 1111 (application de r2 à f2)4. f4 : 11 + 111 = 11111 (application de r1 à f3)

est une déduction de 11 + 111 = 11111 à partir d’un axiome

11 + 111 = 11111 est un théorème de S

Réda DEHAK 221

Plan


Réda DEHAK 222

Logique des propositions

Une logique possède :– Une syntaxe qui définit comment construire des formules par

un système formel– Une sémantique qui donne une interprétation des formules

La logique des propositions (ou calcul propositionnel) permet de manipuler des formules composées de propositions qui sont vraies ou fausses

simple, mais peu expressive

Réda DEHAK 223

Calcul propositionnel P0

Un système formel défini par :1. ΣP0 ={p0, p1,…, pn} ∪ {¬ , ⇒ , ( , ) }

Les symboles pi sont appelés variables propositionnelles ou atomes

2. FP0 le plus petit ensemble de formules tel que :• ∀i : pi ∈ FP0

• ∀A ∈ FP0, ∀B ∈ FP0 : ¬A ∈ FP0, ( A ⇒ B )∈ FP0

3. AP0 l’ensemble de toutes les formules de l’une des trois formes (appelées schémas d’axiomes) :

SA1 : A ⇒ (B ⇒ A)SA2 : (A ⇒ ( B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C))SA3 : (¬A ⇒ ¬B) ⇒ (B ⇒ A)

4. RP0 ={m.p} règle du modus ponensA, (A ⇒ B) ├─m.P B

Réda DEHAK 224

Exemple de déduction dans P0

La suite de formules :

1. f1 : (A ⇒ ((B ⇒ A) ⇒ A)) ⇒ ((A ⇒ (B ⇒ A)) ⇒ (A ⇒ A))(SA2)

2. f2 : A ⇒ ((B ⇒ A) ⇒ A) (SA1)3. f3 : (A ⇒ (B ⇒ A)) ⇒ (A ⇒ A) (m.p. f1, f2)4. f4 : A ⇒ (B ⇒ A) (SA1)5. f5 : A ⇒ A (m.p. f3, f4)

est une déduction de (A ⇒ A) à partir de deux axiomes (A ⇒ A) est un théorème de P0

Réda DEHAK 225

Interprétation pour P1

Soit le calcul propositionnel P1 tel que :1. ΣP1 ={p0, p1,…, pn} ∪ {¬ , ⇒ , ∨ , ∧ , ⇔ , ( , ) }2. FP1 le plus petit ensemble de formules tel que :

• ∀i : pi ∈ FP1

• ∀A ∈ FP1, ∀B ∈ FP1 : ¬A ∈ FP1, ( A ⇒ B )∈ FP1 , (A ∧ B)∈ FP1 , ( A ∨ B )∈ FP1 , ( A ⇔ B )∈ FP1

On appelle interprétation de FP1 toute application :I : {p0, p1,…, pn} {V, F}

Une formule est soit vraie soit fausse.

Réda DEHAK 226

Interprétation des formules

Table de vérité : ensemble exhaustive de valeurs de l’interprétation d’une formule dans {V, F}

Tautologie (formule valide)– Vraie pour toute interprétation– « A est une tautologie » est notée ╞═ A

Contradiction (formule inconsistante)– Fausse pour toute interprétation

Formule consistante(satisfiable)– Vraie pour au moins une interprétation

Réda DEHAK 227

Tables de vérité des connecteurs

La signification des connecteurs logiques est définie par les applications de {V, F} dans {V, F} suivante :

VFFVVFF

FFVVVVF

FFVFFFV

VVVVFVV

A⇔BA∧BA∨BA⇒B¬ABA

Réda DEHAK 228

Plan


Réda DEHAK 229

Logique du premier ordre

La logique du premier ordre (ou calcul des prédicats) permet de manipuler des formules dont la vérité dépend de variables, c-a-d de prédicats :

– Généralise le calcul propositionnel– Grande puissance d’expression– Très utilisée en pratique :

• Systèmes experts• Langage PROLOG• BD relationnelles, BD déductives

Réda DEHAK 230

Syntaxe

L’alphabet des symboles suivants :– Des variables : x, y, z, …– Des constantes : a, b, c, …– Des prédicats : P, Q, R, …– Des connecteurs logiques : ¬ , ⇒ , ∨ , ∧– Des fonctions n-aires : f, g, h– Les quantificateurs : ∀ et ∃

Un terme est une variable, une constante ou le résultat de l’application d’une fonction à un terme– Exemple : x, a, f(x) et f(f(x)) sont des termes

Réda DEHAK 231

Syntaxe

Soit T l’ensemble des termes.Les formules FPR : le plus petit ensemble de formules tel que :

• ∀t1, t2, …,tn ∈ T : P(t1, t2, …,tn) ∈ FPR

• ∀A ∈ FPR, ∀B ∈ FPR : ¬A ∈ FPR, ( A ⇒ B )∈ FPR , (A ∧ B)∈ FPR , ( A ∨ B )∈ FPR

• Si x est une variable et A ∈ FPR alors :∀x ( A ) ∈ FPR

∃x ( A ) ∈ FPR

Réda DEHAK 232

Système formel PR

défini par :1. ΣPR , l’alphabet de symboles précédent2. FPR , l’ensemble de formules précédent3. APR l’ensemble de toutes les formules de schémas

d’axiomes SA1, SA2, SA3 de P0 et :SA4 : ∀x A(x) ⇒ A(t)SA5 : (D ⇒ B) ⇒ (D ⇒ ∀x B)

4. RPR ={m.p, g} règle du modus ponensA ├─g ∀x A

Réda DEHAK 233

Equivalence de formules

Pour simplifier et transformer des formules :– (A ⇒ B) ≡ (¬A ∨ B)– (A ∧ B) ≡ ¬(¬A ∨ ¬B)– (A ⇔ B) ≡ (A ⇒ B) ∧ (B ⇒A) ≡ (A ∧ B) ∨ (¬A ∧ ¬B)– ¬(A ∨ B) ≡ (¬A ∧ ¬B)– ¬(A ∧ B) ≡ (¬A ∨ ¬B)– (A ∨ (B ∧ C)) ≡ (A ∨ B) ∧ (A ∨ C)– (A ∧ (B ∨ C)) ≡ (A ∧ B) ∨ (A ∧ C)– ¬(¬A) ≡ A– ¬(∃x A) ≡ ∀x (¬A)– ¬(∀x A) ≡∃x (¬A)

Réda DEHAK 234

Sémantique

Une formule est interprétée dans {V, F} sur un ensemble d’objets appelé domaine de discours :– Constantes : objets particuliers– Variables : objets quelconques– Prédicats : relations entre objets– Fonctions : fonctions particulières entre objets

Exemple :La formule ∀x ∃y (chef(x,y) ∨ chef(y,x) ⇒ projet(x,y)) interprétée sur {Pierre, Paul, David} est vraie si Pierre, Paul et David travaillent dans le même projet.


Réda DEHAK 237

Plan

• Calcul relationnel de tuples

• Calcul relationnel de domaines

• Query By Example (QBE)

Réda DEHAK 238

Classification

• Deux grandes classes :1. Langage algébrique :

Algèbre relationnelle.Opérateurs relationnels.Définit les opérations : utile pour la définition des plans d’exécution.

2. Langage prédicatif :Logique des prédicats.Langage déclaratif : on définit les données recherchées et non la manière de les obtenir.

Réda DEHAK 239

Calcul Relationnel

Un langage non procédural qui sert à décrire formellement l’information que l’on veut extraire sans spécifier une séquence particulière de recherche.

Basé sur la logique des prédicats du 1er ordre :– Alphabet de symboles

• Symboles logiques (ex : ¬, ⇒, ∧, ∨, …)• Un ensemble de variables• Un ensemble de prédicats n-aires• Un ensemble de fonctions n-aires• Parenthèses

– Expressions (appelées formules bien formées) construites à partir de cet alphabet

Réda DEHAK 240

Types de calcul relationnel

Selon les variables de base utilisées pour spécifier les requêtes

Deux classes :– Calcul relationnel de tuples.– Calcul relationnel de domaines.

Réda DEHAK 241

Calcul relationnel de tuples

• Variables:– x, y, z parcourent les relations

• les relations sont définies par « ∈ »• l'ordre de parcours n'est pas défini

– les valeurs sont les tuples correspondants

s ∈ SS = (s#, nom, age, ville)s = ('123', dupont, 30, Paris)

Réda DEHAK 242

Calcul relationnel de tuples

• Forme générale :{ t | P(t) }

Où :t est une variable tupleP est un prédicat (formule) construit à partir

d’atomes et d’opérateurs. t représente la seule variable libre de P.

• t peut être qualifiée par des attributs : t[A]• La réponse est constituée de tous les tuples t pour

lesquels P est vrai.

Réda DEHAK 243

Atomes

Les atomes sont :1. Variables tuples

– La variable est qualifiée par le nom de la relation, noté : t ∈ R

2. Conditions – s[A] θ t[B], où s et t sont des variables tuples et A et B sont

des attributs de s et t, respectivement :θ = { < , > , = , ≠ , ≤ , ≥ }

– s[A] θ c par ex. s[prenom] = ‘jerome’

Réda DEHAK 244

Formules

Une formule est composée de :– Atomes– Opérateur booléens ∨, ∧, ¬, ⇒, ⇔– Quantificateur existentiels ∃– Quantificateur universels ∀

Formation des formules– Tout atome est une formule– Si F et G sont des formules, alors :

F ∨ G, F ∧ G, ¬F, F ⇒ G, F ⇔ G sont des formules– Si F est une formule et t une variable libre dans F, alors ∃t(F)

et ∀t(F) sont des formules (notées aussi ∃t F et ∀t F resp.)

Réda DEHAK 245

Exemples

PROD(nprod, design, couleur, volume)

Les produits de couleur rouge{ t | t ∈ Prod ∧ t[couleur] = ‘rouge’}

Le volume des produits de couleur rouge{ t[volume] | t ∈ Prod ∧ t[couleur] = ‘rouge’}

Réda DEHAK 246

Exemples

PROD(nprod, design, couleur, volume)CMD(nclt, nprod, qte, date)

Liste des nprod, couleur commandés par le client n° 13 :{ t[nprod], t[couleur] | t ∈ Prod ∧ ∃c ( c∈ Cmd ∧

t[nprod] = c[nprod] ∧ c[nclt]=13 )}

Liste des nprod, couleur et qte commandés par le client n°13 :

{ t[nprod], t[couleur], c[qte] | t ∈ Prod ∧ c ∈ Cmd ∧t[nprod] = c[nprod] ∧ c[nclt]=13}

Réda DEHAK 247

Formule saine

{ s | ¬ ( s ∈ Prod ) } ???• Soit P une formule formée à partir des relations R1,R2,…,Rn et

des constantes a1,a2,…ak. Le domaine de P, noté Dom(P), est un ensemble fini défini par :

Dom(P) = {a1,a2,…,ak} ∪ ensemble des composants des tuples de R1,R2,…,Rn

• Une formule saine vérifie les 3 conditions suivantes :– Si s est un n-uplet tel que P(s) est vrai, alors chaque composant de s est

un élément de Dom(P).– Pour chaque sous-formule P’ de P de la forme ∃u P’(u), si u est un n-

uplet tel que P’(u) est vrai. Alors chaque composant de u est un élément de Dom(P’).

– Pour chaque sous-formule P’ de P de la forme ∀u P’(u), si un quelconque composant de u n’est pas un élément de Dom(P’), alors P’(u) est vrai.

Réda DEHAK 248

Toute proposition formulable en algèbre relationnelle est formulable en calcul de tupleet vice versa.

– Codd, 1978

Théorème d’équivalence

Réda DEHAK 249

• ALPHA (Codd, 1978)– Jamais implémenté dans un SGBD commercial

• QUEL (Stonebraker, Wong, Rowe, 1979)– Le langage initial de INGRES– Plus puissant que SQL

• SQL (Salinger & al)– System R – Éléments de syntaxe algébrique

Utilisations dans les SGBDs

Réda DEHAK 250

ExemplesSoit les trois tables suivantes :

CLIENT(nclt, nom, age, adresse)PROD(nprod, design, couleur, volume)

CMD(nclt, nprod, qte, date)

1. La liste des noms de clients qui ont un age > 20.2. La liste des noms de clients ayant commandés le produit numéro 13.3. La liste des noms de clients ayant commandés un produit de couleur rouge.4. La couleur des produits commandés par monsieur Dupont.5. La liste des noms de clients ayant commandés au moins un produit.6. La liste des noms de clients ayant commandés un produit vert ou rouge.7. La liste des noms de clients ayant commandés un produit vert ou bien



Réda DEHAK 251

Calcul relationnel de domaines

• Variables:– x, y, z parcourent les domaines (valeurs

d'attributs). Elles varient sur le domaines de la relation

S = (s#, nom, age, ville)(x, y, z, t)

y parcours les noms

Réda DEHAK 252

Requêtes

Les requêtes sont spécifiées ainsi :{ <x1, x2, …,xn> | F(x1, x2, …,xn) }

où :– F est une formule – x1, x2, …,xn sont des variables libres.

Réda DEHAK 253

Formules

Différence avec le calcul de tuples :– Les atomes sont définis ainsi :

• Chaque domaine est un atome.• Les conditions définies comme suit sont des atomes :

– x θ y, où x et y sont des variables domaines ou des constantes– <x1, x2, …, xn> ∈ R où R est une relation de degré n et chaque xi

est une variable domaine ou une constante

– Les formules sont définies comme pour le calcul de tuples, en remplaçant les variables tuples par les variables domaines.

Réda DEHAK 254

Exemples

PROD(nprod, design, couleur, volume)

Les produits de couleur rouge{ <x, y, z, t> | <x,y,z,t> ∈ Prod ∧ z = ‘rouge’}

Le volume des produits de couleur rouge{ <t> | ∃ x y (<x, y, ‘rouge’, t> ∈ Prod) }

Réda DEHAK 255

Exemples

PROD(nprod, design, couleur, volume)CMD(nclt, nprod, qte, date)

Liste des nprod, couleur commandés par le client n° 13 :{ <t, c> | ∃ d v (<t, d, c, v>∈ Prod ∧

∃ q d ( <13, t, q,d>∈ Cmd) )}

Liste des nprod, couleur et qte commandés par le client n° 13 :{ <t, c, q> | ∃ d v (<t, d, c, v>∈ Prod ∧

∃ d ( <13, t, q,d>∈ Cmd) )}

Réda DEHAK 256







Réda DEHAK 257

• Calcul de tuples -> SQL• Calcul de domaines -> QBE

– les domaines peuvent être visualisés• "squelette" de relations

– Les conditions et les variables de domaines peuvent être placée dans les lignes correspondantes

– une énorme simplification par rapport à SQL

Équivalence de formalismes relationnels

Réda DEHAK 258

• Inventé par Moshe Zloof.

• Langage de choix pour les utilisateurs ad-hoc.

• Programmation visuelle de la requête.

• Proche du CRD.

• Disponible en version modifiée sur plusieurs SGBD.

• QBE moderne: MS Access

QBE

Réda DEHAK 259

Exemple

adresseagenomncltClient

Produit volumecouleurdesignnprod

Cmd dateqtenprodnclt

Condition Box :

Réda DEHAK 260

Nom et adresse des clients

P.

adresse

P.

agenomncltClient



Condition Box :

Réda DEHAK 261

Liste des clients

adresse

P.

agenomncltClient



Condition Box :

Réda DEHAK 262

1) La liste des noms de clients qui ont un age = 20.

adresse

20P.

agenomncltClient



Condition Box :

Réda DEHAK 263

1) La liste des noms de clients qui ont un age > 20.

adresse

> 20P.

agenomncltClient



Condition Box :

Réda DEHAK 264

Opérateurs de comparaison

• <, >, <=, >=, ¬• Les variables : _<suite de caractères>• P. : permet d’afficher le contenu de la colonne

Réda DEHAK 265







Réda DEHAK 266

2) La liste des noms de clients ayant commandés le produit numéro 13.

adresse

P._idclt

agenomncltClient


Cmd date

13_idclt

qtenprodnclt

Condition Box :

Réda DEHAK 267







Réda DEHAK 268

3) La liste des noms de clients ayant commandés un produit de couleur rouge.

adresse

P._nclt

agenomncltClient

Produit volume

‘rouge’_nprod

couleurdesignnprod

Cmd date

_nprod_nclt

qtenprodnclt

Condition Box :

Réda DEHAK 269







Réda DEHAK 270

4) La couleur des produits commandés par monsieur Dupont.

adresse

‘Dupont’_nclt

agenomncltClient

Produit volume

P._nprod

couleurdesignnprod

Cmd date

_nprod_nclt

qtenprodnclt

Condition Box :

Réda DEHAK 271







Réda DEHAK 272

5) La liste des noms de clients ayant commandés au moins un produit

adresse

P._nclt

agenomncltClient


Cmd date

_nclt

qtenprodnclt

Condition Box :

Réda DEHAK 273







Réda DEHAK 274

6) La liste des noms de clients ayant commandés un produit vert ou rouge

adresse

P._nclt

agenomncltClient

Produit volume

_coulprod_nprod

couleurdesignnprod

Cmd date

_nprod_nclt

qtenprodnclt

_coulprod = ‘rouge’ ∨ _coulprod = ‘vert’Condition Box :

Réda DEHAK 275

La liste des produits vert ou rouge

adresseagenomncltClient

Produit volume

‘rouge‘vert’

P.P.

couleurdesignnprod


Condition Box :

Réda DEHAK 276


adresse

P._nclt

agenomncltClient

Produit volume

‘rouge’‘vert’

_nprod_nprod

couleurdesignnprod

Cmd date

_nprod_nclt

qtenprodnclt

Condition Box :

Réda DEHAK 277


adresse

P.P.

_nclt1_nclt2

agenomncltClient

Produit volume

‘rouge’‘vert’

_nprod1_nprod2

couleurdesignnprod

Cmd date

_nprod1_nprod2

_nclt1_nclt2

qtenprodnclt

Condition Box :

Réda DEHAK 278







Réda DEHAK 279

8) La liste des noms de clients ayant commandés au moins deux produits

adresse

P._nclt

agenomncltClient


Cmd date

_nprod1_nprod2

_nclt_nclt

qtenprodnclt

_nprod1 <> _nprod2Condition Box :

Réda DEHAK 280







Réda DEHAK 281

9) La liste des clients qui ont un age > 50 et qui n’ont pas commandé un produit

adresse

> 50P._nclt

agenomncltClient


¬

Cmd date

_nclt

qtenprodnclt

Condition Box :

Réda DEHAK 282

9) La liste des clients qui ont un age > 50 et qui n’ont pas commandé un produit vert

adresse

> 50P._nclt

agenomncltClient

Produit volume

‘vert’_nprod

couleurdesignnprod

¬

Cmd date

_nprod_nclt

qtenprodnclt

Condition Box :

Réda DEHAK 283

9) La liste des clients qui ont un age > 50 et qui n’ont pas commandé un produit vert

adresse

> 50P._nclt

agenomncltClient

Produit volume

<>‘vert’_nprod

couleurdesignnprod

Cmd date

ALL._nprod_nclt

qtenprodnclt

Condition Box :

Réda DEHAK 284







Réda DEHAK 285

10) La liste des noms de clients qui ont commandé tous nos produits

adresse

P._clt

agenomncltClient

Produit volume

ALL._prod

couleurdesignnprod

Cmd date

_prod_clt

qtenprodnclt

Condition Box :

Réda DEHAK 286







Réda DEHAK 287

7) La liste des noms de clients ayant commandés un produit vert ou bien rouge.

adresse

P.P.

_nclt1_nclt2

agenomncltClient

Produit volume

‘rouge’<>‘vert’‘vert’<> ‘rouge’

_nprod1_nprod2_nprod3_nprod4

couleurdesignnprod

Cmd date

_nprod1ALL._nprod2_nprod3ALL._nprod4

_nclt1_nclt1_nclt2_nclt2

qtenprodnclt

Réda DEHAK 288







Réda DEHAK 289

11) La liste des noms de clients qui ont commandé tous nos types de pince

adresse

P._clt

agenomncltClient

Produit volume

‘pince’ALL._prod

couleurdesignnprod

Cmd date

_prod_clt

qtenprodnclt

Condition Box :

Réda DEHAK 290

Remarque

• Les P. doivent apparaître dans une seule table

P._dateP._qteP._prod

adresse

P._clt

agenomncltClient


Cmd

_date

date

_qte_prod_clt

qtenprodnclt

Prochain cours : SQL


Réda DEHAK 293

Plan

• Requêtes multi-tabulaires• Jointure ( Interne et externe)• Opérateurs ensemblistes (UNION, INTERSECT, EXCEPT)• Requêtes imbriquées :

– Opérateur EXISTS– Opérateur IN– Opérateur ANY– Opérateur ALL

• Valeurs Booléennes• GROUP BY• Modification de BDD• Applications

Réda DEHAK 294

Requêtes multi-tabulaires

• Dans la majorité des cas, on doit combiner des informations venant de plusieurs schémas relationnels (plusieurs tables).

• On peut utiliser plusieurs relations en même temps en le précisant dans la clause From.

• On utilise la notation relation.attribut pour différencier les attributs qui porte le même nom

Réda DEHAK 295

Syntaxe

SELECT [DISTINCT | ALL] { * | liste de colonnes} [ FROM liste de tables ][ WHERE prédicat ][ GROUP BY liste des colonnes du groupage ][ HAVING prédicat ][ ORDER BY liste de colonnes de tri ]

Réda DEHAK 296

Exemple

En utilisant les relations CLIENT(nclt, nom, age, adresse) et CMD(nclt, nprod, qte, date), trouver la liste des nprodscommandés par Dehak?

SELECT nprodFROM Client, CmdWHERE nom = ‘Dehak’ AND

Client.nclt = Cmd.nclt

Réda DEHAK 297

Sémantique

1. Commencer avec le produit cartésien de toutes les tables citées dans la clause FROM.

2. Appliquer une sélection sur le résultat avec la condition de la clause WHERE.

3. Projeter le résultat du 2 sur les attributs de la clause SELECT.

Réda DEHAK 298

Exemple

En utilisant les relations CLIENT(nclt, nom, age, adresse) et CMD(nclt, nprod, qte, date), trouver la liste des nprodscommandés par Dehak?

SELECT nprodFROM Client, CmdWHERE nom = ‘Dehak’ AND

Client.nclt = Cmd.nclt

Client

Client.nprod = Cmd.nprodAND

nom = ‘dehak’

nprod

Cmd

x

Réda DEHAK 299

Sémantique opérationnel

• Une variable tuple pour parcourir chaque relation de la clause FROM :– Ces variables tuples visitent toutes les combinaisons

possibles de tuples.

• Si les variables tuples pointent sur des tuples qui vérifient la condition du WHERE, les tuples sont envoyés à la clause SELECT

Réda DEHAK 300

Exemple

………………….

Paris

adresse

……………

Dehak

NOM

123

NcltClient

20145123

QTENPROD

…………….

……….

NCLTCMD

VT1 VT2

Égalité Résultat

Réda DEHAK 301

Variables Tuples

1. Quand la requête utilise plusieurs fois la même relation.

2. Permet de différencier les tables de la clause FROM.

3. Reste optionnel dans les cas non ambigus.

4. Utilisation de [ AS ] pour définir des variables tuples.

Réda DEHAK 302

Exemple

Trouver les nclts qui ont commandés le même produit.

SELECT c1.nclt, c2.ncltFROM Cmd c1, Cmd c2WHERE c1.nprod = c2.nprod

Problème :Réponse (42, 42) (42, 57) (57,42) …

Réda DEHAK 303

Exemple

Trouver les nclts qui ont commandés le même produit.Problème :Réponse (42, 42) (42, 57) (57,42) …

SELECT c1.nclt, c2.ncltFROM Cmd c1, Cmd c2WHERE c1.nprod = c2.nprod AND

c1.nclt < c2.nclt

Réda DEHAK 304

Les Jointures

1. Jointure :

SELECT [DISTINCT | ALL] * | liste_de_colonnesFROM table1 { [INNER] |

{LEFT | RIGHT | FULL} OUTER} JOIN table2 ON <Cond>

Réda DEHAK 305

Exemples

1. Jointure classique.2. Jointure externe.

Réda DEHAK 306

Les Jointures

2. Jointure Naturelle:

SELECT [DISTINCT | ALL] * | liste_de_colonnesFROM table1 NATURAL

{ [INNER] |{LEFT | RIGHT | FULL} OUTER

} JOIN table2 [ USING (col1, …) ]

Réda DEHAK 307

exemples

Réda DEHAK 308

Les Jointures

3. Produit cartésien:

SELECT [DISTINCT | ALL] * | liste_de_colonnesFROM table1 CROSS JOIN table2

SELECT [DISTINCT | ALL] * | liste_de_colonnesFROM table1, table2

Réda DEHAK 309

Opérateurs ensemblistes

Syntaxe :

SELECT ….{ UNION | INTERSECT | EXCEPT } [ALL] SELECT …[ORDER BY …]

Réda DEHAK 310

Exemples

• Union• Intersection• Différence

Réda DEHAK 311

Sous rêquetes

• Le résultat d’une requête peut être utilisé pour répondre à une autre requête

• Le résultat d’une requête peut être utilisén’importe où on attend une table (ex : FROM…)

• Le résultat d’une requête peut être utilisén’importe où on attend une constante si la requête retourne une seule valeur.

Réda DEHAK 312

Une seule valeur

Trouver le nom des clients qui habitent à la même adresse que ‘Dehak’?

SELECT nomFROM ClientWHERE adresse = ( SELECT adresse

FROM ClientWHERE nom = ‘Dehak’ )

Réda DEHAK 313

Une seule valeur

Trouver le nom des clients plus âgés que ‘Dehak’?

SELECT nomFROM ClientWHERE age > ( SELECT age

FROM ClientWHERE nom = ‘Dehak’ )

Réda DEHAK 314

Une seule valeur

Trouver le nom des clients les plus âgés de la table client?

SELECT nomFROM ClientWHERE age = ( SELECT max(age)

FROM Client )

Réda DEHAK 315

Une seule valeur

Trouver le nom des clients et la somme des quantités commandées pour les clients parisiens?

SELECT nom, ( SELECT SUM(QTE)FROM CmdWHERE Cmd.nclt = Client.nclt )

FROM ClientWHERE adresse = ‘Paris’

Réda DEHAK 316

Plusieurs tuples : Opérateur EXISTS

• EXISTS( <relation> ) : est vrai si et seulement si la relation contient au moins un tuple.

• Trouver les noms de client qui apparaissent plusieurs fois dans la table ?

SELECT nomFROM Client l1WHERE EXISTS ( SELECT *

FROM Client l2WHERE l2.nom = l1.nom AND

l2.nclt <> l2.nclt )

Réda DEHAK 317

Plusieurs tuples

Opérateur IN• <tuple> IN <relation> : est vrai si et seulement

si le <tuple> est un membre de la table <relation>.

• <tuple> NOT IN <relation> représente la négation.

• La <relation> représente souvent une sous requête

Réda DEHAK 318

Exemple

Trouver la liste nprods commandés par des clients dont le nom commence par ‘D’

SELECT nprodFROM CmdWHERE nclt IN ( SELECT nclt

FROM Client WHERE nom LIKE ‘D%’)

Réda DEHAK 319

L’opérateur ANY

• x = ANY ( <relation> ) : est vrai si et seulement si le tuple x est égale à au moins un tuple de la relation.

• L’opérateur = peut être remplacé par n’importe quel autre opérateur de comparaison

• x >= ANY ( <relation> ) : x n’est pas inférieure à tous les tuples de la relation.

Réda DEHAK 320

L’opérateur ALL

• x <> ALL ( <relation> ) : est vrai si et seulement si pour chaque tuple t de <relation>, le tuple x est différent de t.

• L’opérateur <> peut être remplacé par n’importe quel autre opérateur de comparaison

• x >= ALL ( <relation> ) : il n’existe pas une valeur plus grande que x dans la table <relation>

Réda DEHAK 321

Exemple

Trouver le(s) nprod(s) de la plus importante commande de la table cmd.

SELECT nprodFROM CmdWHERE qte >= ALL (SELECT qte

FROM Cmd)

Réda DEHAK 322

Valeurs booléennes

• Logique à 3 états : TRUE, FALSE, NULL.• NOT• Valeur NULL :

– SELECT * FROM clt WHERE age = NULL; faux– SELECT * FROM clt WHERE age IS NULL;

• Expression IS {TRUE | FALSE | NULL}

NFNN

FFFF

NFTT

NFTAND

NNTN

NFTF

TTTT

NFTOR

Réda DEHAK 323

Group By

TABLEWHERE

TABLE

Création de groupe suivant les attributs

du GROUP BY

TABLEGroupe

TABLEGroupe

filtréHAVING

SELECT

Résultat

Réda DEHAK 324

Exemple

La liste des clients avec le total des quantités commandées?

SELECT nclt, SUM(Qte)FROM CmdGROUP BY nclt

Réda DEHAK 325

Exemple

La liste des clients ayant commandés 5 produits différents avec le total des quantités commandées?

SELECT nclt, SUM(Qte)FROM CmdGROUP BY ncltHAVING COUNT(DISTINCT nprod) = 5

Réda DEHAK 326

Exemple

La liste des clients ayant commandés 5 produits rouges différents avec le total des quantités commandées?

SELECT nclt, SUM(Qte)FROM CmdWHERE couleur = ‘rouge’GROUP BY ncltHAVING COUNT(DISTINCT nprod) = 5

Réda DEHAK 327

Exemple

La liste des noms et ages de clients classés par ordre croissant sur l’age?

SELECT nom, ageFROM ClientORDER BY age

Réda DEHAK 328

Exemple

La liste des noms et ages de clients classés par ordre croissant sur l’age? Rajouter une colonne classement

SELECT count(*) as classement, c1.nom, c1.ageFROM Client c1 JOIN Client c2

ON c1.age <= c2.ageGROUP BY c1.nom, c1.ageORDER BY age

Réda DEHAK 329

Exemple

La liste des noms et ages de clients classés 5ieme ou bien 10ieme par ordre croissant sur l’age?

SELECT c1.nom, c1.ageFROM Client c1 JOIN Client c2

ON c1.age <= c2.ageGROUP BY c1.nom, c1.ageHAVING count(*) IN (5, 10)

Réda DEHAK 330

Modification d’une BDD

• Les requêtes de modifications ne retournent pas un résultat, elles effectuent un changement de la BDD.

• Trois types de modifications :– INSERT : Insertion d’un ou plusieurs tuples.

– UPDATE : modification d’un ou plusieurs tuples.

– DELETE : suppression d’un ou plusieurs tuples.

Réda DEHAK 331

Insertion

• Insertion d’un tuple :INSERT INTO <relation> [( liste_attr )]VALUES (liste_valeur)

• Exemple :INSERT INTO ClientVALUES (42, ‘Dehak’, ‘Reda’, 29, ‘Paris’)

INSERT INTO Client(nclt, nom)VALUES (48, ‘Daniel’)

Réda DEHAK 332

Spécifier la liste des attributs

• On ne connaît pas l’ordre des attributs.

• On ne connaît pas la valeur de certains attributs, Le système doit leur attribuer la valeur par défaut ou bien NULL)

Réda DEHAK 333

Insertion de plusieurs tuples

• À l’aide de sous requêtes :INSERT INTO <relation>(<sous requête>)

• Exemple :INSERT INTO N_Client_Parisien( SELECT nclt, nom

FROM ClientWHERE adresse = ‘Paris’ )

Réda DEHAK 334

Suppression

Supprimer des tuples qui vérifient une condition :

DELETE FROM <relation>[ WHERE <Cond> ]

Exemples :DELETE FROM ClientWHERE nom = ‘Dehak’

Réda DEHAK 335

Absence du WHERE

• Supprimer tous les tuples d’une relation :

DELETE FROM cmd

Attention : Si vous avez oublié le WHERE, le DELETE supprime tous les tuples.

Réda DEHAK 336

Suppression de plusieurs tuples

• Élimination des tuples en doubles :

Exemple :

DELETE FROM Client c1WHERE EXISTS ( SELECT *

FROM Client c2WHERE c2.age = c1.age AND

c2.nclt <> c1.nclt)

Résultat : ?

Réda DEHAK 337

UPDATE

• Modification de la valeur des attributs d’un ou plusieurs tuples

UPDATE <relation>SET <list_attr_affectation>[ WHERE <Cond> ]

Exemple : modifier le nom du client n°42UPDATE ClientSET nom = ‘Barbier’WHERE nclt = 42

Réda DEHAK 338

Exemple

• Augmenter l’age des parisiens de 2 ans

UPDATE ClientSET age = age + 2WHERE adresse = ‘Paris’

Réda DEHAK 339

ApplicationsSoit les trois tables suivantes :






Réda DEHAK 340

Les vues

Une vue est une table virtuelle = une relation définie àpartir des données contenues d’autres tables et vues.

Syntaxe :

CREATE VIEW nom_vue [(nomcol1,…)]AS requete_SELECT[WITH CHECK OPTION]

Réda DEHAK 341

Les vues

Objectifs :– Masquer la complexité d’un schéma

relationnel.

– Simplifier les requêtes SELECT complexes

– Préserver la confidentialité des données.

– Contribuer à la non redondance des données.

Réda DEHAK 342

Exemples

Les clients parisiens :

CREATE VIEW client_parisien

AS SELECT *

FROM client

WHERE adresse = ‘PARIS’

Réda DEHAK 343

Exemples

Les commandes + produits des clients ‘DUPONT’ :

CREATE VIEW cmd_dupont

AS SELECT nprod, design, couleur, volume, qte, date

FROM cmd NATURAL JOIN prod

WHERE nclt IN ( SELECT nclt

FROM client

WHERE nom = ‘DUPONT’

)

Réda DEHAK 344

Exemples

Facture (attributs calculés)

CREATE VIEW Facture (nprod, nclt, qte, vol_tot, date)

AS SELECT nprod, nclt, qte, qte * volume, date

FROM cmd NATURAL JOIN prod

Réda DEHAK 345

Utilisation d’une vue

Exemples

Réda DEHAK 346

Utilisation de la vue

• Le SGBD interpréte la requête en considérant la vue comme une table

Les SGBDs traduisent la requête en arbre algébrique.

• Il remplace la Vue par son arbre algébrique.

Réda DEHAK 347

Question

Peut on modifier le contenu d’une vue ?

Réda DEHAK 348

Vues modifiables

Les vues crées à partir de requête SELECT contenant :

1. Une seule table ou une seule vue, elle-même modifiable.

2. Ni intersection, ni union, ni différence, ni jointure.

3. Ni mot DISTINCT, ni expression de calcul dans la clause SELECT

4. Ni clause group by ni HAVING5. Aucune sous-requête faisant référence à la même

table que la table externe.6. Présence obligatoire d’une clé primaire

Réda DEHAK 349

Exemples


AS SELECT *

FROM client

WHERE adresse = ’PARIS’


AS SELECT nclt, nom, prenom

FROM client



AS SELECT *

FROM client

WHERE adresse = ’PARIS’

WITH CHECK OPTION

Réda DEHAK 350

Exemples


AS SELECT *

FROM client T

WHERE adresse IN ( SELECT adresse

FROM fournisseur

WHERE fournisseur.nom = T.nom )

CREATE VIEWclient_parisien

AS SELECT nom, prenom

FROM client


Réda DEHAK 351

Supprimer une vue

DROP VIEW <nom vue> : permet de supprimer une vue existante

Réda DEHAK 352

Contrôle d’accèsAttribution des privilèges :

GRANT { ALL PRIVILEGES | liste_privilèges } ON objetTO { PUBLIC | liste_user }[ WITH GRANT OPTION ]

Privilèges :– SELECT : lecture de toutes les colonnes d’une table ou d’une vue.– INSERT[liste_colonne] : insertion dans une table ou dans une vue,

éventuellement limitée à certaines colonnes.– UPDATE[liste_colonne] : mise à jour dans une table ou dans une vue,

éventuellement limitée à certaines colonnes.– DELETE : suppression dans une table ou dans une vue.– REFERENCES[liste_colonne] : Faire référence aux colonnes d’une

table ou d’une vue lors de la pose d’une contrainte référentielle, éventuellement limitée à certaines colonnes.

Réda DEHAK 353

Exemples

GRANT SELECT ON client TO PUBLIC

GRANT SELECT ON produit TO PUBLIC

GRANT ALL PRIVILEGES ON cmd TO User_Service_CmdWITH GRANT OPTION

GRANT SELECT ON cmd TO User_Facturation

Réda DEHAK 354

Contrôle d’accès

• Suppression des droits d’accès :REVOKE [ GRANT OPTION FOR] {ALL PRIVILEGES | liste_privilèges} ON object FROM { PUBLIC | liste_utilisateurs}

• Exemple :REVOKE UPDATE ON cmd FROM User_Service_Cmd

REVOKE GRANT OPTION FOR DELETE ON cmd

FROM User_Service_Cmd

Réda DEHAK 355

Transaction

BEGINCOMMITROLLBACK

Réda DEHAK 356

TRIGGER

Syntaxe :CREATE TRIGGER <nom trigger>{BEFORE | AFTER | INSTEAD OF}{INSERT | DELETE | UPDATE [OF liste_colonnes]}ON <relation>[ ORDER <liste colonne> ][ REFERENCING OLD [AS] anc_val

| NEW [AS] nouv_val| OLD_TABLE [AS] anc_tab| NEW_TABLE [AS] nouv_tab ]

[FOR EACH {ROW | STATEMENT}]Code_trigger

Réda DEHAK 357

SQL DDL

1. Création d’une base de donnéeCREATE DATABASE nom_base

2. Suppression d’une base de donnéeDROP DATABASE nom_base

3. Création d’une tableCREATE [{LOCAL | GLOBAL} TEMPORARY] TABLE nom_table

(…définition des colonnes et des contraintes…)4. Modification d’une table

ALTER TABLE nom_table { [ADD CONSTRAINT contrainte]DROP CONSTRAINT nom_contrainte]ADD COLUMN def_colonneDROP COLUMN nom_colonneALTER COLUMN { SET DEFAULT val_default]

| DROP DEFAULT}

Réda DEHAK 358

FOREIGN KEY

FOREIGN KEY REFERENCES table(col) [ [NOT] DEFERRABLE [INITIALLY [DEFERRED | IMMEDIATE] ]

SET CONSTRAINT <cont> DEFERRED

Réda DEHAK 359

Soit la base de données relationnelle, PUF, de schéma :U (NU, NomU, Ville)P (NP, NomP, Couleur, Poids)F (NF, NomF, Statut, Ville)PUF (NP, NU, NF, Quantité)

décrivant les faits suivants :– U: une usine est décrite par son numéro NU, son nom NomU, la ville

Ville dans laquelle elle est située;– P: un produit est décrit par son numéro NP, son nom NomP, sa

Couleur, son Poids;– F: un fournisseur est décrit par son numéro NF, son nom NomF, son

Statut (fournisseur soustraitant, fournisseur-exclusif, .....), la Ville où il est domicilié;

– PUF: le produit de numéro NP a été livré à l'usine de numéro NU par le fournisseur de numéro NF dans une Quantité donnée.

Réda DEHAK 360

Exprimer en SQL les requêtes suivantes:1. Donner le script de création de cette base de donnée.2. Donner tous les droits à l’utilisateur direction avec

possibilité de session de droit.3. Donner le droit de selection à tous les utilisateurs.4. Supprimer le droit d’insertion à l’utilisateur toto.5. Supprimer la possibilité de session de droit sur tous les

privilèges de l’utilisateur david.6. Créer une vue UParis avec les usines parisiennes7. Donner le numéro, le nom et la ville de toutes les usines.8. Donner le numéro, le nom et la ville de toutes les usines de

Londres.

Réda DEHAK 361

8. Donner les numéros des fournisseurs qui approvisionnent l'usine n°1 en produit n°1.

9. Donner le nom et la couleur des produits livrés par le fournisseur n°1.

10. Donner les numéros des fournisseurs qui approvisionnent l'usine n°1 en un produit rouge.

11. Donner les noms des fournisseurs qui approvisionnent une usine de Londres ou de Paris en un produit rouge.

12. Donner les numéros des produits livrés à une usine par un fournisseur de la même ville.

13. Donner les numéros des produits livrés à une usine de Londres par un fournisseur de Londres.

14. Donner les numéros des usines qui ont au moins un fournisseur qui n'est pas de la même ville.

15. Donner les numéros des fournisseurs qui approvisionnent à la fois les usines n°1 et n°2.

Réda DEHAK 362

16. Donner les numéros des usines qui utilisent au moins un produit disponible chez le fournisseur n°3 (c'est-à-dire un produit qu'il livre mais pas nécessairement à cette usine).

17. Donner le numéro du produit le plus léger (les numéros si plusieurs produits ont ce même poids).

18. Donner les numéros des usines qui ne reçoivent aucun produit rouge d'un fournisseur parisien.

19. Donner les numéros des fournisseurs qui fournissent au moins un produit fourni par au moins un fournisseur qui fournit au moins un produit rouge.

Réda DEHAK 363

20. Donner les numéros des produits qui sont livrés à toutes les usines de Londres.

21. Donner les numéros des fournisseurs qui approvisionnent toutes les usines avec un même produit.

22. Donner les numéros des usines qui achètent au fournisseur n°4 tous les produits qu'il fournit.

23. Donner les numéros des usines qui s'approvisionnent uniquement chez le fournisseur n°3.

24. Ajouter un nouveau fournisseur : <45, Alfred, sous-traitant, Lausanne>

25. Supprimer tous les produits de couleur noire et de numéro compris entre 100 et 199.

26. Changer la ville du fournisseur n°1 : il a déménagé àGenève.


Réda DEHAK 366

Introduction

Définition du schéma relationnel :1. Schéma Entité Association.

2. Passage au modèle relationnel.

3. Ajout des contraintes d’intégrité.

4. Refonte du schéma entité association (Problèmes ou anomalies dans le schéma de départ).

Réda DEHAK 367

Introduction

• Conception du modèle relationnel :Regroupement des attributs en relation pour former un bon schéma relationnel

• Deux niveaux de conception :– Niveau logique– Niveau physique

• Quelles sont les critères pour avoir un bon schéma relationnel?

Réda DEHAK 368

Plan

• Un bon modèle relationnel.• Dépendances fonctionnelles.• Formes normales :

– 1ère FN– 2ème FN– 3ème FN– FNBC– 4ème FN– 5ème FN

Réda DEHAK 369

Conception du modèle relationnel

1. Sémantique des attributs de la relation.

Les tuples doivent représenter les attributs d’une seule entité ou bien d’une seule association.

– Ne pas mélanger l’origine des attributs dans une relation.– Utiliser les clés étrangères pour faire référence à une

autre relation.

But : Simplifier la compréhension du schéma

Réda DEHAK 370


2. Mélanger les attributs provenant de différentes entités peut causer de sérieux problèmes :

• Les mêmes informations sont stockées plusieurs fois ⇒ Perte de place mémoire.

• Problèmes liés au fonctionnement de la base :– Les anomalies de mise à jour.

– Les anomalies d’insertion.

– Les anomalies de suppression.

Réda DEHAK 371


3. Valeurs NULL pour les attributs d’un tuple :- L’attribut ne s’applique pas à ce tuple.- La valeur de cet attribut est inconnue.- La valeur est connue, mais elle n’est pas encore enregistrée.

Il faut éviter de placer des attributs qui vont prendre souvent la valeur NULL à l’intérieur d’un schéma de la relation.

Placer les attributs qui peuvent prendre une valeur NULL dans un autre schéma

Réda DEHAK 372

Solutions aux problèmes de conception

Décomposer un schéma relationnel en plusieurs sous schéma :– Comment décomposer un schéma relationnel?– Comment détecter et résoudre les problèmes

qu’on peut rencontrer?

Solution : Les formes normales

Réda DEHAK 373

Dépendances fonctionnelles

Soit R(A1, A2 … An) un schéma de relation, X et Y des sous-ensembles de { A1, A2 …An}

Définition :On dit qu’il existe une dépendance fonctionnelle de X vers Y notée X Y (X détermine Y ou Y dépend fonctionnellement de X) ssi il existe une fonction qui a partir de toute valeur de X détermine une valeur unique de Y :

∀ T1, T2 ∈ R, T1.X = T2.X ⇒ T1.Y = T2.Y

Réda DEHAK 374

Évaluation d’une DF

X Y peut être imposée au schéma selon trois cas :1. X et Y sont inclus dans le même schéma de relation R :

La vérification de la contrainte est simple ( il faut surveiller les insertions et les modifications dans la table R)

2. X et Y sont inclus dans des schémas de relation différents : La vérification est complexe ( il faut surveiller les insertions et les modifications dans les deux schéma àpartir d’une jointure)

3. X ou Y n’est pas inclus dans un seul schéma :vérification plus complexe

Réda DEHAK 375

Déduction des DF

A partir de certaines DF, on peut déduire des nouvelles DF :

Si A B et B C alors A C

Axiome d’amstrong :1. Réflexivité : si X ⊇ Y alors X Y2. Augmentation : si X Y alors XZ YZ3. Transitivité : si X Y et Y Z alors X Z

Réda DEHAK 376

Propriétés supplémentaires

4. Union :si X Y et X Z alors X YZ

5. Décomposition :si X YZ alors X Y

6. Pseudo-transitivité :si X Y et WY Z alors XW Z

Réda DEHAK 377

Fermeture transitive d’un ensemble de DF

• Fermeture transitive d’un ensemble de DF:La fermeture transitive F+ d’un ensemble F de dépendance fonctionnelles est l’ensemble de toutes les dépendances fonctionnelles qu’on peut déduire de F :

F+ = { X Y | F ⇒ X Y }

• Fermeture transitive d’un ensemble d’attributs :Soit X un ensemble d’attributs et F un ensemble de DF, la fermeture transitive [X]+ de l’ensemble X par rapport à F

[X]+ = { A | X A ∈ F+ }

Réda DEHAK 378

Algorithme

Algorithme itératif pour calculer X+ :1. [ X ](0) := X , i := 02. [ X ](i+1) := [ X ](i)

3. Pour tout f : Y Z ∈ F tel que Y ⊂ [ X ](i)

[ X ](i+1) := [ X ](i+1) ∪ ZF := F \ {f}

4. Si [ X ](i+1) ≠ [ X ](i) alors aller en 2 avec i++5. Sinon [ X ]+ = [ X ](i+1)

Réda DEHAK 379

Équivalence et ensemble minimale de DF

Deux ensembles de DF F1 et F2 sont équivalent (F1 ≡ F2) s’ils ont la même fermeture transitive:

F1 ≡ F2 ⇔ F1+ = F2

+

F est un ensemble minimal de DF si :1. F est sous forme canonique : toute dépendance de F

est sous la forme X A (un seul attribut à droite)2. F ne contient pas de DF redondante.3. F ne contient aucune DF redondante à gauche

Réda DEHAK 380

Couverture minimale

Définition :F’ est une couverture minimale d’un ensemble de DFF ssi :

1. F’ est un ensemble minimale de DF.2. F’ ≡ F.

Réda DEHAK 381

Algorithme de calcul de la couverture minimale

F1 := F sous forme canonique.F2 := F1 :

Pour toute DF f de F1 , si (F2 \ f) ≡ F2 alors remplacer F2 par F2 par (F2 \ f)F3 := F2

Pour toute DF f : X A de F2,soit f ’ Y A tel que :

• Y ⊂ X• ( (F3 \ f ) ∪ f’ ) ≡ F3

• ∀z ⊂ Y, f" : Z A et ( (F3 \ f ) ∪ f" ) T F3

Faire F3 := ((F3 \ f ) ∪ f’ )

Réda DEHAK 382

Décomposition de schéma relationnel

• La décomposition d’un schéma R est un ensemble de schéma R1, R2, …, Rn tel que :– ∀i, Ri ⊂ R– R = »i Ri– Ri1 … Ri2 ∫ «, Ri2 … Ri3 ∫ « …, Ri(n-1) … Rin∫ «

La décomposition possède exactement les mêmes attributs que R et il est possible de recomposer R par

une jointure naturel

Réda DEHAK 383

Décomposition sans perte d’information (SPI)

Une décomposition de R en R1, R2, …, Rn est sans perte d’informations par rapport à un ensemble de DF F si

R = PR1(R) NJoin PR2(R) … NJoin PRn(R)

Il suffit de vérifier une seule inclusion car :R ⊂ PR1(R) NJoin PR2(R) … NJoin PRn(R)

Est vrai ∀ R

Réda DEHAK 384

Décomposition SPI

Théorème :Soit { R1, R2 } une décomposition de R et F l’ensemble des DF qui s’appliquent à R, alors :

La décomposition de R en { R1, R2 } est SPI ssi((R1 … R2) R1) v ((R1 … R2) R2)

Réda DEHAK 385

Décomposition sans perte de dépendance (SPD)

La propriété SPI n’est pas suffisante :R(Code_pos, Ville, Rue) et F = { (V,R) CP, CP

V }R1(Code_pos, Rue) et R2(Code_pos, Ville)

Problème pour vérifier (V,R) CP

Définition :Une DF X Y est projetée si il existe une relation de la décomposition qui contient XY

Réda DEHAK 386

Décomposition SPD

Buts :Il faut que la décomposition permette de vérifier toutes les DF

Définition :On note FR les DF F qui se projettent sur le schéma R.

Une décomposition de R en R1, R2, …, Rn est sans perte de dépendance par rapport à F si :

F+ = (F+R1 » F+

R2 » … F+Rn)+

Réda DEHAK 387

Vérification

Il suffit de vérifier que F+ ⊂ (F+

R1 » F+R2 » … F+

Rn)+

Car (F+R1 » F+

R2 » … F+Rn)+ ⊂ F+ est toujours vrai.

Algorithme pour tester si une DF X Y est perdue par décomposition :

1. Z := X2. Pour i = 1 à n faire Z := Z » ([ Z … Ri ]+ … Ri )3. Si Z contient Y alors retourner faux4. Si Z n’a pas augmenté à l’étape 2 retourner vrai5. Continuer en 2

Réda DEHAK 388

Exemples

• R(A,B,C,D) : F={A B, B C, C D, D A }– R1(AB), R2(BC), R3(CD)

Réda DEHAK 389

Plan

• Un bon modèle relationnel.• Dépendances fonctionnelles.• Formes normales :

– 1ère FN– 2ème FN– 3ème FN– FNBC– 4ème FN– 5ème FN

Réda DEHAK 390

Forme normale

• 1ère Forme normale :Une relation est en 1ère forme normale si tout attribut contient une valeur atomique (unique)

PERSONNE NOM PROFESSION

DUPONT Ingénieur, Professeur

MARTIN Géomètre

Réda DEHAK 391

Forme normale

• 2ème Forme normale :une relation est en 2e forme normale ssi :

1. elle est en 1ère forme2. tout attribut non clé ne dépend pas d'une partie de clé

Une telle relation doit être décomposée en

R1(C1,C2,X) et R2(C2,Y)

YXC2C1R

Réda DEHAK 392

Forme normale

• 3ème Forme normaleune relation est en 3e forme normale ssi :

1. elle est en 2e forme2. tout attribut n'appartenant pas a une clé ne dépend

pas d'un autre attribut non clé

Une telle relation doit être décomposée en

R1(C, X, Y) et R2(X, Z)

ZYXCR

Réda DEHAK 393

Forme Normale

• Forme Normale de Boyce Coddune relation est en BCNF (Boyce-Codd Normal Form) ssi :

• les seules dépendances fonctionnelles sont du type clédétermine attribut non clé

Une telle relation peut être décomposée en

R1(C1, Y, X) et R2(Y, C2)

YXC2C1R

Réda DEHAK 394

Exercice

Soit S le schéma d’une base de données relationnelle suivant, comportant la seule relation R, sur lequel on a défini une famille F de dépendances fonctionnelles:

S={R(A,B,C,D,E)}F={DE C, C B, B E }

1. F est- elle minimale? Justifiez votre réponse.2. Quelles sont les clés minimales de R? montrez comment vous les obtenez.3. Donner 2 exemples de redondances susceptibles d’apparaître dans une instance de

R?4. En quelle forme normale est S?5. La décomposition de S en S’={R1(C,D,E), R2(A,B,D,E)} est elle sans perte

d’information? Si oui prouvez-le, si non montrez un contre exemple.6. Quelles sont les dépendances projetées sur R1 et sur R2? La décomposition de S en

S’ est- elle sans perte de dépendance?7. Proposez une décomposition de S, sans perte d’information, sans perte de

dépendance et en 3ème forme normale. Le schéma ainsi obtenu est-il en forme normale de Boyce-Codd?

Réda DEHAK 395

Algorithme de décomposition en 3FN (SPI, SPD)

• Entrée : R(a1,a2, …,an) et F un ensemble minimal de DF

1. Regrouper les DF qui ont la même partie gauche.2. Créer un schéma de relation Ri avec les attributs de chaque

groupe de DF.3. Si aucune clé minimale de R n’apparaît dans un Ri existant,

rajouter un schéma de relation formé par les attributs d’une cléminimale de R.

4. Éliminer les schémas de relation inclus dans d’autres.

Réda DEHAK 396

Algorithme de décomposition en FNBC (SPI)

• Entrée : R(a1,a2, …,an) et F un ensemble minimal de DF

1. Si R n’est pas en FNBC, alors il existe X A tel que X n’est pas une surclé de R

2. Remplacer R par (X,A) et R\{A} et recommencer.

Réda DEHAK 397

Exercices

1. F={AB C, B D, CD E, CE GH, G A}A-t-on : AB E, BG C, AB G

2. Les deux ensembles de DF F et G sont-ils équivalents?

– F={A B, CE H, C E, A CH}– G={C EH, A BC}

Réda DEHAK 398

Exercices

Soit la relation R(A,B,C,D,E,F,G,H) avec la liste de dépendances fonctionnelles suivantes :DF = {A B, A C, D E, F A, F C, F G, AD C, AD H}

1. Proposer une décomposition en 3e FN de R.2. FNBC?

Réda DEHAK 399

4e FN et DMV

• Exemple :

NormalVERTMEGANE

BreakVERTR25

NormalROUGER25

NormalVERTR25

BreakROUGER25

VERSIONCOULEURTYPE_VOI

Réda DEHAK 400

4e FN et DMV

• Exemple :

NormalBLEUMEGANE

BreakVERTMEGANE

BreakBLEUMEGANE

NormalVERTMEGANE

BreakVERTR25

NormalROUGER25

NormalVERTR25

BreakROUGER25

ModèleCOULEURTYPE_VOITURE

Réda DEHAK 401

MVD

• Définition :Une dépendance multivaluée X Y (X multidétermine Y) si, étant donné des valeurs x de X, il y a un ensemble de valeurs de Y associées à ce x et cet ensemble est indépendant des autres attributs de la relation.

• Exemples :

TYPE_VOITURE COULEUR

Réda DEHAK 402

X Y Z

=T1

T2

DMV

• Propriétés :soit X Y, s’il existe deux tuples T1 et T2 dans R avec T1.X = T2.X alors il existe deux autres tuples T3 et T4 avec :

• T3.X = T1.X, T3.Y = T2.Y et T3.Z = T1.Z• T4.X = T2.X, T4.Y = T1.Y et T4.Z = T2.Z

Réda DEHAK 403

Raisonnement sur les DMV

1. DF :Si X Y alors X Y

2. Complémentation :Si X Y alors X R \ {X,Y}

3. Augmentation :Si X Y et W ⊇ Z alors WX YZ

4. Transitivité :Si X Y et Y Z alors X (Z-Y)

Réda DEHAK 404

4e FN

• Une relation est en quatrième forme normale si et seulement si les dépendances multivaluées X Yvérifient :– Y ⊆ X ou XY = R– X est une surclé.

• Exemples :Voiture (Type, Couleur, mod)

V1(Type, couleur)V2(Type, Mod)

Réda DEHAK 405

Algorithme de décomposition

• Utiliser le même algo que BCNF

1. Si R n’est pas en 4e FN, alors il existe X Atel que X n’est pas une surclé de R

2. Remplacer R par (X,A) et R\{A} et recommencer.

Réda DEHAK 406

Exercice

• Décomposer en 4e FN les schémas suivants :

1. R(A,B,C,D) avec A B et A C.2. R(A,B,C,D) avec A B et B CD3. R(A,B,C,D) avec AB C et B D4. R(A,B,C,D,E) avec A B, AB C et

A D, AB E

Réda DEHAK 407

5e et Dépendance de jointure (DJ)

• Exemples :

NormalROUGEMEGANE

NormalVERTR25

NormalROUGER25

BreakROUGER25


Réda DEHAK 408


NormalROUGEMEGANE

NormalVERTR25

NormalROUGER25

BreakROUGER25


ROUGER25

VERTR25

ROUGEMEGANE

COULEURTYPE_VOI

BreakR25

NormalR25

NormalMEGANE

VERSIONTYPE_VOI

ROUGEBreak

VERTNormal

ROUGENormal

COULEURVersion

Réda DEHAK 409


• Décomposer un schéma en plusieurs schémas (Nb >= 3)• Utilisation de la dépendance de jointure :

Soit R(a1,a2,…,an) un schéma de relation et R1,R2,..,Rk des sous ensembles de (a1,a2,…,an).

On dit qu’il existe une dépendance de jointure (JD){R1,R2,..,Rk} si R est la jointure de ses projections sur R1,R2,..,Rk :

R = Njoin(PR1(R), PR2(R),…, PRm(R))

Réda DEHAK 410

DJ, DMV, et DF

• Si X Y alors R=join(PR\{Y}(R), P{X,Y}(R))(DJ)(R\{Y}, {X,Y})

• Si X Y alors R=join(PR\{Y}(R), P{X,Y}(R))(DJ)(R\{Y}, {X,Y})


Réda DEHAK 413






Récupération




Évaluation des

requêtes


Requêtes SQL

Réda DEHAK 414

Support des données

• Disques : Permet un accès direct à n’importe quelle page avec un coût fixe.– L’accès à des pages consécutives est plus rapide

qu’un accès aléatoire.

• Bandes magnétiques : lecture des pages en séquence.– Moins chère que les disques– Utilisées pour l’archivage et les sauvegardes.

Réda DEHAK 415

Organisation des données

• Fichier : ensemble d’enregistrements de données sur le support externe.– Un enregistrement est identifié par un Record id (RID)– Indexes sont des structures de données qui permettent de

retrouver les enregistrements correspondants aux RID à partir de la clé de l’indexe.

• Le gestionnaire du tampon : copie les pages de la mémoire physique vers les tampons de la mémoire vive.– Les accès aux fichiers et indexes passent par le gestionnaire

du tampon (buffer manager)

Réda DEHAK 416

Organisation des fichiers

Plusieurs méthodes d’organisation sont possibles :

• Tas (ordre aléatoire) :– Utile pour un accès global à l’ensemble des données (scanner)

• Fichier trié :– Utile si les données doivent être extraites dans un ordre particulier.

– Accès rapide à un enregistrement particulier du fichier à partir de la valeur de la clé du tri

• Fichier indexé : structure de données pour organiser les enregistrement en arbre ou à l’aide d’une fonction de hachage.– Comme les fichiers triés pour la vitesse d’accès.

– Les modifications de la base sont plus rapide par rapport au cas des fichiers triés.

Réda DEHAK 417

Indexes

• Un indexe augmente la vitesse d’accès au fichier àpartir de la clé de l’indexe :– Une clé d’indexe est constituée de n’importe quel sous

ensemble d’attributs de la relation.– La clé d’indexe est différente de la clé de la relation

(ensemble minimal permettant d’identifier un enregistrement de la relation).

Réda DEHAK 418

Indexes : Arbre B+

• Les pages feuilles contiennent les données et sont doublement chaînées (avant arrière)

• Les pages non feuilles contiennent les clés de l’indexe, elles sont utilisées pour diriger la recherche.

… … … …

… …

…

Pages non feuilles

Feuilles de l’arbre

Réda DEHAK 419

Exemple

• Rechercher 28*? 29*?• Rechercher les tuples pour qui vérifient 15*< clé < 30*?• INSERT / DELETE : rechercher la page concernée et insérer (ou

supprimer) la nouvelle données*– Dans certain cas, il est nécessaire de modifier le nœud parent.

17

135 3027

3Y

2X

8Z

7B

6A

15M

14L

24U

22T

29W

27V

39R

38P

34S

33D

Données <= 17 Données > 17

Réda DEHAK 420

Indexe : hachage

• Le meilleur pour une sélection avec un critère d’égalité.

• Un indexe est une collection de paquets :– Un paquet = une page primaire + 0 ou n pages de

débordement.– Les paquets contiennent les données.

• Fonction de hachage H :– H(k) = l’adresse du paquet qui doit contenir les

données correspondant à l’enregistrement contenant la clé k.

Réda DEHAK 421

Exemple

Hélène, 44, 1987

John, 40, 1980

Smith, 44, 1983

Jerome, 29, 1980

Daniel, 25, 1983

Pierre, 50, 1987

H

H(age) = 00

H(age) = 01

H(age) = 10

Réda DEHAK 422

Les données de l’indexe

Les entrées k* peuvent correspondre à :1. Les données avec la clé de valeur k.

Indexe Plaçant (Clustered Index)2. <k, RID de l’enregistrement correspondant à

la clé k>Indexe non plaçant (Unclustered Index)

3. <k, liste des RID correspondants à la clé k>Indexe non plaçant sans unicité de la clé k

Réda DEHAK 423

Les données de l’indexe

1. Les données avec la clé de valeur k :• L’indexe est une structure pour organiser le fichier

de données (enregistrement)• Un seul indexe peut être du type 1, sinon il faut

dupliquer les données)2. Pour les autres cas des données pour

rediriger la recherche sont stockées dans les feuilles de l’indexe.

Réda DEHAK 424

Classification des indexes

• Primaire / Secondaire– Indexe primaire : Si la clé de recherche contient la clé

primaire de la relation.– Indexe secondaire : Si la clé primaire de la relation n’est pas

incluse dans la clé de l’indexe.• Plaçant / Non Plaçant (Clustered/Unclustered)

– Si les données sont stockées dans le même ordre que l’indexe alors l’indexe est plaçant.

– La méthode 1 implique un indexe plaçant.– En pratique un indexe plaçant implique la méthode 1 (les

fichiers triés ne sont jamais implémentés)– Les coûts d’accès varient selon que l’indexe est plaçant ou

non.

Réda DEHAK 425

Indexe Plaçant / Non Plaçant

Construction d’un indexe plaçant :– Trier le fichier tas en ajoutant des places libres dans chaque

page– Les pages de débordement sont nécessaire pour les insertions.

… …

Indexe

Données de l’indexe

Données

Plaçant Non Plaçant

Réda DEHAK 426

Modèle pour l’évaluation des coûts d’accès

On s’intéresse aux coûts de lecture / écriture :– P : le nombre de pages de la base de données.– E : Le nombre d’enregistrements par page.– D : temps moyen de lecture écriture d’une page disque.

Remarque :On ignore les gains liés à une lecture séquentielle des pages consécutives

Réda DEHAK 427

Comparaison

Un fichier contenant les informations d’un employé : nom, prénom, age, salaire.

1. Tas : Ordre aléatoire des enregistrements dans le fichier.2. Fichier Trié sur (age)3. Fichier indexé (plaçant) (age) avec un arbre B+ (méthode

1).4. Un tas avec un indexe (age) non plaçant en utilisant un

arbre B+.5. Un tas avec un indexe (age) non plaçant utilisant les

fonctions de hash.

Réda DEHAK 428

Opérations de comparaison

1. Scanner : extraire tous les enregistrement de la table.SELECT * FROM Emp;

2. Recherche avec critère d’égalité.SELECT * FROM Emp WHERE age = 29;

3. Sélection avec un critère BETWEEN.SELECT * FROM Emp WHERE age BETWEEN 20 AND 40;

4. Insertion.INSERT INTO Emp VALUES(42, ‘Dubois’, ‘Alain’, 42, 2500)

5. Suppression.DELETE FROM Emp WHERE age = 42;

Réda DEHAK 429

Hypothèse

• Tas :– Le critère de sélection avec égalité aboutit à un seul résultat.

• Fichier trié :– Compacter le fichier après suppression.

• Indexes :– Méthode (2 et 3) : taille de la clé de l’indexe = 10% de la taille d’un

enregistrement.– Hash : pas de page de débordement– Taux de remplissage des pages avec B-TREE : 67%.– Taux de remplissage des pages avec méthode de HASH : 80%.

• Scanner :– Les feuilles de l’indexe sont doublement chaînées.

Réda DEHAK 430

Comparaison

Non plaçant, hash

Non plaçant, arbre B+

Indexe plaçant

Trié

Tas

DeleteInsertBetweenEgalitéScan

Réda DEHAK 431

Scan

SELECT * FROM Emp;1. Tas :

– Il faut lire toutes les pages de la tables EmpNombre de page à lire : P

Coût : DP2. Fichier trié :

– Il faut lire toutes les pages de la tables EmpNombre de page à lire : P

Coût : DP– Avantage : le résultat est trié selon les valeurs de la clé de

tri.

Réda DEHAK 432

Scan

3. Indexe plaçant :– Il faut lire toutes les pages de la tables Emp

Nombre de page à lire : 1.5 * PCoût : 1.5DP

– Avantage : le résultat est trié selon les valeurs de la clé de tri.4. Indexe B-TREE non plaçant :

– Il faut lire toutes les pages de données de l’indexeNombre de page à lire : 0.15 * P

– Pour chaque tuple, charger une page, donc il faut lire une page pour chaque tuple de la table employé :

Nombre de page à lire : PRCoût : DP (R + 0.15)

– Avantage : le résultat est trié selon les valeurs de la clé de tri.

Réda DEHAK 433

Scan

5. Indexe hash non plaçant :– Il faut lire toutes les pages de données de l’indexe (les

paquets)

Nombre de page à lire : 0.125 * P– Pour chaque tuple, charger une page, donc il faut lire une

page pour chaque tuple de la table employé :


– Avantage : le résultat est trié selon les valeurs de la clé de tri.

Réda DEHAK 434

Comparaison

DP * (R + 0.125)

Non plaçant, hash

DP *(R + 0.15)


1.5DPIndexe plaçant

DPTrié

DPTas


Réda DEHAK 435

Égalité

SELECT * FROM Emp WHERE age = 29;1. Tas :

– Dans le pire des cas, on doit lire toutes les pages de la table employé,

– Dans le meilleur des cas, on lit une seule page :Nombre de page à lire en moyenne : 0.5 P

Coût : 0.5 DP2. Fichier trié :

– On utilise la dichotomie :Nombre de page à lire : Log2( P )

Coût : D Log2( P )

Réda DEHAK 436

Égalité

3. Indexe plaçant :– Il faut lire toutes les pages des nœuds internes du B-TREE de la racine

vers les feuilles pour trouver la page concernée :Nombre de page à lire : H = LogF( 1.5 P )

Coût : H D = D LogF( 1.5 P )– F le nombre de fils pour chaque nœud du B-TREE.

4. Indexe B-TREE non plaçant :– Il faut lire toutes les pages des nœuds internes du B-TREE de la racine

vers les feuilles pour trouver la page concernée de l’indexe:Nombre de page à lire : LogF ( 0.15 * P)

– Lire la page qui contient le tuple concerné :Nombre de page à lire : 1

Coût : D ( LogF ( 0.15 * P) + 1)

Réda DEHAK 437

Égalité

5. Indexe hash non plaçant :– En utilisant la fonction de hash, lire la page des données de

l’indexe concernée

Nombre de page à lire : 1– Déterminer et charger la page de données concernée

Nombre de page à lire : 1Coût : 2D

Réda DEHAK 438

Comparaison

2DDP ( R + 0.125 )

Non plaçant, hash

D(1+ logF(1.5P))

DP ( R + 0.15 )


DlogF(1.5P)1.5DPIndexe plaçant

Dlog2(P)DPTrié

0.5DPDPTas


Réda DEHAK 439

BETWEEN

SELECT * FROM Emp WHERE age BETWEEN 20 AND 40;1. Tas :

– Il faut lire toutes les pages

Nombre de page à lire : PCoût : DP

2. Fichier trié :– On utilise la dichotomie pour trouver le premier élément ensuite

continuer en séquence sur les pages suivante:

Nombre de page à lire : Log2( P ) + T0 / RCoût : D ( Log2( P ) + T0 / R)

– T0 : nombre de tuples qui vérifient la condition du BETWEEN

Réda DEHAK 440

BETWEEN

3. Indexe plaçant :– Il faut lire toutes les pages des nœuds internes du B-TREE de la racine vers les

feuilles pour trouver la page qui contient le premier tuple et continuer en séquence sur les autres pages:

Nombre de page à lire : H + 1.5 T0 / R = LogF( 1.5 P ) + 1.5 T0 / R

Coût : D ( LogF( 1.5 P ) + 1.5 T0 / R )

4. Indexe B-TREE non plaçant :– Il faut lire toutes les pages des nœuds internes du B-TREE de la racine vers les

feuilles pour trouver la première page de l’indexe du premier tuple qui vérifie la condition du between et continuer en séquence :

Nombre de page à lire : LogF ( 0.15 * P) + 0.15 T0 / R– Pour chaque tuple, lire une page

Nombre de page à lire : T0

Coût : D ( LogF ( 0.15 * P) + 0.15 T0 / R + T0)

Réda DEHAK 441

BETWEEN

5. Indexe hash non plaçant :– Il faut utiliser le scan, en particulier dans le cas où l’age est

un attribut réel :– Il faut lire toutes les pages de données de l’indexe (les

paquets)

Nombre de page à lire : 0.125 * P– Pour chaque tuple, charger une page, donc il faut lire une

page pour chaque tuple de la table employé :


Réda DEHAK 442

Comparaison

DP(R+0.125)2DDP ( R + 0.125 )

Non plaçant, hash

D ( logF(1.5P) + 0.15 T0 / R

+ T0)

D(1+ logF(1.5P))

DP ( R + 0.15 )


D ( logF(1.5P) + 1.5 T0 / R )DlogF(1.5P)1.5DPIndexe

plaçant

D ( log2(P) + T0 / R )

Dlog2(P)DPTrié

DP0.5DPDPTas


Réda DEHAK 443

INSERT

INSERT INTO Emp VALUES(42, ‘Dubois’, ‘Alain’, 42, 2500);

1. Tas :– Il faut lire la dernière page du tas :

Nombre de page à lire : 1 – Il faut écrire la page mémoire après modification

Nombre de page à écrire : 1 Coût : 2D

2. Fichier trié :– On cherche l’endroit où il faut insérer le tuple (coût identique à une recherche).– On insère le tuple en décalant tous les autres d’une case sur la page courante et

sur les pages consécutives.

Nombre de page traiter en moyenne : P/2Coût : Recherche + DP

Réda DEHAK 444

BETWEEN

3. Indexe plaçant :– On cherche l’endroit où il faut insérer le tuple (coût identique à une

recherche).– On insère le tuple et on écrit la nouvelle page :

Coût : Recherche + D4. Indexe B-TREE non plaçant :

– On cherche l’endroit où il faut insérer le tuple (coût identique à une recherche).

– On insère le tuple dans l’indexe et dans la page de données :

Coût : Recherche + 2D

Réda DEHAK 445

BETWEEN

5. Indexe hash non plaçant :– On cherche l’endroit où il faut insérer le tuple (coût identique à une

recherche).– On insère le tuple dans l’indexe et dans la page de données :

Coût : Recherche + 2D

Réda DEHAK 446

Comparaison

Search + 2DDP(R+0.125)2DDP ( R +

0.125 )Non plaçant,

hash

Search +2DD ( logF(1.5P) + 0.15 T0 / R

+ T0)

D(1+ logF(1.5P))

DP ( R + 0.15 )


Search +DD ( logF(1.5P) + 1.5 T0 / R )DlogF(1.5P)1.5DPIndexe

plaçant

Search + DP

D ( log2(P) + T0 / R )

Dlog2(P)DPTrié

2DDP0.5DPDPTas


Réda DEHAK 447

Comparaison

Search + 2DSearch + 2DDP(R+0.125)2DDP ( R +

0.125 )Non plaçant,

hash

Search + 2DSearch +2DD ( logF(1.5P) + 0.15 T0 / R

+ T0)

D(1+ logF(1.5P))

DP ( R + 0.15 )


Search + DSearch +DD ( logF(1.5P) + 1.5 T0 / R )DlogF(1.5P)1.5DPIndexe

plaçant

Search + DPSearch + DP

D ( log2(P) + T0 / R )

Dlog2(P)DPTrié

Search + D2DDP0.5DPDPTas


Réda DEHAK 448

Conclusion

• Les méthodes d’indexation ont des avantages et des inconvénients.

• Il faut choisir le type d’indexes qui est le plus favorable pour les traitement qu’on veut faire.

Réda Dehak [email protected]

Réda DEHAK 451

Traitement des requêtes

Requête

Plan d’exécution

Plan d’exécution : définit l’ensemble des opérations (algorithmes) à exécuter pour déterminer la réponse

Optimisation des requêtes Le meilleur plan

Réda DEHAK 452

Exemple

Select B,DFrom R,SWhere R.A = “c” ∧ S.E = 2 ∧ R.C=S.C

R A B C S C D E

a 1 10 10 x 2

b 1 20 20 y 2

c 2 10 30 z 2

d 2 35 40 x 1

e 3 45 50 y 3Réponse B D

2 x

Réda DEHAK 453

Comment?

• Idées :1. Faire un produit cartésien

Sélectionner les tuplesFaire une projection

RXS R.A R.B R.C S.C S.D S.E

a 1 10 10 x 2

a 1 10 20 y 2. . . . . .. . . . . .

C 2 10 10 x 2. . . . . .. . . . . .

Réda DEHAK 454

Description des plans

• Algèbre relationnel :

x

R.A = “c” ∧S.E = 2 ∧R.C=S.C

B,D

R S

ΠB,D [ σR.A=“c”∧ S.E=2 ∧ R.C = S.C (RXS)]

Réda DEHAK 455

Plan II

B,D

R S

R.A = “c” S.E = 2

PB,D [ Join ( σR.A="c" ( R ) , σS.E=2 ( S ) ) ]

Réda DEHAK 456

Plan II

R S

A B C σ (R) σ(S) C D E

a 1 10 A B C C D E 10 x 2

b 1 20 c 2 10 10 x 2 20 y 2

c 2 10 20 y 2 30 z 2

d 2 35 30 z 2 40 x 1

e 3 45 50 y 3

B D2 x

Réda DEHAK 457

Plan III

• Utilisation des indexes sur R.A et S.C(1) Utiliser l’indexe sur R.A pour sélectionner les tuples de R vérifiant R.A

= "c"

(2) Utiliser l’indexe sur S.C pour sélectionner les tuples correspondants àchaque tuple de R.

(3) Éliminer les tuples tel que S.E ∫ 2

(4) Faire la jointure

(5) Projeter sur B,D

Réda DEHAK 458

Plan III

R S

A B C C D E

a 1 10 10 x 2

b 1 20 20 y 2

c 2 10 30 z 2

d 2 35 40 x 1

e 3 45 50 y 3

A CI1 I2

=“c”

<c,2,10> <10,x,2>

check=2?

output: <2,x>

next tuple:<c,7,15>

Réda DEHAK 459

Problèmes

• Pour chaque requêtes :– Comment déterminer un plan d’exécution?

– Comment évaluer le coût de chaque plan?

• Idéalement : trouver le meilleur plan

• Pratiquement : éviter les mauvais plans

• Les algorithmes utilisés pour évaluer une opération de base

Réda DEHAK 460

Plan

• Exécution d’une requête– Étude des différents algorithmes

• Compilation des requêtes :– Déterminer un plan logique.

– Déterminer le meilleur plan physique.

Réda DEHAK 461






Récupération




Évaluation des

requêtes


Requêtes SQL

Réda DEHAK 462

Évaluation d’une requête

• Les principales composantes du query processor

Requête SQL

Parser

Détermination du meilleur plan logique

Détermination du meilleur plan physique

Plan d’exécution

Arbre syntaxique

Arbre correspondant au plan logique

Arbre correspondant au plan physique

Réda DEHAK 463

Opérations

LC

Sélection Projection Produit cartésien

Union

∪

Différence

-

Jointure

C

Intersection

∩

x

Renommage

L

Réda DEHAK 464

Opérateurs supplémentaires

• Élimination des doublons :δ : transformer le multi-set en ensemble.

• Grouperγ Liste : La liste permet de spécifier les attributs du groupe ainsi que les différents opérateurs d’agrégation.

• Tri :Sortliste_attributs

Réda DEHAK 465

Exemples

Select nomrea, min(année) as minannéeFrom filmGroup by nomreaHaving count(titre) >= 3

Pnomrea,minanne ( σcttitre>=3[ γnomrea,

min(année) minannée, count(titre) cttitre(film) ] )

Réda DEHAK 466

Exemples

Select distinct nomreaFrom film

δ [ Pnomrea ( film ) ]

Pnomrea ( δ (film) )

∫

Réda DEHAK 467

Classification des algorithmes

1. Algorithmes en 1 passe2. Algorithmes en 2 passes3. Algorithmes en multi-passes

1. Méthodes classiques2. Méthodes fondées sur le tri3. Méthodes fondées sur le hachage4. Méthodes fondées sur les indexes

Réda DEHAK 468

Comparaison

Search + 2DSearch + 2DDP(R+0.125)2DDP ( R + 0.125 )

Non plaçant, hash

Search + 2DSearch +2DD ( logF(1.5P) + 0.15 T0 / R

+ T0)

D(1+ logF(1.5P))

DP ( R + 0.15 )


Search + DSearch +DD ( logF(1.5P) + 1.5 T0 / R )DlogF(1.5P)1.5DPIndexe

plaçant

Search + DPSearch + DP

D ( log2(P) + T0 / R )

Dlog2(P)DPTrié

Search + D2DDP0.5DPDPTas


Réda DEHAK 469

Étude des performances

• Card( R ) : nombre de tuples de la table R• B( R ) : nombre de blocs physique de la table R.• Card( R, A ) : nombre de valeurs différentes contenues

dans R pour l’attribut (s) A.• M : nombre de blocs mémoires nécessaire.

Méthodes classiques

Réda DEHAK 471

Algorithme en 1 passe pour les opérateurs unaires

1. Un tuple à la fois :

R

Opérateur

unaire

Buffer d’entrée Buffer de sortie

Sélection

Projection

Condition M = 1

Nbre I/O : B( R )

Réda DEHAK 472

Algorithme en 1 passe pour les opérateurs unaires

• Élimination des doublons :

R

Déjà VU?

Buffer d’entréeBuffer de sortie

M-1 buffers

Condition B(δ (R) ) < M

Nbre I/O : B( R )

Réda DEHAK 473

Grouper γ

R

Groupe déjà vu?

Buffer d’entrée M-1 buffers

Condition B(δ (P<> ( R )) ) < M

Nbre I/O : B( R )

Réda DEHAK 474

Algorithme en 1 passe pour les opérateurs binaires

• Union :– Multiset : Évidente (M=1, B(R) + B(S))– Ensemble.

• Intersection (Multiset, Ensemble).• Différence (Multiset, Ensemble).• Produit cartésien.• Jointure.

Réda DEHAK 475

Algorithme en une passe

Idée : Charger la petite table entièrement en mémoire.

R & S

Si

R

M main memory buffersDisk

Output buffer

Traitement

Réda DEHAK 476

Algorithme en 1 passe pour les opérateurs binaires

• Union :– Multiset : Évidente (M=1, B(R) + B(S))– Ensemble.

• Intersection (Multiset, Ensemble).• Différence (Multiset, Ensemble).• Produit cartésien.• Jointure.

Condition Min( B(S), B(R) ) < M

Nbre I/O : B( R ) + B(S)

Réda DEHAK 477

Exemple : jointure

• 2 boucles imbriquées (tuples): Join(R(X,Y), S(Y,Z))

For EACH tuple s IN S DOFOR EACH tuple r IN R DO

IF r.Y == s.Y thenoutput join(r,s)

Réda DEHAK 478

Algorithme en :une passe sur R

Plusieurs passe sur S

R & S

Lecture de toutes les

pages de S

R


Output buffer

Réda DEHAK 479

Exemple : jointure

• 2 boucles imbriquées (tuples): Join(R(X,Y), S(Y,Z))

For EACH tuple s IN S DOFOR EACH tuple r IN R DO

IF r.Y == s.Y thenoutput join(r,s)

Condition M=2

Nbre I/O : B( R ) * B(S)

Réda DEHAK 480

Exemple : jointure

• 2 boucles imbriquées (blocs) :Join(R(X,Y), S(Y,Z))

Idée : utiliser toute la mémoire disponible pour faire la jointuredécomposer S en plusieurs relations Si (i=1..n) de taille (M-1) blocs

FOR EACH i IN [1..n] DOlire Si en mémoire (rajouter une structure de recherche pour accélérer la suite) FOR EACH bloc b OF R DO

lire b en mémoireFOR EACH tuple t OF b DO

Rechecher les tuples de Si (en mémoire) qui match avec t output join(r,s)

Réda DEHAK 481

Algorithme en :une passe sur R

Plusieurs passes sur S

R & S

Lecture de tous Rj

Si


Output buffer

Réda DEHAK 482

Exemple : jointure

• 2 boucles imbriquées (blocs): Join(R(X,Y), S(Y,Z))

Idée : utiliser toute la mémoire disponible pour faire la jointuredécomposer S en plusieurs relations Si (i=1..n) de taille (M-1) blocs

FOR EACH i IN [1..n] DOlire Si en mémoire (rajouter une structure de recherche pour accélérer la suite) FOR EACH bloc b OF R DO

lire b en mémoireFOR EACH tuple t OF b DO

Rechecher les tuples de Si (en mémoire) qui match avec t output join(r,s)

Condition M>=2

Nbre I/O : B( R ) * B(S) / (M-1)

Réda DEHAK 483

Conclusion

B(R) B(S) /(M-1)∀ ≥ 2Join

B(R) + B(S)Min(B(R), B(S))», …, -, x, Join

BBγ, δ

B1σ, P

I/OM nécessaireOpérateurs

Réda DEHAK 484

Algorithme en 2 passes fondés sur les méthodes de tri

• Les données sont lues une première fois :

– Elles sont traitées en mémoire

– Transférer vers le disque

• Les données sont lues une deuxièmes fois pour calculer

le résultat

Réda DEHAK 485

Exemples : tri en 2 passes

• Tri fusion :1. On subdivise R en plusieurs sous ensembles Ri (i=1..n)2. On trie indépendamment chaque sous relation Ri

3. On fusionne toute les sous relations triées

Réda DEHAK 486


R

M buffers

Trier en fusionnant

Réda DEHAK 487


• Tri fusion :1. On subdivise R en plusieurs sous ensembles Ri (i=1..n)2. On trie indépendamment chaque sous relation Ri

3. On fusionne toute les sous relations triées

Condition B( R ) <= M2

Nbre I/O : 3 B( R )

Réda DEHAK 488

Applications

• L’algorithme peut calculer le résultat des deux opérateurs δ, γ, en modifiant la deuxième phase.

Condition B( R ) <= M2

Nbre I/O : 3 B( R )

Réda DEHAK 489

Opérateurs binaires

Union :• Première phase :

– Trier chaque sous relation Ri (taille M blocs) de R en mémoire.– Trier chaque sous relation Sj (taille M blocs) de S en mémoire.

• Deuxième phase :– Lire un bloc de chaque sous relation Ri et Sj en mémoire.– Faire l’union en traitant chaque bloc.

Idem pour … , - , Join

Réda DEHAK 490

Jointure en 2 passes fondés sur les méthodes de tri

deuxième phase

Sorted partitionsof R & S


Output buffer

Disk

Join Result

Ri

Si

Réda DEHAK 491

Opérateurs binaires

Union :• Première phase :

– Trier chaque sous relation Ri (taille M blocs) de R en mémoire.– Trier chaque sous relation Sj (taille M blocs) de S en mémoire.

• Deuxième phase :– Lire un bloc de chaque sous relation Ri et Sj en mémoire.– Faire l’union en traitant chaque bloc.

Condition B( R ) + B(S) <= M2

Nbre I/O : 3 [ B( R ) + B(S) ]

Idem pour … , - , Join

Réda DEHAK 492

Conclusion

5(B(R) + B(S))Join

3(B(R) + B(S))», …, -, x, Join

3Bγ, δ


B

)()( SBRB +

( ))(),( SBRBMAX

Réda DEHAK 493

Algorithme en 2 passes fondés sur les méthodes de hachage

Idée : Partitionner R en (M-1) sous relation avec une fonction de hachage

M main memory buffers DiskDisk

Original Relation OUTPUT

2INPUT

1

hashfunction

h M-1

Partitions

1

2

M-1

. . .

Réda DEHAK 494

Algorithme en 2 passes fondés sur les méthodes de hachage

Idée : Partitionner R en (M-1) sous relation avec une fonction de hachage

Partitionsof R & S

Input bufferfor Si

Hash table for partitionRi (k < B-1 pages)

B main memory buffersDisk

Output buffer

Disk

Join Result

hashfnh2

h2

Réda DEHAK 495

Conclusion

3(B(R) + B(S))», …, -, x, Join

Join (M>>k)

3Bγ, δ


B

))(),(( SBRBMIN

))(),(( SBRBMIN ( ))()())(),((

23 SBRBSBRBMIN

M+⎟⎟

⎠

⎞⎜⎜⎝

⎛−

Réda DEHAK 496

Multi-passes

• Algorithme récursif :– Si B( R ) ≤ M alors charger R en mémoire et effectuer le tri– Sinon partitionner R en M relations R1,…,RM :

• Trier récursivement chaque Ri.• Fusionner le résultat

Condition B( R ) <= Mk

Nbre I/O : (2k-1) B( R )

Réda DEHAK 497

Généralisation

(2k – 1) (B(R) + B(S))», …, -, x, Join

(2k-1)Bγ, δ


k B

k SBRBMIN ))(),((

Réda DEHAK 498

Conclusions

(2k – 1) (B(R) + B(S))», …, -, x, Join

(2k-1)Bγ, δ


k B

k SBRBMIN ))(),((

3(B(R) + B(S))», …, -, x, Join

3Bγ, δ


B

))(),(( SBRBMIN

Réda DEHAK 499

Plan

• Exécution d’une requête– Étude des différents algorithmes

• Compilation des requêtes :– Déterminer un plan logique.

– Déterminer le meilleur plan physique.

Réda DEHAK 500

Construction de l’arbre correspondant au plan logique

Parser

Préprocesseur

Génération du plan logique

Réécriture

Requête

Meilleur plan logique

Réda DEHAK 501

Construction

SELECT AFROM <list_B>WHERE CGroup by DHAVING E

A

x

List_B

C

γD+attr(E)

E

Réda DEHAK 502

Comparaison des plans

x

R.A = “c” ∧S.E = 2 ∧R.C=S.C

B,D

R S

B,D

R S

R.A = “c” S.E = 2

Réda DEHAK 503

Optimisation de l’algèbre relationnel

• Règles de transformations (préserver l’équivalence) :– Propriétés mathématiques des opérateurs.

• Quelle sont les bonnes transformations?

Réda DEHAK 504

Jointure

R S = S R(R S) T = R (S T)

R S S T

T R

Réda DEHAK 505

Produit cartésien et Union

• R x S = S x R• (R x S) x T = R x (S x T)

• R U S = S U R• R U (S U T) = (R U S) U T

Réda DEHAK 506

Sélection

σp1 [ σp2 (R)] = σp2 [ σp1 (R)]

σp1∧p2(R) = σp1 [ σp2 (R)]

σp1vp2(R) = [ σp1 (R)] U [ σp2 (R)]

Réda DEHAK 507

Projection

• Soit :– X un ensemble d’attributs– Y un ensemble d’attributs

PXY(R) ∫ PX [ PY (R) ]PX [ PY (R) ] = PX (R)

Réda DEHAK 508

Sélection, jointure

• p = prédicat avec que des attributs de R

q = prédicat avec que des attributs de S

m= prédicat avec des attributs de R et S

• σ p (R S) = [σp (R)] S

• σ q (R S) = R [σq (S)]

Réda DEHAK 509

Sélection, jointure

• σ p∧q (R S) = [σp (R)] [σq (S)]

• σ p∧q∧m (R S) = σm [ σp (R) σq (S)]• σ p∨q (R S) = [σp (R) S]

» [R σq (S)]

Réda DEHAK 510

Sélection, projection

• Soit :– x un sous ensemble d’attributs de R– z l’ensemble des attributs utilisés pour prédicat P (sous

ensemble des attributs de R)

Px [σp (R)] = Px { σp [ Pxz (R) ] }

Réda DEHAK 511

Projection, jointure

• Soit :– x un sous ensemble d’attributs de R– y un sous ensemble d’attributs de S.– z l’intersection des attributs de R et de S.

Pxy [R S] = Pxy { [Pxz (R)] [Pyz (S)] }Pxy [σp (R S)] =

Pxy {σp [Pxz’ (R) Pyz’ (S)] }z’ = z » attributs de P

Réda DEHAK 512

Sélection, union, différence

Union :σp (R » S) = σp (R) » σp (S)

Différence :σp (R - S) = σp (R) – S

= σp (R) - σp (S)

Réda DEHAK 513

Les transformations

1. Faire descendre les sélections :– σp1∧p2 (R) σp1 [ σp2 (R) ]– σp1 [ σp2 (R) ] σp2 [ σp1 (R) ]– σp [ R S ] [ σp (R) S]

2. Faire descendre les projections :– Px [σp (R)] Px { σp [ Pxz (R) ] }– Px [R S] Px { [ Pxz (R) ] [ Pxz (S) ]}

Réda DEHAK 514

Exemples(1)

• Soit le schéma relationnel suivant :EMP(eid, did, sal, adresse)Dept(diddid, dnom, etage, tel)Budget(diddid, budget, dépenses, bénéfices)

Soit la requête suivante :SELECT D.dnom, B.budgetFROM Emp E, Dept D, Budget BWHERE E.did = D.did AND D.did = B.did AND

D.etage = 1 AND E.sal >= 59000 ANDE.adresse = ‘PARIS’

Réda DEHAK 515

Exemples(2)

On donne les informations suivantes :– Employe(nom, grade, d_nom, adresse)– Le nom de l’employé est une clé candidate– La relation contient 10000 pages : B(employe)=10000– M = 10

Réda DEHAK 516

suite

1) Soit la requête suivante :SELECT grade, nom from personne where grade = ‘ING’On suppose que 10% des tuples de personne vérifient cette condition

a) En supposant qu’il existe un indexe B+tree plaçant sur l’attribut grade, donnez le coût (nombre d’E/S) du meilleur plan?

b) Idem avec un indexe non plaçant?c) Idem avec un indexe plaçant sur l’attribut nom?d) Idem avec un indexe non plaçant sur l’attribut nom?

Réda DEHAK 517

suite

2) Soit la requête suivante :SELECT nom from personne where grade = ‘ING’ and d_nom = ‘Prod’

On suppose que :• 10% des tuples de personne vérifient la condition (grade = ‘ING’)• 20% des tuples de personne vérifient la condition (d_nom = ‘Prod’)• 5% des tuples de personne vérifient la condition du select

a) En supposant qu’il existe un indexe B+tree plaçant sur l’attribut grade (l’unique indexe), donnez le coût (nombre d’E/S) du meilleur plan?

b) Idem avec un indexe plaçant sur d_nom?c) Idem avec un indexe plaçant sur les attributs (grade, d_nom)?d) Idem avec un indexe plaçant sur les attributs (grade, nom)?e) Idem avec un indexe plaçant sur les attributs (d_nom, grade, nom)?f) Idem avec un indexe plaçant sur les attributs (nom, grade, d_nom)?

Réda DEHAK 518

Suite

3) Soit la requête suivante :SELECT grade, count(*) from personne group by grade

a) En supposant qu’il existe un indexe B+tree plaçant sur l’attribut grade, donnez le coût (nombre d’E/S) du meilleur plan?

b) Idem avec un indexe non plaçant?c) Idem avec un indexe plaçant sur l’attribut nom?d) Idem avec un indexe plaçant sur les attributs (nom, grade)?e) Idem avec un indexe plaçant sur les attributs (grade, nom)?

Réda DEHAK 519

suite

4) Soit la requête suivante :SELECT grade, count(*) FROM personne WHERE d_name > ‘W’ group by grade

On suppose que 10% des tuples d’employe vérifient la condition du wherea) En supposant qu’il existe un indexe B+tree plaçant sur l’attribut grade, donnez

le coût (nombre d’E/S) du meilleur plan?b) Idem avec un indexe non plaçant?c) Idem avec un indexe plaçant sur l’attribut d_nom?d) Idem avec un indexe plaçant sur les attributs (d_nom, grade)?e) Idem avec un indexe plaçant sur les attributs (grade, d_nom)?

Réda DEHAK 520

Exemples(3)

• Soit le schéma relationnel suivant :EMP(eid, did, sal, adresse)Dept(diddid, dnom, etage, tel)Budget(diddid, budget, dépenses, bénéfices)

Soit la requête suivante :SELECT D.dnom, B.budgetFROM Emp E, Dept D, Budget BWHERE E.did = D.did AND D.did = B.did AND

D.etage = 1 AND E.sal >= 59000 ANDE.adresse = ‘PARIS’

Réda DEHAK 521

Questions

1. Donner l’arbre optimisé de cette requête?2. Quelles sont les possibilités pour l’ordre des jointures possibles3. Supposant qu’on dispose des informations suivantes :

• indexe b+tree non plaçant sur Emp.did, Emp.sal, Dept.etage, Dept.did, Budget.did.

• Min(Emp.sal)=10000, Max(Emp.sal)= 60000.• Card(Employe, Adresse) = 200.• L’entreprise est sur 2 étages.• On a 50000 employés et 5000 départements.a) Pour chaque nœud de l’arbre, donner une estimation du nombre de tuples de la

table?b) Donner l’ordre optimal des jointures?


Réda DEHAK 523

Plan

• Transactions : Définitions et propriétés.• Journalisation et la gestion de pannes.• Gestion de la concurrence.• Transaction en SQL.

Réda DEHAK 524

Définitions

Ensemble d’actions qui réalisent des transformations cohérentes de la base de données.

Base de données dans un état

cohérent

Base de données dans un état

cohérent

Début de la transaction

Fin de la transaction

Exécution

La BD peut être dans un état incohérent

Réda DEHAK 525

• Beaucoup d'opérations sur une BD doivent être atomiques :– Exemple : Transfert d'argent entre deux comptes:

UPDATE CompteSET Val = Val -100WHERE Nc = 10723UPDATE CompteSET Val = Val + 100WHERE Nc = 10845

• Si seulement une de ces requêtes est exécutée, la BDperd sa consistance

Définitions

Réda DEHAK 526

Syntaxe

Une transaction est délimitée par « BEGIN TRANSACTION » et « END TRANSACTION », elle comporte :

– Des opérations de lecture (SELECT) ou d’écriture (UPDATE) de la BD.

– Des opérations de manipulation (calculs, tests, etc…)– Des opérations transactionnelles : COMMIT, ROLLBACK

Réda DEHAK 527

Exemple

BEGIN TRANSACTIONUPDATE CompteSET Val = Val -100WHERE Nc = 10723;

IF SQLCODE <> 0 ROLLBACK ;UPDATE CompteSET Val = Val + 100WHERE Nc = 10845;

IF SQLCODE <> 0 ROLLBACK ;

END TRANSACTION;

Réda DEHAK 528

Propriétés des transactions

• Exécution Atomiques d’une suite d’opérations inexprimables avec une seule requête relationnelle.– entièrement ou pas du tout.

• préservant la Cohérence de la BD• comme si l'usager était Isolé sur la BD

– Pas d’accès concurrent.

• à effet Durable sur la BD, une fois terminées comme prévu

Modèle ACID de transactions

Réda DEHAK 529

Propriétés des transactions

Les transactions fournissent :

– L’exécution atomique et fiable en présence de pannes.

– L’exécution correcte en présence d’utilisateurs concurrents.

Réda DEHAK 530

Implémentation des transactions

Problème :

Comment maintenir– Atomicité– Durabilité– Isolation

des transactions.

Et les pannes?

Réda DEHAK 531

Type de pannes

1. Panne de transactions– Abandon (normal ou du à un deadlock)– Pratique : En moyenne 3% des transactions abandonnent

anormalement

2. Panne système– Panne matérielle : processeur, mémoire, alimentation…– Perte du contenu de la mémoire principale : coupure

d’électricité.

3. Panne disque– Panne de tête de lecture ou du contrôleur disque– Perte des données de la BD sur dique.

Réda DEHAK 532

Implémentation des transactions

• TID : Identificateur de transaction• Inscription dans la BD seulement après le COMMIT• Journalisation :

– Toute opération d'une transaction est notée avant et après l'exécution dans un fichier journal présumé à l'abris de pannes

– Les opérations de commit sont notées avant d'être exécutéessur la BD (write-ahead log protocol)

• Points de reprise (checkpoints)– sauvegardes de l'état de la BD et notamment de TIDs de

transactions en cours à intervalles réguliers

Réda DEHAK 533

Architecture

Gestion de pannes

Gestion de cache BDBDstable

Commandes transactionnelles

Mémoire principale

Cache BD

LectureÉcriture

LectureÉcriture

Réda DEHAK 534

Stratégies de MAJ

• MAJ en place :– Chaque MAJ implique la modification des données

dans les pages du cache de la BD.– L’ancienne valeur est écrasée par la nouvelle

• MAJ hors place :– Les nouvelles valeurs de données sont écrites

séparément des anciennes dans des pages ombres– Peu utilisé en pratique car très coûteux

Réda DEHAK 535

Journal de la BD

Chaque action d’une transaction doit réaliser le traitement demandé, ainsi qu’écrire un enregistrement dans le journal

ModificationAncien état de

la BDNouvel état

de la BD

Journal de la BD

Et si la panne arrive …

Réda DEHAK 537

Reprises sur pannes

• Panne régulière– reprise à partir du journal et du checkpoint

• Panne catastrophique– reprise à partir d'une sauvegarde (copie globale) de la

BDReprise a froid (règle générale)– l'accès des usagers à la base est arrêté

Reprise A chaud– l'accès à la base continue

Réda DEHAK 538

Principes

Une transaction = unité de reprise– l'effet de toute transaction commise doit être restauré

– l'effet de toute transaction avortée doit être annulé

Le journal (log file) doit survivre aux pannes– bande ou disque

Réda DEHAK 539

Articles du journal

• TID (début)• TID (commit/abort)• TID, Op, TupleId, ImageAvant, ImageAprès

– ImageAvant = Null pour un Insert– ImageAprès = Null pour un Delete

• Checkpoint record– timestamp t – copie du cache au moment t– TIDs des transactions en cours au moment t

Réda DEHAK 540

Exemple de journal

Début du journal T1, beginT1, maj, x, 99, 100T2, beginT2, maj, y, 199, 200T3, beginT3, maj, z, 51, 52T2, maj, w, 1000, 10T2, commitT4, beginT3, abortT4, maj, x, 100, 200T5, beginT5, maj, w, 10, 200

Fin du journal T2, commit

Réda DEHAK 541

L’utilité du journal

tempsCheckpoint

begin end

begin

T1

T2

begin endT3

begin T4

PanneLors de la reprise :

– Toute les MAJ de T1 et T2 effectuée après le checkpoint doivent être faite dans dans la BD (REDO)

– Aucune MAJ de T2 et T4 ne doit être faite dans la BD (UNDO)

Réda DEHAK 542

Et si la panne arrive...

• On ferme l'accès à la base (reprise à froid)• On reprend le dernier checkpoint• On retrouve sur le journal toutes les transactions ayant

exécutées le commit avant la panne et ayant commencées avant ou après le checkpoint

• On reexécute chronologiquement ces transactions– et seulement ces transactions

• On retrouve sur le journal toutes les transactions qui n’ont pas commité avant la panne et ayant commencées avant le checkpoint

• On annule chronologiquement ces transactions.• On ouvre la base aux usagers

Réda DEHAK 543

Algo général de reprise

• on trouve le dernier checkpoint• on restaure le cache• on crée deux listes vides UNDO et REDO• On lit le journal en arrière, et la liste des TIDS dans

l'article checkpoint :– si Commit T, alors REDO := REDO + T ;– si Abort T, alors UNDO := UNDO + T ;– si Begin T et T ∉ REDO, alors

UNDO := UNDO + T ;• Défaire les transactions dans UNDO• Refaire les transaction dans REDO

Réda DEHAK 544

Gestion du journal

Gestion de reprise

Gestion de cache BDBDstable

Mémoire principale

Cache BD

LectureÉcriture

LectureÉcriture

Cache journal

LectureÉcriture

Journal

Réda DEHAK 545

Quand faut il écrire le journal?

Supposons une transaction T qui modifie la page PCas chanceux ☺

– Le système écrit P dans la BD sur disque– Le système écrit le journal sur disque pour cette opération– PANNE !.........(avant la validation de T)On restore l’ancienne état de P à partir du journal

Cas malchanceux – Le système écrit P dans la BD sur disque– PANNE !.........(avant l’écriture du journal)

Nous ne pouvons pas récupérer car il n’y a pas d’enregistrement avec les anciennes images dans le journal

Solution : Le protocol Write-Ahead Log (WAL)

Réda DEHAK 546

Protocole WALRemarque :

– Si une panne précède la validation de transaction, alors toutes ses opérations doivent être défaites, en restaurant les images avant (partie undo du journal).

– Dès qu’une transaction a été validée, certaines de ses actions doivent être refaites, en utilisant les images après (partie redodu journal)

Protocole WAL :– Avant d’écrire dans la BD sur disque, la partie undo du

journal doit être écrite sur disque.– Lors de la validation de transaction, la partie redo du journal

doit être écrite sur le disque avant la validation

Réda DEHAK 547

Points de reprise (checkpoints)

Réduire la quantité de travail à refaire ou à défaire lors d’une panne

• Les checkpoints sont pris aux intervalles réguliers• Le checkpoint enregistre la liste des transactions actives• Poser un checkpoint :

– Écrire un enregistrement begin_checkpoint dans le journal.– Écrire les buffers du journal et de la BD sur le disque.– Écrire un enregistrement end_checkpoint dans le journal

Réda DEHAK 548

Conclusion

Le journal des transactions permet :– D’annuler une transaction non terminée (Atomicité)– Refaire une transaction qui a commité (Durabilité)

Comment assurer l’Isolation et la Cohérence des transactions?

Réda DEHAK 549

Solution

• Évidente :– Pas d’accès concurrent – Problème de performance

• Solutions :– Synchroniser les transactions concurrentes afin de maintenir la

cohérence de la BD, tout en maximisant le degré de concurrence (multi-utilisateur)

– Exécution simultanée des transactions pour des raisons de performance.

– Les résultats doivent être équivalents à des exécutions non simultanées (en série)

Comment?

Réda DEHAK 550

Exécution sérialisable

Les transactions s’exécutent simultanément, mais le résultat sur la BD est équivalent à une exécution en série

Exemples :T1 : L(X) T2 : E(X) T3 : L(x)

E(X) E(Y) L(y)Commit L(Z) L(z)

Commit CommitE1= L1(X), E1(X), C1, E2(X), E2(Y), L2(Z), C2, L3(X), L3(y), L3(Z),

C3.E2= E2(X), L1(X), E2(Y), E1(X), C1, L3(X), L3(y), L2(Z), C2, L3(Z),

C3E3= E2(x), L1(x), L3(x), E1(x), C1, L3(Y), E2(Y), L2(Z), C2, L3(Z), C3

Réda DEHAK 551

Actions permutables et exécutions équivalentes

• Deux actions de deux transactions différentes, consécutives dans une transaction, sont permutables si le résultat de l’ensemble des deux actions ne dépend pas de l’ordre dans lequel sont effectuées.– Deux actions sur deux granules différents sont toujours permutables.– Deux lectures sur le même granule sont permutables.– Une lecture et une écriture sur le même granule ne sont pas permutables.– Deux écritures sur le même granule ne sont pas permutables.

• Deux exécutions sont équivalentes si on peut passer de l’une àl’autre par une suite de permutations de deux opérations permutables.

Réda DEHAK 552

Exemple

E2= E2(X), L1(X), E2(Y), E1(X), C1, L3(X), L3(y), L2(Z),C2, L3(Z), C3

E2 = T2, T1, T3

Réda DEHAK 553

Graphe de précédence

• GPE = ( X, U) pour l’exécution E– X = { T | T est une transaction valide dans E }– U = { Ti Tj si oik ∈ Ti et ojl ∈ Tj sont en conflit et oik <E ojl }

• Deux opérations sont en conflit ssi :– Elles sont incompatibles (L/E ou E/L) et elles accèdent au même

granule.– Deux opération d’écriture sur le même granule (E/E)

(Deux actions non permutables)

Réda DEHAK 554

Exemples

E1= L1(X), E1(X), C1, E2(X), E2(Y), L2(Z), C2, L3(X), L3(y), L3(Z), C3.

X : L1, E1, E2, L3

Y : E2, L3

Z : L2, L3T1

T2

T3

X

X,Y

Réda DEHAK 555

Exemples

E2= E2(X), L1(X), E2(Y), E1(X), C1, L3(X), L3(y), L2(Z),C2, L3(Z), C3

X : E2, L1, E1, L3

Y : E2, L3

Z : L2, L3T1

T2

T3

X

YX

Réda DEHAK 556

Exemples

E3= E2(x), L1(x), L3(x), E1(x), C1, L3(Y), E2(Y), L2(Z), C2, L3(Z), C3

X : E2, L1, L3, E1

Y : L3, E2

Z : L2, L3T1

T2

T3

X

XX Y

Réda DEHAK 557

Graphe de précédence et exécution sérialisable

Théorème :L’exécution E est sérialisable ssi le graphe de précédence de E ne contient pas de circuit.

T1T2

T3

X

X,Y

T1T2

T3

X

YX

T1T2

T3

X

XX Y

Réda DEHAK 558

Problèmes de la concurrence• Perte d’opérations

T1

L(A)

W(A)

A := A * 10

T2

L(A)

W(A)

A := A + 10

Base

A = 100

A=100

A=100

A=110

A = 110

A=1000

A = 1000

Réda DEHAK 559

Problèmes de la concurrence• Non reproductibilité des lectures

T1

L(A)

T2

L(A)

W(A)

A := A + 10

Base

A = 100

A=100

A=100

A=110

A = 110

A=110 L(A)

Réda DEHAK 560

Problèmes de la concurrence• Introduction d’incohérence

T1

A := A * 10

T2

A := A + 10

Base

A = 10, B=10

A=100

A=110

A = 100, B=10

A = 110, B=10

B := B + 10A = 110, B=20

B := B * 10 A = 110, B=200B=200

B=20

Réda DEHAK 561

Problèmes de la concurrence• Lecture impropre

T1

L(A)

W(A)

A := A * 10

T2

L(A)

W(A)

A := A + 10

Base

A = 10

A=10

A=100

A=110

A = 100

A=100

A = 110Abort

Réda DEHAK 562


Deux solutions :1. Les verrous.2. Les estampilles.

Réda DEHAK 563

Gestion de la concurrenceSolution 1 : Verrou

• Verrouillage exclusif– toute opération d’écriture d'une transaction T sur une donnée

D ne peut se faire que si T obtient un verrou exclusif sur D– si D est déjà verrouillé par T' quand T le demande, alors T est

mise en attente

• Verrouillage partagé– toute opération de lecture d'une transaction T sur une donnée

D ne peut se faire que si T obtient un verrou partagé sur D– si D est déjà verrouillé par T' quand T le demande, alors :

• Si le verrou de T’ est exclusif alors T est mise en attente• Sinon T obtient son verrou partagé sur D

Réda DEHAK 564


T1

L(A)

W(A)

A := A * 10

T2

L(A)

W(A)

A := A + 10

Base

A = 100

A=100

A=100

A=110

A = 110

A=1000

A = 1000

Réda DEHAK 565


VX(A)

L(A)

W(A)

A := A * 10

VX(A)

L(A)

W(A)

A := A + 10

Base

A = 100

A=100 wait

A = 1000

A=1000

U(A)

Réda DEHAK 566

Est-ce que c’est suffisant?

T1

A := A * 10

T2

A := A + 10

Base

A = 10, B=10

A=100

A=110

A = 100, B=10

A = 110, B=10

B := B + 10A = 110, B=20

B := B * 10 A = 110, B=200B=200

B=20

Réda DEHAK 567

Verrouillage deux phases

1. Une transaction verrouille un objet avant de l’utiliser2. Quand un objet est verrouillé par une autre transaction,

la transaction qui demande doit attendre.3. Quand une transaction libère un verrou, elle ne peut

plus demander de verrou

temps

Nom

bre

de v

erro

us

Begin End

Phase 1 :

Obtention de verrousPhase 2 :

Libération de verrous

Réda DEHAK 568

Verrouillage deux phases strict

• On garde les verrous jusqu’à la fin (commit ou bien abort)

temps

Nom

bre

de v

erro

us

Begin End

Réda DEHAK 569

Verrouillage 2P et exécution sérialisable

Théorème :toute exécution de transaction respectant toutes le protocole de V2P est sérialisable.

Démonstration : par l’absurde

Problème des verrous : – Toutes les exécutions sérialisable ne sont pas en V2P– l’interblocage

Réda DEHAK 570

L’interblocage

Graphe des attentes :– Pour détecter la situation d’interblocage, on construit le

graphe des attentes. En cas de présence d’un circuit, on relance une transaction.

– Arcs du graphe : Si la transaction Ti attend qu’une autre transaction Tj libère un verrou sur un granule, alors Ti Tjest un arc du graphe des attentes

T1T2

Réda DEHAK 571

Solutions

1. Préventif : pas de circuitLes transaction sont numéroté par ordre de début. On donne la priorité aux transactions les plus anciennes. Deux possibilités d’implémentation Préemptif ou non.

Soit Ti désirant un verrou détenu par Tj• Préemptif : si Ti est plus ancienne que Tj, Ti prend le verrou et Tj est

abondonnée. Sinon, Ti attend.• Non préemptif : si Ti est plus ancienne que Tj, elle attend. Sinon elle

est abondonnée.Dans les deux cas , à chaque fois qu’on abandonne une transaction, on la relance avec le même numéro.

Inconvénient : Possibilité de défaire des transactions inutilement

Réda DEHAK 572

Solutions

2. Détection (utilisation du graphe des attentes):On laisse faire et on détecte les circuit. Dès qu’il y a interblocage, l’ordonnanceur choisi une victime àabandonner.

Critères : Nombre d’opérations effectuées, nombre d’opérations à effectuées …

Réda DEHAK 573

Sérialisation par estampillage

Principe : Prévention– Le choix de l’ordre des transactions est choisi avant

l’exécution.– Chaque transaction est étiquetée avec une estampille TS(T).– L’ordre des opérations de lecture et écriture sur un granule

doivent suivre l’ordre des estampille

Mécanisme :– A chaque granule on associe deux étiquettes, une étiquette de

lecture EL(G) et une étiquette écriture EE(g) :• EL(G) étiquette de la transaction la plus jeune à avoir lu g• EE(G) étiquette de la transaction le plus jeune ayant déjà écrit sur g.

Réda DEHAK 574

Règle de lecture et d’écriture

1. T demande de lire le granule x :a) TS(T) ≥ EE(x) : T est plus jeune que la dernière transaction ayant

modifiée la valeur de xLa lecture est acceptée et EL(x) Max( EL(x), TS(T) )

b) TS(T) < EE(x) : T est plus vielle que la dernière transaction ayant modifiée la valeur de xT arrive en retard sur le granule x, T est abondonnée.

2. T demande d’écrire le granule x :a) Si TS(T) ≥ EE(x) et TS(T) ≥ EL(x) : T est plus jeune que la dernière

transaction ayant lue ou bien modifiée la valeur de x.L’écriture est acceptée et on modifie l’’étiquette de EE(x) TS(T)

b) Sinon T arrive en retard sur le granule x, T est abondonnéeUne transaction abandonnée est relancée avec une nouvelle

estampille

Réda DEHAK 575

Estampillage et sérialisation

Théorème :Toutes exécution utilisant l’estampillage des transaction et respectant les deux règles de lecture et d’écriture est sérialisable.

Exemples :E2(X), L1(X), E2(Y), E1(X), L3(X), L3(y), L2(Z), L3(Z)L1(b), L2(b), E2(b), L1(a), L2(a), E2(a)

Réda DEHAK 576

Amélioration : règle de Thomas

L1(b), E2(b), L1(a), L2(a), E2(a), E1(b) ?

Modification de la règle d’écriture

Réda DEHAK 577

Règle de Thomas

• T demande d’écrire le granule x :a) Si TS(T) ≥ EE(x) et TS(T) ≥ EL(x) : T est plus jeune que la

dernière transaction ayant lue ou bien modifiée la valeur de x.

L’écriture est acceptée et on modifie l’’étiquette de EE(x) TS(T)

b) Si TS(T) < EE(x) et TS(T) ≥ EL(x) :On ne fait rien, cette écriture n’est pas utile. De toutes les façons, elle n’est jamais lue

c) Sinon T arrive en retard sur le granule x, T est abondonnée

Réda DEHAK 578

Amélioration : règle de Thomas

L1(b), E2(b), L1(a), L2(a), E2(a), E1(b)

Réda DEHAK 579

Niveaux d’isolation de SQL

• Lecture sale (dirty read) :cette anomalie se produit lorsqu'une transaction lis des données qui sont en train d'être modifiées par votre transaction (non encore validée).

• Lecture non répétable (nonrepeatable read) :cette anomalie survient si une requête ne renvoie pas les mêmes résultats lors d'exécutions successives. C'est le cas si les données que vous lisez sont modifiées par une autre transaction (c'est un peu l'inverse de la lecture impropre).

• Fantôme (phantom read) :cette anomalie se produit si des exécutions successives d'une même requête renvoient des données en plus ou en moins. Cela peut être le cas si une autre transaction est en train de supprimer ou d'ajouter des données àla table.

Réda DEHAK 580

Syntaxe

• BEGIN TRANSACTION [< trans_mod >]• trans_mod :

ISOLATION LEVEL { SERIALIZABLE | REPEATABLEREAD | READ COMMITTED | READ UNCOMMITTED} READ WRITE | READ ONLY

ImpossibleImpossibleImpossibleserializablePossibleImpossibleImpossiblerepeatable readPossiblePossibleImpossibleread committedPossiblePossiblePossibleread uncommitted

Phantom readNonrepeatablereadDirty readIsolation

Documents

Réda DEHAK [email protected]