Datalog

S Vikipedije, slobodne enciklopedije

Datalog je programski jezik deklarativne i logičke paradigme, koji nastaje kao značajan podskup programskog jezika Prolog. Često se koristi kao jezik za pisanje upita za deduktivne baze podataka. Datalog je našao svoju primenu u integraciji, ekstrakciji informacija, računarskim mrežama, analizama programa, sigurnosti podataka i računarstvu u oblaku.[1]

Datalog je programski jezik napravljen još od osnivanja logičkog programiranja, ali postaje zasebna oblast oko 1977. godine kada Herve Galer i Džek Minker organizuju radionicu Logika i baze podataka.[2] David Majer je profesor kome se pripisuje kovanje termina Datalog.[3]

Karakteristike, ograničenja i proširenja[uredi | uredi izvor]

Za razliku od Prologa, naredbe u Datalogu mogu biti biti proizvoljnog redosleda. Osim toga, Datalog upiti na konačnim skupovima garantuju završetak izvršavanja tako da Datalog nema operator cut koji ima programski jezik Prolog što ga čini čistim deklarativnim programskim jezikom.

U odnosu na Prolog, Datalog:

  1. ne dozvoljava složene terme kao argumente predikata npr. p (1, 2) jeste, dok p (f (1), 2) nije dozvoljeno,
  2. nameće ograničenja za upotrebu negacije i rekurzije,
  3. zahteva da svaka promenljiva koja se pojavljuje u glavi klauze, takođe mora da se pojavi u pozitivnim (nenegiranim) literalima u telu klauze,
  4. zahteva da se svaka promenljiva koja se javlja u negativnom literalu u telu klauze takođe pojavljuje i u nekom pozitivnom literalu tela klauze[4]

Evaluacija upita zasnovana je na logici prvog reda, pa zadovoljava svojstvo soundness (čuva tautologije) i kompletnost. Ipak, Datalog nije Tjuring potpun, i koristi karakteristike domena i prednosti efikasnih algoritama razvijenih za evaluaciju upita. Postoje različiti načini za efikasno obavljanje upita npr. algoritam Magičnih skupova (the Magic Sets algorithm)[5] i tabelarno logičko programiranje.[6]

Neke široko korišćene baze podataka uključuju i ideje i algoritme razvijene za Datalog. Na primer, standard SQL 1999 uključuje rekurzivne upite, i pomenuti algoritam magičnih skupova (koji je napravljen za bržu evaluaciju Datalog upita) koji je implementiran u IBM-ovom DB2.[7]

Napravljeno je nekoliko dodataka za Datalog, kao što su podrška za agregatne funkcije i objektno-orijentisano programiranje, kao i mogućnost korišćenja disjunkcija kao glava klauze. Ovi dodaci su imali veliki uticaj na definiciju semantike Dataloga i implementaciju odgovarajućeg Datalog interpretatora.

Primer[uredi | uredi izvor]

Primer Datalog programa: 

 roditelj(Marko, Marija).
 roditelj(Marija, Zoran).

Prethodne linije definišu dve činjenice koje mogu biti protumačene kao: Marko je Marijin roditelj i kao Marija je Zoranov roditelj. 

 predak(X,Y) :- roditelj(X,Y).
 predak(X,Y) :- roditelj(X,Z),predak(Z,Y).

Prethodne linije definišu pravila kojim se opisuje osobina predak koja je glava pravila. Svako pravilo se sastoji iz dva glavna dela koji su razdvojeni simbolom :-. Levi deo pravila se zove glava pravila, dok se desni zove telo. Pravilo se čita (i može da bude intuitivno shvaćeno kao) <glava> ako se zna da važi <telo>. Velika slova su promenljive. U našem primeru prvo pravilo može biti pročitano kao X je predak osobe Y ako se zna da je X roditelj osobe Y. Drugo pravilo bi bilo X je predak osobe Y ako se zna da je X roditelj neke osobe Z koja je predak osobe Y. Kao što smo rekli redosled klauza u telu nije bitan u Datalogu što je drugačije od Prologa kod koga je redosled od ključnog značaja za evaluaciju poziva upita.

Datalog pravi razliku između simbola koji su definisani činjenicama i onih definisanih pravilima.[8] U prethodnom primeru predak bi bio predikatski simbol za pravilo, a roditelj za činjenicu. Predikati mogu takođe biti definisani kao činjenice i pravila, a svaki Datalog kod može biti ponovo napisan tako da se izgube oni predikatski simboli koji imaju višestruke uloge. 

 ?- predak(Marko,X).

Poslednji upit traži sve osobe kojima je osoba sa imenom Marko predak, i povratna vrednost biće Marija i Zoran ukoliko se postavi u Datalog sistemu koji ima činjenice i pravila definisana u ovom primeru.

Sistemi koji implementiraju Datalog[uredi | uredi izvor]

Evo kratke liste sistema koji su ili bazirani na Datalogu ili imaju Datalog interpretator:

Besplatan softver[uredi | uredi izvor]

