The web of linked data represents a globally distributed dataspace, which can be queried using the SPARQL query language. However, with the growth in size and complexity of the web of linked data, it becomes impractical for the user to know enough about its structure and semantics for the user queries to produce enough answers. Moreover, there is a prevalence of unreliable data which can dominate the query results misleading the users and software agents. These problems are addressed in the paper by making use of ontologies available on the web of linked data to produce approximate results and also by presenting a trust model that associates RDF statements with trust values, which is used to give prominence to trustworthy data. Trustworthy approximate results can be generated by performing the relaxation steps at compile-time leading to the generation of multiple relaxed queries that are sorted in decreasing order of their similarity scores with the original query and executed. During their execution the trust scores of RDF data fetched are computed. However, the relaxed queries generated have conditions in common and we propose that by performing trust-based relaxations on-the-fly at runtime, the shared data between several relaxed queries need not be fetched repeatedly. Thus, the trust-based relaxation steps are integrated with the query execution itself resulting in performance benefits. Further opportunities for optimizations during query execution are identified and are used to prune relaxation steps which do not produce results. The implementation of our approach demonstrates its efficacy.