Chapitre 18

SGBD déductifs

1. Introduction
Les SGBD déductifs, appelés aussi systèmes de gestion de bases de connaissances (en anglais
Knowledge Base Management Systems, KBMS), sont nés de la rencontre de deux domaines:
l'intelligence artificielle (plus précisément la programmation logique et les méthodes de preuve
automatique de théorèmes) et les bases de données. Les SGBD déductifs ont pour objectif de
décrire explicitement et de gérer non pas uniquement les connaissances factuelles (les données),
mais aussi les connaissances génériques qui sont de deux types:
- les règles de déduction qui permettent de déduire des informations nouvelles à partir des
informations stockées dans la base de données,
- les contraintes d'intégrité qui définissent des normes et permettent ainsi de contrôler la validité
des mises à jour.

Exemple de règles de déduction:

- Tous les livres de la collection "Computer" de l'éditeur "Springer Verlag" sont en anglais.
- S'il existe un train Paris/Lausanne et un train Lausanne/Milan, alors il existe une liaison
ferroviaire Paris/Milan
- Règles administratives définissant la citoyenneté
- Règles bancaires pour décider de l'octroi de prêts
- Règles boursières décidant quand il faut vendre ou acheter des actions
- Calcul du rang des joueurs de tennis
- Calcul des horaires de train à partir des heures de départ et de la durée des trajets
...
Exemple de contraintes d'intégrité:
- Valeur nulle interdite pour tel attribut
- Les heures de décollage et d'atterrissage sur l'aéroport de CDG sont comprises entre 5h et 23h
- L'age d'un adulte est supérieur ou égal a 18 ans
...

Les SGBD classiques ne prennent pas en compte ces règles de déduction, ni les contraintes
d'intégrité (sauf certaines très simples) alors qu'il existe une demande réelle de la part des
utilisateurs de SGBD. Les applications des SGBD déductifs sont variées: la gestion classique ou
prévisionnelle, l'aide à la décision, la médecine, la robotique, la productique, ..., et plus
généralementtoute application des systèmes experts qui requiert un grand volume de données.

L'intérêt de faire gérer les règles de déduction et contraintes d'intégrité par le système est que les
programmes d'application n'ont plus à le faire: ils pourront être indépendants de ces règles,
notamment des règles de gestion propres à chaque entreprise (cas des progiciels). Ils seront plus
vite écrits et de maintenance plus simple. La modélisation de la base qui comprend les données et
les règles est plus complète, plus naturelle, plus générale et plus aisée (il y a moins de données à
entrer dans la base). La base sera moins volumineuse. Le gain de place peut être d'un facteur 10,
100, ... Par exemple, la description des différentes configurations possibles pour un avion militaire

© Christine Parent 1
particulier tenait en mémoire centrale quand elle était faite avec des règles, et ne tenait pas sur un
SGBD classique quand elle était faite uniquement avec des données.

Il y a plusieurs façons d'employer les techniques d'intelligence artificielle dans un SGBD, ou
vice versa:

- Créer un nouveau type de SGBD qui offre les fonctions d'un SGBD classique et dont tout
l'interface utilisateur, langage de manipulation des données et langage de programmation, est le
même: un langage déclaratif de type langage logique qui permet d'effectuer des déductions et
d'exprimer des contraintes d'intégrité.
Avantages de ce type de SGBD:
- ceux des SGBD
- déduction
- un seul langage d'interface: plus de problème d'incompatibilité entre deux langages
- langage déclaratif: optimisation possible (comme SQL, QUEL, ...).

- Une autre solution, plus facile à réaliser mais moins efficace, est de faire coopérer un système
expert et un SGBD relationnel. Le SGBD gère la base de faits et de règles. Le système expert
offre le langage logique d'interface, et ses mécanismes d'inférence.
On parle alors de "couplage" fort ou faible selon le degré de vision qu'a l'utilisateur des deux
systèmes, ou d'un seul.
Il existe des prototypes de ce type dans les laboratoires de recherche. IBM commercialise
PROSQL.

- On peut aussi utiliser les mécanismes de l'intelligence artificielle dans certains modules du
SGBD pour réaliser un SGBD d'interface classique mais plus performant.
Exemples:
- conception du schéma conceptuel à l'aide d'un système expert (SECSI d'INFOSIS)
- conception du schéma logique/interne à l'aide d'un système expert
- traitement des requêtes avec valeurs nulles ou floues
- réponses "intelligentes" dans le cas de réponse vide
- ...

Nous nous intéressons ici au premier cas, et plus particulièrement aux principes des langages
logiques spécifiques aux bases de données.

Exemples d'emploi de règles logiques en bases de données

La notation employée est de type Prolog. Mais c'est un Prolog purement déclaratif: sans aucun
ordre entre les règles, ni entre les sous-buts des règles.

Exemple: définition d'une vue

Relation EMPLOYE (Nom, Adresse, Salaire, Service)
On veut créer une vue sans le salaire, pour des raisons de confidentialité
SQL: Create View EMP As Select Nom, Adresse, Service From EMPLOYE
Langage logique: emp (N, A, Serv) :- employé (N, A, Sal, Serv)
ce qui signifie: <N, A, Serv> est un "emp" s'il existe un Sal tel que <N, A, Sal, Serv> est un
employé.

Exemple: écriture d'une requête

EMPLOYE (Nom, Adresse, Salaire, Service)
SERVICE (NomS, NomChef)

© Christine Parent 2
On veut le chef d'André.
SQL: Select NomChef From SERVICE, EMPLOYE Where NomS=Service And Nom="André"
Langage logique:
1) chef (C, E) :- employé (E, A, Sal, Serv) & service (Serv, C)
ce qui signifie: C est le chef de E s'il existe un Sal et un Serv tels que :
<E, A, Sal, Serv> est un employé et C est le chef de Serv.
2) chef (C, "André")
ce qui définit l'ensemble des C qui sont les chefs d'André.

Puissance des langages logiques

