Abstract
We consider a generalization of instance retrieval over knowledge bases that provides users with assertions in which descriptions of qualifying objects are given in addition to their identi?ers. Notably, this involves a transfer of basic database paradigms involving caching and query rewriting in the context of an assertion retrieval algebra. We present an optimization framework for this algebra, with a focus on ?nding plans that avoid any need for general knowledge base reasoning at query execution time when suf?cient cached results of earlier requests exist.