Napisan u Ime sistema Mogućnost testiranja Spoljašnja baza podataka Opis Licenca
Java IRIS[9] da[10] IRIS nasleđuje Datalog funkcionalne simbole, ugrađene predikate, lokalno raslojene ili slojevite logičke programe (koji koriste Datalog semantiku), nesigurna pravila i XML šeme tipova podataka. (GNU LGPL v2.1).
Jena semantički frejmvork za Veb koji uključuje implementaciju Dataloga, što definiše OWL i predstavlja podršku za RDFS.[11] (Apache v2)
SociaLite SociaLite je varijanta Dataloga koja se koristi u Stranfordu za analizu velikih grafova. (Apache v2)
Graal[12] Graal je Java alat posvećen upitima u bazu znanja u okviru frejmvorka egzistencijalnih pravila, zvanog Datalog+/-. (CeCILL v2.1)
C XSB logičko programiranje i deduktivne baze podataka za Unix i Windows (GNU LGPL).
C++ Inter4QL[13] javno dostupan interpretator u komandnoj liniji za Datalog-like 4QL upitni jezik implementiran u programskom jeziku C++ za Windows, Mac OS X i Linux. Negacija je dozvoljena u glavama i telima pravila kao i u rekurziji. (GNU GPL v3).
Pajton pyDatalog 11 dijalekata SQL-a dodaje logičko programiranje u pajton alate. Može da pokreće logičke upite u baze podataka ili pajton objekte, a i da koristi logičke klauze, kako bi se definisalo ponašanje klasa u pajtonu. (GNU LGPL)
Lua Datalog[14] da[15] za deduktivne baze podataka. (GNU LGPL).
Prolog DES[16] javno dostupna implementacija koja može da se koristi za kurseve na kojima se uči Datalog. (GNU LGPL).
Clojure Cascalog Hadoop biblioteka Clojure za upite nad podacima čuvanim na Hadoop klasterima. (Apache).
Clojure Datalog biblioteka koja implementira neke od aspekata Dataloga. (Eclipse Public License 1.0).
Racket Datalog za Racket[17] (GNU LGPL).
Tcl tclbdd[18] implementacija zasnovana na binarnim dijagramima odluke. Napravljen za razvijanje ompimizujućeg kompilatora za Tcl. (BSD).
U ostalim nepoznatim jezicima bddbddb[19] implementacija Dataloga je urađena na Univerzitetu Stanford. Najviše je korišćena za upite nad Java bajt kodom uključujući i neke veće Java programe. (GNU LGPL).
ConceptBase[20] deduktivna i objektno-orijentisana baza podataka za sistem koji je zasnovan na Datalog upitnom evaluatoru. Najviše se koristi za modelovanje i metamodelovanje. (FreeBSD-style license). Prolog, Java.

Softver koji nije besplatan[uredi | uredi izvor]

  • Datomic baza podataka napravljena za izradu skalabilnih, fleksibilnih i pametnih aplikacija koje mogu biti pokrenute na svim novim "oblak" arhitekturama, a koja koristi Datalog kao upitni jezik.
  • DLV je komercijalni Datalog dodatak koji podržava disjunktivne glave klauza.
  • FoundationDB nudi besplatnu bazu podataka za povezivanje sa pyDatalog, sa uputstvima za njeno korišćenje.[21]
  • LogicBlox, komercijalna implementacija Dataloga korišćena za Veb maloprodaju i za aplikacije za osiguranje.
  • .QL, je komercijalna objektno-orijentisana varijanta kreirana od strane kompanije Semmle.[22]
  • SecPAL je jezik kojim je napisana politika sigurnosti razvijena u Majkrosofta.[23]

Reference[uredi | uredi izvor]

  1. ^ Shan Shan Huang; Green, Todd J.; Boon Thau Loo, „Datalog and Emerging applications”, SIGMOD 2011 (PDF), UC Davis 
  2. ^ Gallaire, Hervé; Minker, John ‘Jack’, ur. (1978), „Logic and Data Bases, Symposium on Logic and Data Bases, Centre d'études et de recherches de Toulouse, 1977”, Advances in Data Base Theory, New York: Plenum Press, ISBN 0-306-40060-X 
  3. ^ Abiteboul, Serge; Hull, Richard; Vianu, Victor, Foundations of databases, str. 305 
  4. ^ „Datalog”. Arhivirano iz originala 25. 03. 2017. g. Pristupljeno 15. 04. 2016. 
  5. ^ Bancilhon. „Magic sets and other strange ways to implement logic programs” (PDF). PT: UNL. Arhivirano iz originala (PDF) 08. 03. 2012. g. Pristupljeno 15. 04. 2016. 
  6. ^ Pfenning, Frank; Schuermann, Carsten. „Twelf User's Guide”. CMU. 
  7. ^ Gryz; Guo; Liu; Zuzarte. „Query sampling in DB2 Universal Database” (PDF). 
  8. ^ Lifschitz. „Datalog Programs and Their Stable Models”. DE: Springer. 
  9. ^ Iris reasoner, Arhivirano iz originala 11. 03. 2016. g., Pristupljeno 15. 04. 2016 
  10. ^ „IRIS demo”. Arhivirano iz originala 12. 05. 2016. g. Pristupljeno 15. 04. 2016. 
  11. ^ „Jena”. Source forge. 
  12. ^ Graal library 
  13. ^ 4QL 
  14. ^ Ramsdell, „Datalog”, Tools, NEU, Arhivirano iz originala 11. 01. 2011. g., Pristupljeno 15. 04. 2016 
  15. ^ Sangkok, Y, „Wrapper”, Mitre Datalog, Git hub [mrtva veza], (compiled to JavaScript).
  16. ^ Saenz-Perez, DES: A Deductive Database System, ES: ENTCS 
  17. ^ „Datalog”, Racket (technical documentation) 
  18. ^ Kenny, Kevin B (12. 11. 2014). Binary decision diagrams, relational algebra, and Datalog: deductive reasoning for Tcl (PDF). Twenty-first Annual Tcl/Tk Conference. Portland, Oregon. Pristupljeno 29. 12. 2015. [mrtva veza]
  19. ^ „bddbddb”, Source forge 
  20. ^ ConceptBase 
  21. ^ FoundationDB Datalog Tutorial 
  22. ^ Semmle 
  23. ^ „SecPAL”. Microsoft Research. Arhivirano iz originala 23. 02. 2007. g. Pristupljeno 15. 04. 2016. 

Literatura[uredi | uredi izvor]

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Даталог&oldid=27673385”