Les LMD usuels, SQL, QUEL, algèbre relationnelle, ... n'ont pas la fermeture transitive.
Rappel: la fermeture transitive d'une relation binaire, R(A,B), dont les deux attributs A et B ont le
même domaine, est la plus petite relation S qui contient R et qui est transitive.
C'est-à-dire S est la plus petite relation telle que:
RS
X,Y,Z S(X,Y) S(Y,Z)  S(X,Z)

La fermeture transitive est utile, car fréquente dans les applications des systèmes experts, par
exemple pour la composition des produits, la gestion des réseaux (transports, fluides), les graphes,
...

Exemple:
chef(C,E) qui signifie: C est le chef direct de E
On veut définir tous les supérieurs hiérarchiques par le prédicat déduit "supérieur" :
supérieur(C,E) :- chef(C,E)
supérieur(C,E) :- supérieur(C,X) & chef (X,E)
Ceci ne peut pas s'exprimer en SQL seul, il faut recourir à SQL et à un langage de programmation
(C, Pascal,...).

Choix d'un langage logique pour bases de données

La logique des prédicats du premier ordre permet de représenter la connaissance (faits et règles) et
d'exprimer des opérations (requêtes, mises à jour) sur les relations. Prolog est un langage logique
bien connu, qui permet l'inférence. Mais, on ne peut pas l'employer comme langage d'interface de
bases de données déductives pour les raisons suivantes. C'est un langage de programmation qui
travaille uniquement sur des données en mémoire centrale. C'est un langage procédural: l'ordre des
règles et l'ordre des prédicats est important et fixe l'ordre d'exécution. Deux programmes Prolog
"logiquement équivalents" peuvent s'exécuter de façons totalement différentes, en particulier avec
la possibilité de boucler infiniment alors que la solution est évaluable ! De plus, le fait d'être
procédural implique que le système ne peut pas (ou à peine) optimiser le programme Prolog,
puisqu'on ne peut pas changer l'ordre des règles.

C'est pourquoi un nouveau langage logique, purement déclaratif, conçu pour les bases de données a
été proposé et est devenu un standard pour les chercheurs: Datalog que nous présentons dans ce
chapitre.

Datalog travaille sur un modèle de données plat du type modèle relationnel en première forme
normale. Mais les idées et principes de Datalog sont valables pour tout modèle de données, qu'il
soit plat comme le modèle relationnel ou structuré comme les modèles de données orientés objets.

© Christine Parent 3
2. Sémantique des règles logiques Datalog
Avec un LMD relationnel, tel que SQL, QUEL ou l'algèbre relationnelle, la sémantique des
requêtes est bien définie. On sait, à partir de l'expression de la requête, définir formellement les
tuples qui constituent le résultat. Par contre, définir exactement quel est le résultat d'un programme
composé d'un ensemble de règles n'est pas évident.

Il y a trois façons de définir la sémantique des règles. Dans les cas simples (comme dans ceux vus
ci-dessus) les trois donnent le même résultat. Mais si les règles sont plus complexes (avec
négation, fonctions ...), ce n'est plus vrai. En effet les règles ne définissent que les propriétés du
résultat, pas le résultat. Dans la plupart des cas (absence de fonction, absence de de négation ou
négations stratifiées), la sémantique peut être définie de façon unique en transformant les règles
déclaratives en une suite d'instructions qui calculent le résultat.

La première définition de la sémantique (théorie de la preuve) correspond à la compréhension

intuitive qu'on peut avoir des règles logiques: par déduction à partir des faits connus.
L'inconvénient de cette définition est qu'elle n'est pas utilisable quand il y a des négations dans la
partie droite, car elle ne fournit pas toujours en résultat ce qu'on attendrait intuitivement.
La seconde définition (théorie des modèles) est valable dans tous les cas et permet donc de définir
formellement la signification des programmes constitués de règles.
La dernière définition (par calcul) est une approche pratique: elle consiste à fournir un algorithme
qui permet de calculer/trouver les faits déduits. C'est ce que fait par exemple Prolog.
L'inconvénient de cette solution est qu'elle est uniquement pratique et non formelle.

2.1. Interprétation des règles par la théorie de la preuve (démonstration de théorème)

A partir des faits (relations) stockés dans la base de données, en utilisant les règles uniquement "en
avant", on déduit la partie gauche de la partie droite dans chaque règle autant que possible.

2.2. Interprétation des règles par la théorie des modèles

Etant donné un ensemble de règles, on peut en déduire les conséquences par la théorie de la preuve.
On peut aussi chercher quels sont les "mondes", appelés modèles, qui satisfont toutes les règles. Par
exemple, le monde réel que ces règles modélisant est un modèle de l'ensemble des règles. Autre
exemple, une base de données classique où tout est stocké sous forme de faits peut représenter
exactement les mêmes informations que les règles: c'est un modèle de cet ensemble de règles.

Plus formellement, étant donné un domaine D, infini, de constantes, l'interprétation d'un prédicat
d'arité n consiste à définir le sous-ensemble de D n (la relation n-aire) pour lequel le prédicat est
vrai.
Un modèle d'un ensemble de règles est constitué d'une interprétation pour chaque prédicat, telle
que toutes les règles sont toujours vraies quelles que soient les valeurs (prises dans D) affectées à
leurs variables.

Exemple:
p(X) :- q(X) (1)
q(X) :- r(X) (2)
D = entiers
Modèle 1: r(1), q(1), p(1), q(2), p(2), p(3) sont vrais
C'est un modèle, car les deux règles sont vraies pour tout X entier.

Application aux bases de données:

© Christine Parent 4
Pour un prédicat base de données, une occurrence de ce prédicat est vraie ssi cette occurrence est
un tuple de la relation décrivant l'extension de ce prédicat. Pour les prédicats de déduction, il faut
leur trouver une interprétation cohérente avec celle des prédicats base de données, qui conduise à
un modèle.

