Bases de données

avancées
cours 5 : optimisation de programme datalog,
«magic sets rewritting».
 Datalog et requêtes

Pour effectuer une requête avec datalog on

instancie un prédicat avec des constantes et
on cherche les valeurs possibles des places
occupées par des variables:
anc(X,Y) :- par(X,Y)
anc(X,Y) :- par(X,Z) & anc(Z,Y)
?- anc(John,X)
Algorithme semi-naïf
anc(X,Y) :- par(X,Y)
anc(X,Y) :- par(X,Z) & anc(Z,Y)
?- anc(John,X)

Si on applique l’algorithme semi-naïf, on peut

calculer la relation anc(X,Y) et trouver les
éléments X tel que anc(John,X) soit vérifié.

Seulement on calcule beaucoup d’information

inutile.
Magic set rewriting :
réécriture magique
L’idée de cet algorithme est de transformer
la base de donnée intentionnelle pour tenir
compte des ‘sélections’ effectuées dans la
requête : il s’agit de calculer seulement les
relation nécessaires.

Nous nous restreignons aux programmes

datalog sans négation (il existe cependant
des généralisation de la réécriture magique
pour prendre la négation en compte).
Liage des arguments
d’un prédicat
lorsque l’on cherche à répondre à la
requête ?- anc(John,X), le premier argument
de anc est connu, il est dit ‘lié’, le second est
à trouver, il est dit ‘libre’.

on note ‘bf’ le profil de liage du prédicat anc,

‘b’ pour ‘lié’ (bound en anglais) et ‘f’ pour
‘libre’ (free en anglais).
Propagation du profil de
liage

La requête datalog induit un profil de liage

pour le prédicat sur lequel elle porte.

Ce profil de liage peut se propager aux

autres prédicats, si l’on considère que les
clauses sont évaluées de gauche à droite.
Propagation des profils
de liage : exemple
anc(X,Y) :- par(X,Y)
anc(X,Y) :- par(X,Z) & anc(Z,Y)
?- anc(John,X)

anc(X,Y) :- par(X,Y)
anc(X,Y) :- par(X,Z) & anc(Z,Y)
?- anc_bf(John,X)
Propagation des profils
de liage : exemple
anc(X,Y) :- par(X,Y)
anc(X,Y) :- par(X,Z) & anc(Z,Y)
?- anc(John,X)

anc_bf(X,Y) :- par(X,Y)
anc_bf(X,Y) :- par(X,Z) & anc(Z,Y)
?- anc_bf(John,X)
Propagation des profils
de liage : exemple
anc(X,Y) :- par(X,Y)
anc(X,Y) :- par(X,Z) & anc(Z,Y)
?- anc(John,X)

anc_bf(X,Y) :- par_bf(X,Y)
anc_bf(X,Y) :- par(X,Z) & anc(Z,Y)
?- anc_bf(John,X)
Propagation des profils
de liage : exemple
anc(X,Y) :- par(X,Y)
anc(X,Y) :- par(X,Z) & anc(Z,Y)
?- anc(John,X)

anc_bf(X,Y) :- par_bf(X,Y)
anc_bf(X,Y) :- par_bf(X,Z) & anc(Z,Y)
?- anc_bf(John,X)
Propagation des profils
de liage : exemple
anc(X,Y) :- par(X,Y)
anc(X,Y) :- par(X,Z) & anc(Z,Y)
?- anc(John,X)

anc_bf(X,Y) :- par_bf(X,Y)
anc_bf(X,Y) :- par_bf(X,Z) & anc_bf(Z,Y)
?- anc_bf(John,X)
L’ordre des prédicats
dans les clauses
Comme on suppose une évaluation de
gauche à droite, l’ordre des prédicats qui
apparaissent dans une clause a une
incidence.

En particulier, les prédicats internes, =, <>,

<, ou >, ne peuvent être évalués qu’avec
des profils de liage particulier (bf ou fb
pour = et bb pour les autres).
 Ordre des clauses et
liage
sg(X,Y) :- person(X) & X=Y
sg(X,Y) :- par(X,Xp) & par(Y,Yp) & sg(Yp,Xp)
?- sq(j,X)

sg_bf(X,Y) :- person_b(X) & X=Y

