Slide1 Lemodèlerelationnel: Langagesderequêtesetdemiseàjourfc.isima.fr/~ftoumani/enseignement/intro-BD/SupportsCours/... · Introductionauxbasesdedonnées-2009/2010 F.Toumani Slide1

Introduction aux bases de données - 2009/2010 F.Toumani

Slide 1

'

&

$

%

Le modèle relationnel :Langages de requêtes et de mise à jour

Slide 2

'

&

$

%

Langages de requêtes

Le modèle relationnel défini de manière rigoureuse des langages derequêtes simples et puissants

– Approche algébrique : Algèbre relationnelleLangage procédurale, mais très utile pour représenter les plansd’exécution des requêtes

– Approche logique– Calcul relationnelOrienté utilisateur car il est plus proche du langage naturel :permet à un utilisateur de décrire le résultat recherché sansspécifier comment l’obtenir (langage déclaratif)

– DatalogLangage déclaratif à base de règlesAugmente le calcul relationnel avec des capacités d’inférence


Slide 3

'

&

$

%

Notions préliminaires

– Une requête est appliquée à des instances de relations,– Le résultat d’une requête est une instance de relation.– Le schéma de la relation résultat est déterminé par la définition desconstructeurs du langage de requêtes utilisé

Slide 4

'

&

$

%

Exemple

La relation r1 sur StudentName Age Address dept

Toto 21 Clermont Computing

Dupond 35 Paris Maths

Durand 45 Lyon linguistics

Dan 34 Lyon Computing

La relation r2 sur Department

loc mgr dept

Bât A Ullman Computing

Bât B Mendelson Maths

Bât C Dupond linguistics


Slide 5

'

&

$

%

L’algèbre relationnelle

Proposée par Codd en 1970

– C’est une collection d’opérateurs algébriques– Entrée : une ou deux relations– Sortie : une relation

– Requête relationnelle : composition d’un nombre fini d’opérateursalgébriquesL’ordre d’évaluation des opérateurs est spécifié dans la requête(requête procédurale)

– Possibilité de composition des opérations puisque chaque opérationrenvoie une relation (propriété de fermeture de l’algèbre relationnelle)

Slide 6

'

&

$

%

Opérateurs de l’algèbre relationnelle

– Opérations de base– Projection (π) : suppression des attributs d’une relation– Selection (σ) : sélection d’un sous ensemble de tuples d’une relation.– Produit cartésien (×) : combinaison de deux relations– Différence (−) : sélection des tuples d’une relation r1 quin’appartiennent pas à une relation r2

– Union (∪) : sélection des tuples d’une relation r1 et de ceux d’uneautre relation r2

– Opérations supplémentaires : Intersection (∩), jointure (./), division(÷), renommage (ρA→B) (non essentielles, mais très utiles)


Slide 7

'

&

$

%

Projection et sélection

Soit r une relation sur R

– Projection : la projection de r sur Y ⊆ schema(R), notée πY (r), estdéfinie comme suit : πY (r) = {t[Y ] | t ∈ r}

– Selection– Une formule de sélection simple sur R est une expression de laforme : A = a ou A = B, où A,B ∈ Schema(R) et a ∈ Dom(A)

– Une formule de sélection est une expression composée de formulesde sélection simples connectées à l’aide des connecteurs logique∧,∨,¬ et des parenthèses

– Opération de sélection : La sélection des tuples de la relation r parrapport à F , notée σF (r), est définie comme suit :σF (r) = {t ∈ r | t |= F}(cf. notion d’implication logique (|=) dans le transparent suivant)

Slide 8

'

&

$

%

Implication logique (|=)

1. t |= A = a si t[A] = a

2. t |= A = B si t[A] = t[B]

3. t |= F1 ∧ F2 si t |= F1 et t |= F2

4. t |= F1 ∨ F2 si t |= F1 ou t |= F2

5. t |= ¬F si t 6|= F

6. t |= (F ) si t |= F


Slide 9

'

&

$

%

Opérations ensemblistes

Soient r1 et r2 deux relations sur R

– Union : r1 ∪ r2 = {t | t ∈ r1 ou t ∈ r2}– Différence : r1 − r2 = {t | t ∈ r1 et t /∈ r2}– Intersection : r1 ∩ r2 = {t | t ∈ r1 et t ∈ r2}

Note :– r1 ∩ r2 = r1 − (r1 − r2)– σ¬F (r) = r − σF (r)– σF1∨F2(r) = σF1(r) ∪ σF2(r)– σF1∧F2(r) = σF1(r) ∩ σF2(r)

Slide 10

'

&

$

%

Produit cartésien

Soient r1 et r2 deux relations sur R1 et R2 respectivement, avecschema(R1) ∩ schema(R2) = ∅.Le produit cartésien r1 × r2 est une relation sur un schéma de relationR, avec schema(R) = schema(R1) ∪ schema(R2), définie par :

