Bases de donn ees avanc ees - grappa.univ-lille3.frgilleron/cours-bases-de-donnees-avanc... · Objectifs et organisation Objectifs du cours comprendre l’environnement informatique

Bases de donnees avancees

Remi Gilleron

Inria Lille - Nord Europe & LIFL & Univ Lille 3

septembre 2013

Remi Gilleron (Mostrare) Informatique M1 MIASHS septembre 2013 1 / 143

Objectifs et organisation

Objectifs du cours

comprendre l’environnement informatique des entreprises ;

connaıtre les concepts avances sur les bases de donnees relationnelles :optimisation, contraintes d’integrite et acces concurrents ;

connaıtre les autres modeles de donnees associes au decisionnel, auWeb et au“Big Data” : modele en etoile, modele cle-valeur, modelecolonne, modele document, modele graphe

Organisation du cours

12 seances de 2 heures


Plan

1 Systemes d’information

2 Bases de donnees relationnellesNotions fondamentalesCalcul relationnel et optimisation de requetes

3 Complements sur les BDs relationnellesSQL- Le langage de definition des donneesarchhitecture BDR – les utilisateurs, les droits, les vuesSQL- gerer la concurrence

4 Autres modeles de donneesDecisionnel et modele en etoileBig Data et bases NoSQLModeles NoSQL de donnees


Schema general

Le Systeme d’information (SI)

est la memoire de l’activite de l’entreprise,

est l’interface entre le systeme de pilotage et le systeme operant.

Le Systeme d’information (SI)

est constitue d’un systeme operationnel

et d’un systeme decisionnel,

il est desormais integre dans un systeme d’information et decommunication (SIC).


Informatique operationnelle 70 –

est axee sur la production, la memorisation et le traitement des donnees del’activite de l’entreprise. On peut distinguer :

l’aspect statique : enregistrement des donnees, faits, regles etcontraintes ;

l’aspect dynamique : mise a jour (ajout, modification et suppression)des donnees, faits, regles et contraintes.

Elle est centrale pour l’activite de l’entreprise et est organisee autour debases de donnees relationnelles avec les suites logicielles associees (SGBDRtels que Oracle) et le langage SQL.


Informatique decisionnelle 90 –

est axee sur l’aide a la decision.Les donnees sur l’activite issues du systeme operationnel et de sourcesexternes sont extraites, filtrees, historisees et traitees a l’aide d’outilsd’ETL (“Extraction Treatment Loading”) pour etre deposees dans desinfocentres et/ou des entrepots de donnees (datawarehouse).Ces donnees sont alors utilisees pour la production de syntheses et derapports afin de faciliter la prise de decision. Ceci a l’aide de suiteslogicielles telles que Business Object.


Systeme d’information et de communication 00 –

ne se contente plus de stocker, traiter et synthetiser les donnees pourl’activite de l’entreprise mais prend en compte les aspects decommunication : communication interne et externe de l’entreprise,echange de donnees informatisees (EDI) avec tous les partenaires, ...On parle d’Intranet, d’Extranet, de portail d’entreprise. Il concerne toutesles bases et entrepots de donnees l’entreprise mais aussi les bases dedocuments (gerees par des CMS “Content Management Systems”). Ilsutilisent les technologies Web.


Exemple d’une banque

le systeme operationnel va memoriser toutes les informations sur lesclients, leurs differents comptes et les operations sur ces comptes :debit, credit, virement, change, ... ; declencher des actions (envoi dereleves, ...) ; ...

le systeme decisionnel conserve sur une periode, par exemplemensuelle, le nombre d’operations, leur montant moyen, la moyennedes soldes sur les differents comptes, ... sur une duree historique deune ou plusieurs annees. Il dispose egalement d’informations (tres,trop) personnelles sur le client.

le systeme de communication met a disposition des clients un portaild’entreprise pour leurs activites : solde, virement, prets, ... ; il permetegalement des echanges avec les partenaires (mouvements financiers,virements internationaux, ...) ; ...


Conclusion

Existant

des systemes d’information et de communication contenant des bases dedonnees, des bases de documents et des entrepots de donnees. Lestechnologies sont eprouvees : technologies Internet, bases de donneesrelationnelles, systemes de gestion de contenus, entrepots de donnees etoutils de production de rapports.

Evolutions en cours

developpement des petits objets portables communicants et leurintegration dans le SIC avec images et videos,

developpement des capteurs et generation de flux de donnees(positionnement GPS, consommation electrique, ...)

des masses de donnees et le phenomene “Big Data” : cloud, gestionet traitement de donnees reparties, analyse de masses de donnees, ...


Plan






Bases de Donnees

Un systeme d’information est construit autour de volumes de donnees deplus en plus important. Ces donnees doivent etre stockees sur des supportsphysiques. Les donnees sont stockees et organisees dans des bases dedonnees – BD (databases – DB).Un utilisateur doit pouvoir les retrouver. Il faut pouvoir les interroger pardes requetes.Les donnees evoluent, il faut donc pouvoir les manipuler : ajouter,modifier, supprimer des donnees.Le logiciel de base qui permet de manipuler ces donnees est appele unsysteme de gestion de bases de donnees – SGBD (database managementsystem – DBMS).

Tout systeme d’information est construit autour de bases dedonnees


Exemple - BD gestion de commandes

Contenu : les clients, les produits, les prix, les fournisseurs, lafacturation, la livraison, ...

Applications : toutes les applications de gestion de l’entreprise,

Manipulation : par les services de l’entreprise mais aussi de l’exterieur(commandes par le site web, ...)

Variabilite : forte, des ajouts et modifications frequentes ;

Consultation : par les services de l’entreprise mais aussi de l’exterieur(suivi de commande, ...)


Exemple - BD et Web

Un site dynamique est construit sur une base de donnees.

l’utilisateur sollicite une page, la demande est envoyee au site, leserveur execute un programme,

les informations utiles sont extraites de la base de donnees etrapatriees au serveur,

une feuille de style est appliquee, un document html est construit etenvoye sur le reseau,

le document est affiche dans le navigateur de l’utilisateur.

l’interet est de distinguer les donnees des traitements et de l’affichage :pour modifier le contenu du site, il suffit de mettre a jour les informationsdans la base de donnees ; pour modifier la presentation, il suffit de modifierle style du document Web.


Fonctionnalites principales

BD

memoriser de grandes quantites de donnees essentielles a la vie del’entreprise,

les organiser, faciliter les requetes et permettre l’evolution,

donner l’acces a des applications diverses, a des utilisateurs differentsavec des modes d’acces varies.

SGBD

gerer le stockage sur des supports physiques eventuellement repartiset distants,

assurer la rapidite des acces, l’independance des donnees et desapplications,

assurer le controle de la concurrence car les donnees sont partagees etreparties,

assurer la protection des donnees : reprise sur panne, verifier les droitsd’usage et d’acces,


Le modele relationnel

Dans un contexte operationnel ou les donnees sont en volume important,ou les donnees evoluent, ou les utilisateurs sont nombreux avec des accesconcurrents, le modele de reference est

le modele relationnel base sur des tables verifiant des proprietes deforme normales implante dans

des systemes de gestion de bases de donnees relationnelles (SGBR telsque Oracle, PosGres, SQLite, ...) et utilisant

un langage d’interrogation standardise SQL et

des transactions verifiant les proprietes ACID : Atomicite, Coherence,Isolation et Durabilite.


Les relations

Un domaine est l’ensemble des valeurs que peut prendre une donnee.

Une relation (ou table) est un sous ensemble du produit des domainesqui porte un nom.

Un attribut est une colonne de relation caracterisee par un nom.

Une relation peut etre definie en extension par l’ensemble desenregistrements (lignes, tuples) constituant la relation a un instantdonne ou en intention par le schema de la relation qui contient lenom de la relation, la liste des attributs, le domaine de chaqueattribut et des contraintes d’integrite associees a la relation.

Toute relation possede une cle primaire qui est un attribut dont lavaleur est toujours definie et dont la valeur determine un et un seulenregistrement.


Les formes normales

Dependance fonctionnelle

Un modele relationnel est donc constitue de relations. Pour s’assurer quele modele est bien construit pour preserver la coherence des donnees, on adefini des formes normales.

Dependance fonctionnelle

Soit X et Y deux ensembles d’attributs, on dit que Y est en dependancefonctionnelle de X , note X → Y , si a toute valeur de X correspond auplus une valeur de YExemple : soit la relation PERSONNEL(Nom, Sexe, Age, Ville), on a :Nom → Sexe ; Nom → Age ; Nom → Ville ; Nom, Sexe → Ville ; Sexe6→ Age ; Sexe, Age 6→ Ville


Premiere et deuxieme formes normale

Definitions

Une relation est en premiere forme normale (1FN) si tous les attributssont en dependance fonctionnelle de la cle. Soit encore : tout attributa au plus une valeur et la valeur de la cle determine la valeur desautres attributs.

Une relation est en deuxieme forme normale (2FN) si elle est en 1FNet les dependances fonctionnelles liant la cle aux attributs sontelementaires : un attribut ne depend pas fonctionnellement d’unepartie de la cle.

Exemple

