INFO710 : Compléments de base de données - Historique des versions

Hyvernat : /* Les support de TD et TP */

2009-08-31T10:15:19Z

Les support de TD et TP

← Version précédente		Version du 31 août 2009 à 10:15
Ligne 44 :		Ligne 44 :
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td4.pdf td4]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td4.pdf td4]
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td5.pdf td5]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td5.pdf td5]
			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/tp2.pdf tp2]

	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/examen.pdf examen corrigé]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/examen.pdf examen corrigé]

Hyvernat : /* Les support de TD et TP */

2009-01-09T16:43:44Z

Les support de TD et TP

← Version précédente		Version du 9 janvier 2009 à 16:43
Ligne 44 :		Ligne 44 :
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td4.pdf td4]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td4.pdf td4]
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td5.pdf td5]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td5.pdf td5]

			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/examen.pdf examen corrigé]

Hyvernat : /* Intégration avec d'autres outils */

2008-12-08T13:22:13Z

Intégration avec d'autres outils

← Version précédente		Version du 8 décembre 2008 à 13:22
Ligne 533 :		Ligne 533 :
	===Déclencheurs===		===Déclencheurs===

	==¿Intégration avec d'autres outils?==		==Intégration avec d'autres outils==

			===Utilisation d'une base de données en Perl avec DBI===

			cf [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/tp2.pdf TP2].

	==Quelques références==		==Quelques références==

Hyvernat : /* Le langage SQL, deuxième partie */

2008-12-08T13:20:46Z

Le langage SQL, deuxième partie

← Version précédente		Version du 8 décembre 2008 à 13:20
Ligne 523 :		Ligne 523 :
	==Le langage SQL, deuxième partie==		==Le langage SQL, deuxième partie==

			--- PAS FAIT ---

			===Vues===

			===Transactions===

			===Contraintes===

			===Déclencheurs===

	==¿Intégration avec d'autres outils?==		==¿Intégration avec d'autres outils?==

Hyvernat : /* Formes normales */

2008-12-08T13:19:05Z

Formes normales

← Version précédente		Version du 8 décembre 2008 à 13:19
Ligne 513 :		Ligne 513 :
	==Formes normales==		==Formes normales==

			===Décompositions sans perte d'information===

			===Décompositions sans perte de dépendances===

			===Forme normale de Boyce-Codd===

			===3ème (et 2ème) forme normale===

	==Le langage SQL, deuxième partie==		==Le langage SQL, deuxième partie==

Hyvernat : /* Organisation des séances */

2008-12-08T13:17:02Z

Organisation des séances

← Version précédente		Version du 8 décembre 2008 à 13:17
Ligne 28 :		Ligne 28 :
	* huitième séance (3/11/2008) : cours (algèbre relationnelle), TD3.		* huitième séance (3/11/2008) : cours (algèbre relationnelle), TD3.
	* neuvième séance (10/11/2008) : TD3.		* neuvième séance (10/11/2008) : TD3.
	* dixième/onzième séance (17/03/2008) : dépendances fonctionnelles, axiomes de Armstrong et recouvrements, TD4.		* dixième/onzième séance (17/11/2008) : dépendances fonctionnelles, axiomes de Armstrong et recouvrements, TD4.
			* douzième séance (24/11/2008) : fin TD4.
			* treizième séance (24/11/2008) : TP2.
			* quatorzième séance (01/12/2008) : décompositions sans perte d'information, forme normale de Boyce-Codd, début TD 5.
			* quinzième séance (01/12/2008) : TP2.
			* seizième séance (08/12/2008) : TD5 (sans le dernier exercice sur la 3èmes forme normale).
			* dix-septième séance (08/12/2008) : TP2.

	==Les support de TD et TP==		==Les support de TD et TP==

Hyvernat : /* Les support de TD et TP */

2008-12-08T13:11:12Z

Les support de TD et TP

@@ Ligne 37 : / Ligne 37 : @@
 * [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td3.pdf td3]
 * [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td4.pdf td4]
 ==Introduction==

Hyvernat : /* Modèle théorique : modèle relationnel */

2008-11-18T10:36:50Z

Modèle théorique : modèle relationnel

