Modèle relationnel

Serge Abiteboul

INRIA

April 3, 2009

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 1 / 39

Introduction

Modèle de bases de données :

LDD (langage de définition de données) +
LMD (langage de manipulation de données)

Modéle relationnel (Ted Codd 1970) :

Données sont structurées en tables
Langages : algèbre, calcul, SQL
Bases : calcul des prédicats du 1er ordre

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 2 / 39

Langage de définition de données

Table : relation, e.g., Film

Colonnes : attribut, e.g., Titre
Lignes : n-uplet (ou enregistrement)
Alphabets
Attributs : att
Constantes (entrées des tables) : dom
Noms de relations : relname
Variables : var
À chaque nom de relation R est associé un ensemble d’attributs
sort(R)
e.g., sort(Pariscope) = {Salle, Titre, Horaire}

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 3 / 39

Base de données Cinéma
Film Titre Directeur Acteur

The Trouble with Harry Hitchcock Gwenn

The Trouble with Harry Hitchcock Forsythe
The Trouble with Harry Hitchcock MacLaine
The Trouble with Harry Hitchcock Hitchcock

· · ·

Cries and Whispers Bergman Andersson

Cries and Whispers Bergman Sylwan
Cries and Whispers Bergman Thulin
Cries and Whispers Bergman Ullman

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 4 / 39

Base de données Cinéma (2)

Coordonnées Salle Adresse

Gaumont Opéra 31 bd. des Italiens

Saint André des Arts 30 rue Saint André des Arts
Le Champo 51 rue des Ecoles

· · ·

Georges V 144 av. des Champs-Elysées

Les 7 Montparnassiens 98 bd. du Montparnasse

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 5 / 39

Base de données Cinéma (3)

Pariscope Salle Titre Horaire

Gaumont Opéra Cries and Whispers 20:30

Saint André des Arts The Trouble with Harry 20:15
Georges V Cries and Whispers 22:15

· · ·

Les 7 Montparnassiens Cries and Whispers 20:45

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 6 / 39

Schémas et instances
Schéma de relation : nom de relation R
on l’écrit parfois R[sort(R)] e.g., Pariscope [Salle, Titre, Horaire]
en pratique
relation Coordonnées ( Salle: string, Ad: string, Tél: int)
Schéma de base de données : ensemble de noms de relations
BD = { Film, Coordonnées, Pariscope }
Nuplet sur un ensemble d’attributs U
Une fonction de U dans dom
hSalle : G5, Titre : CaW , Horaire : 20i
Instance de R ou une relation sur U = sort(R) : ensemble fini de
nuplets sur U
Instance I d’un schéma de base de données R
Une fonction dont le domaine est R
pour chaque R dans R, I(R) instance de R.
Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 7 / 39
Autre formalisme possible
colonnes numérotées au lieu d’être nommées
n-uplet : élément du produit cartésien domn
e.g., habdf , dghjac, kadgfdi

Terminologie base de données

I(R) = {f1 , f2 , f3 }
f1 (A) = a f1 (B) = b
f2 (A) = c f2 (B) = b
f3 (A) = a f3 (B) = a
I(S) = {g}
g(A) = d

Terminologie programmation logique

I = {R(a, b), R(c, b), R(a, a), S(d)}.

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 8 / 39

Requêtes conjonctives

Langage très limité mais essentiel

3 paradigmes: algébriques, logiques, tabulaires

1 Algèbre PSJR
2 Calcul conjonctif (sous ensemble calcul des prédicats)
3 Rêgles conjonctives
4 ( Tableaux )

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 9 / 39

Exemples

Qui est le directeur de “Straw Dogs”?

Quelles salles affichent “Straw Dogs”?
Quels sont l’adresse et le numéro de télephone du Studio?
Donner les noms et adresses des salles affichant un film de Bergman.
Quels sont les directeurs qui ont joué dans un film qu’ils ont dirigé.
Donner les paires de personnes telles que la première a dirigé la
seconde, et vice versa;

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 10 / 39

Formalisons l’intuition
Donner les noms et adresses des salles affichant un film de Bergman.
Intuitivement (variables nuplets),

si les n-uplets r1 , r2 , r3 respectivement dans les relations

