Real-time scheduling for continuous queries with deadlines

ABSTRACT

Many stream-based applications have real-time performance requirements for continuous queries over time-varying data streams. In order to address this challenge, a real-time continuous query model is presented to handle multiple queries with timing constraints. In this model, the execution of one tuple passing through an operator path is modeled as a real-time task instance. A fine-grained scheduling strategy named OP-EDF is proposed for real-time scheduling, which schedules the operator path with the earliest deadline of the waiting tuples at any time slot. The experimental results show that the proposed continuous query model and scheduling algorithm are effective in real-time query processing for data streams with bursty arrival rates.

REFERENCES

• 1: Brian Babcock , Shivnath Babu , Rajeev Motwani , Mayur Datar, Chain: operator scheduling for memory minimization in data stream systems, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872789]
• 2: Don Carney , Uğur Çetintemel , Alex Rasin , Stan Zdonik , Mitch Cherniack , Mike Stonebraker, Operator scheduling in a data stream manager, Proceedings of the 29th international conference on Very large data bases, p.838-849, September 09-12, 2003, Berlin, Germany
• 3: Yuan Wei , Sang H. Son , John A. Stankovic, RTSTREAM: Real-Time Query Processing for Data Streams, Proceedings of the Ninth IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing, p.141-150, April 24-26, 2006 [doi>10.1109/ISORC.2006.68]
• 4: Sven Schmidt , Thomas Legler , Daniel Schaller , Wolfgang Lehner, Real-Time Scheduling for Data Stream Management Systems, Proceedings of the 17th Euromicro Conference on Real-Time Systems, p.167-176, July 06-08, 2005 [doi>10.1109/ECRTS.2005.24]
• 5: Q. C. Jiang and S. Chakravarthy. Scheduling Strategies for Processing Continuous Queries over Streams. In Proc. of the 21st British National Conf. on Databases, 2004.16--30.
• 6: M. A. Sharaf , P. K. Chrysanthis , A. Labrinidis, Preemptive rate-based operator scheduling in a data stream management system, Proceedings of the ACS/IEEE 2005 International Conference on Computer Systems and Applications, p.46-I, January 03-06, 2005

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Keywords:
continuous query, data stream, real-time schedule