LIGNEARTICLE(numcommande, numproduit, quantite,

prixproduit) dont la cle est numcommande + numproduit n’est pas en2FN car prixproduit depend fonctionnellement de numproduit


Troisieme forme normale

Definition

Une relation est en troisieme forme normale (3FN) si elle est en 2FN et lesdependances fonctionnelles liant la cle aux attributs sont directes,c’est-a-dire ne peuvent etre obtenues par transitivite.

Exemples

PRODUIT(numproduit, ..., numfournisseur, nomfournisseur,

adressefournisseur, ...) de cle numproduit n’est pas en 3FN carnomfournisseur et adressefournisseur dependent fonctionnellementde numfournisseur.Une solution est d’eclater la relation en deux relations :la relation PRODUIT(numproduit, ..., numfournisseur) et la relationFOURNISSEUR(numfournisseur, nomfournisseur, adresse

fournisseur).


Conception de bases de donnees

Formes normales

un modele relationnel en forme normale 3FN assure la non-redondance desinformations pour conserver l’integrite de la BD au cours de son cycle devie. Il existe des formes normales plus strictes : Boyce-Codd, quatriemeforme normale, ...

Analyse

designe tout le travail de conception d’une base de donnees.

les methodes de conception (UML, Merise) ont pour objectif demodeliser des problemes reels pour construire des applications.

elles traitent de la modelisation des donnees et des traitements

le modele entite association (EA) permet de concevoir des basesrelationnelles en forme normale

elles sont decoupees en differentes phases : etude prealable dontanalyse de l’existant, etude detaillee, realisation et tests, implantationet formation.


BD relationnelle

Une base de donnees relationnelle est une base de donnees qui a etedefinie relativement au modele relationnel en satisfaisant lesproprietes de forme normale. La phase de conception est une tachecomplexe et de haut niveau.

une BD relationnelle est definie par un schema relationnel :I les relations (ou tables). Une relation est definie par la liste des

attributs, le domaine de chaque attribut, la precision de la cle primaire ;I les associations (ou jointures) naturelles entre les tables ;I les contraintes d’integrite : de domaine qui expriment des conditions

remplies par les valeurs d’un attribut, de structure sur les cles et dereference qui expriment des proprietes pour les associations et descontraintes liees a la denormalisation.


une BD simplifiee

CLIENTS(numclient, nom, prenom, ...)

COMMANDES(numcommande, datecommande, refclient, refvendeur)

LIGNECOMMANDES(refcommande, refproduit, quantite)

PRODUITS(numproduit, nom, couleur, ...)

VENDEURS(numvendeur, nom, prenom, ...)

contrainte de domaine : LIGNECOMMANDES.quantite est un entier >0

et <=100.contrainte de structure : LIGNECOMMANDES.refcommande +

LIGNECOMMANDES.refproduit est la cle primaire de LIGNECOMMANDES

contrainte de reference : COMMANDES.refclient toujours defini et refere aun client existant. COMMANDES.refvendeur peut etre non defini et s’il estdefini il refere a un vendeur existant.


BD en contexte reel

Considerations de volume

peut contenir plusieurs dizaines de tables, voire plusieurs centaines.Les noms des tables et des champs peuvent etre cryptiques ;

une table a en general plusieurs dizaines d’attributs, une table peutavoir de plusieurs milliers a plusieurs millions de lignes.

La vision utilisateur

un utilisateur ne voit, en general, qu’une partie de la base grace a desvues que l’on peut voir comme une requete qui vous montre unepartie comprehensible de la base de donnees

un utilisateur dispose alors de droits pour les actions de lecture(interrogation), d’ecriture (ajout, modification, suppression) sur leselements de la vue.


SGBDR

Le logiciel de base pour les BD relationnelles sont les systemes degestion de bases de donnees relationnelles – SGBDR .

Une BD relationnelle est geree par un administrateur (DBA – databaseadministrator).

Les principaux SGBDR sont : Access sur micro-ordinateurs ; Oracle,Informix, SQLserver en informatique de gestion d’entreprise ;SQLite, Posgres dans le monde du Web.

Le SGBDR gere le stockage physique, assure la rapidite des acces,l’independance des donnees et des applications, le controle de laconcurrence avec la gestion des transactions, assure la reprise surpanne et la verification des droits d’usage et d’acces.

Le SGBDR contient un moteur SQL


SQL : LE langage des bases de donnees relationnelles

Le besoin

de separer les donnees et les traitements pour manipuler

des bases de donnees complexes (un grand nombre de tables) etvolumineuses ;

dans des environnements heterogenes : materiels et logiciels.

SQL

il est normalise (normes SQL 2 et SQL 3) mais ... ;

c’est un langage algebrique base sur le calcul relationnel ;

c’est un langage declaratif : on decrit le resultat (pas l’algorithme) ;

il est compose de trois parties : le LDD : langage de definition desdonnees ; le LMD : langage de manipulation des donnees ; le LCD :langage de controle des donnees.


SQL - le langage de manipulation des donnees

Interroger une base de donnees relationnelle

avec SQL et l’instruction SELECT . C’est une instruction tres richepermettant la realisation de requetes complexes.

avec une interface graphique de conception des requetes. Mais, uneinterface repose sur un moteur SQL donc une requete SELECT SQL estgeneree.

L’instruction SELECT

SELECT

attributsexpressions extraitesFROM expressions de tablesWHERE conditions de filtrageGROUP BY conditions de groupe

HAVING conditions de filtrage sur les groupesORDER BY criteres de tri


ecrire une requete SQL avec un SELECT

Pre-requis

bien connaıtre le modele relationnel : tables, attributs, domaines desattributs, cles primaires et cles etrangeres ;

bien connaıtre sa semantique : dictionnaire des donnees, modelesentite-association et/ou UML.

Strategie d’ecriture

determiner les relations et les jointures a realiser dans la clause FROM

determiner les champs a afficher avec repetition ou pas ;

determiner les conditions limitant la recherche dans la clause WHERE ;

determiner les groupes et les conditions sur les resultats ;

pensez a comprendre les operations qui vont etre faites, pensez avalider la requete avec un expert du domaine en l’appliquant sur desexemples, sur une base simplifiee.


Plan






Comment un moteur SQL calcule une requete SQL ?

Moteur SQL

designe les processus qui transforment une requete SQL ecrite dans unlangage declaratif en un programme de calcul qui va prendre en entreel’etat courant de la base de donnees et va produire en resultat la relationresultat de la requete.

Exemple de requete et de calcul

SELECT c.numcommande, c.datecommande

FROM (COMMANDES c JOIN LIGNECOMMANDES l ON

c.numcommande=l.refcommande) JOIN

PRODUITS p ON l.refproduit = p.numproduit

WHERE p.couleur =’’rouge’’

Prendre des tables tres simples en exemple et reflechir a differentes faconspossibles de calculer la relation resultat.


Les operations du modele relationnel

Le calcul des requetes repose sur le calcul relationnel. Ce calcul est basesur 5 operations de base :

1 la projection ou selection verticale,

2 la selection ou selection horizontale,

3 le produit,

4 l’union,

5 la difference.

Ces operations peuvent etre combinees car elles portent sur des relationset produisent des relations permettant de definir le langage SQL qui est lelangage d’interrogation de BD relationnelle.


La projection

Definition

La projection ou selection verticale prend en entree une relation A et uneliste d’attributs de A et sort la relation restreinte a cette liste d’attributs.

Exemple

Etant donne la table PERSONNEL :

Dupont 1 35 Lille

Gilleron 1 38 Lomme

Lemoine 30 Leers

et la projection : AGES=PROJECT(PERSONNEL) OVER Nom, Age, on

obtient en resultat la relation :

Dupont 35

Gilleron 38

Lemoine 30


La selection

Definition

La selection ou selection horizontale prend en entree une relation et uneexpression logique portant sur des valeurs d’attributs et sort la relationrestreinte aux lignes qui satisfont l’expression logique (i.e. l’expressionlogique est vraie).

Exemple

Etant donne la table PERSONNEL :

Dupont 1 35 Lille

Gilleron 1 38 Lomme

Lemoine 30 Leers

la selection : SELECT PERSONNEL WHERE Ville = ‘‘Lille’’, produiten resultat la relation : Dupont 1 35 Lille

la selection : SELECT PERSONNEL WHERE Ville = ‘‘Lomme’’ or

Age=30, produit en resultat la relation :Gilleron 1 38 Lomme

Lemoine 30 Leers


Le produit (1)

Pourquoi des operations binaires

Les operations de selection horizontale et verticale sont des operationsessentielles ;

elles peuvent etre combinees ;

ce sont des operations unaires (sur une table) ;

cependant, nous avons vu que, pour obtenir un modele robuste, il etaitrecommande d’eclater en plusieurs relations. Par exemple :PRODUIT(numproduit, nomproduit, ..., numfournisseur)

FOURNISSEUR(numfournisseur, nomfournisseur, ...)

Il faut donc avoir egalement des operations binaires sur les relations.


Le produit (2)

Definition

Le produit est une operation binaire qui prend deux relations A et B enentree et produit en sortie la relation PRODUIT (A,B) ou A× B quicorrespond au produit cartesien.

Exemple

X 1

Y 5×

1 M xx

2 N yy

5 N zz

=

X 1 1 M xx

X 1 2 N yy

