Datalog

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.

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

Syntaxe

Datalog a la syntaxe suivante^[1],[2]. On fixe:

• Un ensemble ${\displaystyle {\mathcal {X}}}$, dont les éléments sont appelés variables
• Un ensemble ${\displaystyle {\mathcal {D}}}$, dont les éléments sont appelés constantes
• Un schéma relationnel ${\displaystyle {\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é ^[3] ${\displaystyle {\mathit {But}}}$

Une règle Datalog est une expression de la forme: ${\displaystyle S(\mathbf {y} )\leftarrow R_{1}(\mathbf {x} _{1}),\dots ,R_{n}(\mathbf {x} _{n})}$ où ${\displaystyle S}$ est un prédicat intensionnel, ${\displaystyle R_{1}\dots R_{n}}$ sont des prédicats intensionnels ou extensionnels, et ${\displaystyle \mathbf {x} _{1}\dots \mathbf {x} _{n}}$ et ${\displaystyle \mathbf {y} }$ sont des n-uplets d'éléments de ${\displaystyle {\mathcal {X}}\cup {\mathcal {D}}}$, dont l'arité est compatible avec celle des prédicats. ${\displaystyle S(\mathbf {y} )}$ est appelé la tête de la règle, ${\displaystyle R_{1}(\mathbf {x} _{1}),\dots ,R_{n}(\mathbf {x} _{n})}$ son corps. On impose que chaque variable ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle P}$ définit une requête sur cette base de données ^[1],[2], l'arité de cette requête étant l'arité du prédicat ${\displaystyle {\mathit {But}}}$.

Pour définir cette sémantique, observons tout d'abord que chaque règle ${\displaystyle r\in P}$ de la forme ${\displaystyle 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 :$${\displaystyle 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ù ${\displaystyle \{z_{1}\dots z_{k}\}}$est l'ensemble des variables de ${\displaystyle {\mathcal {X}}}$ apparaissant dans le corps de la règle ${\displaystyle r}$.

Introduisons l'opérateur de conséquence ${\displaystyle \Gamma _{P}}$ qui transforme une instance du schéma relationnel ${\displaystyle {\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 ${\displaystyle P}$ : ${\displaystyle \Gamma _{P}(I):=I\cup \bigcup _{r\in P}\{r(I)\}}$. Pour ${\displaystyle n\in \mathbb {N} }$, posons ${\displaystyle I_{n+1}:=\Gamma _{P}(I_{n})}$. Le résultat de l'évaluation de ${\displaystyle P}$ sur ${\displaystyle I_{0}}$, noté ${\displaystyle P(I_{0})}$, est ${\displaystyle {\mathit {But}}(I_{\infty })}$, où ${\displaystyle I_{\infty }}$est le point fixe de la suite ${\displaystyle (I_{n})_{n\in \mathbb {N} }}$. L'existence de ce point fixe est garanti ^[1],[2] par le fait que ${\displaystyle \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.

Notes

1. (en) Serge Abiteboul, Richard Hull et Victor Vianu, Foundations of Databases, Addison Wesley, 1994, 685 p. (ISBN 978-0-201-53771-0, lire en ligne)
2. Serge Abiteboul, Richard Hull et Victor Vianu, Fondements des bases de données, Vuibert, 2000, 269 p. (ISBN 978-2-7117-8678-7)
3. (en) Stefano Ceri, Georg Gottlob et Letizia Tanca, « What You Always Wanted to Know About Datalog (And Never Dared to Ask) », IEEE Transactions on Knowledge and Data Engineering, vol. 1, n^o 1,‎ mars 1989 (ISSN 1041-4347, lire en ligne)

Articles connexes

• Structured Query Language

• Portail de la programmation informatique
• Portail des bases de données