Jurnal de date

Jurnal de date
Clasa de limba	Boolean , declarativ
Aparut in	1986 ( 1986 )
Tip sistem	Slab
Dialectele	Datomic , pyDatalog , Dyna etc.

Datalog este un limbaj de programare logic declarativ. Deși din punct de vedere sintactic arată ca un subset al lui Prolog , Datalog utilizează în general un model de rezoluție a expresiei de jos în sus și nu de sus în jos. Această diferență duce la o diferență semnificativă de comportament și proprietăți față de Prolog. Este adesea folosit ca limbaj de interogare pentru bazele de date deductive. În ultimii ani, Datalog a găsit noi utilizări în integrarea datelor, extragerea informațiilor, rețele, analiza programelor, securitate, cloud computing și învățarea automată [1] [2] .

Originile sale datează de la începutul programării logice, dar a început să iasă în evidență ca un subiect aparte în jurul anului 1977, când Herve Galler și Jack Minker au organizat un seminar despre logică și baze de date [3] . David Mayer este creditat cu inventarea termenului Datalog [4] .

Caracteristici, limitări și extensii

Spre deosebire de Prolog, instrucțiunile programului Datalog pot fi specificate în orice ordine. Mai mult, interogările Datalog față de seturi finite sunt garantate să se completeze, motiv pentru care Datalog nu are o declarație de tăiere în Prolog. Acest lucru face Datalog un limbaj complet declarativ.

Spre deosebire de Prolog, Datalog:

interzice termenii complecși ca argumente pentru predicate, de exemplu, p(1, 2) este permis, dar nu p(f(1), 2),
impune anumite restricții de stratificare privind utilizarea negației și recursiunii,
necesită ca fiecare variabilă care apare într-un cap de propoziție să apară și într-un literal pozitiv non-aritmetic (adică nu inversat) în corpul propoziției,
cere ca fiecare variabilă care apare într-un literal negativ din corpul unei clauze să apară și într-un literal pozitiv din corpul clauzei [5]

Procedura de rezolvare a unei interogări cu Datalog se bazează pe logica de ordinul întâi și, din acest motiv, este corectă și completă. Cu toate acestea, Datalog nu este complet Turing și, prin urmare, este folosit ca un limbaj specific domeniului care poate profita de algoritmi eficienți proiectați pentru a rezolva interogările. Într-adevăr, au fost propuse diverse metode pentru a executa eficient interogări, precum algoritmul Magic Sets [6] , programarea logică tabelară [7] sau rezoluția SLG [8] .

Unele sisteme de baze de date utilizate pe scară largă includ idei și algoritmi dezvoltați pentru Datalog. De exemplu, standardul SQL:1999 include interogări recursive, iar algoritmul Magic Sets (conceput inițial pentru a evalua mai rapid interogările Datalog) este implementat în IBM DB2 . În plus, motoarele Datalog sunt în spatele sistemelor de baze de date specializate, cum ar fi baza de date Intellidimension pentru Web-ul Semantic [9] . Au fost făcute mai multe extensii la Datalog, cum ar fi pentru a suporta funcții agregate, pentru a permite programarea orientată pe obiecte sau pentru a permite disjuncții ca antete de propoziție. Aceste extensii au un impact semnificativ asupra definirii semanticii Datalog și asupra implementărilor unor versiuni specifice ale interpretului Datalog.

Fragmente

Programele Datalog pot folosi sau nu negația în corpurile de reguli: Programele Datalog cu negație trebuie adesea să o folosească ca negație stratificată pentru a se asigura că semantica este bine definită. Programele Datalog pot folosi sau nu inegalități între variabilele din corpurile de reguli.

Sunt definite unele fragmente de sintaxă Datalog, cum ar fi următoarele (cel mai restricționat la cel mai puțin restricționat):