X 1 5 N zz

Y 5 1 M xx

Y 5 2 N yy

Y 5 5 N zz

Attention : la taille de A× B est le produit des tailles de A et B et10 000× 100 000 = 1 000 000 000.


L’union

Definition

L’union prend en entree deux relations de meme structure et sort unerelation de meme structure en effectuant l’union ensembliste des lignes desdeux relations. On ne repete pas deux fois des lignes identiques.

Exemple

1 M xx

2 N yy

5 N zz

∪3 P zz

2 N yy

7 Q xx

=

1 M xx

2 N yy

5 N zz

3 P zz

7 Q xx


La difference

Definition

La difference prend en entree deux relations de meme structure et sort unerelation de meme structure en prenant toutes les lignes de la premiererelation qui ne sont pas dans la seconde.

Exemple

1 M xx

2 N yy

5 N zz

3 P zz

7 Q xx

–1 M xx

7 Q xx=

2 N yy

5 N zz

3 P zz


La jointure (1)

Definition

La jointure est une operation fondamentale qui prend deux tables A et B,un attribut de A, un attribut de B et une condition logique liant unattribut de A et un attribut de B.Le resultat est une relation obtenue en juxtaposant les lignes de A et de Bpour lesquelles la condition est vraie.

Exemple

A JOIN B ON A.2=B.1

A :X 1

Y 5B :

1 M xx

2 N yy

5 N zz

X 1 M xx

Y 5 N zz


La jointure (2)

Fait

L’operation de jointure peut effectivement etre definie a partir de laselection (horizontale), de la projection (selection verticale) et du produit.A titre de verification par l’exemple, Considerons la jointure suivante :R(1,2,3,4) ← A(1,2) JOIN B(1,2,3) ON A.2=B.1

Elle peut etre definie par la sequence suivante : le produitC(1,2,3,4,5) ← PRODUIT(A,B)

suivi de la selection hrizontaleD(1,2,3,4,5) ← SELECT C WHERE C.2 = C.3

suivi de la projectionR(1,2,3,4) ← PROJECT D OVER D.1, D.2, D.4, D.5


Algebre relationnelle

Les cinq operations de projection, selection, produit, union etdifference permettent de definir un calcul sur les relations suffisantpour l’interrogation de modeles relationnels ;

Les relations et les operations forment l’algebre relationnelle

TOUT EST RELATION : on effectue des operations sur des relations(ou tables), on produit des relations (ou tables) qui peuvent, a leurtour, etre utilisees dans de nouvelles operations.

quelques operations supplementaires (par exemple, les operations surles groupes) sont ajoutees pour obtenir un langage d’interrogationplus riche.


Gestion des performances

La norme SQL se limite a la definition, la manipulation et au controledes donnees.

Pour une requete, on specifie le resultat attendu dans un langagelogique declaratif. On ne specifie rien quant a la facon dont seraeffectue le calcul de le requete de maniere a assurer des performancessatisfaisantes. Le moteur SQL tranforme la description en un calcul.

La gestion des performances est du ressort de l’administrateur de labase de donnees et pas de l’utilisateur.

Cependant, un utilisateur averti doit connaıtre les optimisationsprincipales : definition de la requete et du plan de calcul, utilisationd’index, ajout d’informations calculees dans la base.


Modifier la requete et/ou son plan de calcul

Faits

Un meme resultat peut etre obtenu avec des requetes differentes

Une meme requete peut etre calculee de differentes facons

Les moteurs SQL sont en general efficaces pour les requetes simples

Si une requete est trop lente

Reflechir a d’autres ecritures de la requete : remplacer des clauses pardes requetes imbriquees, remplacer une requete imbriquee par unejointure, ... et voir si les performances s’ameliorent

Vous pouvez regarder les plans de calcul generes par les requetes pourvous aider. Mais, modifier les plans de calcul est plutot du ressort del’administrateur.

ce cours : definir un nouvel index

ce cours : denormaliser le schema relationnel


Qu’est-ce qu’un index ?

Definition

Un index est une table a deux champs. Le premier est le champ sur lequelporte l’index. Le second est le numero d’enregistrement correspondantdans la table. La table d’index est triee sur les valeurs du premier champ.

Exemple

Soit une table CLIENTS(numclient, nom, prenom, ...). Un index surle cham CLIENTS.nom est une table :

... ...

Dupond 135 487

Dupond 23 788

Dupont 357 302

... ...


Interets et limites des index

Un index sur un champ permet un acces rapide sur les valeurs de cechamp. En effet, le temps moyen d’acces a un element est de N/2sans index a comparer avec log2 N avec un index

Les index permettent d’accelerer les selections horizontales et doncaussi les jointures. Donc ils permettent d’accelerer les calculs derequetes.

MAIS1 ils doivent etre mis a jour (par le SGBDR) lors de toute mise a jour de

la table,2 ils prennent de la place car c’est une nouvelle table. On parle de

compromis temps-espace.


Definir un index ?

sur quels champs ?

regle 1 La table doit avoir un grand nombre de lignes

regle 2 l’attribut doit avoir beaucoup de valeurs differentes

regle 3 indexer les attributs servant aux jointures et donc les clesprimaires et cles etrangeres (souvent fait par le SGBDR)

regle 4 indexer les attributs qui interviennent dans les clauses WHERE

et ORDER BY de requetes tres souvent executees

et pas tous les champs a cause du compromis temps-espace !

Optimiser une requete

Si une requete a un temps de calcul trop long, on peut voir si il ne seraitpas utile d’ajouter un index sur un des champs de la requete.


Comment definir un index ?

par l’instruction CREATE [ UNIQUE ] INDEX name index ON

table ( column | ( expression ) [, ...] )

on peut creer un index sur un ou plusieurs attributs et meme unchamp calcule, le declarer unique ou pas

souvent en SQL des index sont crees par le SGBDR lors de la creationde la base de donnees pour les cles primaires, cles etrangeres,attributs precises UNIQUE


Revisiter la normalisation

Un modele relationnel en forme normale permet, avec les proprietesACID des transactions, d’assurer la coherence et l’integrite d’une basede donnees dans son cycle de vie ;

Ceci implique que les donnees soient non redondantes dans le modele.En particulier, une regle de conception affirme que : une donneecalculee ne doit pas apparaıtre dans le modele

Pour des questions d’efficacite, on peut deroger a cette regle etdenormaliser le modele. Mais, cette denormalisation devra etrecontrolee et assuree a l’aide de contraintes d’integritesupplementaires.


Exemple classique

Soit (un extrait de) la BD relationnelle :PRODUIT(numproduit, ...,prixproduitht, ...)

COMMANDE(numcommande, datecommande, ..., numclient)

LIGNECOMMANDE(numcommande, numproduit, ..., quantite)

Le montant de la commande peut etre calcule et n’apparait pas pour desraisons de normalisation. Mais de nombreuses requetes (montant d’unecommande, montant total des commandes par periode, par type deproduit, ...) necessite son calcul. On peut alors denormaliser le modele etl’ajouter.COMMANDE(numcommande, datecommande, montantcommande, ...)

La coherence devra alors etre controlee par des contraintes d’integrite.Note : situation reelle plus complexe avec dates, reductions, promotions,...


Exemple emprunts

Soit (un extrait de) la BD relationnelle :OEUVRE(numoeuvre, titre, isbn, ..., numediteur)

LIVRE(cotelivre, numoeuvre, dateachat, ...)

EMPRUNT(cotelivre, numadherent, datedebut, dateretour)

Le fait qu’un livre soit present dans la bibliotheque ou emprunte peut etrecalcule. On peut alors denormaliser le modele et ajouter un champ dans latable des livres :LIVRE(cotelivre, numoeuvre, dateachat, sorti, ...)

La coherence devra alors etre controlee par des contraintes d’integrite : ilfaudra verifier lors de toute rentree de livre que l’on met a jourdateretour dans EMPRUNT mais aussi le champ sorti dans LIVRE. Dememe pour tout emprunt.


Conclusion sur l’optimisation

de requetes SQL

Essayer d’ecrire differemment votre requete (vous) ;

Regarder le plan de calcul (vous et DBA) ;

Voir si un index peut etre ajoute (DBA) ;

Voir si on peut denormaliser le schema mais modification tresimportante car modifie le schema de la base (DBA).

de calculs de rapport

On peut agir sur la requete necessaire au calcul du rapport.

On peut precalculer la requete et importer les resultats.

On peut agir sur le rapport.


Plan






BD relationnelle

Une base de donnees relationnelle est une base de donnees definierelativement au modele relationnel.

une BD relationnelle est definie par un schema relationnel :I les relations (ou tables). Une relation est definie par la liste des

attributs, le domaine de chaque attribut, la precision de la cle primaire ;I les associations (ou jointures) naturelles entre les tables ;I les contraintes d’integrite (plus tard dans ce cours, maintenant ! ).


La necessite de contraintes

une base de donnees relationnelle en forme normale permet d’assurerla consistance des donnees

a condition que les proprietes assurant la forme normale soientverifiees lors des evolutions de la base de donnees.

ces proprietes qui doivent etre verifiees par la base de donnees sont lesles contraintes d’integrite

Souvent s’ajoutent des contraintes specifiques a la base de donneesconsideree.


