Пређи на садржај

Даталог

С Википедије, слободне енциклопедије

Даталог je програмски језик декларативне и логичке парадигме, који настаје као значајан подскуп програмског језика Пролог. Често се користи као језик за писање упита за дедуктивне базе података. Даталог је нашао своју примену у интеграцији, екстракцији информација, рачунарским мрежама, анализама програма, сигурности података и рачунарству у облаку.[1]

Даталог је програмски језик направљен још од оснивања логичког програмирања, али постаје засебна област око 1977. године када Херве Галер и Џек Минкер организују радионицу Логика и базе података.[2] Давид Мајер је професор коме се приписује ковање термина Даталог.[3]

Карактеристике, ограничења и проширења

[уреди | уреди извор]

За разлику од Пролога, наредбе у Даталогу могу бити бити произвољног редоследа. Осим тога, Даталог упити на коначним скуповима гарантују завршетак извршавања тако да Даталог нема оператор cut који има програмски језик Пролог што га чини чистим декларативним програмским језиком.

У односу на Пролог, Даталог:

  1. не дозвољава сложене терме као аргументе предиката нпр. p (1, 2) јесте, док p (f (1), 2) није дозвољено,
  2. намеће ограничења за употребу негације и рекурзије,
  3. захтева да свака променљива која се појављује у глави клаузе, такође мора да се појави у позитивним (ненегираним) литералима у телу клаузе,
  4. захтева да се свака променљива која се јавља у негативном литералу у телу клаузе такође појављује и у неком позитивном литералу тела клаузе[4]

Евалуација упита заснована је на логици првог реда, па задовољава својство soundness (чува таутологије) и комплетност. Ипак, Даталог није Тјуринг потпун, и користи карактеристике домена и предности ефикасних алгоритама развијених за евалуацију упита. Постоје различити начини за ефикасно обављање упита нпр. алгоритам Магичних скупова (the Magic Sets algorithm)[5] и табеларно логичко програмирање.[6]

Неке широко коришћене базе података укључују и идеје и алгоритме развијене за Даталог. На пример, стандард SQL 1999 укључује рекурзивне упите, и поменути алгоритам магичних скупова (који је направљен за бржу евалуацију Даталог упита) који је имплементиран у IBM-овом DB2.[7]

Направљено је неколико додатака за Даталог, као што су подршка за агрегатне функције и објектно-оријентисано програмирање, као и могућност коришћења дисјункција као глава клаузе. Ови додаци су имали велики утицај на дефиницију семантике Даталога и имплементацију одговарајућег Даталог интерпретатора.

Пример

[уреди | уреди извор]

Пример Даталог програма: 

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

Претходне линије дефинишу две чињенице које могу бити протумачене као: Марко је Маријин родитељ и као Марија је Зоранов родитељ. 

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

Претходне линије дефинишу правила којим се описује особина предак која је глава правила. Свако правило се састоји из два главна дела који су раздвојени симболом :-. Леви део правила се зове глава правила, док се десни зове тело. Правило се чита (и може да буде интуитивно схваћено као) <глава> ако се зна да важи <тело>. Велика слова су променљиве. У нашем примеру прво правило може бити прочитано као X је предак особе Y ако се зна да је X родитељ особе Y. Друго правило би било X је предак особе Y ако се зна да је X родитељ неке особе Z која је предак особе Y. Као што смо рекли редослед клауза у телу није битан у Даталогу што је другачије од Пролога код кога је редослед од кључног значаја за евалуацију позива упита.

Даталог прави разлику између симбола који су дефинисани чињеницама и оних дефинисаних правилима.[8] У претходном примеру predak би био предикатски симбол за правило, а roditelj за чињеницу. Предикати могу такође бити дефинисани као чињенице и правила, а сваки Даталог код може бити поново написан тако да се изгубе они предикатски симболи који имају вишеструке улоге. 

 ?- predak(Marko,X).

Последњи упит тражи све особе којима је особа са именом Marko предак, и повратна вредност биће Marija и Zoran уколико се постави у Даталог систему који има чињенице и правила дефинисана у овом примеру.

Системи који имплементирају Даталог

[уреди | уреди извор]

Ево кратке листе система који су или базирани на Даталогу или имају Даталог интерпретатор:

Бесплатан софтвер

