Conception Développement Logiciel

Cours B3 n° 16472

1999/2000

DATALOG - SQL

Bases de données relationnelles

et

déductives  (?)


Le modèle relationnel

Les données sont structurées en relations.

Soient D1 ,..., Dn des ensembles appelés Domaines  (non nécessairement distincts, mais finis),

soit D le produit cartésien D1 x ... x Dn ,

une relation R sur D est un sous-ensemble de D1 x ... x Dn

n est l'arité de la relation.

Tuples et attributs

Soient d1 D1 , ... , dn Dn  
un tuple < d1 , ... , dn> R

  1. Cardinalité d'une relation : nombre de tuples de R (pas d'ordre)
  2. Table : une relation peut être représentée par une table
  3. Attribut : les noms des colonnes (ou n° de colonne) de la table sont les attributs de la relation
  4. Schéma d'une relation : la liste ordonnée des attributsSchéma d'une relation : la liste ordonnée des attributs.

Base de données

Soient les relations enseigne et suit :

enseigne ( Enseignant Cours )
< Milton , Cs507 >
< Milton , Cs531 >
< Kim , Cs502 >
< Barth , Cs501 >
< Gupta , Cs523 >
suit ( Etudiant Cours Niveau )
< Adams , Cs507 , A >
< Adams , Cs502 , B >
< Arnold , Cs507 , A >
< Arnold , Cs531 , C >
< Arnold , Cs501 , A >
< Alt , Cs501 , A >

en DATALOG on écrira :

enseigne(milton, cs507).
enseigne(milton, cs531).
enseigne(kim,    cs502).
enseigne(barth,  cs501).
enseigne(gupta,  cs523).

suit(adams,  cs507, a).
suit(adams,  cs502, b).
suit(arnold, cs507, a).
suit(arnold, cs531, c).
suit(arnold, cs501, a).
suit(alt,    cs507, a).

% données extensionnelles
% remarquer les minuscules car les données sont des constantes 

Requêtes SQL et buts DATALOG

Sélection : réduction du nombre des lignes
SQL SELECT * FROM enseigne
    WHERE Enseignant = milton
Résultats :
Milton Cs507
Milton Cs531

DATALOG ?- enseigne(milton,Cours).
Résultats : Cours = cs507 ;

Cours = cs531 ;

no

Projection : réduction du nombre des colonnes

SQL SELECT Cours, Niveau  
        FROM suit
Résultats :
Cours Niveau
Cs507 A
Cs502 B
Cs507 B
Cs531 C
Cs501 A
DATALOG ?- suit(_ , Cours , Niveau).
Résultats Cours = cs507, Niveau = a  ;
Cours = cs502, Niveau = b ;
Cours = cs507, Niveau = a ;
Cours = cs531, Niveau = c ;
Cours = cs501, Niveau = a ;
Cours = cs507, Niveau = ;

No

% remarquer l'utilisation d'une variable anonyme...
% d'autre part dans les réponses Prolog on ne sait pas simplement éviter les doublons...

Union, intersection et différence

(entre relations ayant les mêmes attributs)

2 nouvelles relations :

demande ( Etudiant Cours )
< Adams , Cs509 >
< Adams , Cs511 >
< Arnold , Cs509 >
< Arnold , Cs511 >
< Alt , Cs513 >
autorisation ( Etudiant Cours )
< Adams , Cs509 >
< Arnold , Cs511 >
< Alt , Cs509 >
< Alt , Cs511 >

UNION (entre relations ayant les mêmes attributs)

SQL SELECT * FROM demande
    UNION
SELECT * FROM autorisation
Résultats
Etudiant Cours
Adams Cs509
Adams Cs511
Arnold Cs509
Arnold Cs511
Alt Cs513
Alt Cs509
Alt Cs511
DATALOG union(Etudiant, Cours):-
   demande(Etudiant,Cours).
union(Etudiant, Cours):-
  autorisation(Etudiant,Cours).

?- union(Etudiant , Cours).
Résultats
Etudiant = Adams , Cours = Cs509 ;
Etudiant = Adams , Cours = Cs511 ;
Etudiant = Arnold , Cours = Cs509 ;
Etudiant = Arnold , Cours = Cs511 ;
Etudiant = Alt , Cours = Cs513 ;
Etudiant = Adams , Cours = Cs509 ;
Etudiant = Arnold , Cours = Cs511 ;
Etudiant = Alt , Cours = Cs509 ;
Etudiant = Alt , Cours = Cs511 ;
No

Intersection  (entre relations ayant les mêmes attributs)

SQL SELECT * FROM demande
   WHERE EXISTS
      ( SELECT * FROM autorisation
         WHERE
            demande.étudiant = autorisation.étudiant
             AND
            demande.cours = autorisation.cours
      )
Résultats
Etudiant Cours
Adams Cs509
Arnold Cs511
DATALOG intersection(Etudiant,Cours):-
    demande(Etudiant,Cours),
    autorisation(Etudiant,Cours).

?- intersection(Etudiant,Cours).
Résultats
Etudiant = Adams , Cours = Cs509 ;
Etudiant = Arnold , Cours = Cs511 ;
Etudiant = Adams , Cours = Cs509 ;
Etudiant = Arnold , Cours = Cs511 ;
No

Jointure (entre relations ayant des attributs communs)