Film, Pariscope, Coordonnées sont tels que
le Directeur dans r1 est “Bergman”
et les Titres dans r1 et r2 sont les mêmes
et les Salles dans n-uplet r2 et r3 sont les mêmes
alors nous voulons les Salle et Adresse du n-uplet r3 .

Intuitivement (variables domaines)

si les n-uplets hxti , “Bergman”, xac i, hxsa , xti , xs i et hxsa , xad , xp i,

sont respectivement, dans les relations
Film, Pariscope et Coordonnées
alors inclure le n-uplet hSalle : xsa , Adresse : xad i dans la réponse,

où xti , xac , ... sont des variables.

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 11 / 39
Une syntaxe: rêgles conjonctives

Syntaxe utilisant des rêgles

ans(xsa , xad ) ← Film(xti , “Bergman”, xac ), Pariscope(xsa , xti , xs ),

Coordonnes(xsa , xad , xp )

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 12 / 39

Rêgles conjonctives
Une règle conjonctive sur R est une expression q de la forme:

ans(u) ← R1 (u1 ), ..., Rn (un )

n ≥ 0, R1 , ..., Rn ∈ R
ans 6∈ R
u, u1 , ..., un n-uplets libres (i.e., variables + constantes) de bonnes
arités
chaque variable apparaîssant dans u doit aussi apparaître au
moins une fois dans u1 , ..., un .
R1 (u1 ), . . . , Rn (un ) : corps
ans(u) : tête.
Intuition: usine à fournir des faits

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 13 / 39

Requêtes conjonctives

Valuation: V un ensemble de variables, une valuation est une fonction

ν de V dans dom. Pour chaque constante a, ν(a) = a

q(I) = {ν(u) | ν est une valuation sur var (q) et ν(ui ) ∈ I(Ri ),
pour chaque i ∈ [1, n]}.

Exemple:
Domaine actif: adom(I) est l’ensemble des constantes apparaîssant
dans I; similarly adom(q), adom(q, I)
adom(q(I)) ⊆ adom(q, I) (donc q(I) est fini)

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 14 / 39

Une autre syntaxe: Calcul conjonctif
Requête
ans(xsa , xad ) ← Film(xti , “Bergman”, xac ), Pariscope(xsa , xti , xs ),
Coordonnees(xsa , xad , xp )
virgule devient ∧ (conjonction)
variables non dans le résultat sont existentielles ∃
En calcul conjunctif
{xsa , xad | ∃xti ∃xac ∃xs ∃xp (Film(xti , “Bergman”, xac ) ∧
Pariscope(xsa , xti , xs ) ∧
Coordonnees(xsa , xad , xp ))}
Imbrication : Elle s’exprime aussi par:
{xsa , xad | ∃xti ∃xac ∃xs (Film(xti , “Bergman”, xac ) ∧
Pariscope(xsa , xti , xs )) ∧
∃xp (Coordonnees(xsa , xad , xp ))}

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 15 / 39

Formalisme graphique : tableaux
Langage Query-By-Example (QBE).
Les identificateurs commençant par ‘_’ désignent variables (des
“exemples” dans la terminologie QBE)
‘P.’ indique ce qu’il faut imprimer.

Film Titre Directeur Acteur

_The Seventh Seal Bergman

Pariscope Salle Titre Horaire

_Rex _The Seventh Seal

Coordonnées Salle Adresse Téléphone

P._Rex P._1 bd. Poissonnière

Une requête en QBE

Nombreuses interfaces graphiques, e.g., Microsoft Access
Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 16 / 39
Algèbre : PSJR

Langage procédural (algèbre) 6= déclaratif

Facile à implanter
Compiler : calcul → algèbre
Opérations
1 Projection: ne garder que certaines colonnes
2 Sélection: enlever des lignes suivant un critère
3 Jointure: faire un pont entre deux tables
4 Renommage: renommer attributs d’une table

Problème des dupliquets

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 17 / 39

Algèbre : PSJR
R S R ./ S
A B B C A B C
1 2 2 3 1 2 3
4 2 2 5 1 2 5
6 6 9 1 4 2 3
7 7 8 8 4 2 5
1 7
1 6
σA=1 (R) δB:B 0 ,C:A (S) πA (R)
A B B0 A A
1 2 2 3 1
1 7 2 5 4
1 6 9 1 6
8 8 7

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 18 / 39

