Datalog
Datalog è un linguaggio di interrogazione per basi di dati che ha riscosso un notevole interesse dalla comunità scientifica dalla metà degli anni ottanta.
Datalog si presenta come un linguaggio di programmazione logica sintatticamente derivato da Prolog rappresentandone un sottoinsieme relativo ai database 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 di query per database deduttivi. Negli ultimi anni, Datalog ha trovato nuove applicazioni per l'integrazione dei dati, l'estrazione delle informazioni, il networking, l'analisi dei programmi, la sicurezza e il cloud computing.[1]
David Maier è accreditato come inventore del termine Datalog.[2]
Dettagli
modificaIn Datalog è possibile descrivere un dominio attraverso predicati estensionali, che corrispondono alle relazioni nelle basi di dati e all'ABox delle basi di conoscenza, e predicati intensionali che vengono specificati attraverso regole logiche e che, come la TBox delle basi di conoscenza, ne arricchiscono il modello concettuale.
La risposta ad interrogazioni complesse è tipicamente affidata ad un motore d'inferenza di tipo backward chaining il quale realizza una procedura chiamata goal-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 tipo forward; 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 del punto 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 di don'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 di unificazione che sostituisce valori costanti alle variabili e ne controlla la presenza 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.
Espressività
modificaStudi 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 come negation 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 scrittura delle 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 di ridefinire 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.
Note
modifica- ^ Huang, Green, and Loo, Datalog and Emerging applications (PDF), in SIGMOD 2011, UC Davis..
- ^ Serge Abiteboul, Richard Hull e Victor Vianu, Foundations of databases, p. 305..
Bibliografia
modifica- Paolo Atzeni, Stefano Ceri, Piero Fraternali, Stefano Paraboschi e Riccardo Torlone, Basi di dati, modelli e linguaggi di interrogazione, McGraw-Hill, 2013, ISBN 978-8838668005.
- (EN) Anthony J. Bonner, Hypothetical Datalog: Negation and Linear Recursion, in Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems (PODS '89), New York (NY, USA), Association for Computing Machinery, 1989, DOI:10.1145/73721.73750.
| Controllo di autorità | LCCN (EN) sh2013000095 · J9U (EN, HE) 987007600062705171 |
|---|