Exemple ci-dessus:
r est un prédicat base de données. Supposons que seul r(1) soit vrai.
Modèle 2: r(1), q(1), p(1)
C'est un deuxième modèle, qui est, comme le premier, cohérent avec la base de données (c'est-à-
dire qui contient les prédicats base de données: r(1)).
Il y a une infinité de modèles cohérents avec cette base de données.
Modèle 2 est un modèle minimum de cette base de données: on ne peut pas en ôter un seul fait
sans détruire le modèle cohérent avec la base de données. C'est le plus petit modèle minimum: il
n'existe pas de modèle plus petit.

S'il n'y a pas de négation dans les règles, il y a un seul modèle minimum qui est le plus petit
modèle, et il est identique à l'ensemble des faits déduits par l'approche de la théorie de la preuve.
Par contre, quand il y a négation, il peut coexister plusieurs modèles minimums sans qu'il n'y ait de
plus petit modèle, et ils ne correspondent pas nécessairement aux faits trouvés par la théorie de la
preuve.

2.3. Calcul de la sémantique d'un ensemble de règles

Un algorithme définit pour chaque "fait potentiel" (prédicat avec des arguments) s'il est vrai ou
faux.
- Par exemple Prolog cherche la preuve des faits potentiels
Mais les faits trouvés par Prolog ne sont pas toujours ceux trouvés par la théorie de la preuve, et
ils ne constituent pas toujours un modèle. C'est vrai en général; cela dépend des règles
(problème des négations).

- Autre approche: traduire les règles en une suite d'opérations d'algèbre relationnelle.
S'il n'y a pas de négation, on prouve que le résultat trouvé est le même que celui du plus petit
modèle et que celui de la théorie preuve. Dans le cas de négation stratifiée, on prouve que le
résultat trouvé est le même que celui d'un modèle minimum particulier.

Cette définition de la sémantique est très utile car elle permet d'implémenter efficacement les
ensembles de règles. Mais seule, elle n'est pas suffisante, car elle ne donne aucune définition
formelle de cette sémantique. La seule définition qu'elle donne est: "C'est l'ensemble de faits que
mon interpréteur déduit".

3. Datalog, modèle de données logique

Datalog est différent de Prolog:
- il n'y a pas de fonctions en argument des prédicats. Les arguments sont des constantes ou des
variables,
- il est purement déclaratif;
- la sémantique est définie par la théorie des modèles (ou quand c'est équivalent par la théorie de la
peuve).

Datalog et le modèle relationnel:

© Christine Parent 5
- Les prédicats sont des relations dont les attributs:
- n'ont pas de nom, mais uniquement un numéro d'ordre
- ont tous le même domaine D (on ne précise pas les domaines).

- Il y a deux types principaux de prédicats en Datalog:

- prédicat dont la relation est stockée dans la base de données, appelé prédicat de base, ou
prédicat base de données, ou prédicat défini par extension. C'est la relation du modèle
relationnel;
- prédicat défini par une (ou des) règle(s) logique(s), appelé prédicat de déduction, ou prédicat
déductif, ou prédicat défini par intension.

3.1. Définition de la syntaxe de Datalog

 Formule atomique
Une formule atomique est constituée d'un symbole de prédicat et d'une liste d'arguments. Par
exemple: p(A1, A2, ..., An)
où p est le nom d'un prédicat d'arité n, et les Ai sont les arguments du prédicat (constantes ou
variables).

Conventions d'écriture:
prédicats et constantes: première lettre minuscule
variables: première lettre majuscule
les relations correspondant aux prédicats base de données ont le même nom que le prédicat,
mais écrit en majuscules.

Remarque: toute formule atomique représente une sélection d'une relation, c'est-à-dire une
relation.
Exemple:
Soit la relation ARTICLE (no, couleur, prix)
la formule atomique:
article (100,C,P)
représente: [no = 100] ARTICLE .
La formule atomique:
article (X,C,X)
représente: [no = prix] ARTICLE .

 Prédicats évaluables
Afin de permettre dans les règles de comparer des variables ou constantes, il y a un dernier type de
prédicat: les prédicats évaluables ou prédicats de comparaison. Ce sont des prédicats qui utilisent
un opérateur de comparaison arithmétique: =, ≠, >, <, ≥, ≤.
Exemples: X<Y ou X=Y.
On peut classer ces prédicats évaluables dans les prédicats définis par extension bien que leur
interprétation (extension) ne soit pas stockée dans la base de données, mais plutôt calculée par le
SGBD. L'interprétation des prédicats évaluables est particulière: elle est non modifiable (pas de
mise à jour), et en général infinie.

 Clauses de Horn:
Une clause de Horn est une disjonction de formules atomiques éventuellement niées, dont au
maximum une seule est positive:
P1  P2 ... Pr
Ce qui s'écrit aussi: P1  (P2 ... Pr)
Il y a trois types de clauses de Horn:
- les faits: P1

© Christine Parent 6
 - les contraintes d'intégrité: (P2 ... Pr)
- lesrègles: P1  (P2 ... Pr)
qu'on écrit: P1 :- P2 & ... & Pr
On appelle: P1 : la tête de la règle
P2 & ... & Pr : le corps de la règle
P2, ...., Pr : les sous-buts de la règle
Les variables n'apparaissant que dans le corps sont quantifiées existentiellement sur le corps, les
autres variables universellement sur toute la règle.

Nous nous restreindrons aux clauses de Horn de type faits et règles (avec une et exactement une
formule atomique positive). On appelle programme logique un ensemble de ces clauses de Horn.

Exemple:
parent (X,Y) prédicat base de données qui signifie: X est parent direct de Y
gdparent (X,Y) :- parent (X,Z) & parent (Z,Y) (1)
cette règle (1) se lit. "X, Y, si Z tel que: X est parent de Z et Z est parent de Y, alors X
est un gdparent de Y"
ancêtre (X,Y) :- parent (X,Y) (2)
ancêtre (X,Y) :- ancêtre (X,Z) & parent (Z,Y) (3)
la règle (2) se lit: "X, Y, si X est parent de Y, alors X est un ancêtre de Y"
la règle (3) se lit; "X, Y, si Z tel que: X est ancêtre de Z et Z est parent de Y, alors X
est un ancêtre de Y".

