Keyword search helps users to efficiently get interested information from relational databases, and users are exempted from learning the professional structural query language for relational databases, which greatly reduces the usabilitye threshold. Keyword search over relational databases commonly employs data-graph-based methods which first models a database into a graph and then uses it to identify the minimum Steiner tree. However, the available methods are not able to dynamically optimize query results according to the dynamically changing user interest. In this paper, an ant-colony-optimization-based algorithm is proposed to achieve the task of keyword search over relational databases. Furthermore, a novel approach based on the theory of concept drift is presented to capture the mutation of user interest. In addition, based on concept drift theory and ant colony optimization algorithm, a new algorithm called ACOKS* is proposed to dynamically optimize the search results according to the time-changing user interest, so as to achieve the results in more accordance with user interest. Finally, a prototype is developed to carry out extensive experiments, and the results show that our method can achieve high scalability and perform better than other state-of-the-art methods.