r1 × r2 = {t|∃t1 ∈ r1 and ∃t2 ∈ r2 tel que t[schema(R1)] =t1 et t[schema(R2)] = t2}

– Si schema(R1) ∩ schema(R2) 6= ∅, alors il y a un conflit entre lesattributs de mêmes noms dans R1 et R2 (résolution de ce type deconflit à l’aide de l’opérateur de renommage)


Slide 11

'

&

$

%

Jointure

Soient r1 et r2 deux relations sur R1 et R2 respectivement.

– Jointure naturelleLa jointure naturelle de r1 et r2 (notée r1 ./ r2) est une relation surun schéma de relation R, avecschema(R) = schema(R1) ∪ schema(R2), définie comme suit :r1 ./ r2 = {t|∃t1 ∈ r1 and ∃t2 ∈ r2 tel que t[schema(R1)] =t1 et t[schema(R2)] = t2}

– Theta−jointure : r1 ./F r2 = σF (r1 × r2)

Note :– Si schema(R1) = schema(R2), alors r1 ./ r2 = r1 ∩ r2– Si schema(R1) ∩ schema(R2) = ∅, alors r1 ./ r2 = r1 × r2

Slide 12

'

&

$

%

Algorithme Join

Soient r1 et r2 deux relations sur R1 et R2 respectivement etX = schema(R1) ∩ schema(R2)

Join(r1, r2)

1: Result := ∅2: for all t1 ∈ r1 do3: for all t2 ∈ r2 do4: if t1[X] = t2[X] then5: Joined_tuple := a tuple over R s.t.6: Joined_tuple[schema(R1)] = t1 and7: Joined_tuple[schema(R2)] = t2 and8: Result := Result ∪ Joined_tuple

Ensure: Result


Slide 13

'

&

$

%

Renommage

Soit r une relation sur R, A ∈ schema(R) et B 6∈ schema(R)

Le renommage de A en B dans r, noté ρA→B(r), est une relation sur Stel que :– schema(S) = schema(R)− {A} ∪ {B}, et– ρA→B(r) = {t|∃u ∈ r, t[schema(S)− {B}] =u[schema(R)− {A}] et t[B] = u[A]}

Slide 14

'

&

$

%

Division

– La division permet d’exprimer la quantification universelle (∀).Exemple de requête pour la quelle la division est utile : "Donner laliste des étudiants qui sont inscrits dans tous les départements"

– Définition formelle de la divisionSoit r une relation sur R, avec schema(R) = XY , et s une relationsur S, avec schema(S) = Y . La division de r par s, notée r ÷ s, estune relation sur un schéma de relation R1, avec schema(R1) = X,définie par :r ÷ s = {t[X]|t ∈ r et s ⊆ πY (σF (r)), ou X ={A1, . . . , Aq} et F est la formuleA1 = t[A1] ∧ . . . ∧Aq = t[Aq]}


Slide 15

'

&

$

%

Exemples de division

r1

sno pno

s1 p1

s1 p2

s1 p3

s1 p4

s2 p1

s2 p2

s3 p2

s4 p2

s4 p4

r2

pno

p2

r1 ÷ r2sno

s1

s2

s3

s4

r3

pno

p2

p4

r1 ÷ r3sno

s1

s4

r4

pno

p1

p2

p4

r1 ÷ r4sno

s1

Slide 16

'

&

$

%

Expression de r ÷ s

La division n’est pas une opération essentielle car elle peut être expriméeà l’aide des opérations de projection, différence et produit cartésien

Pour calculer r ÷ s, il faut calculer toutes les valeurs de X dans r qui nesont pas disqualifiées par des valeurs de Y dans sUne valeur de X est disqualifiée si en lui rattachant une valeur de Y des, le tuple XY obtenu n’appartient pas à r

– Valeurs disqualifiées de X : πX((πX(r)× s)− r)– r ÷ s = πX(r)− valeurs disqualifiées de X⇒ r ÷ s = πX(r)− πX((πX(r)× s)− r)


Slide 17

'

&

$

%

Complétude

Un langage d’interrogation de bases de données relationnelles est ditrelationnellement complet si il peut exprimer toute requête exprimabledans l’algèbre relationnelle

Extension de l’algèbre relationnelleDeux extensions importantes, très utiles en pratiques .. mais qui ne sontpas considérées comme faisant partie de l’algèbre relationnelle :– Fermeture transitive– Fonctions d’agrégation

Slide 18

'

&

$

%

Exemple

Relation Family

Parent Child

p1 p3

p1 p4

p2 p4

p2 p5

p3 p6

p3 p7

p7 p12

Requête : "Donner la liste des parents

et leurs petits-fils"

πGparent,Gchild(ρChild→Jatt(ρParent→Gparent(Family))

./ ρParent→Jatt(ρChild→Gchild(Family))))

Requête impossible avec l’algèbre relationnelle :

"Donner tous les descendants de p1 "