sg_bf(X,Y) :- par_bf(X,Xp) & par_ff(Y,Yp) & sg_bb(Yp,Xp)
?- sq_bf(j,X)

Le fait que le profil de liage de la seconde

occurrence de par est ff, cela indique qu’il
faut explorer toute la sg(j,X).
 Ordre des clauses et
liage
sg(X,Y) :- person(X) & X=Y
sg(X,Y) :- par(X,Xp) & sg(Yp,Xp) & par(Y,Yp)
?- sq(j,X)
sg_bf(X,Y) :- person_b(X) & X=Y
sg_bf(X,Y) :- par_bf(X,Xp) & sg_fb(Yp,Xp) & par_fb(Y,Yp)
?- sq_bf(j,X)

En changeant l’ordre, on obtient des

sous-requêtes avec des profils de liages
plus simples.
Réécriture magique et
profil de liage

Pour effectuer la réécriture magique, il faut

que chaque prédicat intentionnel ait un
unique profil de liage.

Pour cela, on propage le liage en réordonnant

les clauses judicieusement et en définissant
de nouvelles règles pour chaque liage.
 Exemple
sg(X,Y) :- person(X) & X=Y
sg(X,Y) :- par(X,Xp) & sg(Yp,Xp) & par(Y,Yp)
?- sq(j,X)

sg_fb(X,Y) :- par_bf(Y,Yp) & sg_bf(Yp,Xp) & par_fb(X,Xp)

sg_bf(X,Y) :- person_b(X) & X=Y
sg_bf(X,Y) :- par_bf(X,Xp) & sg_fb(Yp,Xp) & par_fb(Y,Yp)
?- sq_bf(j,X)
A propos de l’unicité de
liage.
On peut en fait utiliser une condition moins
forte pour la réécriture magique, il suffit
qu’à chaque fois qu’un prédicat doive être
résolu, le profil de liage de la requête soit
plus ‘fort’ qu’un profil donné.

un profil de liage a et plus fort qu’un profil

de liage b (b ≤ a) si à chaque position liée
par b, est également liée par a :
ffb ≤ bfb
Réordonner les prédicats

Trouver un ordre convenable pour les

prédicats d’une clause peut s’avérer
couteux. En utilisant les profils de liage les
plus faibles, on peut trouver un bon
compromis. En particulier, on peut trouver, un
ordre assurant un liage correct pour les
prédicats internes, si il en existe un.
Faisabilité d’un profil de
liage
Un profil de liage est dit ‘faisable’ pour un
prédicat, si pour toute clause définissant ce
prédicat, il existe un ordre de la clause
induisant un liage des prédicats tel que les
profils de liage induits soient ‘faisables’.

Le liage ff n’est pas faisable pour le prédicat

p(X,Y) définit par la clause p(X,Y):-X=Y
Ordre dans les clauses
et faisabilité.

Si les prédicats d’une clause sont G1,...,Gn

alors et que dans cet ordre les prédicats
Gi1,...,Gik sont faisables alors si il existe un
ordre où tous les prédicats sont faisables, il
en existe un commençant par Gi1,...,Gik où
tous les prédicats sont faisables.
 Algorithme pour la
faisabilité des liages
ENTREE :
un prédicat avec son profil de liage (requête)
un programme datalog
une liste des profils minimaux de liage
faisables pour les prédicats extensionnels.
SORTIE :
l’ensemble des profils faisables nécessaires
pour répondre à la requête, si il y en a un.
 Algorithme pour la