Les contraintes d’integrite

les contraintes d’integrite de domaine : verifier que les valeurs d’unattribut appartiennent a un domaine de valeurs

les contraintes d’integrite de structure ou d’entite : verifier que la cleprimaire et les cles candidates sont toujours definies par une valeurunique

les contraintes d’integrite referentielles : elles sont relatives auxjointures naturelles entre les tables du modele.

les autres contraintes : sont relatives a des proprietes particulieres dela base ou a la verification de regles de gestion sur plusieurs tables.


Le LDD

Le langage de definition des donnees est l’ensemble des instructionsSQL permettant la creation d’une base de donnees relationnelles :

I la creation des tables,I et donc des attributs,I les contraintes de domaine,I les contraintes de structure,I les contraintes de reference,I les contraintes specifiques.

les instructions principales sont : CREATE TABLE, ALTER TABLE,

DROP TABLE


La creation de tables

CREATE TABLE table name

(

column name data type [DEFAULT default exp]

[column constraint],

column name data type [DEFAULT default exp]

[column constraint],

[...]

[table constraint] [...]

)

construit une table vide dans la base de donnees courante avec pourproprietaire celui qui execute l’instruction.


La creation de tables

l’execution de l’instructionCREATE TABLE CLIENTS (

numclient INTEGER,

nom VARCHAR(20), prenom VARCHAR(20),

datenaissance DATE

numrue INTEGER, nomrue VARCHAR(40),

codepostal CHAR(5), ville VARCHAR(20),

typeclient VARCHAR(16) )

cree une table CLIENTS dans la base courante. La table est definie avec sesattributs et leur type mais il faut aussi preciser les contraintes d’integrite.


Donner une valeur par defaut

on peut specifier une valeur par defaut par l’intermediaire de DEFAULT.

la valeur par defaut est du meme type que l’attribut

si on ajoute une ligne sans preciser la valeur de cet attribut, c’est lavaleur par defaut qui est donnee, sinon, c’est la valeur NULL.

on utilise DEFAULT pour eviter des saisies inutiles (la date du jourpour une commande, particulier pour l’attribut type de client)

on utilise DEFAULT pour incrementer une sequence de type entier pourune cle primaire


La contrainte de domaine NOT NULL

l’attribut considere ne peut pas prendre la valeur NULL , on lui imposed’avoir une valeur.

pour les champs qui doivent avoir une valeur (un nom de client)

pour les cles etrangeres dont la valeur doit etre obligatoirementrenseignee (la reference du client faisant une commande)

la verification est effectuee lors de toute action sur la valeur de cetattribut dans une ligne de la table. L’ajout ou la mise a jour estrefusee si une valeur NULL est affectee.

en son absence, la valeur NULL est autorisee


La contrainte de domaine UNIQUE

elle permet de preciser qu’un attribut a une valeur unique

cette contrainte est utilisee pour les cles candidates

il est conseille de l’associer a la contrainte de domaine NOT NULL

la verification est effectuee lors de toute action sur la valeur de cetattribut dans une ligne de la table. L’ajout ou la mise a jour estrefusee si la contrainte est violee

il est conseille de donner un nom a toute contrainte pour que lemessage d’erreur soit comprehensible

on peut avoir une clause UNIQUE portant sur plusieurs champs


autres contraintes de domaine

On peut specifier des contraintes de domaine plus complexes portant surun ou plusieurs attributs d’une meme table a l’aide de la clause CHECK

precisee apres le type du champ si elle porte sur un attribut(contrainte d’attribut), apres la definition des attributs si elle portesur plusieurs attributs (contrainte de table).

le type de client est limite aux valeurs particulier, administration,grand compte et pme

le prix de vente est superieur au prix d’achat

la date de commande est infereure a la date de livraison


definir un domaine

Il est frequent que plusieurs attributs de tables d’une meme base dedonnees soient construits sur les memes domaines. On peut definirdes domaines a l’aide de l’instruction CREATE DOMAIN

definir un domaine pour des quantites d’articles :CREATE DOMAIN quantite INTEGER

DEFAULT 0

CHECK (VALUE >=0)

Il suffit alors d’utiliser le nom du domaine pour definir un attributcomme on utilise un type existant.


contraintes d’integrite de structure

Egalement appelees contraintes d’integrite d’entite, elles permettentde preciser la cle primaire de la table.

Grace a la contrainte PRIMARY KEY

Elle verifie que la cle primaire est toujours definie et a une valeurunique et est donc equivalente a la conjonction des contraintes NOT

NULL et UNIQUE

precisee apres le type du champ si elle porte sur un attribut(contrainte d’attribut), apres la definition des attributs si elle portesur plusieurs attributs (contrainte de table)


contraintes d’integrite de reference

Elles permettent de verifier que les liaisons ou jointures naturelles entre lestables sont correctement definies. Elles sont donc essentielles a lacorrection d’une base de donnees relationnelle. Quelques rappels :

cle etrangere : attribut ou groupe d’attributs d’une table T1 dont lesvaleurs doivent exister comme valeurs de la cle primaire (oucandidate) d’une table T2 (non necessairement distincte de T1)

table qui reference : la table T1 qui contient la cle etrangere, parfoisappelee table secondaire

table referencee : la table T2 qui contient la cle primaire (oucandidate) a laquelle la cle etrangere fait reference, parfois appeleetable primaire


du cote de la table qui reference

Il faut controler l’ajout d’une nouvelle ligne et donc d’une nouvellevaleur de cette cle etrangere

Il faut controler la modification de cette cle etrangere

Il faut verifier que la valeur donnee a la cle etrangere existe dans latable referencee. Pour cela :

I controler les saisiesI ecrire une fonction par le programmeurI assurer le controle par le SGBDRI executer un “trigger”


la clause REFERENCES

Elle permet de deleguer au SGBDR le controle d’integrite de reference

sa syntaxe : REFERENCES nom table referencee

[(cle candidate)]

si le nom de la table est seul, il est suppose que c’est la cle primairequi est referencee.

Effet : lors de tout ajout ou modification, la nouvelle valeur estrecherchee dans la table referencee. Si cette valeur n’existe pas, leSGBDR refusera l’ajout ou modification

Note : les clauses REFERENCES et NOT NULL sont complementairesmais differentes.


la clause FOREIGN KEY

Elle permet de deleguer au SGBDR le controle d’integrite de reference

sa syntaxe : FOREIGN KEY cle etrangere REFERENCES

nom table referencee [(cle candidate)]

cette clause est utilisee comme contrainte de table, c’est-a-dire, apresla definition des attributs. Son utilisation est obligatoire si la cleetrangere est constituee de plusieurs attributs.

Effet : identique


du cote de la table referencee (1)

On peut etre amene a modifier ou a supprimer la valeur de la cleprimaire de la table referencee :

I supprimer un client ouI modifier un numero de client

Que faire pour les lignes qui faisaient reference a cette valeur :I les commandes faisant reference au client supprime ouI les commandes faisant reference au client dont on change le numero



Differentes attitudes sont possibles :I interdire toute suppression ou modification ;I interdire toute suppression ;I autoriser suppression et modification.

Si on autorise, il faut dire les actions a mener en cas de suppression eten cas de modification.

Un SGBDR et SQL permettent de preciser ces autorisations et cesactions



La clause REFERENCES peut etre completee par les clauses ON DELETE

et ON UPDATE

En cas de modification ou de suppression d’une valeur de cleetrangere de la table referencee, quatre possibilites :

I NO ACTION : interdireI CASCADE : autoriser et propagerI SET NULL : autoriser et mettre a NULLI SET DEFAULT : autoriser et mettre a valeur par defaut

par defaut les suppressions et modifications sont interdites si la clauseREFERENCES est presente


autres contraintes

contraintes de domaine : sur un attribut d’une table ou plusieursattributs d’une meme table

contraintes d’entite : sur la cle primaire d’une table

contraintes de reference : sur la cle etrangere d’une table en lien avecles valeurs de la cle primaire referencee

les autres contraintes servent :I a verifier au niveau de la BD des regles de gestionI a verifier la consistance lorsque la base contient des redondances.


assertions et triggers

assertions : permettent d’exprimer des contraintes ne portant pas surune table en particulier : le prix de vente d’un article dans unecommande ne peut pas avoir obtenu une reduction superieure a 20%du prix catalogue

les assertions ne sont pas supportees par PostgreSQL.

triggers : suite d’instructions SQL ou procedure compilee quis’execute automatiquement chaque fois que l’evenement declenchantassocie se produit : a chaque ajout d’une ligne de livraison mettre ajour la quantite livree dans la ligne de commande correspondante

les triggers ont un grand pouvoir d’expression : les contraintes“classiques” sont implantees avec des triggers.


exemple de trigger

a chaque ajout d’une ligne de livraison mettre a jour la quantite livreedans la ligne de commande correspondante

CREATE TRIGGER calcultotalqtelivreesiajoutlivraison

AFTER INSERT ON ligneslivraisons

UPDATE lignescommandes SET quantiteliv =

(SELECT SUM(ligneslivraisons.quantiteliv) FROM

ligneslivraisons

WHERE ligneslivraisons.refcommande=

lignescommandes.refcommande

AND ligneslivraisons.refarticle =

lignescommandes.refarticle)


