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

Даталог — разлика између измена

С Википедије, слободне енциклопедије
Садржај обрисан Садржај додат
Нова страница: '''Даталог''' je програмски језик Декларативно програмирање|декларативне…
(нема разлике)

Верзија на датум 15. април 2016. у 04:27

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

Даталог је програмски језик направљен још од оснивања логичког програмирања, али постаје засебна област око 1977. године када Hervé Gallaire и Jack Minker организују радионицу Логика и базе података.[2] David Maier је професор коме се приписује ковање термина Даталог.[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[12] SociaLite је варијанта Даталога која се користи у Странфорду за анализу великих графова. (Apache v2)
Graal[13] Graal је Јава алат посвећен упитима у базу знања у оквиру фрејмворка егзистенцијалних правила, званог Datalog+/-. (CeCILL v2.1)
C XSB логичко програмирање и дедуктивне базе података за Unix и MS Windows (GNU LGPL).
C++ Inter4QL[14] јавно доступан интерпретатор у командној линији за Datalog-like 4QL упитни језик имплементиран у програмском језику C++ за Windows, Mac OS X и Linux. Негација је дозвољена у главама и телима правила као и у рекурзији. (GNU GPL v3).
Пајтон pyDatalog 11 дијалеката SQL-а додаје логичко програмирање у пајтон алате. Може да покреће логичке упите у базе података или пајтон објекте, а и да користи логичке клаузе, како би се дефинисало понашање класа у пајтону. (GNU LGPL)
Lua Datalog[15] да[16] за дедуктивне базе података. (GNU LGPL).
Prolog DES[17] јавно доступна имплементација која може да се користи за курсеве на којима се учи Даталог. (GNU LGPL).
Clojure Cascalog Hadoop библиотека Clojure за упите над подацима чуваним на Hadoop кластерима. (Apache).
Clojure Datalog библиотека која имплементира неке од аспеката Даталога. (Eclipse Public License 1.0).
Racket Даталог за Racket[18] (GNU LGPL).
Tcl tclbdd[19] имплементација заснована на бинарним дијаграмима одлуке. Направљен за развијање омпимизујућег компилатора за Tcl. (BSD).
У осталим непознатим језицима bddbddb[20] имплементација Даталога је урађена на Универзитету Станфорд. Највише је коришћена за упите над Јава бајт кодом укључујући и неке веће Јава програме. (GNU LGPL).
ConceptBase[21] дедуктивна и објектно-оријентисана база података за систем који је заснован на Даталог упитном евалуатору. Највише се користи за моделовање и метамоделовање. (FreeBSD-style license). Prolog, Java.

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

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


Референце

  1. ^ Huang, Green, and 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
  5. ^ Bancilhon. „Magic sets and other strange ways to implement logic programs” (PDF). PT: UNL. 
  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 .
  10. ^ IRIS demo
  11. ^ „Jena”. Source forge. 
  12. ^ SociaLite homepage .
  13. ^ Graal library .
  14. ^ 4QL .
  15. ^ Ramsdell, „Datalog”, Tools, NEU .
  16. ^ Sangkok, Y, „Wrapper”, Mitre Datalog, Git hub , (compiled to JavaScript).
  17. ^ Saenz-Perez, DES: A Deductive Database System, ES: ENTCS .
  18. ^ „Datalog”, Racket (technical documentation) .
  19. ^ Kenny, Kevin B (12—14. 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. 
  20. ^ „bddbddb”, Source forge .
  21. ^ ConceptBase .
  22. ^ FoundationDB Datalog Tutorial .
  23. ^ Semmle .
  24. ^ „SecPAL”. Microsoft Research. 

Библиографија

За додатно читање