Recent developments in the design of database systems include proposals of several extensions to the basic model of relational database systems. Such a system is presented in this paper. The system is based on QUEL+ which extends the query language QUEL by introducing among others database procedures as full fledged objects. We briefly describe a variation of the original INGRES decomposition algorithm and then some ideas that can improve the performance of a system that supports procedures are discussed. First, we examine the idea of storing results of previously processed procedures in secondary storage (caching). Using a cache, the cost of processing a query can be reduced by preventing multiple evaluations of the same procedure. Problems associated with cache organizations, such as replacement policies and validation schemes are examined. Another means for reducing the execution cost of queries is indexing. Indexing results of procedures can be done through coventional schemes. However, at any given time, it is highly probable that not all procedures stored in a relation have been evaluated which makes known indexing techniques useless, since the latter assume that all values are known. As a solution to that problem, a new indexing scheme, Partial Indexing, is proposed and analyzed.