← Version précédente		Version du 18 novembre 2008 à 10:36
Ligne 336 :		Ligne 336 :

	==Modèle théorique : modèle relationnel==		==Modèle théorique : modèle relationnel==
			===Rappels===

			L'idée du modèle abstrait est de remplacer la notion de ''table'' par celle, plus mathématique, de ''relation''.

			;Définition: le produit cartésien des ensembles <math>A_1</math> et <math>A_2</math> (noté <math>A_1\times A_2</math>) est défini comme <math>A_1\times A_2 = \{ (a_1,a_2)\ \|\ a_1\in A_1\ \hbox{et}\ a_2\in A_2\}</math>. Le produit de 3, 4 ou plus ensembles est définie de manière similaire.



			;Définition: une relation <math>R</math> entre les ensembles <math>A_1</math>, ..., <math>A_n</math> est un sous-ensemble du produit cartésien <math>A_1 \times \cdots \times A_n</math>. Intuitivement, <math>R=\{(a_1,...,a_n)\ \|\ a_1, ..., a_n \ \hbox{sont en relation par } R\}</math>.


			===Modèle relationnel des données===

			On modélise une table <math>T</math> dont les attributs sont de type <math>A_1</math>, ..., <math>A_n</math> par une relation entre <math>A_1</math>, ... et <math>A_n</math>. Si les attributs ont les noms <math>t_1</math>, ... <math>t_n</math>, on notera <math>R(t_1,...,t_n)</math> pour designer une telle relation.


			<u>Exemple :</u> on pourra avoir une relation <math>\mathit{Dep}(\mathit{Code},\mathit{Nom},\mathit{Prefecture})</math>, ou plus succinctement, une relation <math>D(c,n,p)</math>.



			===Algèbre relationnelle===

			* union sur des relations de mêmes attributs : <math>R\cup S</math>
			* différence sur des relations de mêmes attributs : <math>R\setminus S</math>
			* produit cartésien sur des relations quelconques : <math>R\times S</math>
			* projection d'attributs quelconques : <math>\Pi_{t_{i_1},...,t_{i_k}} (R)</math>
			* sélection par une formule simple : <math>\sigma_F(R)</math>



			===Dépendances fonctionnelles===

			Une des difficultés lors de la création d'une base de donnée est d'éviter une redondance de l'information présente dans la base. Le problème principal lié à la redondance est celui de la cohérence des données : il faut garantir qu'on ne peut pas modifier un seul endroit où l'information est stockée. Par exemple, si un des attribut est l'adresse complète et un autre attribut est le département, il faut garantir que le code postal correspond bien au département. SQL permet de gérer ce genre de contraintes, mais pas forcement de manière simple. Il est donc préférable d'éviter la redondance dés la conception de la base.

			Le problème de la taille des données (la redondance implique un besoin en mémoire plus gros) est relativement anecdotique pour la plupart des utilisations d'une base de données.


			Les dépendances entre attributs est un des moyens utilisés pour étudier la redondance d'information.

			;Définition: si <math>R(A,B,...)</math> est un schéma relationnel, et si <math>X</math> et <math>Y</math> sont deux ensembles d'attributs, on dit que <math>Y</math> dépend fonctionnellement de <math>X</math> (et on écrit <math>X \to Y</math> si pour tous les éléments <math>u,v</math> de la table <math>R</math>, on a <math>\Pi_X(u) = \Pi_X(v) \Rightarrow \Pi_Y(u)=\Pi_Y(v)</math>.


			Comme le choix d'une clé, le choix des dépendances à imposer est à faire au moment de la conception, et il s'agit d'une notion sémantique...


			<u>Remarque :</u> si <math>X</math> est une clé, alors on a toujours <math>X\to Y</math> pour n'importe quel ensemble <math>Y</math> d'attributs...



			===Axiomes de Armstrong===

			Certaines dépendances génèrent d'autres dépendances automatiquement. On aimerait pouvoir calculer toutes les dépendances satisfaites par une table.

			;Fait: les 3 propriétés suivantes sont appelées axiomes de Armstrong:
			* réflexivité : si <math>Y\subseteq X</math> alors <math>X\to Y</math> est valide,
			* augmentation : si <math>X\to Y</math> est valide, alors <math>X,Z\to Y,Z</math> est aussi valide,
			* transitivité : si <math>X\to Y</math> est valide et si <math>Y\to Z</math> est valide, alors <math>X\to Z</math> est aussi valide.


			Ces axiomes permettent de déduire d'autres principes généraux. Par exemple :
			* si <math>X\to Y</math> et <math>X\to Z</math> alors $X\to Y,Z</math>
			* ...


			;Théorème: les axiomes de Armstrong sont complets. Autrement dit, si <math>\mathcal{F}</math> est un ensemble de dépendances, et si toutes les tables qui satisfont <math>\mathcal{F}</math> satisfont également <math>X\to Y</math>, alors on peut déduire la dépendance <math>X\to Y</math> uniquement à partir de <math>\mathcal{F}</math> et des axiomes de Armstrong.

			<u>Remarque :</u> la contraposé de ce théorème garantit qu'une dépendance ne peut pas se déduire d'autres dépendances ssi il y a une table contre-exemple...



			===Calcul des recouvrements===

			Si <math>\mathcal{F}</math> est un ensemble de dépendances, l'ensemble de toutes les dépendances générées (appelé <math>\mathcal{F}^+</math> par <math>\mathcal{F}</math> est potentiellement de taille exponentielle par rapport à la taille de <math>\mathcal{F}</math>. Par exemple, si on prend <math>\mathcal{F} = \{A\to B_1, A\to B_2, \dots, A\to B_n\}</math>...

			Par contre, si <math>X</math> est un ensemble d'attributs, le calcul de <math>X^+</math> (l'ensemble des attributs <math>A</math> tels que <math>X\to A\ \in\ \mathcal{F}^+</math> peut se faire en temps linéaire. Comme on a <math>X\to Y \ \in\ \mathcal{F}^+</math> ssi $Y\subseteq X^+</math>, cet algo remplace avantageusement le calcul de <math>\mathcal{F}^+</math>.

			<u>Algorithme :</u> on va calculer une suite <math>X_0, \dots , X_n</math> d'ensembles d'attributs, et le dernier terme de cette suite sera exactement <math>X^+</math> :
			* on initialise <math>X_0 = X\!</math>
			* on calcule <math>X_{i+1} = X_{i} \cup \{ A\ \|\ Y\to A,Z \in \mathcal{F}, Y\sub X_i\}</math>.

			Le calcul s'arrête lorsque <math>X_i=X_{i+1}</math>.


			<u>Remarque :</u> il faut quand même transformer ça en véritable algo, et il faut faire attention si on veut effectivement obtenir un algo linéaire.


			;Définition :
			* si <math>\mathcal{F}</math> et <math>\mathcal{G}</math> sont deux ensembles de dépendances, on dit que <math>\mathcal{F}</math> et <math>\mathcal{G}</math> sont équivalents si <math>\mathcal{F}^+ = \mathcal{G}^+</math>. On dit aussi que $\mathcal{G}</math> est un recouvrement de <math>\mathcal{F}</math>.
			* un ensemble <math>\mathcal{F}</math> de dépendances est minimal si les trois propriétés suivantes sont vérifiées:
			** les dépendances de <math>\mathcal{F}</math> n'ont qu'un seul attribut à droite de la flèche
			** si on enlève une dépendance de <math>\mathcal{F}</math>, l'ensemble obtenu n'est pas équivalent à <math>\mathcal{F}</math>
			** si <math>X\to Y</math> est dans <math>\mathcal{F}</math>, et si <math>A\in X</math>, alors si on remplace <math>X\to Y</math> par <math>X\setminus \{A\}\to Y</math>, l'ensemble obtenu n'est pas équivalent à <math>\mathcal{F}</math>.


			;Propriété: si <math>\mathcal{F}</math> est un ensemble de dépendances, on peut toujours trouver un ensemble minimal équivalent à <math>\mathcal{F}</math>. Un tels ensemble est appelé recouvrement minimal de <math>\mathcal{F}</math>.

			Pour trouver un recouvrement minimal, on se débrouille pour satisfaire les 3 propriétés dans l'ordre...


			<u>Remarque :</u> un tels ensemble n'est pas unique ; et son cardinal n'est pas unique non plus:
			* <math>A,B\to C</math>, <math>A\to B</math> et <math>B\to A</math> : pour l'étape 3, on peut supprimer <math>A</math> ou <math>B</math> dans la première dépendance, mais pas les deux à la fois,
			* <math>A\to B</math>, <math>A\to B</math>, <math>B\to A</math>, <math>A\to C</math>, <math>C\to A</math> et <math>B\to C</math> : pour l'étape 2, on peut supprimer <math>B\to C</math> ou bien <math>B\to A</math> <u>et</u> <math>A\to C</math>.

	==Formes normales==		==Formes normales==

