Datalog

Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties from Prolog. It is often used as a query language for deductive databases. Datalog has been applied to problems in data integration, networking, program analysis, and more. A Datalog program consists of facts, which are statements that are held to be true, and rules, which say how to deduce new facts from known facts. For example, here are two facts that mean xerces is a parent of brooke and brooke is a parent of damocles: parent(xerces, brooke). parent(brooke, damocles). The names are written in lowercase because strings beginning with an uppercase letter stand for variables. Here are two rules: ancestor(X, Y) :- parent(X, Y). ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y). The :- symbol is read as "if", and the comma is read "and", so these rules mean: 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. The meaning of a program is defined to be the set of all of the facts that can be deduced using the initial facts and the rules. This program's meaning is given by the following facts: parent(xerces, brooke). parent(brooke, damocles). ancestor(xerces, brooke). ancestor(brooke, damocles). ancestor(xerces, damocles). Some Datalog implementations don't deduce all possible facts, but instead answer queries: ?- ancestor(xerces, X). This query asks: Who are all the X that xerces is an ancestor of? For this example, it would return brooke and damocles. The non-recursive subset of Datalog is closely related to query languages for relational databases, such as SQL. The following table maps between Datalog, relational algebra, and SQL concepts: More formally, non-recursive Datalog corresponds precisely to unions of conjunctive queries, or equivalently, negation-free relational algebra. s(x, y). t(y). r(A, B) :- s(A, B), t(B).