3.2 Graphe de dépendance et récursivité

Il est souvent utile dans un programme logique de savoir de quels prédicats dépend un prédicat
déductif. Le graphe de dépendance formalise cette notion.

Définition: Le graphe de dépendance d'un programme logique est un graphe orienté dont:
- les noeuds sont les prédicats (sauf les prédicats évaluables)
- les arcs vont de chaque sous-but vers la tête du prédicat.

Exemple:
Le graphe de dépendance du programme logique de l'exemple précédent est:
U ti li se z W ord 6.0 c ( ou u l tŽr ie ur )

p ou r a ffich e r u n e im ag e M aci nto sh.

Un programme logique est récursif s'il existe un (ou des) cycle(s). Un prédicat est récursif s'il est
sur un cycle ou s'il dépend d'un prédicat récursif. Les prédicats base de données (qui n'ont pas de
sous-but) sont nécessairement non récursifs (pas d'arc entrant).

3.3 Règles Datalog sûres

Objectif: on veut que les règles Datalog ne définissent en résultat que des relations finies.

Problèmes:
Les prédicats évaluables peuvent définir des relations infinies.
Exemple: sup (X,Y) :- X>Y
Les règles avec des variables qui n'apparaissent que dans la tête génèrent aussi des relations
infinies.
Exemple: aime (X,Y) :- film (Y,"excellent")

© Christine Parent 7
Une solution simple est que toutes les variables des règles soient bornées, c'est-à-dire aient un
domaine de définition limité. Par exemple, les variables des prédicats base de données le sont
nécessairement. A l'opposé celles des prédicats évaluables ne le sont pas.

Définition: Les variables bornées d'une règle sont les suivantes:

- toute variable argument d'un sous-but qui n'est pas un prédicat évaluable,
- toute variable X d'un prédicat évaluable du type égalité tel que:
- X = constante ou constante = X ou
- X = Y ou Y=X avec Y variable bornée .

Définition: une règle est sûre si toutes ses variables (de la tête et du corps) sont bornées.

Cette définition suppose que les prédicats déductifs qui sont dans le corps de la règle sont eux-
mêmes définis par des règles sûres.

Exemples:
sup(X,Y) :- X>Y X et Y non bornés règle non sûre
aime(X,Y) :- film(Y,"excellent") Y borné, X non borné règle non sûre
ancêtre(X,Y) :- parent(X,Y) X et Y bornés règle sûre
ancêtre(X,Y) :- ancêtre(X,Z) & parent (Z,Y) X, Y, Z bornés règle sûre
p(X,Y) :- q(X,Z) & W=a & Y=W X, Y, Z, W bornés règle sûre

4. Evaluation de règles non récursives

On ne considère ici que les règles Datalog sûres, sans négation, et non récursives.
Objectif: évaluer ces règles par un algorithme qui les traduit en expressions d'algèbre relationnelle.

4.1 Principe
1. Le programme logique est non récursif. On peut donc définir grâce au graphe de dépendance un
ordre sur les prédicats selon lequel les évaluer: on va évaluer les sous-buts avant d'évaluer le
prédicat de tête.
2. Calcul de la relation correspondante à un prédicat p:
2.1. Pour chaque règle de tête p :
p :- q1 & ... & qn (1),
calculer l'expression d'algèbre P correspondante de la façon suivante:
Les tuples de P doivent satisfaire q1 et ... et qn. Si une même variable apparaît dans qi
et qj, les tuples correspondant dans les relations Qi et Qj doivent avoir pour cet attribut
la même valeur. P est donc construit à partir de la jointure : Q1 * Q2 ... * Qn.
1

2.2. Le prédicat p peut avoir comme variables un sous ensemble des variables du corps, alors il
faut projeter sur ces variables:
P =  [variables de tête de p] ( Q1 * ... * Qn )
2.3. Le prédicat p peut être défini par plusieurs règles. Dans ce cas, les tuples obtenus par
chaque règle sont bons. Il faut en faire l'union:
P = pour les règles de tête p  [variables de tête de p] ( Q1 * ... * Qn )

Il reste quelques problèmes:

- dans les prédicats sous-buts, il peut y avoir des constantes,
1 Notation: l'opérateur de jointure naturelle de l'algèbre relationnelle est représenté par une étoile * .
© Christine Parent 8
 - il peut aussi y avoir des prédicats évaluables.
Les algorithmes 1 et 2 tiennent compte de ces problèmes.

4.2 Relation définie par le corps d'une règle

Définition: la relation définie par le corps d'une règle est une relation:
- de schéma: l'ensemble des variables du corps: X1 ... Xm
- de population: les tuples <a1, ..., am> tels que quand on substitue les ai (pour i = {1 ... m}) aux
variables Xi dans le corps, tous les sous-buts deviennent vrais.

Exemples:
gdparent (X,Y) :- parent (X,Z) & parent (Z,Y)
Relation GDPARENT:
schéma: X Y Z
population: PARENTXZ * PARENTZY

fratrie(X,Y) :- parent(Z,X) & parent (Z,Y) & XY

Relation FRATRIE:
schéma: X Y Z
population: [XY] (PARENTXZ * PARENTZY)

p(X,Y) :- q(a,X) & r(X,Z,X) & s(Y,Z)

Relation P:
schéma: X Y Z
population: [X,Y,Z] ([T=a]QTX * [X=U]RXZU *SYZ)

Algorithme 1: Eval-rule
Données: une règle: r :- p1 & ... & pn
où les prédicats pi correspondent à des relations Ri (soit pi est un prédicat base de données, soit
c'est un prédicat déductif qui a déja été évalué)
Résultat: une expression d'algèbre, R, d'arguments (R1, ... Rn), équivalente au corps de la règle.
Début
1) Pour tout sous-but, pi, du corps de la règle, qui n'est pas un prédicat évaluable, calculer la
relation Qi correspondante:
Qi = [variables qui apparaissent] [#j = constante ......  #j = #k]Ri
dans le sous-but pi si "constante" si la même variable
apparaît dans pi apparaît à deux places
à la place de la différentes dans pi
variable Xj (aux places j et k)

2) Pour toute variable X du corps, qui n'est dans aucun des prédicats traités ci-dessus (qui est
uniquement dans des prédicats évaluables) calculer la relation unaire Dx:
- si un des prédicats est: X=a ou (X=Y & ... & Y=a)
alors: Dx={<a>}
- sinon on a: (X=Z & ... & Z=Y) et Y est variable dans un prédicat non évaluable: p k(....Y...),
alors: Dx=[#j]Rk

3) R = [prédicats évaluables du type XY] Jointurei,X (Qi, Dx)

