Executing Semantic Services requires, in contrast to traditional SOAP-based Web Services, frequent read and write accesses to graph-based semantic data stores - for instance, for the evaluation of preconditions or the materialization of service effects. Therefore, the overall performance of semantic service execution, in particular for composite services, is strongly affected by the efficiency of these reads and writes. In this paper we present two data access optimization techniques for semantic data stores: Prepared Queries and Frame Caching. The former reduces the costs for repeated query evaluation, e.g., in loops. The latter provides rapid access to frequently read triples or subgraphs based on materialized views using a Frame-based data structure. The described techniques have been implemented and evaluated on the basis of OSIRIS Next, our open infrastructure for Semantic Service support.