Slide 19

'

&

$

%

Fermeture transitive

Soit r une relation sur R, avec schema(R) = {att(1) = A, att(2) = B},et Dom(A) = Dom(B). La fermeture transitive de r, notée r+, estdéfinie comme étant le résultat de l’algorithme suivant :Algorithm r+

1: Result := r

2: TMP := ∅3: while Tmp 6= Result do4: Tmp := Result

5: Result := Result ∪Qjoin(Result)

Ensure: Result

Note : Qjoin(R) dénote la requête suivante :π{A,B}(ρB→Jatt(R) ./ ρA→Jatt(R))

Slide 20

'

&

$

%

Fonctions d’agrégation

Les fonctions d’agrégation permettent de répondre aux requêtes dutype :"Quel est le nombre d’étudiants inscrits dans chaque département""Quel est l’âge moyen des étudiants"

Définition (fonction d’agrégation)Soit R un schéma de relation et A ∈ schema(R). Une fonctiond’agrégation fA sur R est une fonction calculable qui pour un ensemblefini de tuples sur R renvoie une valeur entière.Exemples de fonctions : MIN,MAX,AV G,COUNT


Slide 21

'

&

$

%

Algorithme

Soit fA une fonction d’agrégation sur R,X ⊆ schema(R) et supposantque Af /∈ schema(R). Le resultat de l’application de fA à une relation rsur R avec une partition X, notée fX

A , est une relation sur S, avecschema(S) = X ∪Af , définie par l’algorithme suivant :

Algorithm AGG(fa, X, r)

1: Result := ∅2: P := a partition of r s.t. t1, t2 are in the same block in P iff t1[X] = t2[X]

3: for all block Bi in the partition P do4: Agg_tuple[X] := a tuple over S such that5: Agg_tuple[X]=t[X] with t ∈ ri and6: Agg_tuple[Af ]=fA({t|t ∈ B}]7: Result := Result ∪ {Agg_tuple}

Ensure: Result

Slide 22

'

&

$

%

Langages logiques

Donner les noms et âges des étudiants du département dont le managerest ‘Ullman’.

Deux approches :

– Approche basée sur les variables domainesSi les tuples 〈xna, xag, xad, xde〉 et 〈xlo, ‘Ullman′, xde〉 sontrespectivement dans les relations Student et Department alorsinclure dans la réponse le tuple 〈Name : xna, Age : xag〉,où xna, xag, xad, xde, xlo sont des variables.

– Approche basée sur les tuplesSi les tuples t1 et t2 respectivement dans les relations Student etDepartment sont tels que le manager dans t1 est "Ullman" et lesnoms de département (attribut dept) dans t1 et t2 sont les mêmesalors nous voulons les nom et âge du tuple t1.


Slide 23

'

&

$

%

Le calcul relationnel

– Deux types de calculs : Calcul relationnel de tuples (TRC) et calculrelationnel de domaine (DRC).

– Le calcul utilise des variables, des constantes, des opérateurs decomparison, des connecteurs logiques et des quantificateurs– TRC : les variables prennent comme valeurs des tuples.– DRC : les variables prennent comme valeurs des éléments dudomaine.

TRC et DRC sont des sous-ensembles de la logique du premier ordre– Les expressions dans le calcul sont appelées formules– Un tuple réponse est une affectation de constantes à des variables quipermet à la formule d’être évaluée à vrai

Slide 24

'

&

$

%

Syntaxe DRC

Symboles autorisés dans une formule– Constantes : v1, . . . , vn membres de l’ensemble D– Variables : x1, . . . , xn membres d’un ensemble infini dénombrable Vdisjoint de D

– Symboles de relations : R,R1, R2, . . ., chacun correspondant auschéma de relation qui lui est associé

– Opérateurs de comparaison : <,>,=,≤,≥, 6=– Quantificateurs et connecteurs logiques : ∃,∀,∧,∨,⇒,¬– Délimiteurs : () et ,


Slide 25

'

&

$

%

Formules DRC

Une formule est définie de manière récursive, commençant par desformules atomiques simples , et construisant ensuite des formules pluscomplexes en utilisant les connecteurs logiques– Formule atomique– R(x1, . . . , xn), où R est un symbole de relation avec type(R) = n et∀i[1, n], xi est une constante ou une variable

– x op y, où x est une variable, y une constante ou une variable etop ∈ {<,>,=,≤,≥, 6=}

– Formule bien formée– Une formule atomique– (p),¬p, p ∧ q, p ∨ q, p⇒ q où p et q sont des formules– ∃x : A(F ), ∀x : A(F ) où F est une formule, x une variable et A unnom d’attribut

Slide 26

'

&

$

%

Variables libres et variables liées

Les quantificateurs ∃ et ∀ permettent de lier les variables

– Toutes les variables apparaissant dans une formule atomique sontlibres

– Les variables libres apparaissant dans ¬F sont les mêmes que ceuxapparaissant dans la formule F

