Relevant Links:
Univ. of Évora
Évora (in Portuguese)

APPIA-GULP-PRODE 2001
2001 JOINT CONFERENCE ON DECLARATIVE PROGRAMMING

Invited Talk -- Domenico Sacca

Search queries in DATALOG: complexity and tractability

by Domenico Sacca', DEIS-UNICAL & ISI-CNR, 87030 Rende (CS), Italy, sacca@unical.it

Designing declarative, logic-oriented database languages for wider application domains has been a key motivation of much of the research on databases and knowledge bases in the past years. The introduction of DATALOG represented a major breakthrough in this line of work. Unfortunately, the basic DATALOG language (without negation and function symbols) or the version with stratified negation are severely limited in their expressive power and cannot express many of the queries of practical interest.

A dramatic leap in expressive power is provided by the concept of stable model, which has emerged as the compendium of many concepts and theories developed over the years by AI researchers working on nonmonotonic reasoning, default theories and autoepistemic logic. This gain in expressive power, however, is not without complications: 1) the nondeterministic nature of such semantics that follows from the fact that a program can have several stable models; 2) the usage of unrestricted negation in programs is often neither simple nor intuitive 3) computational complexity of stable models blows up not only with hard queries but also with polynomial one.

The drawback of the first point can be turned into an advantage as the existence of several alternative stable models for a DATALOG program can be exploited to express search queries in a purely declarative framework. The other two points remain strong limitations in the usage of stable model semantics in practical application domains. A solution we envision is a language where the usage of stable model semantics is disciplined to avoid both undefinedness and unnecessary computational complexity, and to refrain from abstruse forms of unstratified negation. Thus we propose a language, DATALOG/NOT, whose core is stratified DATALOG, that is extended with controlled types of non-stratified negation, hardwired into ad-hoc constructs such as the choice. The disciplined structure of negation in the language and its resulting amenability to efficient implementation implies that every program in our language has at least one total stable model, and each stable model can be computed in polynomial time. As a stable models of a program implementing a search query is not necessarily "feasable" (thus it could not correspond to a query solution), complexity depends on finding a feasible stable model.

The aim of this talk is to supply a systematic analysis of structural properties of complexity classes of search queries in DATALOG/NOT. An important question we address in the talk will be: which classes of non-deterministic queries can be refined by a polynomial-time single-valued function, i.e., can be executed in polynomial-time? A class enjoying this property is NQPTIME, that is, the class of all queries computed by polynomial-time transducers such that for each input, each branch of the transducer's computation halts into an accepting state. However, this class suffers from a severe drawback: while finding a solution is done in polynomial-time, testing whether a given string is a solution is not --- the typical situation is the reverse: the hard part is finding a result rather than testing it! We then introduce a new class of search queries whose solutions are both computable and verifiable in polynomial time. We shall finally show how to express queries in this class using DATALOG/NOT.