base des ventes et livraisons (1)

CREATE TABLE magasins

(nummagasin INTEGER CONSTRAINT PRIM MAGASINS PRIMARY KEY,

ville VARCHAR(25) NOT NULL,

gerant VARCHAR(20) ) ;

CREATE TABLE fournisseurs

(numfournisseur INTEGER CONSTRAINT PRIM FOURNISSEURS

PRIMARY KEY,

nom VARCHAR(25) CONSTRAINT NOM UNIQUE FOURNISSEURS NOT NULL

UNIQUE,

ville VARCHAR(20), pays VARCHAR(20) ) ;



CREATE TABLE clients

(numclient INTEGER CONSTRAINT PRIM CLIENTS PRIMARY KEY ,

nom VARCHAR(20) NOT NULL,

prenom VARCHAR(20),

codepostal CHAR(5),

ville VARCHAR(25) NOT NULL,

pays VARCHAR(20),

ca INTEGER DEFAULT 0,

type VARCHAR(16) DEFAULT ’particulier’

CONSTRAINT TYPE CLIENT CHECK (type IN (’particulier’,

’administration’, ’grand compte’, ’pme’)) CONSTRAINT

TYPE CLIENT ) ;



CREATE TABLE articles

(numarticle INTEGER PRIMARY KEY CONSTRAINT PRIM ARTICLES,

nom VARCHAR(20) NOT NULL,

poids NUMERIC(10,1), couleur VARCHAR(20),

stock INTEGER NOT NULL DEFAULT 0 CONSTRAINT STOCK ARTICLES

CHECK (stock >=0),

prixachat INTEGER NOT NULL,

prixvente INTEGER NOT NULL,

reffournisseur INTEGER CONSTRAINT ARTICLES REF FOURNISSEURS

REFERENCES fournisseurs ON UPDATE CASCADE ON DELETE SET

NULL

CHECK (prixvente >= prixachat /0.9) CONSTRAINT

PVPA ARTICLES) ;



CREATE TABLE commandes

(numcommande INTEGER PRIMARY KEY CONSTRAINT PRIM COMMANDES,

date DATE NOT NULL,

refclient INTEGER NOT NULL CONSTRAINT COMMANDES REF CLIENTS

REFERENCES clients ON UPDATE CASCADE ON DELETE NO ACTION

refmagasin INTEGER NOT NULL CONSTRAINT

COMMANDES REF MAGASINS REFERENCES magasins ON UPDATE CASCADE

ON DELETE NO ACTION ) ;



CREATE TABLE lignescommandes

(refcommande INTEGER NOT NULL, refarticle INTEGER NOT NULL,

quantitecom INTEGER NOT NULL, quantiteliv INTEGER NOT NULL,

prixventecom INTEGER NOT NULL, dateprevueliv DATE,

CONSTRAINT PKLC PRIMARY KEY (refcommande, refarticle),

CONSTRAINT FKLCRC FOREIGN KEY refcommande REFERENCES

commandes ON UPDATE CASCADE ON DELETE CASCADE,

CONSTRAINT FKLCRA FOREIGN KEY refarticle REFERENCES

articles ON UPDATE CASCADE ON DELETE NO ACTION,

CONSTRAINT QLC CHECK (quantiteliv <= quantitecom) ) ;



CREATE TABLE livraisons

(numlivraison INTEGER PRIMARY KEY CONSTRAINT

PRIM LIVRAISONS,

date DATE DEFAULT CURRENT DATE,

refclient INTEGER REFERENCES clients ON UPDATE CASCADE ON

DELETE NO ACTION CONSTRAINT LIVRAISONS REF CLIENTS

refmagasin INTEGER REFERENCES magasins ON UPDATE CASCADE ON

DELETE NO ACTION CONSTRAINT LIVRAISONS REF MAGASINS) ;



CREATE TABLE ligneslivraisons

(reflivraison INTEGER NOT NULL,

refarticle INTEGER NOT NULL,

quantiteliv INTEGER NOT NULL CONSTRAINT QLV CHECK

(quantiteliv >=0) ,

refcommande INTEGER NOT NULL,

CONSTRAINT PKLV PRIMARY KEY (reflivraison, refarticle),

CONSTRAINT FKLVL FOREIGN KEY reflivraison REFERENCES

livraisons ON UPDATE CASCADE ON DELETE CASCADE,

CONSTRAINT FKLVA FOREIGN KEY refarticle REFERENCES articles

ON UPDATE CASCADE ON DELETE NO ACTION ,

CONSTRAINT FKLVLC FOREIGN KEY (refcommande, refarticle)

REFERENCES lignescommandes ON UPDATE CASCADE ON DELETE

CASCADE) ;


Plan






Architecture d’une BD dans un SGBDR

le serveur de bases de donnees

Sur ce serveur est implante un SGBDR .

il faut se connecter au serveur en precisant un nom d’utilisateur etune base de donnees avec une connexion securisee, la connexion peutetre transparente a l’utilisateur,

apres connexion, on entre dans une session ou il est possible de seconnecter a une autre base de donnees.

hierarchie des objets

1 un serveur contient des bases de donnees et les informations sur lesutilisateurs

2 une base de donnees ou catalogue est constituee d’un ensemble deschemas

3 un schema contient des elements : tables, contraintes, vues,


Les utilisateurs dans un serveur de BDR

ils sont crees et definis au niveau du serveur, leur nom peut etredifferent de leur nom systeme,

le mot de passe est, en general, different du mot de passe systeme etdoit etre suffisamment complexe

a ce niveau un utilisateur peut se voir attribuer les droits (voirci-apres)

Instructions SQL

les instructions de gestion des utilisateurs sont : CREATE USER etALTER USER

les instructions de gestion des bases de donnees sont CREATEDATABASE et ALTER DATABASE. Il faut alors creer tous les objets etles renseigner. Le createur d’une base possede tous les droits decreation puis d’usage de tous les objets de la base.


les schemas dans une BDR

Interet des schemas et leur usage

pour organiser la base en sous-ensembles logiques pour une gestionplus facile et pour eviter des interactions entre utilisateurs d’unememe base de donnees

les schemas sont contenus dans les bases de donnees (ou catalogues)et contiennent les tables, vues, ...

par defaut, le schema public existe et contient tous les objets crees,le schema pg catalog lui contient les tables systemes.

Instructions SQL

On cree les schemas par l’instruction CREATE SCHEMA, puis les objetsdans chacun des schemas,

on attribue des droits au niveau des schemas, par exemple, decreation de tables dans le schema.


Les vues dans une BDR

Pourquoi les vues

les bases de donnees relationnelles contiennent des schemas, un grandnombre de tables, des cles primaires et etrangeres pour les jointures,des informations “techniques”, des contraintes d’integrite, ...

cette complexite n’est pas a la portee d’un utilisateur de base, etmeme d’un utilisateur averti que vous etes.

Objectifs des vues

elles permettent de donner a l’utilisateur une vue simplifiee de la base :

on restreint sa vision aux seules informations pertinentes au vu de safonction

avec une une image globale dans son langage plus concrete et plusclaire,

on montre a l’utilisateur des relations sans qu’il ait conscience ducalcul effectue


Implantation des vues dans une BDR

Principes des vues

une vue est dynamique,

une vue a une definition logique,

elle est recalculee lors de toute utilisation,

par consequent toute modification sur les tables de base serarepercutee sur la vue

Les vues en SQL

CREATE VIEW [(liste de colonnes)] AS

expression de table, ou expression de table est une clauseSELECT. Par defaut, les noms de colonnes sont herites des noms desattributs des tables mais on peut renommer dans le langage metier,

on peut supprimer une vue, on peut definir des requetes basees surdes vues, on peut definir des vues basees sur des vues


Vues modifiables et conclusion

Peut-on modifier avec une vue ?

Les vues definies a partir de SELECT permettent d’extraire facilementde l’information par leur simple execution,

La norme precise les regles pour qu’une vue soit modifiable sansrisque pour la coherence de la BDR,

pour une vue modifiable, il faut preciser le comportement vis a vis desajout, mise a jour et suppression,

Les dialectes SQL acceptent ou pas les vues modifiables

Conclusion sur les vues

Le concept de vue permet de definir des schemas externes pourl’utilisateur constitues d’un ensemble de vues au travers desquels il voit labase de donnees. Les avantages principaux des vues sont : personnalisationde la base de donnees, simplification, confidentialite des donnees,independance entre applications et definition de la base.


Les droits

Les differents droits et non droits

Dans un environnement multi-utilisateurs, vous avez des droits

au niveau systeme : poste de travail, le reseau, les applications, ...

au niveau du serveur de bases de donnees : authentification, droits deconnexion, de creation, ...

au niveau des objets d’un schema ou d’une base de donnees : tables,vues, requetes, mises a jour, ...

Principes generaux

le super-utilisateur (superuser) a tous les privileges sur tous lesobjets,

le createur d’un objet possede tous les privileges sur cet objet,

Un utilisateur ne peut effectuer une operation que s’il possede lesdroits ou privileges appropries pour cette operation

le possesseur de la base (et le superutilisateur) doit attribuer desprivileges aux autres utilisateurs, qui eux-memes ...


La gestion des privileges

