## 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.