Fin

4.3 Règles rectifiées

© Christine Parent 9
Quand un prédicat de déduction est défini par plusieurs règles (par exemple, supérieur ou ancêtre),
il faut faire l'union des relations définies par le corps de chacune de ces règles. Mais les variables
définies dans la tête des différentes règles peuvent être différentes, et il peut y avoir des constantes.

Exemple: pour le programme de recherche des ancêtres, dans telle famille on peut savoir descendre
de tel personnage illustre mais ne pas savoir exactement comment.
ancêtre (louis14, toto)

Solution: Pour que toutes les règles définissant le même prédicat déductif aient les mêmes variables
de tête, il faut rajouter des variables chaque fois qu'il y a une constante (soit X la variable mise à la
place de la constante) ou deux fois la même variable (soient X et Y les deux variables renommées),
et rajouter dans le corps les prédicats évaluables correspondants: X=constante ou X=Y.

Exemple:
ancêtre (X,Y) :- ancêtre (X,Z) & parent (Z,Y) (1)
ancêtre (U,V) :- parent (U,V) (2)
ancêtre (louis14, toto) (3)
On réécrit (2): ancêtre (X,Y) :- parent (X,Y)
On réécrit (3): ancêtre (X,Y) :- ancêtre (louis14, toto) & X=louis14 & Y=toto

4.4 Calcul de la relation équivalente à un programme Datalog non récursif:

Algorithme 2
Données: un programme Datalog non récursif, sûr
les relations R1 ... Rm des prédicats base de données du programme
Résultat: une suite d'expressions d'algèbre (d'arguments R1, ..., Rm) équivalente au programme.

Début
1) Rectifier toutes les règles
2) Etablir le graphe de dépendance afin d'ordonner les prédicats: p1, p2, ..., pr
3) Calculer la relation Pi pour chaque prédicat pi (en suivant l'ordre défini au point 2) de la façon
suivante:
- si c'est un prédicat base de données: Pi = Ri
- si c'est un prédicat déductif:
pour chaque règle rij de tête pi:
employer l'algorithme 1 pour calculer la relation Rij équivalente au corps de la règle,
projeter sur les variables de tête de pi,
faire l'union des Rij. On obtient ainsi l'expression d'algèbre équivalente au prédicat pi. Le
calcul de cette expression définit la relation Pi.
Fin

Théorème: L'algorithme 2 crée en résultat l'ensemble des faits qui peut être trouvé par la théorie de
la preuve, et qui est aussi le plus petit modèle (voir la démonstation dans [1]).

5. Evaluation de règles récursives

L'algorithme 2 pose des problèmes avec les programmes logiques récursifs car il n'y a pas d'ordre
selon lequel évaluer les prédicats (cycle dans le graphe de dépendance).

5.1 Principe

© Christine Parent 10
Dans le cas d'un programme récursif Datalog, on calcule les prédicats non récursifs selon
l'algorithme vu précédemment. Pour chaque ensemble de prédicats récursifs p 1, p2, ..., pr,
mutuellement dépendants (situés sur le même cycle), à partir des relations R 1, R2, ... Rm
correspondant aux prédicats base de données et à ceux déjà évalués, on peut calculer les relations
P1, P2, ..., Pr qui leur correspondent: c'est la solution à l'ensemble d'équations d'algèbre
relationnelle (appelées équations Datalog):
Pi = Eval (pi, Ri, ..., Rm, P1, ..., Pr) pour i=1, 2, ...., r
où Eval est la procédure algébrique qui fait l'union des projections des Eval-rule pour toutes les
règles de tête le même prédicat déductif pi.
On appelle point fixe d'un ensemble d'équations Datalog toute solution <P1, P2 ..., Pr> à ces
équations.

On démontre que les points fixes sont des modèles du programme logique. Mais tout modèle n'est
pas un point fixe de l'ensemble d'équations correspondantes. On démontre que le plus petit modèle
est le plus petit point fixe qui est aussi l'ensemble des faits dérivables par la théorie de la peuve.

5.2 Exemple: Fermeture transitive d'un graphe

chemin (X,Y) :- arc (X,Y) (1)
chemin (X,Y) :- chemin (X,Z) & chemin (Z,Y) (2)
Equation Datalog: CHEMINXY = ARCXY  [X,Y] (CHEMINXZ * CHEMINZY)
Soit le graphe suivant: 123
La base de données correspondante est:
ARC: <1,2> <2,3>
La théorie de la preuve définit l'ensemble de faits déduits suivants:
CHEMIN: <1,2> <2,3> <1,3>

Vérifions que cet ensemble de faits satisfait l'équation:

XZ * ZY
<1,2> <1,2> <1,2> <1,2>
<2,3> = <2,3> [X,Y] <2,3> <2,3>
<1,3> <1,3> <1,3>
C'est donc un point fixe.
C'est le plus petit point fixe car <1,3> doit en faire partie à cause de la jointure.
C'est le plus petit modèle cohérent avec la base de données: on ne peut pas en oter un seul fait.

Mais il y a d'autres solutions à l'équation. Par exemple:

CHEMIN: <1,2> <2,3> <1,3> <1,1>
est aussi un point fixe. En effet, l'équation est vérifiée.
Les deux règles sont vérifiées; c'est donc aussi un modèle.

Exemple d'un modèle (non minimum) qui n'est pas solution de l'équation Datalog:
Soit la base de données suivante: ARC = Ø
Soit: CHEMIN = <1,2>
C'est un modèle parce que les deux règles sont vraies (partie droite fausse).
Ce n'est pas un point fixe car:
<1,2> ≠ Ø  [X,Y] (<1,2> * <1,2>)

5.3 Evaluation des équations récursives:

Principe: calculer tous les Pi (par Eval), itérativement: P1, P2, ... Pr, P1, P2, ...Pr, P1, P2 ... Pr, ....,
jusqu'à ce que ça converge, c'est-à-dire jusqu'à ce que plus aucun Pi ne change.
Cette méthode converge, car Eval est "monotone", et toute fonction monotone converge.
© Christine Parent 11
Rappel: une fonction est monotone si: x, x', x>x' f(x)>f(x').
Dans notre cas, si l'argument de Eval contient le précédent, Eval contiendra le résultat précédent.
Preuve de la convergence de Eval: les opérateurs d'algèbre relationnelle qui servent à Eval
(sélection, projection, produit, jointure, union) sont monotones.

Algorithme 3
Données: un ensemble de prédicats base de données r1 ... rk, avec leurs relations R1 ..., Rk
un ensemble de prédicats déductifs p1 ... pm
Résultat: le plus petit point fixe (solution minimum des équations correspondant aux prédicats
p1, ... pm)

Début
1) Créer une équation pour chaque prédicat déductif pi:
Pi = Eval (pi, R1, ..., Rk, Pr, ..., Pm)
2) Initialiser les relations Pi à Ø.
3) Calculer Eval pour tous les Pi, et recommencer jusqu'à ce qu'aucun nouveau tuple ne soit ajouté
dans aucun Pi.
Fin

