Declarative Features for Deductive Databases

Deductive databases provide a declarative framework based on first-order logic for writing queries. Entries in the database define the answer to a query without indicating how to answer the query. By allowing recursion, deductive databases yield higher expressive power than classical relational databases. The two main problems addressed in this project are semantics and optimization. This research studies semantics for deductive databases extended with aggregate operators such as ``minimum'' and ``sum.'' Extensions of such semantics to programs with second-order constructs are also considered. The project is assessing how effectively second-order features can be incorporated into present-day relational databases. Optimization techniques for deductive databases with aggregates, both new techniques and extensions of existing strategies are also be investigated. This project will contribute fundamental knowledge about how to provide declarative features, such as aggregation and second-order constructs, within deductive databases.