Datalog, also known as database logic, is one of the simplest formalisms that can be used to write rule-based programs; intuitively, Datalog is Prolog without function symbols. Datalog is the language of choice to write knowledge-based applications, by adding rules to a relational database system. However, to be able to use this formalism efficiently, the optimization problem of Datalog programs must be solved. To solve this problem it is desirable to be able to detect when a recursive database logic program is bounded, that is, whether the program is equivalent to a nonrecursive one. This is a central issue in the optimization of Datalog programs. This research project is concerned with the characterization of some classes of bounded Datalog programs when the relational database is consistent with respect to some constraints. The constraints considered in this research are functional dependencies. This research project provides a methodology for more efficient query processing in knowledge-base systems that are being built as extensions of relational database systems. This in turn makes such knowledge-base systems more feasible for use in practice.