jurnal de date liniar, unde corpurile de reguli trebuie să fie formate dintr-un singur atom
un jurnal de date protejat, în care pentru fiecare regulă, toate variabilele care apar în corpurile regulilor trebuie să apară împreună în cel puțin un atom, numit atom de gardă.
un jurnal de date protejat de limite, în care pentru fiecare regulă, toate variabilele care sunt comune corpului regulii și antetului regulii (numite variabile limită) trebuie să apară toate împreună într-un atom de gardă.

O altă limitare se referă la utilizarea recursiunii: un Datalog nerecursiv este definit prin interzicerea recursiunii în definirea programelor Datalog. Acest fragment de Datalog este la fel de expresiv ca interogările concatenate, dar scrierea interogărilor ca un Datalog nerecursiv poate fi mai concis.

Expresivitatea

Problema constrângerii pentru Datalog se rezumă la dacă programul Datalog este mărginit, adică dacă adâncimea maximă de recursivitate atinsă la evaluarea programului în baza de date de intrare poate fi delimitată de o constantă. Cu alte cuvinte, problema se rezumă la dacă programul Datalog poate fi rescris ca program Datalog nerecursiv. Soluția la limitarea programelor arbitrare Datalog este indecidabilă, dar poate fi decidabilă limitându-ne la unele fragmente din Datalog [10] .

Exemple

Aceste două rânduri definesc două fapte, adică lucruri care sunt valabile întotdeauna:

părinte ( xerces , brooke ). părinte ( brooke , damocles ).

Iată ce înseamnă: xerces este părintele lui Brooke și Brooke este părintele lui Damocles. Numele sunt scrise cu litere mici, deoarece șirurile care încep cu o literă mare reprezintă variabile.

Note

↑ Huang, Green, and Loo, Datalog and Emerging applications , SIGMOD 2011 , UC Davis , < http://www.cs.ucdavis.edu/~green/papers/sigmod906t-huang.pdf > Arhivat 22 octombrie 2020 la Wayback Masina .
↑ Mei, Hongyuan; Qin, Guanghui; Xu, Minjie; Eisner, Jason (2020). „Înregistrare de date neuronale prin timp: modelare temporală informată prin specificație logică”. Proceedings of ICML 2020 . arXiv : 2006.16723 .
↑ Logica si baze de date . - New York, 1978. - viii, 458 pagini p. - ISBN 0-306-40060-X , 978-0-306-40060-5.
↑ S. Abiteboul. Bazele bazelor de date . - Reading, Mass.: Addison-Wesley, 1995. - xviii, 685 pagini p. - ISBN 0-201-53771-0 , 978-0-201-53771-0.
↑ Datalog (prezentare) (downlink) . web.archive.org (25 martie 2017). Preluat la 20 august 2022. Arhivat din original la 25 martie 2017. (nedefinit)
↑ Bancilhon. „Seturi magice și alte moduri ciudate de a implementa programe logice” (PDF) . PT : UNL. Arhivat din original (PDF) la 08.03.2012. Parametrul depreciat folosit |url-status=( ajutor )
↑ Pfenning, Frank; Schuermann, Carsten. „Ghidul utilizatorului Douăsprezece” . CMU. Arhivat din original pe 22.08.2022 . Preluat 2022-08-22 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ „Calcul eficient de sus în jos a interogărilor sub o semantică bine fundamentată” (PDF) . Arhivat (PDF) din original pe 2013-10-04 . Preluat 2022-08-22 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data : 2004, Paris, France, June 13-18, 2004. . - [New York]: Association for Computing Machinery, 2004. - xvii, 988 pagini p. - ISBN 1-58113-859-8 , 978-1-58113-859-7.
↑ Gerd G Hillebrand, Paris C Kanellakis, Harry G Mairson, Moshe Y Vardi. Probleme de limitare indecidabile pentru programele de jurnal de date // The Journal of Logic Programming. — 1995-11. — Vol. 25 , iss. 2 . — P. 163–190 . - doi : 10.1016/0743-1066(95)00051-K . Arhivat 7 mai 2021.