Datalog

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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

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[modifier | modifier le code]

Datalog a la syntaxe suivante^[1]^,^[2]. 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é ^[3] ${\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[modifier | modifier le code]

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 ^[1]^,^[2], 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 ^[1]^,^[2] 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[modifier | modifier le code]

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

De même Datalog est un module pour OCaml.

Notes[modifier | modifier le code]

↑ ^{a b et c} (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)
↑ ^{a b et c} Serge Abiteboul, Richard Hull et Victor Vianu, Fondements des bases de données, Vuibert, 2000, 269 p. (ISBN 978-2-7117-8678-7)
↑ (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[modifier | modifier le code]

Structured Query Language

[:0-1] {a b et c} (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)

[:1-2] {a b et c} 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)

[1]

[2]

[3]