SQL : SELECT  enseigne.Enseignant, suit.Etudiant,
         suit.Cours, suit.Niveau

     FROM enseigne, suit

     WHERE enseigne.Cours = suit.Cours ;
Résultats
Enseignant Etudiant Cours Niveau
Milton Adams Cs507 A
Milton Arnold Cs507 A
Milton Arnold Cs531 C
Kim Adams Cs502 B
Barth Arnold Cs501 A
Barth Alt Cs501 A
DATALOG jointure(Enseignant,Etudiant,Cours,Niveau):-
    enseigne(Enseignant,Cours),
    suit(Etudiant,Cours,Niveau).

?- jointure(En,Et,C,N)
Résultats
En = milton , Et = adams , C = cs507 , N = a ;
En = milton , Et = arnold , C = cs507 , N = a ;
En = milton , Et = arnold , C = cs531 , N = c ;
En = kim , Et = adams , C = cs502 , N = b ;
En = barth , Et = arnold , C = cs501 , N = a ;
En = barth , Et = alt , C = cs501 , N = a , ;
No




Algèbre relationnelle


Définitions :

Algèbre (structure algèbrique) :  ensemble(s) muni(s) de fonctions et relations

Opérateur (sur les ensembles) : fonction d'une relation dans une autre.
ex : la composition de relation  R1°R2

Algèbre relationnelle : ensemble des relations muni des opérateurs de sélection ,  projection , produit cartésien , 
union , différence ,  jointure (opérateur dérivé)




Notations (algèbre relationnelle)


Soit F une formule entre attributs de relations (+ constantes)

Sélection : F R : enseignant=milton enseigne

Projection : R d'arité n , i1,..., ik des noms d'attributs ou des numéros de colonnes o<k <= n,

i1,..., ikR la relation d'arité k et d'attributs i1,..., ik obtenus à partir de R par suppression des autres colonnes

(la cardinalité peut donc en être différente).

ex : cours,niveau suit

Produit cartésien : R x S    ( d'arité a(R) + a(S) )

Le schéma de R x S est obtenu par concaténation de ceux de R et S

Union de deux relations de même schéma

différence : R-S                 ex: demande - autorisation

L'ensemble des 5 opérateurs est complet

(même pouvoir d'expression que le calcul de prédicats)




opérateurs dérivés


Jointure : F une formule réduite à la comparaison d'attributs des 2 relations opérandes

R |><| F S = F (R x S)

Jointure naturelle : R |><| S

Toute paire d'attributs de même nom est supposée sous contrainte d'égalité

Semi-jointure : R |>< F S = Schéma(R) (R |><| S)





SQL / DATALOG / Algèbre relationnelle

3 relations R1,R2,R3 :

R1(A1,A2,A3) , R2(A4,A5,A6) , R3(A7,A8,A9)

SQL

SELECT R1.A1, R3.A9
   FROM R1,R2,R3
     WHERE R1.A2 = a
          AND R2.A5 = b
          AND R3.A8 = c
          AND R1.A3 = R2.A4
          AND R2.A6 = R3.A7 ;


DATALOG

but(A1,A9) :-
     r1(A1,a,A3),
     r2(A4,A5,A6), A5=b , A4=A3
     r3(A7,A8,A9), A8=c , A7=A6.
%ou bien ("plus Prolog...")
but1(A1,A9):-
     r1(A1 , a , X),
     r2(X  , b , Y),
     r3(Y  , c , A9).




Algèbre relationnelle

A1,A9 ((A2=aR1) |><|A3=A4 (A5=b R2))
                                |><|A6=A7 (A8=cR3)





SQL / DATALOG

La comparaison, le parallèle ne s'arrête pas là, on verra qu'on dispose en Prolog d'outils pour représenter les contrainte d'intégrité, pour la mise à jour, pour construire des vues SQL, etc...

Tableau de correspondance :

Base de données DATALOG-Prolog
Relation

 <-->

 Prédicat
Attribut  <--> Argument
Tuple  <--> Fait clos
Vue  <--> Règle
Requête  <--> But
Contrainte  <--> But





Evaluation naïve d'une réquête récursive

Idée :  implantation de la fonction Tp et itération de celle-ci dans l'algèbre relationnelle

Deux phases :  
1. Calcul des relations en cause.
2. Extraction des faits/Tuples relatifs à la question .

Exemple en DATALOG on peut poser la question

?- ancêtre(paul,Y).

Elle correspond à la relation Ancêtre :

Ancêtre = Parent U 1,4 (2=3 (Parent X Ancêtre)
1ère clause 2ème clause

Chercher le plus petit point fixe de cette équation récursive ou encore, la plus petite relation Ancêtre qui satisfasse cette équation.


Etape O : ancêtre0 = ø

Etape 1 : ancêtre1 = parent U 1,4(2=3(parent x ancêtre0))
                   = parent

Etape 2 : ancêtre2 = parent U 1,4(2=3(parent x ancêtre1))
                   = parent U 1,4(2=3(parent x parent))

Etape 3 : ancêtre3 = parent U 1,4(2=3(parent x ancêtre2))
                    = parent U
                      1,4(2=3(parent x parent)) U
                      1,6(2=3,4=5(parent x parent x parent ))
                    = ancêtre2 U
                                 1,6(2=3,4=5(parent x parent x parent ))

Etape 4 ...

Retour aux exercices