Datalog

Datalog
Date de première version	1977
Paradigme	Langage de requête
Auteur	Hervé Gallaire et Jack Minker

Datalog est un langage de requête et de règles pour les bases de données déductives. Il correspond à un sous ensemble de Prolog. Ses origines remontent aux débuts de la programmation logique.

Syntaxe

Datalog a la syntaxe suivante. On fixe:

• Un ensemble ${\mathcal {X}}$, dont les éléments sont appelés variables
• Un ensemble ${\mathcal {D}}$, dont les éléments sont appelés constantes
• Un schéma relationnel ${\mathit {Sch}}$, c'est-à-dire un ensemble fini de prédicats, à chaque prédicat étant associé un entier positif ou nul appelé arité
• Une partition de ce schéma relationnel en deux sous-schémas, le schéma intensionnel et le schéma extensionnel (les prédicats sont donc soit intensionnels, soit extensionnels)
• Un prédicat intensionnel distingué ${\mathit {But}}$

Une règle Datalog est une expression de la forme: $S(\mathbf {y} )\leftarrow R_{1}(\mathbf {x} _{1}),\dots ,R_{n}(\mathbf {x} _{n})$ où $S$ est un prédicat intensionnel, $R_{1}\dots R_{n}$ sont des prédicats intensionnels ou extensionnels, et $\mathbf {x} _{1}\dots \mathbf {x} _{n}$ et $\mathbf {y}$ sont des n-uplets d'éléments de ${\mathcal {X}}\cup {\mathcal {D}}$, dont l'arité est compatible avec celle des prédicats. $S(\mathbf {y} )$ est appelé la tête de la règle, $R_{1}(\mathbf {x} _{1}),\dots ,R_{n}(\mathbf {x} _{n})$ son corps. On impose que chaque variable $y\in {\mathcal {Y}}$ apparaissant dans la tête de la règle apparaisse également dans son corps.

Un programme Datalog est un ensemble fini de règles Datalog.

Sémantique

Fixons une instance $I_{0}$ du schéma extensionnel, c'est-à-dire une base de données relationnelle dont les tables sont des instances des prédicats extensionnels. Un programme Datalog $P$ définit une requête sur cette base de données , l'arité de cette requête étant l'arité du prédicat ${\mathit {But}}$.

Pour définir cette sémantique, observons tout d'abord que chaque règle $r\in P$ de la forme $S(\mathbf {y} )\leftarrow R_{1}(\mathbf {x} _{1}),\dots ,R_{n}(\mathbf {x} _{n})$peut être vue comme une requête sur des instances du schéma relationnel :$$r(I):=\{S(\mathbf {y} )\mid \exists z_{1}\dots z_{k}~R_{1}(\mathbf {x_{1}} )\in I\land \dots \land R_{n}(\mathbf {x_{n}} )\in I\}$$où $\{z_{1}\dots z_{k}\}$est l'ensemble des variables de ${\mathcal {X}}$ apparaissant dans le corps de la règle $r$.

Introduisons l'opérateur de conséquence $\Gamma _{P}$ qui transforme une instance du schéma relationnel ${\mathit {Sch}}$ en une autre instance de ce même schéma, formée de l'instance initiale et de toutes ses conséquences par chaque règle de $P$ : $\Gamma _{P}(I):=I\cup \bigcup _{r\in P}\{r(I)\}$. Pour $n\in \mathbb {N}$, posons $I_{n+1}:=\Gamma _{P}(I_{n})$. Le résultat de l'évaluation de $P$ sur $I_{0}$, noté $P(I_{0})$, est ${\mathit {But}}(I_{\infty })$, où $I_{\infty }$est le point fixe de la suite $(I_{n})_{n\in \mathbb {N} }$. L'existence de ce point fixe est garanti par le fait que $\Gamma _{P}$ est un opérateur croissant, via une application élémentaire du théorème de Knaster-Tarski.

Implémentations

pyDatalog est un module qui ajoute Datalog à la bibliothèque de Python.

De même Datalog est un module pour OCaml.

Articles connexes

• Structured Query Language