Hyvernat : /* Les support de TD et TP */

2008-11-18T09:30:37Z

Les support de TD et TP

← Version précédente		Version du 18 novembre 2008 à 09:30
Ligne 36 :		Ligne 36 :
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/tp1.pdf tp1]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/tp1.pdf tp1]
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td3.pdf td3]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td3.pdf td3]
			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info710/td4.pdf td4]

	==Introduction==		==Introduction==

Hyvernat : /* Organisation des séances */

2008-11-18T09:30:16Z

Organisation des séances

← Version précédente		Version du 18 novembre 2008 à 09:30
Ligne 27 :		Ligne 27 :
	* septième séance (20/10/2008) : TP1.		* septième séance (20/10/2008) : TP1.
	* huitième séance (3/11/2008) : cours (algèbre relationnelle), TD3.		* huitième séance (3/11/2008) : cours (algèbre relationnelle), TD3.
			* neuvième séance (10/11/2008) : TD3.
			* dixième/onzième séance (17/03/2008) : dépendances fonctionnelles, axiomes de Armstrong et recouvrements, TD4.

	==Les support de TD et TP==		==Les support de TD et TP==

INFO710 : Compléments de base de données - Historique des versions

Hyvernat : /* Les support de TD et TP */

Hyvernat : /* Les support de TD et TP */

Hyvernat : /* Intégration avec d'autres outils */

Hyvernat : /* Le langage SQL, deuxième partie */

Hyvernat : /* Formes normales */

Hyvernat : /* Organisation des séances */

Hyvernat : /* Les support de TD et TP */

Hyvernat : /* Modèle théorique : modèle relationnel */

Hyvernat : /* Les support de TD et TP */

Hyvernat : /* Organisation des séances */

Hyvernat : /* Les support de TD et TP */

Hyvernat : /* Les support de TD et TP */

Hyvernat : /* Intégration avec d'autres outils */

Hyvernat : /* Le langage SQL, deuxième partie */

Hyvernat : /* Formes normales */

Hyvernat : /* Organisation des séances */

Hyvernat : /* Les support de TD et TP */

Hyvernat : /* Modèle théorique : modèle relationnel */

Hyvernat : /* Les support de TD et TP */

Hyvernat : /* Organisation des séances */