au niveau utilisateur ou groupe d’utilisateurs

les utilisateurs peuvent etre organises en groupes, ces groupescorrespondent a des fonctions logiques dans l’entreprise,

avec les instructions CREATE GROUP et ALTER GROUP,

on peut alors attribuer des privileges au groupe, le groupe PUBLIC

correspond a l’ensemble des utilisateurs.

Instructions d’attribution de privileges en SQL

attribuer : GRANT privilege ON objet nom objet TO

liste utilisateurs [WITH GRANT OPTION],

enlever : REVOKE [GRANT OPTION FOR] privilege ON objet

nom objet TO liste utilisateurs,

les privileges a attribuer dependent de l’objet, la liste d’utilisateurspeut contenir des groupes,

on peut combiner l’utilisation de ces deux instructions


Quels privileges ?

bases et schemas

dans une BD, le privilege CREATE permet de creer des schemas dansla base de donnees,

dans un schema, le privilege USAGE permet l’acces aux objets duschema, le privilege CREATE permet de creer des objets dans le schema

tables et vues

le privilege SELECT donne acces a toutes les colonnes

le privilege INSERT pour inserer des lignes

le privilege DELETE pour supprimer des lignes

le privilege REFERENCES pour creer une contrainte de reference. Il fautposseder ce privilege sur les deux tables

le privilege TRIGGER pour creer des “triggers”

La clause WITH GRANT OPTION permet de transferer les privilegesattribues


L’acces aux donnees dans un SGBDR

les schemas permettent de decouper une base en sous-ensembleslogiques

les vues permettent de donner a chaque utilisateur un acces simplifiesur les donnees utiles a ses fonctions

les privileges permettent de gerer finement les droits d’acces auxdonnees

une utilisation conjointe des schemas, vues et privileges permetd’atteindre une grande souplesse pour l’acces facilite et securise auxdonnees

les groupes sont egalement tres utiles


Un point d’etape

Nous venons de parcourir divers elements proches de l’administration d’unSGBDR a connaıtre pour un utilisateur avise :

la notion de serveur de bases de donnees

les notions de schemas, vues, privileges et groupes

les questions de performances

le dictionnaire des donnees contient toutes les informations sur lesutilisateurs et leurs privileges, les schemas, les tables, cles, index,contraintes, triggers, ...

Il nous reste a etudier les problemes lies a la concurrence


Plan






SGBDR et concurrence

Composants d’un SGBDR

un moteur relationnel responsable de toutes les operations sur lesdonnees,

un dictionnaire des donnees contenant la description de toutes lesdonnees,

un systeme de gestion des transactions permettant d’assurer que lesdonnees restent integres (coherentes) quels que soient les evenements.

Syseme de gestion des transactions

En effet, le modele relationnel a ete defini pour assurer l’integrite desdonnees d’une base de donnees. Mais, il faut prendre en compte :

les pannes : defaillance technique, erreur de programmation, ... UnSGBDR doit etre tolerant aux pannes

la concurrence : la base est utilisee simultanement par plusieursutilisateurs. Un SGBDR doit gerer la concurrence


Les transactions

Definition d’une transaction

Une application est constituee de groupes d’operations.

Certains groupes d’operations forment des unites logiques indivisiblespour conserver l’integrite des donnees relativement au respect deregles de gestion du domaine et au respect de contraintes sur la basede donnees,

une transaction est un groupe d’operations tel que :I soit toutes les operations sont effectueesI soit aucune ne l’est

Les transactions en SQL

Une transaction debute par l’instruction BEGIN, elle se termineI soit par COMMIT : toutes les operations sont effectuees et enregistreesI soit par ROLLBACK : toutes les operations sont annullees (defaites) et

on retrouve l’etat initial.

Par defaut, toute instruction SQL est une transaction


Les transactions pour recuperer les pannes

la base de donnees est sauvegardee regulierement

le gestionnaire des transactions doit memoriser l’etat de toutes lestransactions

En cas de panne :I on recupere la derniere sauvegardeI on reconstruit toutes les transactions termineesI on annulle toutes les transactions qui etaient en cours


Les transactions pour gerer la concurrence

Les transactions sont un element important pour la gestion de laconcurrence

On pourrait penser a effectuer une transaction a la fois mais lesperformances seraient catastrophiques !

Plusieurs (un grand nombre de) transactions doivent pouvoirs’executer simultanement, il faut donc etudier le comportement detransactions s’executant en parallele

Les trois cas d’incoherence

la lecture inconsistante (dirty read) : lire des donnees non validees

la lecture non repetitive (nonrepeatable read) : deux lecturessuccessives donnent des resultats differents

la lecture fantome (phantom read) : des donnees apparaissent etdisparaissent lors de lectures successives


La lecture inconsistante

peut se produire lorsque deux transactions s’executent en parallele selon leschema suivant :

transaction 1 transaction 2Update ligne 1

select ligne 1

actions ROLLBACK

on lit une valeur temporaire non validee. la lecture inconsistante est uneanomalie grave : faire croire qu’une propriete est verifiee et engendrer desactions menant a des incoherences


La lecture non repetitive


transaction 1 transaction 2select ligne 1

actions update ligne 1 ; COMMITselect ligne 1

On lit deux fois une meme ligne avec des resultats differents dans la memetransaction.


La lecture fantome


transaction 1 transaction 2select propriete

update ligne extraite

delete ligne extraite

select propriete

une transaction qui calcule deux fois un ensemble de lignes verifiant unecondition ne trouvera pas les memes lignes


Les solutions

Les niveaux d’isolation

On associe a toute transaction un niveau d’isolation :

READ UNCOMMITTED : pas d’isolation

READ COMMITTED : pas de lecture inconsistante

REPEATABLE READ : pas de lecture non repetitive

SERIALIZABLE : pas de lecture fantome

Le choix est souvent entre READ COMMITTED et SERIALIZABLE. Si lesecond est le plus sur, il peut y avoir degradation des performances.

Les methodes

une solution est l’utilisation de verrous. On verrouille un (bloc d’)enregistrement, une table pendant le temps de la transaction,attention au verrou mortel.

une autre solution est l’utilisation de versions. Chaque transactiontravaille sur une copie virtuelle de la base, copies a synchroniser.


La concurrence

Une transaction est une suite d’instructions indissociables

Il existe differents niveaux d’isolation

Il faut un compromis entre isolation maximale et performances

Il existe des mecanismes pour eviter les verrous mortels

Le systeme de gestion des transactions est un element essentiel d’unSGBDR,

tout particulierement les systemes transactionnels comme lareservation de billets de train, par exemple.


Plan






Critiques du modele relationnel

Evolutivite

Quelle que soit la qualite de l’analyse, les besoins et donc les donneesevoluent et les schemas doivent integrer ces changements. Mais lemodele relationnel est peu evolutif.

La question de l’integration de donnees est un secteur d’activites apart entiere des entreprises.

Efficacite

La masse des donnees a analyser et a gerer est de plus en plus importanteet on voit apparaıtre : reseaux sociaux, Web, capteurs, ... d’ou

informatique decisionnelle pour l’analyse de grands jeux de donnees et

le phenomene Big data pour la gestion et l’analyse de masses dedonnees.


Evolutivite : cas agence de voyages

Des exemples d’evolution

On souhaite garder memoire du mode d’inscription avec la forteevolution du Web.

On souhaite offrir la possibilite aux clients de poser des options surdes voyages.

On souhaite memoriser les transports associes a un voyage.

On souhaite integrer un nouveau voyagiste qui gere des voyages “a lacarte”, c’est-a-dire ou le client choisit des prestations : avion,transferts, hotels.

Implications de l’evolution d’un schema

Une migration des donnees en accord avec le nouveau schema(integration de donnees)

Une reecriture de toutes les applications (requetes, programmes)affectees par cette evolution.


Efficacite et analyse : cas agence de voyages

Des exemples de requete decisionnelle

Donner le nombre voyages par destination sur tous les mois de 2013

Donner le CA par voyagiste sur les 5 dernieres annees

Comparer le nombre de voyages par region de client et moded’inscription au voyage.

Constatation liees a ces besoins

On peut repondre a ces requetes mais

Ces requetes peuvent etre complexes a ecrire et sont peu lisibles pourun utilisateur

elles demandent du temps de calcul et peuvent nuire au bonfonctionnement du systeme operationnel


Plan






modele relationnel et modele en etoile

Modele relationnel

Assurer l’integrite des donnees dans un contexte multi-utilisateurs etd’informatique operationnelle : gerer les clients, les inscriptions, lesvoyages et les circuits.

modele base sur tables (pour les entites) et jointures (pour lesassociations) avec la notion de forme normale

Modele en etoile

Permettre d’effectuer de facon efficace des analyses pour produire desrapports en vue de la prise de decision

modele base sur la notion de faits et dimensions ou un fait est toutequantite qu’on souhaite analyser et une dimension est un axed’analyse


Modele en etoile : le cas voyage

Faits et dimensions

fait : une inscription a un voyage avec son prix

dimension : temporelle (toujours), geographique, client, vendeur, typede voyage.

Exemple de modele

FAITVOYAGE(refjour, reflieu, refclient, refvendeur, refvoyage,prixvoyage)

