Datalog

Datalog is a database query language that syntactically is a subset of Prolog. Its origins date back to around 1978 when

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Herve Gallaire and Jack Minker organized a workshop on logic

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

and databases.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In contrast to Prolog, it

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:#disallows complex terms as arguments of predicates, e.g. P(1, 2) is admissible but not P(f1(1), 2),

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:#imposes certain stratification restrictions on the use of negation and recursion, and

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:# can be efficiently evaluated by a bottom-up strategy yielding finite results in finite time.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Datalog was popular in academic database research but never succeeded in becoming part of a commercial database system even though it has its advantages over standard query languages like SQL. In particular, it has clean semantics and allows recursive query definitions.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Recently, the SUIF group at Stanford developed an application called bddbddb, which implements Datalog to query Java bytecode. They have demonstrated a number of uses for this system, including points-to analysis on large Java programs.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Database: A database is an organized collection of data. The term originated within the computer industry, but its meaning has been broadened by popular use, to the extent that the European Database Directive (which creates intellectual property rights for databases) includes non-electronic databases within i...

Prolog: Prolog is a logic programming language. The name Prolog is taken from programmation en logique (French for "logic programming"). It was created by Alain Colmerauer and Robert Kowalski around 1972. It was an attempt to make a programming language that enabled the expression of logic instead of carefu...

1978: 1978 was a common year starting on Sunday (the link is to a full 1978 calendar)....