1

MABD Modèles Avancés pour les Bases de Données

UE MIOO5

Master d’informatique spécialité IAD niveau M1

Anne Doucet anne.doucet@lip6.fr

Septembre-décembre 13 http://www-bd.lip6.fr/ens/mabd2013/index.php/Accueil

2

Objectifs

Présenter les techniques de gestion de données utilisées dans les SGBD pour les données du Web, afin de résoudre les problèmes liés à l’interopérabilité des données.

Modélisation, gestion et interrogation de données hétérogènes,

provenant de sources diverses. Architectures d’intégration de grands ensembles de données.

3

Plan

• Le relationnel : rappels et bilan • BD objet : modèle et langage • L’objet-relationnel et SQL3 • BD et Web • Modèles et langages semi-structurés • XML et DTD • Xschema • Xpath • Xquery • Intégration de données hétérogènes et réparties

4

Bibliographie

• G. Gardarin : Bases de Données – objet et relationnel, Eyrolles, 2003.

• H. Garcia-Molina, J.D.Ullman, J. Widom : Database System Implementation, Prentice Hall, 2000.

• R. Ramakrishnan, Gehrke J. : Database Management Systems, mc-Graw Hill, 3ème édition.

• G. Gardarin : XML : des bases de données aux services Web, Dunod, 2002.

• Documentation XML : www.w3c.org/TR/REC-xml • http://www.w3.org/TR

5

Module MABD Master Informatique

Spécialité IAD

Cours 1- Le relationnel : rappels et bilan

6

SGBD Relationnels : rappels et bilan

• Fonctions et structure des SGBD • Expression des requêtes et programmation des

applications • Limites du modèle relationnel • Concepts du modèle objet

7

• Contrôle intégré des données – cohérence et intégrité – partage – performances d’accès – Sécurité

• Indépendance des données – logique : cache les détails de l’organisation conceptuelle des données – physique : cache les détails du stockage physique des données

Objectifs des SGBD

8

Fonctions

• Schéma intégré – vue uniforme des données, par ex. sous formes de relations (ou tables)

• Intégrité déclarative et cohérence – 24000 ≤ Salaire ≤ 250000 – l’utilisateur spécifie et le SGBD valide

• Vues – réorganisation de relations pour certaines classes d’utilisateurs

• Accès déclaratif – avec un langage de requête (SQL), l’utilisateur spécifie ce qu’il veut

obtenir et non ce qu’il faut faire pour l’obtenir (le quoi et non le comment)

9

Fonctions • Traitement et optimisation de requêtes

– performances obtenues automatiquement

• Transactions – exécution des requêtes par des unités atomiques – indépendance à la concurrence multi-utilisateurs et aux pannes

• Conception d’applications BD – conception visuelle des schémas de BD – conception des traitements et des interfaces graphiques

• Administration système – outils d’audit et de réglage (tuning) – visualisation des plans d’accès

10

Architecture ANSI/SPARC

Vue interne

Vue conceptuelle

Vue externe

SGBD

EMP(ENO: string, ENAME: string, TITLE: string) PROJ(PNO: string, PNAME: string, BUDGET: integer) WORKS(ENO: string, PNO: string, RESP: string, DUR: integer)

Stocke les relations dans des fichiers, avec des index sur certains attributs.

ASSIGNMENT(ENO,PNO,ENAME,PNAME)

Vue externe

Vue externe

Schéma externe

Schéma conceptuel

Schéma interne

11

Architecture système Utilisateurs Programmeurs

d’application Administrateur de BD

Formes Applications Interface DML CLI DDL

Index

Fichiers

Compilateur DDL

Gestionnaire du disque

Gestionnaire de tampons

Gestionnaire de fichiers

Processeur de requêtes

Commandes SQL

Ges

tionn

aire

de

pa

nnes

Gestionnaire de

transactions

SGBD

Répertoire système

12

Stockage des données • Les données sont stockées en mémoire secondaire (disques,

bandes magnétiques). • L’unité de stockage, et de transfert de données (disque-MC)

est le bloc. • Le coût d’une opération de la BD est fonction du nombre

d’accès disque nécessaires pour accéder aux données. Il dépend donc fortement de la façon dont les données sont organisées sur le disque.

• Le gérant du disque gère l’espace disque. L’unité de gestion est la page, qui correspond à un bloc. La taille de la page (4K ou 8K) est un paramètre du SGBD.

• Le gestionnaire de tampons gère l’occupation de la mémoire centrale (plus efficace que l’OS).

13

Organisation des données en fichiers

• Les données sont stockées dans des fichiers (ensemble d’enregistrements). Chaque enregistrement a un identificateur unique.

• Les fichiers sont stockés sur plusieurs pages. La page sur

laquelle se trouve un enregistrement est déterminée par le gestionnaire de fichiers.