JOURS(numjour, nomjour, debutWE ?, debutvacances ?, ...)

LIEUX(numlieu, nomlieu, typeclimat, pays, continent,nomregiontouristique, ...)

CLIENTS(numclient, nom, prenom, adresse, codepostal, ...)

VENDEURS(numvendeur, nomvendeur, prenomvendeur, agence)

VOYAGES(numvoyage, intitule, duree, numcatalogue, nomvoyagiste,typevoyage, niveauconfort, gammeprix, ...)


Modele en etoile et informatique decisionnelle

Necessite l’integration des donnees du modele relationnel (etd’autres) avec des outils d’ETL (Extraction Treatment Loading)

vers des magasins de donnees (datamart) inclus dans des entrepots dedonnees (datawarehouse)

avec des suites logicielles adaptees et

des outils pour la production de rapports : documents contenant desanalyses croisees souvent avec interactions possibles (drill-down etdrill-up) bases sur des requetes en general ecrites en SQL et

des outils de fouille de donnees (classification ou clustering,classification supervisee).


Plan






Nouveaux besoins en gestion de donnees

Evolution des donnees

Apparition de tres grandes plate-formes autour du Web : recherched’information, reseaux sociaux, bases de documents, twitter, ...

Volume considerable de donnees liees au Web, a la memorisation dedocuments (textes, rapports, images, videos, ...) et aux capteurs(compteurs intelligents, telesurveillance, ...)

Donnees evolutives sans structure connue a l’avance

Evolution des besoins en gestion de donnees

Necessite de repartir les donnees pour maintenir les performancesmalgre la masse des donnees et

necessite de gerer des donnees heterogenes et evolutives.


Nouvelles solutions

Le constat et les solutions

Les SGBDR ne sont pas adaptes en terme de performance,d’evolutivite et de flexibilite pour le traitement de donnees evolutivesa grande echelle dans un contexte distribue.

D’ou l’appartition de nouveaux paradigmes de gestion de donnees, enparticulier NoSQL “Not only SQL”, mais aussi NewSQL entre autres.

Plan du cours1 parenthese sur les collections (cle,valeur)

2 gestion de donnees distribuees (theoreme CAP)

3 calculs sur des donnees distribuees (Map Reduce)

4 les modeles de donnees NoSQL


Collection (cle,valeur)

Definition

est une collection constituee de paires (cle,valeur) telles que chaquecle apparaıt au plus une fois dans la collection,

aussi nommee associative array, dictionary, collection, (key, value)pairs, tableaux associatifs, dictionnaires, ...

exemples

cle = numero du client, valeur = informations sur le client dans latable des clients

cle = nom+prenom+email, valeur = informations sur un membred’un reseau social

cle = titre d’un morceau de musique, valeur = nombre d’ecoutes etdescriptions des dernieres ecoutes


Operations et implantation

Operations

lookup : trouver la valeur associee a une cle

add : ajouter une paire

remove : retirer une paire

reassign : modifier la valeur d’une paire

Implantation

Les operations, en particulier le lookup, doivent etre efficaces

une liste pour une petite collection, un tableau pour une collectionavec des cles entieres en nombre raisonnable,

le plus souvent un tableau et une fonction de hachage,

mais aussi une repartition des valeurs sur des machines pour de tresgrandes collections.


Introduction aux tables de hachage

Hash table et hash function - definition ideale

Une table de hachage est constituee d’un tableau indexe par des entierscontenant les valeurs et d’une fonction de hachage qui a chaque cle associel’indice entier ou se trouve la valeur correspondante dans le tableau.

Exercice

Que peut etre une fonction de hachage sur les noms et prenoms declient ? Que peut-il se produire si on ajoute de nouveaux elements ?Pensez-vous pouvoir eviter les conflits ?

Quel est le temps d’acces (lookup) a une valeur ? Comparer a unerecherche lineaire et dichotomique.


Tables de hachage

Hash table et hash function

Une table de hachage est constituee d’un tableau indexe par desentiers contenant les valeurs et d’une fonction de hachage qui achaque cle associe l’entier ou peut etre trouvee rapidement la valeurcorrespondante a la cle.

systemes eprouves et efficaces avec gestion des ajouts, suppressions etconflits assurant un lookup en temps constant car les valeurscorrespondant a une meme valeur d’index sont en nombre borne parune constante.

Les techniques ont ete etendues pour gerer la repartition des donneessur plusieurs machines dans des reseaux.


Gestion de donnees distribuees

Systeme distribue

systeme logiciel qui permet de coordonner de nombreuses machines

souvent dans un meme reseau local (LAN)

communiquant par l’echange de messages

avec des machines peu specialisees pouvant etre retirees (pannes) ouajoutees (besoins supplementaires en capacite)

pour les donnees distribuees

systeme de gestion de donnees distribuees est un cas particulier desysteme distribue

pour assurer des acces efficaces avec des volumes de donnees tresimportants

tout en assurant l’acces meme en cas d’indisponibilite de machines


Exemple des data centers

Data center

est decoupe en racks (machines avec liaison reseau rapide 1Go/sec),

eux-memes interconnectes par des routeurs (switches) avec liaison a100 Mo/sec.

Les data centers peuvent etre connectes (2-3 Mo/sec)

Exemple : 1 data center de Google : environ 125 racks, 1 rack = environ40 machines, soit environ 5000 serveurs. On estime a environ 200 datacenters soit un million de serveurs pour Google.


Deux strategies de gestion de donnees distribuees

Distribution des traitements

Les programmes de traitement sont repartis sur les machines,

on envoie les donnees sur les machines qui realisent les traitements

C’est un scenario de type workflow (chaınes de traitement), par exempleavec des Web services.

Distribution des donnees

Les donnees sont reparties sur les machines,

on envoie les programmes vers les machines pour traiter les donnees

C’est le scenario pour les masses de donnees reparties. En effet, il est plusefficace d’echanger des programmes (plus courts) quand les donnees sonttres volumineuses. Pour NoSQL, ceci est realise avec le paradigme MapReduce presente ci-apres.


Proprietes des systemes de gestion de donnees distribuees

Consistency (coherence) : tous les noeuds du systeme voientexactement les memes donnees au meme moment.

Availability (disponibilite) : la perte d’un noeud du systemen’empeche pas le systeme de fonctionner.

Partition Tolerance : le systeme continue de fonctionner en cas derupture de communication entre deux noeuds.

Exercice sur distribution simpliste

Discuter les 3 proprietes pour une base de users repartie comme suit

toute la base sur un seul noeud : A-Z,

la base repartie sur 2 noeuds : A-L ; M-Z,

la base dupliquee sur 2 noeuds : A-Z, A-Z.


Theoreme CAP

Dans un systeme de gestion de donnees distribuees, il est impossibled’assurer les trois proprietes C(onsistency), A(vailability) et P(artitionTolerance) en meme temps


Distribution pour les SGBDR et les bases NoSQL

Un SGBD distribue doit toujours assurer la “Partition Tolerance” donc ona deux types principaux de SGBD distribue :

SGBDR

choisit d’assurer les proprietes C(onsistency) + (P)artition Tolerance

en verifiant les proprietes ACID (Atomicite, Coherence, Isolation etDurabilite) en raison des besoins des BDs transactionnelles,

ceci au detriment de l’efficacite et avec des schemas peu evolutifs

Bases NoSQL

choisit d’assurer les proprietes A(vailability) + (P)artition Tolerance,

pour assurer des performances d’acces a des masses de donnees,

ceci au detriment de la coherence des donnees (pas de gestion destransactions) et avec des schemas absents ou evolutifs.


Principes des bases NoSQL

Bases NoSQL

pas de schema fige,

on privilegie lecture a ecriture et pas de gestion des transactions,

pas de langage d’interrogation standard mais ecrire des programmesadaptes aux donnees.

Bases NoSQL et partitionnement

Assurer les proprietes A(vailability) + (P)artition Tolerance,

forte distribution des donnees avec des techniques de partitionnementsophistiquees (sharding, consistent hashing, ...)

et un paradigme de calcul parallele adapte aux masses de donneesdistribuees : Map reduce


Map Reduce

est un

paradigme de calcul distribue pour traiter des masses de donnees,

par distribution des traitements sur les serveurs de donnees.

Il a ete concu par Google mais est base sur des modeles bien etudiesde programmation parallele.

Caracteristiques

permet de repartir la charge sur de nombreux serveurs, augmenter lenombre de serveurs augmente la rapidite de traitement,

abstrait l’infrastructure materielle pour le programmeur en traitant lecluster, la repartition de la charge, la distribution des donnees, latolerance aux pannes, ...,

est disponible dans de nombreux environnements de programmation.


Map Reduce

Programmation

Le travail du programmeur pour un calcul (un programme complexe peutnecessiter plusieurs calculs) se limite a l’ecriture de deux fonctions

Map : fait des calculs elementaires sur des paires (cle,valeur) etretourne une liste de resultats intermediaires,

Reduce : combine les listes de resultats intermediaires en une liste deresultats finaux.

exemple en recherche d’information

Le score du celebre moteur de recherche d’information Googlecontient une composante basee sur la frequence d’apparition des motsdans les documents

Il faut donc etre capable, en particulier, de calculer le nombred’apparitions des mots dans l’ensemble des documents du Web ! ! !