Exemple:
gdparent (X,Y) :- parent (X,Z) & parent (Z,Y) (1)
ancêtre (X,Y) :- parent (X,Y) (2)
ancêtre (X,Y) :- ancêtre (X,Z) & parent (Z,Y) (3)
Equations:
GDPARENTXY = [X,Y] (PARENTXZ * PARENTZY) (4)
ANCETREXY = PARENTXY [X,Y] (ANCETREXZ * PARENTZY) (5)
Soit la base de données PARENT suivante:
Utilisez Word 6.0c (ou ultŽrieur)

pour afficher une image Macintosh.

On calcule GDPARENT grâce à l'équation 4.

GDPARENT: ad, ae, bg, af, ch
On évalue itérativement ANCETRE grâce à l'équation 5:
ANCETRE
Initialisation Ø
itération 1 ab, bd, be, dg, ac,cf, fh
itération 2 + ad, ae, bg, af, ch
itération 3 + ag, ah
itération 4 aucun nouveau tuple

Théorème: L'algorithme 3 fournit le plus petit point fixe (solution des équations), qui est le plus
petit modèle, et qui est aussi l'ensemble des faits déductibles par la théorie de la preuve (voir la
démonstration dans [1]).

5.4. Optimisation des requêtes récursives

© Christine Parent 12
C'est un problème difficile, important, car la récursion est fréquente dans les applications.
Différents algorithmes ont été proposés, dont le suivant, appelé algorithme d'évaluation par
incrément ou "semi-naïve" (par opposition à l'algorithme 3: évaluation naïve).

Le principe même de l'algorithme 3 permet d'optimiser cet algorithme. A chaque itération,

l'algorithme 3 calcule la solution entière à l'équation, alors qu'on sait que cette solution est celle de
la précédente, plus (éventuellement) de nouveaux tuples. Il suffit donc de calculer les nouveaux
tuples. Ceux-ci proviennent des tuples nouveaux créés à la passe précédente.
Algorithme d'évaluation par incrément:
Pour évaluer un Pi:
- pour chaque sous-but Pk de type déductif, calculer Eval avec les relations complètes des autres
sous-buts, et uniquement les tuples créés par la passe précédente pour Pk  résultat partielk
- faire l'union des résultats partielsk.

Il existe d'autres méthodes d'optimisation plus sophistiquées.

6. Négations dans le corps des règles: Datalog neg

Avoir la possibilité de nier un sous-but est souvent utile, notamment pour réaliser l'équivalent de
l'opérateur de différence de l'algèbre relationnelle. Alors les règles ne sont plus des clauses de
Horn. Heureusement, la plupart des idées développées pour les clauses de Horn peuvent s'étendre à
ces règles.

Intuitivement, quand un sous-but est nié, cela signifie qu'il faut prendre le complément de la
relation correspondant à ce sous-but. Mais sur quel domaine définir le complément ? R est une
relation infinie.

Une solution pour que les règles soient sûres est que les variables de tout sous-but nié apparaissent
dans un autre sous-but non nié qui n'est pas de type évaluable.

Mais il reste des problèmes:

- il n'y a pas de méthode pour prouver les faits niés, et donc pas de théorie de la preuve
- il n'y a pas forcément de plus petit point fixe, mais plusieurs points fixes minimums.
On est obligé de choisir un des modèles minimums comme sémantique.

6.1 Ajuster les variables des sous-buts niés

Exemple (où tout va bien): base de données généalogique

Soient les deux prédicats suivants:
parent(X,Y) prédicat base de données signifiant: X est le père ou la mère de Y
descendant(X,Y) prédicat déductif signifiant: X est un descendant de Y
On définit un autre prédicat déductif:
petit_enfant(X,Y) :- descendant(X,Y) & parent(Y,X)
qui signifie: X est un petit enfant de Y à n générations (n≥2).
Cette règle est très proche de la différence de l'algèbre relationnelle:
PETITENFANTXY = DESCENDANTXY - PARENTYX

Exemple (où il y a trop de variables dans le sous-but nié)

Soient les deux prédicats base de données:

© Christine Parent 13
 homme(X) signifiant: X est un homme (de sexe masculin)
marié(X,Y) signifiant: X est le mari de Y
on définit le prédicat déductif suivant:
jeune_homme(X) :- homme(X) & marié(X,Y)
qui signifie: X est un jeune_homme si X est un homme et s'il n'existe pas de Y auquel X est marié.
En algèbre, on ne peut ici faire la différence car les deux relations n'ont pas le même schéma. Si on
essaye d'employer la négation de la relation MARIE, on obtient l'expression d'algèbre relationnelle:
[X]( HOMMEX *  MARIEXY )
où MARIEXY est l'ensemble des couples <X,Y> tel que X n'est pas le mari de Y.
Le résultat est l'ensemble des <X> tel que X n'est pas marié à toutes les femmes! C'est-à-dire tel
qu'il existe une femme à laquelle X n'est pas marié!
Solution: n'autoriser dans les sous-buts niés que des variables qui apparaissent dans un autre sous-
but positif et non évaluable.
Il faut (c'est toujours possible) réécrire la règle autrement. Par exemple, la règle jeune_homme peut
s'écrire:
mari(X) :- marié(X,Y)
jeune_homme(X) :- homme(X) & mari(X)
Ce qui conduit à l'expression d'algèbre suivante:
HOMMEX -[X]MARIEXY

Exemple (où il n'y a pas assez de variables dans le sous-but nié):

Soit le prédicat base de données:
aime(X,Y) qui signifie X aime l'objet Y
on définit le prédicat déductif suivant:
acheteur(X,Y) :- aime(X,Y) & fauché(X)
où fauché(X) est un prédicat base de données qui signifie que X est fauché.
Si on traduit en algèbre, on obtient:
ACHETEURXY = AIMEXY *  FAUCHEX
Mais FAUCHEX est une relation infinie. Pour éviter les relations infinies, il faut utiliser la
différence de relations compatibles (de même schéma) plutot que le complément:
ACHETEURXY = AIMEXY - (FAUCHEX * [Y]AIMEXY)
On peut donc réécrire la règle, avec la même idée: avoir le même ensemble de variables dans le
sous-but positif et dans le sous-but négatif. Ici il faut compléter le sous-but nié avec la (les)
variable manquante.
objet(Y) :- aime(X,Y)
fauché_objet(X,Y) :- fauché(X) & objet(Y)
acheteur(X,Y) :- aime(X,Y) &  fauché_objet(X,Y)

Les définitions de variable bornée et de programme sûr sont donc étendues de la façon suivante:

Définition: un programme est sûr si toutes ses variables sont bornées:

- soit par un argument d'un prédicat positif non évaluable,
- soit par égalité avec une constante ou une variable bornée, égalité directe ou par une chaîne
d'égalités.

6.2 Plusieurs points fixes minimums!

Problème: quand il y a négation dans un programme logique, il peut y avoir plusieurs points fixes
minimums (et non plus un unique plus petit point fixe). Que signifie alors un tel programme
logique?

© Christine Parent 14
Exemple:
homme(X) :- humain(X) & femme(X)
femme(X) :- humain(X) & homme(X)
où r est un prédicat base de données; p et q des prédicat déductifs.
Equations d'algèbre:
HOMME = HUMAIN - FEMME
FEMME = HUMAIN - HOMME
Soit la base de données: HUMAIN = {annie}
alors:
S1: HOMME = Ø , FEMME = {annie} est une solution minimale
S2: HOMME = {annie} , FEMME = Ø est une solution minimale
Il y a deux points fixes minimums! Il n'y a pas de plus petit point fixe.

6.3 Négation stratifiée

C'est une solution au problème de la multiplicité des points fixes minimums. On n'accepte un
programme logique avec négation que s'il respecte le principe suivant:
S'il existe une règle: p :- ... & q alors il n'existe pas de chemin p  q dans le graphe de
dépendance: p dépend négativement de q, mais q ne dépend pas de p. En d'autres termes, dans le
graphe de dépendance, il ne doit pas exister de cycle impliquant un arc avec négation. On dit que le
programme est stratifiable, car on va pouvoir le découper en couches de prédicats (les strates) de
telle façon que l'on saura évaluer chaque couche.

Dans l'exemple humain, homme et femme, il y a un cycle avec négation: le programme n'est pas
stratifiable.

Dans le cas de programme stratifiable, on peut avoir encore plusieurs points fixes minimums, mais
on sait choisir parmi eux celui qui représente la sémantique du programme logique.

Exemple de programme stratifiable:

p(X) :- r(X) (R1)
p(X) :- p(X) (R2) (sic. pour les besoins de l'exemple)
q(X) :- s(X) & p(X) (R3)
où r et s sont des prédicats base de données, de relations correspondantes:
R = {1}
S = {1, 2}
Les équations d'algèbre sont:
P=RP
Q=S-P
La solution S1: P = {1} , Q = {2} est un point fixe minimum.
La solution S2: P = {1, 2} , Q = Ø est un point fixe minimum. Il n'y a pas de plus petit point fixe.
S1 est plus "naturel" car on peut l'obtenir par substitutions dans les règles des faits connus. En effet:
r(1) et règle R1  p(1) vrai
p(2) et s(2) et règle R3  q(2) vrai
On retrouve: P = {1} , Q = {2} .

6.4 Trouver les stratifications

Idée: transformer un programme avec négation en un programme stratifié, si c'est possible.
Définition: Une strate est un ensemble (indicé) maximum de prédicats, tel que pour toute règle de
la strate on a:
- si: p :- ... &  q alors strate(p) > strate(q)
- si: p :- ... & q alors strate(p) ≥ strate(q)

© Christine Parent 15
Ces strates nous définissent l'ordre selon lequel calculer les prédicats du programme logique.

Algorithme 4: Stratification d'un programme logique

Données: un ensemble de règles Datalog avec éventuellement des sous-buts niés
Résultat: un programme stratifié (c'est-à-dire découpé en strates) si c'est possible
Début
1) Initialisation: strate 1 = ensemble de tous les prédicats
2) Examiner toutes les règles en recommençant jusqu'à ce qu'il n'y ait plus de changement dans les
affectations des prédicats aux strates, ou que le numéro d'une strate soit supérieur au nombre total
de prédicats, et en faisant:
- si p :- ... & q et strate(p) ≤ strate(q) alors changer p de strate, le mettre dans la strate =
strate(q)+1
- si p :- ... & q et strate(p) < strate(q) alors changer p de strate, le mettre dans la strate de q.
3) S'il advient que le numéro d'une strate devienne supérieur au nombre total de prédicats du
programme, alors il est impossible de stratifier ce programme.
Fin

Exemple: un programme sans négation: tous les prédicats sont dans la strate 1.

Exemple:
homme(X) :- humain(X) & femme(X) (R1)
femme(X) :- humain(X) & homme(X) (R2)
Initialisation:
strate 1 = humain, homme, femme
nb prédicats = 3
Première passe sur les règles:
R1  homme en strate 2
R2  femme en strate 3
Deuxième passe sur les règles:
R1  homme en strate 4 Impossible de stratifier ce programme.

Exemple:
p(X) :- r(X) (R1)
p(X) :- p(X) (R2)
q(X) :- s(X) & p(X) (R3)
Initialisation:
strate 1 = r, p, q, s
nb prédicats = 4
Première passe sur les règles:
R1  /
R2  /
R3  q en strate 2
Deuxième passe sur les règles:
R1  /
R2  /
R3  / OK: Le programme est stratifié.
La strate 1 contient donc p, r, et s; la strate 2 contient q.

6.5 Evaluation des programmes logiques stratifiés et sûrs

© Christine Parent 16
Quand un programme est stratifié et sûr, il est possible de calculer un point fixe minimum qui est le
plus "naturel" comme choix pour définir la sémantique du programme.

Principe: Les règles de chaque strate ne dépendent que des règles des strates inférieures ou de la
strate elle-même. S'il y a un sous-but nié, il est forcément défini dans une strate inférieure.
On peut calculer, par l'algorithme 3, les prédicats de la strate i en fonction des relations (ou de leur
complément) représentant les prédicats des strates inférieures ou égales.

Problème: comment calculer le complément d'une relation pour un sous-but nié

Soit, dans la strate i, un sous-but nié  q(X1, ..., Xn) d'arité n.
On a nécessairement calculé dans une strate précédente, la relation Q correspondante au prédicat q.
Soit DOM l'ensemble des symboles contenus dans les relations base de données et des constantes
du programme (les règles étant sûres, le résultat est nécessairement construit à partir de ces
valeurs).
Alors  Q = (DOM x ... x DOMn fois) - Q

Algorithme 5: évaluation d'un programme Datalog sûr et stratifié.

Données: le programme
les relations correspondant aux prédicats base de données
Résultat: un point fixe minimum particulier: celui qui trouve les plus petites relations pour les
prédicats des strates les plus basses (les strates d'indice 1, 2 ...)

Début:
1) Calculer DOM = ij  [un attributi] relationj base de données  {constantes du programme}
2) Pour chaque strate i = 1, 2, ... faire:
- pour chaque sous-but non nié de type prédicat de base de données ou prédicat déductif déjà
calculé dans une strate précédente, prendre la relation correspondante
- pour chaque sous-but nié q d'arité n, prendre la relation:
(DOM x ... x DOMn fois) - Q (Q étant la relation déjà calculée pour q)
- utiliser l'algorithme 3 (évaluation d'un programme récursif) pour calculer les relations
correspondant aux prédicats de la strate i.
Fin