– Les variables libres apparaissant dans les formules F1 ∧ F2, F1 ∨ F2 etF1 ⇒ F2 sont les variables libres qui apparaissent dans F1 ou dans F2

– Les variables libres qui apparaissent dans ∃x : A(F ) et ∀x : A(F ) sontles variables libres qui apparaissent dans F excepté les occurrences dex dans F


Slide 27

'

&

$

%

Calcul relationnel de domaine

Soit d = {r1, . . . , rm} une base de données sur un schémaR = {R1, . . . , Rm}.– Une requête à la forme suivante :

{〈x1 : A1, . . . , xn : An〉|F (〈x1, . . . , xn〉)}

où : F est une formule bien formée,A1, . . . , An sont des attributs distincts appartenant à Ux1, . . . , xn sont des variables libres dans F

– Réponse : relation r sur un schéma R avecschema(R) = {A1, . . . , An} définie par : r = {t | t satisfait F}

Un tuple 〈v1, . . . , vn〉 satisfait la formule F par rapport à d, si∀i ∈ [1, n], vi ∈ DOM(Ai), et une des six conditions suivantes estvérifiée :

Slide 28

'

&

$

%

Satisfaction d’une formule

1. F est la formule atomique R(y1, . . . , yk) (avec R ∈ R) et le tuplet = 〈y1/v1, . . . , yk/vk〉 ∈ r où r est la relation sur R dans d

2. F est la formule atomique xi = yj alors on a vi = vj où vi estsubstituée à xi et, si yj est une variable alors vj est substituée à yj

ou bien yj est une constante et dans ce cas yj = vj

3. F est la formule (G) et t satisfait la formule G4. F prend une de ces formes : ¬F, F1 ∧ F2, F1 ∨ F2, F1 ⇒ F2 (cf.

sémantique du connecteur logique correspondant)5. F est la formule ∃xi : A(G(x1, . . . , xi, . . . , xn)) alors〈v1, . . . , vi−1, vi+1, . . . , vn〉 satisfait F si il existe une constantevi ∈ DOM(A) tel que 〈v1, . . . , vi−1, vi, vi+1, . . . , vn〉 satisfait G

6. F est la formule ∀xi : A(G(x1, . . . , xi, . . . , xn)) alors〈v1, . . . , vi−1, vi+1, . . . , vn〉 satisfait F pour toute constantevi ∈ DOM(A) le tuple 〈v1, . . . , vi−1, vi, vi+1, . . . , vn〉 satisfait G


Slide 29

'

&

$

%

Exemple (rappel)

La relation r1 sur StudentName Age Address dept

Toto 21 Clermont Computing

Dupond 35 Paris Maths

Durand 45 Lyon linguistics

Dan 34 Lyon Computing

La relation r2 sur Department

loc mgr dept

Bât A Ullman Computing

Bât B Mendelson Maths

Bât C Dupond linguistics

Slide 30

'

&

$

%

Exemples de requêtes

Donner la liste de tous les étudiants qui habitent à ’Clermont’{x1 : Name, x2 : Age, x4 : Dept|∃x3 : address(Student(x1, x2, x3, x4) ∧ x1 = ‘Clermont′)}La condition Student(x1, x2, x3, x4) assure que les variables de domainex1, x2, x3 et x4 sont liées aux champs du même tuple de la relation r1sur Student.

– "Donner la liste de tous les étudiants"{x1 : Name, x2 : Age, x3 : Address, x4 : Dept|Student(x1, x2, x3, x4)}

– "Donner les noms et les départements de tous les étudiants"{x1 : Name, x4 : Dept|∃x2 : Age(∃x3 :Address(Student(x1, x2, x3, x4)))}


Slide 31

'

&

$

%

Exemples de requêtes (cont.)