Algèbre
Algèbre SPJR: sélection (σ), projection (π), jointure (1), renomage (δ)
Sélection: σA=c et σA=B , (A, B ∈ att, a ∈ dom)

σA=c (I) = {t ∈ I | t(A) = c} et σA=B (I) = {t ∈ I | t(A) = t(B)}.

Projection: πA1 ,...,An (n ≥ 0, A1 , . . . , An ∈ att)

πA1 ,...,An (I) = {hA1 : t(A1 ), . . . , An : t(An )i | t ∈ I}

πA1 ,...,An (I) = {t|A1 ,...,An | t ∈ I}.

Jointure (Naturelle):
sort(I) = V , sort(J) = W , sort(I 1 J) = V ∪ W

I 1 J = {t sur V ∪ W | pour v ∈ I et w ∈ J, t|V = v et t|W = w}

sort(I) = sort(J), I 1 J = I ∩ J
sort(I) ∩ sort(J) = ∅, I 1 J = I × J (p. cartésien).
Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 19 / 39
Algèbre - dernière opération

Renomage:
utilise une fonction injective de U = A1 ...An dans att que l’on notera
A1 /B1 , . . . , An /Bn .

δA1 /B1 ,...,An /Bn (I) = {v sur B1 , . . . , Bn | pour u ∈ I,

v (Bi )) = u(Ai ) pour tout i ∈ [1..n]}

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 20 / 39

Composition
Requêtes de base
(i) chaque input relation R, [R] est une requête
(ii) pour chaque a ∈ dom et A ∈ att, {hA : ai}
+ les 4 opérations
Exemple
I1 := σDirecteur =“Bergman” (Film).
I2 := πTitre (I1 ).
I3 := I2 1 Pariscope
I4 := πSalle Titre (I3 ).
πSalle Titre (πTitre (σDirecteur =“Bergman” (Film)) 1 Pariscope), ou
πSalle Titre (σDirecteur =“Bergman” (Film 1 Pariscope))
Arbres de requêtes, réecritures, optimisation

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 21 / 39

Théorème d’équivalence

q est exprimable comme une rêgle conjonctive

ssi q est exprimable dans le calcul conjonctif
ssi q est exprimable dans l’algèbre PSJR

Rêgle ⇒ Calcul : évident

Calcul ⇒ Algèbre
∃ par projection, ∧ par jointure
Algèbre ⇒ Rêgle
On se ramème à la forme

