Abstract. We propose a framework for navigation-driven evaluation of virtual mediated views. The approach is based on lazy mediators that translate incoming client navigations on a virtual XML view (or the result of an XML query) into navigations on wrapped sources or lower level mediators. Such a demand-driven approach is inevitable in order to handle up-to-date mediated views of huge Web sources or large query results, which are commonplace when querying the Web. The proposed MIX mediator provides to the client an abstraction of the DOM API, the de facto API to XML documents, hence hiding the non-materialization of the view or the query. We also describe the inherent navigational complexity of queries and view definitions wrt. navigations. Next, we discuss the query/navigation processing aspects of the MIX mediator. The mediator translates a view into an algebraic plan. Then each operator of the algebraic plan acts as a navigation-driven lazy mediator. This allows to characterize the complexity of plans and to compare their navigational complexity.