Datalog
Datalog is a declarative logic programming language that syntactically is a subset of Prolog. It is often used as a query language for deductive databases. In recent years, Datalog has found new application in data integration, information extraction, networking, program analysis, security, and cloud computing.[1]
Its origins date back to the beginning of logic programming, but it became prominent as a separate area around 1977 when Hervé Gallaire and Jack Minker organized a workshop on logic and databases.[2] David Maier is credited with coining the term Datalog.[3]
Features, limitations and extensions
Unlike in Prolog, statements of a Datalog program can be stated in any order. Furthermore, Datalog queries on finite sets are guaranteed to terminate, so Datalog does not have Prolog's cut operator. This makes Datalog a fully declarative language.
In contrast to Prolog, Datalog
- disallows complex terms as arguments of predicates, e.g., p (1, 2) is admissible but not p (f (1), 2),
- imposes certain stratification restrictions on the use of negation and recursion,
- 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,
- 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.[citation needed]
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
These two lines define two facts, i.e. things that always hold:
parent(bill, mary).
parent(mary, john).
This is what they mean: bill is a parent of mary and mary is a parent of john. The names are written in lowercase because uppercase letters stand for variables.
These two lines define rules, which define how new facts can be inferred from known facts.
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
meaning:
- X is an ancestor of Y if X is a parent of Y.
- X is an ancestor of Y if X is a parent of some Z, and Z is an ancestor of Y.
This line is a query:
?- ancestor(bill, X).
It asks the following: Who are all the X that bill is an ancestor of? It would return mary and john when posed against a Datalog system containing the facts and rules described above.
More about rules: a rule has a :- symbol in the middle: the part to the left of this symbol is the head of the rule, the part to the right is the body. A rule reads like this: <head> is known to be true if it is known that <body> is true. Uppercase letters in rules stand for variables: in the example, we don't know who X or Y are, but some X is the ancestor of some Y if that X is the parent of that 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.
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] | 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.[11] | Apache v2 | |||
SociaLite[12] | SociaLite is a datalog variant for large-scale graph analysis developed in Stanford | Apache v2 | |||
Graal[13] | Graal is a Java toolkit dedicated to querying knowledge bases within the framework of existential rules, aka Datalog+/-. | CeCILL v2.1 | |||
Flix[14] | Yes[15] | A functional and logic programming language inspired by Datalog extended with user-defined lattices and monotone filter/transfer functions. | Apache v2 | ||
In C | XSB | A logic programming and deductive database system for Unix and MS Windows with tabling giving Datalog-like termination and efficiency, including incremental evaluation[16] | GNU LGPL | ||
In C++ | Coral[17] | A deductive database system written in C++ with semi-naïve datalog evaluation. Developed 1988-1997. | custom licence, free for non-commercial use | ||
Inter4QL[18] | 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 | |||
RDFox[19] | RDF triple store with Datalog reasoning. Implements the FBF algorithm for incremental evaluation. | custom licence, free for non-commercial use[20] | |||
Souffle[21] | an open-source Datalog-to-C++ compiler converting Datalog into high-performance, parallel C++ code, specifically designed for complex Datalog queries over large data sets as e.g. encountered in the context of static program analysis | UPL v1.0 | |||
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 Ruby | bloom / bud | A Ruby DSL for programming with data-centric constructs, based on the Dedalus extension of Datalog which adds a temporal dimension to the logic. | BSD 3-Clause | ||
In Lua | Datalog[22] | Yes[23] | a lightweight deductive database system. | GNU LGPL | |
In Prolog | DES[24] | 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 | |||
Datascript | in-memory | Immutable database and Datalog query engine that runs in the browser | Eclipse Public License 1.0 | ||
In Racket | Datalog for Racket[25] | GNU LGPL | |||
Datafun[26] | Generalized Datalog on Semilattices | GNU LGPL | |||
In Tcl | tclbdd[27] | Implementation based on binary decision diagrams. Built to support development of an optimizing compiler for Tcl. | BSD | ||
In Haskell | Dyna[28] | Dyna is a declarative programming language for statistical AI programming. The language is based on Datalog, supports both forward and backward chaining, and incremental evaluation. | GNU AGPL v3 | ||
In other or unknown languages | bddbddb[29] | 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[30] | a deductive and object-oriented database system based on a Datalog query evaluator : Prolog for triggered procedures and rewrites, axiomatized Datalog called « Telos » for (meta)modeling. It is mainly used for conceptual modeling and metamodeling | BSD (FreeBSD-style license) Prolog, Java, C++. |
Non-free software
- 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.[31]
- Leapsight Semantic Dataspace (LSD) is a distributed deductive database that offers high availability, fault tolerance, operational simplicity, and scalability. LSD uses Leaplog (a Datalog implementation) for querying and reasoning and was create by Leapsight.[32]
- LogicBlox, a commercial implementation of Datalog used for web-based retail planning and insurance applications.
- Profium Sense is a native RDF compliant graph database written in Java. It provides Datalog evaluation support of user defined rules.
- .QL, a commercial object-oriented variant of Datalog created by Semmle.[33]
- SecPAL a security policy language developed by Microsoft Research.[34]
- Stardog is a graph database, implemented in Java. It provides support for RDF and all OWL 2 profiles providing extensive reasoning capabilities, including datalog evaluation.
- 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).
See also
- Answer set programming
- SWRL
- D (data language specification)
- D4 (programming language)
- Conjunctive query
References
- ^ Huang, Green, and Loo, "Datalog and Emerging applications", SIGMOD 2011 (PDF), UC Davis
{{citation}}
: CS1 maint: multiple names: authors list (link). - ^ Gallaire, Hervé; Minker, John ‘Jack’, eds. (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.
- ^ Abiteboul, Serge; Hull, Richard; Vianu, Victor, Foundations of databases, p. 305.
- ^ Datalog
- ^ Bancilhon. "Magic sets and other strange ways to implement logic programs" (PDF). PT: UNL. Archived from the original (PDF) on 2012-03-08.
{{cite journal}}
: Cite journal requires|journal=
(help); Unknown parameter|deadurl=
ignored (|url-status=
suggested) (help) - ^ Pfenning, Frank; Schuermann, Carsten. "Twelf User's Guide". CMU.
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ "Efficient top-down computation of queries under the well-founded semantics" (PDF).
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ Gryz; Guo; Liu; Zuzarte. "Query sampling in DB2 Universal Database" (PDF).
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ Lifschitz. "Datalog Programs and Their Stable Models". DE: Springer.
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ Iris reasoner.
- ^ "Jena". Source forge.
- ^ SociaLite homepage, archived from the original on 2017-09-11, retrieved 2015-10-12
{{citation}}
: Unknown parameter|dead-url=
ignored (|url-status=
suggested) (help). - ^ Graal library.
- ^ "Flix | The Programming Language". flix.github.io. Retrieved 2017-05-03.
- ^ "Flix | Try Online". flix.github.io. Retrieved 2017-05-03.
- ^ The XSB System, Version 3.7.x, Volume 1: Programmer's Manual (PDF).
- ^ Coral Database Project web page.
- ^ 4QL.
- ^ RDFox web page.
- ^ RDFox licence.
- ^ Souffle Compiler.
- ^ Ramsdell, "Datalog", Tools, NEU.
- ^ Sangkok, Y, "Wrapper", Mitre Datalog, Git hub, (compiled to JavaScript).
- ^ Saenz-Perez, DES: A Deductive Database System, ES: ENTCS.
- ^ "Datalog", Racket (technical documentation).
- ^ "Datafun", Datafun in Racket (Links to paper, talk and github site).
- ^ Kenny, Kevin B (12–14 November 2014). Binary decision diagrams, relational algebra, and Datalog: deductive reasoning for Tcl (PDF). Twenty-first Annual Tcl/Tk Conference. Portland, Oregon. Retrieved 29 December 2015.[permanent dead link]
- ^ "Dyna", Dyna web page, archived from the original on 2016-01-17, retrieved 2016-11-07
{{citation}}
: Unknown parameter|dead-url=
ignored (|url-status=
suggested) (help). - ^ "bddbddb", Source forge.
- ^ ConceptBase.
- ^ FoundationDB Datalog Tutorial, archived from the original on 2013-08-09
{{citation}}
: Unknown parameter|dead-url=
ignored (|url-status=
suggested) (help). - ^ "Leapsight".
- ^ Semmle.
- ^ "SecPAL". Microsoft Research. Archived from the original on 2007-02-23.
{{cite web}}
: Unknown parameter|deadurl=
ignored (|url-status=
suggested) (help)
Bibliography
- Ceri, S.; Gottlob, G.; Tanca, L. (1989), "What you always wanted to know about Datalog (and never dared to ask)", Transactions on Knowledge and Data Engineering, 1 (1), IEEE: 146–66, doi:10.1109/69.43410.
Further reading
- Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007), Finite model theory and its applications, Texts in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, ISBN 978-3-540-00428-8, Zbl 1133.03001