(†) π(σγ1 (δ|f1 (R1 ) 1 · · · 1 σγn (δ|fn (Rn ))

En utilisant, des équivalences algébriques

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 22 / 39

Equivalences algébriques

σF (σF 0 (q)) ↔ σF0 (σF (q))

πX (πY (q)) ↔ πX ∩Y (q)
σF (πX (q)) ↔ πX (σF (q)) si F porte sur des attributs de X
q1 1 q2 ↔ q2 1 q1
σF (q1 1 q2 ) → σF (q1 ) 1 q2
si F porte sur des attributs
de sort(q1 )
πX (q1 1 q2 ) → πX (q1 ) 1 πX (q2 ) si sort(q1 ) ∩ sort(q2 ) ⊆ X

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 23 / 39

Résultats
Les requêtes exprimables comme des rêgles conjonctives sans
constantes sont satisfaisables: pour tout q, il existe i tel que q(I) 6= ∅.
Avec constantes: σA=0 (R) 1 σA=1 (R) Non!
Les requêtes conjonctives sont monotones: pour tout I,J, pour tout q,

I ⊆ J ⇒ q(I) ⊆ q(J)

Fermeture sous composition

S1 (x, z) ← Q(x, y ), R(y , z, w)
S2 (x, y , z) ← S1 (x, w), R(w, y , v ), S1 (v , z)
S3 (x, z) ← S2 (x, u, v ), Q(v , z)
Peut être obtenu directement
S2 (x, y , z) ← Q(x, y1 ), R(y1 , w, w1 ), R(w, y , v ), Q(v , y2 ), R(y2 , z, w2 )
S3 (x, z) ← Q(x, y1 ), R(y1 , w, w1 ), R(w, u, v1 ), Q(v , y2 ), R(y2 , v , w2 ), Q(v
Vues
Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 24 / 39
Exercices

Soit le schéma suivant :

Salle (Nom Horaire Titre)

Film (Titre Réalisateur Acteur)
Produit (Producteur Titre)
Vu (Spectateur Titre)
Aime (Spectateur Titre)

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 25 / 39

Exercices (2)

Écrire en algèbre, en calcul n-uplet et domaine.

1 Où et quant peut on voir le film “Mad Max...”?
2 Quels sont les films réalisés par Welles ?
3 Quels sont les acteurs de “Ran” ?
4 Où peut-on voir un film où joue Signoret ?
5 Quels sont les acteurs qui ont produit un film ?
6 Quels acteurs produisent un film dans lequel ils jouent ?
7 Quels sont les acteurs qui jouent dans les films de Truffaut ?
8 Quels acteurs jouent dans tous les films de Welles ?
9 Qui produit tous les films de Kurosawa ?
10 Quels spectateurs voient tous les films ?

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 26 / 39

Exercices (3)

1 Quels sont les spectateurs qui aiment tous les films qu’ils voient ?
2 Où peut on voir M. Brando après 16h ?
3 Quels films ne passent dans aucune salle ?
4 Qui produit un film qui ne passe dans aucune salle ?
5 Quels producteurs voient tous les films qu’ils produisent ?
6 Quels producteurs voient tous les films de Kurosawa ?
7 Quels spectateurs aiment un film qu’ils n’ont pas vu ?
8 Qui n’aime aucun film ?
9 Qui ne produit aucun film de Doillon ?
10 Quels sont les producteurs qui ne voient que les films qu’ils
produisent ?

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 27 / 39

On rajoute union/disjonction
Où puis-je voir “Annie Hall” ou “Manhattan”?
Algèbre avec union (algèbre PSJRU)

πSalle (σTitre=“Annie Hall” Pariscope ∪ σTitre=“Manhattan” Pariscope)

Plusieurs rêgles
ans(xt ) ← Pariscope(xt , “Annie Hall”, xs )
ans(xt ) ← Pariscope(xt , “Manhattan”, xs )
Calcul avec disjunction ∨
{xt | ∃xs (Pariscope(xt , “Annie Hall”, xs )∨Pariscope(xt , “Manhattan”, xs
Autres possibilités:
Sélection plus complexes
πSalle (σTitre=“Annie Hall”∨Titre=“Manhattan” Pariscope)
Constantes plus complexes
πSalle (Pariscope 1 {hTitre : “Annie Hall”i, hTitre : “Manhattan”i})
Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 28 / 39
On rajoute l’union (2)

Théorème d’équivalence reste vrai

Problème avec le calcul : {x, y | R(x) ∨ R(y )}

Infini si on n’est pas prudent → formules sures

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 29 / 39

On rajoute la différence/négation
Dans quel film d’Hitchcock, n’a-t-il pas joué?
Quels films passent au Gaumont Opéra mais pas au Réal?
Algèbre relationnelle : PSJRU + différence
Calcul relationnel : ∃, ∧, ∨ ¬, ∀
Rêgles : négation dans le corps des rêgles
πTitre σDirecteur =“Hitchcock” (Film) − πTitre σActeur =“Hitchcock” (Film)
nr-datalog¬ par l’exemple

ans(x) ← Film(x, “Hitchcock”, z),

¬Film(x, “Hitchcock”, “Hitchcock”)

Hitch-Acteur (z) ← Film(x, “Hitchcock”, z)

not-ans(x) ← Film(x, y , z), ¬Hitch-Acteur (z)
ans(x) ← Film(x, y , z), ¬not-ans(x)
Note: vérifier l’exemple

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 30 / 39

Calcul relationnel

On rajoute au calcul conjonctif ¬, ∨, ∀

ϕ ∨ ψ ≡ ¬(¬ϕ ∧ ¬ψ), et ∀xϕ ≡ ¬∃x¬ϕ
Terme : constante ou variable
Atome : R(e1 , . . . , en ) (R nom de relation, n = arit é(R), chaque ei est
un terme)
Formules de base : atomes sur R + e = e0
Formules bien-formées
(a) ¬ϕ
(b) (ϕ ∧ ψ), (ϕ ∨ ψ)
(c) ∃x ϕ, ∀x ϕ
ϕ → ψ ≡ ¬ϕ ∨ ψ
ϕ ↔ ψ ≡ (ϕ ∧ ψ) ∨ (¬ϕ ∧ ¬ψ)

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 31 / 39

Calcul relationnel

Variables libres et liées

litéral P : free(P) = variables de P

free(ϕ ∧ ψ) = free(ϕ) ∪ free(ψ) free(ϕ ∨ ψ) = free(ϕ) ∪ free(ψ)

free(¬ϕ) = free(ϕ)
free(∃xϕ) = free(ϕ) − {x} free(∀xϕ) = free(ϕ) − {x}

Requêtes : {e1 , ..., en | ϕ}

variables de e1 , ...en sont les variables libres de ϕ
{xt | ∃xa Film(xt , “Hitchcock”, xa ) ∧ ¬Film(xt , “Hitchcock”, “Hitchcock”)}
{xt | ∃xd , xa Film(xt , xd , xa ) ∧
∀ya (∃yd Film(xt , yd , ya )
→ ∃zt Film(zt , “Hitchock”, ya ))}

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 32 / 39

Sémantique du calcul

Problême : résultat fini

(non-sure-1) {x | ¬Film(“Cries and Whispers”, “Bergman”, x)}
(non-sure-2) {x, y | Film(“Cries and Whispers”, “Bergman”, x)
∨ Film(y , “Bergman”, “Ullman”)}

Solution A : variables prennent leurs valeurs dans le domaine actif

Solution B : interdire les requêtes non-sures ←
non-sure-3 {x | ∀y R(x, y )}
Résultats intermédiaires non finis

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 33 / 39

Sémantique domaine actif
valuations ν de free(ϕ) dans adom(q, I)
I satisfait ϕ pour ν
I |=adom ϕ[ν]
(a) ϕ = R(u) et ν(u) ∈ I(R);
(b) ϕ = (s = s0 ) et ν(s) = ν(s0 );
(c) ϕ = (ψ ∧ ξ) et (I |=adom ψ[ν] et I |=adom ξ[ν]);
(d) ϕ = (ψ ∨ ξ) et (I |=adom ψ[ν] ou I |=adom ξ[ν]);
(e) ϕ = ¬ψ et I 6|=adom ψ[ν],
(f) ϕ = ∃x ψ et pour quelque c ∈ adom, I |=adom ψ[ν ∪ {x/c}]; ou
(g) ϕ = ∀x ψ et pour chaque c ∈ adom, I |=adom ψ[ν ∪ {x/c}].
Sémantique d’une requête
qadom (I) = {ν(he1 , . . . , en i) | I |=adom ϕ[ν],
ν est une valuation sur free(ϕ)
dont l’image ⊆ adom}.

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 34 / 39

Exercice : la division

Opération redondante
I sur X, J sur Y ⊂ X,
sort(I ÷ J) = sort(I) − sort(J)

I ÷ J = {u | ∀v ∈ J, [u, v ] ∈ I}
Exemple: Quels acteurs jouent dans tous les films de Hitchcock?

πTitle,Actor σDirector =Hitchcock (Movies)

÷
πTitle σDirector =Hitchcock (Movies)

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 35 / 39

Exercice : Complément de jointure

I sur X, J sur Y, X ∩ Y = Z

sort(I./J) = X ,

I./J = {x ∈ I | πZ (x) 6∈ πZ (J)}

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 36 / 39

Résultats

Théorème d’équivalence
algèbre ↔ calcul ↔ nr-datalog¬

Non-monotonie (différence)
Fermeture sous composition (à cause de l’algèbre)
Minimalité des opérateurs de l’algébre Projection Sélection Jointure
Renomage Différence Union
Faible complexité (logspace, ptime, NC)
Tests d’équivalence et d’inclusion sont indécidables - donc
optimisation difficile
Décidable pour les requêtes conjonctives - optimisation principalement
pour RQ

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 37 / 39

De la théorie à la pratique
Algèbre et calcul relationnels sont équivalents
La traduction de l’un à l’autre est facile

Requete en calcul langage

assertionnel
↓
Compilation

↓
Requete algebrique langage
procedural
↓
Optimisation

↓
Langage
machine → Evaluation
Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 38 / 39
Merci

Serge Abiteboul (INRIA) Modèle relationnel April 3, 2009 39 / 39