Datalog è unlinguaggio di interrogazione perbasi di dati che ha riscosso un notevole interesse dalla comunità scientifica dalla metà deglianni ottanta.
Datalog si presenta come unlinguaggio di programmazione logica sintatticamente derivato daProlog rappresentandone un sottoinsieme relativo aidatabase relazionali; infatti è basato anch'esso su regole di deduzione ma non permette l'utilizzo di simboli di funzione né un modello di valutazione non procedurale (risoluzione SLD). Viene spesso utilizzato come linguaggio diquery per database deduttivi. Negli ultimi anni, Datalog ha trovato nuove applicazioni per l'integrazione dei dati, l'estrazione delle informazioni, ilnetworking, l'analisi dei programmi, la sicurezza e ilcloud computing.[1]
David Maier è accreditato come inventore del termine Datalog.[2]
In Datalog è possibile descrivere un dominio attraverso predicati estensionali, che corrispondono alle relazioni nelle basi di dati e all'ABox dellebasi di conoscenza, e predicati intensionali che vengono specificati attraverso regole logiche e che, come laTBox delle basi di conoscenza, ne arricchiscono il modello concettuale.
La risposta ad interrogazioni complesse è tipicamente affidata ad un motore d'inferenza di tipobackward chaining il quale realizza una procedura chiamatagoal-driven; per verificare la richiesta dell'utente (goal) cerca di scomporla riducendo i predicati intensionali fino a renderli una serie di predicati estensionali da verificare singolarmente. È tuttavia ininfluente dal punto di vista dei risultati ottenuti la scelta di utilizzare un motore d'inferenza di tipoforward; questo tipo di decisione è lasciata al progettista della specifica implementazione. Le più semplici implementazioni del linguaggio, per portare a terminazione il processo deduttivo, ricorrono alla tecnica delpunto fisso, che consiste nell'interrompere il processo di valutazione delle regole relative al predicato intensionale ricorsivo quando l'ultima iterazione non genera nuovi risultati.
Ogni regola è composta da una testa (head o conseguente) e da un corpo (body o antecedente) a loro volta formati da uno o più predicati atomici con argomenti che possono essere variabili, costanti oppure il simbolo didon't care. Nella definizione di regole si possono anche usare predicati speciali come operatori di confronto e funzioni aritmetiche predefinite. Se tutti gli atomi del corpo sono verificati ne consegue logicamente che anche il predicato atomico della testa lo sia.
La veridicità di un atomo è affidata al processo diunificazione che sostituisce valori costanti alle variabili e ne controlla lapresenza nella base di dati. L'interpretazione in logica del prim'ordine di una regola è dunque quella di un'implicazione tra disgiunzione di predicati.Vi è inoltre da segnalare che Datalog costituisce anche un linguaggio per la definizione di viste e di vincoli d'integrità dato che il corpo di una regola può verificare delle eventuali inconsistenze e la testa segnalarle all'applicazione che gestisce il DB.
Studi sull'espressività del linguaggio Datalog hanno dimostrato che esso è più espressivo dell'algebra relazionale delle basi di dati a patto di introdurre l'uso dell'operatore di negazione di condizioni atomiche necessario per definire il complemento;[senza fonte] in questo modo si introduce però un costrutto non monotòno che attribuisce al linguaggio un'espressività all'infuori della logica del prim'ordine, nota comenegation as failure. La maggiore espressività è dovuta alla possibilità di scrivere regole ricorsive in grado cioè di richiamare il medesimo atomo della testa anche nel corpo della regola. L'introduzione di ricorsione e negazione porta facilmente alla scrittura di regole indecidibili. Per non incorrere in questo problema e per preservare l'integrità della base di dati si è scelto di imporre alcune condizioni di scritturadelle regole che limitano il potere espressivo del linguaggio chiamate safety conditions.
La prima impone che i predicati estensionali possano comparire solo nel corpo delle regole in modo da garantire che non vi sia il tentativo diridefinire le relazioni memorizzate nella base di dati. La seconda e la terza condizione impongono che tutte le variabili che appaiono nella testa debbano apparire anche nel corpo della regola e che se una variabile compare in un atomo di confronto debba allora comparire in un atomo del corpo della stessa regola. Queste ultime hanno lo scopo di garantire che il processo di deduzione giunga a termine.L'operatore di negazione inoltre deve essere usato con la clausola di safe che tutte le variabili in un letterale negato debbano apparire anche in uno non negato all'interno del corpo; inoltre non ci devono essere cicli di dipendenza tra letterali negati.
| Linguaggi di interrogazione | |
|---|---|
| In uso | .QL ·ALPHA ·CQL ·Cypher ·D ·DMX ·Datalog ·GraphQL ·Gremlin ·ISBL ·LDAP ·LINQ ·MQL ·MDX ·OQL ·OCL ·QUEL ·SMARTS ·SPARQL ·SQL ·XQuery ·XPath ·YQL |
| Proprietari | YQL ·LINQ |
| Superati | CODASYL |
| Controllo di autorità | LCCN(EN) sh2013000095 ·J9U(EN, HE) 987007600062705171 |
|---|
