Корисник:MilosivanaMATF/sandbox

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

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

Даталог је програмски језик направљен још са заснивањем логичког програмирања, али постаје засебна област око 1977. године када Hervé Gallaire и Jack Minker организатор радионице логике и база података.[2] David Maier је професор коме се приписује ковање термина Даталог.[3]

Карактеристике, ограничења и проширења[уреди | уреди извор]

За разлику од Пролога, наредбе у Даталогу могу бити сложене у било ком редоследу. Осим тога, Даталог упити на коначним скуповима гарантују завршетак извршавања тако да Даталог нема оператор cut који има програмски језик Пролог. Unlike in Prolog, statements of a Datalog program can be stated in any order. Furthermore, Datalog queries on finite sets are guaranteed to so Datalog does not have Prolog's cut operator. This makes Datalog a truly declarative language.

In contrast to Prolog, Datalog

  1. disallows complex terms as arguments of predicates, e.g., p (1, 2) is admissible but not p (f (1), 2),
  2. imposes certain stratification restrictions on the use of negation and recursion,
  3. requires that every variable that appears in the head of a clause also appears in a nonarithmetic positive (i.e. not negated) literal in the body of the clause,
  4. requires that every variable appearing in a negative literal in the body of a clause also appears in some positive literal in the body of the clause[4]

Query evaluation with Datalog is based on first order logic, and is thus sound and complete. However, Datalog is not Turing complete, and is thus used as a domain-specific language that can take advantage of efficient algorithms developed for query resolution. Indeed, various methods have been proposed to efficiently perform queries, e.g., the Magic Sets algorithm,[5] tabled logic programming[6] or SLG resolution.[7]

Some widely used database systems include ideas and algorithms developed for Datalog. For example, the SQL:1999 standard includes recursive queries, and the Magic Sets algorithm (initially developed for the faster evaluation of Datalog queries) is implemented in IBM's DB2.[8] Moreover, Datalog engines are behind specialised database systems such as Intellidimension's database for the semantic web.[тражи се извор]

Several extensions have been made to Datalog, e.g., to support aggregate functions, to allow object-oriented programming, or to allow disjunctions as heads of clauses. These extensions have significant impacts on the definition of Datalog's semantics and on the implementation of a corresponding Datalog interpreter.

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

Example Datalog program: 

 parent(bill, mary).
 parent(mary, john).

These two lines define two facts, i.e. things that always hold. They can be intuitively understood as: the parent of mary is bill and the parent of john is mary. 

 ancestor(X,Y) :- parent(X,Y).
 ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y).

These two lines describe the rules that define the ancestor relationship. A rule consists of two main parts separated by the :- symbol. The part to the left of this symbol is the head of the rule, the part to the right is the body. A rule is read (and can be intuitively understood) as <head> if it is known that <body>. Uppercase letters stand for variables. Hence in the example the first rule can be read as X is the ancestor of Y if it is known that X is the parent of Y. And the second rule as X is the ancestor of Y if it is known that X is the parent of some Z and Z is the ancestor of Y. The ordering of the clauses is irrelevant in Datalog in contrast to Prolog which depends on the ordering of clauses for computing the result of the query call.

Datalog distinguishes between Extensional predicate symbols (defined by facts) and intensional predicate symbols (defined by rules).[9] In the example above ancestor is an intensional predicate symbol, and parent is extensional. Predicates may also be defined by facts and rules and therefore neither be purely extensional nor intensional, but any Datalog program can be rewritten into an equivalent program without such predicate symbols with duplicate roles. 

 ?- ancestor(bill,X).

The query above asks for all that bill is ancestor of, and would return mary and john when posed against a Datalog system containing the facts and rules described above.

Systems implementing Datalog[уреди | уреди извор]

Here is a short list of systems that are either based on Datalog or provide a Datalog interpreter:

Free software/Open source[уреди | уреди извор]