– "Donner les noms et âges des étudiants qui sont soit inscrits dans ledépartement Linguistics soit habitent à Clermont"{x1 : Name, x2 : Age|∃x3 : Address(∃x4 :Dept(Student(x1, x2, x3, x4) ∧ (x4 =′ Linguistics′ ∨ x3 =′

Clermont′)))}ou {x1 : Name, x2 : Age|∃x4 : Dept(Student(x1, x2,

′ Clermont′, x4) ∨∃x3 : Address(Student(x1, x2, x3,

′ Linguistics′))}– "Donner les noms des étudiants non parisiens qui ne sont pas inscritsdans le département Computing"{x1 : Name|∃x2 : Age(∃x3 : Address(∃x4 :Dept(Student(x1, x2, x3, x4) ∧ (x4 6=′ Computing′ ∧ x3 6=′ Paris′))))}

Slide 32

'

&

$

%

Exemples de requêtes (cont.)

– "Donner les noms des étudiants et les localisations des départementsdans lesquels ils sont inscrits"{x1 : Name, x5 : loc|∃x2 : Age(∃x3 : Address(∃x4 : Dept(∃x6 :mgr(Student(x1, x2, x3, x4) ∧Department(x5, x6, x4)))))}

– "Donner la liste des étudiants qui sont inscrits dans tous lesdépartements"{x1 : Name, x2 : Age, x3 : Address, x4 :Dept|Student(x1, x2, x3, x4) ∧ ¬∃x7 : dep(∃x5 : loc(∃x6 :mgr(Department(x5, x6, x7) ∧ ¬Student(x1, x2, x3, x7))))}


Slide 33

'

&

$

%

Requêtes peu sûres

– Il est possible d’écrire des requêtes de calcul correctes du point de vuesyntaxique .. mais qui ont un nombre infini de réponsesDe telles requêtes sont appelées : requêtes peu sûresExemple{x1 : Name|∃x2 : Age(∃x3 : Address(∃x4 :dep(¬Student(x1, x2, x3, x4))))}

– Chaque requête qui peut être exprimée en algèbre relationnel peutégalement être exprimée comme une requête sûre en DRC/TRC ;l’inverse est également vraie.


Slide 34

'

&

$

%

Datalog

Langage logique muni d’une capacité d’inférence (bases de donnéeslogiques ou déductives)Syntaxe

– Formule atomique : prédicat + arguments (cf. calcul relationnel)– Prédicat : symbole de relation ou prédicat arithmétique (e.g., <)– Un prédicat de la forme : R(v1, . . . , vn) où toutes les vi sont desconstantes appartenant respectivement à DOM(att(i)) est appeléatome clos sur R

– Un littéral est soit une formule atomique L (littéral positif) ou sanégation ¬L (littéral négatif)

Slide 35

'

&

$

%

Notion de règle

Une règle (clause) est une expression de la forme :

tete︷︸︸︷L `

Corps︷︸︸︷L1, . . . , Ln

où chaque Li est un littéralSi n = 0 et L1 est un atome clos, alors L est un fait

Exemple de faits :

Student(Toto, 21, Clermont, Computing),Department(Bât A, Ullman, Computing)

Une règle est une "usine à fournir des faits"


Slide 36

'

&

$

%

Programme Datalog

– Un programme Datalog est une collection de règles– Deux classes de prédicats/relations– EDB (extensional database schema) : l’ensemble de tous les nomsde relations apparaissant uniquement dans le corps des règles.

– IDB (intensional database) : l’ensemble de tous les noms derelations apparaissant au moins une fois dans une tête de règle.

– Un prédicat est soit un IDB soit un EDB– Deux types de programmes Datalog : récursifs et non recursifsExemple : programme Datalog récursif :Ancetre(x1, x2) ` Parent(x1, x2)Ancetre(x1, x3) ` Parent(x1, x2), Ancetre(x2, x3)

Slide 37

'

&

$

%

Exemple d’un programme Datalog

Considérons le Programme Datalog P suivant :Student(Toto, 21, Clermont, Computing)Student(Dupond, 35, Paris,Maths)Student(Durand, 45, Lyon, linguistics)Student(Dan, 34, Lyon,Computing)Department(BatA,Ullman,Computing)Department(BatB,Mendelson,Maths)Department(BatC,Dupond, linguistics)Course−loc(x1, y2) ` Student(x1, x2, x3, x4), Department(y1, y2, x4)–"Requête : Donner la liste de tous les étudiants"Result1(x1, x2, x3, x4) ` Student(x1, x2, x3, x4)

edb(P ) = {Student,Department}idb(P ) = {Course−loc, Result1}


Slide 38

'

&

$

%

Exemple de requêtes Datalog

– "Donner la liste de tous les étudiants"Result(x1, x2, x3, x4) ` Student(x1, x2, x3, x4)

– "Donner les noms et départements de tous les étudiants"Result(x1, x2, x4) ` Student(x1, x2, x3, x4)

– "Donner les noms et âges des étudiants qui sont soit inscrits dans ledépartement Linguistics soit habitent à Clermont"Result(x1, x2) ` Student(x1, x2, x3, x4), x4 =′ Linguistics′

Result(x1, x2) ` Student(x1, x2, x3, x4), x3 =′ Clermont′

– "Donner les noms des étudiants non parisiens qui ne sont pas inscritsdans le département Computing"Result(x1) ` Student(x1, x2, x3, x4), x3 6=′ Paris′, x4 6=′ Computing′

Slide 39

'

&

$

%

Exemple (cont.)

– Union entre deux relations Student1 et Student2 de même schéma :Result(x1, x2, x3, x4) ` Student1(x1, x2, x3, x4)Result(x1, x2, x3, x4) ` Student2(x1, x2, x3, x4)

– Différence entre deux relations Student1 et Student2 de mêmeschéma :Result(x1, x2, x3, x4) `Student1(x1, x2, x3, x4),¬Student2(x1, x2, x3, x4)

– Intersection entre Student1 et Student2 de même schéma :Result(x1, x2, x3, x4) `Student1(x1, x2, x3, x4), Student2(x1, x2, x3, x4)

– Division entre deux relations R1(X,Y ) et R2(Y ) :Result(x1) ` R1(x1, x3),¬DIFF (x1)DIFF (x1) ` PROD(x1, x3),¬R1(x1, x2)PROD(x1, x2) ` R1(x1, x3), R2(x2)


Slide 40

'

&

$

%

Programmes peu sûrs

Un programme Datalog à un sens uniquement si la relation qui peutêtre dérivée en exécutant ces programmes est finie.

Exemples de règles non sûres :Result(x) ` Student(x1, x2, x3, x4)Result(x1, x2, x4) ` ¬Student(x1, x2, x3, x4)Result(x1) ` Student(x1, x2, x3, x4), x5 = x6

Slide 41

'

&

$

%

Programme Datalog sûrs

Une variable x apparaît positivement dans une règle C ssi :

– x apparaît dans un prédicat R(y1, . . . , x, . . . , yk), qui est un littéralpositif dans le corps de C, ou

– x apparaît dans une formule d’égalité x = v, qui est un littéral positifdans le corps de C, où v est une constante, ou

– x apparaît dans une formule d’égalité x = y ou y = x, qui est unlittéral positif dans le corps de C, où y est une variable qui apparaîtpositivement dans C

Definition 1 (Programme Datalog sûrs)Une règle Datalog C est dite sûre si toutes les variables qui apparaissentdans les littéraux de C (dans le corps ou dans la tête) apparaissentpositivement dans C

Un programme Datalog P est dit sûr si toutes les règles de P sont sûres


Slide 42

'

&

$

%

Remarques

– Dans une règle Datalog sûre C, toutes les variables qui apparaissentdans la tête doivent apparaître au moins une fois dans le corps de C.

– Toutes les variables apparaissant dans les littéraux négatifs dans lecorps d’une règle sûre doivent également apparaître positivement dansau moins une formule atomique dans le corps de la règle

Slide 43

'

&

$

%

Définitions

Definition 2 (Schéma d’un programme Datalog)Le schéma de base de données d’un programme Datalog P , notéSCHEMA(P ), est l’ensemble des schémas de relations défini par :SCHEMA(P ) = {R|R est un symbole de relation qui apparaît dans unlittéral d’une règle dans P}Exemple : SCHEMA(P ) = {Student,Department, Course−loc}

Definition 3 (Substitution de variables)Soit C une règle Datalog et {x1, . . . , xq} les variables apparaissant dansles littéraux du corps de C. Une substitution θ pour C est l’ensembledes affectations {x1/v1, . . . , xq/vq}, où les vi sont des constantes.Notons C(θ) la clause résultant de l’application de la substitution θ aulittéraux dans C.

Note : Tous les littéraux de la clause C(θ) sont des atomes clos.


Slide 44

'

&

$

%

Vérité d’une clause par rapport à une BD

Un littéral L dans le corps d’une clause C d’un programme Datalog Pest vrai par rapport à une substitution θ pour C et une base de donnéesd sur un schéma SCHEMA(P ) si l’une des conditions suivantes estsatisfaites :

– θ(L) est un atome clos atomique de la forme R(v1, . . . , vk) et〈v1, . . . , vk〉 ∈ r, où r ∈ d est la relation sur R

– θ(L) est une égalité v = v où v est une constante– θ(L) est un atome clos de la forme ¬R(v1, . . . , vk) et 〈v1, . . . , vk〉 6∈ r,où r ∈ d est la relation sur R

– θ(L) est un littéral négatif de la forme ¬(vi = vj), où vi et vj sont desconstantes distinctes, i.e., vi 6= vj

Une clause C dans un programme P est vraie par rapport à unesubstitution θ pour C et une base de données d sur SCHEMA(P ) sichacun des littéraux du corps de C est vrai par rapport à θ et d

Slide 45

'

&

$

%

Sémantique d’un programme Datalog

La signification d’un programme Datalog P , notée Meaning(P ), est labase de données résultant de l’augmentation de l’ensemble des faitsinitial d’un programme P par tous les nouveaux faits possibles de laforme θ(L), où θ est une substitution qui rend une règle C de P vraie etL est la tête de C.

Note : D’autres types de sémantiques sont possibles.


Slide 46

'

&

$

%

Algorithme Meaning

Meaning(P)

1: Result := ∅2: TMP := {〈〉}3: while TMP 6= Result do4: TMP := Result

5: Im := ∅6: for all clauses C in P and substitutions θ for C such that C is true

with respect to θ and Result do7: Im := Im ∪ {θ(L)} where L is the head of C8: Result := Result ∪ Im

Ensure: Result

Slide 47

'

&

$

%

Exemple


Slide 48

'

&

$

%

Un résultat intéressant

Soit CONST (P ) l’ensemble des constantes apparaissant dans leslittéraux des clauses d’un programme Datalog P .

θ = {x1/v1, . . . , xq/vq} est une substitution sûre pour une clause C dansP si {v1, . . . , vq} ⊆ CONST (P )

– Lors du calcul de Meaning(P ) pour un programme Datalog P sûr, ilsuffit de considérer uniquement les substitutions sûres

– Si uniquement les substitution sûres sont considérées, alors lesprogramme Datalog sûrs et non sûrs sont équivalents

Slide 49

'

&

$

%

Langage de mise à jour pour le modèle relationnel

Notions préliminaires

– Une condition simple sur R est soit une expression de la forme A = a

ou A 6= a, où A ∈ schema(R) et a ∈ Dom(A)– Une condition C sur R est une conjonction c1 ∧ . . . ∧ cn de conditionssimples ci, i ∈ [1, n], tel que C ne contient pas deux conditionssimples distinctes de la forme (A = a et A = b) ou (A = a et A 6= a)pour A ∈ schema(R)

– Une condition positive sur R est une condition de la formeA1 = a1 ∧ . . . ∧An = an, où {A1, . . . , An} ∈ schema(R) etai ∈ Dom(Ai)

– Une condition complète sur R est une condition positive sur R avec{A1, . . . , An} = schema(R)


Slide 50

'

&

$

%

Satisfaction d’une condition

Soit r une relation sur R, et t un tuple dans r. Soit C = c1, . . . , cn unecondition sur R.t satisfait C, noté t |= C, est définie comme suit :

– t |= A = a si t[A] = a est vraie– t |= A 6= a si t[A] 6= a est vraie– t |= C si t |= ci,∀i ∈ [1, n] est vraie

Slide 51

'

&

$

%

Opérations de mise à jour

Soit r une relation sur un schéma R, avec schema(R) = {A1, . . . , An}.Une mise à jour sur R est soit une insertion, une suppression ou unemodification sur R.

– Une insertion sur R est notée insert(C) où C est une conditioncomplète sur R.[insert(C)](r) = r ∪ {t | t |= C}

– Une suppression sur R est notée delete(C) où C est une condition surR.[delete(C)](r) = r − {t | t |= C}

– Une modification d’un tuple t sur R par rapport à une condition C,notée [modify(C)](t) est définie par :[modify(C)](t) = u où u est un tuple sur R tel que∀Ai ∈ schema(R), u[Ai] = ai si (Ai = ai) ∈ C, sinon u[Ai] = t[Ai]


Slide 52

'

&

$

%

Opérations de mise à jour (cont.)

– Une modification sur un schéma R est une expression de la formemodify(C1;C2), où C1 et C2 sont des conditions sur R telles que∀A ∈ schema(R), siA 6= a est dans C2 alors A 6= a est aussi dans C1.[modify(C1;C2)](r) = (r − {t | t |= C1}) ∪ {[modify(C2)](t) | t ∈r et t |= C1}

Slide 53

'

&

$

%

Exemples

– [insert(Name = Jean ∧Age = 24 ∧Address = Paris ∧ dept =Maths)](r)

– [delete(Name = Jean ∧Address 6= Paris)](r)– [modify(dept = MTH; dept = Maths)](r)


Slide 54

'

&

$

%

Problème d’équivalence : notions préliminaires

– Domaine actif d’une BD (rappel)Le domaine actif d’une base de données d, noté ADOM(d), estl’ensemble des constantes apparaissant dans d

– Domaine actif d’une requêteLe domaine actif d’une requête Q, noté ADOM(Q), est l’ensembledes constantes apparaissant dans Q

– Indépendance du domaineUne requête Q est indépendante du domaine si pour toute base dedonnées d, les réponses de Q sur d dépendent uniquement deADOM(Q) ∪ADOM(d)

– Réponse à une requêteSoit Q une requête ayant pour arguments des schémas de relationsdans un schéma de base de données R. Si d est la base de donnéesassociée à R, la réponse à la requête Q sera notée Q(d).

Slide 55

'

&

$

%

Equivalence de requêtes et de langages

– Equivalence de requêtesSoient Q1 et Q2 deux requêtes dont les arguments sont des schémasde relations dans un schéma de base de données R.Q1 ≡ Q2 si pour toute base de données d sur R, on a : Q1(d) = Q2(d).

– Inclusion de langagesUn langage L1 est contenu dans un autre langage L2 si pour touterequête Q1 de L1 il existe une requête Q2 de L2 tel que : Q1 ≡ Q2.

– Equivalence de langagesUn langage L1 est équivalent à langage L2 si L1 est contenu dans L2

et vice versa.


Slide 56

'

&

$

%

Requêtes indépendantes du domaine

Les requêtes de l’algèbre relationnelle et les requêtes Datalog sûres sontindépendantes du domaine, celles du calcul relationnels ne le sont pas.

Exemple : soient Etudiant et Inscrit deux schémas de relations avecschema(Etudiant) = schema(Inscrit) = {nom}. Les requêtes suivantesont une réponse infinie si DOM(nom) est infini.

{x : nom|¬Etudiant(x)}

{x1 : nom, x2 : nom|Etudiant(x1) ∨ Inscrit(x2)}

D’où deux problèmes principaux dans les requêtes du calcul :

– La requête contient une formule ¬F telle qu’une des variables de Fn’apparaît pas positivement ailleurs

– La requête contient une formule de la forme F1 ∨ F2 telle que lesvariables libres de F1 sont distinctes de celles de F2

Slide 57

'

&

$

%

Requêtes indépendantes du domaine (suite)

ThéorèmeDéterminer si une requête du calcul relationnel est indépendante dudomaine est indécidable.

Ce résultat impose de restreindre les formules valides de façon à rendreles requêtes du calcul indépendante du domaine.

Deux notions :– variables positives– variables négatives


Slide 58

'

&

$

%

Variable positive

Une variable x est positive dans une formule si :– x est positive dans une formule atomique R(y1, . . . , x, yk)– x est positive dans une formule atomique x = v où v est une constante– x est positive dans la formule ¬F qui contient x, si x est négativedans F

– x est positive dans la formule F1 ∧ F2 si x est positive dans F1 ou xest positive dans F2

– x est positive dans la formule F1 ∨ F2 si x est positive dans F1 et xest positive dans F2

– x est positive dans la formule F1 ⇒ F2 si x est négative dans F1 et xest positive dans F2

– x est positive dans la formule ∃y : A(F ), si x 6= y et x est positivedans F

Slide 59

'

&

$

%

Variable négative

Une variable x est négative dans une formule si :– x est négative dans une formule atomique x = y où y est une variable– x est négative dans la formule ¬F si x est positive dans F– x est négative dans la formule F1 ∧ F2 si x est négative dans F1 et xest négative dans F2

– x est négative dans la formule F1 ∨ F2 si x est négative dans F1 ou xest négative dans F2

– x est négative dans la formule F1 ⇒ F2 si x est positive dans F1 ou xest négative dans F2

– x est négative dans la formule ∀y : A(F ), si x 6= y et x est négativedans F

– si x n’apparaît pas dans une formule F , alors x est négative dans F


Slide 60

'

&

$

%

Exemple

Soient Etudiant, Inscrit et Habite trois schémas de relations avecschema(Etudiant) = schema(Inscrit) = {nom} etschema(Habite) = {nom, adresse}.

Soient les formules suivantes :

F1 = Etudiant(x)

F2 = Etudiant(x1) ∨ Inscrit(x2)

F3 = Habite(x1, x2) ∧ ¬Habite(x1, Lyon)

F4 = Habite(x1, Antragues) ∨Habite(x1, Lyon)

F5 = ∀x : nom(¬Etudiant(x))

F6 = ¬(∃x : nom(Etudiant(x)))

Donner le status des variables dans F1 − F6.

Slide 61

'

&

$

%

Requête du calcul autorisée

Une formule du calcul F est autorisée si :

– Chaque variable libre x de F est positive dans F– Pour chaque sous-formule ∃x : A(G) de F , x est positive dans G– Pour chaque sous-formule ∀x : A(G) de F , x est négative dans G

Une requête de calcul est autorisée si toutes ses formules sont autorisées.

Tester si une requête est autorisée peut se faire par simple récursion surla structure de la formule.

ThéorèmeToute formule autorisée du calcul relationnel est indépendante dudomaine.


Slide 62

'

&

$

%

Exemple (suite)

Soient Etudiant, Inscrit et Habite trois schémas de relations avecschema(Etudiant) = schema(Inscrit) = {nom} etschema(Habite) = {nom, adresse}.

Les requêtes ci-dessous sont elles indépendantes du domaine ?

{x : nom|¬Etudiant(x)}

{x1 : nom, x2 : nom|Etudiant(x1) ∨ Inscrit(x2)}

{x1 : nom|Habite(x1, x2) ∧ ¬Habite(x1, Lyon)}

{x1 : nom|Habite(x1, Antraigues) ∨Habite(x1, Lyon)}

{x : nom|∀x : nom(¬Etudiant(x))}

{x : nom|¬(∃x : nom(Etudiant(x)))}

Slide 63

'

&

$

%

Equivalence des langages relationnels

ThéorèmeLes trois langages relationnels suivants sont équivalents :

– L’algèbre relationnelle– nr−datalog¬ (Datalog sûr non récursif avec la négation)– Le calcul relationnel du domaine autorisé

Résultat fondamental des bases de données

Preuve en TD

Documents

Slide1 Lemodèlerelationnel: Langagesderequêtesetdemiseàjourfc.isima.fr/~ftoumani/enseignement/intro-BD/SupportsCours/... · Introductionauxbasesdedonnées-2009/2010 F.Toumani Slide1