Foto Aftrati

National Technical University of Athens

Datalog Queries on Graphs

DIMACS Center - Room 431

Busch Campus

Piscataway, New Jersey

May 31, 2:30 p.m.

Abstract:

Datalog is the query language of logic programs; it can be thought of as Prolog without function symbols. It extends a simple fragment of first order logic by incorporating recursion to capture a larger class of queries (such as transitive closure). A Datalog program is defined to be a collection of negation-free function-free Horn clauses. Datalog programs can be viewed as a declarative query language with the fixpoint semantics. The expressive power of Datalog and its extensions (with inequalities and/or negation) has been investigated over the past ten years and is well understood in certain cases. Specifically, if only ordered databases are considered , then Datalog with negation on EDB predicates expresses all polynomial time queries. On the other hand, there are simple queries (e.g., the even cardinality query) which are easily shown not to be expressible in Datalog through certain monotonicity properties. The talk will address questions about the expressive power of Datalog on databases consisting only of binary relations. The main result that will be presented is : the hierarchy that is formed by varying the maximum arity allowed on the recursively defined predicates is strict even in the case where EDB predicates are fixed. We shall discuss technical tools that are useful in proving expressibility results for Datalog programs applied on simple databases such as graphs.