Many emerging applications operate on continuous unbounded data streams and need real-time data services. Providing deadline guarantees for queries over dynamic data streams is a challenging problem due to bursty stream rates and time-varying contents. This paper presents a prediction-based QoS management scheme for real-time data stream query processing in distributed environments. The prediction-based QoS management scheme features query workload estimators, which predict the query workload using execution time profiling and input data sampling. In this paper, we apply the prediction-based technique to select the proper propagation schemes for data streams and intermediate query results in distributed environments. The performance study demonstrates that the proposed solution tolerates dramatic workload fluctuations and saves significant amounts of CPU time and network bandwidth with little overhead.