[уреди | уреди извор]
Написан у Име система Могућност тестирања Спољашња база података Опис Лиценца
Јаva IRIS[9] да[10] IRIS наслеђује Даталог функционалне симболе, уграђене предикате, локално раслојене или слојевите логичке програме (који користе Даталог семантику), несигурна правила и XML шеме типова података. (GNU LGPL v2.1).
Jena семантички фрејмворк за Веб који укључује имплементацију Даталога, што дефинише OWL и представља подршку за RDFS.[11] (Apache v2)
SociaLite SociaLite је варијанта Даталога која се користи у Странфорду за анализу великих графова. (Apache v2)
Graal[12] Graal је Јава алат посвећен упитима у базу знања у оквиру фрејмворка егзистенцијалних правила, званог Datalog+/-. (CeCILL v2.1)
C XSB логичко програмирање и дедуктивне базе података за Unix и Windows (GNU LGPL).
C++ Inter4QL[13] јавно доступан интерпретатор у командној линији за Datalog-like 4QL упитни језик имплементиран у програмском језику C++ за Windows, Mac OS X и Linux. Негација је дозвољена у главама и телима правила као и у рекурзији. (GNU GPL v3).
Пајтон pyDatalog 11 дијалеката SQL-а додаје логичко програмирање у пајтон алате. Може да покреће логичке упите у базе података или пајтон објекте, а и да користи логичке клаузе, како би се дефинисало понашање класа у пајтону. (GNU LGPL)
Lua Datalog[14] да[15] за дедуктивне базе података. (GNU LGPL).
Prolog DES[16] јавно доступна имплементација која може да се користи за курсеве на којима се учи Даталог. (GNU LGPL).
Clojure Cascalog Hadoop библиотека Clojure за упите над подацима чуваним на Hadoop кластерима. (Apache).
Clojure Datalog библиотека која имплементира неке од аспеката Даталога. (Eclipse Public License 1.0).
Racket Даталог за Racket[17] (GNU LGPL).
Tcl tclbdd[18] имплементација заснована на бинарним дијаграмима одлуке. Направљен за развијање омпимизујућег компилатора за Tcl. (BSD).
У осталим непознатим језицима bddbddb[19] имплементација Даталога је урађена на Универзитету Станфорд. Највише је коришћена за упите над Јава бајт кодом укључујући и неке веће Јава програме. (GNU LGPL).
ConceptBase[20] дедуктивна и објектно-оријентисана база података за систем који је заснован на Даталог упитном евалуатору. Највише се користи за моделовање и метамоделовање. (FreeBSD-style license). Prolog, Java.

Софтвер који није бесплатан

[уреди | уреди извор]
  • Datomic база података направљена за израду скалабилних, флексибилних и паметних апликација које могу бити покренуте на свим новим "облак" архитектурама, а која користи Даталог као упитни језик.
  • DLV је комерцијални Даталог додатак који подржава дисјунктивне главе клауза.
  • FoundationDB нуди бесплатну базу података за повезивање са pyDatalog, са упутствима за њено коришћење.[21]
  • LogicBlox, комерцијална имплементација Даталога коришћена за Веб малопродају и за апликације за осигурање.
  • .QL, је комерцијална објектно-оријентисана варијанта креирана од стране компаније Semmle.[22]
  • SecPAL је језик којим је написана политика сигурности развијена у Мајкрософта.[23]

Референце

[уреди | уреди извор]
  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’, ур. (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, стр. 305 
  4. ^ „Datalog”. Архивирано из оригинала 25. 03. 2017. г. Приступљено 15. 04. 2016. 
  5. ^ Bancilhon. „Magic sets and other strange ways to implement logic programs” (PDF). PT: UNL. Архивирано из оригинала (PDF) 08. 03. 2012. г. Приступљено 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, Архивирано из оригинала 11. 03. 2016. г., Приступљено 15. 04. 2016 
  10. ^ „IRIS demo”. Архивирано из оригинала 12. 05. 2016. г. Приступљено 15. 04. 2016. 
  11. ^ „Jena”. Source forge. 
  12. ^ Graal library 
  13. ^ 4QL 
  14. ^ Ramsdell, „Datalog”, Tools, NEU, Архивирано из оригинала 11. 01. 2011. г., Приступљено 15. 04. 2016 
  15. ^ Sangkok, Y, „Wrapper”, Mitre Datalog, Git hub [мртва веза], (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. Приступљено 29. 12. 2015. [мртва веза]
  19. ^ „bddbddb”, Source forge 
  20. ^ ConceptBase 
  21. ^ FoundationDB Datalog Tutorial 
  22. ^ Semmle 
  23. ^ „SecPAL”. Microsoft Research. Архивирано из оригинала 23. 02. 2007. г. Приступљено 15. 04. 2016. 

Литература

[уреди | уреди извор]
Преузето из „https://sr.wikipedia.org/w/index.php?title=Даталог&oldid=27673385”