• La façon d’organiser les enregistrements dans un fichier a un

impact important sur les performances. Elle dépend du type de requêtes.

• Un SGBD offre en général plusieurs méthodes d’accès : index,

hachage, arbre B+. Le choix de la meilleure méthode est du ressort de l’administrateur de la base.

14

Expression de requêtes

• SQL : SELECT … FROM … WHERE – Toutes les opérations de l’algèbre relationnelle – Mais ne permet pas d’exprimer toutes les manipulations

• Ex : fermeture transitive

Grand-parents : OK Arrière-grands-parents : OK Descendants : ?

Parent Enfant Luc Max Luc Paul Max Léa Léa Marie Paul Marc Marc Jean

PL/SQL

• Intégrer SQL avec un langage de programmation – Oracle : PL/SQL

• On utilise : – SQL pour accéder aux données de la base et les manipuler – Le langage de programmation PL pour manipuler et traiter

les données (utilisation de variables, procédures, fonctions, boucles, conditionnelles, instructions d’entrée/sortie, …)

15

16

PL/SQL • Toutes les fonctionnalités classiques des langages de

programmation :

– Déclaration de variables • Types de données de SQL (CHAR, DATE, NUMBER, … ) et

types de données PL/SQL (BOOLEAN…) • Ex : declare t varchar2(30);

– Boucles • LOOP …. END LOOP; • FOR i IN …. LOOP… END LOOP; • WHILE … LOOP … END LOOP;

PL/SQL

– Conditionnelle

• IF … THEN … ELSE … END IF;

– Procédures et fonctions

• CREATE OR REPLACE PROCEDURE toto AS [déclarations] BEGIN ….. ….. END

17

18

PL/SQL

DECLARE x NUMBER(4); BEGIN SELECT qte INTO x FROM Stock WHERE nom=‘stylo’ IF x > 0 THEN UPDATE Stock SET qte= qte-1 WHERE nom=‘stylo’; ELSE INSERT INTO Commande values (‘stylo’,50); END IF; COMMIT; END;

19

PL/SQL : Curseurs

DECLARE CURSOR c1 is SELECT nom, fonction FROM Emp WHERE sal> 5000;

Instructions de contrôle : OPEN : exécute la requête, identifie l’ensemble résultat et

positionne le curseur sur le premier n-uplet FETCH : récupère le n-uplet courant, et se positionne sur le suivant CLOSE : déconnecte le curseur.

20

Traitement des requêtes

Requête déclarative (SQL)

Processeur de requêtes

Plan d'exécution (accès bas niveau aux données)

Générateur de plans

Estimation de coûts

Exécution des plans

Compilateur

21

Etapes du traitement des requêtes

Normalisation

Analyse

Simplification

Restructuration

Optimisation

Plan d'exécution “optimal”

Répertoire système

Requête SQL

22

• Conversion en arbre algébrique • Exemple

SELECT Ename FROM Emp, Works, Project WHERE Emp.Eno=Works.Eno AND Works.Pno=Project.Pno AND Ename NOT=‘J.Doe’ AND Pname = ‘CAD/CAM’ AND (Dur=12 OR Dur=24)

Restructuration

ΠENAME

σDUR=12 OR DUR=24

σPNAME=“CAD/CAM”

σENAME≠“J. DOE”

Project Works Emp

PNO

ENO

23

Optimisation

• Elaborer des plans – arbre algébrique, restructuration, ordre d’évaluation

• Estimer leurs coûts – fonctions de coût

• en terme de temps d’exécution • coût I/O + coût CPU • poids très différents

– par ex. coût I/O = 1000 * coût CPU

• Choisir le meilleur plan – Espace de recherche : ensemble des expressions algébriques

équivalentes pour un même requête – algorithmes de recherche

24

Calcul du coût d’un plan • La fonction de coût donne les temps I/O et CPU

– nombre d’instructions et d’accès disques

• Estimation du coût d’exécution de chaque noeud de l’arbre algébrique

• Estimation de la taille du résultat de chaque noeud

– Statistiques sur les relations (cardinalité, taille d’un n-uplet, nb de n-uplets participant à une jointure, …), les attributs…

– Hypothèses sur la distribution des différentes valeurs d’attributs

– Estimer les tailles des relations intermédiaires

Apports du modèle relationnel

• Simplicité des concepts et du schéma • Bon support théorique • Langage d’interrogation déclaratif • Haut degré d’indépendance des données • Optimisation des accès à la BD

– bonnes performances • Gestion de contraintes d’intégrité

25

Limites du modèle relationnel

• Trop grande simplicité du modèle de données – 1ère forme normale de Codd

• attributs mono-valués : n-uplets plats – Pauvreté du système de typage

• Types prédéfinis (entier, réel, chaîne, …) : pas de possibilité d’extension – Inadapté aux objets complexes (ex: documents structurés)