Map Reduce par l’exemple

Fonction Map de calcul du nombre d’occurences

entree : identifiant d’un document, contenu d’un documentsortie : liste des mots avec leur nombre d’occurence

Que se passe-t-il sur un noeud Map ?

On produit une liste de la forme ((base : 2), ..., (reparti : 3), ..., (xml : 1))pour chacun des documents du noeud.

et apres ?

Ces listes recues des differents noeuds sont regroupees et triees par motpour produire des listes : (base, 1, 2, 1, 2, ...), ..., (reparti, 1, 1, 3, ...), ...

et enfin la fonction Reduce

entree : mot, liste des nombres d’occurences du mot dans les documentssortie : liste des mots avec leur nombre d’occurence total


Principes generaux de Map Reduce

Fonctionnement

la distribution des programmes Map et des donnees est gere parl’environnement, les noeuds executent les Map,

l’environnement gere le groupement, le tri, la distribution des listesresultats et des programmes Reduce, les noeuds executent lesprogrammes Reduce

l’environnement gere la collecte des resultats des Reduce.

Tout est gere avec des systemes (cle,valeur) repartis

Applications du paradigme

les calculs de score en recherche d’information,

les calculs de regles d’association (panier de la menagere) pour lesgrands jeux de transactions

la detection de spam, les reseaux sociaux, la fouille du web, ...


Plan






Modeles NoSQL de donnees

Quatre modeles principaux

Dans l’ordre de la presentation dans ce cours :

bases cle-valeur

bases document

bases graphe

bases colonne


Principes des bases cle-valeur

Definition

chaque objet de la base est identifie par une cle unique. C’est le seulmoyen d’acces a l’objet

la structure de l’objet est libre. Les traitements sur l’objet sont laissesa la charge du programmeur

Les 4 operations CRUD des bases NoSQL cle-valeur

Create : creer une paire, create(cle,valeur)

Read : lire une valeur a partir de la cle, read(cle)

Update : met a jour une valeur a partir de la cle, update(cle,valeur)

Delete : supprime une paire a partir de la cle, delete(cle)


Les bases cle-valeur

Utilisations et implantations

masses de donnees avec des besoins de requetage simple comme lessessions Web et les fichiers de log, les profils utilisateurs, les donneesde capteurs, ...

bases : Amazon Dynamo, Riak, Redis, Voldemort

Critiques

modele simple, bonne mise a l’echelle, disponibilite, evolutivite desvaleurs (sous reserve d’adapter les programmes de traitement),

modele trop simple, interrogation seulement sur la cle, la complexiteeventuelle des valeurs doit etre geree par des programmes et donc unecouche applicative complexe si les valeurs sont trop complexes.


Principes des bases document

Definition

Elles sont basees sur les bases cle-valeur,

la valeur est un document semi-structure hierarchique de type JSONou XML, i.e. un document a une structure arborescente sans schemafige

Les operations des bases documents

Les operations CRUD du modele cle-valeur,

augmentees de capacites de requetage sur le contenu des documentset de vues.


Exemple de document semi-structure XML

<?xml version="1.0" encoding="ISO-8859-1"?>

<BIBLIO SUBJECT="XML">

<BOOK ISBN="9782212090819" LANG="fr" SUBJECT="applications">

<AUTHOR>

<FIRSTNAME>Jean-Christophe</FIRSTNAME>

<LASTNAME>Bernadac</LASTNAME> </AUTHOR>

<AUTHOR>

<FIRSTNAME>Francois</FIRSTNAME>

<LASTNAME>Knab</LASTNAME> </AUTHOR>

<TITLE>Construire une application XML</TITLE>

<PUBLISHER>

<NAME>Eyrolles</NAME>

<PLACE>Paris</PLACE> </PUBLISHER>

<DATEPUB>1999</DATEPUB> </BOOK>

<BOOK ISBN="9782212090529" LANG="fr" SUBJECT="general">

<AUTHOR>


Exemple de document semi-structure JSON

{

"data": [

{ "id": "X999_Y999",

"from": {"name": "Tom Brady", "id": "X12"},

"message": "Looking forward to 2010!",

"actions": [

{ "name": "Comment",

"link": "http://www.facebook.com/X999/posts/Y999"

},

{ "name": "Like",

"link": "http://www.facebook.com/X999/posts/Y999"

}

],

"type": "status",

"created_time": "2010-08-02T21:27:44+0000",

"updated_time": "2010-08-02T21:27:44+0000"

},Remi Gilleron (Mostrare) Informatique M1 MIASHS septembre 2013 134 / 143

Les bases document


les outils de gestion de contenu (CMS), catalogues de produits,analyse du Web, ...

bases : CouchDB, RavenDB, MongoDB, Terrastore

Critiques

modele simple augmente de la richesse des documentssemi-structures, bonne mise a l’echelle, expressivite des requetes,

efficace pour les interrogations par cle mais peut etre limite pour lesinterrogations par le contenu des documents, limite aux donneeshierarchiques.


Principes des bases graphe

Definition

Elles permettent de manipuler des donnees de triplets de la forme(sujet, predicat objet) representables sous forme de graphes orientes,

on utilise du (cle,valeur) pour acceder rapidement d’un objet auxcouples (predicat, sujet) qui le concerne (aux arcs sortant du noeud),d’un predicat aux couples (objet, sujet), d’un sujet aux couples (objet,predicat).

Les operations des bases graphes

Le langage SPARQL est un langage avec une syntaxe inspiree de SQLqui permet l’interrogation en utilisant des variables dans desexpressions de triplets ou de chemins

Exemple : SELECT ?vil ?pop WHERE ?vil rdf :type d :Settlement. ?vil d :mayor ?o. ?vil d :country :France . ?vil d :populationTotal ?pop. FILTER( ?pop > 100 000)


Exemple de graphe de relations sociales


vu comme des triplets (s,p,o)

<http://semprog.com/people/colin> foaf:name "Colin Evans".

<http://semprog.com/people/colin> rdf:type foaf:Person.

<http://semprog.com/people/colin> foaf:mbox <mailto:[email protected]>.

<http://kiwitobes.com/toby.rdf#ts> foaf:homepage <http://kiwitobes.com/>.

<http://kiwitobes.com/toby.rdf#ts> foaf:nick "kiwitobes".

<http://kiwitobes.com/toby.rdf#ts> rdf:type foaf:Person.

<http://kiwitobes.com/toby.rdf#ts> foaf:knows <http://semprog.com/people/colin>.

<http://kiwitobes.com/toby.rdf#ts> foaf:knows _:x3.

<http://kiwitobes.com/toby.rdf#ts> foaf:interest <http://semprog.com>.

<http://kiwitobes.com/toby.rdf#ts> foaf:mbox <mailto:[email protected]>.

<http://kiwitobes.com/toby.rdf#ts> foaf:name "Toby Segaran".

<http://semprog.com> rdf:label "Semantic Programming".

<http://semprog.com> rdf:type foaf:Document.

_:x3 foaf:name "Jamie Taylor".

_:x3 rdf:type foaf:Person.

_:x3 foaf:mbox <mailto:[email protected]>.


Les bases graphe


les reseaux sociaux, le Web semantique (knowledge graph de Google),les open data, les donnees cartographiques, ...

bases : Neo4J, OrientDB, ...

Critiques

modele riche et evolutif (ajout de sujets, d’objets et de predicats) bienadapte aux situations ouil faut modeliser beaucoup de relations, unlangage d’interrogation generaliste (SPARQL) et des langagesspecialises

repartition des donnees peut etre problematique pour des masses detriplets.


Principes des bases colonne

Definition

Les donnees sont stockees en colonne,

une colonne est une entite de base representant un champ de donnee,chaque colonne est definie par un couple (cle,valeur),

les colonnes peuvent etre groupees en supercolonnes et en famille decolonnes, les colonnes sont regroupees par ligne

chaque ligne est identifiee par un identifiant unique et un nom unique

Les operations des bases graphes

les requetes doivent etre predefinies en fonction de l’organisation encolonnes (et supercolonnes et familles de colonnes) choisie.


Exemple de base colonnes


Les bases colonne


la journalisation d’evenements, les analyses de clientele et larecommandation, ...

bases : HBase, Cassandra, SimpleDB, ...

Critiques

modele efficace avec indexation sur les colonnes en particulier pour lesrequetes de calcul de type OLAP, supporte des donnees tabulaires aschema variable,

ne supporte pas les donnees structurees complexes, efficaces pour desrequetes temps reel connues a l’avance, la modification de structuresen colonnes necessite de la maintenance


Conclusion sur les bases NoSQL

Leur interet

l’interrogation de masses de donnees a structure heterogene etevolutive,

trois modeles (cle,valeur), colonne et document avec des structuresde donnees simples, tabulaires et hierarchiques,

un modele graphe pour les donnees fortement interdependantes.

Les principes sous-jacents

la repartition des donnees,

l’utilisation de collections (cle,valeur) reparties,

l’utilisation du paradigme Map reduce pour les calculs de requetes.


Documents

Bases de donn ees avanc ees - grappa.univ-lille3.frgilleron/cours-bases-de-donnees-avanc... · Objectifs et organisation Objectifs du cours comprendre l’environnement informatique