Two fundamental ways for dealing with the growing complexity of query processing in deductive database systems, Complexity Tailored Design and Complexity Tailored Query Answering, are investigated. In Complexity Tailored Design, the acceptance of database updates is based on the estimation of future complexity of query processing. In Complexity Tailored Query Answering, approximate answers are provided due to resource constraints, e.g. not having enough time to compute the full answer. Standard proof techniques used in query evaluation are modified in such a way that the computation of the answer to a given query can be stopped before its completion and the meaningful partial answer can still be returned. This research leads to new methodologies of query processing and database design in the presence of incomplete information or limited computational resources.
