Correctness verification of query results is an important security concern in data outsourcing scenarios. In previous approaches, the correctness verification was impossible in real applications due to its high overhead. A trust-based approach is proposed here to reduce the correctness verification overhead which relies on the previous positive behavior of service provider. A client maintains a trust value for service provider showing the history of service provider comportment. Considering the trust value, the client selects a portion of query result randomly, and forwards it toward the data owner as a result-proof request. The data owner responses to the correctness of the result-proof request using a bloom filter structure. Based on the result-proof response and the trust in the service provider, the client decides whether to accept or reject its query result. In terms of performance, this approach outperforms previous approaches since it does not contain signature overhead in the verification process (which is presented by simulation results). In terms of correctness, this approach is modeled using a transition system and the correctness properties are verified through the Linear Temporal Logic.