Written in Name Try it online External Database Description Licence
In Java IRIS[10] yes[11] IRIS extends Datalog with function symbols, built-in predicates, locally stratified or un-stratified logic programs (using the well-founded semantics), unsafe rules and XML schema data types (GNU LGPL v2.1).
Jena a Semantic Web framework which includes a Datalog implementation as part of its general purpose rule engine, which provides OWL and RDFS support.[12] (Apache v2)
SociaLite[13] SociaLite is a datalog variant for large-scale graph analysis developed in Stanford (Apache v2)
Graal[14] Graal is a Java toolkit dedicated to querying knowledge bases within the framework of existential rules, aka Datalog+/-. (CeCILL v2.1)
In C XSB a logic programming and deductive database system for Unix and Microsoft Windows (GNU LGPL).
In C++ Inter4QL[15] an open-source command-line interpreter of Datalog-like 4QL query language implemented in C++ for Windows, Mac OS X and Linux. Negation is allowed in heads and bodies of rules as well as in recursion (GNU GPL v3).
In Python pyDatalog 11 dialects of SQL adds logic programming to python's toolbox. It can run logic queries on databases or python objects, and use logic clauses to define the behavior of python classes. (GNU LGPL)
In Lua Datalog[16] yes[17] a lightweight deductive database system. (GNU LGPL).
In Prolog DES[18] an open-source implementation to be used for teaching Datalog in courses (GNU LGPL).
In Clojure Cascalog Hadoop a Clojure library for querying data stored on Hadoop clusters (Apache).
Clojure Datalog a contributed library implementing aspects of Datalog (Eclipse Public License 1.0).
In Racket Datalog for Racket[19] (GNU LGPL).
In Tcl tclbdd[20] Implementation based on binary decision diagrams. Built to support development of an optimizing compiler for Tcl. (BSD).
In other or unknown languages bddbddb[21] an implementation of Datalog done at Stanford University. It is mainly used to query Java bytecode including points-to analysis on large Java programs (GNU LGPL).
ConceptBase[22] a deductive and object-oriented database system based on a Datalog query evaluator. It is mainly used for conceptual modeling and metamodeling (FreeBSD-style license). Prolog, Java.

Софтвер који није бесплатан[уреди | уреди извор]

  • Datomic is a distributed database designed to enable scalable, flexible and intelligent applications, running on new cloud architectures. It uses Datalog as the query language.
  • DLV is a commercial Datalog extension that supports disjunctive head clauses.
  • FoundationDB provides a free-of-charge database binding for pyDatalog, with a tutorial on its use.[23]
  • LogicBlox, a commercial implementation of Datalog used for web-based retail planning and insurance applications.
  • .QL, a commercial object-oriented variant of Datalog created by Semmle.[24]
  • SecPAL a security policy language developed by Microsoft Research.[25]
  • StrixDB: a commercial RDF graph store, SPARQL compliant with Lua API and Datalog inference capabilities. Could be used as httpd (Apache HTTP Server) module or standalone (although beta versions are under the Perl Artistic License 2.0).

Види такође[уреди | уреди извор]

Референце[уреди | уреди извор]

  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. ^ „Efficient top-down computation of queries under the well-founded semantics” (PDF). 
  8. ^ Gryz; Guo; Liu; Zuzarte. „Query sampling in DB2 Universal Database” (PDF). 
  9. ^ Lifschitz. „Datalog Programs and Their Stable Models”. DE: Springer. 
  10. ^ Iris reasoner .
  11. ^ IRIS demo
  12. ^ „Jena”. Source forge. 
  13. ^ SociaLite homepage .
  14. ^ Graal library .
  15. ^ 4QL .
  16. ^ Ramsdell, „Datalog”, Tools, NEU .
  17. ^ Sangkok, Y, „Wrapper”, Mitre Datalog, Git hub , (compiled to JavaScript).
  18. ^ Saenz-Perez, DES: A Deductive Database System, ES: ENTCS .
  19. ^ „Datalog”, Racket (technical documentation) .
  20. ^ 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. 
  21. ^ „bddbddb”, Source forge .
  22. ^ ConceptBase .
  23. ^ FoundationDB Datalog Tutorial .
  24. ^ Semmle .
  25. ^ „SecPAL”. Microsoft Research. 

Библиографија[уреди | уреди извор]

За додатно читање[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=Корисник:MilosivanaMATF/sandbox&oldid=22895626”