This research explores a fundamental revision of the concept of deductive databases. The new approach, Complexity Tailored Information Systems, 1) allows a variety of possible answers to any given query, 2) produces answers determined both by the query and by the computational resources of the system, and 3) uses meaningful approximations to the precise answers, when determination of a precise answer would be impossible because of lack of time or computational resources. The significance of this research is that database systems will increasingly be required to function in real-time and draw on large knowledge resources to solve complex queries. Effective alternatives to exhaustive search and deduction will be vital.