Datalog is a query and rule language for deductive databases that syntactically is a subset of Prolog. Its origins date back to the beginnning of logic programming, but it became prominent as a separate area around 1978 when Hervé Gallaire and Jack Minker organized a workshop on logic and databases. The term Datalog was coined in the mid 1980's by a group of researchers interested in database theory. Query languages are computer languages used to make queries into databases and information systems. ... A deductive database system is a database system which can make deductions (ie: infer additional rules or facts) based on rules and facts stored in the (deductive) database. ... Prolog is a logic programming language. ... Logic programming (which might better be called logical programming by analogy with mathematical programming and linear programming) is, in its broadest sense, the use of mathematical logic for computer programming. ... 1978 (MCMLXXVIII) was a common year starting on Sunday. ... Logic, from Classical Greek λόγος logos (the word), is the study of patterns found in reasoning. ... The term database originated within the computer industry. ...

Features, limitations and extensions

Query evaluation with Datalog is sound and complete and can be done efficiently even for large databases. Query evaluation is usually done using bottom up strategies. For restricted forms of datalog that don't allow any function symbols, safety of query evaluation is guaranteed. In formal logic and related branches of mathematics, a functional predicate, or function symbol, is a logical symbol that may be applied to an object term to produce another object term. ...

In contrast to Prolog, it

1. disallows complex terms as arguments of predicates, e.g. P(1, 2) is admissible but not P(f1(1), 2),
2. imposes certain stratification restrictions on the use of negation and recursion, and
3. only allows range restricted variables, i.e. each variable in the conclusion of a rule must also appear in a not negated clause in the premise of this rule.

Datalog was popular in academic database research but never succeeded in becoming part of a commercial database system. Advantages of Datalog over SQL such as the clean semantics or recursive queries were not sufficient. Modern database systems, however, include ideas and algorithms developed for Datalog: the SQL99 standard, which includes recursive queries and the Magic Sets algorithm initially developed for the faster evaluation of Datalog queries, is implemented in IBMs DB2. Stratification in mathematical logic In mathematical logic, stratification is any consistent assignment of numbers to predicate symbols guaranteeing that a unique formal interpretation of a logical theory exists. ... SQL (commonly expanded to Structured Query Language — see History for the terms derivation) is the most popular computer language used to create, modify, retrieve and manipulate data from relational database management systems. ... DB2 is IBMs line of RDBMS (or, as IBM now calls it, data server) software products within IBMs broader Information Management software line. ...

Extensions to Datalog were made to make it object-oriented, or to allow disjunctions as heads of clauses. Both extensions have major impacts on the definition of the semantics and the implementation of a corresponding Datalog interpreter. Object-oriented programming (OOP) is a computer programming paradigm in which a software system is modeled as a set of objects that interact with each other. ... Logical disjunction (usual symbol or) is a logical operator that results in true if either of the operands is true. ... In logic and declarative programming, a clause is a disjunction of literals and can be interpreted as a (conditional) statement. ...

Example

Example Datalog program:

 parent(bill,mary). parent(mary,john). ancestor(X,Y) :- ancestor(X,Z),ancestor(Z,Y). ancestor(X,Y) :- parent(X,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.

Systems implementing Datalog

Most implementations of Datalog stem from university projects. Here is a short list of a few systems that are either based on Datalog or are providing a Datalog interpreter:

• bddbddb, an implementation of Datalog done at the Stanford University. It is mainly used to query Java bytecode including points-to analysis on large Java programs.

• ConceptBase, a deductive and object-oriented database system based on a Datalog query evaluator. It is mainly used for conceptual modeling and meta-modeling.

• DES, an open-source implementation of Datalog to be used for teaching Datalog in courses.

• DLV, is a a Logic Programming and Deductive Database system which implements Disjunctive Datalog, using a disjunctive version of Answer set programming and adds many useful features also available in commercial database systems and query languages, such as aggregates, ODBC binding, etc.

• XSB, is a Logic Programming and Deductive Database system for Unix and Windows.

• Internet Business Logic, is a Wiki-like system for business rules in open vocabulary, executable English. The rules are automatically translated to and from an extended version of datalog. The underlying rule engine combines forward- and backward-chaining, and is based on the stratified datalog semantics described in "Backchain Iteration: Towards a Practical Inference Method that is Simple Enough to be Proved Terminating, Sound and Complete", Journal of Automated Reasoning, 11:1-22.

• Microsoft SecPAL, Microsoft has recently started using Datalog for a security policy language called SecPAL. SecPAL is a flexible and robust declarative security policy language developed to meet the access control requirements of large-scale Grid Computing Environments.

More implementations are listed at ACM SIGMOD Database Software. ConceptBase is a deductive and object-oriented database management system based on Datalog rather than SQL. It stores all factual information in a single flat data structure called P-facts. ... Answer set programming is a form of declarative programming that is similar in syntax to traditional logic programming and close in semantics to non-monotonic logic. ... Open Database Connectivity (ODBC) is a standard software API for connecting to database management systems (DBMS). ...

See also

• Logic programming
• Answer set programming
• SWRL

This article is part of a series on programming languages. Logic programming (which might better be called logical programming by analogy with mathematical programming and linear programming) is, in its broadest sense, the use of mathematical logic for computer programming. ... Answer set programming is a form of declarative programming that is similar in syntax to traditional logic programming and close in semantics to non-monotonic logic. ... SWRL (Semantic Web Rule Language) is a proposal for a Semantic Web rules-language, combining sublanguages of the OWL Web Ontology Language (OWL DL and Lite) with those of the Rule Markup Language (Unary/Binary Datalog). ...

	Preceding:	Prolog
	Subsequent:	IBM DB2