Methods and apparatus are provided for rewriting view queries into equivalent queries on the source document. According to one aspect of the invention, methods are provided for processing a view query on a database view. The method comprises the steps of translating the view query to a mixed finite state automata representation of a document query on one or more documents underlying the database view; and evaluating the document query on the one or more documents to obtain a result to the view query. The view query may be, for example, a regular XPath query.