• Un objet du monde réel est modélisé à l’aide de plusieurs relations : mauvaise lisibilité, perte d’information sémantique, nombreuses jointures

• Mauvais support des applications non standards – CAO, CFAO – BD Géographiques – BD techniques – …

26

Limites du modèle relationnel

• Langage d’interrogation et de manipulation non complet – Pas de récursion – Pas de structures de contrôle : conditionnelles, boucles – L’utilisation de deux langages (SQL + un langage de programmation)

provoque un dysfonctionnement du système • Sql déclaratif, LP procédural • Systèmes de typage différent • Espaces de noms différents • Utilisation de curseurs pour manipuler les ensembles • Mauvaises performances

• Ensemble fermé d’opérateurs : algèbre relationnelle – Critères d’optimisation liés à ces opérateurs

• Index restreints aux types de base • Pas de versions, pas de transactions longues

27

Besoins

• Modèle de données plus riche, conception plus proche du monde réel

• Gestion de gros objets (données multimedia) avec structures de stockage adaptées

• Nouveaux modèles de transactions (transactions longues, distribuées, imbriquées..)

• Prise en compte des versions • Indépendance des objets et des traitements • Extensibilité • Meilleure intégration des langages d’interrogation et de

manipulation 28

Approches

• Extensions du modèle relationnel

• Langages de programmation persistants

• Systèmes orienté-objet

29

Modèle Objet

• Concepts : – Valeur et objet – Identité d’objet – Classe – Héritage

30

Valeur

• Valeur atomique (valeur de type simple : caractère, entier, booléen, …)

• Valeur complexe : les tuples, les ensembles, les listes, sont des valeurs complexes – Ex : [Max, 25, Paris] , {Jean, Marc, Paul}

31

Objet

• Un objet a un identificateur et une valeur. • Un objet atomique a une valeur atomique • Un objet complexe est construit en appliquant les

constructeurs tuple, set, list, array, à des objets atomiques ou complexes.

• L’utilisation des constructeurs est indépendante du type des objets (orthogonalité du système de types)

• Ex : (i1, 25) (i2, [Max, i1, Paris, {Jean, Marc, Paul}])

32

Encapsulation

• Un objet est constitué – de données – d’opérations applicables à ces données

• On distingue l’interface (description des opérations applicables à l’objet), de l’implémentation (structure des données physique et code des opérations)

• L’utilisateur ne voit que l’interface, les données sont encapsulées.

33

Max, 25

Paris

get_age get_adresse modify_adresse

Identité d’objet

• Chaque objet a une identité indépendante de sa valeur • L’identificateur est géré par le système (correspond à une clef

interne) • Deux objets sont identiques s’ils ont le même identificateur, et

sont égaux s’ils ont la même valeur.

• Les objets peuvent être représentés par un graphe de composition, qui peut comporter des cycles

34

Identité d’objet • L’identité d’objet permet

– le partage d’objets, – les cycles entre objets, – le maintien automatique des contraintes référentielles, – la mise à jour de la valeur sans changer l’identité, – plusieurs niveaux de comparaison (égalité profonde, égalité

superficielle)

• Ex:

35

conjoint

enfant enfant

i1 i2

i3

Classe

• Les objets partageant des caractéristiques communes (structure et comportement) sont regroupés dans des classes

• Les classes permettent une abstraction des informations et de leur représentation. Ce sont les concepts utilisés pour décrire le schéma de la base.

• Ex: Class Personne [nom : string, age : integer, adresse : string, conjoint : Personne, enfants : {Personne} ] method get_age() : integer, get_adresse(): string

36

Héritage

• Factoriser des classes ayant des propriétés communes (structure et/ou méthodes). Une sous-classe hérite des propriétés de sa super-classe.

• Spécialisation : affiner une classe en une sous-classe – Spécialiser la classe Personne en la classe Employé

37

nom age

adresse

nom age

adresse salaire

Personne

Employé

get-_age get_adresse

get-_age get_adresse augmenter_salaire

Héritage

• Généralisation : création d’une super-classe regroupant les caractéristiques communes à plusieurs classes. – Généraliser les classes Voiture et Camion en une classe Véhicule

38

marque type

puissance couleur

marque type

puissance volume

marque type

puissance

Voiture

Véhicule

Camion

Get_puissance

Get_puissance Get_volume

Get_puissance Get_couleur

39

L'apport des modèles objets

• Identité d'objets – introduction de pointeurs invariants – possibilité de chaînage

• Encapsulation des données – possibilité d'isoler les données par des opérations – facilite l'évolution des structures de données

• Héritage d'opérations et de structures – facilite la réutilisation des types de données – permet l'adaptation à son application

• Possibilité d'opérations abstraites (polymorphisme) – simplifie la vie du développeur