Exemple:
p(X) :- r(X) strate 1
p(X) :- p(X)
q(X) :- s(X) & p(X) strate 2
Soient les relations R = {1} et S = {1,2} pour les prédicats base de données.
DOM = R  S
Strate 1:
Equation Datalog: P=RP
Cette équation est évaluée itérativement:
Eval(P) P
initialisation Ø
itération 1 1
itération 2 aucun nouveau tuple
Donc P ={1} c'est-à-dire P = R
Strate 2:
On calcule P :
P = DOM - P = (R  S) - R = S - R
Equation Datalog: Q = S *  P = S * (S-R) = S  (S-R) = S - R
© Christine Parent 17
Donc: Q = S - R
Cette équation peut se calculer directement (pas de récursivité):
Q={2}
C'est le point fixe minimum S1, trouvé le plus"naturel" au § 6.3.

7. Conclusion
Les SGBD déductifs souffrent actuellement d'une mauvaise image de marque dans la communauté
des clients potentiels (entreprises ...) parce que jugés trop "théoriques". Il est important de
développer au dessus de Datalog des interfaces utilisateurs plus agréables à manipuler, d'un aspect
plus connu, comme un SQL augmenté de capacités de déduction, ou un interface graphique. Il
faudra aussi proposer des méthodes de conception de bases de données déductives: comment
structurer l'ensemble de règles pour qu'il soit facilement compréhensible, comment choisir s'il faut
mémoriser telles informations en extension (par relation) ou en intension (par règle) ? ...

D'autres travaux ont permis d'enrichir Datalog avec des fonctions, ou des opérateurs de mise à jour.
Actuellement, un fort courant de recherches propose des langages de règles adaptés, non plus au
modèle relationnel plat, mais aux modèles orientés objets, de façon à combiner les avantages du
pouvoir descriptif des modèles orientés objets et la puissance de manipulation des langages de
règles; ce sont les DOOD "Deductive and Object Oriented Databases".

Bibliographie
[1] J. D. Ullman
"Principles of Database and Knowledge-Base Systems" volume 1
Computer Science Press

[2] N. Bidoit
"Bases de données déductives - Présentation de Datalog"
Armand Colin

[3] S. Ceri, [Link], [Link]

"Logic Programming and Databases"
Surveys in Computer Science, Springer Verlag

© Christine Parent 18