Keyword Search Over Relational Databases(KSORD) has attracted much research interest since casual users or Web users can use the techniques to easily access databases through free-form keyword queries, just like searching the Web. However, it is a critical issue that how to improve the performance of KSORD systems. In this paper, we focus on the performance improvement of schema-graph-based online KSORD systems and propose a novel Preprocessing Candidate Network(PreCN) approach to support efficient keyword search over relational databases. Based on a given database schema, PreCN reduces CN generation time by preprocessing the maximum Tuple Sets Graph(G _ts ) to generate CNs in advance and to store them in the database. When a user query comes, its CNs will be quickly retrieved from the database instead of being temporarily generated through a breadth-first traversal of its G _ts . Extensive experiments show that the approach PreCN is efficient and effective.