Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

Complexity of DATALOG on dense linear orders

DATALOG is a modification of logic programming to the database context and has become a common database query language in database theory. While most research has concentrated on finite databases, we consider DATALOG on infinite structures. One motivation for this is, that DATALOG can be seen as a restriction of constraint logic programming -- which deals with infinite structures -- and it could be used to learn more about the relation between the complexity of constraint logic program evaluation and the structure of the constraints involved. This talk will deal with strict linear orders as constraints, or EDBs in the DATALOG context, and it will be shown that DATALOG on dense strict linear orders has EXPTIME-complete program complexity, and that monadic DATALOG has PTIME-complete program complexity on strict linear orders. Some of these results are transfers of the results for DATALOG on finite structures while others demonstrate techniques for evaulating DATALOG programs on infinite structures.