Datalog

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

Related Topics:
Database - Prolog - 1978

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~