Information Retrieval systems such as web search engines offer convenient keyword-based search interfaces. In contrast, relational database systems require the user to learn SQL and to know the schema of the underlying data even to pose simple searches. We propose an architecture that supports highly efficient keyword-based search over relational databases: A relational database is "crawled" in advance, text-indexing virtual documents that correspond to interconnected database content. At query time, the text index supports keyword-based searches with interactive response, identifying database objects corresponding to the virtual documents matching the query. Our system, EKSO, creates virtual documents from joining relational tuples and uses the DB2 Net Search Extender for indexing and keyword-search processing. Experimental results show that index size is manageable and database updates (which are propagated incrementally as recomputed virtual documents to the text index) do not significantly hinder query performance. We also present a user study confirming the superiority of keyword-based search over SQL for a range of database retrieval tasks.