faisabilité des
(p,a) pair prédicat profil de liage
liages
F = ensemble des (p,a) non faisables
I = ensemble de (p,a) intéressants
pour chaque (p,a) de I:
pour chaque règle r de conclusion p:
trouver un ordre faisable pour r avec le profil a en
considérant les profils de F comme impossibles
si on trouve un tel ordre
alors ajouter à I les profils de liage induits
sinon enlever (p,a) de I et l’ajouter à F
/*on considère que si (p,a) est dans F alors (p,b)
avec b ≤ a est également dans F
Profil de liage unique
Une fois les profils de liage intéressants
étant calculés, et si celui de la requête est
dans I, alors on peut calculer les règles
associés à chacun des prédicats spécialisés
aux profils de liage intéressants. Dans ce
cas, le nouveau programme datalog obtenu a
le même plus petit point fixe que le
précédent pour la requête.

Si le prédicat de la requête n’est pas

intéressant alors le programme n’a pas de
plus petit point fixe. Si le programme est
sûr, alors on n’est jamais dans ce cas.
 Transformation magique
ENTREE :
un programme datalog ayant un unique profil de liage
une requête q(s1,...,sn)
SORTIE :
un nouvel ensemble de règles tel que la relation q
réponde à la requête
METHODE :
créer un prédicat magique m_p pour chaque prédicat p
créer les prédicats supplémentaires sup_j.i pour
chaque règle r_j de longueur n avec i dans [1,n-1]
Les prédicats magiques

si p est un prédicats de profil de liage a

(unique par hypothèse), on définit m_p le
prédicat magique de p qui porte sur les
variables liées de p.
 Les prédicats
supplémentaires
Les prédicats supplémentaires servent à
évaluer les clauses de gauche à droite. Ils
servent à transférer les instanciations de
variables vers la droite.

Etant donnée une règle r_j de longueur n, les

variables de sup_j.i sont les variables liées
de la tête et les variables qui apparaissent
dans le i premier sous-buts et dans l’un des
suivants.
 Les règles pour les
prédicats magiques

si p est un prédicat intentionnel et r_j une

régle dont p(X1,...,Xn) est le ième sous-but
alors si les variables liées de p sont Xi1,...,Xik
et si Y1,...,Yl sont les variables du prédicat
sup_j.(i-1) alors on ajoute la règle :

m_p(Xi1,...,Xik) :- sup_j.(i-1)(Y1,...,Yl)
 Règle pour le prédicat
sup_j.1

si r_j = p(X1,...,Xn):-q(Z1,...,Zm) &... et si si les

variables liées de p sont Xi1,...,Xik et si
Y1,...,Yl sont les variables du prédicat sup_j.1
alors on ajoute la règle :

sup_j.1(Z1,...,Zm):-m_p(Xi1,...,Xik) & q(Z1,...,Zm)

 Règle pour sup_j.(i+1)

Si Y1,...,Yl sont le variable de sup_j.i, Z1,...,Zm

celle de sup_j.(i+1) et q(U1,...,Uk) est le (i
+1)ème prédicat de la clause de r_j alors on
ajoute la règle :

sup_j.(i+1)(Z1,...,Zm):-sup_j.i(Y1,...,Yl) & q(U1,...,Uk)

 Règle pour les prédicats
intentionnels

Si r_j = p(X1,...,Xn):- ... & q(Z1,...,Zm) et est

de longueur n alors on ajoute la règle :

p(X1,...,Xn):-sup_j.(n-1)(Y1,...,Yl) & q(Z1,...,Zm)

 Initialisation

Si la requête est q(s1,...,sn) et que les

arguments liés sont si1,...,sim alors on ajoute
la règle :

m_q(si1,...,sim)
 Exemple
r1 : sg(X,Y) :- person(X) & X=Y
r2 : sg(X,Y) :- par(X,Xp) & sg(Xp,Yp) & par(Y,Yp)
?-sg(j,X)

m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)
 Execution du programme
transformé
m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)

a
b d
j c e
 Execution du programme
transformé
m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)

a
b d
j c e
 Execution du programme
transformé
m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)

a
b d
j c e
 Execution du programme
transformé
m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)

a
b d
j c e
 Execution du programme
transformé
m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)

a
b d
j c e
 Execution du programme
transformé
m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)

a
b d
j c e
 Execution du programme
transformé
m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)

a
b d
j c e
 Execution du programme
transformé
m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)

a
b d
j c e
 Execution du programme
transformé
m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)

a
b d
j c e
 Execution du programme
transformé
m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)

a
b d
j c e
 Execution du programme
transformé
m_sg(Xp) :- sup_2.1(X,Xp)
sup_2.1(X,Xp) :- m_sg(X) & par(X,Xp)
sup_2.2(X,Xp,Yp) :- sup_2.1(X,Xp) & sg(Xp,Yp)
sg(X,Y) :- sup_2.2(X,Xp,Yp) & par(Y,Yp)
sg(X,Y) :- m_sg(X) & person(X) & X=Y
m_sg(j)

a
b d
j c e